OSTEP01

操作系统导论（中文版） | ostep-chinese

进程

进程就是运行中的程序，程序本身是没有生命周期的，它只是存在磁盘上面的一些指令或者静态数据，操作系统让这些字节运行起来，让程序发挥作用

常常需要同时运行多个程序，实际上，一个正常的系统可能会有上百个进程同时在运行，需要对每个进程提供有许多 CPU 的假象

操作系统通过虚拟化（virtualizing）CPU来提供这种假象

让一个进程只运行一个时间片，然后切换到其他进程，操作系统提供了存在多个虚拟CPU的假象。这就是时分共享（time sharing）CPU 技术。

时分共享（time sharing）是操作系统共享资源所使用的最基本的技术之、一。通过允许资源由一个实体使用一小段时间，然后由另一个实体使用一小段时间，如此下去，所谓的资源（例如，CPU或网络链接）可以被许多人共享

操作系统为正在运行的程序提供的抽象就是进程

进程包括程序再运行时可以读取或更新的内容，比如进程可以访问的内存（地址空间）、程序计数器、栈指针、帧指针、管理函数参数栈、局部变量和返回地址、当前打开的文件列表、进程标识符（PID）等

进程 API

操作系统的所有接口必须包括下面内容：

创建（create）：在 shell 中键入命令或双击应用程序图标时，会调用操作系统来创建新进程，运行指定的程序
销毁（destroy）：系统提供了一个强制销毁进程的接口
等待（wait）：提供某种等待的接口
其他控制（miscellaneous control）：除了杀死或等待进程外，有时还可能有其他控制。例如，大多数操作系统提供某种方法来暂停进程（停止运行一段时间），然后恢复运行
状态（statu）：有些接口获取有关进程的状态信息，例如运行了多长时间，或者处于什么状态

创建进程

操作系统运行程序的第一件事将代码和所有静态数据（例如初始化变量）加载到内存中，加载到进程的地址空间中

也就是说，操作系统必须做一些工作才能将重要的程序字节从磁盘读入内存

操作系统为程序的运行时栈（run-time stack 或 stack）分配一些内存，也可能会用参数初始化栈，即将参数填入 main() 函数，即 argc 和 argv 数组

操作系统为程序的堆（heap）分配一些内存，在 C 程序中，堆用于显示请求动态分配数据，程序通过调用 malloc() 来请求空间，并调用 free() 来释放空间。起初堆会很小，随着程序运行，，通过 malloc()库API请求更多内存

操作系统还执行一些其他初始化任务，特别是和 I/O 相关的任务。例如：在UNIX系统中，默认情况下每个进程都有3个打开的文件描述符（file descriptor），用于标准输入、输出和错误

进程状态

在早期的计算机系统中，进程可能处于下面的 3 中状态之一

运行（running）：在运行状态下，进程正在处理器上运行即正在执行指令
就绪（ready）：在就绪状态下，进程已准备好运行，但操作系统选择不在此时运行
阻塞（blocked）：在阻塞状态下，进程正在等待某些事件发生，例如等待 I/O 操作完成

从就绪到运行意味着进程被调度（scheduled）

从运行到就绪意味着进程被取消调度（descheduled）

一旦进程被阻塞（例如，通过发起I/O操作），OS将保持进程的这种状态，直到发生某种事件（例如，I/O完成），此时，进程再次转入就绪状态（也可能立即再次运行）

考虑下面一个进程在运行一段时间后发送 I/O 请求：

也就是说，Process0 发起 I/O 请求后，OS 将 Process0 转入阻塞状态，并调度 Process1 运行，当 Process1 运行时， I/O 完成，OS 将 Process0 转入就绪状态，等待调度，Process1 结束，OS 调度 Process0 运行

数据结构

操作系统为所有就绪的进程保留某种进程列表，以及跟踪当前正在运行的进程的一些附加信息，，并且需要以某种方式跟踪被阻塞的进程，当 I/O 完成后能正常运行

下面这段代码展示了 OS 需要跟踪 xv6 内核中每个进程的信息类型：

