lab util
sleep
-
介紹：主要用來(lái)熟悉下環(huán)境以及代碼結(jié)構(gòu)。
- See
kernel/sysproc.cfor the xv6 kernel code that implements thesleepsystem call (look forsys_sleep),user/user.hfor the C definition ofsleepcallable from a user program, anduser/usys.Sfor the assembler code that jumps from user code into the kernel forsleep.
- See
-
代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-615929.html
#include "kernel/types.h" #include "user/user.h" int main(int argc, char *argv[]) { if (argc <= 1) { fprintf(2, "usage: sleep `time`...\n"); } int tick_num = atoi(argv[1]); sleep(tick_num); exit(0); }
pingpong
-
單個(gè)管道一般用于單向通信，父子進(jìn)程可通過(guò)兩個(gè)管道進(jìn)行雙向通信。（管道詳細(xì)行為參考
primes實(shí)驗(yàn)部分） -
代碼：
#include "kernel/types.h" #include "user/user.h" #define BUFFSIZE 128 void perror_exit(char* err_msg) { fprintf(2, "%s\n", err_msg); exit(-1); } int main(int argc, char *argv[]) { int toson_fd[2]; int toparent_fd[2]; int ret1 = pipe(toson_fd); int ret2 = pipe(toparent_fd); if (ret1 == -1 || ret2 == -1) { perror_exit("pipe error"); } int pid = fork(); if (pid == -1) { // perror_exit("fork error"); } else if (pid == 0) { // child process close(toson_fd[1]); close(toparent_fd[0]); // read from the pipe1 char buf[BUFFSIZE]; int rbytes = read(toson_fd[0], buf, sizeof(buf)); if (rbytes == -1) { perror_exit("read error"); } buf[rbytes] = '\0'; // print the msg from parent fprintf(1, "%d: received %s\n", getpid(), buf); // write response to parent (to pipe2) char resp[4] = "pong"; int ret = write(toparent_fd[1], resp, sizeof(resp)); if (ret == -1) { perror_exit("write error"); } } else { // parent process close(toson_fd[0]); close(toparent_fd[1]); // write to son char msg[4] = "ping"; int ret = write(toson_fd[1], msg, sizeof(msg)); if (ret == -1) { perror_exit("write error"); } // read from son char buf[BUFFSIZE]; int rbytes = read(toparent_fd[0], buf, sizeof(buf)); if (rbytes == -1) { perror_exit("read"); } buf[rbytes] = '\0'; // print the resp from son fprintf(1, "%d: received %s\n", getpid(), buf); } exit(0); }
primes
介紹
實(shí)驗(yàn)要求通過(guò) fork 和 pipe 系統(tǒng)調(diào)用建立起如下素?cái)?shù)篩的 pipeline.
p = get a number from left neighbor
print p
loop:
n = get a number from left neighbor
if (p does not divide n)
send n to right neighbor
思路
CSP 的關(guān)鍵點(diǎn)在于：?jiǎn)蝹€(gè)步驟內(nèi)部操作是串行的，所有步驟之間是并發(fā)的。步驟之間的通信通過(guò)特定的 channel 完成，這里通過(guò) pipe 完成。
如上圖，除去第一個(gè)進(jìn)程和最后一個(gè)進(jìn)程，每個(gè)進(jìn)程有兩種身份（父/子）。
分析上述 pipeline, 每個(gè)進(jìn)程需做如下事情：
-
從 left-side-pipe 中讀取數(shù)據(jù)，嘗試打印素?cái)?shù) prime。
- 如果 left-side-pipe 的寫端關(guān)閉且沒(méi)讀到數(shù)據(jù)，代表沒(méi)有數(shù)據(jù)到達(dá)。本進(jìn)程任務(wù)結(jié)束，正常 exit.
-
建立一個(gè)新的 right-side-pipe, fork 出一個(gè)子進(jìn)程, 自身即作為“父身份”根據(jù)第一步得出的 prime 進(jìn)行 filter, 將過(guò)濾后的數(shù)據(jù)傳入 right-side-pipe. wait 子進(jìn)程，等待子進(jìn)程打印結(jié)束。
- 進(jìn)程 p0 由 shell fork 創(chuàng)建，如果 p0 不 wait 子進(jìn)程，父進(jìn)程 p0 可能在所有子進(jìn)程打印完成前結(jié)束，此時(shí) shell 會(huì)向終端輸出提示符
$，造成$穿插在打印結(jié)果中的現(xiàn)象。 - 不 wait:
- 子進(jìn)程還在運(yùn)行，父進(jìn)程結(jié)束 -> 孤兒進(jìn)程 -> 由 init 收養(yǎng)。缺點(diǎn)：原父進(jìn)程得不到子進(jìn)程的狀態(tài)。
- 父進(jìn)程還在運(yùn)行，子進(jìn)程結(jié)束 -> 僵尸進(jìn)程。缺點(diǎn)：占用資源得不到釋放 (
task_struct)。
- 進(jìn)程 p0 由 shell fork 創(chuàng)建，如果 p0 不 wait 子進(jìn)程，父進(jìn)程 p0 可能在所有子進(jìn)程打印完成前結(jié)束，此時(shí) shell 會(huì)向終端輸出提示符
notes: fork 出來(lái)的子進(jìn)程重復(fù)上述操作。
注意點(diǎn)
- 注意 close(pipe) 的時(shí)機(jī)，最保險(xiǎn)的做法是盡可能早關(guān)閉不需要的讀寫端。
- wait 操作。
- 錯(cuò)誤處理。
代碼
#include "kernel/types.h"
#include "user/user.h"
#define NULL 0
void perror_exit(char* err_msg) {
fprintf(2, "%s\n", err_msg);
exit(-1);
}
void child_processing(int left_pipe[2]) {
// every process do things below：
// 0. read from left-side pipe, and try to print a prime.
// 1. create a new right-side pipe, do fork, pass the filtered data to right-side pipe.
// notes: The new child processes forked will recursively do the above tasks.
close(left_pipe[1]);
int prime;
int rbytes = read(left_pipe[0], &prime, sizeof(prime));
if (rbytes == -1) {
close(left_pipe[0]);
perror_exit("read error");
} else if (rbytes == 0) {
// No more data reaches here
close(left_pipe[0]);
exit(0);
} else {
fprintf(1, "prime %d\n", prime);
}
int right_pipe[2];
int ret = pipe(right_pipe);
if (ret == -1) {
perror_exit("pipe error");
}
ret = fork();
if (ret == -1) {
perror_exit("fork error");
} else if (ret > 0) { // parent/current process
close(right_pipe[0]);
// do filtering, write data into the right-side pipe
int num;
while ((rbytes = read(left_pipe[0], &num, sizeof(num))) != 0) {
if (rbytes == -1) {
perror_exit("read error");
}
if (num % prime != 0) {
write(right_pipe[1], &num, sizeof(num));
}
}
// if rbytes == 0, no more data reaches. the job of this process is done
close(left_pipe[0]);
close(right_pipe[1]);
wait(NULL);
exit(0);
} else if (ret == 0) { // child process
child_processing(right_pipe);
}
}
int main(int argc, char* argv[])
{
int pipe_fds[2];
int ret = pipe(pipe_fds);
if (ret == -1) {
perror_exit("pipe error");
}
// create child process
int pid = fork();
if (pid == -1) {
perror_exit("fork error");
} else if (pid == 0) { // child process
// read from pipe, do filtering and pass the data to next stage
child_processing(pipe_fds);
} else { // parent process
close(pipe_fds[0]);
const int MAX = 35;
for (uint32 i = 2; i <= MAX; ++ i) {
write(pipe_fds[1], &i, sizeof(i));
}
close(pipe_fds[1]);
wait(NULL);
}
exit(0);
}
知識(shí)點(diǎn)
- 多個(gè)寫者向同一管道寫數(shù)據(jù)時(shí)，可以確保寫入不超過(guò) PIPE_BUF 字節(jié)的操作是原子的。
- 即假設(shè) A 寫入數(shù)據(jù) aa; B 寫入數(shù)據(jù) bb. 可以保證管道內(nèi)數(shù)據(jù)必是 aabb 或者 bbaa，不會(huì)出現(xiàn) abab 此類交叉的情況。
- 如果寫入數(shù)據(jù)量超過(guò)限制，內(nèi)核會(huì)將其切分成若干個(gè)片段進(jìn)行傳輸，
write()調(diào)用會(huì)阻塞直到所有數(shù)據(jù)都被寫入管道位置（此時(shí)便可能出現(xiàn)數(shù)據(jù)交叉的情況）。
- 如果管道的寫端被關(guān)閉，從讀端讀數(shù)據(jù)的進(jìn)程讀完所有剩余數(shù)據(jù)后，將會(huì)看到文件結(jié)束，
read()返回 0. - 管道容量是有限的，非特權(quán)進(jìn)程可以通過(guò)
fctnl(fd, F_SETPIPE_SIZE, size)進(jìn)行修改，修改范圍為 pagesize 和 /proc/sys/fs/pipe-max-size 之間。- 更大的管道容量意味著更少的上下文切換。
- 管道用于單向通信，即某進(jìn)程在一端讀，另一進(jìn)程在一端寫。
- 如果允許父子進(jìn)程都能夠讀/寫同一管道，那么會(huì)發(fā)生競(jìng)爭(zhēng)，需要額外的同步機(jī)制。
- 如果需要雙向通信，分別在兩個(gè)方向上各設(shè)立一個(gè)管道即可。
- 關(guān)閉未使用管道 fd.
- 如果讀進(jìn)程沒(méi)有關(guān)閉管道的寫端，那么在其他進(jìn)程關(guān)閉了寫入文件描述符后，讀者也不會(huì)看到文件結(jié)束，因?yàn)閮?nèi)核知道至少還存在一個(gè)管道的寫入描述符打開(kāi)著，即讀取進(jìn)程自己。
- 如果寫進(jìn)程沒(méi)有關(guān)閉管道的讀端，那么即使其他進(jìn)程已經(jīng)關(guān)閉了讀端文件描述符，寫進(jìn)程仍然能夠向管道中寫入數(shù)據(jù)，最后管道被寫滿，后續(xù)的寫入請(qǐng)求會(huì)被永遠(yuǎn)阻塞。
- 當(dāng)進(jìn)程嘗試向一個(gè)管道寫入數(shù)據(jù)，但是沒(méi)有進(jìn)程占用該管道讀端時(shí)，內(nèi)核會(huì)向進(jìn)程發(fā)送
SIGPIPE信號(hào)，默認(rèn)處理會(huì)殺死進(jìn)程。
find
-
思路：查找待查找目錄下所有條目：
- 如果是目錄，遞歸查找
- 如果是普通文件，比對(duì)文件名，輸出
-
實(shí)現(xiàn)：參考
ls.c實(shí)現(xiàn)。目錄文件本質(zhì)也是一個(gè)文件，不過(guò)文件內(nèi)容是一個(gè)個(gè) directory entry. 因此對(duì)于目錄，讀取其文件內(nèi)容至 dir_entry 中，判斷其類型，進(jìn)行相應(yīng)處理。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-615929.html -
代碼：
#include "kernel/types.h"
#include "kernel/stat.h"
#include "kernel/fs.h"
#include "user/user.h"
char* fmtname(char *path) {
static char buf[DIRSIZ+1];
char *p;
// Find first character after last slash.
for (p = path + strlen(path); p >= path && *p != '/'; p--)
;
p++;
// Return blank-padded name.
if (strlen(p) >= DIRSIZ)
return p;
memmove(buf, p, strlen(p));
memset(buf+strlen(p), ' ', DIRSIZ-strlen(p));
return buf;
}
void find(char* path, char* file_name) {
int fd = open(path, 0);
if (fd < 0) {
fprintf(2, "find: cannot open %s\n", path);
goto clean;
}
int ret;
struct stat st;
ret = fstat(fd, &st);
if (ret < 0) {
fprintf(2, "find: cannot stat %s\n", path);
goto clean;
}
if (st.type != T_DIR) {
fprintf(2, "find: the first param should be directory\n");
goto clean;
}
char buf[512];
if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
fprintf(2, "find: path too long\n");
goto clean;
}
strcpy(buf, path);
char* p = buf + strlen(buf);
*p++ = '/';
struct dirent de;
while (read(fd, &de, sizeof(de)) == sizeof(de)){
if (de.inum == 0)
continue;
memmove(p, de.name, DIRSIZ);
p[DIRSIZ] = '\0';
if (stat(buf, &st) < 0) {
printf("find: cannot stat %s\n", buf);
continue;
}
switch (st.type) {
case T_FILE:
if (strcmp(file_name, de.name) == 0) {
fprintf(1, "%s\n", buf);
}
break;
case T_DIR:
if (strcmp(".", de.name) != 0 && strcmp("..", de.name) != 0) {
find(buf, file_name);
}
break;
case T_DEVICE:
break;
}
}
clean:
close(fd);
return;
}
int main(int argc, char *argv[])
{
if (argc != 3) {
fprintf(2, "Usage: %s <directory> <filename>\n", argv[0]);
exit(1);
}
find(argv[1], argv[2]);
exit(0);
}
到了這里，關(guān)于操作系統(tǒng)復(fù)習(xí) MITS6.1810 lab util 記錄的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
