0 引子
CPU虚拟化就是对系统中的有限的物理CPU进行虚拟化，让系统中的多道程序都误认为自己占用了CPU资源。
CPU虚拟化的关键是对运行程序的抽象，即进程的概念，然后，系统需要保证多个进程可以独立的、不受干扰的运行，最后CPU如何调度这些进程，合理利用有限的CPU资源。
1 进程
进程就是运行的程序，是程序在某一个数据集上的执行过程。
1.1 进程的创建
- 将存放在磁盘上的代码和静态数据加载进内存；
- 为栈和堆分配内存；
- 其他初始化任务 ，如I/O初始化；
- 跳转到main()入口处，OS将CPU控制权转移到该进程；
1.2 进程的状态
阻塞状态也可以直接进入运行状态，这取决于系统的调度策略。
1.3 进程的API
-
fork()——系统创建新进程的系统调用
子进程不会从main()函数开始执行，而是从fork系统调用返回，就好像它自己调用了fork()一样，这说明子进程复制了父进程的程序计数器寄存器。
调用fork()之后，父进程返回子进程的PID，子进程返回0，出错返回负数。（类似于链表）
-
wait()——父进程等待子进程执行完毕，该系统调用，会在任意一个子进程运行结束之后才返回。
如果没有子进程，则wait调用会立即返回-1
-
exec()——让子进程执行与父进程不同的程序
对exec的成功调用，永远也不会返回。
-
shell的工作原理
shell是一个用户程序，它首先显示一个提示符，然后等待用户输入。shell在文件系统中找到命令的可执行文件后，调用fork()创建新进程，并调用exec()执行这个可执行程序，调用wait()等待该命令完成。子进程结束后，shell从wait()返回，并再次显示提示符。
2 受限直接执行
有了进程之后，我们可以让一个进程运行一段时间，然后切换另外一个进程运行一段时间，因为CPU的速度很快，所以看起来这些进程就像在同时运行一样。
现在的问题是，我们怎么样实现快速的进程切换，即性能问题。还有一个问题，操作系统必须拥有绝对的控制权，如何才能实现系统在执行用户程序的时候，操作系统还能重新获得CPU控制权呢？即控制权问题。
CPU存在两种模式（硬件支持）：用户模式和内核模式。用户模式下运行的程序需要执行陷阱指令，才能进入内核模式。由于加入了硬件机制，此时操作系统可以掌控CPU。
时钟中断——操作系统打断正在运行的进程，获得CPU控制权。
中断发生时，硬件可以捕获到中断号，利用中断向量表（上图中的陷阱表），找到处理此中断的处理程序。
上下文切换：操作系统为当前正在执行的进程保存一些寄存器的值，并为即将执行的进程恢复一些寄存器的值。
请注意，在此协议中，有两种类型的寄存器保存/恢复。第一种是发生时钟中断的时候。在这种情况下，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈。第二种是当操作系统决定从A切换到B。在这种情况下，内核寄存器被软件（即OS）明确地保存，但这次被存储在该进程的进程结构的内存（进程控制块PCB）中。后一个操作让系统从好像刚刚由A陷入内核，变成好像刚刚由B陷入内核。
Linux 中的各种栈：进程栈 线程栈 内核栈 中断栈
3 进程调度
一个评价指标：周转时间——任务完成时间减去任务到达时间。
-
先进先出（First In First Out，FIFO）
如果长任务先到，则可能导致平均周转时间过长。下图任务的平均周转时间是110
为什么FIFO没有这么好 -
最短任务优先（Shortest Job First，SJF）
该调度算法是非抢占式的，在所有任务同时到达的情况下，这种调度算法的周转时间最优。 -
最短完成时间优先（Shortest Time-to-Completion First，STCF）
SJF算法的抢占式版本，当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
另外一个评价指标：响应时间——从任务到达系统到首次运行的时间。交互性。
-
轮转（Round-Robin，RR）
RR在一个时间片内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。
时间片长度必须是时钟中断周期的倍数。
-
多级反馈队列（Multi-level Feedback Queue，MLFQ）
- 规则1：如果A的优先级 > B的优先级，运行A（不运行B）。
- 规则2：如果A的优先级 = B的优先级，轮转运行A和B。
- 规则3：工作进入系统时，放在最高优先级（最上层队列）。
- 规则 4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。
- 规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。
课后作业
1．编写一个调用fork()的程序。在调用fork()之前，让主进程访问一个变量（例如x）并将其值设置为某个值（例如100）。子进程中的变量有什么值？当子进程和父进程都改变x的值时，变量会发生什么？
子进程复制（但不共享）父进程中的局部变量值
输出结果：
init x value: 100
child! x value is 200
child done! x value is 100
parent! x value is 300
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
int main(int argc, char* argv[])
{
int x = 100;
printf("init x value: %d\n", x);
int rc = fork();
if(rc < 0){
fprintf(stderr, "fork error\n");
exit(-1);
}
else if(rc == 0){
x = 200;
printf("child! x value is %d\n", x);
}
else{
int wc = wait(NULL);
printf("child done! x value is %d\n", x);
x = 300;
printf("parent! x value is %d\n", x);
}
return 0;
}
2．编写一个打开文件的程序（使用open()系统调用），然后调用fork()创建一个新进程。子进程和父进程都可以访问open()返回的文件描述符吗？当它们并发（即同时）写入文件时，会发生什么？
子进程复制了父进程的文件描述符，使用同一个流。都可以往打开文件中写入数据。
并发执行时可能会交替写入文件。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/wait.h>
int main(int argc, char *argv[])
{
int fd = open("q2.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork error\n");
exit(1);
}
else if(rc == 0) {
for(int i = 0; i < 10000; i++)
write(fd, "c", 1);
}
else {
int wc = wait(NULL);
for(int i = 0; i < 10000; i++)
write(fd, "p", 1);
}
return 0;
}
3．使用fork()编写另一个程序。子进程应打印“hello”，父进程应打印“goodbye”。你应该尝试确保子进程始终先打印。你能否不在父进程调用wait()而做到这一点呢？
怎么实现进程同步？这里使用了文件进行同步。父进程需要以只读的方式重新打开文件，读取标记。
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <fcntl.h>
int main(int argc, char *argv[])
{
int fd = open("q3.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);
// printf("fd is %d\n", fd);
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork error\n");
exit(0);
}
else if(rc == 0) {
printf("child! hello\n");
write(fd, "a", 1);
exit(0);
}
else{
printf("enter parent\n");
char buf[5];
int tmp;
while((tmp = read(fd, buf, 1)) != 1) {
// printf("%d\n", tmp);
// 为什么需要重新打开文件???
// （猜测：）子进程exit()，所以子进程自动关闭了文件描述符
fd = open("q3.output", O_RDONLY);
// 也可以判断文件描述符是否可用
// but how??
// ERROR OPEN
// fd = open("q3.output", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);
}
printf("parent! goodbye\n");
}
return 0;
}
4．编写一个调用fork()的程序，然后调用某种形式的exec()来运行程序/bin/ls。看看是否可以尝试exec()的所有变体，包括execl()、execle()、execlp()、execv()、execvp()和execvP()。为什么同样的基本调用会有这么多变种？
5．现在编写一个程序，在父进程中使用wait()，等待子进程完成。wait()返回什么？如果你在子进程中使用wait()会发生什么？
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char *argv[])
{
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork error\n");
exit(1);
}
// 如果没有子进程而调用wait()，会怎么样呢？
// 出错，并直接返回-1
else if(rc == 0) {
int wc = wait(NULL);
printf("child! (pid: %d)\n", (int)getpid());
printf("child wc: %d\n", wc);
}
else{
// int wc = wait(NULL);
printf("parent of %d, (pid: %d)\n", rc, (int)getpid());
// printf("wc: %d\n", wc);
}
printf("done!\n");
return 0;
}
6．对前一个程序稍作修改，这次使用waitpid()而不是wait()。什么时候waitpid()会有用?
__pid_t waitpid (__pid_t __pid, int *__stat_loc, int __options);
If PID is greater than 0, match any process whose process ID is PID.
If PID is (pid_t) -1, match any process.
If PID is (pid_t) 0, match any process with the
same process group as the current process.
If PID is less than -1, match any process whose
process group is the absolute value of PID.
wait(NULL); 等价于 waitpid(-1, NULL, 0);
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
int main(int argc, char *argv[])
{
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork error\n");
exit(1);
}
// 如果没有子进程而调用wait()，会怎么样呢？
// 出错，并直接返回-1
else if(rc == 0) {
printf("child! (pid: %d)\n", (int)getpid());
}
else{
int tmpc = fork();
if(tmpc == 0) {
printf("other child~ (pid: %d)\n", (int)getpid());
sleep(20);
}
else{
int wc = waitpid(-1, NULL, 0);
printf("parent of %d, (pid: %d)\n", rc, (int)getpid());
printf("wc: %d\n", wc);
}
}
printf("(pid: %d) done!\n", (int)getpid());
return 0;
}
7．编写一个创建子进程的程序，然后在子进程中关闭标准输出（STDOUT_FILENO）。如果子进程在关闭描述符后调用printf()打印输出，会发生什么？
父进程和子进程不会公用stdin，stdout，stderr流吗？为什么子进程关闭了，父进程还是可以输出呢？为啥第二题就会共用open打开的文件？
printf是带有缓冲区的，所以close在前面和后面不一样，但是write不带缓冲区，close在前后都一样的。
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int rc = fork();
if(rc < 0) {
fprintf(stderr, "fork error\n");
exit(-1);
}
else if(rc == 0) {
// printf 属于标准I/O，带有缓冲区，write属于系统I/O，没有缓冲区
// close(STDOUT_FILENO);
printf("child\n");
// fflush(stdout);
write(STDOUT_FILENO, "child\n", 6);
close(STDOUT_FILENO);
close(STDIN_FILENO);
close(STDERR_FILENO);
fprintf(stderr, "don't output\n");
}
else{
// 父进程和子进程貌似不会共用输出流(and stdin, stderr)，
// 因为子进程关闭之后，父进程还是可以输出
wait(NULL);
printf("parent\n");
int c;
scanf("%d", &c);
printf("%d\n", c);
fprintf(stderr, "close\n");
}
return 0;
}
8．编写一个程序，创建两个子进程，并使用pipe()系统调用，将一个子进程的标准输出连接到另一个子进程的标准输入。
int pipe (int __pipedes[2])
If successful, two file descriptors are stored in PIPEDES; bytes written on PIPEDES[1] can be read from PIPEDES[0].
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
int pipefd[2];
// If successful, two file descriptors are stored in PIPEDES;
// bytes written on PIPEDES[1] can be read from PIPEDES[0].
pipe(pipefd);
int rc1 = fork();
if(rc1 < 0) {
exit(1);
}
else if(rc1 == 0) {
char s[] = "this message transproted by pipe\n";
write(pipefd[1], s, sizeof(s)); // write to pipe
// close(pipefd[0]);
// close(pipefd[1]);
}
else{
waitpid(rc1, NULL, 0);
int rc2 = fork();
if(rc2 < 0) {
exit(1);
}
else if(rc2 == 0) {
char buf[1024];
//read(pipefd[0], buf, 1024);
//printf("%s", buf);
int tmp;
while((tmp = read(pipefd[0], buf, 1)) == 1){
printf("%c", buf[0]);
printf("%d", tmp);
}
// close(pipefd[0]);
// close(pipefd[1]);
}
else{
waitpid(rc2, NULL, 0);
}
}
return 0;
}
