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的方式执行。
- 当任务到达时，放入最高优先级队列中。
- 如果任务在当前队列的时间片配额用完后，被移入低一个等级的队列中。
- 每过一段时间，所有任务都被移入最高优先级的队列中。