本章作业见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:“不闻不若闻之,闻之不若见之,见之不若知之,知之不若行之;学至于行之而止矣。”(荀子《儒效篇》)

本章主要介绍了如何以锁为基础,将常见的数据结构改造为线程安全的。

  • 一种通用的解决方法
  • 性能:缩放(scaling)问题
  • 并发计数器
  • 并发链表
  • 并发队列
  • 并发哈希表

最后强调了几点经验教训:

  • 在控制流变化的时候不要忘记释放锁(见并发链表的错误实现)
  • 提高并发性不等于提升性能(见交替上锁的链表)
  • 在编写多线程应用时,正确性比效率更重要,需要避免过早优化(premature optimization)

一种通用的解决方法

很容易想到,使常见的数据结构线程安全的最简单的方法,就是在对该数据结构执行任何操作之前都上锁,执行完之后再释放锁。

以计数器为例。一个普通的计数器的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct __counter_t {
int value;
} counter_t;

void init(counter_t *c) {
c->value = 0;
}

void increment(counter_t *c) {
c->value++;
}

void decrement(counter_t *c) {
c->value--;
}

int get(counter_t *c) {
return c->value;
}

直接在计数器上加入一个操作锁,此时程序如下:

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
typedef struct __counter_t {
int value;
pthread_mutex_t lock;
} counter_t;

void init(counter_t *c) {
c->value = 0;
Pthread_mutex_init(&c->lock, NULL);
}

void increment(counter_t *c) {
Pthread_mutex_lock(&c->lock);
c->value++;
Pthread_mutex_unlock(&c->lock);
}

void decrement(counter_t *c) {
Pthread_mutex_lock(&c->lock);
c->value--;
Pthread_mutex_unlock(&c->lock);
}

int get(counter_t *c) {
Pthread_mutex_lock(&c->lock);
int rc = c->value;
Pthread_mutex_unlock(&c->lock);
return rc;
}

这样的实现方法显然是简单且正确的。

性能:缩放(scaling)问题

上述简单粗暴的实现显然会降低并发性,因为有些操作完全是可以并行执行的(如多个get操作)。对于这一问题,给出一形式化的定义如下:

完全缩放(perfect scaling):对于一个线程安全的数据结构,如果需要访问它的线程数量小于系统中处理器的数量,且满足多个线程并发访问该数据结构的运行时间不多于只有单个线程访问该数据结构时的运行时间,则称该数据结构是完全缩放的。

实验结果表明,上述实现方法完全做不到完全缩放,多线程并发访问的时间随线程数量而线性增加(在线程数<CPU数的前提下)。这是符合逻辑的。

并发计数器

我个人认为精确的计数器实现是很难(或者说不可能?)做到完全缩放的,因为这些操作本身已经足够简单,很难再有并行优化的余地。书中给出了一种不精确的计数器的实现,称为“sloppy counter”。

这一计数器的基本思想如下:

  • 每个CPU拥有一个本地计数器,除此之外,有一个全局计数器;每个计数器各有一个锁
  • 当某个CPU上运行的线程需要执行increment操作时,获得本地计数器的锁,执行操作,并释放锁
  • 当某个本地计数器的值达到阈值S时,则获得该计数器和全局计数器的锁,全局计数器+=本地计数器,本地计数器清零;释放锁
  • 全局计数器中存放的是计数器的一个估计值,读取时需要先获得全局计数器的锁。可以通过获得全部锁来获得计数器当前的真实值,但这一操作显然是非缩放的

下面是一个S=5,4个线程的执行示例:

可以看出,S的值越小,该实现方法越类似于直接加锁的实现(当S=1时基本退化为直接加锁的实现);S的值越大,该方法的缩放性越强,性能越好,但全局计数器的值就会偏离真实值更远。

4个线程,4个CPU,分别increment一百万次,执行时间随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
33
34
35
36
37
38
39
40
41
42
43
44
typedef struct __counter_t {
int global; // global count
pthread_mutex_t glock; // global lock
int local[NUMCPUS]; // local count (per cpu)
pthread_mutex_t llock[NUMCPUS]; // ... and locks
int threshold; // update frequency
} counter_t;

