处理器的管理是操作系统重要的核心组成部分。处理器的管理优劣直接影响系统性能，程序以进程的形式来占用处理器和系统资源，处理器以进程的形式来占用处理器和系统资源，处理器管理中最重要的是处理器调度，即进程调度，也就是控制、协调进程对处理器的竞争。

进程可被调度在一个处理器上交替执行，或者在多处理器上并行执行。为了提高并发粒度和降低并发开销，现代操作系统又引进了线程概念，此时进程仍然是资源分配和管理的单位，线程则成为处理器调度的基本单位。

处理器状态

处理器

指令系统（Instruction System）和寄存器（Register）

计算机的机器指令集合称为指令系统，反映计算机的功能和处理能力。一般处理器的机器指令集是专用的，指令往往分为数据处理、转移、传送、移位、字符串及I/O等六大类。

为实现指令功能，处理器中设置了一组寄存器用作寻址或存放数据、变量和中间结果，个数根据处理器型号不同而异。

特权指令（Privileged Instruction）和非特权指令

由于操作系统是系统资源的管理者和控制者，所以常常赋予系统程序较高的特权，可以使用全部的机器指令，而应用程序权限较低，只能使用指令系统子集（非特权指令）。在多用户、多任务的计算机系统中特权指令必不可少。

常见的特权指令有以下几种:

1. 有关对I/O设备使用的指令：如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。
2. 有关访问程序状态的指令：如对程序状态字（PSW）的指令等。
3. 存取特殊寄存器指令：如存取中断寄存器、时钟寄存器等指令。
4. 其他指令。

内核态（Kernel Mode）与用户态（User Mode）

用户态也称为『目态』，内核态也称为『管态』、『系统态』、『特权态』。

根据执行程序对资源和机器指令的使用权限将处理器设置成两个状态，且至少需要划分为这两种状态。CPU的状态属于程序状态字PSW的一位。

内核态：系统程序运行时所处的状态，可以认为是处理器在运行可信任的系统软件，此时全部机器指令都被允许在处理器上执行，程序可以访问所有内存单元和系统资源，并具有改变处理器状态的能力。

用户态：正在运行非可信任的应用程序，无法执行特权指令，且访问仅限当前处理器上执行程序所在的地址空间，这样就能防止操作系统程序受到应用程序的侵害。

在内核态执行的程序比用户态执行的程序拥有更多的权限去访问内存和执行特权指令，所以状态位被用来区分可信软件和非可信软件。对资源的需求、时间的紧迫和效率高低等因素决定了什么样的功能在内核态中实现。

说白了，凡是牵扯到计算机本体根本运行的事情都应该在内核态下执行，只与用户数据和应用相关的东西则放在用户态执行。另外，对时序要求特别高的事情，也应该在内核态做。

处理器状态及其转换

用户态向内核态转换的条件：

1. 程序请求操作系统服务，执行系统调用。
2. 程序运行时产生中断事件（I/O操作完成），运行程序被中断，转向中断处理程序处理。
3. 程序运行时产生异常事件（程序性中断、目态执行特权指令），运行程序被打断，转向异常处理程序。

上述三类情况都通过中断机制发生，中断和异常是用户态转换到内核态仅有的途径，从用户态转向内核太不存在类似指令或其他方法，否则任何进程都可以轻易转入特权状态。当系统中产生中断或异常，处理器将做出响应并交换程序状态字（PSW）。

内核态转到用户态的方法是通过加载程序状态字（Load Program Status Word）的特权指令，来实现内核态返回用户态，操作系统转交控制权。

用户栈和核心栈

进程有两个栈，用户栈和核心栈，硬件栈指针仅有一个，随着处理器状态转换进行改变。

用户栈是用户进程空间中开辟的一块区域，用于保存应用程序的子程序（函数）间相互调用的参数、返回值、返回点以及子程序的局部变量。

核心栈也称为系统栈、内核栈，是内存中属于操作系统空间的一块区域。用途是：

1. 保护现场，嵌套中断被中断程序的现场信息压栈，中断返回时弹出栈。
2. 保存操作系统程序（函数）间相互调用的参数、返回值、返回点和局部变量。

每个进程创建时捆绑一个核心栈，具有可读可写不可执行的属性。核心栈大小有限。

