OSTEP笔记：进程和调度

Operating Systems Three Easy Piece的读书笔记

绪论：为什么需要操作系统

操作系统做的事情大概可以分为三个部分：

对资源(CPU, MEM)虚拟化
处理并发问题
提供持久化的文件系统

OSTEP说，虚拟化不适用于文件系统，文件系统本身是程序间通信的一种方式。不过现在移动端的iOS和Android，其实也在做文件系统的隔离。 Docker可以算是对OS本身的虚拟化，文件系统对应也被虚拟化了。对文件系统的隔离算是个越来越强的需求了。

设计目标：

提供抽象方法API
降低抽象的额外开销
提供应用程序的保护

最开始的操作系统只是一系列对硬件操作的API的集合库。但是对资源的保护和虚拟化是库做不了的。最先被虚拟化的资源是CPU，通过对CPU时间片的管理，一个CPU可以跑多个程序。

想到看一些早期的数据库实现的论文，写一个数据库前，首先要选择一类机型，有特定的CPU，硬盘参数和驱动，然后port一个操作系统，在上面做线程, 文件系统的抽象。那时候的操作系统，估计做的就只是一些对硬件资源的抽象。

进程

进程就是一个运行中的程序。操作系统想运行一段程序，需要经历：

将程序代码和静态数据(例如变量初始化的值）从磁盘中加载到内存中。因为虚拟内存机制，加载可以是eager的，立刻将程序全部加载到内存中，也可以是lazy的，只加载目前用到的部分。
为程序分配堆栈空间。
做一些初始化工作，主要是I/O相关的，例如UNIX会开启STDIN, STDOUT, STDERR这些文件。
跳转到main()函数处，执行代码。

操作系统将这样的一个运行中的程序的概念，抽象为进程。

对应的，进程会有一些运行中可以读写的一些状态：

地址空间。
寄存器。特殊的寄存器有：Program Counter，Stack Pointer和frame Counter等等。
IO信息，如file descriptor等。

操作系统可以对进程做一些操作：

创建
销毁
等待。等待一个进程结束。
获取进程状态。
一些杂项控制。

当需要同时运行多个进程时，OS需要让进程认为有无限个CPU可用，通过对CPU资源的虚拟化，来实现并发的运行。例如分时系统，每个进程都只能占用一定的时间片。

简单的说，进程的生命周期可以分成三类：

运行(RUNNING)。进程执行中。
准备就绪(READY)。进程可以被调度，但尚未被调度。
阻塞（BLOCKING）。进程被某些操作阻塞，无法被调度。例如，执行某些IO操作，且IO操作未返回时。

这三种状态可以相互流转。

至于怎么流转，取决于OS的调度策略。

xv6进程状态:

  // 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 !zero, sleeping on chan
    int killed;                 // If !zero, has 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
  };

API

Unix关于进程的一些API：

fork, 将目前的context复制，创建出一个子进程。子进程返回0，父进程返回子进程的pid。
wait, 等待一个进程完全停止。
exec, 用一个新的程序，完全替换掉当前进程。

一种实现重定向的方式：关掉STDOUT，再open一个文件。操作系统会从0寻找可用的文件描述符，因为STDOUT比较小，这个文件的fd就是STDOUT。

有限直接执行机制

操作进程是如何执行一个进程的？最简单的方法是：将PC跳转到进程的代码入口，由CPU直接执行进程的代码。

限制操作

但是这样做之后，每一个进程都会拥有CPU的所有权限，可以用来读、写其他进程的内存等等不应该访问的区域，操作系统无法阻止进程做任何事情。

为了防止这样的情况发生，CPU引入了一套机制：内核态和用户态。在内核态下，程序可以做任何事情，操作系统运行在内核态下，而操作系统执行的进程运行在用户态下。操作系统提供了一系列的系统调用，应用程序可以通过系统调用来访问一些资源。

系统调用的实现是通过trap来做的。当操作系统启动时，会在内核态下注册一系列的trap跳转表，跳转到操作系统的内部代码中。进程执行系统调用时，会通过trap表，进入内核态，跳转到操作系统中的对应代码。当系统调用完成时，操作系统会将CPU的控制还给应用程序，返回用户态。

一次带系统调用的程序执行路径是这样的：

操作系统启动时，初始化trap跳转表。CPU记下trap跳转的地址。
操作系统从硬盘中将程序加载到内存中，并分配堆栈空间，寄存器，初始化进程状态，进入用户态，跳转到程序的main函数中开始执行。
进程执行到系统调用时，通过cpu的trap进入到操作系统代码，陷入内核态。操作系统保存进程的寄存器等信息，执行对应的操作。
当操作系统执行完时，将保存的进程上下文恢复，返回用户态，继续执行对应的程序。
进程执行完后，执行系统调用exit
操作系统清理进程的状态、内存。

中断执行

当CPU在执行进程的代码时，是无法执行操作系统的代码的。操作系统也就无法控制进程的执行。

解决这个问题，一种方法是，进程通过特殊的系统调用，主动放弃对CPU的控制。这个需要进程的主动配合。

操作系统如果需要主动的掌握控制权，必须要利用CPU的时钟中断。启动时操作系统注册CPU的时钟中断，启动计时器，当一个时间片过去后，会发生一次时钟中断，CPU会跳转到操作系统注册的内存地址执行，操作系统就相应掌握了CPU的控制权，可以处理进程的调度了。

切换线程执行是一次上下文切换的过程（context swtich)。上下文切换时，操作系统会保存之前执行的进程的上下文，加载将要运行的进程的上下文。

当一次中断发生时，如果另一次中断再次发生，操作系统可以选择禁用中断，也有一些锁机制防护对内部数据结构的并发修改。

调度策略(policies)

OS怎么调度进程更合适呢？

关于任务，我们有一些假设：

所有任务运行相等时间
所有任务启动的时间一致
启动任务后，任务必须执行完。
任务只使用CPU。
操作系统知道所有进程的需要消耗的时间。

有两种指标：

周转时间（turnaround time），任务完成时间减去任务到达时间。
响应时间（Response Time），第一次运行减去任务到达时间。

FIFO

先到达先处理

当1，2，3，4，5都满足时，是合理的

SJF

去掉假设1

先执行消耗时间最短的任务，这样总和周转时间最短。

STCF

去掉假设2,3

抢占式的算法，可以打断一个任务执行。

先执行完成时间最短的任务。总和周转时间最短。

RR

引入响应时间作为关注指标

每个任务执行一个时间片，轮流执行。

允许Overlap

去掉假设4,引入IO。

将每个中间有IO的任务，拆分成若干个独立的任务，再使用STCF，增加CPU的利用率。

多级反馈队列调度算法

去掉假设5

思路：设立多个队列，按优先级由高到低排列。CPU调度时，从最高优先级队列开始取任务执行。

当任务A的优先级 > 任务B时，任务A先执行。
当两个任务优先级相等时，两个任务以RR的方式执行。
当任务到达时，放入最高优先级队列中。
如果任务在当前队列的时间片配额用完后，被移入低一个等级的队列中。
每过一段时间，所有任务都被移入最高优先级的队列中。