// init: record threshold, init locks, init values
// of all local counts and global count
void init(counter_t *c, int threshold) {
c->threshold = threshold;
c->global = 0;
pthread_mutex_init(&c->glock, NULL);
int i;
for (i = 0; i < NUMCPUS; i++) {
c->local[i] = 0;
pthread_mutex_init(&c->llock[i], NULL);
}
}

// update: usually, just grab local lock and update local amount
// once local count has risen by ’threshold’, grab global
// lock and transfer local values to it
void update(counter_t *c, int threadID, int amt) {
int cpu = threadID % NUMCPUS;
pthread_mutex_lock(&c->llock[cpu]);
c->local[cpu] += amt; // assumes amt > 0
if (c->local[cpu] >= c->threshold) { // transfer to global
pthread_mutex_lock(&c->glock);
c->global += c->local[cpu];
pthread_mutex_unlock(&c->glock);
c->local[cpu] = 0;
}
pthread_mutex_unlock(&c->llock[cpu]);
}

// get: just return global amount (which may not be perfect)
int get(counter_t *c) {
pthread_mutex_lock(&c->glock);
int val = c->global;
pthread_mutex_unlock(&c->glock);
return val; // only approximate!
}

并发链表

书中给出了一种错误的实现,在此不再摘录了。该错误的问题在于,如果获得锁之后未能成功进行相应操作,则直接返回,忘记释放锁了。我们可以从中得出如下教训:

  • 不要扩大锁覆盖的范围,只覆盖关键区就可以了
  • 安排好代码的执行顺序,对于有多个出口点的代码,最好将出口点汇总在一起,这样不容易忘记释放锁;在具体实现的时候,可以记录返回值,并配合goto语句

下面是正确的实现:

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
void List_Init(list_t *L) {
L->head = NULL;
pthread_mutex_init(&L->lock, NULL);
}

void List_Insert(list_t *L, int key) {
// synchronization not needed
node_t *new = malloc(sizeof(node_t));
if (new == NULL) {
// 这是原先出错的位置,现在已移出上锁区域
perror("malloc");
return;
}
new->key = key;

// just lock critical section
pthread_mutex_lock(&L->lock);
new->next = L->head;
L->head = new;
pthread_mutex_unlock(&L->lock);
}

int List_Lookup(list_t *L, int key) {
int rv = -1;
pthread_mutex_lock(&L->lock);
node_t *curr = L->head;
while (curr) {
if (curr->key == key) {
rv = 0;
break;
}
curr = curr->next;
}
// 出口点集合
pthread_mutex_unlock(&L->lock);
return rv; // now both success and failure
}

链表的缩放性

显然上述实现并不具有完全缩放性。另一种想法是采用交替上锁(hand-over-hand locking)技术:为每个结点都初始化一个锁,需要访问结点时,则获取该结点对应的锁。这个想法虽然听起来很好,极大地增加了并发性,但在实际操作中效率很低,因为请求/释放锁的操作耗时太多。如果采取一种混合策略(如每$\sqrt{n}$个结点上一个锁),就可以在并发性和效率之间取得一种平衡。

并发队列

书中给出了一种比较巧妙的实现。一般来说,入队操作只会访问队头,出队操作只会访问队尾,因此可以对这两种操作分别建立一个锁,一个队头锁,一个队尾锁;在进行操作时分别上锁。

代码中的细节是,为了将两种操作分离开,在队列的头部增加了一个伪结点;所以出队的时候返回的是队头的下一个结点的值;然后删除队头,它原来的下一个结点成为队头,也成为伪结点。

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
typedef struct __node_t {
int value;
struct __node_t *next;
} node_t;

typedef struct __queue_t {
node_t *head;
node_t *tail;
pthread_mutex_t headLock;
pthread_mutex_t tailLock;
} queue_t;

void Queue_Init(queue_t *q) {
node_t *tmp = malloc(sizeof(node_t));
tmp->next = NULL;
q->head = q->tail = tmp;
pthread_mutex_init(&q->headLock, NULL);
pthread_mutex_init(&q->tailLock, NULL);
}