程序状态字

操作系统将程序运行时的一组动态信息汇集在一起，称为程序状态字（Program Status Word），并存放在处理器的一组特殊寄存器里，以方便系统的控制和管理。

PSW指示运行程序状态，控制指令执行顺序，并保留和指示与运行程序有关的各种信息，主要作用是实现程序状态的保护和恢复。每个程序都有一个PSW，每个处理器都设置一个硬件PSW寄存器，当程序占用处理器时，硬件PSW寄存器被程序PSW占用。不同处理器的特殊寄存器组织方式不同。

中断技术

概念

为了请求系统服务、实现并行工作、处理突发事件、满足实时要求，需要打断处理器的正常工作流，为此提出中断概念。

中断原因及中断源分类

由硬件发出或产生的中断称为硬中断，按硬中断事件的来源和实现手段可将中断划分为外中断和内中断。

外中断

外中断又称为中断或异步中断，是指来自处理器之外的中断信号。外中断可分为可屏蔽中断和不可屏蔽中断，各个中断具有不同中断优先级，表示时间的紧急程度，在处理高一级中断时往往会全部或部分屏蔽低级中断。

内中断

内中断又称异常（exception）或同步中断，是指来自处理器内部的中断信号，通常是由于在程序执行过程中，发现与当前指令关联的、不正常的或错误的事件。

内中断可细分为：

1. 访管中断，由执行系统调用而引起
2. 硬件故障中断，如电源失效、奇偶校验错误等
3. 程序性异常，如非法操作、地址越界等

内部中断不能被屏蔽，一旦出现应立即响应并进行处理。外部中断的屏蔽，根据异常处理的需要来设定。

最初只有外部中断，随着中断适用范围扩大，出现了内中断（异常）。但随着中断和异常的产生原因和处理方式逐渐地增大，中断和异常区分开来，区别如下：

1. 中断是由当前运行程序无关的中断信号触发的，系统无法确定中断事件的发生时间，中断与CPU是异步的，CPU对中断的响应完全是被动的。异常是由CPU控制单元产生的，源于现行程序执行指令过程中检测到例外，与CPU是同步的，允许指令在执行期间响应异常，而且允许多次响应异常，大部分发生在用户态，内核态唯一发生的异常是缺页异常。
2. 要求中断被快速处理，以便及时响应其他中断信号，所以中断处理程序过程中是不能阻塞的。异常处于被打断的当前进程上下文中，所提供的服务是当前进程所需要的，所以异常处理程序处理过程中可以阻塞。
3. 中断允许发生嵌套，但异常大多是单重的。异常处理过程中可能会产生中断，中断处理过程绝不会被异常打断。

中断和异常响应及服务

中断/异常响应需要顺序执行四个事件：

1. 发现中断源。中断未被屏蔽时，硬件发现中断/异常事件，由CPU响应中断/异常请求。发现多个中断源时，根据预定中断优先级先后响应中断请求。
2. 保护现场。暂停当前程序，硬件将PSW保存至核心栈，使中断/异常处理程序在运行时不会破坏被有用数据。
3. 转向中断/异常事件处理程序执行。处理器状态从用户态转为内核态，中断/异常处理程序开始工作。
4. 恢复现场。中断处理结束后，恢复PSW，返回中断点继续执行原程序。当异常处理结束后，返回点会因为异常类型而异，大部分应用程序指令执行出错时，异常处理会结束进程，不能回到原程序；如果执行访管指令，则异常处理完成后返回这条访管指令的下一条指令；对于页面故障，异常处理程序结束后会返回发生异常的那条指令重新执行。

中断事件处理原则

硬件故障中断

保护现场，停止设备工作，停止处理器运行，向操作员报告故障并对故障造成的破坏进行估计和恢复。

程序性中断

不同用户往往有不同的处理要求，借助于信号机制，操作系统可将所捕获的这类中断事件原封提供给应用程序自行处理。

I/O中断

I/O中断情况：

1. I/O操作正常结束：设置下一个等待传输的进程为就绪态，使其占用设备或通道，并启动数据传输。
2. I/O操作发生故障：先向设备发命令索取状态字，分析故障确切原因，再进行恢复或人工干预。
3. I/O操作发生异常：分析情况再操作。
4. 设备报到或设备结束：有新设备可用或老设备断开，系统修改相应数据。

