1. 进程和程序
1.1概念
程序放入CPU准备运行，称其为进程，若程序放在硬盘上，称其为程序。
进程：从操作系统的角度来看，进程使系统分配资源的基本单位，也是系统分配资源的最小单位。进程=数据段+代码段+堆栈+PCB（Process Control Block，进程控制块），PCB可以将数据段、代码段和堆栈结合起来。
程序：数据段+代码段
PCB结构：进程控制块是进程存在的唯一的标记，PCB是一个数据结构。记录进程的全部信息（进程名，标识符等信息）。PCB通过指针指向数据段和代码段。
代码段：记录进程的代码。
数据段：进程的数据。
进程控制块
一个进程只有一个PCB，PCB是进程存在与否的唯一标记。
描述信息：进程名字，标识符（PID），用户组号和用户号反映进程家族关系。
管理信息：管理进程的状态、优先级（为调度所用）、正文段、数据段。
资源清单：包括主存量，外设，优先级等
现场保护区：保护进程的上下文。
其他：包含一些其他信息（例如指向下一个PCB链接指针）。
进程与程序的区别：
1）进程是动态的，程序是静态的；
2）进程生命周期短暂，程序相对永久；
3）一个进程只能对应一个程序，一个程序可以对应多个进程；
4）进程有PCB。
进程具有以下特性：动态性，并发性，独立性（系统中独立存在的实体）。动态性和并发性使进程具有同步、互斥和死锁功能。独立性体现在一个程序可以对应多个进程，但一个进程只能对应一个程序。
1.2 进程的状态和转换
1.2.1 三态模式
一个进程从创建而产生至撤销而消亡的整个生命周期，可以用一组状态加以刻画，根据三态模型，进程的生命周期可以分为如下三种进程状态：
1）就绪态(ready)：具备运行条件，等待系统分配处理器以便运行。
2）运行态(running)：占有处理器正在运行。
3）阻塞态(blocked)：不具备运行条件，正在等待某个事件的完成。
三个状态的转换图如下：
运行状态的进程将由于出现外部事件进入阻塞状态，当外部事件结束以后，阻塞状态的进程将进入就绪状态，而处理器的调度策略优惠引起就绪状态向运行状态切换。
引起进程状态转换的原因如下：
- 运行态——>阻塞态：等待使用资源；如等待外设传输、人工干预。
- 阻塞态——>就绪态：资源得到满足；如外设传输结束、人工干预完成。
- 运行态——>就绪态：运行时间片到或出现有更高优先权的进程。
- 就绪态——>运行态：CPU空闲时选择一个就绪进程。
以下两种状态是不可能发生的：
阻塞——>运行：即使给阻塞进程分配CPU，也无法执行，操作系统在进行调度时不会从阻塞队列进行挑选，而是从就绪队列中选取；
就绪——>阻塞：就绪态根本就没有执行，谈不上进入阻塞态。
1.2.2 五态模式
在一个实际的系统里进程的状态及其转换比上节叙述的会复杂一些，例如引入专门的新建态和终止态。
状态转换图如下所示：
新建态对应于进程刚刚被创建的状态，创建一个进程要通过两个步骤：
1）为一个新进程创建必要的管理信息；
2）让该进程进入就绪态。此时进程将处于新建态，它并没有被提交执行，而是等待操作系统完成创建进程的必要操作。需要注意的是，操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交。
进程的终止也要通过两个步骤，首先，等待操作系统进行善后，然后，推出主存。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止态。进入终止态的进程以后不再执行，但依然临时保留在操作系统中等待善后。一旦其他进程完成了对终止态进程的信息抽取之后，操作系统将删除该进程。
引起进程状态转换的原因：
- NULL——>新建态：执行一个程序，创建子进程。
- 新建态——>就绪态：当操作系统完成了进程创建的必要操作，并且当前系统的性能和虚拟内存的容量均允许。
- 运行态——>终止态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程终结。
- 终止态——>NULL：完成善后操作。
- 就绪态——>终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。
- 等待态——>终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。
1.2.3 七态
在一些系统中，又增加了一些新状态：
浅度睡眠状态：进程正在睡眠（被阻塞），等待资源的到来是唤醒，也可以通过其他进程信号或时钟中断唤醒，进入运行队列。Linux 中使用TASK_INTERRUPTIBLE 宏表示此状态。
深度睡眠状态：其和浅度睡眠基本类似，但不可被其他进程信号或时钟中断唤醒。Linux 中使用TASK_UNINTERRUPTIBLE 宏表示此状态。
暂停状态：进程暂停执行接受某种处理。Linux 使用TASK_STOPPED 宏表示此状态。
僵尸状态：进程已经结束但未释放进程控制块（PCB），Linux 使用TASK_ZOMBIE 宏表示此状态。
挂起状态
挂起状态：在执行状态的进程通过挂起即可进入就绪状态，就绪状态和阻塞状态都分为活动态和静止态。由活动态向静止态转换就是通过挂起实现的。
挂起分为：
挂起就绪态（ready,suspend）：挂起就绪态表明了进程具备运行条件但目前在二级存储器中，只有当它被对换到主存才能被调度执行
挂起等待态（blocked,suspend）：挂起等待态则表明了进程正在等待某一个事件且在二级存储器中。
引入挂起状态的原因有：
(1) 终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂时使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态称为挂起状态。
(2) 父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。
(3) 负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。
(4) 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。
具有挂起状态的进程状态转换图为：
2. 进程的调度算法.
2.1 进程调度的概念：需要进程调度的理由，即充分利用计算机系统中的CPU资源，让计算机系统能够多快好省地完成我们让它做的各种任务。为此，可在内存中存放数目远大于计算机系统内CPU个数的进程，让这些进程在操作系统的进程调度器的调度下，能够让进程高效（高的吞吐量–throughput）、及时（低延迟–latency）、公平地使用CPU。为此调度器可设计不同的调度算法来选择进程，这体现了进程调度的策略，同时还需并进一步通过进程的上下文切换（context switch）来完成进程切换，这体现了进程调度的机制。总体上说，我们需要了解何时调度（调度的时机）、是否能够在内核执行的任意位置进行调度（调度的方式）、如何完成进程切换（上下文切换）、如何选择“合适”的进程执行（调度策略/调度算法）、如何评价选择的合理性（进程调度的指标）。
2.2 进程调度的指标
不同的进程调度算法具有不同的特征，为此需要建立衡量一个算法的基本指标。进程调度算法性能的指标如下：
- CPU利用率：CPU是计算机系统中的稀缺资源，所以应在有具体任务的情况下尽可能使CPU保持忙，从而使得CPU资源利用率最高。
- 吞吐量：CPU运行时的工作量大小是以每单位时间所完成的进程数目来描述的，即称为吞吐量。
- 周转时间：指从进程创建到作进程结束所经过的时间，这期间包括了由于各种因素（比如等待I/O操作完成）导致的进程阻塞，处于就绪态并在就绪队列中排队，在处理机上运行所花时间的总和。
- 等待时间：即进程在就绪队列中等待所花的时间总和。因此衡量一个调度算法的简单方法就是统计进程在就绪队列上的等待时间。
- 响应时间：指从事件（比如产生了一次时钟中断事件）产生到进程或系统作出响应所经过的时间。在交互式桌面计算机系统中，用户希望响应时间越快越好，但这常常要以牺牲吞吐量为代价。
这些指标其实是相互有冲突的，响应时间短也就意味着在相关事件产生后，操作系统需要迅速进行进程切换，让对应的进程尽快响应产生的事件，从而导致进程调度与切换的开销增大，这会降低系统的吞吐量。
2.3进程调度的时机
进程调度发生的时机（也称为调度点）与进程的状态变化有直接的关系。回顾进程状态变化图，我们可以看到进程调度的时机直接与进程在运行态<–>退出态/就绪态/阻塞态的转变时机相关。简而言之，引起进程调度的时机可归结为以下几类：
- 正在执行的进程执行完毕，需要选择新的就绪进程执行。
- 正在执行的进程调用相关系统调用（包括与I/O操作，同步互斥操作等相关的系统调用）导致需等待某事件发生或等待资源可用，从而将白己阻塞起来进入阻塞状态。
- 正在执行的进程主动调用放弃CPU的系统调用，导致自己的状态为就绪态，且把自己重新放到就绪队列中。
- 等待事件发生或资源可用的进程等待队列，从而导致进程从阻塞态回到就绪态，并可参与到调度中。
- 正在执行的进程的时间片已经用完，导致自己的状态为就绪态，且把自己重新放到就绪队列中。
- 在执行完系统调用后准备返回用户进程前的时刻，可调度选择一新用户进程执行
- 就绪队列中某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。
2.4进程调度的方式
这里需要注意，存在两种进程抢占处理器的调度方式：
可抢占式（可剥夺式，preemptive)：就绪队列中一旦有某进程的优先级高于当前正在执行的进程的优先级时，操作系统便立即进行进程调度，完成进程切换。
不可抢占式（不可剥夺式non_preemptive）：即使在就绪队列存在有某进程优先级高于当前正在执行的进程的优先级时，当前进程仍将占用处理机执行，直到该进程自己进入阻塞状态，或时间片用完，或在执行完系统调用后准备返回用户进程前的时刻，才重新发生调度让出处理机。
显然，可抢占式调度可有效减少等待时间和响应时间，但会带来较大的其他管理开销，使得吞吐量等的性能指标比不可抢占式调度要低。所以一般在桌面计算机中都支持可抢占式调度，使得用户可以得到更好的人机交互体验，而在服务器领域不必非要可抢占式调度，而通常会采用不可抢占式调度，从而可提高系统的整体吞吐量
2.5 进程调度的算法
对于操作系统的周转时间，我们有以下定义：
1> 作业周转时间：作业完成时间-作业提交时间
2> 带权周转时间=周转时间/服务时间
3>平均周转时间=作业周转总时间/作业个数
4>平均带权周转时间=带权周转总时间/作业个数
1）先来先服务 （FCFS，first come first served）
在所有调度算法中，最简单的是非抢占式的FCFS算法。
算法原理：进程按照它们请求CPU的顺序使用CPU.谁第一个排，谁就先被执行，在它执行的过程中，不会中断它。当其他人也想进入内存被执行，就要排队等着，如果在执行过程中出现一些事，他现在不想排队了，下一个排队的就补上。此时如果他又想排队了，只能站到队尾去。
算法优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平
算法缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。有时为了等待场作业的执行，使短作业的周转时间变大，从而使平均周转时间也变大。
例：
| 作业名 | 所需CPU时间 |
|---|---|
| 作业1 | 28 |
| 作业2 | 9 |
| 作业3 | 3 |
按照1->2->3的顺序所需总时间为 (28+37+40)/3 = 35 ,如果按作业3->2->1进行，所需时间为(3+12+40)/3 ~= 18.3,FCFS 调度算法的平均作业周转时间与作业提交的顺序有关
2）最短作业优先（SJF, Shortest Job First）
短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
算法原理：对预计执行时间短的进程优先分派处理机。通常后来的短进程不抢先正在执行的进程。
算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。
例：以下4个作业同时到达系统并立即进入调度：
| 作业名 | 所需CPU时间 |
|---|---|
| 作业1 | 9 |
| 作业2 | 4 |
| 作业3 | 10 |
| 作业4 | 8 |
根据SJF调度算法，调度顺序为2、4、1、3，
平均作业周转时间 T = (4+12+21+31)/4 = 17
平均带权作业周转时间 W = (4/4+12/8+21/9+31/10)/4 = 1.98
根据FCFS调度算法：
平均作业周转时间 T = (9+13+23+31)/4 = 19
均带权作业周转时间 W = (9/9+13/4+23/10+31/8)/4 = 2.51
SJF 的平均作业周转时间比 FCFS 要小，故它的调度性能比 FCFS 好。但实现 SJF 调度算法需要知道作业所需运行时间，否则调度就没有依据，作业运行时间只知道估计值，要精确知道一个作业的运行时间是办不到的。
SJF 算法既可以是非抢占式的，也可以是抢占式的。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的 CPU 时间比当前正在执行的作业剩余下来还需的 CPU 时间短，抡占式短作业优先算法强行赶走当前正在执行作业,这种方式也叫最短剩余时间优先算法(Shortest Remaining Time First)算法。此算法不但适用于 JOB 调度，同样也适用于进程调度
例：
| 作业名 | 到达系统时间 | CPU时间 |
|---|---|---|
| 作业1 | 0 | 8 |
| 作业2 | 1 | 4 |
| 作业3 | 2 | 9 |
| 作业4 | 3 | 5 |
作业1 从 0 开始执行，这时系统就绪队列仅有一个作业。作业2 在时间 1 到达，而 作业1的剩余时间(7毫秒)大于 作业2 所需时间(4 毫秒),所以,作业1 被剥夺,作业2被调度执行。这个例子的平均等待时间是((（1+4+5）-1)+(1-1)+(（1+4+5+7）-2)+(（1+4）-3))/4=26/4=6.5 毫秒。如果采用非抢占式 SJF 调度，那么（0+（8-1）+（8+4-2）+（8+4+9-3））/4=8.75，平均等待时间是 8.75 毫秒
3）最高响应比优先法(HRRN，Highest Response Ratio Next)
最高响应比优先法(HRRN，Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。
算法原理：响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。
算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。
算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。
例：
| 作业名 | 到达系统时间 | CPU时间 |
|---|---|---|
| 作业1 | 0 | 20 |
| 作业2 | 5 | 15 |
| 作业3 | 10 | 5 |
| 作业4 | 15 | 10 |
假设系统中没有其他作业，现对它们实施 SJF 调度算法(非抢占)，这时的作业调度顺序为作业 1、3、4、2
平均作业周转时间 T = (20 + （20+5-10） + （20+5+10-15） + （20+5+10+15-5))/4 = 25
平均带权作业周转时间 W = (20/20+15/5+25/10+45/15)/4 = 2.25
如果对它们施行 FCFS 调度算法，
平均作业周转时间 T = (20+(35-5)+(20+15+5-10)+(20+15+5+10-15))/4 = 38.75
平均带权作业周转时间 W = (20/20+30/15+30/5+35/10)/4 = 3.13
如果对这个作业流执行 HRN 调度算法，
开始时只有作业 1，作业 1 被选中，执行时间 20；
作业 1 执行完毕后，响应比依次为 (20-5)/15、(20-10)/5、(20-15)/10，作业 3 被选中，执行时间 5；
作业 3 执行完毕后，响应比依次为 (25-5)/15、(25-15)/10，作业 2 被选中，执行时间 15；
作业 2 执行完毕后，作业 4 被选中，执行时间 10；
平均作业周转时间 T = (20+（20-10+5）+（25-5+15）+（20+5+15-15+10）)/4 = 26.25
平均带权作业周转时间 W = (20/20+15/5+35/15+35/10)/4 = 2.42
4）时间片轮转算法（RR，Round-Robin）
该算法采用剥夺策略。时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称RR调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
算法原理：让就绪进程以FCFS 的方式按时间片轮流使用CPU 的调度方式，即将系统中所有的就绪进程按照FCFS 原则，排成一个队列，每次调度时将CPU 分派给队首进程，让其执行一个时间片，时间片的长度从几个ms 到几百ms。在一个时间片结束时，发生时钟中断，调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程，进程可以未使用完一个时间片，就出让CPU（如阻塞）。（ 当正在运行的进程用完了时间片后，即使此进程还要运行，操作系统也不让它继续运行，而是从就绪队列依次选择下一个处于就绪态的进程执行，而被剥夺CPU使用的进程返回到就绪队列的末尾，等待再次被调度。时间片的大小可调整，如果时间片大到让一个进程足以完成其全部工作，这种算法就退化为FCFS调度算法；若时间片设置得很小，那么处理机在进程之间的进程上下文切换工作过于频繁，使得真正用于运行用户程序的时间减少。时间片可以静态设置好，也可根据系统当前负载状况和运行情况动态调整，时间片大小的动态调整需要考虑就绪态进程个数、进程上下文切换开销、系统吞吐量、系统响应时间等多方面因素。）
算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当
怎样确定时间片的大小：
时间片大小的确定
1.系统对响应时间的要求
2.就绪队列中进程的数目
3.系统的处理能力
5）多级反馈队列(Multilevel Feedback Queue)
多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
多级反馈队列调度算法描述：
1>进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2>首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
3>对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
4>在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。
在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能够较好的满足各种类型用户的需要。MLFQ调度算法可以看出长进程无法长期占用处理机，且系统的响应时间会缩短，吞吐量也不错（前提是没有频繁的短进程）。所以MLFQ调度算法是一种合适不同类型应用特征的综合进程调度算法。
操作系统中为了能够让每个进程都有机会运行，需要给每个进程分配一个时间片，当一个进程的时间片用完以后，操作系统的调度器就会让当前进程放弃CPU，而选择另外一个进程占用CPU执行。为了有效地支持进程调度所需的时间片，ucore设计并实现了一个timer（计时器）功能。这样，通过timer就对基于时间事件的调度机制提供了基本支持。