void Queue_Enqueue(queue_t *q, int value) {
node_t *tmp = malloc(sizeof(node_t));
assert(tmp != NULL);
tmp->value = value;
tmp->next = NULL;

pthread_mutex_lock(&q->tailLock);
q->tail->next = tmp;
q->tail = tmp;
pthread_mutex_unlock(&q->tailLock);
}

int Queue_Dequeue(queue_t *q, int *value) {
pthread_mutex_lock(&q->headLock);
node_t *tmp = q->head;
node_t *newHead = tmp->next;
if (newHead == NULL) {
pthread_mutex_unlock(&q->headLock);
return -1; // queue was empty
}
*value = newHead->value;
q->head = newHead;
pthread_mutex_unlock(&q->headLock);
free(tmp);
return 0;
}

并发哈希表

并发哈希表的实现借用了上述并发链表的实现,这一实现是比较简化的。由于不同的槽对应的链表的操作是可以并行的(相当于每个槽对应一个锁),因此这一实现的并发性是比较高的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define BUCKETS (101)

typedef struct __hash_t {
list_t lists[BUCKETS];
} hash_t;

void Hash_Init(hash_t *H) {
int i;
for (i = 0; i < BUCKETS; i++) {
List_Init(&H->lists[i]);
}
}

int Hash_Insert(hash_t *H, int key) {
int bucket = key % BUCKETS;
return List_Insert(&H->lists[bucket], key);
}

int Hash_Lookup(hash_t *H, int key) {
int bucket = key % BUCKETS;
return List_Lookup(&H->lists[bucket], key);
}

作业

没写。

本章主要介绍了锁的基础知识,以及各种锁的实现方法和评价标准:

  • 硬件支持
    • 关中断
    • TS指令实现自旋锁
    • CS指令实现自旋锁
    • LL/SC指令实现自旋锁
    • FA指令实现无饥饿的自旋锁
  • 硬件和OS支持
    • 从自旋锁到yield
    • 使用队列和睡眠
    • Linux中的实际例子
    • 两阶段锁

锁的基本定义和用法

锁是一个变量。在任意时刻,该变量中都存储着锁的状态:

  • 可获得(或者说释放,开锁的,说明没有线程持有该锁)
  • 不可获得(未被释放,上锁的,说明有一个线程持有该锁,很可能处于关键区内)

锁的使用方法:

1
2
3
4
5
lock_t mutex; // some globally-allocated lock 'mutex'
...
lock(&mutex);
balance = balance + 1; // 关键区
unlock(&mutex);

lock()的语义:

  • 尝试获得锁
  • 如果该锁未被获得,则获得该锁,进入关键区,该线程成为锁的拥有者
  • 如果该锁已被获得,则在锁被释放之前始终阻塞,防止多个线程同时进入关键区
    unlock()的语义:
  • 释放线程当前持有的锁
  • 如果还有其他线程在等待锁,则通知其中一个进程开始运行,获得锁,并进入关键区

锁能够帮助程序员更多地获得对线程的控制权。

锁的评价标准

  1. 基本要求:提供互斥访问功能
  2. 公平性:是否会出现线程饥饿的状况?
  3. 性能:不同场景下的时间开销
  4. 单线程获取并释放锁
  5. 多线程请求同一个锁
  6. 多CPU上的多线程请求同一个锁

锁的实现方法

本章中给出了一种单纯用现有非特权指令(加载和存储)实现锁的方法,但是失败了。当然,其实这样是可以成功的(Dekker和Peterson算法),也做过一些研究,但是这些算法对硬件也有一些假设,而且人们已经发现,在硬件中提供一些支持会方便很多。所以就不赘述了。

用硬件原语实现锁

关中断

代码实现如下:

1
2
3
4
5
6
void lock() {
DisableInterrupts();
}
void unlock() {
EnableInterrupts();
}

优点:简单