访管中断

由于程序执行了访管指令，当前的程序对系统功能进行了调用，引起了访管中断。访管中断可以看做是机器指令的一种扩充。访管指令包括操作码和访管参数两部分，

时钟中断

时钟作为操作系统进行调度工作的重要工具，可用于维护系统日期时间、使分时进程按照时间片轮转、让实时进程定时发送接收控制信号、系统定时唤醒活阻塞进程等等，具体不表。

中断优先级和多重中断

中断优先级

中断是随机发生的。任何时间都有可能同时产生多个中断，对于多个中断的处理，就需要根据中断的紧迫程度来安排中断优先级，以这种方式来在一个时刻处理多个中断。

响应不同优先级中断的方式为硬件和软件方法。硬件链式排队器负责在高级中断事件发生时，屏蔽掉低级的中断源；软件查询程序根据优先级顺序进行顺序查询，一旦发现有中断请求便停止查询，并转入相应的中断事件处理程序。

中断屏蔽

计算机均配置可编程中断控制器，CPU可通过指令设置可编程中断控制器屏蔽码。中断屏蔽禁止CPU响应中断或禁止中断产生。

多重中断事件处理

同时产生多个中断，或前一个中断尚未处理又发生了新中断，CPU要暂停正在运行的中断处理程序，转而执行新的中断处理程序，称为多重中断或中断嵌套。

通常高优先级中断具有打断低优先级中断处理程序的权利。

处理多重中断通常有以下三个方式：

1. 串行处理：运行一个中断处理程序时屏蔽其他所有中断。
2. 嵌套处理：在低优先级中断处理程序运行时产生高优先级中断，此时保护低优先级中断处理程序现场，转向处理高优先级中断。
3. 即时处理：在运行中断处理程序时，立即对新的中断做处理。

进程及其实现

引入进程概念的目的：

1. 刻画程序的并发性。在多道程序环境下，程序并发执行，程序执行不是连续的而是走走停停的。同时程序并发执行会引发资源共享和竞争，造成各个程序之间存在制约关系。进程是并发程序设计的一种有力工具，操作系统中引入进程概念能较好地刻画系统内部程序的并发执行，提高系统利用率。
2. 解决资源的共享性。“可再入”程序概念：能够被多个程序同时调用的程序；“可再用”程序概念：在被调用过程中可以有自身修改，在调用它的程序退出之前不允许其他程序来调用。“可再入”程序只是纯代码，在执行过程中不被修改，调用它的各个应用程序提供工作区。所以”可再入“程序可同时被多个应用程序调用。

定义和属性

• 定义：具有独立功能的程序在某个数据集合上的一次运行活动，也是操作系统进行资源分配和保护的基本单位。

• 属性：
  1. 动态性。进程是程序在数据集合上的一次执行过程，是动态概念，同时具有生命周期，由创建而产生、由调度而执行，由事件而等待、由撤销而消亡。
  2. 共享性。同一程序同时运行于不同数据集合上构成不同进程。多个不同进程可执行相同程序。进程不与程序一一对应。
  3. 独立性。每个进程是操作系统中的一个独立实体，有自己的虚存空间、程序计数器和内部状态。
  4. 制约性。进程因共享资源或协同工作产生相互制约关系，造成进程执行速度的不可预测性，必须对进程的执行次序或相对执行速度加以协调。
  5. 并发性。多个进程的执行在时间上可以重叠，在单处理器系统中可以并发执行；在多处理环境中可以并发执行。因此进程执行可以被打断，或者说可能会在某条指令执行结束被迫让出处理器。

进程状态和转换

三态模型

为了便于系统管理，按照进程在执行过程中的不同情况至少要定义三个状态：

1. 运行态：进程占有处理器正在运行的状态。
2. 就绪态：进程具备运行条件，等待系统分配处理器以便运行的状态。
3. 等待态：又称阻塞态或睡眠态，进程不具备运行条件，正在等待某个事件完成的状态。

处于运行态的进程个数不能大于处理器个数，处于就绪态和等待态的进程可有多个。通常情况下，进程被创建后处于就绪态。