// the register xv6 will save and restore
// to stop ans subsequetly restart a process
struct context{
    int eip;
    int esp;
    int ebx;
    int ecx;
    int edx;
    int esi;
    int edi;    
    int ebp; 
};

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

// the information xv6 tracks zbout 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 channel
    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 current  interrupt
};

可以看到，除了运行、就绪和阻塞状态外，还有一些其他状态，有时候系统会有一个初始状态，表示进程在创建时处于的状态，还有最终状态，表示已退出但未已退出但尚未清理

进程 API

fork()

系统调用 fork() 创建一个新进程，新进程是调用进程的副本，称为子进程（child process），调用进程称为父进程（parent process）

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

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

运行上面的程序，会看到下面的输出：

1
2
3

hello world (pid=869)
hello, I am parent of 870 (pid=869)
hello, I am child (pid=870)

上面这个代码运行时，进程输出hello world 以及自己的进程描述符

接着进程调用了 fork() 创建了一个新进程，这个新进程称为子进程，调用 fork() 的进程称为父进程，子进程不会从头开始运行，而是从 fork() 调用返回处开始运行

父进程获得的子进程返回值为子进程的 PID，而子进程获得的返回值为 0

当然，在单个 CPU 系统上运行时，父进程和子进程会交替运行，此时同时运行的输出顺序是不确定的，CPU 调度程序决定了哪个进程先运行，所以也有可能看到下面的输出：

1
2
3

hello world (pid=869)
hello, I am child (pid=870)
hello, I am parent of 870 (pid=869)

wait()

考虑下面这个程序：

#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", getpid());
    int rc = fork();
    if(rc < 0){
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if(rc == 0){
        printf("hello, I am child (pid=%d)\n", getpid());
    } else {
        int wc = wait(NULL);
        printf("hello, I am parent of %d (pid=%d)\n", rc, getpid());
    }
    return 0;
}

父进程调用了 wait() 延迟自己的执行，直到子进程终止

wait() 的返回值是终止的子进程的 PID

由于添加了 wait() 调用，父进程现在总是等待子进程终止后才继续运行，因此输出顺序是确定的：

1
2
3

hello world (pid=962)
hello, I am child (pid=963)
hello, I am parent of 963 (pid=962)

即使父进程先运行，调用 wait() 后也会阻塞，直到子进程终止

有些情况下，wait() 在子进程退出前返回。
如果父进程在阻塞等待期间捕获到了一个信号，那么 wait() 可能会提前返回，此时返回值为 -1，并且 errno 被设置为 EINTR。在这种情况下，父进程可以选择再次调用 wait() 来继续等待子进程的终止
如果父进程正在使用 ptrace 跟踪子进程，那么每当子进程收到信号或遇到断点停止时，wait() 也会返回。在这种情况下，返回值是子进程的 PID，而不是 -1。此时子进程处于停止状态

exec()

exec() 有几种变体：execl()、execle()、execlp()、execv()、execvp()，可以阅读 man 手册了解更多信息

考虑下面的程序

#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", getpid());
    int rc = fork();
    if(rc < 0){
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if(rc == 0){
        printf("hello, I am child (pid=%d)\n", getpid());
        char *myargs[3];
        myargs[0] = "wc";      // program: "wc" (word count)
        myargs[1] = "exec.c";  // argument: file to count
        myargs[2] = NULL;      // marks end of array
        execvp(myargs[0], myargs); // runs word count
        fprintf(stderr, "this should not print\n");
    } else {
        int wc = wait(NULL);
        printf("hello, I am parent of %d (wc=%d)(pid=%d)\n", rc, wc, getpid());
    }
    return 0;
}

在这个例子中，子进程调用 execvp() 来运行另一个程序 wc，该程序计算文件中的单词数，从而告诉我们文件有多少行、多少单词、多少字节

给定可执行文件名称及所需要的参数，exec() 会从可执行程序中加载代码和静态数据，并用它覆写自己的代码段（以及静态数据），堆、栈及其他内存空间也会被重新初始化，然后 OS 就执行该程序，将参数通过 argv 传递给该进程，因此，它并没有创建新进程，而是直接将当前程序替换为不同的运行程序（wc），因此，exec() 调用后面的任何代码都不会被执行，除非 exec() 调用失败