缺点:

  • 需要线程执行特权指令,可能被滥用,OS无法得到控制权
  • 不适用于多处理器系统
  • 关中断太久可能导致重要的中断请求被丢失
  • 效率低,因为现代CPU开关中断的速度比较慢

目前这一方法主要用于OS本身的原子性操作,因为这样就不存在滥用问题。

使用TS(Test-And-Set)指令实现自旋锁

TS指令原子地完成以下操作:

  • 读出某个地址处的值
  • 将新的值写入该地址
  • 返回旧值

用代码表示如下:

1
2
3
4
5
int TestAndSet(int *old_ptr, int new) {
int old = *old_ptr; // fetch old value at old_ptr
*old_ptr = new; // store 'new' into old_ptr
return old; // return the old value
}

可以利用TS指令实现自旋锁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct __lock_t {
int flag;
} lock_t;

void init(lock_t *lock) {
// 0 indicates that lock is available, 1 that it is held
lock->flag = 0;
}

void lock(lock_t *lock) {
while (TestAndSet(&lock->flag, 1) == 1)
; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
lock->flag = 0;
}

工作原理是:

  • flag变量表示锁是否被持有,0表示空闲
  • lock()函数中,不断使用TS指令测试锁是否空闲,空闲则获得锁并将flag置为1;不空闲则自旋等待
  • unlock()函数中,只需简单地将flag置为0

对自旋锁的评价

  1. 正确性:显然是正确的
  2. 公平性:无法保证,可能会导致饥饿
  3. 性能:
  4. 单CPU系统:性能很差
  5. 多CPU系统:还不错(如果线程的数量大致与CPU相等)

使用CS(Compare-And-Swap)指令实现自旋锁

CS指令原子地完成以下操作:

  • 读出某个地址处的值
  • 判断它是否与期望的值相等,如果相等,则更新该地址处的值为某给定的值
  • 返回该地址处原有的值

用代码表示如下:

1
2
3
4
5
6
int CompareAndSwap(int *ptr, int expected, int new) {
int actual = *ptr;
if (actual == expected)
*ptr = new;
return actual;
}

与TS指令类似,可以利用CS指令实现自旋锁(其他函数与TS指令的实现相同):

1
2
3
4
void lock(lock_t *lock) {
while (CompareAndSwap(&lock->flag, 0, 1) == 1)
; // spin
}

工作原理也类似。

用LL(Load-Linked)和SC(Store-Conditional)指令实现自旋锁

这两个指令是MIPS架构下提供的。LL指令类似于普通的加载指令,把某个值从内存中加载到寄存器中;但它会标记这个地址,SC指令更新该地址处的值时,仅在上次LL过后该值还没有被修改过时才会成功。

用代码描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
int LoadLinked(int *ptr) {
return *ptr;
}

int StoreConditional(int *ptr, int value) {
if (no one has updated *ptr since the LoadLinked to this address) {
*ptr = value;
return 1; // success!
} else {
return 0; // failed to update
}
}

锁的实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
void lock(lock_t *lock) {
while (1) {
while (LoadLinked(&lock->flag) == 1)
; // spin until it's zero
if (StoreConditional(&lock->flag, 1) == 1)
return; // if set-it-to-1 was a success: all done
// otherwise: try it all over again
}
}

void unlock(lock_t *lock) {
lock->flag = 0;
}

如果两个线程同时在请求这个锁,则先执行SC指令的线程可以获得锁,另一个线程执行SC指令时就会返回0,需要重新进入请求状态。

用FA(Fetch-And-Add)指令实现标签锁(ticket lock)

FA指令原子地完成以下任务:

  • 读出某个地址处的值
  • 将这个值+1
  • 重新写回该地址处
  • 返回原来的值

用代码描述如下:

1
2
3
4
5
int FetchAndAdd(int *ptr) {
int old = *ptr;
*ptr = old + 1;
return old;
}

用该指令可以实现一个思路稍有不同的锁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct __lock_t {
int ticket;
int turn;
} lock_t;

void lock_init(lock_t *lock) {
lock->ticket = 0;
lock->turn = 0;
}

