【操作系统导论】CPU虚拟化

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 进程调度

一个评价指标：周转时间——任务完成时间减去任务到达时间。
T_{周转时间}=T_{完成时间}-T_{到达时间}

  • 先进先出（First In First Out，FIFO）
    如果长任务先到，则可能导致平均周转时间过长。下图任务的平均周转时间是110
    为什么FIFO没有这么好
  • 最短任务优先（Shortest Job First，SJF）
    该调度算法是非抢占式的，在所有任务同时到达的情况下，这种调度算法的周转时间最优。
  • 最短完成时间优先（Shortest Time-to-Completion First，STCF）
    SJF算法的抢占式版本，当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。

另外一个评价指标：响应时间——从任务到达系统到首次运行的时间。交互性。
T_{响应时间}=T_{首次运行}-T_{到达时间}

  • 轮转（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;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容