运行上面的程序，输出如下：

hello world (pid=790)
hello, I am child (pid=791)
 25  99 833 exec.c
hello, I am parent of 791 (wc=791)(pid=790)

可以看到，子进程输出了 wc 命令的结果，显示 exec.c 文件中有 25 行、99 个单词和 833 个字节

重定向

shell 也是一个用户程序，它提供了一个命令行界面，允许用户运行其他程序。

大多数情况下，shell 可以在这个文件系统中刚找到这个可执行程序，调用 fork() 创建新进程，并调用 exec() 的某个变体来执行这个可执行程序，调用 wait() 等待该命令完成，子进程执行结束后，shell 从 wait() 返回并再次输出一个提示符，等待用户输入下一条命令

fork() 和 exec() 的分离使得 shell 可以实现很多功能，比如重定向（redirection）

考虑下面的指令

1	ls > out.txt

ls 指令的输出结果通常会显示在终端上，但是通过 > 符号，用户告诉 shell 将输出重定向到文件 out.txt 中，而不是显示在屏幕上

shell 实现重定向的方式也简单，当完成子进程的创建后，shell 在调用 exec() 之前先关闭了标准输出，打开了文件 out.txt，这样运行程序的结果就会写入到 out.txt 文件中，而不是显示在终端上

下面是一个简单的实现重定向的示例代码：

#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){
        fprintf(stderr, "fork failed\n");
        exit(1);
    } else if(rc == 0){ // child:redirect standard output to a file
        close(STDOUT_FILENO); // close standard output
        open("output.txt", O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU); // create file and set as standard output
        char *myargs[3];
        myargs[0] = "ls";      // program: "ls" (list directory)
        myargs[1] = NULL;      // no arguments to ls
        execvp(myargs[0], myargs); // run ls
        fprintf(stderr, "this should not print\n");
    } else { // parent
        int wc = wait(NULL);
    }
    return 0;
}

output.txt 文件中显示如下：

exec
exec.c
fork
fork.c
output.txt
re
re.c
wait
wait.c

UNIX 管道也是用类似方法实现的，但用的是 pipe() 系统调用，在这种情况下，一个进程的输出被链接到了一个内核管道上，另一个进程的输入也被链接到了同一个管道上，此时前一个进程的输出无缝地作为后一个进程的输入，许多命令可以用这种方式串联在一起，共同完成某项任务

比如使用 grep 命令从 ls 命令的输出中过滤出包含特定字符串的行：

1	ls \| grep "exec"

受限直接执行

为了使程序尽可能快地运行，操作系统开发人员想出了一种技术，称为受限直接执行（limited direct execution）

OS 希望启动程序运行时，它会在进程列表中为其创建一个进程条目，分配内存，加载程序代码和数据，初始化堆和栈，然后让 CPU 直接运行该程序

但这种方法在虚拟化 CPU 时产生了一些问题

如果我们只运行一个程序，操作系统怎么能确保程序不做任何我们不希望它做的事，同时仍然高效地运行它？

当我们运行一个进程时，操作系统如何让它停下来并切换到另一个进程，从而实现虚拟化 CPU 所需的时分共享？

问题1：受限制的操作

直接执行的明显优势是快速，但是如果进程希望执行某种受限操作，比如向磁盘发出 I/O 请求或获得更多系统资源，如 CPU 或内存，该怎么办？

采用的方法为引入一种新的处理器模式：用户模式

在用户模式下运行的代码会受到限制，例如：在用户模式下运行时，进程不能发出 I/O 请求

OS 以内核模式运行

在此模式下，代码可以做任何事情，包括发出 I/O 请求、访问硬件设备以及执行其他受限操作

但是，如果用户希望执行受限操作怎么办？

要执行系统调用，程序必须执行特殊的陷阱（trap）指令，陷阱指令会将处理器从用户模式切换到内核模式，，完成后， OS 调用一个特殊的从陷阱返回（return-from-trap）指令，将处理器切换回用户模式，并返回到用户程序中陷阱指令的下一条指令

