本章作业见http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf


在本次作业中,你将熟悉刚讲到的进程管理API的用法。这可是很有趣的,代码写得越多越好。所以赶紧去写吧。

(以下代码运行结果来自Ubuntu 16.04)

1

写一个程序,调用fork()。在调用fork()之前,让主进程设置一个变量(如x)的值(如100)。子进程中这个变量的值是多少?当子进程和父进程都修改x的值时,会发生什么?


程序代码见hw01.c

程序输出如下:

1
2
3
4
5
6
7
prompt> ./hw01
x = 100 (pid:2597)
parent: x = 100 (pid:2597)
parent: x = 101 (pid:2597)
child: x = 100 (pid:2598)
child: x = 99 (pid:2598)
prompt>

可以看出,子进程中x的值仍然为100,且父进程和子进程对x的修改是互相独立的。这是因为fork()系统调用把内存空间复制了一份(或者大概用了COW机制,不过这个暂时并不重要)。

2

写一个程序,通过open()系统调用打开一个文件,并调用fork()创建一个新的进程。子进程和父进程可以同时访问open()返回的文件描述符吗?如果它们同时写这个文件,会发生什么?


程序代码见hw02.c

程序输出如下:

1
2
3
4
5
prompt> ./hw02
prompt> cat hw02.output
I am parent
I am child
prompt>

可以发现,子进程和父进程可以同时访问这个文件,且输出结果基本是正常的。Linux实际上并不会保证并发的文件操作不出问题。不过,其实Linux的内部实现保证了read()write()操作是串行执行的。详情可见How do filesystems handle concurrent read/write?

3

再写一个调用fork()的程序。令子进程打印"hello",父进程打印"goodbye"。你能否在父进程中不调用wait()的情况下保证子进程总是先打印?


我感觉上一道题暗示我们,让子进程打印一点东西到文件中,然后在父进程中不断查看该文件中是否含有希望的信息。但我感觉这个做法可能不太可取。查了一些资料之后,我尝试让父进程用kill(2)检查子进程是否正在运行,但是我发现这也不可行,因为对僵尸进程进行这一检查也会返回0。事实上最科学的做法就是wait()系统调用了……所以我干脆用waitpid()好了。

程序代码见hw03.c

程序输出如下:

1
2
3
4
prompt> ./hw03
Hello, I am child
Goodbye, I am parent
prompt>

4

写一个程序,调用fork(),然后通过某种形式的exec()运行/bin/ls。你能否尝试使用exec()的所有变形,包括execl()execle()execlp()execv()execp()execvpe()?这个调用为何有这么多种形式?


程序代码见hw04.c

程序输出如下:

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
31
32
prompt> ./hw04
Parent: ready for execl(const char *path, const char *arg, ... /* (char *) NULL */)
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
Parent: ready for execlp(const char *file, const char *arg, ... /* (char *) NULL */)
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
Parent: ready for execle(const char *path, const char *arg, ... /*, (char *) NULL, char * const envp[] */)
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
Parent: ready for execv(const char *path, char *const argv[])
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
Parent: ready for execvp(const char *file, char *const argv[])
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
Parent: ready for execvpe(const char *file, char *const argv[], char *const envp[])
bin etc lib32 media root sys vmlinuz
boot home lib64 mnt run tmp
cdrom initrd.img libx32 opt sbin usr
dev lib lost+found proc srv var
prompt>

