摘要
这是一篇学习笔记
进程是一段正在运行的程序。它是一个抽象概念，为什么需要抽象出进程的概念，来源于操作系统的物理机CPU有限的场景，人们总是希望要同时运行多个程序，但是CPU是有限。势必要分享CPU。
问题：如何做成一个有很多很多CPU——而不是三四个这样比较少的CPU？
怎么分享 CPU ？很容易想到的方法是不同的时间段分给不同的程序，这就是时分共享的观念
时分共享即在不同的时间段运行不同的程序，也就是进程，这样到了另一段时间就切换到另一个进程
这就是 CPU 虚拟化技术——通过共享 CPU 造成有许多CPU 的假象。
进程的机器状态：内存，即进程可以访问的地址空间
寄存器（程序计数器，栈指针，帧指针）
时分共享技术的挑战点：
性能： 切换地址空间势必带来一些性能的代价，时分共享技术需要尽可能降低性能损耗
控制权： 这是什么情况呢？控制权是指，指令对于硬件资源的管理权力，应用程序的逻辑来自用户，操作系统不能全权把资源控制的权利交给一个进程，否则进程可能无法被制约，它想做什么就做什么——这也是操作系统的意义之一
如何高效，可靠地虚拟化CPU
这个问题现代操作系统的方案是
让程序直接在CPU上运行，这是最朴素的操作系统——OS启动程序时，为他创建一个条目，加载内存，把指令从磁盘加载到内存上，然后从入口 main 函数处开始执行，结束后回收内存。
朴素的办法不能保证应用程序的行为是受限，这可能导致我们的机器失去控制，第二点就是时分共享的需求要怎么满足。
受限操作如何执行？
现代操作系统通过执行模式来处理受限执行和控制权转移的问题
用户模式(User mode) 不能完全访问硬件
内核模式(Kenel mode) 可以访问全部硬件
用户模式可以理解成是解决应用程序的权限问题而设置的，但是几乎大多复杂一点的程序都有访问硬件资源的需求，比如写磁盘。是不是我们的应用程序大部分只能运行在内核态？如果是这样，分成用户模式和内核模式是毫无意义的。
所以，我们有了系统调用这个东西。
操作系统提供了一组 API 在用户模式下调用，一般是申请硬件资源，做一些硬件操作的 API ，一旦调用，操作系统通过一种叫 trap的方式陷入内核，完成操作后返回
这些api是精心设计的，实现细节不暴露给用户，但同时它的逻辑是值得信赖的，他们除了说明文档声明会做的事情，不会偷偷去搞其他事情。
这个设计可以理解为在两个地域之间开了几道门，API相当于最高机构派驻的代理，它们只做他们应该做的事情，通过这个比喻，我们大概可以将他将一些软件设计模式联系起来，比如代理模式。
系统调用在代码层看起来就是一个过程调用，但是内部细节几乎都包含了陷入指令。
函数过程调用唯一能做的事情就是发起一个调用，然后等待内核态陷阱指令返回恢复用户态，至于陷阱的指令怎么做过程调用管不着,它不能控制陷阱要跳转的地址——否则违反了受限保护的初衷，将会使应用程序不受控制。
那么，陷阱指令如何知道OS要运行哪些指令，跳转的目的地在哪里？
这个就是陷阱表要解决的事情，trap table
操作系统启动（初始化）的时候就告诉硬件哪些异常发生时干那些事情，这些叮嘱被记录在trap table上，
想想为什么是启动时约定好陷阱表？
时间线：
另外一个问题：进程切换。
好像很自然，进程A运行一会，操作系统把A的进程空间，内存状态，寄存器这些东东存在栈内，运行程序B，一段时间后回来运行A，从栈里恢复状态继续运行A。很自然。
但是灵魂问题来了： CPU是在跑进程 A，这个时候操作系统不是什么都做不了吗？它的“切换”动作怎么完成？换言之，CPU的控制权是怎么被交回 OS 的？
很自然想到的两种方案分别是主动和被动两种，
主动方式类似于，我提前设置好一个机制，每隔一段时间硬件自动把控制权还给操作系统
被动则是应用程序很乖，跑一段时间时候把控制权交回
被动式很明显的问题是“死机”现象，它不乖，一直在无限循环做自己的事情，也不触及任何系统调用，怎么办？只能重启机器。
时钟中断：如何在没有协作的情况下重获控制权
时钟中断是一个硬件装置，它事先编好程序，每隔几毫秒产生一次中断，OS在启动时规定好中断产生时操作系统会运行的程序。
这样，每隔几毫秒操作系统就有希望通过中断重新夺回控制权。
操作系统在这种情况下，几乎看起来时时都能掌控全局资源，所以在时钟中断机制下，可以认为操作系统在资源支配方面做到了处于最上层的地位
操作系统的这项权力来源非常仰仗时钟的开闭和，因为可以控制时钟必然是一项很高级的权限。
操作系统密集地获得时钟中断返回的控制权，那么它肯定要做点什么，是继续当前的进程运行，还是换一个进程。这就是进程调度问题领域关注的点了
以上。相当于大致搞清楚了，软件如何与硬件结合，能够将系统资源安全掌控，同时又做到具备了进程调度的前提——上下文切换。
进程调度
进程调度的目的是让全局进程尽可能有一个合理的时间分配
这个“合理”的度量有几个常见的标准
一组进程的平均周转时间最短
周转时间定义为：任务结束时刻 减去 任务到达系统的时刻。
举例子来说明：我是一个快递员，有一个包裹到了我手里的时刻是T1，我最终完成送达的时刻是 T2，那么周转时间 就是 T2 - T1
一些调度追求的原则：
FIFO： 简单理解为先到先得，先到的任务先执行。例如有三个任务A, B, C 同时过来，完成的时间单位分别是10, 100, 1 ，它们的周转时间按照FIFO 原则，因为是同时，假定按照A，B，C顺序的处理，它们的周转时间分别是 10,110,111
平均周转时间为 (10 + 100 + 111) / 3 = 73.33
如果调换顺序，按照C A B的顺序处理，周转时间分别是
1, 11, 111
平均周转时间为 37. 几乎降低了一半。
这个例子启示我们，任务调度的周转时间和顺序密切相关。
为了节约周转时间，我们很容易想到的策略就是，短时任务优先处理。这样理论上，可以获得最短的周转时间（为什么？）
这就是最短任务优先原则 (SJF)
(Shortest Job First)
SJF 是一个贪心算法，它在某些情况下确实很好，做到了我们想要的。但是这都是基于我们预设的假设之上：
操作系统的工作任务都是在较短的时间内一起出现，并且它们的完成时间都是可知的。
如果长任务先到达，我们用FIFO的原则保证不了 SJF 长任务会占用很长的时间从而大大降低平均调度时间
继续SJF的原则，我们要把到达时间的预设放宽一点。如果某一时刻到达一个任务，评估其完成时间实行切换就好了。
比如 A B C三个任务分别在0,, 10, 30 时刻到达，完成需要100,10,1的时间单位
0 时刻 OS 选择A运行，10 时刻B 到达，切换到B运行，20时刻，B
完成，操作系统又切回到A，30时刻，C到达，操作系统切换到C，31时刻完成后，切回 A，这样计算其平均周转时间为
[图]
这就是STCF策略(Shortest Time-to-Completion First)
还有一种度量来自于用户需求，用户在终端面前，他关心的是一个操作是否得到及时的回应，如果他划一下手机没有看到系统给他任何反馈，比如这个划一下的操作被系统认定为一个优先级低的任务，那对于用户来说肯定会得到很糟糕的体验。
基于响应时间度量的调度
响应时间的度量定义：
任务响应时间 = 首次响应的时刻 - 任务抵达时刻
抵达时刻往往是应用程序的用户决定，那么响应时间决定于首次响应的时刻，这个时间当然是越快越好。
STCF的策略显然在这个度量上不太好，一个比较慢的任务总是被放到后面才处理，它的响应时间肯定是不太好的。
解决这个问题的一种想法是——轮转
大概的思想是，每个任务都能在短时间内获得机会，但是系统很快会切掉，反反复复，直到所有任务结束。可以想象轮转涉及了较多的上下文切换，switch的开销肯定比STCF这种调度要大得多。
这里工程关键在于选择一个合适的时间片，这段时间内运行一个工作，然后切换到下一个任务，这个时间片的选择，一般是时钟中断间隔的整数倍，其次它不能太小也不能太大。
太小会加剧切换上下文的代价；
太大会降低响应速度。
因此响应速度很难计算出理论的最小值——只有合适的比较小的值。
总结一下：
STCF是工作任务时长能够被准确度量并且系统追求整体的最短调度时间的情况下，它是一个最好的办法。
这个证明涉及到贪婪算法的一种剪贴技术。我们假设有其它的调度能获得更好的结果，然后，尝试推出矛盾。
如果关注响应速度，则轮转是一种方案。轮转会带来很不好的平均周转时间，甚至是最差的之一，但是可以获得很好的响应时间。
应对IO
以上的讨论没有考虑任务会进行IO的情况，或者将IO内化到时间表现上去了，但是，现实情况IO一般会发生进程切换。
发生IO的场景一般代表当前应用程序让出了CPU的使用权，这个时候系统最好做一点什么以提高CPU的利用率。所以在STCF的策略中，如果遇到长作业，并且带 IO，意味着有一段时间CPU空闲了，它陷进内核里面执行指令去了——从用户进程到内核陷阱指令是不是进程切换？
多级反馈算法(MLFQ)
多级反馈算法追求的是调度周转时间，但是在实际运行中，任务时间很难事先得知。
同时，MLFQ 也追求用户体验，它希望有一个比较好响应时间。
问题：没有完备的知识怎么调度？
预测。利用历史经验来预测未来。
也是的！毕竟陷入这个动作需要保存一些现场等待指令返回恢复现场，这个过程中，如果是一个单CPU，可以认为CPU还是很忙的
lmbench的使用
网友评论