void lock(lock_t *lock) {
int myturn = FetchAndAdd(&lock->ticket);
while (lock->turn != myturn)
; // spin
}

void unlock(lock_t *lock) {
lock->turn = lock->turn + 1;
}

其中,ticket变量表示曾经请求过锁的线程的个数,turn变量表示当前(应该)是第几个等待线程持有锁。lock()函数中,通过FA指令为本线程获得“排位”(myturn),并等待前面的线程执行完毕。unlock()函数中,只需简单地将turn变量+1(轮到下一个线程了)。

这个实现方法的优点是,不存在饥饿问题,请求同一个锁的线程按请求顺序获得锁。(但是这样会不会有死锁问题??)

用硬件原语和OS的支持实现锁

直接把自旋改为yield

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
void init() {
flag = 0;
}

void lock() {
while (TestAndSet(&flag, 1) == 1)
yield(); // give up the CPU
}

void unlock() {
flag = 0;
}

得不到锁的线程不再自旋,而是主动放弃控制权。虽然减少了自旋浪费的时间片,不过仍然耗费了一些切换上下文的时间。

利用队列和睡眠实现锁

现在改为由OS控制当前的锁被释放之后,哪一个线程能够获得锁。为此引入睡眠机制:

  • park()系统调用:将调用线程睡眠
  • unpark(ThreadID)系统调用:唤醒某个进程

下面是一个使用队列、TS指令、yield、自旋和睡眠机制的代码实现:

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
typedef struct __lock_t {
int flag;
int guard;
queue_t *q;
} lock_t;

void lock_init(lock_t *m) {
m->flag = 0;
m->guard = 0;
queue_init(m->q);
}

void lock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1)
; //acquire guard lock by spinning
if (m->flag == 0) {
m->flag = 1; // lock is acquired
m->guard = 0;
} else {
queue_add(m->q, gettid());
setpark(); // avoid wakeup/waiting race
m->guard = 0;
park();
}
}

void unlock(lock_t *m) {
while (TestAndSet(&m->guard, 1) == 1)
; //acquire guard lock by spinning
if (queue_empty(m->q))
m->flag = 0; // let go of lock; no one wants it
else
unpark(queue_remove(m->q)); // hold lock (for next thread!)
m->guard = 0;
}

该锁的内部嵌套了一个用TS指令实现的自旋锁,对应的变量是guard,保护的关键区是对锁的内部状态的修改和更新过程。

  • lock()函数:
    • 首先尝试进入关键区
    • 如果能获得锁,则离开关键区
    • 如果不能获得锁,则把自己加入队列中,离开关键区,然后放弃CPU(注意,如果先放弃CPU,则guard永远不会变成0,别的进程就无法获得和释放锁了)
  • unlock()函数:
    • 首先尝试进入关键区
    • 如果等待队列为空,则直接放弃锁,并离开关键区
    • 否则从队列中唤醒一个线程(注意,此时flag并不会被置为0,因为被唤醒的线程此时回到了park()执行完毕的地方,它已经离开了关键区,因此也不应该尝试把flag设为1;因此,我们直接把锁交给下一个线程,重甲不进行释放)

另一个可能存在的问题是,如果没有setpark()一句,且请求锁的线程在park()之前被打断,那么如果此时锁被释放了,重新被唤醒的请求线程会继续执行park(),并永远沉睡下去。setpark()可以解决这个问题:在调用它之后,如果线程在调用park()之前被打断,且其他的线程对它调用了unpark(),那么该线程随后对park()的调用会立即返回。

一个实际的锁的实现

这个实现利用了Linux中的两个函数:

  • futex_wait(address, expected):如果address处的值与expected相等,则睡眠,否则返回
  • futex_wake(address):唤醒一个在该地址的队列中等待的线程