执行陷阱时，它必须确保存储足够的调用者寄存器，以便在 OS 发出从陷阱返回指令时能够正确返回

例如，在 x86 上，处理器会将程序计数器 EIP 和标志 EFLAGS 压入内核栈中，然后将处理器切换到内核模式，并跳转到内核中的陷阱处理程序

其他硬件系统类似

内核通过在启动时设置陷阱表（trap table）来管理陷阱处理程序

OS 告诉硬件在发生某些异常事件时需要运行哪些代码，操作系统通常通过某种特殊的指令，通知硬件这些陷阱处理程序的位置

LDE 协议有两个阶段

一个阶段内核初始化陷阱表，，并且 CPU 记住它的位置以供随后使用，内核通过特权指令来执行此操作
第二个阶段在使用从陷阱返回指令开始执行进程之前，内核设置了一些内容。这会将CPU切换到用户模式并开始运行该进程。当进程希望发出系统调用时，它会重新陷入操作系统，然后再次通过从陷阱返回，将控制权还给进程。该进程然后完成它的工作，并从main()返回

问题2：在进程之间切换

如果一个进程在 CPU 上运行，这就意味着 OS 没有运行，如果 OS 没有运行，它就无法切换到另一个进程

协作方式：等待系统调用

老 OS 采用的方式称为协作方式（cooperative multitasking）

操作系统相信系统的进程会合理运行，运行时间过长的进程被假定定期放弃 CPU，以便 OS 可以决定运行其他任务

如果应用程序执行了某些非法操作，也会将控制转移给操作系统。例如，如果应用程序以0为除数，或者尝试访问应该无法访问的内存，就会陷入（trap）操作系统。操作系统将再次控制CPU（并可能终止违规进程）

但是，如果进程是恶意的或有缺陷的，它可能永远不会放弃 CPU，从而阻止其他进程运行

非协作方式：操作系统进行控制

在协作方式中，当进程陷入无限循环时，唯一的办法就是使用古老的解决方案来解决计算机系统中的所有问题——重新启动计算机

时钟中断（clock interrupt）是一种硬件机制，允许操作系统定期获得 CPU 控制权

时钟设备可以编程为每隔几毫秒产生一次中断，产生中断时，当前正在运行的进程停止，操作系统中预先配置的中断处理程序（interrupt handler）会运行。此时，操作系统重新获得CPU的控制权

操作系统必须通知硬件哪些代码在发生时钟中断时运行，在启动时，操作系统必须启动时钟，这是一项特权操作

保存和恢复上下文

调度程序（scheduler）是操作系统的一部分，负责在进程之间切换 CPU

如果决定进行切换，OS 就会执行一些底层代码，即所谓的上下文切换（context switch）

操作系统为当前正在执行的进程保存一些寄存器的值，并为即将执行的进程恢复一些寄存器的值，此时操作系统就可以确保最后执行从陷阱返回指令时，不是返回到之前的进程，而是继续执行另一个进程

操作系统会执行一些底层汇编代码，来保通用寄存器、程序计数器，以及当前正在运行的进程的内核栈指针，然后恢复寄存器、程序计数器，并切换内核栈，供即将运行的进程使用

通过切换栈，内核在进入切换代码调用时，是一个进程（被中断的进程）的上下文，在返回时，是另一进程（即将执行的进程）的上下文

当操作系统最终执行从陷阱返回指令时，即将执行的进程变成了当前运行的进程。至此上下文切换完成

考虑下面的例子：

进程A正在运行，然后被中断时钟中断。硬件保存它的寄存器到内核栈中，并进入内核模式，在时钟中断处理程序中，操作系统决定从正在运行的进程A切换到进程B，此时调用 switch() 例程，仔细保存当前寄存器的值（保存到 A 的进程结构），恢复寄存器进程B，然后切换上下文

具体来说是通过改变栈指针来使用B的内核栈（而不是A的）。最后，操作系统从陷阱返回，恢复B的寄存器并开始运行

有两种类型的寄存器保存/恢复