七态模型

很多系统中增加了新建态和终止态。

除此之外，可能有这样一种情况，由于不断创建进程，当系统资源尤其是是内存资源已经不能满足进程运行的要求时，必须要把某些进程挂起（suspend），对换到磁盘兑换区中，释放它占有的某些资源。除了内存不足，也可能因为系统出现故障、用户需要等等原因导致进程挂起。

具有七种状态的示意图如下，两个新的状态位挂起就绪态和挂起等待态。不同的操作系统，对状态的设置有所不同。

进程的描述和组成

进程映像

由于进程状态在不断发生变化，某时刻进程的内容及其状态集合成为进程映像（process image），包括：进程控制块、进程程序快、进程核心栈、进程数据块。

进程控制块

每个进程有且只有一个进程控制块（Process Control Block, PCB），也称进程描述符，是操作系统用来记录和刻画进程状态及环境信息的数据结构，是进程动态特征的汇集，是操作系统掌握进程的唯一资料结构和管理依据。通常包含以下信息：标识信息、现场信息、控制信息等。

进程队列及其管理

并发系统中同时存在很多进程，通常情况下，把相同状态的所有进程PCB连接在一起的数据结构称为进程队列，方式有：链接方式和索引方式两种。

进程上下文切换与处理器状态转换

上下文切换

多任务系统中，上下文切换是指CPU的控制权由运行任务，转移到另外一个就绪任务时所发生的事件。进程切换必定在内核态而非用户态发生。

CPU切换到另一个进程需要保存当前进程的状态并恢复另一个进程的状态：当前运行任务转为就绪（或者挂起、删除）状态，另一个被选定的就绪任务成为当前任务。上下文切换包括保存当前任务的运行环境，恢复将要运行任务的运行环境。

上下文切换时机

由于种种情况，如在中断处理程序运行期间发生一个更高优先级的I/O中断等，会导致发生重新调度事件、执行调度程序和进程上下文切换工作不能连续进行。所以上下文切换时机是比较讲究的。在此不细说了。

处理器状态转换

与进程上下文切换有关的是用户态和内核态之间的处理器状态转换，此时仍然在同一个进程中运行。当发生中断、系统调用时暂停正在运行的进程，处理器从用户态转为内核态，执行操作系统命令，这就是一次状态转换，此时的进程仍然在自己的上下文执行，只处理器状态变化。

过程大致为：保存现场、处理器状态转换、若处理中断则设置中断屏蔽、根据系统调用号和中断号找到系统服务程序或中断处理程序地址。

进程控制和管理

对进程的控制和管理均由原语实现。

线程及其实现

引入多线程的目的

目的：为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。

思路：把进程的“独立分配资源”和“被调度分派执行”两项功能分离开。独立分配资源仍然有进程完成，作为系统资源分配和保护的陆地烂尾，无需频繁切换。后一项任务交给称为“线程”的实体来完成，线程作为系统调度和分派的基本单位，会频繁地调度和切换。

优点：

1. 快速线程切换。同一进程中的多线程切换只需改变堆栈和寄存器，地址空间不变。
2. 通信易于实现。自动共享进程的内存和文件，线程可以自由访问全局数据，实现数据共享十分方便，线程通信相对简单不必经过内核。
3. 减少管理开销。线程创建和撤销工作比进程少很多，而且无需再分配存储空间和各种资源。
4. 并发程度提高。多线程适宜并行工作，能充分发挥处理器与设备的并行工作能力，使多核和多处理器系统的效能发挥得更好。

多线程环境中的进程与线程

多线程

无论是单线程环境还是多线程环境，线程在操作系统中均可定义为：操作系统中除处理器以外的资源分配和保护的基本单位。拥有一个独立的虚拟地址空间容纳进程映像，并以进程为单位对各种资源实施保护。

线程是进程中能够并发执行的实体，是进程的组成部分，也是处理器调度和分派的基本单位，一个进程可以同时包含多个线程，这些线程共享进程所获得的内存空间和资源，可以为完成某一项任务而协同工作。

县城组成部分由线程唯一标识符、线程状态信息（运行态、就绪态、阻塞态、终止态）。线程是一条执行路径，有独立的程序计数器，未运行时保护线程上下文。线程拥有执行栈和存放局部变量的私有存储空间。可以访问所属进程的内存和和资源，并与该进程中其他线程共享这些资源。