这个实现中,一个整数(mutex)用于跟踪锁是否被持有(最高位)和等待该锁的线程数(其他所有位)。所以,如果mutex为负数,则锁被持有。

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
void mutex_lock (int *mutex) {
int v;
/* Bit 31 was clear, we got the mutex (this is the fastpath) */
if (atomic_bit_test_set (mutex, 31) == 0)
return;
atomic_increment (mutex);
while (1) {
if (atomic_bit_test_set (mutex, 31) == 0) {
atomic_decrement (mutex);
return;
}
/* We have to wait now. First make sure the futex value
we are monitoring is truly negative (i.e. locked). */
v = *mutex;
if (v >= 0)
continue;
futex_wait (mutex, v);
}
}

void mutex_unlock (int *mutex) {
/* Adding 0x80000000 to the counter results in 0 if and only if there are not other interested threads */
if (atomic_add_zero (mutex, 0x80000000))
return;

/* There are other threads waiting for this mutex,
wake one of them up. */
futex_wake (mutex);
}
  • mutex_lock函数:
    • 如果该锁空闲,则返回
    • 否则等待线程数+1,并开始循环
    • 在每次循环中,如果发现该锁空闲,则获得该锁(使用的是TS指令),等待线程数-1,并返回
    • 如果发现该锁不空闲,在等待之前重新进行一次检查,如果发现锁空闲则继续循环;否则开始睡眠
  • mutex_unlock函数:
    • 将最高位置0的同时检查是否有其他线程在等待,如果没有,则直接返回
    • 如果有,则唤醒一个等待中的线程

其中,在尝试睡眠的过程中,futex_wait函数的特性保证了“wakeup/waiting race”不会发生:首先读出mutex处的值,确保此时锁不空闲;即使此时被打断,mutex处的值被修改,futex_wait也会因为两个值不相等而返回,不会永远进入睡眠状态。

两阶段锁

这个锁的原理是混合了自旋锁和队列睡眠机制。好像没有什么好说的。

作业

没有做。

本章主要介绍了POSIX标准下的线程API,包括:

  • 创建线程
  • 等待线程结束
  • 创建和使用互斥锁
  • 创建和使用条件变量

创建线程

1
2
3
4
5
int
pthread_create( pthread_t * thread,
const pthread_attr_t * attr,
void * (*start_routine)(void*),
void * arg);

4个参数的含义如下:

  • thread:指向struct pthread_t类型的变量的指针,我们需要这一变量用来控制线程,因此需要把它的指针传递过去进行初始化
  • attr:指定线程的属性,如栈的大小和线程的调度优先级;属性是通过调用pthread attr_init()进行初始化的
  • start_routine:指定线程运行的函数,它只有一个void*类型的参数,返回值也是void*类型
  • arg:在进程执行的时候传递给函数的参数

例子:

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 <pthread.h>

typedef struct __myarg_t {
int a;
int b;
} myarg_t;

void *mythread(void *arg) {
myarg_t *m = (myarg_t *) arg;
printf("%d %d\n", m->a, m->b);
return NULL;
}

int
main(int argc, char *argv[]) {
pthread_t p;
int rc;

myarg_t args;
args.a = 10;
args.b = 20;
rc = pthread_create(&p, NULL, mythread, &args);
...
}

等待线程结束

1
int pthread_join(pthread_t thread, void **value_ptr);

参数说明:

  • thread:等待哪一个线程结束;这个变量是通过调用pthread_create()来初始化的
  • value_ptr:指向将会得到的返回值的指针

使用示例

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
#include <stdio.h>
#include <pthread.h>
#include <assert.h>
#include <stdlib.h>
typedef struct __myarg_t {
int a;
int b;
} myarg_t;

typedef struct __myret_t {
int x;
int y;
} myret_t;

void *mythread(void *arg) {
myarg_t *m = (myarg_t *) arg;
printf("%d %d\n", m->a, m->b);
myret_t *r = Malloc(sizeof(myret_t));
r->x = 1;
r->y = 2;
return (void *) r;
}

int
main(int argc, char *argv[]) {
pthread_t p;
myret_t *m;

myarg_t args = {10, 20};
Pthread_create(&p, NULL, mythread, &args);
Pthread_join(p, (void **) &m);
printf("returned %d %d\n", m->x, m->y);
free(m);
return 0;
}