我猜这些形式主要是为了满足用户不同的需求。实际上,exec后面的那些后缀的含义是这样的(参见了linux系统编程之进程(五):exec系列函数(execl,execlp,execle,execv,execvp)使用):

  • l:参数以可变参数列表的形式给出,且以NULL结束(execl()execle()execlp()
  • 没有l:参数以char *arg[]形式给出,且arg最后一个元素必须为NULLexecv()execp()execvpe()
  • p:第一个参数不用输入完整路径,给出命令名即可,程序会在环境变量PATH当中查找命令(execlp()execp()execvpe()
  • 没有p:第一个参数需要输入完整路径(execl()execle()execv()
  • e:将环境变量传递给新进程(execle()execvpe()
  • 没有e:不传递环境变量(execl()execlp()execv()execp()

5

写一个程序,让父进程调用wait(),等待子进程完成。wait()将返回什么?如果在子进程中调用wait(),会发生什么?


程序代码见hw05.c

程序输出如下:

1
2
3
4
5
6
prompt> ./hw05
I am parent (pid:4154)
I am child (pid:4155)
Child: wait() returns -1
Parent: wait() returns 4155
prompt>

如果wait(2)找到了至少一个状态已经变化的子进程,则它会返回这个子进程的PID(因此此处父进程返回了子进程的PID,4155);而子进程自己没有子进程,因此调用失败,返回-1

6

稍微修改一下上一题中的程序,改为使用waitpid(),而不是wait()waitpid()何时是有用的?


程序代码见hw06.c

程序输出如下:

1
2
3
4
5
6
prompt> ./hw06
I am parent (pid:4368)
I am child (pid:4369)
Child: waitpid(-1) returns -1
Parent: waitpid(4369) returns 4369
prompt>

在需要等待某一个子进程执行完毕时,可以使用waitpid()。调用waitpid(-1)的效果与wait()基本是类似的。

7

写一个程序,创建一个子进程,并在子进程中关闭标准输出(STDOUT_FILENO)。在关闭该文件描述符之后,如果子进程调用printf()来打印输出,会发生什么?


程序代码见hw07.c

程序输出如下:

1
2
3
prompt> ./hw07
I am parent
prompt>

结果,无论是关闭之前还是关闭之后的printf都没有在屏幕打印出结果。我并没有查到为什么……

8

写一个程序,创建两个子进程,通过pipe()系统调用,把其中一个进程的标准输出连接到另一个的标准输入。


程序代码见hw08.c,参考了UNIX管道编程——使用pipe函数,dup函数,dup2函数

程序输出如下:

1
2
3
4
5
prompt> ./hw08
Child 1 (pid=4727), writing to pipe.
Child 2 (pid=4728), reading from pipe.
Hello world , this is transported by pipe.
prompt>

本章作业见http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdfhttp://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-CPU-Intro.tgz


作业说明和模拟器代码见https://github.com/zhanghuimeng/ostep-hw-translation/tree/master/ch04_Process-Intro

这次作业没有明确地说明调度策略——这也是因为现在还没有介绍到调度策略这么复杂的东西。通过阅读代码,我发现选择下一个运行进程的策略是通过PID进行循环查找:从当前进程的PID开始,如果这个进程处于就绪态,则选择它;否则PID = (PID + 1) % 进程总数。这个策略不太实际(有点类似于FIFO,但是优先级依赖于PID),但显然对于手动模拟比较方便。

1

用以下参数运行程序:./process-run.py -l 5:100,5:100。CPU利用率(CPU处于使用状态的时间比例)是多少?为什么?用参数-c-p验证你的回答的正确性。


我猜测Process0会先运行5个时间片;Process0运行完之后,Process1再运行5个时间片,也会结束。因为CPU运行完Process0就运行了Process1,中间没有空闲的时间,因此CPU利用率为100%。

运行结果如下(因为是win环境,所以用的是python):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
prompt> python process-run.py -l 5:100,5:100 -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:cpu READY 1
3 RUN:cpu READY 1
4 RUN:cpu READY 1
5 RUN:cpu READY 1
6 DONE RUN:cpu 1
7 DONE RUN:cpu 1
8 DONE RUN:cpu 1
9 DONE RUN:cpu 1
10 DONE RUN:cpu 1

Stats: Total Time 10
Stats: CPU Busy 10 (100.00%)
Stats: IO Busy 0 (0.00%)

可以看出这个推测是正确的。

2

用以下参数运行程序:./process-run.py -l 4:100,1:0。这些参数给定了两个进程,其中一个包含4条CPU指令,另一个只发出一个I/O请求并等待请求结束。两个进程都结束执行需要多长时间?用参数-c-p验证你的回答的正确性。


Process0不发出I/O请求,因此它会一直执行到结束,共花费4个时间片。Process1发出一个I/O请求(1个时间片),I/O请求执行完毕需要5个时间片;因此,一共需要10个时间片结束执行。

运行结果如下(实际上刚才的结果参考了运行结果,因为我不知道所谓的“I/O请求花费5个时间片”算不算发出请求的指令的时间……当然从情理上和实验上来说都是不算的):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
prompt> python process-run.py -l 4:100,1:0 -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:cpu READY 1
3 RUN:cpu READY 1
4 RUN:cpu READY 1
5 DONE RUN:io 1
6 DONE WAITING 1
7 DONE WAITING 1
8 DONE WAITING 1
9 DONE WAITING 1
10* DONE DONE

Stats: Total Time 10
Stats: CPU Busy 5 (50.00%)
Stats: IO Busy 4 (40.00%)

3

现在切换进程的顺序:./process-run.py -l 1:0,4:100。切换顺序对于结束执行的时间有影响吗?继续用参数-c-p验证你的回答的正确性。


显然有影响,因为Process0发出一个I/O请求(花费1个时间片)后,就会切换到Process1开始执行(4个时间片);与此同时,I/O请求需要5个时间片完成。因此执行时间减少到了6个时间片。这说明了进程切换的必要性,因为增加了并行性,可以增加各种设备的利用率。

运行结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
prompt> python process-run.py -l 1:0,4:100 -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 WAITING RUN:cpu 1 1
3 WAITING RUN:cpu 1 1
4 WAITING RUN:cpu 1 1
5 WAITING RUN:cpu 1 1
6* DONE DONE

Stats: Total Time 6
Stats: CPU Busy 5 (83.33%)
Stats: IO Busy 4 (66.67%)

4

下面我们探索一下其他的参数。参数-S指定了进程发出I/O请求时系统的反应策略。当该参数的值为SWITCH_ON_END时,系统不会在当前进程发出I/O请求时切换到另一个进程,而是等待进程结束之后再切换。如果你用以下参数运行程序(-l 1:0,4:100 -c -S SWITCH_ON_END),会发生什么?


这道题的进程配置和上一道题一样,但是如果在进程发出I/O请求时不切换,就相当于必须执行完当前进程才能切换到下一个,这样设备利用率显然会下降,而运行时间会增加。Process0执行完需要6个时间片,Process1需要4个时间片,因此总时间为10个时间片,与进程顺序颠倒时相同。

运行结果如下(好吧,这说明我的分析有一点问题,这似乎与结束的总时间如何计算有关):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prompt> python process-run.py -l 1:0,4:100 -c -S SWITCH_ON_END -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 WAITING READY 1
3 WAITING READY 1
4 WAITING READY 1
5 WAITING READY 1
6* DONE RUN:cpu 1
7 DONE RUN:cpu 1
8 DONE RUN:cpu 1
9 DONE RUN:cpu 1

Stats: Total Time 9
Stats: CPU Busy 5 (55.56%)
Stats: IO Busy 4 (44.44%)

5

现在把-S参数的值置为SWITCH_ON_IO,此时只要进程发出I/O请求,就会切换到别的进程。(参数为-l 1:0,4:100 -c -S SWITCH_ON_IO)。那么,会发生什么呢?用参数-c-p验证你的回答的正确性。


把参数设置成这样似乎就是默认值。结论是和第4题的分析相同吧?

运行结果如下(是的,的确如此):

1
2
3
4
5
6
7
8
9
10
11
12
prompt> python process-run.py -l 1:0,4:100 -c -S SWITCH_ON_IO -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 WAITING RUN:cpu 1 1
3 WAITING RUN:cpu 1 1
4 WAITING RUN:cpu 1 1
5 WAITING RUN:cpu 1 1
6* DONE DONE

Stats: Total Time 6
Stats: CPU Busy 5 (83.33%)
Stats: IO Busy 4 (66.67%)

6

I/O请求结束时系统的执行策略也很重要。如果将参数-I的值置为IO_RUN_LATER,则I/O请求完成时,发出请求的进程不会立刻开始执行,当前运行中的进程会继续运行。如果使用以下参数组合,会发生什么?(./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER


IO_RUN_LATER似乎就是默认值。Process0首先发出一个I/O请求(1个时间片),之后Process1,Process2和Process3依次执行完毕(共15个时间片);最后Process0再重新开始执行,花费10个时间片进行两个I/O请求。然后,似乎因为最后一条指令为I/O指令,所以需要多花一个时间片确认为DONE(这一点是根据运行结果凑出来的)。因此总时间为27个时间片。

这个调度方法比较愚蠢,如果把Process0的I/O请求分散开,可以提高CPU和I/O设备的利用率。这说明在设计调度策略的时候,我们应当考虑到I/O密集型进程和CPU密集型进程的不同特点。

运行结果如下:

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
31
32
33
prompt> python process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER -c -p
Time PID: 0 PID: 1 PID: 2 PID: 3 CPU IOs
1 RUN:io READY READY READY 1
2 WAITING RUN:cpu READY READY 1 1
3 WAITING RUN:cpu READY READY 1 1
4 WAITING RUN:cpu READY READY 1 1
5 WAITING RUN:cpu READY READY 1 1
6* READY RUN:cpu READY READY 1
7 READY DONE RUN:cpu READY 1
8 READY DONE RUN:cpu READY 1
9 READY DONE RUN:cpu READY 1
10 READY DONE RUN:cpu READY 1
11 READY DONE RUN:cpu READY 1
12 READY DONE DONE RUN:cpu 1
13 READY DONE DONE RUN:cpu 1
14 READY DONE DONE RUN:cpu 1
15 READY DONE DONE RUN:cpu 1
16 READY DONE DONE RUN:cpu 1
17 RUN:io DONE DONE DONE 1
18 WAITING DONE DONE DONE 1
19 WAITING DONE DONE DONE 1
20 WAITING DONE DONE DONE 1
21 WAITING DONE DONE DONE 1
22* RUN:io DONE DONE DONE 1
23 WAITING DONE DONE DONE 1
24 WAITING DONE DONE DONE 1
25 WAITING DONE DONE DONE 1
26 WAITING DONE DONE DONE 1
27* DONE DONE DONE DONE

Stats: Total Time 27
Stats: CPU Busy 18 (66.67%)
Stats: IO Busy 12 (44.44%)

7

将参数-I的值换成IO_RUN_IMMEDIATE,重新执行上述命令,此时,当I/O请求完成时,发出请求的进程会立刻抢占CPU。现在程序的运行结果有何不同?为什么让刚刚执行完I/O的进程立刻开始运行可能是个好主意?


就像上一题所分析的那样,如果把I/O请求分散开来,则可以提高设备的利用率。在设计调度策略的时候应当考虑到进程的I/O密集程度,这个思路见于多级反馈队列调度算法中——如果进程用完了时间片则下移一个队列;否则,如果在时间片结束之前就发出了I/O请求,则保留在当前队列中。此时花费的总时间就是3条I/O指令加上15条CPU指令的时间。

运行结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
prompt> python process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_IMMEDIATE -c -p
Time PID: 0 PID: 1 PID: 2 PID: 3 CPU IOs
1 RUN:io READY READY READY 1
2 WAITING RUN:cpu READY READY 1 1
3 WAITING RUN:cpu READY READY 1 1
4 WAITING RUN:cpu READY READY 1 1
5 WAITING RUN:cpu READY READY 1 1
6* RUN:io READY READY READY 1
7 WAITING RUN:cpu READY READY 1 1
8 WAITING DONE RUN:cpu READY 1 1
9 WAITING DONE RUN:cpu READY 1 1
10 WAITING DONE RUN:cpu READY 1 1
11* RUN:io DONE READY READY 1
12 WAITING DONE RUN:cpu READY 1 1
13 WAITING DONE RUN:cpu READY 1 1
14 WAITING DONE DONE RUN:cpu 1 1
15 WAITING DONE DONE RUN:cpu 1 1
16* DONE DONE DONE RUN:cpu 1
17 DONE DONE DONE RUN:cpu 1
18 DONE DONE DONE RUN:cpu 1

Stats: Total Time 18
Stats: CPU Busy 18 (100.00%)
Stats: IO Busy 12 (66.67%)

8

用下列随机生成的参数组合运行程序,比如-s 1 -l 3:50,3:50-s 2 -l 3:50,3:50-s 3 -l 3:50,3:50。你能否预测程序运行结果?将-I参数的值分别置为IO_RUN_IMMEDIATEIO_RUN_LATER时,运行结果有何区别?将-S参数的值分别置为SWITCH_ON_IOSWITCH_ON_END时,运行结果有何区别?


8.1

使用参数-s 1 -l 3:50,3:50,输出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prompt> python process-run.py -s 1 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
cpu
io
io

Process 1
cpu
cpu
cpu

Important behaviors:
System will switch when the current process is FINISHED or ISSUES AN IO
After IOs, the process issuing the IO will run LATER (when it is its turn)

-I IO_RUN_LATER时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
prompt> python process-run.py -s 1 -l 3:50,3:50 -I IO_RUN_LATER -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:io READY 1
3 WAITING RUN:cpu 1 1
4 WAITING RUN:cpu 1 1
5 WAITING RUN:cpu 1 1
6 WAITING DONE 1
7* RUN:io DONE 1
8 WAITING DONE 1
9 WAITING DONE 1
10 WAITING DONE 1
11 WAITING DONE 1
12* DONE DONE

Stats: Total Time 12
Stats: CPU Busy 6 (50.00%)
Stats: IO Busy 8 (66.67%)

-I IO_RUN_IMMEDIATE时结果相同,因为Process0发出的I/O请求在Process1完全执行结束之后才完成:

-S SWITCH_ON_IO时结果也相同,因为这个是默认值。

-S SWITCH_ON_END时运行时间变长,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
prompt> python process-run.py -s 1 -l 3:50,3:50 -S SWITCH_ON_END -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:io READY 1
3 WAITING READY 1
4 WAITING READY 1
5 WAITING READY 1
6 WAITING READY 1
7* RUN:io READY 1
8 WAITING READY 1
9 WAITING READY 1
10 WAITING READY 1
11 WAITING READY 1
12* DONE RUN:cpu 1
13 DONE RUN:cpu 1
14 DONE RUN:cpu 1

Stats: Total Time 14
Stats: CPU Busy 6 (42.86%)
Stats: IO Busy 8 (57.14%)

8.2

使用参数-s 2 -l 3:50,3:50,输出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prompt> python process-run.py -s 2 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
io
io
cpu

Process 1
cpu
io
io

Important behaviors:
System will switch when the current process is FINISHED or ISSUES AN IO
After IOs, the process issuing the IO will run LATER (when it is its turn)

-I IO_RUN_LATER时,输出如下,出现了两个进程同时I/O的情况(不过此时我们认为I/O是可以并行的,不存在等待I/O设备的问题):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
prompt> python process-run.py -s 2 -l 3:50,3:50 -I IO_RUN_LATER -p -c
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 WAITING RUN:cpu 1 1
3 WAITING RUN:io 1 1
4 WAITING WAITING 2
5 WAITING WAITING 2
6* RUN:io WAITING 1 1
7 WAITING WAITING 2
8* WAITING RUN:io 1 1
9 WAITING WAITING 2
10 WAITING WAITING 2
11* RUN:cpu WAITING 1 1
12 DONE WAITING 1
13* DONE DONE

Stats: Total Time 13
Stats: CPU Busy 6 (46.15%)
Stats: IO Busy 11 (84.62%)

-I IO_RUN_IMMEDIATE时,输出完全相同(因为I/O请求很多,所以当前I/O结束之后,CPU处于空闲状态,可以直接开始执行下一条指令)。

-S SWITCH_ON_IO时输出完全相同(因为这是默认值……)。

-S SWITCH_ON_END时运行时间大大增加了:

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
prompt> python process-run.py -s 2 -l 3:50,3:50 -S SWITCH_ON_END -p -c
Time PID: 0 PID: 1 CPU IOs
1 RUN:io READY 1
2 WAITING READY 1
3 WAITING READY 1
4 WAITING READY 1
5 WAITING READY 1
6* RUN:io READY 1
7 WAITING READY 1
8 WAITING READY 1
9 WAITING READY 1
10 WAITING READY 1
11* RUN:cpu READY 1
12 DONE RUN:cpu 1
13 DONE RUN:io 1
14 DONE WAITING 1
15 DONE WAITING 1
16 DONE WAITING 1
17 DONE WAITING 1
18* DONE RUN:io 1
19 DONE WAITING 1
20 DONE WAITING 1
21 DONE WAITING 1
22 DONE WAITING 1
23* DONE DONE

Stats: Total Time 23
Stats: CPU Busy 6 (26.09%)
Stats: IO Busy 16 (69.57%)

8.3

使用参数-s 3 -l 3:50,3:50,输出如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
prompt> python process-run.py -s 3 -l 3:50,3:50
Produce a trace of what would happen when you run these processes:
Process 0
cpu
io
cpu

Process 1
io
io
cpu

Important behaviors:
System will switch when the current process is FINISHED or ISSUES AN IO
After IOs, the process issuing the IO will run LATER (when it is its turn)

-I IO_RUN_LATER时:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
prompt> python process-run.py -s 3 -l 3:50,3:50 -I IO_RUN_LATER -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:io READY 1
3 WAITING RUN:io 1 1
4 WAITING WAITING 2
5 WAITING WAITING 2
6 WAITING WAITING 2
7* RUN:cpu WAITING 1 1
8* DONE RUN:io 1
9 DONE WAITING 1
10 DONE WAITING 1
11 DONE WAITING 1
12 DONE WAITING 1
13* DONE RUN:cpu 1

Stats: Total Time 13
Stats: CPU Busy 6 (46.15%)
Stats: IO Busy 9 (69.23%)

-I IO_RUN_IMMEDIATE时输出不变,因为I/O请求结束的时间又一次恰好和CPU被占用的时间错开了。

-S SWITCH_ON_IO时输出不变(因为这仍然是默认值)。

-S SWITCH_ON_END时运行时间仍然会增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
python process-run.py -s 3 -l 3:50,3:50 -S SWITCH_ON_END -c -p
Time PID: 0 PID: 1 CPU IOs
1 RUN:cpu READY 1
2 RUN:io READY 1
3 WAITING READY 1
4 WAITING READY 1
5 WAITING READY 1
6 WAITING READY 1
7* RUN:cpu READY 1
8 DONE RUN:io 1
9 DONE WAITING 1
10 DONE WAITING 1
11 DONE WAITING 1
12 DONE WAITING 1
13* DONE RUN:io 1
14 DONE WAITING 1
15 DONE WAITING 1
16 DONE WAITING 1
17 DONE WAITING 1
18* DONE RUN:cpu 1

Stats: Total Time 18
Stats: CPU Busy 6 (33.33%)
Stats: IO Busy 12 (66.67%)

本章课本见http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-api.pdf


本章的内容是“幕间休息”(interlude):这些章节讲的是OS中与具体API相关的内容,和原理关系不大,如果不想了解这些具体内容,可以跳过。(但是最好还是不跳过,因为实践出真知,对吧?)本章主要介绍了以下三个与进程创建相关的UNIX系统调用,以及它们的设计原理:

  • fork()
  • wait()
  • exec()

fork系统调用:通过复制来创建新进程

下面的例子说明了fork()系统调用的使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// p1.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(int argc, char *argv[])
{
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if (rc < 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else { // parent goes down this path (main)
printf("hello, I am parent of %d (pid:%d)\n",
rc, (int) getpid());
}
return 0;
}

上述程序的输出如下:

1
2
3
4
5
prompt> ./p1
hello world (pid:29146)
hello, I am parent of 29147 (pid:29146)
hello, I am child (pid:29147)
prompt>

可以看出,程序开始执行的时候打印了一条信息,其中包含了进程标识符(process identifier,PID)。该进程的PID是29146。在UNIX系统中,PID是进程的唯一标识。然后进程调用了fork()系统调用,通过拷贝当前进程创建了一个新进程。有趣的是,这两个进程几乎相同,都正准备从fork()系统调用返回。新进程(称为子进程;原来的进程称为父进程)不会从main()开始运行(因为hello world只被打印了一次),而是好像自己已经调用了fork()一样。这样设计的原因,将在后面进行解释。

子进程和父进程几乎相同(地址空间、寄存器、PC),只有一点区别:fork()调用的返回值不同。父进程的返回值是子进程的PID,而子进程的返回值是0。这一区别使得我们可以撰写代码分别处理这两种情况。

值得注意的另一点是,p1.c的输出是不确定的(nondeterminism):当子进程创建的时候,系统中出现了两个活跃进程,而CPU调度器选择哪一个先开始运行是不确定的。因此,如果子进程被创建之后立刻开始运行,上述程序的输出就会变成这样:

1
2
3
4
5
prompt> ./p1
hello world (pid:29146)
hello, I am child (pid:29147)
hello, I am parent of 29147 (pid:29146)
prompt>

wait系统调用:等待子进程退出

下面的例子说明了wait()系统调用的使用方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// p2.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int
main(int argc, char *argv[])
{
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if (rc < 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
} else { // parent goes down this path (main)
int wc = wait(NULL);
printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
rc, wc, (int) getpid());
}
return 0;
}

输出结果如下:

1
2
3
4
5
prompt> ./p2
hello world (pid:29266)
hello, I am child (pid:29267)
hello, I am parent of 29267 (wc:29267) (pid:29266)
prompt>

在这个例子中,父进程调用wait(),使得它在子进程结束执行之后才继续执行。当子进程结束之后,wait()调用才返回。此时,上述代码的输出显然是确定(deterministic)的了。如果父进程先运行,它会立刻调用wait(),等待子进程运行结束;因此子进程必然先运行。

exec系统调用:通过覆盖改变当前进程的内容

下面的例子说明了exec()系统调用的使用方法,它一般和fork()一起使用,用于创建新进程:

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
// p3.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <sys/wait.h>

int
main(int argc, char *argv[])
{
printf("hello world (pid:%d)\n", (int) getpid());
int rc = fork();
if (rc < 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child (new process)
printf("hello, I am child (pid:%d)\n", (int) getpid());
char *myargs[3];
myargs[0] = strdup("wc"); // program: "wc" (word count)
myargs[1] = strdup("p3.c"); // argument: file to count
myargs[2] = NULL; // marks end of array
execvp(myargs[0], myargs); // runs word count
printf("this shouldn’t print out");
} else { // parent goes down this path (main)
int wc = wait(NULL);
printf("hello, I am parent of %d (wc:%d) (pid:%d)\n",
rc, wc, (int) getpid());
}
return 0;
}

输出结果如下:

1
2
3
4
5
6
prompt> ./p3
hello world (pid:29383)
hello, I am child (pid:29384)
29 107 1030 p3.c
hello, I am parent of 29384 (wc:29384) (pid:29383)
prompt>

事实上,在Linux中,exec()是一类系统调用的总称,一共有6个变种:execl()execlp()execle()execv()execvp()execvpe()。详情见exec(3)

在这个例子中,在调用fork()创建子进程后,子进程调用了execvp(),用程序wc覆盖自己并开始执行该程序。wc是字数统计(word counting)程序,此处它被用来统计源文件p3.c中行、词和字节的数量。

fork()系统调用的设计固然很怪,它的“同伙”exec()也有够怪的。事实上,exec()所做的事情是这样的:给定一个可执行文件的名字(如wc)和一些参数(如p3.c),它会加载(load)这个可执行文件的代码(和静态数据),覆盖当前进程的代码段和静态数据,并且重新初始化进程的堆栈和其他内存空间。然后OS把参数作为新进程的argv数组,直接开始运行新程序。所以exec()调用并没有创建一个新进程;它只是把当前正在运行的进程(p3)换成了一个新的程序(wc)。在子进程执行exec()调用之后,p3.c就好像从未运行过一样了;对exec()的成功调用是不会返回的。

fork和exec的设计原因:方便shell和管道的实现

我们为什么要这样设计创建新进程的API呢?事实上,对于UNIX shell来说,在创建新进程的过程中把fork()exec()分开是非常必要的,因为这样shell才能在调用fork()之后,调用exec()的过程之前运行一些代码来改变即将运行的程序的环境,这就使得我们可以创造很多有趣的特性。

shell是一个帮助你执行程序(命令)的用户程序。它显示一个命令提示符(prompt),然后等待你在里面打字。你在里面打一个命令(比如可执行程序的名字和参数);然后,shell一般会找到这个可执行程序在文件系统中的位置,调用fork()创建一个新的子进程,然后(子进程)调用exec()的某个变种开始执行命令,最后(父进程)调用wait()等待命令执行结束。当子进程运行结束之后,shell(父进程)从wait()返回,再次打印出命令提示符,等待你的下一条指令。

fork()exec()分开使得shell能在其间够做很多有用的东西。比如,我们执行如下命令:

1
prompt> wc p3.c > newfile.txt

在这个例子中,wc的输出被重定向(redirect)到输出文件newfile.txt中。shell完成这个任务的方法很简单:在创建子进程之后,调用exec()之前,shell关闭标准输出(standard output)并打开文件newfile.txt。这样,即将被执行的程序wc的任何输出都会被发送到这个文件而不是屏幕。

下面的代码实现了子进程输出的重定向。

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
// p4.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include <sys/wait.h>

int
main(int argc, char *argv[])
{
int rc = fork();
if (rc < 0) { // fork failed; exit
fprintf(stderr, "fork failed\n");
exit(1);
} else if (rc == 0) { // child: redirect standard output to a file
close(STDOUT_FILENO);
open("./p4.output", O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU);

// now exec "wc"...
char *myargs[3];
myargs[0] = strdup("wc"); // program: "wc" (word count)
myargs[1] = strdup("p4.c"); // argument: file to count
myargs[2] = NULL; // marks end of array
execvp(myargs[0], myargs); // runs word count
} else { // parent goes down this path (main)
int wc = wait(NULL);
}
return 0;
}

该程序的输出如下:

1
2
3
4
prompt> ./p4
prompt> cat p4.output
32 109 846 p4.c
prompt>

这种方法的工作原理与OS管理文件描述符的方法相关。UNIX系统在分配文件描述符时,会从0开始寻找空闲的文件描述符。上一章中曾经讲过,对于一个进程,默认有三个文件描述符是开启的:标准输入(STDIN_FILENO=0)、标准输出(STDOUT_FILENO=1)和标准错误输出(STDERR_FILENO=2)。关闭标准输出之后,在调用open()分配新的文件描述符时,STDOUT_FILENO=1就成了第一个可用的文件描述符,于是它就指向了我们需要的输出文件./p4.output。于是,子进程之后对标准输出文件描述符的写操作会被透明地指向新打开的文件。(真是有趣的设计啊)

UNIX管道(pipe)机制的实现方法类似。通过pipe()系统调用,一个进程的输出被连接到一个内核管道(pipe)中,另一个进程的输入也连接到这个相同的管道;这样,一个进程的输出就无缝连接到另一个进程的输入了。下面的例子通过管道命令实现了在文件中查找词并计算这个词出现次数的功能:

1
grep -o foo file | wc -l

温馨提示

RTFM

我们刚才只是大概介绍了这些系统调用的基本原理,还有许多细节没有涉及到。为了了解这些细节,你应当去阅读手册。作为一个系统程序员,阅读手册(manual/man pages)是非常重要的,因为里面提供了很多细节,而且还可以帮助你减少烦你的同事的次数。如果你直接去问他们细节问题,他们可能会回答你:“RTFM。”(Read the fucking manual!)

Get it right

兰普森(Butler W. Lampson)在他那篇广受好评的论文“Hints for Computer Systems Design”中这样说:“做正确的事。(Get it right.)抽象和简化都不能代替正确的做法。”

实际上,设计进程创建API有很多方法,但是UNIX的设计者选择了正确的那一种。(虽然我觉得本章中并没有充分论述它的正确性)

本章课本见http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-intro.pdf


这一章主要讲了OS的一种基本抽象模型:进程(Process)。

  • 进程的定义
  • 与进程相关的API
  • 进程的创建过程和状态(生命周期)
  • 进程的数据结构(进程控制块和进程状态队列)

CPU的虚拟化

我们首先给出一个进程的非正式定义:进程是一个正在运行的程序。

我们通常希望同时运行多个(甚至成百上千个)程序。这样用起来很方便,但是我们遇到的挑战是:如何创造这样由很多个虚拟CPU的假象?

OS通过对CPU进行虚拟化创造这一假象。它不断地运行一个程序,暂停,然后再运行下一个。这被称作CPU的分时共享(time sharing),这种技术允许程序的并发,同时也会牺牲一定的性能,因为一个程序的运行时间肯定会慢得多。

我们可以把实现CPU的虚拟化的过程拆分成两个步骤:

  • 机制(mechanism):这是实现一种功能的底层方法或协议;如上下文切换(context switch),这是一种分时机制(time-sharing mechanism),用于帮助OS实现暂停一个程序后切换到下一个的功能
  • 策略(policy):这是利用底层机制,在OS内进行决策的算法;如调度(scheduling)算法会利用历史信息、程序信息和性能评价方式进行决策

这是一种模块化的程序设计思路。不过,本节中我们似乎既没有讲机制也没有讲策略,而是讲了一些抽象内容(进程)的基本概念。

进程的正式定义

上面给出的那个定义是正确的,然而并不全面。如何更具体地描述一个进程?一般来说,我们可以通过记录进程在运行过程中访问或影响的系统部分来描述一个进程。于是我们可以定义进程的机器状态(machine state):

  • 内存(地址空间):包含指令和程序读写的数据
  • 寄存器:通用寄存器和一些特殊寄存器,如PC(program counter)和栈指针、帧指针
  • I/O信息:进程开启的文件列表

与进程相关的API

既然进程是OS为我们提供的一种抽象,那么显然需要一些使用它的方法。因此下面介绍了一些与进程相关的API,一般来说,任何现代OS都提供了这些API:

  • 创建(create):创建新进程
  • 销毁(destroy):强制终止进程,对于失控的进程来说是很必要的
  • 等待(wait):等待其他进程结束运行
  • 其他控制(miscellaneous control):除了杀死或等待进程以外的控制方式,如将进程挂起后恢复运行的机制
  • 状态(status):通常会提供一些能够获得进程状态信息的接口,包括运行时间和状态

进程的生命周期

进程的创建过程

为了启动一个进程,OS需要做以下事情:

  1. 将程序的代码和静态数据(初始化了的变量)加载到进程地址空间中。通常程序以某种可执行文件格式存储在磁盘(或者SSD)中,所以OS需要从磁盘读取数据。
  • 此时有一个加载策略的选择问题:积极加载(eager load)还是懒惰加载(lazy load)
  • 积极加载:将所有代码和数据在运行之前就全部装入内存中,是早期和简单OS的做法
  • 懒惰加载:用到对应的代码和数据时才加载,是现代OS的做法。
  • 这个问题与分页(paging)和交换(swapping)有关,之后还会谈到。
  1. 为程序的运行栈分配内存;对栈进行初始化(比如把main函数的argcargv放进去)
  2. 为程序的堆分配内存。堆用于在程序运行中动态分配内存,程序调用malloc()请求内存,调用free()释放内存。
  3. 对I/O进行初始化:对于类UNIX系统,每个进程默认有三个打开的文件描述符(file descriptor),用于标准输入、标准输出和标准错误输出,这使得进程能够从终端读入输入并打印到屏幕。我们将在本书的第三部分(持久化)中更多的谈到这个问题。
  4. 跳转到main()函数的起始点,将CPU的控制权交给新创建的进程。

进程的状态模型

创建了一个进程之后,它的状态(state)会不断变化。一个简化的进程三状态模型如下:

  • 运行态(running):进程正在处理器上运行,正在执行指令。
  • 就绪态(ready):进程已经准备好执行了,但由于某些原因,OS现在并没有运行它。
  • 等待态(blocked):进程执行了一些操作,使得它不能继续运行,直到发生某些其他事件为止。例如,进程启动对磁盘的I/O请求时,它就被阻塞了,此时其他的进程可以使用处理器。

进程在状态之间的迁移

上图说明了这个简化模型中进程如何在状态间迁移:

  • OS可以通过调度使进程在运行态和就绪态之间转换
  • 如果进程进入了等待态,则只有对应的事件发生时才会进入就绪态

下面举两个例子进行说明。在第一个例子中,两个进程只使用CPU而不进行I/O;调度策略是进程0执行完之后进程1才能开始执行。

只使用CPU的两个进程的状态变化

在第二个例子中,进程会进行I/O操作。当进程0进行I/O之后,它进入阻塞状态。于是进程1开始运行。进程0的I/O完成之后,它进入就绪态,等待进程1执行结束之后继续执行。

使用CPU并进行I/O的两个进程的状态变化

事实上,在上述过程中,OS采用了以下两种策略:

  • 在进程0进行I/O时切换到进程1:这个决策看起来是明智的,因为可以增加CPU使用率
  • 在进程0的I/O操作结束之后,没有立即切换回切换0:这个策略的好坏很难说

(上述内容将出现在作业中)

进程的数据结构

上面的内容可以说是非常抽象了。所以下面会讲到,这些抽象的内容如何用OS中具体的数据结构来表示。

进程控制块

我们把进程信息对应的数据结构称为进程控制块(Process Control Block,PCB)。下面是xv6教学OS中一个实际的进程控制块的定义(也就是说,会涉及大量底层机制内容):

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
31
32
33
34
35
// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
int eip;
int esp;
int ebx;
int ecx;
int edx;
int esi;
int edi;
int ebp;
};

// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
RUNNABLE, RUNNING, ZOMBIE };

// the information xv6 tracks about each process
// including its register context and state
struct proc {
char *mem; // Start of process memory
uint sz; // Size of process memory
char *kstack; // Bottom of kernel stack
// for this process
enum proc_state state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
struct context context; // Switch here to run process
struct trapframe *tf; // Trap frame for the
// current interrupt
};

下面对其中一些比较重要的内容给出说明。首先可以看到,context中存储了通用寄存器的内容,用于上下文切换(保存一个暂停的进程的寄存器的值;在进程恢复运行时,这些值将被重新加载到寄存器中),这是之前讲到的。其次可以发现,这里定义了6种状态,和之前讲到的三状态模型不完全相符(这可能也体现了抽象策略和底层机制的区别)。除了运行态、就绪态和等待态以外,此处还定义了其他的状态,如初始(initial)态(进程刚被创建时的状态,对应的大概是上述代码中的EMBRYO态)和终止(final)态(进程已经退出,但尚未被完全清理,在类UNIX系统中,这一状态被称为僵尸(zombie)态)。进入终止态的进程允许其他进程(通常是创建这个进程的父进程)检查进程的返回值,查看它是否成功结束。父进程在自己结束之前会执行最后一个调用(wait()),等待子进程执行完成(进入终止态),此时OS可以清理子进程相关的数据结构。

(我不知道我有没有理解清楚关于僵尸态的内容)

进程状态队列

为了管理进程的状态,OS会维护一些进程状态队列,用来跟踪就绪进程、正在运行的进程和阻塞进程,并且在发生事件的时候唤醒正确的进程。

本章课本见http://pages.cs.wisc.edu/~remzi/OSTEP/dialogue-virtualization.pdf


这篇对话是本书第一部分——虚拟化(Virtualization)——的开头,简单叙述了一下虚拟化的概念。

Professor教授(我今后就这样叫他了,毕竟这位教授的名字就是“Professor”)举了一个这样的例子:假设我们有一个物理的桃子,有很多人都想吃桃子,但桃子只有一个,不能满足所有人的需求。于是我们通过某种神奇的技术,在物理桃子的基础上创造出许多虚拟桃子,仿佛每个人都拥有自己的桃子一般,但事实上只有一个桃子。

这时Student学生(同理)提了一个很好的问题:如果很多人同时共享一个桃子,他们应该会注意到这一点。Professor教授指出,这些人大部分时间都在干别的,所以把桃子直接拿走是完全可行的。

Student学生要求Professor教授举一个具体的例子——那就PCU吧。假定系统里有一个物理CPU,虚拟化技术使得系统里好像有很多虚拟CPU在同时运行。每个进程都认为它独占了一个虚拟CPU,而实际上只有一个物理CPU。OS的工作就是将实际的CPU进行虚拟化。

最后Professor教授表示,今后不会再有这么多桃子的例子,因为他自己也不是很喜欢吃桃子。(但是作者很喜欢吧?)


我很想探讨一下这个故事中的比喻到底指代的什么。桃子当然指的是被虚拟化后共享的资源——除了物理CPU之外,物理内存也被进程这样共享。不过桃子和CPU相比有一个小问题:桃子是会被吃完的,也就是说,这是一种不可再生资源,和CPU可以不断重复利用的性质不同。那我们就当这些食客只是在舔桃子好啦……

所谓“很多人同时共享一个桃子会被注意到”也许只是Student学生随口一说的结果,但我觉得这一点说的更像是同步互斥问题。毕竟进程没有思想和感受,它们之间一般是相互隔离的,所谓“注意到”必然是进程通信或共享资源的结果,而这种时候是一定会出现同步互斥问题的。但是,如果这样认为,Professor教授给出的解决方案就有点儿怪了——这些人大部分时间都在干别的?我想这说的是CPU运行进程和设备I/O的并行化——I/O需要的时间很多,所以在需要进行I/O时,进程就主动放弃控制权,切换别的进程来继续占用CPU。这一点当然很好,不过好像并不能解决同步互斥问题。

不过这也并没有那么重要,希望Professor教授和Student在书里过得开心,吃点自己想吃的水果好啦。

本章课本见http://pages.cs.wisc.edu/~remzi/OSTEP/intro.pdf


这一章对全书内容做了一些简单的概括:

  • 用三个程序概括了本书将讲到的三个基本概念(虚拟化、并发、持久化)
  • 讲了一些OS的设计目标和OS的历史

基本概念概述

虚拟化

虚拟化是本书第一部分的主题。

CPU的虚拟化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <stdlib.h>
#include "common.h"

int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "usage: cpu <string>\n");
exit(1);
}
char *str = argv[1];

while (1) {
printf("%s\n", str);
Spin(1);
}
return 0;
}

上述程序中调用的Spin()函数(具体程序见本章附带的代码)会在运行1秒后返回。这个程序会不断运行,每秒输出一个A,如下:

1
2
3
4
5
6
7
8
prompt> gcc -o cpu cpu.c -Wall
prompt> ./cpu "A"
A
A
A
A
ˆC
prompt>

如果同时运行不同的程序实例,CPU会不断在程序之间切换,使得每个程序都认为自己独占了CPU,这被称为CPU的虚拟化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
prompt> ./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D &
[1] 7353
[2] 7354
[3] 7355
[4] 7356
A
B
D
C
A
B
D
C
A
C
B
D
...

而OS选择什么程序来运行是一种策略,之后我们会学到相关内容(进程调度)。

内存的虚拟化

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
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "common.h"

int
main(int argc, char *argv[])
{
if (argc != 2) {
fprintf(stderr, "usage: mem <value>\n");
exit(1);
}
int *p; // memory for pointer is on "stack"
p = malloc(sizeof(int)); // malloc'd memory is on "heap"
assert(p != NULL);
printf("(pid:%d) addr of p: %llx\n", (int) getpid(),
(unsigned long long) &p);
printf("(pid:%d) addr stored in p: %llx\n", (int) getpid(),
(unsigned long long) p);
*p = atoi(argv[1]); // assign value to addr stored in p
while (1) {
Spin(1);
*p = *p + 1;
printf("(pid:%d) value of p: %d\n", getpid(), *p);
}

return 0;
}

现代机器的内存模型就是一个数组,读写都需要给出地址。

上述程序所做的事很简单:

  • 分配一些内存
  • 打印内存的地址,以及程序的PID
  • 将数0放入新分配的内存的第一个位置(4字节的int)中
  • 循环,将p中存储的值+1

运行结果如下:

1
2
3
4
5
6
7
8
prompt> ./mem
(2134) address pointed to by p: 0x200000
(2134) p: 1
(2134) p: 2
(2134) p: 3
(2134) p: 4
(2134) p: 5
ˆC

如果仍然同时运行几个程序的实例,则会发现,每个程序都在同一地址处分配内存,而且对这一内存处存储的值的更新是相互独立的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
prompt> ./mem &; ./mem &
[1] 24113
[2] 24114
(24113) address pointed to by p: 0x200000
(24114) address pointed to by p: 0x200000
(24113) p: 1
(24114) p: 1
(24114) p: 2
(24113) p: 2
(24113) p: 3
(24114) p: 3
(24113) p: 4
(24114) p: 4
...

这说明OS对内存进行了虚拟化,每个进程访问的是自己的虚拟地址空间。

并发

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
#include <stdio.h>
#include <stdlib.h>
#include "common_threads.h"

volatile int counter = 0;
int loops;

void *worker(void *arg) {
int i;
for (i = 0; i < loops; i++) {
counter = counter + 1;
}
pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "usage: threads <loops>\n");
exit(1);
}
loops = atoi(argv[1]);
pthread_t p1, p2;
printf("Initial value : %d\n", counter);
Pthread_create(&p1, NULL, worker, NULL);
Pthread_create(&p2, NULL, worker, NULL);
Pthread_join(p1, NULL);
Pthread_join(p2, NULL);
printf("Final value : %d\n", counter);
return 0;
}