第一种是发生时钟中断的时候。在这种情况下，运行进程的用户寄存器由硬件隐式保存，使用该进程的内核栈
第二种是当操作系统决定从A切换到B。在这种情况下，内核寄存器被OS 明确地保存，但这次被存储在该进程的进程结构的内存中。后一个操作让系统从好像刚刚由A陷入内核，变成好像刚刚由B陷入内核。

下面给出了 x86 上 switch() 例程的汇编代码：

# void switch(struct context *old, struct context *new);
    # Save current register context in old 
	# and then load register context from new. 
	.glob_switch
	switch:
	# Save old registers
	movl 4(%esp), %eax  # put old ptr into eax
	popl 0(%eax)        # save the old IP 
	movl %esp, 4(%eax)  # and stack
	movl %ebx, 8(%eax)  # and other registers 
	movl %ecx, 12(%eax)
	movl %edx, 16(%eax)
	movl %esi, 20(%eax)
	movl %edi, 24(%eax)
	movl %ebp, 28(%eax) 
	
	# Load new registers
	movl 4(%esp), %eax # put new ptr into eax 
	movl 28(%eax), %ebp # restore other registers
	movl 24(%eax), %edi
	movl 20(%eax), %esi 
	movl 16(%eax), %edx 
	movl 12(%eax), %ecx 
	movl 8(%eax), %ebx 
	movl 4(%eax), %esp  # stack is switched here 
	pushl 0(%eax)       # return addr put in place 
	ret                 # finally return into new ctxt

首先，切换进程时，栈状态如下：（地址由低变高）

1
2
3

| pointer to new context             |
| pointer to old context             |
| return address to caller of switch | <- %esp

此时执行 movl 4(%esp), %eax，取出 old 结构体地址并放入 %eax

执行 popl 0(%eax)，此时 pop 的是 return address to caller of switch，将其保存到 old->eip 中，然后 %esp 增加4

1 2	\| pointer to new context \| \| pointer to old context \| <- %esp

执行movl %esp, 4(%eax)，将 %esp 保存到 old->esp 中，记住了旧进程的栈顶在哪里，然后依次保存其他寄存器到 old 结构体中

之后准备切换到新进程

执行 movl 4(%esp), %eax，取出 new 结构体地址并放入 %eax，现在 %eax 指向 new 结构体，依次把 new 结构体中的寄存器值恢复到 CPU 寄存器中

执行 movl 4(%eax), %esp，将 new->esp 恢复到 %esp 中，此时栈切换到了新进程的内核栈

执行 pushl 0(%eax) ，将 new->eip 压入栈中，作为返回地址，构造了一个刚调用完函数返回的栈帧

进程调度

如何开发调度策略？
该如何开发一个考虑调度策略的基本框架？什么是关键假设？哪些指标非常重要？哪些基本方法已经在早期的系统中使用？

工作负载假设

先做一些简化假设。这些假设与系统中运行的进程有关，称为工作负载（workload）

对进程做出如下的假设

每一个工作运行相同的时间
所有的工作同时到达
一旦开始，每个工作保持运行直到完成
所有的工作只是用CPU（即它们不执行IO操作）
每个工作的运行时间是已知的

调度指标

进程调度中有不同的指标，分别比较不同的调度算法

这里简化问题，只使用一个指标：周转时间（turnaround time） \[ T_{周转时间}=T_{完成时间}-T_{到达时间} \] 因为我们假设所有的任务在同一时间到达，那么 \(T_{到达时间}=0\)，因此 \[ T_{周转时间}=T_{完成时间} \]

(´-ω-｀)

OSTEP01

进程

进程 API

创建进程

进程状态

数据结构

进程 API

fork()

wait()

exec()

重定向

受限直接执行

问题1：受限制的操作

问题2：在进程之间切换

协作方式：等待系统调用

非协作方式：操作系统进行控制

保存和恢复上下文

进程调度

工作负载假设

调度指标

先进先出（FIFO）

最短任务优先（SJF）

最短完成任务优先（STCF）

新度量指标：响应时间

轮转法（RR）

结合 I/O

无法预知

多级反馈队列（MLFQ）