6.S081 - Lecture 1 Introduciton
本文最后更新于：2024年4月23日 下午
感觉学校的OS课程写的过于草率，加上最近似乎没有什么事情做，那就开一个新坑吧！
Lecture 1: Introduction
操作系统的工作是在多个程序之间共享计算机，并提供比硬件单独支持的更有用的服务集。
- 管理和抽象低级硬件
- 在多个程序之间共享硬件
- 玮程序交互提供受控方式
操作系统通过接口项用户程序提供服务。
- 简单而狭窄、易于正确实现
- 提供更多复杂功能
- tradeoff：设计依赖于一些机制的界面，组合提供更多的通用性。
操作系统应该提供的功能：
- 多进程支持
- 进程间隔离
- 受控制的进程间通信
xv6：一种在本课程中使用的类UNIX的教学操作系统，运行在RISC-V指令集处理器上，本课程中将使用QEMU模拟器代替
kernel(内核)：为运行的程序提供服务的一种特殊程序。每个运行着的程序叫做进程，每个进程的内存中存储指令、数据和堆栈。一个计算机可以拥有多个进程，但是只能有一个内核
每当进程需要调用内核时，它会触发一个system call（系统调用），system call进入内核执行相应的服务然后返回。
- shell：一个普通的程序，其功能是让用户输入命令并执行它们，shell不是内核的一部分，这意味着外壳易于更换
进程与内存
一个 xv6 进程由两部分组成，一部分是用户内存空间（指令，数据，栈），另一部分是仅对内核可见的进程状态。每个进程拥有自己的用户空间内存以及内核空间状态，当进程不再执行时，xv6将存储和这些进程相关的CPU寄存器直到下一次运行这些进程。kernel将每一个进程用一个PID(process identifier)指代。
常用syscall
fork：形式：int fork()。其作用是让一个进程生成另外一个和这个进程的内存内容相同的子进程。在父进程中，fork的返回值是这个子进程的PID，在子进程中，返回值是0exit：形式：int exit(int status)。让调用它的进程停止执行并且将内存等占用的资源全部释放。需要一个整数形式的状态参数，0代表以正常状态退出，1代表以非正常状态退出wait：形式：int wait(int *status)。等待子进程退出，返回子进程PID，子进程的退出状态存储到int *status这个地址中。如果调用者没有子进程，wait将返回-11
2
3
4
5
6
7
8
9
10
11int pid = fork();
if (pid > 0) {
printf("parent: child=%d\n", pid);
pid = wait((int *) 0);
printf("child %d is done\n", pid);
} else if (pid == 0) {
printf("child: exiting\n");
exit(0);
} else {
printf("fork error\n");
}前两行输出可能是
1
2parent: child=1234
child: exiting也可能是
1
2child: exiting
parent: child=1234这是因为在fork了之后，父进程和子进程将同时开始判断PID的值，在父进程中，PID为1234，而在子进程中，PID为0。看哪个进程先判断好PID的值，以上输出顺序才会被决定。
最后一行输出为：
1
parent: child 1234 is done子进程在判断完
pid == 0之后将exit，父进程发现子进程exit之后，wait执行完毕，打印输出。尽管
fork了之后子进程和父进程有相同的内存内容，但是内存地址和寄存器是不一样的，也就是说在一个进程中改变变量并不会影响另一个进程。exec：形式：int exec(char *file, char *argv[])。加载一个文件，获取执行它的参数，执行。如果执行错误返回-1，执行成功则不会返回，而是开始从文件入口位置开始执行命令。文件必须是ELF格式。xv6 shell使用以上四个system call来为用户执行程序。在shell进程的
main中主循环先通过getcmd来从用户获取命令，然后调用fork来运行一个和当前shell进程完全相同的子进程。父进程调用wait等待子进程exec执行完（在runcmd中调用exec）。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/* sh.c */
int
main(void)
{
static char buf[100];
int fd;
// Ensure that three file descriptors are open.
while((fd = open("console", O_RDWR)) >= 0){
if(fd >= 3){
close(fd);
break;
}
}
// Read and run input commands.
while(getcmd(buf, sizeof(buf)) >= 0){
if(buf[0] == 'c' && buf[1] == 'd' && buf[2] == ' '){
// Chdir must be called by the parent, not the child.
buf[strlen(buf)-1] = 0; // chop \n
if(chdir(buf+3) < 0)
fprintf(2, "cannot cd %s\n", buf+3);
continue;
}
if(fork1() == 0)
runcmd(parsecmd(buf));
wait(0);
}
exit(0);
}
I/O 和文件描述符
file descriptor：文件描述符，用来表示一个被内核管理的、可以被进程读/写的对象的一个整数，表现形式类似于字节流，通过打开文件、目录、设备等方式获得。一个文件被打开得越早，文件描述符就越小。
每个进程都拥有自己独立的文件描述符列表，其中0是标准输入，1是标准输出，2是标准错误。shell将保证总是有3个文件描述符是可用的。
1
2
3
4
5
6while((fd = open("console", O_RDWR)) >= 0){
if(fd >= 3){
close(fd);
break;
}
}read和write：形式int write(int fd, char *buf, int n)和int read(int fd, char *bf, int n)。从/向文件描述符fd读/写n字节bf的内容，返回值是成功读取/写入的字节数。每个文件描述符有一个offset，read会从这个offset开始读取内容，读完n个字节之后将这个offset后移n个字节，下一个read将从新的offset开始读取字节。write也有类似的offset。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17/* essence of cat program */
char buf[512];
int n;
for (;;) {
n = read(0, buf, sizeof buf);
if (n == 0)
break;
if (n < 0){
fprintf(2, "read errot\n");
exit(1);
}
if (write(1, buf, n) != n){
fprintf(2, "write error\n");
exit(1);
}
}close。形式是int close(int fd)，将打开的文件fd释放，使该文件描述符可以被后面的open、pipe等其他system call使用。使用
close来修改file descriptor table能够实现I/O重定向。1
2
3
4
5
6
7
8
9
10
11
12
13/* implementation of I/O redirection,
* more specifically, cat < input.txt
*/
char *argv[2];
argv[0] = "cat";
argv[1] = 0;
if (fork() == 0) {
// in the child process
close(0); // this step is to release the stdin file descriptor
open("input.txt", O_RDONLY); // the newly allocated fd for input.txt is 0, since the previous fd 0 is released
exec("cat", argv); // execute the cat program, by default takes in the fd 0 as input, which is input.txt
}父进程的fd table将不会被子进程fd table的变化影响，但是文件中的offset将被共享。考虑这个例子
1
2
3
4
5
6
7if(fork() == 0) {
write(1, "hello ", 6);
exit();
} else {
wait();
write(1, "world\n", 6);
}绑定在文件描述符1上的文件有数据”hello world”，父进程的
write会从子进程write结束的地方继续写 (因为wait,父进程只在子进程结束之后才运行write)。这种行为有利于顺序执行的 shell 命令的顺序输出，例如(echo hello; echo world)>output.txt。dup。形式是int dup(int fd)，复制一个新的fd指向的I/O对象，返回这个新fd值，两个I/O对象(文件)的offset相同。1
2
3
4fd = dup(1);
write(1, "hello ", 6);
write(fd, "world\n", 6);
// outputs hello world除了
dup和fork之外，其他方式不能使两个I/O对象的offset相同，比如同时open相同的文件。
管道
pipe：管道，暴露给进程的一对文件描述符，一个文件描述符用来读，另一个文件描述符用来写，将数据从管道的一端写入，将使其能够被从管道的另一端读出
pipe是一个system call，形式为int pipe(int p[])，p[0]为读取的文件描述符，p[1]为写入的文件描述符。
1 | |
这段程序调用pipe，创建一个新的管道并且将读写描述符记录在数组p中。
在fork之后，父进程和子进程都有了指向管道的文件描述符。子进程将管道的读端口拷贝在描述符0上，关闭p中的描述符，然后执行wc。当wc从标准输入读取时，它实际上是从管道读取的。父进程向管道的写端口写入然后关闭它的两个文件描述符。
xv6中的实现和上述的类似：
1 | |
这里我有点没搞懂为什么要在写入/读取之前执行一些close操作（包括wc和Lab中的pingpong），在网上查了资料之后，我大概理解了。先来看看管道是如何实现进程之间的通信的：
- 父进程创建管道，得到两个文件描述符指向管道的两端
- 父进程fork出子进程，子进程也有两个文件描述符指向同⼀管道
- 父进程关闭fd[0],子进程关闭fd[1]，即父进程关闭管道读端,子进程关闭管道写端（因为管道只支持单向通信）。父进程可以往管道⾥写，子进程可以从管道里读,管道是⽤环形队列实现的,数据从写端流⼊从读端流出,这样就实现了进程间通信。
所以两个进程要相互通信，可以创建两个pipe分别关闭读写端，两个单向就变成了双向了。
文件系统
xv6文件系统包含了文件(byte arrays)和目录(对其他文件和目录的引用)。目录生成了一个树，树从根目录/开始。对于不以/开头的路径，认为是是相对路径
mknod：创建设备文件，一个设备文件有一个major device #和一个minor device #用来唯一确定这个设备。当一个进程打开了这个设备文件时，内核会将read和write的system call重新定向到设备上。- 一个文件的名称和文件本身是不一样的，文件本身，也叫inode，可以有多个名字，也叫link，每个link包括了一个文件名和一个对inode的引用。一个inode存储了文件的元数据，包括该文件的类型(file, directory or device)、大小、文件在硬盘中的存储位置以及指向这个inode的link的个数
fstat。一个system call，形式为int fstat(int fd, struct stat *st)，将inode中的相关信息存储到st中。link。一个system call，将创建一个指向同一个inode的文件名。unlink则是将一个文件名从文件系统中移除，只有当指向这个inode的文件名的数量为0时这个inode以及其存储的文件内容才会被从硬盘上移除
注意：Unix提供了许多在用户层面的程序来执行文件系统相关的操作，比如mkdir、ln、rm等，而不是将其放在shell或kernel内，这样可以使用户比较方便地在这些程序上进行扩展。但是cd是一个例外，它是在shell程序内构建的，因为它必须要改变这个calling shell本身指向的路径位置，如果是一个和shell平行的程序，那么它必须要调用一个子进程，在子进程里起一个新的shell，再进行cd，这是不符合常理的。
Lab：Xv6 and Unix utilities
Boot xv6
1 | |
sleep（easy）
简单包装系统调用sys_sleep()。
注意：如果没有传入参数，需要打印错误信息。
1 | |
pingpong（easy）
开两个pipe，一个pipe负责子进程写父进程读，另一个pipe负责父进程写子进程读。
注意最后要把所有的pipe fd关闭掉。
1 | |
prime（moderate/hard）
素数筛法：将一组数feed到一个进程里，先print出最小的一个数，这是一个素数，然后用其他剩下的数依次尝试整除这个素数，如果可以整除，则将其drop，不能整除则将其feed到下一个进程中，直到最后打印出所有的素数。
采用递归，每次先尝试从左pipe中读取一个数，如果读不到说明已经到达终点，exit，否则再创建一个右pipe并fork一个子进程，将筛选后的数feed进这个右pipe。
注意最开始的父进程要等待所有子进程exit才能exit。
1 | |
find（moderate）
参照ls的实现即可。注意递归查找时忽略.和..。
1 | |
xargs（moderate）
xargs指令的含义可以参照这里。
使用fork起一个子进程，在子进程中用exec执行相应的命令。父进程wait。对标准输入每次读一个char，若读到\n需要执行命令。
1 | |