这一程序通过调用Pthread_create创建了两个线程,分别将一个计数器自增N次,然后将计数器的结果输出。显然,正常情况下程序输出应该为2N。

1
2
3
4
prompt> gcc -o thread thread.c -Wall -pthread
prompt> ./thread 1000
Initial value : 0
inal value : 2000

但如果两个线程执行的次数N比较大,则程序的输出可能不再会为2N,而且会不太稳定。这是由于+1的操作不是原子的。

1
2
3
4
5
6
prompt> ./thread 100000
Initial value : 0
Final value : 143012 // huh??
prompt> ./thread 100000
Initial value : 0
Final value : 137298 // what the??

这体现了并发中可能出现的一些问题,我们将要在本书的第二部分讲到这些问题。

持久化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/types.h>
#include <string.h>

void do_work() {
int fd = open("/tmp/file", O_WRONLY | O_CREAT | O_TRUNC,
S_IRUSR | S_IWUSR);
assert(fd >= 0);
char buffer[20];
sprintf(buffer, "hello world\n");
int rc = write(fd, buffer, strlen(buffer));
assert(rc == strlen(buffer));
printf("wrote %d bytes\n", rc);
fsync(fd);
close(fd);
}

int main(int argc, char *argv[]) {
do_work();
return 0;
}

