操作系统：CPU虚拟化

intro

线程简单理解：一个进程里可以有多个线程，线程可以看作小的进程。同一个进程下的线程共享全局变量和堆内存。

进程

创建

现代操作系统lazily执行该过程，只有到需要时才会加载数据到进程的地址空间。

API

fork

拷贝父进程，但从fork开始执行。同时fork的返回值，子进程是0，父进程为子进程的pid。

wait

延迟进程的执行，直到子进程运行完毕才返回

exec

并无创建子进程，而是将当前运行的程序替换为不同的运行程序。通过参数来重新初始化代码段、堆、栈等。

fork和exec的分开可以实现很多功能。shell：先找到可执行程序，接着fork新进程，在新进程里面exec程序，最后wait直到进程结束。比如shell的重定向。

如：$ cat hello.c > hello.txt，在运行cat之前，先打开hello.txt，关闭stdout，然后再运行，就可以实现重定向。

limited direct execution

限制操作

为了让进程可以安全地在cpu上运行，引入不同的模式：

• user mode：行为受限
• kernel mode：可以实现特权操作。
  执行系统调用时，会通过trap来跳入内核并切换模式。通过内核启动时设置的trap table来跳转到相应的异常处理代码

进程切换

cooperative

当应用程序结束、异常、运行时间过长，或者通过系统调用，控制权回归操作系统。（理想的程序）

timer interrupt

时钟为设备产生周期性的中断，控制权还给操作系统，让os决定接下来运行什么。

context

保存恢复上下文，即上下文切换。为当前的进程保存状态（寄存器etc），为接下来的进程恢复状态。注意与上文的中断不同，前者隐式保存用户的寄存器到该进程的内核栈，后者显示保存到该进程结构的内存（通过保存指针，来保存和恢复状态）（？）

进程调度基础

指标

对于每个进程：
周转时间 = 完成时间 - 到达时间 （性能）
响应时间 = 首次运行时间 - 到达时间（公平）

SJF

shortest job first，先运行最短时间的任务。对比FIFO的工作方式，周转时间降低。

STCF

shortest time-to-complete first，又称抢占式任务优先，每当有新工作加入系统，都会确定哪个工作的剩余时间最小，周转时间降低。

RR

轮转调度，将工作变成多个时间切片，循环执行不同工作的切片。时间片变短，响应时间越高，但相对的上下文切换的成本提高。公平和性能是一对需要权衡的因素，不可兼得。

overlap

一个工作使用I/O的时间，可以看成是独立于该工作。则另一个工作可以利用I/O运行的时间。

MLFQ

multi-level feedback queue，多级反馈队列，其维护了多个优先级不同的队列，每个工作只存在于一个队列中，不同的队列有不同的时间配额，利用反馈的信息来决定工作的优先级。下面是其规则：

• A的优先级 > B的优先级，则运行A而不运行B
• A的优先级 = B的优先级，则轮转运行A和B
• 工作进入系统时，放在最高优先级的队列
• 一旦工作用完了其在该队列的时间配额，就降低其优先级
• 经过一段时间S，所有工作重新加入最优先队列

proportional-share

比例份额调度

lottery share

进程运行越久，其彩票越多。在每次调度决策之前，都会抽出一个数字（中奖号码），显然，彩票越多的进程，中奖概率越大，则作为下一个运行的对象。该方法运用了随机性，当运行时间足够长时，不同工作的时间比例会趋于期望。实现上，比较轻量。

和LRU替换算法进行对比，LRU在遇到重复循环序列时，性能低。而彩票调度可以避免。

stride scheduling

步长调度，算法始终选择行程值最小的工作。严格实现，在每次调度都是正确的比例。

然而以上两种方法都不常用。