在上述代码中,创建了一个线程,传入了一些参数,在该线程返回之后,得到了它的返回值。当然,我们并不是总需要把参数和返回值包装成struct的。值得注意的是,不要返回指向在线程的调用栈上分配的内存的指针(而改为使用malloc()在堆上分配内存),因为在线程返回之后,它的栈就会被回收。

当然,在这个例子中,调用pthread_create()之后立刻调用pthread_join()的做法是没有什么意义的,因为函数调用也可以达到相同的效果。

并不是所有多线程程序都会用到join函数。有些多线程服务器可能会创建一些工作线程,然后让主线程不断接收请求并传递给其他线程。

互斥锁

最基本的一对上锁/解锁API是:

1
2
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

较高级的API包括:

1
2
3
4
5
// 在无法获得锁时返回错误
int pthread_mutex_trylock(pthread_mutex_t *mutex);
// 在试图获得锁而不成功一段时间后返回错误
int pthread_mutex_timedlock(pthread_mutex_t *mutex,
struct timespec *abs_timeout);

使用示例

1
2
3
4
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is
pthread_mutex_unlock(&lock);

上述代码的含义是:

  • 如果调用pthread_mutex_lock()时没有其他线程持有锁,则该线程可以获得锁并进入关键区
  • 如果有其他的线程正在持有锁,则试图获得锁的进程将会阻塞,直到其他进程将锁释放,该进程获得锁为止

注意几点:

  1. 只有拥有锁的线程才能调用pthread_mutex_unlock()
  2. 需要检查上锁和开锁时可能发生的错误,最简单的方法是assert返回值
  3. 除了静态初始化方法(使用PTHREAD_MUTEX_INITIALIZER进行默认初始化)

修改为动态初始化的示例如下:

1
2
3
4
5
6
7
pthread_mutex_t lock;
int rc = pthread_mutex_init(&lock, NULL);
assert(rc == 0); // always check success!
pthread_mutex_lock(&lock);
x = x + 1; // or whatever your critical section is
pthread_mutex_unlock(&lock);
pthread_mutex_destroy(&lock);

条件变量

1
2
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

需要在线程之间传递信号的时候(比如某个线程等待另一个完成),条件变量是很重要的。条件变量需要一个与它相关的锁。调用上述函数的前提是持有该锁。

pthread_cond_wait()函数的功能是,将调用该函数的线程睡眠,直到其他线程发出信号为止。通常的用法如下:

1
2
3
4
5
6
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
Pthread_mutex_lock(&lock);
while (ready == 0)
Pthread_cond_wait(&cond, &lock);
Pthread_mutex_unlock(&lock);

上述代码在初始化之后,对ready变量进行检查,如果不满足要求,则继续睡眠,等待再次被唤醒。

在其他线程中唤醒该线程的代码如下:

1
2
3
4
Pthread_mutex_lock(&lock);
ready = 1;
Pthread_cond_signal(&cond);
Pthread_mutex_unlock(&lock);

值得注意的是:

  • 在发出信号和修改全局变量ready时,为了防止竞争条件,我们总是确保已经获得了锁
  • wait函数的第二个参数是锁,但signal函数的参数没有锁。这是因为wait函数在使线程进入睡眠的同时也释放了锁(否则其他线程就不可能获得锁并唤醒该线程);在被唤醒之前,wait函数会重新获得锁
  • 等待的线程会通过while循环检查条件是否满足,而不是if语句;这样做是最安全的,因为有些pthread的实现会使得条件未满足时线程仍被唤醒,因此唤醒只是一种提示

作者指出,最好不要自己尝试造轮子来实现条件变量的功能。

线程API使用指南

  • 简化操作:线程之间复杂的互动会导致bug。
  • 减少线程之间的互动
  • 记得初始化锁和条件变量
  • 检查返回值
  • 小心传参的方式,不要返回指向线程栈上的指针
  • 每个线程都拥有自己的栈,只有堆中的变量才是全局的
  • 一定要通过条件变量在线程之间传递信号
  • 多看手册

作业

仍然没做,这次的作业比较复杂,似乎要用到valgrind,还要配置一些环境。