上述代码会创建文件/tmp/file,并在里面写入字符串hello world

内存是一种易失性存储,所以需要能够持续性地存储程序的硬件和软件,也就是硬盘(SSD)和文件系统。

和虚拟化的内存地址空间相比,因为用户通常会使用文件来共享信息,所以OS并不会为每个应用进程创建虚拟化的磁盘。OS向硬盘写数据的过程是十分复杂的,但OS对此进行了抽象,可以通过系统调用来访问设备。因此OS可以被看成是一个标准库。

OS的设计目标

  • 抽象:使系统更易用
  • 高性能
  • 保护:在应用程序之间,以及应用程序和系统之间提供保护和隔离
  • 可靠性
  • 节能、安全性、可移动性……

OS的历史

  • 早期操作系统(大型机批处理系统):基本只是标准库,需要操作员参与管理
  • 中期操作系统:提供了文件系统和保护机制,系统调用和硬件特权级的概念出现了
  • 多道程序系统:内存保护和并发的概念
  • 现代操作系统:……

本章课本见http://pages.cs.wisc.edu/~remzi/OSTEP/dialogue-virtualization.pdf


这是全书开头的第一章,奠定了全书逗比的基调(雾)。这一章主要只是用来扯皮的,真正的介绍性内容在下一章。

本章讲述了一位叫“Professor”的教授和一位叫“Student”的学生的故事。

Professor指出,“Three Easy Pieces”这个题目是为了致敬费曼的“Six Easy Pieces”这本书。因为操作系统只有物理学的一半那么难,所以核心概念也只有物理学的一半那么多。(真的吗?)

我们将要讲授的3个核心概念是:虚拟化(virtualization),并发(concurrency)和持久化(persistence)。

我们将要学到OS如何工作,具体内容包括:

  • OS如何决定下一个将在CPU上运行的是什么程序
  • 如何在虚拟内存系统中处理内存过载
  • 如何管理磁盘上的信息
  • 如何建立一个可靠的分布式系统
  • 等等

Professor对学习者的建议:

  • 上课,听讲
  • 每周结束时读这本书
  • 考试之前再读一遍书(虽然可能我没有那么多的时间,我就没有)
  • 做教授留的作业和项目

Professor:“不闻不若闻之,闻之不若见之,见之不若知之,知之不若行之;学至于行之而止矣。”(荀子《儒效篇》)

课程内容概述

TODO

练习

来自lab5 用户进程 在线练习lab5 spoc 思考题

选择填空题

下列叙述中正确的是()

  • lab5建立了用户进程,且0~3GB都是用户可访问空间,用户进程可进行正常读写
  • lab5建立了用户进程,且3GB~4GB都是内核可访问空间,内核可进行正常读写
  • lab5中的第一个用户进程是内核创建的。
  • lab5中的用户进程可通过fork创建新的用户进程。

lab5中建立了用户进程这一点没啥问题。用户和内核可访问的空间这点有问题。简单来说,内核虚拟内存空间处于0xC0000000~0xF8000000位置(KERNBASE~KERNTOP),用户进程可访问的虚拟内存空间位于0x0080000~-0xB0000000位置(UTEXT~USERTOP)。

这样ucore把用户进程的虚拟地址空间分了两块,一块与内核线程一样,是所有用户进程都共享的内核虚拟地址空间,映射到同样的物理内存空间中,这样在物理内存中只需放置一份内核代码,使得用户进程从用户态进入核心态时,内核代码可以统一应对不同的内核程序;另外一块是用户虚拟地址空间,虽然虚拟地址范围一样,但映射到不同且没有交集的物理内存空间中。这样当ucore把用户进程的执行代码( 即应用程序的执行代码) 和数据( 即应用程序的全局变量等) 放到用户虚拟地址空间中时,确保了各个进程不会“非法”访问到其他进程的物理内存空间。


lab5通过do_execve函数执行新的程序,为此需要完成()

  • 更新用户进程的context
  • 更新用户进程的代码内容
  • 更新用户进程的数据内容
  • 更新用户进程的页表基址

Lab5中的do_execve函数的主要功能就是,放弃当前程序的一切内存空间等资源,将新的程序填充到自己里面。所以显然上述内容都要更新。

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
31
32
33
34
35
36
// do_execve - call exit_mmap(mm)&put_pgdir(mm) to reclaim memory space of current process
// - call load_icode to setup new memory space accroding binary prog.
int
do_execve(const char *name, size_t len, unsigned char *binary, size_t size) {
struct mm_struct *mm = current->mm;
if (!user_mem_check(mm, (uintptr_t)name, len, 0)) {
return -E_INVAL;
}
if (len > PROC_NAME_LEN) {
len = PROC_NAME_LEN;
}

char local_name[PROC_NAME_LEN + 1];
memset(local_name, 0, sizeof(local_name));
memcpy(local_name, name, len);

if (mm != NULL) {
lcr3(boot_cr3);
if (mm_count_dec(mm) == 0) {
exit_mmap(mm);
put_pgdir(mm);
mm_destroy(mm);
}
current->mm = NULL;
}
int ret;
if ((ret = load_icode(binary, size)) != 0) {
goto execve_exit;
}
set_proc_name(current, local_name);
return 0;

execve_exit:
do_exit(ret);
panic("already exit: %e.\n", ret);
}

ucore docs中指出,此函数的主要工作流程如下:

首先为加载新的执行码做好用户态内存空间清空准备。如果mm不为NULL,则设置页表为内核空间页表,且进一步判断mm的引用计数减1后是否为0,如果为0,则表明没有进程再需要此进程所占用的内存空间,为此将根据mm中的记录,释放进程所占用户空间内存和进程页表本身所占空间。最后把当前进程的mm内存管理指针为空。由于此处的initproc是内核线程,所以mm为NULL,整个处理都不会做。
接下来的一步是加载应用程序执行码到当前进程的新创建的用户态虚拟空间中。这里涉及到读ELF格式的文件,申请内存空间,建立用户态虚存空间,加载应用程序执行码等。load_icode函数完成了整个复杂的工作。


lab5通过do_icode函数执行新的程序,为此需要完成()

  • 设置用户堆栈
  • 修改页表
  • 根据ELF执行文件的格式描述分配内存并填写内容
  • 设置用户态的EFLAG寄存器不可屏蔽中断

ucore docs中给出的函数工作流程:

  1. 调用mm_create函数来申请进程的内存管理数据结构mm所需内存空间,并对mm进行初始化;
  1. 调用setup_pgdir来申请一个页目录表所需的一个页大小的内存空间,并把描述ucore内核虚空间映射的内核页表( boot_pgdir所指) 的内容拷贝到此新目录表中,最后让mm->pgdir指向此页目录表,这就是进程新的页目录表了,且能够正确映射内核虚空间;
  2. 根据应用程序执行码的起始位置来解析此ELF格式的执行程序,并调用mm_map函数根据ELF格式的执行程序说明的各个段(代码段、数据段、BSS段等) 的起始位置和大小建立对应的vma结构,并把vma插入到mm结构中,从而表明了用户进程的合法用户态虚拟地址空间;
  3. 调用根据执行程序各个段的大小分配物理内存空间,并根据执行程序各个段的起始位置确定虚拟地址,并在页表中建立好物理地址和虚拟地址的映射关系,然后把执行程序各个段的内容拷贝到相应的内核虚拟地址中,至此应用程序执行码和数据已经根据编译时设定地址放置到虚拟内存中了;
  4. 需要给用户进程设置用户栈,为此调用mm_mmap函数建立用户栈的vma结构,明确用户栈的位置在用户虚空间的顶端,大小为256个页,即1MB,并分配一定数量的物理内存且建立好栈的虚地址<-->物理地址映射关系;
  5. 至此,进程内的内存管理vma和mm数据结构已经建立完成,于是把mm->pgdir赋值到cr3寄存器中,即更新了用户进程的虚拟内存空间,此时的initproc已经被hello的代码和数据覆盖,成为了第一个用户进程,但此时这个用户进程的执行现场还没建立好;
  6. 先清空进程的中断帧,再重新设置进程的中断帧,使得在执行中断返回指令“iret”后,能够让CPU转到用户态特权级,并回到用户态内存空间,使用用户态的代码段、数据段和堆栈,且能够跳转到用户进程的第一条指令执行,并确保在用户态能够响应中断;

其中设置中断帧这一步是Lab5的练习1。


关于进程管理的COW(Copy On Write)机制叙述正确的是()

  • 父进程创建子进程需要复制父进程的内存空间
  • 父进程创建子进程需要给子进程分配内核堆栈
  • 父进程创建子进程需要给子进程分配用户堆栈
  • 父进程创建子进程需要创建子进程的页表,但不复制父进程内存空间

总之不需要复制也不需要分配,只是创建一个新的页表,然后和父进程页表指向相同位置。需要进行写时就新创建一页。

简答题

第一个用户进程创建有什么特殊的?

用户态代码段的初始化

好吧,答案是这么说的,但是我并不认同……总之,本实验中第一个用户进程是由第二个内核线程initproc通过把hello应用程序执行
码覆盖到initproc的用户虚拟内存空间来创建的。具体的大概方法是调用kernel_execve()函数,触发SYS_exec系统中断,然后继续调用do_execve()load_icode()函数完成这一过程。其他用户进程是用户进程通过SYS_fork系统调用创建的(大概)。


系统调用的参数传递过程?

参见:用户态函数syscall()中的汇编代码。下面的代码摘自user/libs/syscall.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline int
syscall(int num, ...) {
va_list ap;
va_start(ap, num);
uint32_t a[MAX_ARGS];
int i, ret;
for (i = 0; i < MAX_ARGS; i ++) {
a[i] = va_arg(ap, uint32_t);
}
va_end(ap);

asm volatile (
"int %1;"
: "=a" (ret)
: "i" (T_SYSCALL),
"a" (num),
"d" (a[0]),
"c" (a[1]),
"b" (a[2]),
"D" (a[3]),
"S" (a[4])
: "cc", "memory");
return ret;
}

很显然,参数是这样传递的:

  • 触发INT 0x80中断(T_SYSCALL)
  • eax中存放系统调用号
  • edx、ecx、ebx、edi、esi中按照顺序存放前五个参数
  • 返回值存放在eax中