线程状态

由于线程并不是资源的拥有单位，挂起状态对于线程是没有意义的。如果进程在挂起后背对换出内存，他的所有线程因共享地址空间也必须全部对换出内存，挂起操作是进程级的，而不是线程级的。同样，进程的终止将导致该进程的所有线程终止。

线程组织

一个进程可以包含若干线程，这些线程可以有多种组织方式：调度员－工作者模式、组模式、流水线模式等。

线程的实现

多线程实现分为内核级线程（Kernel Level Thread）、用户级线程（User Level Thread）两种，有些系统提供混合式线程。

内核级线程

线程的管理工作由内核完成，并提供线程API来使用线程。

优点：多处理器上内核能够同时调度同一进程中的多线程并行执行；一个线程被阻塞，内核能够调度同一进程的其他线程占有处理器运行，也可以运行其他进程中的线程；由于内核级线程只有很小的数据结构和堆栈，切换速度快，内核自身也可以用多线程技术实现，从而提高了系统执行效率。

缺点：线程在用户态运行，线程调度和管理在内核实现，在同一进程中控制权从一个线程传送到另一个线程时需要用户态－内核态－用户态模式转换，系统开销大。

用户级线程

线程的管理工作由应用程序来做，在用户空间内实现，内核不知道线程的存在。

优点：线程切换无需使用内核特权方式，所有线程管理的数据结构均在用户空间中，可以节省模式转换开销和内核的宝贵资源来；允许进程按照应用的特定需要选择调度算法，且可以执行在任何操作系统上，内核无需改变。

缺点：由于大多数系统调用时阻塞型的，因此一个用户级线程的阻塞将引起整个进程阻塞；用户级线程不能利用多重处理的优点，进程由内核分配到CPU上，仅有一个用户级线程可以执行，不能得益于多线程的并发执行。

混合式线程

Solaris就是一个既支持内核级线程又支持用户级线程的操作系统，线程的实现分为两个层次，用户层和核心层。

线程调度

当若干进程都有多线程时，就存在两个层次并行：进程和线程。

对于用户级线程，内核并不知道线程的存在，所以操作系统调度程序以进程为单位进行调度。对于内核级线程，操作系统会选择一个优先级高的线程运行，不用考虑该线程属于哪个进程，赋予这个线程一个时间片，超时会强制阻塞该线程。

用户级线程和内核级线程之间的差别在于性能。

处理器调度

处理器调度层次

高级调度

在多道批处理操作系统中，从输入系统的一批作业中按照预定的调度策略挑选若干作业进入内存，为其分配所需资源，并创建对应作业的用户进程后，便完成启动阶段的高级调度任务，已经为进程做好运行前的额额准备工作（具备参与CPU竞争资格）。等待进程被调度运行，在作业完成后还要做结束阶段的善后工作。

高级调度宏观上控制多道程序道数，被选择进入内存的作业越多，每个作业获得的CPU时间就越少。

中级调度

根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存中的进程对换工作。当内存资源紧缺，会把暂时不能运行的进程对换出内存，此进程处于挂起状态，不参与低级调度。当进程具备运行条件且内存资源富裕时，再将进程重新调回内存工作，起到短期均衡系统负载的作用，充分提高内存利用率和系统吞吐率。

低级调度

根据某种原则决定就绪队列中哪个进程或线程获得处理器，并将处理器出让给它使用。

低级调度是操作系统最核心的部分，执行十分频繁，调度策略优劣直接影响系统性能。

选择调度算法的原则

选择调度算法的基本原则是计算机系统性能尽可能好。下面列出5条选择调度算法原则中，前三条面向系统的性能指标，后两条面向用户的性能指标。

1. 资源利用率：让CPU和各种资源尽可能并行工作，使得资源利用率尽可能高。CPU利用率=CPU有效工作时间/CPU总的运行时间
2. 吞吐率：单位时间内CPU处理作业的个数，显然，所处理的长作业多则吞吐率低，所处理短作业多则吞吐率高。
3. 公平性：确保每个进程都能获得合理的CPU份额和其他资源份额，不会出现饥饿现象。
4. 响应时间：交互式用户的响应时间尽可能短或尽快处理实时任务。
5. 周转时间：作业周转时间或平均作业周转时间尽可能短。

批处理系统的调度性能用作业周转时间和带全作业周转时间来衡量，时间越短，系统效率越高，作业吞吐率越高。如果作业i提交给系统的时刻是ts，完成时刻tf，那么作业i的周转时间t为t=tf-ts

通常平均作业周转时间用来衡量不同调度算法对同一作业流的调度性能，平均带权作业周转时间用来衡量同一调度算法对不同作业流的调度性能，这两个数值都是越小越好。

作业管理与调度

作业与进程的关系

作业是用户提交给操作系统计算的一个独立任务。作业是任务实体，进程是完成任务的执行实体；没有作业任务，进程无事可做；没有进程作业任务无法完成。作业的概念更多地用于批处理操作系统中，而进程则用于各种多道程序设计系统。

作业管理与调度

作业可以分为批处理作业和交互型作业。

// TODO: 展开说明

低级调度功能和类型

低级调度功能

调度程序担负两项任务：调度和分派。调度实现调度策略，确定就绪态进程/线程竞争使用处理器的次序的裁决原则；分派实现调度机制，确定如何时分服用CPU，处理上下文切换，完成进程和线程同CPU的绑定和放弃的实际工作。

低级调度用途

正在执行的进程/线程运行结束或由于某事件无法继续运行，出现更高优先级的线程/进程，需剥夺当前进程/线程使用CPU等。

创建进程/线程，进程/线程终止，进程/线程阻塞，进程/线程运行中中断异常，进程/线程执行系统调用，进程/线程请求I/O操作完成，进程/线程耗尽时间片，进程/线程改变优先级等操作后，均需要低级调度。

低级调度类型

由于调度程序自身开销及内存磁盘对换程序与数据开销，剥夺式策略比非剥夺式策略开销大。大多数操作系统采用两方法混合策略。

剥夺式调度

又称抢占式调度，根据规定原则剥夺分配给此线程的处理器，并移入就绪队列。高优先级进程/线程可剥夺低优先级的；在动态改变优先级的系统中，当进程/线程时间片用完后也会被剥夺。

非剥夺式调度

又称非抢占式调度，一旦某进程/线程开始运行后，便不再让出处理器，除非该进程/线程主动放弃处理器，或因某事件不能继续执行。

作业调度和低级调度算法

多数调度算法对两种调度都适用。

FCFS先来先服务

First Come First Served，按照作业进入系统后备作业队列的先后次序挑选作业，先进入系统的作业先进入内存，创建用户进程，分配资源，进入就绪队列。非剥夺式算法，易于实现，效率不高。未考虑作业要求服务时间长度昂，不利于段作业，不利于I/O繁忙型作业，有利于CPU繁忙型作业。

该算法适用于进程/线程调度，每次从就绪队列中选择最先进入的进程/线程。

假设存在以下三个作业：

作业名	所需CPU时间/ms
作业1	28
作业2	9
作业3	3

采用FCFS调度算法，若按照1、2、3的顺序进入系统队列，那么平均作业周转时间T=(28+(28+9)+(28+9+3))/3=35ms，如果我们把作业进入系统顺序改为3、2、1，那么平均作业周转时间就为T=(3+(3+9)+(3+9+28))/3=18ms，所以该算法的平均作业周转时间与作业提交、调度的顺序有关。

SJF最短作业优先

Shortest Job First，已进入系统作业所要求的CPU时间长短为标准，总是选取预计计算时间最短的作业运行，非剥夺式算法，能克服FCFS的偏爱长作业缺点，易于实现，效率不高。缺点：先要与之作业所需CPU时间，难以估算准确，估值过低会提前终止；忽视作业等待时间，若系统不断接收新作业，系统总会选择最短作业运行，导致长作业时间作业一直等待，发生饥饿现象；由于缺少剥夺机制，对分时、实时处理不理想。

假设存在以下四个作业：

作业名	所需CPU时间/ms
作业1	9
作业2	4
作业3	10
作业4	8