令人感到奇怪的是,这与Linux系统在x86架构下一般的习惯并不相符。(https://stackoverflow.com/questions/2535989/what-are-the-calling-conventions-for-unix-linux-system-calls-on-i386-and-x86-6,其中给出的顺序是ebx、ecx、edx、esi、edi)。不过这并不是很重要,总之这个顺序与kern/syscall/syscall.c中对应的代码是相符的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void
syscall(void) {
struct trapframe *tf = current->tf;
uint32_t arg[5];
int num = tf->tf_regs.reg_eax;
if (num >= 0 && num < NUM_SYSCALLS) {
if (syscalls[num] != NULL) {
arg[0] = tf->tf_regs.reg_edx;
arg[1] = tf->tf_regs.reg_ecx;
arg[2] = tf->tf_regs.reg_ebx;
arg[3] = tf->tf_regs.reg_edi;
arg[4] = tf->tf_regs.reg_esi;
tf->tf_regs.reg_eax = syscalls[num](arg);
return ;
}
}
print_trapframe(tf);
panic("undefined syscall %d, pid = %d, name = %s.\n",
num, current->pid, current->name);
}

Ref: https://www.ibm.com/developerworks/library/l-ia/index.html


getpid的返回值放在什么地方了?

参见:用户态函数syscall()中的汇编代码

这个问题很平凡,只是放在eax里面了而已。(又不是fork……)


ucore的内存布局中,页表、用户栈、内核栈在逻辑地址空间中的位置?

参见kern/mm/memlayout.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#define VPT 0xFAC00000

#define KSTACKPAGE 2 // # of pages in kernel stack

#define KSTACKSIZE (KSTACKPAGE * PGSIZE) // sizeof kernel stack

#define USERTOP 0xB0000000

#define USTACKTOP USERTOP

#define USTACKPAGE 256 // # of pages in user stack

#define USTACKSIZE (USTACKPAGE * PGSIZE) // sizeof user stack

事实上,页表位于内核虚拟空间0xFAC00000~0xFB000000位置,用户栈位于用户虚拟空间?~0xB0000000位置(因为栈是向下增长的),内核栈位于内核虚拟空间……诶怎么没说内核栈在什么位置?我猜是在~0xF8000000位置吧。

这个字符画的水平十分高超:

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
31
32
33
34
35
36
37
38
39
40
/* *
* Virtual memory map: Permissions
* kernel/user
*
* 4G ------------------> +---------------------------------+
* | |
* | Empty Memory (*) |
* | |
* +---------------------------------+ 0xFB000000
* | Cur. Page Table (Kern, RW) | RW/-- PTSIZE
* VPT -----------------> +---------------------------------+ 0xFAC00000
* | Invalid Memory (*) | --/--
* KERNTOP -------------> +---------------------------------+ 0xF8000000
* | |
* | Remapped Physical Memory | RW/-- KMEMSIZE
* | |
* KERNBASE ------------> +---------------------------------+ 0xC0000000
* | Invalid Memory (*) | --/--
* USERTOP -------------> +---------------------------------+ 0xB0000000
* | User stack |
* +---------------------------------+
* | |
* : :
* | ~~~~~~~~~~~~~~~~ |
* : :
* | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* | User Program & Heap |
* UTEXT ---------------> +---------------------------------+ 0x00800000
* | Invalid Memory (*) | --/--
* | - - - - - - - - - - - - - - - |
* | User STAB Data (optional) |
* USERBASE, USTAB------> +---------------------------------+ 0x00200000
* | Invalid Memory (*) | --/--
* 0 -------------------> +---------------------------------+ 0x00000000
* (*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
* "Empty Memory" is normally unmapped, but user programs may map pages
* there if desired.
*
* */

在do_execve中的的当前进程如何清空地址空间内容的?在什么时候开始使用新加载进程的地址空间?

清空进程地址空间是在initproc所在进程地址空间
CR3设置成新建好的页表地址后,开始使用新的地址空间

这个答案简直语无伦次……总之上面已经说过do_execve()函数的流程了。清空地址空间是通过释放mm_struct结构完成的(虽然initproc并不会这么做,因为它直接用的是内核的mm_struct)。至于页表,do_execve()在释放mm_struct之前会先换成内核自己的页表;load_icode()中,设置进程的新mm_struct时会加载新页表(第5步)。


新加载进程的第一级页表的建立代码在哪?

load_icode()的第2步中,调用了setup_pgdir(mm)


do_execve在处理中是如何正确区分出用户进程和线程的?并为此采取了哪些不同的处理?

我猜这道题说的是内核线程吧。

1
2
3
4
5
6
7
8
9
if (mm != NULL) {
lcr3(boot_cr3);
if (mm_count_dec(mm) == 0) {
exit_mmap(mm);
put_pgdir(mm);
mm_destroy(mm);
}
current->mm = NULL;
}

内核线程的mm直接借用了内核自己的mm,所以这里处理了这一点。


第一个内核线程和第一个用户进程的创建有什么不同?

  • 相应线程的内核栈创建时,多了SS和ESP的设置;
  • 用户进程需要创建用户地址空间,并把用户代码复制到用户地址空间;

设置ss和esp对应lab5的练习1:在用户进程的内核栈中存放的trapframe中填写对应的寄存器。其次就是要load_icode了,不能直接调用内核中的函数。而且不能和内核共用页表,要新建自己的页表。


尝试跟踪分析新创建的用户进程的开始执行过程?

……反正我写的实验报告中是这么说的:

load_icode函数成功结束运行后,系统中断返回到exit的第一行代码。exit本身的执行过程在此暂时忽略。

exit线程执行结束之后,系统切换到initproc线程,它进行检查并退出。

差不多吧。


为什么新进程的内核堆栈可以先于进程地址空间复制进行创建?

内核栈在进程的内核地址空间,而各进程的内核地址空间是共享的。


进程复制的代码在哪?复制了哪些内容?

以下代码来自lab5/kern/process/proc.c

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
int ret = -E_NO_FREE_PROC;
struct proc_struct *proc;
if (nr_process >= MAX_PROCESS) {
goto fork_out;
}
ret = -E_NO_MEM;

// 1. call alloc_proc to allocate a proc_struct
proc = alloc_proc();
if (proc == NULL) { // 参考答案添加了错误处理
goto fork_out;
}
proc->parent = current; // 参考了答案
// 2. call setup_kstack to allocate a kernel stack for child process
if (setup_kstack(proc) != 0) { // 参考答案添加了错误处理
goto bad_fork_cleanup_proc;
}
// 3. call copy_mm to dup OR share mm according clone_flag
// CLONE_VM表示分享;实际上因为都在内核态所以什么都没做,只是assert NULL了
if (copy_mm(clone_flags, proc) != 0) { // 参考答案添加了错误处理
goto bad_fork_cleanup_kstack;
}
// 4. call copy_thread to setup tf & context in proc_struct
copy_thread(proc, stack, tf);
// 5. insert proc_struct into hash_list && proc_list
// 参考了答案:关中断的原因是,进程号要求唯一性,此操作需要为原子操作,防止被打断而重复添加
// 所以参考答案是很有必要的。但是我认为在实验指导书中也应该说明一下。
bool intr_flag;
local_intr_save(intr_flag);
{
proc->pid = get_pid();
hash_proc(proc);
// list_add_before(&proc_list, &proc->list_link);
set_links(proc);
}
local_intr_restore(intr_flag);
// 6. call wakeup_proc to make the new child process RUNNABLE
wakeup_proc(proc);
// 7. set ret vaule using child proc's pid
ret = proc->pid;

fork_out:
return ret;

bad_fork_cleanup_kstack:
put_kstack(proc);
bad_fork_cleanup_proc:
kfree(proc);
goto fork_out;
}

可以看出,以上代码中复制的主要内容是mm_struct内存管理结构(相当于复制了一份虚拟内存及其中的内容)。


进程复制过程中有哪些修改?为什么要修改?

参见上一题的代码,需要修改的内容包括:

  • 为新进程分配一个新的进程控制块
  • 分配一个新的内核栈
  • 修改内核栈中存储的trapframe的内容
  • 分配一个新的PID

分析第一个用户进程的创建流程,说明进程切换后执行的第一条是什么。

以下内容摘自ucore docs Lab5:

在确定了用户进程的执行代码和数据,以及用户进程的虚拟空间布局后,我们可以来创建用户进程了。在本实验中第一个用户进程是由第二个内核线程initproc通过把hello应用程序执行码覆盖到initproc的用户虚拟内存空间来创建的。
initproc的执行主体是init_main函数,这个函数在缺省情况下是执行宏KERNEL_EXECVE(hello),而这个宏最终会调用kernel_execve函数来执行SYS_exec系统调用。
ucore收到此系统调用后,最终通过do_execve函数来完成用户进程的创建工作。此函数的主要工作流程如下:

  1. 首先为加载新的执行码做好用户态内存空间清空准备。如果mm不为NULL,则设置页表为内核空间页表,且进一步判断mm的引用计数减1后是否为0,如果为0,则表明没有进程再需要此进程所占用的内存空间,为此将根据mm中的记录,释放进程所占用户空间内存和进程页表本身所占空间。最后把当前进程的mm内存管理指针为空。由于此处的initproc是内核线程,所以mm为NULL,整个处理都不会做。
  2. 接下来的一步是加载应用程序执行码到当前进程的新创建的用户态虚拟空间中。这里涉及到读ELF格式的文件,申请内存空间,建立用户态虚存空间,加载应用程序执行码等。load_icode函数完成了整个复杂的工作。
    load_icode函数的主要工作就是给用户进程建立一个能够让用户进程正常运行的用户环境。此函数有一百多行,完成了如下重要工作:
  3. 调用mm_create函数来申请进程的内存管理数据结构mm所需内存空间,并对mm进行初始化;
  4. 调用setup_pgdir来申请一个页目录表所需的一个页大小的内存空间,并把描述ucore内核虚空间映射的内核页表(boot_pgdir所指)的内容拷贝到此新目录表中,最后让mm->pgdir指向此页目录表,这就是进程新的页目录表了,且能够正确映射内核虚空间;
  5. 根据应用程序执行码的起始位置来解析此ELF格式的执行程序,并调用mm_map函数根据ELF格式的执行程序说明的各个段(代码段、数据段、BSS段等) 的起始位置和大小建立对应的vma结构,并把vma插入到mm结构中,从而表明了用户进程的合法用户态虚拟地址空间;
  6. 调用根据执行程序各个段的大小分配物理内存空间,并根据执行程序各个段的起始位置确定虚拟地址,并在页表中建立好物理地址和虚拟地址的映射关系,然后把执行程序各个段的内容拷贝到相应的内核虚拟地址中,至此应用程序执行码和数据已经根据编译时设定地址放置到虚拟内存中了;
  7. 需要给用户进程设置用户栈,为此调用mm_mmap函数建立用户栈的vma结构,明确用户栈的位置在用户虚空间的顶端,大小为256个页,即1MB,并分配一定数量的物理内存且建立好栈的虚地址<-->物理地址映射关系;
  8. 至此,进程内的内存管理vma和mm数据结构已经建立完成,于是把mm->pgdir赋值到cr3寄存器中,即更新了用户进程的虚拟内存空间,此时的initproc已经被hello的代码和数据覆盖,成为了第一个用户进程,但此时这个用户进程的执行现场还没建立好;
  9. 先清空进程的中断帧,再重新设置进程的中断帧,使得在执行中断返回指令“iret”后,能够让CPU转到用户态特权级,并回到用户态内存空间,使用用户态的代码段、数据段和堆栈,且能够跳转到用户进程的第一条指令执行,并确保在用户态能够响应中断;
    至此,用户进程的用户环境已经搭建完毕。此时initproc将按产生系统调用的函数调用路径原路返回,执行中断返回指令“iret”(位于trapentry.S的最后一句)后,将切换到用户进程hello的第一条语句位置_start处(位于user/libs/initcode.S的第三句) 开始执行。

什么是写时复制?