采用SJF调度算法，作业调度顺序是2、4、1、3，那么平均作业周转时间T=(4+(4+8)+(4+8+9)+(4+8+9+10))/4=68/17ms，平均带权作业周转时间W=(4/4+(4+8)/8+(4+8+9)/9+(4+8+9+10)/10)/4=1.98。

若采用FCFS算法，作业调度顺序是1、2、3、4，平均作业周转时间T=(9+(9+4)+(9+4+10)+(9+4+10+8))/4=19ms，平均带权作业周转时间W=(9/9+(9+4)/4+(9+4+10)/10+(9+4+10+8)/8)/4=2.61ms。

所以SJF相较FCFS的性能要好，但实现SJF需要预先知道作业运行时间。在两个作业所需CPU时间相同的情况下，对这两个作业采用FCFS。

SRTF最短剩余时间优先

在SJF的基础上，改造为剥夺式调度算法，即成Shortest Remaining Time First，每执行一次，选择一次剩余时间最短的作业执行。

假设存在以下四个进程：

进程名	到达时间	所需CPU时间/ms
p1	0	8
p2	1	4
p3	2	9
p4	3	5

用SRTF，在0时刻，p1到达，执行一次后p1所需时间变为7，此时p2到达，选择p2执行，执行一次后p2所需时间变为3，此时p3到达，那么就在p1的7、p2的3和p3的9中选择最小CPU时间的进程执行，那么还是执行p2，执行一次后p4到达，那么现在就在p1的7、p2的2、p3的9和p4的5中选择最小CPU时间的进程执行。

将执行过程列举如下：p1执行1次，p2执行4次到结束，p4执行5次到结束，p1执行7次到结束，p3执行9次到结束。

// TODO: 平均等待时间和平均周转时间

HRRF最高响应比优先

FCFS和SJF都比较片面，HRRF介于这两种算法之间的这种非剥夺式算法，既考虑作业等待时间，又考虑作业处理时间。缺点是没次计算各作业响应比会占用一定时间开销，性能略差于SJF，等待时间和处理时间之和是系统对作业的响应时间，它于处理时间的比值称为响应比：

响应比=作业周转时间/作业处理时间=(作业等待时间+作业处理时间)/作业处理时间=1+作业等待时间/作业处理时间。

作业处理时间是用户给出常量，作业等待时间从0开始，随作业在后备队列中等待时间增长而变长，当调度作业运行时，计算后备作业队列的各作业响应比作为优先级，再投入最高优先级的执行。

短作业易获得高响应比，随着长作业在系统中等待时间变长，其优先级提高，不会发生饥饿现象。

假设存在以下四个作业：

作业名	到达时间	所需CPU时间/ms
作业1	0	20
作业2	5	15
作业3	10	5
作业4	15	10

采用HRRF，执行过程为：

时间	执行
0-20	执行作业1，之后2等15ms，3等10ms，4等5ms
21-25	执行作业3，之后2等20ms，4等10ms
26-40	执行作业2，之后4等25ms
41-50	执行作业4

平均作业周转时间T=(20+(40-5)+(25-10)+(50-15))/4=26.25，平均带权作业周转时间W=(20/20+35/15+15/5+35/10)/4=2.46。由此可见，HRRF性能介于SJF和FCFS之间，HRRF同样可用于进程调度，响应比定义为1+进程等待时间/进程预计计算时间。

优先级调度

该算法根据确定的优先级来选取进程/线程执行，总执行就绪队列优先级最高者。需要预先规定非剥夺式或剥夺式。

RR轮转调度

Round-Robin也称时间片调度，调度程序没次把CPU分配给就绪队列首进程/线程使用规定时间片（时间间隔），就绪队列中每个进程/线程运行一个时间片，执行完一个时间片就出队再进队尾。是剥夺式算法。

MLFQ多级反馈队列调度

Multi-Level Feedback Queue又称反馈循环队列，由系统建立多个就绪队列，每个队列对应一个优先级，第一队列优先级最高，其余队列优先级依次降低，高优先级队列的进程/线程分配较短时间片，低优先级队列分配较长时间片，最后一个队列按照FCFS进行调度，处理器调度每次先从第一个队列中选取执行者，同一队列按照FCFS排队执行。若第一队列未选到执行者， 那么从第二队列中选取。

MLFQ性能较好，会导致饥饿问题。