写时复制(Copy-on-Write,也缩写为COW),顾名思义,就是在写入时才真正复制一份内存进行修改。COW最早应用在*nix系统中对线程与内存使用的优化,后面广泛的被使用在各种编程语言中,如C++的STL等。在PHP内核中,COW也是主要的内存优化手段。在前面关于变量和内存的讨论中,引用计数对变量的销毁与回收中起着至关重要的标识作用。引用计数存在的意义,就是为了使得COW可以正常运作,从而实现对内存的优化使用。(50-写时复制COW机制


写时复制的页表在什么时候进行复制?共享地址空间和写时复制有什么不同?

在发生写操作时进行复制。共享地址空间并不在意是否发生写操作……


存在有多个(n>2)进程具有父子关系,且采用了COW机制的情况。这个情况与只有父子两个进程的情况相比,在设计COW时,需要注意的新问题是什么?有何解决方案?

大概发生一次写操作可能有多个页表发生修改。

实践题

尝试在panic函数中获取并输出用户栈和内核栈的函数嵌套信息和函数调用参数信息,然后在你希望的地方人为触发panic函数,并输出上述信息。

没写。


尝试在panic函数中获取和输出页表有效逻辑地址空间范围和在内存中的逻辑地址空间范围,然后在你希望的地方人为触发panic函数,并输出上述信息。

没写。


尝试在进程运行过程中获取内核空间中各进程相同的页表项(代码段)和不同的页表项(内核堆栈)?

没写。。。

OS

课程内容概述

  • 信号量
    • 信号量简介
    • 信号量使用
      • 互斥访问
      • 条件同步
  • 管程
    • 条件变量
    • 管程的语义
  • 经典问题
    • 生产者-消费者问题
      • 信号量实现
      • 管程实现
    • 哲学家就餐问题
    • 读者-写者问题

信号量(Semaphore)

信号量是操作系统提供的一种协调共享资源访问的方法。它和软件同步的区别是:

  • 软件同步是平等线程间的一种同步协商机制
  • 信号量是由操作系统进行管理的,它的地位高于进程(而非平等协商)

信号量由Dijkstra在20世纪60年代提出,目前仍然在OS中被使用。

信号量简介

信号是一种抽象数据类型:

  • 由一个整型变量(sem)和两个原子操作组成
  • sem:要共享的资源的数目
  • P()操作(Prolaag,尝试减少,请求资源时进行)
    • sem-1
    • sem<0,进入等待,否则继续运行
  • V()操作(Verhoog,增加,释放资源时进行)
    • sem+1
    • sem<=0,则唤醒一个等待进程

信号量的一些特点:

  • 信号量可以被认为是被保护的整数变量
    • 初始化完成后,只能通过P()和V()操作修改
    • 由操作系统保证,PV操作是原子操作
    • 可以保证不受应用进程的干扰
  • P()操作可能阻塞,但V()操作不会阻塞
  • 通常假定信号量是“公平的”
    • 线程不会被无限期阻塞在P()操作(实际系统中有一个最长时限的参数,超时之后错误返回)
    • 假定信号量等待按先进先出排队(但是在实际系统中公平有所偏差)

下面给出信号量在原理上的一个实现(之所以是原理上的实现,是因为实际实现时要考虑很多问题):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Semaphore {
int sem;
WaitQueue q;
}

Semaphore::P() {
sem--;
if (sem < 0) {
Add this thread t to q;
block(t);
}
}

Semaphore::V() {
sem++;
if (sem >= 0) {
Remove a thread t from q;
wakeup(t);
}
}

信号量使用

信号量一般可分为两类:

  • 二进制信号量:资源数目为0或1
  • 资源信号量:资源数目为任何非负值

下面讨论两个信号量的使用场景:

  • 互斥访问:临界区的互斥访问控制
  • 条件同步:线程间的事件等待
互斥访问

互斥访问的实现方法非常简单:

1
2
3
4
5
6
// 每类资源设置一个信号量,其初值为1
mutex = new Semaphore(1);
// 临界区的控制代码如下:
mutex->P();
Critical Section;
mutex->V();

在这种情况下,信号量的使用和锁相同。需要注意以下几点:

  • 必须成对使用P()操作和V()操作
  • P()操作保证互斥访问临界资源
  • V()操作在使用后释放临界资源
  • PV操作不能次序颠倒、重复或遗漏
条件同步

举例:线程A执行完X模块之后,线程B才能执行Y模块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 设置一个初值为0的信号量
condition = new Semaphore(0);

// Thread A
Module X {
...
}
condition.V();
...

// Thread B
...
condition.P();
Module Y {
...
}

管程(Monitor)

管程是一种用于多线程互斥访问共享资源的程序结构

  • 采用面向对象方法,简化了线程间的同步控制
  • 任一时刻最多只有一个线程执行管程代码
  • 正在管程中的线程可临时放弃管程的互斥访问,等待事件出现时恢复(这是最大的特点)

管程的组成:

  • 一个锁:控制管程代码的互斥访问
  • 入口队列:每次只能有一个线程进入
  • 0或多个条件变量:管理共享数据的并发访问

下面需要介绍一下条件变量了。

条件变量(Condition Variable)

条件变量是管程内的等待机制

  • 进入管程的线程因资源被占用而进入等待状态
  • 每个条件变量表示一种等待原因,对应一个等待队列
  • Wait()操作:
    • 将自己阻塞在等待队列中
    • 唤醒一个等待者或释放管程的互斥访问(即允许另外一个线程进入管程)
  • Signal()操作:
    • 将等待队列中的一个线程唤醒
    • 如果等待队列为空,这就相当于是一个空操作

条件变量在原理上的实现和信号量有些类似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Condition {
int numWaiting = 0;
WaitQueue q;
}

Condition::Wait(Lock lock) {
numWaiting++;
Add this thread t to q;
release(lock);
schedule(); // need mutex
acquire(lock);
}

Condition::Signal() {
if (numWaiting > 0) {
Remove a thread t from q;
wakeup(t); // need mutex
numWaiting--;
}
}

但是有很多不同的地方,如:

  • 对管程的互斥锁的释放和获得
  • signal和P语义的不同:PV操作必须是成对的,但signal/wait操作完全不需要保证这一点
  • wait和V语义的不同:V操作后线程可能会继续执行,但wait操作后,线程必然进入等待队列并阻塞
  • 执行signal/wait时,都默认已经获得了互斥锁

管程的语义

事实上管程一共有三种语义:

  • Mesa语义
  • Hoare语义
  • Hansen语义

以下内容参考了Piazza上的讨论CMU的课件

考虑如下情况:线程A在条件变量的等待队列中等待资源,此时线程B在该资源(或者说该条件变量)上执行signal操作。

Mesa语义
  • 线程B执行signal之后,不会立刻退出管程,而是执行到lock.release()之后才进入就绪态
  • 线程A会被移动到入口等待队列中
  • 在wait后被唤醒的进程不一定会被立刻调度,因此需要用while来检查条件
  • 大部分实际实现的管程采用的是这一语义

Mesa语义下管程的执行过程

Hoare语义
  • 线程B执行signal之后,迅速唤醒等待中的线程A,自己进入signal队列中(这个队列是此语义特有的)
  • 每次有线程退出时,先到signal队列中调度线程,如果signal队列空,才到入口等待队列调度线程
  • 实际实现中一般不采用,因为需要多一个队列,代价增大了

Hoare语义下管程的执行过程

Brinch Hanson语义
  • 线程B退出的同时才执行signal操作

Brinch Hanson语义下管程的执行过程

经典问题

生产者-消费者问题

有界缓冲区的生产者-消费者问题描述:

  • 一个或多个生产者在生成数据后放在一个缓冲区里
  • 单个消费者从缓冲区取出数据处理
  • 任何时候只能有一个生产者或消费者可访问缓冲区
信号量实现

问题分析:

  • 任何时刻只能有一个线程操作缓冲区,这是临界区(互斥访问)
  • 缓冲区空时,消费者必须等待生产者(条件同步)
  • 缓冲区满时,生产者必须等待消费者(条件同步)

用信号量描述每个约束:

  • 二进制信号量mutex:互斥
  • 资源信号量fullBuffers:缓冲区为满(信号量的值表示缓冲区中数据的个数)
  • 资源信号量emptyBuffers:缓冲区为空(信号量的值表示缓冲区中空位的个数)
  • 其中fullBuffers+emptyBuffers=缓冲区大小

(事实上,OSTEP中讨论了如果只使用一个资源信号量会导致死锁的问题,在此不再赘述了)

下面给出(原理上的)代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class BoundedBuffer {
mutex = new Semaphore(1);
fullBuffers = new Semaphore(0);
emptyBuffers = new Semaphore(n);
}

BoundedBuffer::Deposit(c) {
emptyBuffers->P();
mutex->P();
Add c to the buffer;
mutex->V();
fullBuffers->V();
}

BoundedBuffer::Remove(c) {
fullBuffers->P();
mutex->P();
Remove c from buffer;
mutex->V();
emptyBuffers->V();
}

注意P操作之间不能颠倒顺序。V操作不会阻塞,就无所谓了。

管程实现
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
class BoundedBuffer {
Lock lock;
int count = 0;
Condition notFull, notEmpty;
}

BoundedBuffer::Deposit(c) {
lock->Acquire();
while (count == n)
notFull.Wait(&lock);
Add c to the buffer;
count++;
notEmpty.signal();
lock->Release();
}

BoundedBuffer::Remove(c) {
lock->Acquire();
while (count == 0)
notEmpty.Wait(&lock);
Remove c from buffer;
count--;
notFull.signal();
lock->Release();
}
信号量和管程实现的对比

(以下内容摘自Piazza,修正了一些typo)

生产者-消费者问题的两种实现的对比

如图,信号量中存有int变量sem以及WaitQueue变量q,根据信号量的实现代码(左下角ppt),我们可以得出semq的含义:

  • q代表当前正在等待资源的线程组成的等待队列,若当前资源足够所有进程使用,q为空;
  • sem代表【到目前为止,若所有请求该资源的线程都能够获取该资源,那么资源还剩下多少(这里我们假设资源个数可以为负)】;
  • sem也可以有另一种理解:当sem非负时,sem代表剩余资源的个数;当sem为负数时,sem的绝对值代表等待队列q的长度。

而当我们使用条件变量解决有限资源问题时,我们通常会在条件变量之外,管程之中加入整型变量count(右上角ppt),来帮助条件变量记录当前剩余多少资源(非负)。查看条件变量的实现代码(右下角ppt),我们可以得出条件变量中整型变量numWaiting以及WaitQueue变量q的含义:

  • q代表当前正在等待资源的线程组成的等待队列,若当前资源足够所有进程使用,q为空;
  • numWaiting代表等待队列q的长度(非负)。

结合使用信号量以及条件变量解决有限资源问题的实例(左上及右上ppt),以及以上我们对信号量和条件变量的分析,我们可以得出以下结论:

  • 在任一状态,信号量中的q和条件变量中的q完全相同;
  • sem非负时,含义与管程中的count相同,此时numWaiting为0;
  • sem为负数时,sem的绝对值等于numWaiting,此时count为0。

在生产者-消费者这个问题实例中:

  • 信号量emptyBuffers与条件变量notFull是匹配的,满足上面3个条件,此时count在代码中以n - count的形式出现;
  • 信号量fullBuffers与条件变量notEmpty是匹配的,满足上面3个条件,此时count在代码中以count的形式出现;

综上所述,两种解决方法是完全等价的,至于为什么用管程实现更加安全方便,个人认为老师在视频中并没有解释得很清楚,和老师讨论后得出结论如下:

  • 用信号量的时候(左上角ppt),所有信号量都要自己维护,并配对好PV;
  • 用管程的时候,我们可以理解为BoundedBuffer继承了一个管程类,因此操作系统会给BoundedBuffer中每一个方法自动加上锁(即右上角ppt中的lock->Acquire()lock->Release()函数并不用自己写,是系统加上的),因此更加安全可控,容易查错。

但是个人认为使用条件变量也要根据条件配对好Wait和Signal函数,因此不比使用信号量更容易安全,这个问题见仁见智吧,但如果考试时候问到怎么回答大家懂的~

更新:ucore lab7中实现信号量的sem值非负,这样看来ucore中信号量的sem值和条件变量中的count值应该是完全相等的。

哲学家就餐问题

问题描述:

  • 5个哲学家围绕在一张圆桌周围

  • 桌子上有5根筷子(或者说叉子……随便啦)

  • 哲学家的动作包括思考和进餐

  • 进餐时一个哲学家需要自己两边的两根筷子

  • 如何保证哲学家们的动作有序进行,既不发生饥饿也不发生死锁?

  • 方案1:

    • 每个筷子用一个信号量表示,sem=1
    • 哲学家先拿第一根筷子,再拿第二根筷子,然后吃,最后放回两根筷子
    • 多数情况下这一算法可行;但极端情况下会出现死锁,比如所有哲学家同时拿左边的筷子
  • 方案2:

    • 除了每根筷子的信号量之外,再加上一个互斥信号量,同时只能有一个哲学家就餐
    • 能够保证顺序吃饭,但是浪费了资源和时间
  • 方案3:

    • 和方案1一样,使用5个信号量表示筷子
    • 哲学家根据编号不同,拿取筷子的顺序不同
    • 此时没有死锁,且允许两个人同时就餐
信号量实现

这一实现和ucore lab中给出的使用信号量的实现不太一样,而是参考了OSTEP中的做法(更准确地说是Dijkstra本人的做法)。

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
// Initialization
Semaphore forks[5];
for (int i = 0; i < 5; i++)
forks[i] = new Semaphore(1);

// Helper functions
int left(int p) { return p; }
int right(int p) { return (p + 1) % 5; }

// Thread x
void Philosopher(int x) {
// Switch between thinking and eating
while (true) {
think();
// get forks
if (p == 4) { // break dependency
forks[right(x)].P();
forks[left(x)].P();
}
else {
forks[left(x)].P();
forks[right(x)].P();
}
eat();
// put forks
forks[left(x)].V();
forks[right(x)].V();
}
}

读者-写者问题

问题描述:对于一个共享数据,有两类使用者

  • 读者:只读取数据,不修改(可以同时读)
  • 写者:读取和修改数据(不可以同时写)
  • 读写是互斥的

事实上,也需要考虑到,至少有两种可能的策略(而且还会有更多):

  • 读者优先策略:
    • 只要有读者正在读状态,后来的读者就能直接进入
    • 如果读者不断进入,则写者就处于饥饿
  • 写者优先策略
    • 只要有写者就绪,写者应尽快执行写操作(后来的读者需要阻塞)
    • 如果写者持续不断就绪,则读者就处于饥饿
信号量实现

用信号量描述每个约束:

  • 信号量WriteMutex
    • 控制读写操作的互斥
    • 初始化为1
  • 读者计数Rcount
    • 正在进行读操作的读者数目
    • 初始化为0
  • 信号量CountMutex
    • 保护对读者计数的互斥修改
    • 初始化为1

解决方案:

  • 读者的互斥锁只针对于第一个读者,之后不再判断
  • 因为Rcount也需要保护,所以外面也加上互斥锁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Writer() {
WriteMutex.P();
write;
WriteMutex.V();
}

void Reader() {
CountMutex.P();
if (Rcount == 0)
WriteMutex.P();
Rcount++;
CountMutex.V();

read;

CountMutex.P();
Rcount--;
if (Rcount == 0)
WriteMutex.V();
CountMutex.V();
}

在这一实现中,只要有读者开始阅读,就必须等到全部读者都离开才能进行写操作。即使有写操作在等待,读者仍然先于写者,说明这是一种读者优先策略。

管程实现

管程中包括以下内容:

  • 一个互斥锁
  • 4个状态变量
  • 2个条件变量:可读/可写

从判断条件可以看出,这一实现采用的是写者优先策略。不过其实我还没想明白能否把对AWWW变量的修改移动到while循环外面。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Database {
Lock lock; // 管程的互斥锁
int AR = 0; // Active Readers
int AW = 0; // Active Writers
int WR = 0; // Waiting Readers
int WW = 0; // Waiting Writers
Condition okToRead, okToWrite;
}

// 两个基本操作
Database::Read() {
StartRead(); // Wait until no writers
read database;
DoneRead(); // Exit & wake up waiting writers
}

Database::Write() {
StartWrite(); // Waite until no readers/writers;
write database;
DoneWrite(); // Exit & wake up waiting readers/writers
}

Private Database::StartRead() {
lock.Acquire();
while (AW + WW > 0) {
WR++;
okToRead.wait(&lock);
WR--;
}
AR++;
lock.Release();
}

Private Database::DoneRead() {
lock.Acquire();
AR--;
if (AR == 0 && WW > 0)
okToWrite.signal();
lock.Release();
}

Private Database::StartWrite() {
lock.Acquire();
while (AW + AR > 0) {
WW++;
okToWrite.wait(&lock);
WW--;
}
AW++;
lock.Release();
}

Private Database::DoneWrite() {
lock.Acquire();
AW--;
if (WW > 0)
okToWrite.signal();
else if (AW > 0)
okToRead.broadcast();
lock.Release();
}

练习

来自lec18 信号量与管程 在线练习同步互斥(lec 18) spoc 思考题

选择题

如果有5个进程共享同一程序段,每次允许3个进程进入该程序段,若用PV操作作为同步机制,则信号量S为-1时表示什么()

  • 有四个进程进入了该程序段
  • 有一个进程在等待
  • 有三个进程进入了程序段,有一个进程在等待
  • 有一个进程进入了该程序段,其余四个进程在等待

一般来说,信号量实现中会满足,它的整数值如果为负数,则负数的绝对值表示等待中的线程数量。当然似乎也有些实现不是这么做的。


2元信号量可以初始化为()

  • 0或1
  • 0或-1
  • 只能为1
  • 任意值

之所以可以初始化为0或1,是因为二元信号量至少有两种不同的使用场景:

  • 资源数目为1,如只能互斥访问的代码关键区
  • 代码条件等待,这种情况下有可能会先执行V操作,再执行P操作

多个进程对信号量S进行了6次P操作,2次V操作后,现在信号量的值是-3,与信号量S相关的处于阻塞状态的进程有几个()

  • 1个
  • 2个
  • 3个
  • 4个

等待进程的数量就是信号量的值的负数。不过这样可以推导出,请求过信号量资源的进程为6个,得到资源的为2个,现在仍在等待的进程为3个,说明信号量的初值为6-2-3=1。


(2011年全国统考)有两个并发执行的进程P1和P2,共享初值为1的变量x。P1对x加1,P2对x减1。加1和减1操作的指令序列分别如下所示;两个操作完成后,x的值()。

1
2
3
4
加一操作    		减一操作
Load R1,x load R2,x
inc R1 dec R2
store x,R1 store x,R2
  • 可能为-1或3
  • 只能为1
  • 可能为0、1或2
  • 可能为-1、0、1、1或2

分成以下几种情况讨论:

  • P1和P2的执行完全错开(即加载了不同的x的值):结果正确,x=1
  • P1和P2加载了相同的x的值:结果依赖于P1先写还是P2先写,如果P1先写则x=2,否则x=0

管程的主要特点有()

  • 局部数据变量只能被管程的过程访问
  • 一个进程通过调用管程的一个过程进入管程
  • 不会出现死锁
  • 在任何时候,只能有一个进程在管程中执行

课上好像没有讲这么多管程的特点……


关于管程的叙述正确的是()

  • 管程中的局部数据变量可以被外部直接访问
  • 当一个进程在管程中执行时,调用管程的其他进程都不会被阻塞
  • 在管程中的signal()与信号量中的signal()操作实现及意义完全相同
  • 管程通过使用条件变量提供对同步的支持,这些条件变量包含在管程中,并且只有管程才能访问

管程中的局部变量只能通过管程的过程访问。一个进程在管程中执行时,调用管程的其他过程都会被阻塞。管程中的signal是通过条件变量实现的,而不是信号量,所以意义有微妙的不同。

简答题

什么是信号量?它与软件同步方法的区别在什么地方?

信号量是由操作系统提供的一种协调共享资源访问的方法。信号量是一种抽象数据类,由一个被保护的整形变量(sem)和P()、V()两个原子操作组成,表示系统资源的数量。

区别:

  • 软件同步是平等线程间的一种同步协商机制;
  • 信号量是由地位高于进程的管理者OS协调的同步机制。

自旋锁为什么无法按先来先服务方式使用资源?

原因:自旋锁是由TS指令实现的临界区申请操作,第一个检测到临界区空闲的申请者而不是第一个开始检测的申请者进入。也就是说,访问顺序是由硬件随机决定的。如果要实现FIFO方式,一般都需要一个队列。


下面是一种P操作的实现伪码。它能按FIFO顺序进行信号量申请吗?

1
2
3
4
5
while (s.count == 0) {  //没有可用资源时,进入挂起状态;
调用进程进入等待队列s.queue;
阻塞调用进程;
}
s.count--; //有可用资源,占用该资源;

参考回答: 它的问题是,不能按FIFO进行信号量申请。
它的一种出错的情况如下:

  • 一个线程A调用P()原语时,由于线程B正在使用该信号量而进入阻塞状态;注意,这时value的值为0。
  • 线程B放弃信号量的使用,线程A被唤醒而进入就绪状态,但没有立即进入运行状态;注意,这里value为1。
  • 在线程A处于就绪状态时,处理机正在执行线程C的代码;线程C这时也正好调用P()原语访问同一个信号量,并得到使用权。注意,这时value又变回0。
  • 线程A进入运行状态后,重新检查value的值,条件不成立,又一次进入阻塞状态。
  • 至此,线程C比线程A后调用P原语,但线程C比线程A先得到信号量。

虽然参考答案是这么说的,但我觉得这有些牵强:事实上这种错误情况取决于V操作的语义。如果V操作能够保证使唤醒的进程立刻抢占处理机,就不会发生以上问题了。这就类似于管程的Hoare语义和Mesa语义的区别。

Piazza上有一个类似的讨论。事实上,在一般的Mesa语义下,使用if进行检查根本就是不正确的,需要用while。改用while之后,确实能保证正确性,但是FIFO无法保证了。


什么是条件同步?如何使用信号量来实现条件同步?

条件同步是指线程间的事件等待。

条件同步的实现方法:定义初始值为0的信号量,事件触发进程使用V()操作表示事件出现,事件等待进程使用P()操作表示开始等待事件。

也就是说,此处P和V操作的顺序是颠倒的。


什么是生产者-消费者问题?

  • 生产者生成数据,并放入缓冲区
  • 消费者从缓冲区取出数据,进行处理
  • 任何时间只有一个进程访问缓冲区

为什么在生产者-消费者问题中先申请互斥信号量会导致死锁?

如果先申请互斥信号量,后申请资源信号量,则在两种情况下可能会出现循环等待:

  • 生产者获得互斥信号量后检查emptyBuffers资源信号量,发现缓冲区满了,于是进入睡眠状态;此时消费者无法获得互斥信号量,于是无法消耗缓冲区内的资源
  • 消费者获得互斥信号量后检查fullBuffers资源信号量,发现缓冲区空了,于是进入睡眠状态;此时生产者无法获得互斥信号量,于是无法将资源放入缓冲区内

按答案中更抽象的说法就是这样:

  • 缓冲区空时,生产者等待缓冲区的互斥访问,以便放入数据;消费者占有缓冲区访问权,等待生产者放入的数据
  • 缓冲区满时,生产者占有缓冲区访问权,等待空的缓冲块;消费者等待缓冲区的互斥访问,以便取出数据

为什么互斥信号量的实现比资源信号量的实现要简单?请说明.

信号量中的整形变量的取值不同,互斥信号量的最大取值为1;而资源信号量的最大取值为资源总数。

事实上,互斥信号量和互斥锁是等价的。(如果不考虑sem值和等待进程数量关系的问题)。


管程的组成包括哪几部分?入口队列和条件变量等待队列的作用是什么?

管程是一种并发程序的编程方法,由一个与入口队列对应的锁和若干个与共享数据访问的等待队列对应的条件变量组成,从而实现在任一时刻最多只有一个线程执行管程代码。

管程的组成部分:

  • 一个锁:控制管程代码的互斥访问
  • 入口队列:每次只能有一个线程进入
  • 0或多个条件变量(及其对应的等待队列):管理共享数据的并发访问

入口的等待队列和锁保证任一时刻最多只有一个线程执行管程代码;每个条件变量等待队列表示一种等待的资源。


管程与临界区有什么异同?

  • 相同点:在任一时刻最多只有一个线程执行管程代码或临界区代码
  • 不同点:正在管程中的线程可临时放弃管程的互斥访问(进入条件变量的等待队列),等待事件出现时恢复;而临界区不支持临时退出

(所以其实在管程的概念里面我们已经不谈临界区了?)


为什么用管程实现的生产者-消费者问题中,可以在进入管程后才判断缓冲区的状态?

因为管程允许临时放弃管程的互斥访问,而信号量并不支持临时放弃互斥访问权。在具体实现上,在管程内部的条件变量上进行等待时,会将管程的锁作为wait()操作的参数传递过去,此操作会同时放弃锁(返回时又会重新获得锁),因此不会导致死锁。


请描述管程条件变量的三种释放处理方式的区别是什么?条件判断中的while和if是如何影响释放处理中的顺序的?

  • Mesa管程:占用管程的当前进程可在任何时刻释放占用资源并唤醒相应的等待进程,当前进程继续执行,被唤醒进程放回入口等待队列队首等待当前进程释放管程访问权
  • Hoare管程:占用管程的当前进程可在任何时刻释放占用资源并唤醒相应的等待进程,当前进程进入唤醒队列等待,被唤醒进程继续执行直到释放管程访问权;管程空闲时,优先查看唤醒队列中的等待进程,唤醒队列中没有等待进程时再查看入口队列
  • Hansen管程:占用管程的当前进程只在退出管程时释放占用资源并唤醒相应的等待进程,被唤醒进程继续执行直到释放管程访问权

条件判断中while和if对释放处理中的执行顺序影响:

  • 在Hansen和Mesa管程中,由于条件变量释放操作signal时并没有立即放弃管程访问权,资源的可用状态可能变化,需使用while()进行重新检查;
  • 在Hoare管程中,由于条件变量释放操作signal同时表示立即放弃管程访问权,资源的可用状态保持不变,可使用if判断,不需要再次检查。

Ref: https://piazza.com/class/i5j09fnsl7k5x0?cid=894

Ref: https://www.andrew.cmu.edu/course/15-440-kesden/applications/ln/lecture6.html

(不过在上述Piazza帖子中也有人提出了这样的问题:Hansen管程似乎是直接把访问权转移给了等待进程,这样还需要使用if来判断吗?)


哲学家就餐问题的方案2和方案3的性能有什么区别?

  • 方案2中,最多只有一个哲学家在吃饭
  • 方案3中,最多可以有两个哲学家在同时吃饭

在读者-写者问题的读者优先和写者优先在行为上有什么不同?

  • 读者优先策略:
    • 只要有读者正在读状态,后来的读者就能直接进入
    • 如果读者不断进入,则写者就处于饥饿
  • 写者优先策略
    • 只要有写者就绪,写者应尽快执行写操作(后来的读者需要阻塞)
    • 如果写者持续不断就绪,则读者就处于饥饿

在读者-写者问题的读者优先实现中优先于读者到达的写者在什么地方等待?

互斥信号WriteMutex。因为这是控制读写互斥访问的锁。

实践题

请用管程with条件变量来实现信号量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Semaphore {
Lock lock; // 管程的锁
int count; // 剩余可用资源个数
Condition isEmpty; // 表示是否有可用资源的事件的条件变量
};

Semaphore::Semaphore(int numRes) {
count = numRes;
}

Semaphore::P() {
lock.acquire();
while (count == 0)
isEmpty.wait(&lock);
count--;
lock.release();
}

Semaphore::V() {
lock.acquire();
count++;
isEmpty.signal();
lock.release();
}

考虑到可能是Mesa语义的管程,因此进行了while检查。参考了这个Piazza帖子,我认为上述实现可以满足:

  • 在任一状态,条件变量的等待队列与信号量的等待队列完全相同
  • count != 0时,其含义与信号量中的sem相同,此时条件变量的numWaiting = 0
  • count = 0时,条件变量的numWaiting等于信号量的sem的相反数(实现保证了count不会为负数)

请用信号量来实现管程with条件变量。

这个就有一定的难度了。当然,管程的核心是条件变量,其实实现条件变量就可以了。以下内容参考了Implementing Condition Variables with Semaphores这篇文章。

首先用信号量实现一个锁,这是非常容易的。

1
2
3
4
5
6
7
8
class Lock {
Semaphore sm;
public Lock() { // constructor
sm = new Semaphore(); sm.count =1; sm.limit = 1;
}
public void Acquire() { sm.P(); }
public void Release() { sm.V(); }
}

下面给出一种非常简单但是也非常错误的实现。该实现的显而易见的问题是,wait操作中对锁的释放和当前线程的睡眠不是原子的。然后好像会出现一个叫做“wake-up waiting race”的问题,不过此处好像并不会发生错误。以及,即使在没有线程正在等待时,signal操作也会使得信号量的值增加,这样,下一个等待进程就不会阻塞了,这是不正确的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class CV {
Semaphore s;
public CV() { // Constructor
s = new Semaphore();
s.count = 0;
s.limit = 1;
}
public void Wait(Lock m) { // Pre-condition: this thread holds “m”
m.Release();
s.P();
m.Acquire();
}
public void Signal() {
s.V();
}
}

于是我们用信号量x作为互斥锁来保护wait操作,同时统计等待进程的个数。但这个实现也有两个问题:

  • 由于s信号量的资源个数为1,因此最多只有一个调用wait的进程能够从s.P中返回,其余的都阻塞在s.P上;解决方法是把s的资源个数调到无限大
  • 没有保证先进先出的语义
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
31
32
class CV {
Semaphore s, x;
int waiters = 0;
public CV() { // Constructor
s = new Semaphore(); s.count = 0; s.limit = 1;
x = new Semaphore(); x.count = 1; x.limit = 1;
}
public void Wait(Lock m) { // Pre-condition: this thread holds “m”
x.P();
waiters++;
x.V();
m.Release();
s.P();
m.Acquire();
}
public void Signal() {
x.P();
if (waiters > 0) {
waiters--;
s.V();
}
x.V();
}
public void Broadcast() {
x.P();
while (waiters > 0) {
waiters--;
s.V();
}
x.V();
}
}

下一种实现中,加入了信号量h,它会使发出信号的线程在等待线程离开等待队列之前也阻塞。这个实现是正确的,但是似乎太麻烦了。论文最后表示,他们决定还是在OS中用硬件指令来实现条件变量。

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
31
32
33
34
35
36
37
38
39
class CV {
Semaphore s, x;
int waiters = 0;
Semaphore h;
public CV() { // Constructor
this.m = m;
s = new Semaphore(); s.count = 0; s.limit = 999999;
x = new Semaphore(); x.count = 1; x.limit = 1;
h = new Semaphore(); h.count = 0; h.limit = 999999;
}
public void Wait(Lock m) { // Pre-condition: this thread holds “m”
x.P();
waiters++;
x.V();
m.Release();
s.P();
h.V();
m.Acquire();
}
public void Signal() {
x.P();
if (waiters > 0) {
waiters--;
s.V();
h.P();
}
x.V();
}
public void Broadcast() {
x.P();
for (int i = 0; i < waiters; i++)
s.V();
while (waiters > 0) {
waiters--;
h.P();
}
x.V();
}
}

请评价如下的实现(用信号量来实现管程with条件变量)是否合理?简要说明理由。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
Implementing a Monitor

CONTROL VARIABLES:

mutex: semaphore, initial value 1 (FREE)
next: record, with 2 fields:
next.sem: semaphore, initial value 0
next.count: counter, initial value 0

FOR EACH CONDITION x:

x: record, with 2 fields:
x.sem: semaphore, initial value 0
x.count: counter, initial value 0
ENTRY PROTOCOL (at the beginning of each monitor function):

/* wait for exclusive access to the monitor */
P(mutex);
EXIT PROTOCOL (at the end of each monitor function):

/* if there are processes in the "next" queue, release one */
if (next.count > 0) V(next.sem);

/* otherwise, release the monitor */
else V(mutex);
WAIT ON CONDITION x (x.wait):

/* first perform the exit protocol */
if (next.count > 0) V(next.sem);
else V(mutex);

/* now wait on the condition queue */
x.count++;
P(x.sem);
x.count--;
SIGNAL CONDITION x (x.signal):

/* do nothing unless a process is waiting */
if (x.count > 0) {

/* release the next waiting process */
V(x.sem);

/* wait on the "next" queue */
next.count++;
P(next.sem);
next.count--;
}

每人使用C++或python语言用信号量和条件变量两种手段分别实现40个同步互斥问题中的一题。请先理解python threading 机制的介绍和实例

参考:2015年操作系统课的信号量问题回答

建议参考梁锡豪同学的输出信息显示方式,这种方式的可读性很好。

建议重视测试用例的设计,以检查自己的实现是否有错。


设计某个方法,能够动态检查出对于两个或多个进程的同步互斥问题执行中,没有互斥问题,能够同步等,以说明实现的正确性。


管程和信号量在解决同步互斥问题上是否等价?请证明/说明你的结论.

Piazza上有两个非常优秀的讨论:

简单来说,就是:信号量可以实现管程,管程可以实现信号量,所以在这个层面,二者等价。

OS

课程内容概述

本讲介绍了ucore中的文件系统。

TODO

练习

来自lec22 lab8 文件系统 在线练习lab8 文件系统 (lec 22) spoc 思考题

选择填空题

ucore实现的文件系统抽象包括()

  • 文件
  • 目录项
  • 索引节点
  • 安装点

我猜这里主要说的是VFS文件系统中的内容。

  • struct file:应用程序能够看到的各种文件信息
  • struct inode:映射到特定文件系统的inode
  • struct fs:保存了具体文件系统的结构、类型和信息

然后安装点是个啥我也不知道。

安装点是一个目录或文件,可在该处访问新文件系统、目录或文件。要安装文件系统或目录,安装点必须为一个目录;要安装文件,那么安装点必须为文件。(https://www.ibm.com/support/knowledgecenter/zh/ssw_aix_72/com.ibm.aix.osdevice/mountpoint.htm


ucore实现的simple FS(简称SFS)采用的文件分配机制是()

  • 连续分配
  • 链式分配
  • 索引分配
  • 位图分配

SFS使用的是一级索引。

索引分配的定义:为每个文件创建一个索引数据块,指向文件数据块的指针列表;文件头包含了索引数据块指针。


关于ucore实现的SFS阐述正确的是()

  • SFS的超级块保存在硬盘上,在加载simple FS时会读入内存中
  • SFS的free map结构保存在硬盘上,表示硬盘可用的数据块(扇区)
  • SFS的root-dir inode结构保存在硬盘上,表示SFS的根目录的元数据信息
  • 硬盘上的SFS ,除保存上述三种结构外,剩下的都用于保存文件的数据内容

除了前三种结构,剩下的用于保存文件的inode, dir/file的data。


关于ucore实现的Virtual FS(简称VFS)阐述正确的是()

  • 已支持磁盘文件系统
  • 已支持设备文件系统
  • 已支持网络文件系统
  • 已支持系统状态文件系统

后两种可实现,但现在还没实现

哈哈哈哈哈哈……


关于ucore文件系统支持的I/O设备包括()

  • 串口设备
  • 并口设备
  • CGA设备
  • 键盘设备

总之这些都支持。不过好像从Lab1就有了。

简答题

与文件系统相关的系统调用接口、虚拟文件系统VFS、简单文件系统SFS和设备I/O等四个部分各实现什么功能?

  • 系统调用接口:向应用进程提供文件访问的系统调用
  • 虚拟文件系统VFS:屏蔽具体文件系统差异,对上提供一个统一的文件系统访问接口
  • 简单文件系统SFS:解析和读写磁盘数据块中具体的SFS文件系统存储结构
  • 设备I/O:完成实际磁盘设备上数据块的访问

文件系统中的文件、目录、索引节点(inode)和安装点(挂载点)这几种数据结构分别支持些什么操作?

  • 文件:open/close, read/write
  • 目录:open/close, read
  • 索引节点:lookup, read/write
  • 挂载点:mount/unmount

请简要阐述ucore文件系统架构的四个组成部分。

  • 系统调用接口:用户应用使用封装后的libc库函数,文件访问的libc库函数利用文件访问系统调用来实现
  • VFS:内核的系统调用(文件、目录接口)会转换成对VFS抽象的文件访问接口(索引节点、文件卷、设备等接口)的调用,VFS再把抽象的VFS接口转换成具体的文件系统SFS的访问接口
  • SFS:对具体文件系统存储结构进行解析,把SFS对接口(索引节点、文件卷、设备等接口)的访问请求转换成设备数据块的访问
  • I/O接口:不同具体设备上的数据块访问控制

请简要说明进程proc_struct、文件file、inode之间的关系。

  • 进程控制块数据结构proc_struct中,struct files_struct *filesp指向进程的打开文件表
  • 进程打开文件表中struct file *file指向系统打开文件中的相应文件状态数据
  • VFS中的系统打开文件表中struct inode *inode维护打开文件的状态信息,并最终对应到磁盘上的存储数据块

ucore中的进程打开文件表和系统打开文件表对应到具体的哪个数据结构上?

  • 进程打开文件表:proc_struct中的struct files_struct *filesp
  • 系统打开文件表:不知道

SFS在硬盘上的四大部分主要是什么,有何作用?

  • superblock:数据块大小、文件卷名字等文件卷信息
  • root-dir inode:根目录的inode信息(存储位置等)
  • freemap:数据块占用状态信息
  • data block:inode/文件数据/目录数据

硬盘上的SFS是如何加载到ucore中并初始化的?

ucore docs Lab8:

sfs_fs.c文件中的sfs_do_mount函数中,完成了加载位于硬盘上的SFS文件系统的超级块superblock和freemap的工作。这样,在内存中就有了SFS文件系统的全局信息。


硬盘上的inode和内存中的inode的关系和区别是什么?

内存中的inode数据结构sfs_inode中有一个字段sfs_disk_inode,它对应磁盘上的inode。

ucore docs Lab8:

SFS中的磁盘索引节点代表了一个实际位于磁盘上的文件。
……
可以看到SFS中的内存inode包含了SFS的硬盘inode信息,而且还增加了其他一些信息,这属于是便于进行是判断否改写、互斥操作、回收和快速地定位等作用。需要注意,一个内存inode是在打开一个文件后才创建的,如果关机则相关信息都会消失。而硬盘inode的内容是保存在硬盘中的,只是在进程需要时才被读入到内存中,用于访问文件或目录的具体内容数据


描述file, dir, inode在内存和磁盘上的格式和相关操作。

每一种类型的数据块都在SFS层中有对应的操作函数指针和数据结构定义。

事实上,file、dir和inode在内存和磁盘上都以inode形式存储:

  • 内存:struct sfs_disk_inode
  • 磁盘:inode

通过上表可以看出,如果inode表示的是文件,则成员变量direct[]直接指向了保存文件内容数据的数据块索引值。indirect间接指向了保存文件内容数据的数据块,indirect指向的是间接数据块(indirect block),此数据块实际存放的全部是数据块索引,这些数据块索引指向的数据块才被用来存放文件内容数据。
对于普通文件,索引值指向的block中保存的是文件中的数据。而对于目录,索引值指向的数据保存的是目录下所有的文件名以及对应的索引节点所在的索引块(磁盘块)所形成的数组。


file数据结构的主要内容是什么?与进程的关系是什么?

struct file数据结构定义在lab8/kern/fs/file.h中:

1
2
3
4
5
6
7
8
9
10
11
struct file {
enum {
FD_NONE, FD_INIT, FD_OPENED, FD_CLOSED,
} status;
bool readable;
bool writable;
int fd;
off_t pos;
struct inode *node;
int open_count;
};

struct file数据结构的内容包括:

  • status:文件状态
  • bool readable & writable:文件操作类型
  • int fd:文件描述符
  • off_t pos:文件指针
  • struct inode *node:对应系统打开文件表项指针
  • int open_count:文件打开计数

struct file就是进程打开文件表对应的数据结构。


inode数据结构的主要内容是什么?与file的数据结构的关系是什么?

struct inode数据结构定义在lab8/kern/fs/vfs/inode.h中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct inode {
union {
struct device __device_info;
struct sfs_inode __sfs_inode_info;
} in_info;
enum {
inode_type_device_info = 0x1234,
inode_type_sfs_inode_info,
} in_type;
int ref_count;
int open_count;
struct fs *in_fs;
const struct inode_ops *in_ops;
};

struct inode数据结构的内容:

  • in_info & in_type:文件类型
  • ref_count & open_count:引用计数
  • struct fs *in_fs:对下具体文件操作函数指针
  • const struct inode_ops *in_ops:对上inode操作函数指针

struct inode就是系统打开文件表对应的数据结构。


inode_ops包含哪些与文件相关的操作?

struct inode_ops数据结构定义在lab8/kern/fs/vfs/inode.h中,它是上层使用的inode操作函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct inode_ops {
unsigned long vop_magic;
int (*vop_open)(struct inode *node, uint32_t open_flags);
int (*vop_close)(struct inode *node);
int (*vop_read)(struct inode *node, struct iobuf *iob);
int (*vop_write)(struct inode *node, struct iobuf *iob);
int (*vop_fstat)(struct inode *node, struct stat *stat);
int (*vop_fsync)(struct inode *node);
int (*vop_namefile)(struct inode *node, struct iobuf *iob);
int (*vop_getdirentry)(struct inode *node, struct iobuf *iob);
int (*vop_reclaim)(struct inode *node);
int (*vop_gettype)(struct inode *node, uint32_t *type_store);
int (*vop_tryseek)(struct inode *node, off_t pos);
int (*vop_truncate)(struct inode *node, off_t len);
int (*vop_create)(struct inode *node, const char *name, bool excl, struct inode **node_store);
int (*vop_lookup)(struct inode *node, char *path, struct inode **node_store);
int (*vop_ioctl)(struct inode *node, int op, void *data);
};

文件中有每个操作的详细注释

  • open:打开文件
  • close:关闭文件
  • read:读文件
  • write:写文件
  • fstat:读文件信息
  • fsync:将脏缓存写回持久化存储介质
  • namefile:计算文件相对于文件系统根目录的路径
  • getdirentry:从目录中读一个文件名
  • reclaim:回收inode
  • gettype:文件种类
  • tryseek:检查移动文件指针是否合法
  • truncate:重设文件大小,丢弃多余的数据
  • create:在目录中新建文件
  • lookup:在给定目录中按文件名查找文件
  • ioctl:管理I/O通道(??)

VFS是如何把键盘、显示输出和磁盘文件统一到一个系统调用访问框架下的?

  • VFS把键盘、显示和磁盘文件都视为文件,VFS对上提供的访问接口都是文件访问接口
  • VFS通过区别文件类型、文件操作类型、设备类型等来区别同类操作在不同设备的不同实现

device数据结构的主要内容是什么?与fs的关系是什么?与inode的关系是什么?

这里的device指的应该是lab8/kern/fs/devs/dev.h中定义的struct device

1
2
3
4
5
6
7
8
9
10
11
12
/*
* Filesystem-namespace-accessible device.
* d_io is for both reads and writes; the iobuf will indicates the direction.
*/
struct device {
size_t d_blocks;
size_t d_blocksize;
int (*d_open)(struct device *dev, uint32_t open_flags);
int (*d_close)(struct device *dev);
int (*d_io)(struct device *dev, struct iobuf *iob, bool write);
int (*d_ioctl)(struct device *dev, int op, void *data);
};

struct device数据结构的内容:

  • size_t d_blocks:数据块个数
  • size_t d_blocksize:数据块大小
  • 设备操作函数指针(d_open, d_close, d_io, d_ioctl

fs和inode通过device数据结构中的设备操作函数指针实现对设备数据块的访问。


比较ucore中I/O接口、SFS文件系统接口和文件系统的系统调用接口的操作函数有什么异同?

  • 文件系统的系统调用接口(lab8/kern/syscall/syscall.c):sys_open, sys_close, sys_read, sys_write, sys_seek, sys_fstat, sys_fsync, sys_chdir, sys_getcwd, sys_mkdir, sys_link, sys_rename, sys_unlink, sys_getdirentry, sys_dup, sys_pipe, sys_mkfifo, sys_mount, sys_umount, sys_ioctl
  • VFS文件系统接口(lab8/kern/vfs/vfs.h):vfs_open, vfs_close, vfs_link, vfs_symlink, vfs_readlink, vfs_mkdir, vfs_unlink, vfs_rename, vfs_chdir, vfs_getcwd
  • SFS文件系统接口(lab8/kern/sfs/sfs.h):sfs_rblock, sfs_wblock, sfs_rbuf, sfs_wbuf, sfs_sync_super, sfs_sync_freemap, sfs_clear_block, sfs_load_inode
  • I/O接口(lab8/kern/devs/dev.h):d_open, d_close, d_io, d_ioctl

实践题

理解文件访问的执行过程,即在ucore运行过程中通过cprintf函数来完整地展现出来读一个文件在ucore中的整个执行过程,(越全面细致越好) 完成代码填写,并形成spoc练习报告,需写练习报告和简单编码,完成后放到git server 对应的git repo中。

啊,这个完全没有时间去写了……


在下面的实验代码的基础上,实现基于文件系统的pipe IPC机制。练习用的lab8 spoc exercise project source code

呃,这是lab8的附加题……

OS