操作系统第二章进程与线程

🚥操作系统系列文章导航🚥

操作系统第一章计算机系统概述
操作系统第二章进程与线程

一、进程与线程

1.进程的概念与特征

程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
进程（Process）：是动态的，是程序的一次执行过程（同一个程序多次执行会对应多个进程）。

注意：一个进程可以执行一个或几个程序，一个程序也可构成多个进程。

相比于程序，进程拥有以下特征：

动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的。动态性是进程最基本的特征。
并发性：内存中有多个进程实体，各进程可并发执行。
独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供 “进程同步机制” 来解决异步问题。
结构性：每个进程都会配置一个 PCB。结构上看，进程由程序段、数据段、PCB 组成。

2.进程的组成

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位。它由进程控制块（PCB）、程序段、数据段三部分组成。其中最核心的部分是 PCB，它是进程实体的一部分，是进程存在的唯一标志。

PCB 是给操作系统用的数据结构；程序段、数据段是给进程自己用的，与进程自身的运行逻辑有关。

（1）进程控制块

PCB 主要包括以下几部分内容：

进程描述信息：进程被创建时，操作系统会为该进程分配一个唯一的、不重复的 PID；UID 用于标识进程所归属的用户，为共享和保护服务。
进程控制和管理信息
资源分配清单：
处理机相关信息：也称 CPU 上下文，主要指 CPU 中各寄存器的值。用于实现进程切换。

进程描述信息	进程控制和管理信息	资源分配清单	处理机相关信息
进程标识符（PID）	进程当前状态	代码段指针	通用寄存器值
用户标识符（UID）	进程优先级	数据段指针	地址寄存器值
	代码运行入口地址	堆栈段指针	控制寄存器值
	程序的外存地址	文件描述符	标志寄存器值
	进入内存时间	键盘	状态字
	CPU 占用时间	鼠标
	信号量使用

（2）程序段：能够被进程调度程序调度到 CPU 执行的程序代码段。

（3）数据段：一个进程的数据段，可以是进程对应的程序加工处理原始数据，也可以是程序执行时产生的中间或最终结果。

3.进程的状态与转换

通常进程有以下 5 种状态，前 3 种是进程的基本状态：

运行态：进程正在 CPU 上运行。在单 CPU 中，每个时刻只有一个进程处于运行态。
就绪态：进程获得了除 CPU 外的一切所需资源，一旦得到 CPU，便可立即运行。系统中处于就绪态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
阻塞态：也称等待态。进程正在等待某一事件而暂停运行。系统通常将处于阻塞态的进程也排成一个队列，甚至根据阻塞原因的不同，设置多个阻塞队列。
创建态：进程正在被创建，尚未转到就绪态。
终止态：进程需要结束运行时，系统首先将该进程设置为终止态。然后进一步处理资源释放和回收等工作。

进程状态的转换：

在一个系统中，通常存在着许多进程的 PCB，有的处于就绪态，有的处于阻塞态，而且阻塞的原因各不相同。为了方便进程的调度和管理，需要将各个进程的 PCB 用适当的方法组织起来。目前，常用的组织方式有链接方式和索引方式两种。

链接方式：将同一状态的 PCB 链接成一个队列，不同状态对应不同的队列，也可将处于阻塞态的进程的 PCB，根据其阻塞原因的不同，排成多个阻塞队列。

索引方式：将同一状态的进程组织在一个索引表中，索引表的表项指向相应的 PCB，不同状态对应不同的索引表。

4.进程控制

进程控制的主要功能是对系统中的进程实施有效的管理，具有创建新进程、撤销已有进程、实现进程状态转换等功能。

在操作系统中，一般将进程控制用的程序段称为原语，原语可以用关中断指令和开中断指令这两个特权指令实现原子性。

（1）进程的创建

允许一个进程创建另一个进程，此时创建者为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程终止时，应将其从父进程那里获得的资源还给父进程。

引起进程创建的事件：

终端用户登录系统：分时系统中，用户登录成功，系统会为其建立一个新进程。
作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程。
系统提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求。
用户程序的应用请求：由用户进程主动请求创建一个子进程。

创建原语：创建态 -> 就绪态

为新进程分配一个唯一的 PID，并申请一个空白的 PCB（PCB 是有限的）。若 PCB 申请失败，则创建失败。
为新进程分配所需资源。这些资源或从操作系统获得，或仅从其父进程获得。
初始化 PCB。
若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。

（2）进程的终止

引起进程终止的事件：

正常结束：表示进程的任务已完成并准备退出运行。
异常结束：进程在运行时，发生了某种异常时间，使进程无法继续进行。
外界干预：指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。

终止原语：就绪态/阻塞态/运行态 -> 终止态 -> 无

根据被终止进程的标识符，检索出该进程的 PCB，从中读出该进程的状态。
若被终止进程处于运行状态，立即终止该进程的执行，将 CPU 资源分配给其他进程。
若该进程还有子孙进程，则通常需将其所有子孙进程终止（有些系统无此要求）。
将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。
将该 PCB 从所在队列（链表）中删除。

有些系统不允许子进程在父进程终止的情况下存在，对于这类系统，若一个进程终止，则它的所有子进程也终止，这种现象称为级联终止。然而不是所有操作系统都是这样设计的。

（3）进程的阻塞和唤醒

当进程需要等待系统分配某种资源或等待相互合作的其他进程完成工作，就会从运行态切换到阻塞态；当等待的事件发生，就会再由阻塞态切换到运行态。因何事阻塞，就应由何事唤醒，阻塞原语和唤醒原语必须成对使用。

阻塞原语：运行态 -> 阻塞态

找到将要被阻塞进程的标识号（PID）对应的 PCB。
若该进程为运行态，则保护其现场，将其状态转换为阻塞态，停止运行。
将该 PCB 插入相应事件的等待队列，将 CPU 资源调度给其他就绪进程。

唤醒原语：阻塞态 -> 运行态

在该事件的等待队列中找到相应进程的 PCB。
将其从等待队列中移出，并置其状态为就绪态。
将该 PCB 插入就绪队列，等待调度程序调度。

（4）进程的切换

引起进程切换的事件：

当前进程时间片到
有更高优先级的进程到达
当前进程主动阻塞
当前进程终止

切换原语：

将运行环境信息存入 PCB
PCB 移入相应队列
选择另一个进程执行，并更新其 PCB
根据 PCB 恢复新进程所需的运行环境

5.进程通信

进程间通信（Inter-Process Communication，IPC） 是指两个进程间产生数据交互。

IPC 需要操作系统支持的原因：进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立，为了保证安全，一个进程不能直接访问另一个进程的地址空间。

PV 操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。高级通信方式主要有以下三类。

（1）共享存储

在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行读/写操作实现进程之间的信息交换。在对共享空间进行读写操作时，需要使用同步互斥工具（如 P 操作、V 操作）对共享空间的读/写进行控制。

共享存储又分为两种：低级方式的共享是基于数据结构的共享；高级方式的共享是基于存储区的共享。

操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。

（2）消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的发送消息和接收消息两个原语进行数据交换。

消息传递方式是当前应用最广泛的进程间通信机制。在微内核操作系统中，微内核与服务器之间的通信就采用了消息传递机制。

消息传递方式可以分为两种：

直接通信方式：发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息队列中取得消息。
间接通信方式：发送进程将消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱，因此这种通信方式又称信箱通信方式。

（3）管道通信

管道是一个特殊的共享文件，又名 pipe 文件，其实就是在内存中开辟一个大小固定的内存缓冲区。数据在管道中是先进先出的（循环队列）。

管道只能采用半双工通信，某一个时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
各进程要互斥地访问管道（由操作系统实现）。
当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
当管道读空时，读进程将被阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
管道中的数据一旦被读出，就彻底消失，是一次性操作。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：①一个管道允许多个写进程，一个读进程（2014 年 408 真题高教社官方答案）；②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据（Linux 的方案）。

注意：写进程往管道写数据，即便管道没被写满，只有管道没空，读进程就可以从管道读数据；读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据。

疑惑：王道书上有一句话是 “管道只能由创建进程所访问，当父进程创建一个管道后，管道是一种特殊的文件，子进程会继承父进程的打开文件，因此子进程也会继承父进程的管道，并可用它来与父进程进行通信”。个人感觉很奇怪，没有看明白这里的 “管道只能由创建进程所访问” 是什么意思。Deepseek 给出的答案是：在默认情况下，匿名管道的文件描述符仅由创建它的进程及其子进程持有，其他无关进程无法直接访问。因为匿名管道没有文件系统中的路径名，无法被其他无关进程直接打开或访问。若需要跨无关进程通信，应使用命名管道（FIFO）或消息队列等其他 IPC 机制。

（4）信号

6.线程的概念与特点

引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提供操作系统的并发性能。

线程最直接的理解就是轻量级进程，它是一个基本的 CPU 执行单元，也是程序执行流的最小单位。

线程由线程 ID、程序计数器、寄存器集合和堆栈组成。每个线程都有一个唯一的表示符和一个线程控制块（TCB），TCB 记录线程执行的寄存器和栈等现场状态。

一个线程可以创建和撤销另一个线程。线程也有就绪、阻塞和运行三种基本状态。

引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。

线程和进程的比较：

调度：线程切换的代价远低于进程。同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
并发性：引入线程的操作系统中，不仅进程之间可以并发执行，一个进程中的多个线程之间也可并发执行，甚至不同进程中的线程也能并发执行，从而使操作系统具有更好的并发性，提高了系统资源的利用率和系统吞吐量。
拥有资源：线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。
独立性：某个进程的线程对其他进程不可见。
系统开销：①创建或撤销进程时，系统都要为之分配或回收进程控制块（PCB）及其他资源，所付出的开销远大于创建或撤销进程；②进程切换时设计上下文的切换，而线程切换时只需保护和设置少量寄存器内存，开销很小；③同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无需操作系统的干预。
支持多处理器系统：对于传统单线程进程，不管有多少 CPU，进程只能运行在一个 CPU 上，对于多线程进程，可将进程中的多个线程分配到多个 CPU 上执行。

7.线程的实现方式

线程的实现可以分为两类：用户级线程（User-Level Thread，ULT） 和内核级线程（Kernel-level Thread，KLT）。内核级线程也称内核支持的线程。

（1）用户级线程：在用户级线程中，有关线程管理（创建、撤销和切换等） 的所有工作都由应用程序在用户空间内（用户态）完成，无需操作系统干预，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。

优点：①线程切换不需要转换到内核空间，节省了模式切换的开销。②调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法。③用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分。
缺点：①系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，进程内的所有线程也都被阻塞。②不能发挥多 CPU 的优势，内核每次分配给一个进程的仅有一个 CPU，因此进程中仅有一个线程能执行。

（2）内核级线程：内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。操作系统会为每个内核级线程建立相应的 TCB（线程控制块），通过 TCB 对线程进行管理。

优点：①能发挥多 CPU 的优势，内核能同时调度同一进程中的多个线程并行执行。②若进程中的一个线程被阻塞，则内核可以调度该进程中的其他线程占用 CPU，也可运行其他进程中的线程。③内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。④内核本身也可采用多线程技术，可以提高系统的执行速度和效率。
缺点：同一进程中的线程切换，需要从用户态切换到内核态进行，系统开销较大。

（3）组合方式：组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。

注意：用户级线程是 “代码逻辑” 的载体，内核级线程是 “运行机会” 的载体。内核级线程才是处理机分配的单位。

线程库（thread library） 是为程序员提供创建和管理线程的 API，实现线程库的方式有两种：

用户级线程库：在用户空间中提供一个没有内核支持的库。库的所有代码和数据结构都位于用户空间，调用库中的一个函数只导致用户空间中的一个本地函数的调用。
内核级线程库：实现由操作系统直接支持的内核级的一个库。库内的代码和数据结构位于内核空间，调用库中的一个 API 函数通常会导致对内核的系统调用。

8.多线程模型

在同时支持用户级线程和内核级线程的系统中，用户级线程和内核级线程连接方式的不同，形成了三种不同的多线程模型：

多对一模型：多个用户级线程映射到一个内核级线程（相当于前面的用户级线程模型）。

优点：线程管理是在用户空间上进行的，无须切换到内核态，因此效率较高。
缺点：若一个线程在访问内核时发生了阻塞，则整个进程都会被阻塞；在任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个 CPU 上运行。

一对一模型：将每个用户级线程映射到一个内核级线程。

优点：当一个进程被阻塞后，允许调度另一个线程运行，所以并发能力较强。
缺点：每创建一个用户线程，相应地就需要创建一个内核线程，开销较大。

多对多模型：将 n 个用户级线程映射到 m 个内核级线程，要求 n 大于等于 m。

特点：既克服了多对一模型并发度不高的缺点，又克服了一对一模型开销太大的缺点。此外，还拥有上述两种模型各自的优点。

9.线程的状态与转换

和进程一样，线程之间也存在共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。相应地，线程在运行时也具有下面三种基本状态：

执行态：线程已获得 CPU 而正在运行。
就绪态：线程已具备各种执行条件，只需再获得 CPU 即可立即执行。
阻塞态：线程在执行中因某件事受阻而处于暂停状态。

10.线程的组织与控制

线程控制块（TCB） 通常包括：

线程标识符
一组寄存器，包括程序计数器、状态寄存器、和通用寄存器
线程运行状态，用于描述线程正处于何种状态
优先级
线程专有存储区，线程切换时用于保存现场
堆栈指针，用于过程调用时保存局部变量即返回地址等。

同一进程中所有的线程都能访问进程的地址空间和全局变量。但是，每个线程都拥有自己的堆栈，且互不共享。

线程的创建：用户程序启动时，通常仅有一个称为初始化线程的线程正在执行，其主要功能是用于创建新线程。创建新线程时，需要利用一个线程创建函数，并提供相应参数。创建完成后，函数会返回一个线程标识符。

线程的终止：

通常，线程被终止后并不立即释放它所占用的资源，只有当进程中的其他线程执行了分离函数后，被终止线程才与资源分离，此时的资源才能被其他线程利用。

被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行。

有些线程（主要是系统线程）一旦被建立，便一直运行而不会被终止。

二、CPU 调度

1.调度的概念与层次

一个作业（即一个具体的任务）从提交开始直到完成，往往要经历以下三级调度：

（1）高级调度（内存调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。即作业调度是内存与辅存之间的调度。

每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。

多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。

（2）中级调度（内存调度）：引入中级调度的目的是提高内存利用率和系统吞吐量。为此，将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。被挂起的进程 PCB 会被组织成挂起队列。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定将外存上的哪个挂起进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。

中级调度实际上是存储器管理中的对换功能。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

（3）低级调度（进程调度/处理机调度）：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度时操作系统中最基本的一种调度，各种操作系统中都必须配置这级调度。进程调度的频率很高，一般几十毫秒一次。

三层调度的对比

	负责内容	调度位置	发生频率	对进程状态的影响
高级调度（作业调度）	从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存 -> 内存（面向作业）	最低	无 -> 创建态 -> 就绪态
中级调度（内存调度）	进程挂起与恢复	外存 -> 内存（面向进程）	中等	挂起态 -> 就绪态（阻塞挂起 -> 阻塞态）
低级调度（进程调度）	从就绪队列中选择一个进程为其分配处理机	内存 -> CPU	最高	就绪态 -> 运行态

补充：暂时调到外存等待的进程状态称为挂起态（suspend），挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态，从而扩展出七状态模型。

挂起和阻塞的区别：两种状态都是暂时不能获得 CPU 的服务，但挂起态是将进程映像调到外存去，而阻塞态下进程映像还在内存中。

有的操作系会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

2.进程调度的时机、方式、切换与过程

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

（1）需要进行进程调度与切换的情况

①当前运行的进程主动放弃处理机

进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞（如等待 I/O）

②当前运行的进程被动放弃处理机

分给进程的时间片用完
有更紧急的事需要处理（如 I/O 中断）
有更高优先级的进程进入就绪队列

（2）不能进行进程调度与切换的情况

在处理中断的过程中。
进程在操作系统内核程序临界区中。
在原子操作过程中（原语）。

注意：进程在普通临界区中是可以进行调度、切换的。

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。

临界区：访问临界资源的那段代码。

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列。

内核临界资源和普通临界资源：

根据当前运行的进程是否可以被强行地剥夺处理机资源（被动放弃），可以将进程调度的方式分为两种：

①非剥夺调度方式：又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

特点：实现简单，系统开销小。但是无法及时处理紧急任务，适合于早期的批处理系统。

②剥夺调度方式：又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的任务需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

特点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统。

“狭义的进程调度” 与 “进程切换” 的区别：

狭义的进程调度指的是从就绪队列中选中一个要运行的进程（这个进程可以是刚刚被暂停执行的进程，也可以是另一个进程，后一种情况就需要进程切换），是一种决策行为。

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程，是一种执行行为。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：①对原来运行进程各种数据的保存。②对新的进程各种数据的恢复。

进程的切换是有代价的，因此如果过于频繁的进行进程调度、转换，必然会使整个系统的效率降低。

3.调度程序（调度器）和闲逛进程

用于调度和分派 CPU 的组件称为调度程序（调度器）。

调度程序通常由三部分组成：

排队器：将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入相应的就绪队列。
分派器：依据调度程序所选的进程，将其从就绪队列中，将 CPU 分配给新进程。
上下文切换器：在对 CPU 进行切换时，会发生两对上下文的切换操作。①将当前进程的上下文保存到其 PCB 中，再装入分派程序的上下文，以便分派程序运行。②移出分派程序的上下文，将新选进程的 CPU 现场信息装入 CPU 的各个相应寄存器。

上下文切换时，需要执行大量 load 和 store 指令，会花费较多时间。现在已有硬件实现的方法来减少上下文切换时间。通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可。

不支持内核级线程的操作系统，调度程序的处理对象是进程；支持内核级线程的操作系统，调度程序的处理对象是内核线程。

当进程切换时，若系统重没有就绪程序，则会调度闲逛进程（Idle Process） 运行，它的 PID 为 0。

闲逛进程的特性：

优先级最低，没有就绪进程时才会执行闲逛进程，只要有进程就绪，就会立即让出 CPU。
不需要 CPU 之外的资源，能耗低，不会被阻塞。
可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断，周期性地唤醒调度程序，让调度程序检查此时是否有其他进程已经就绪）

4.调度算法的评价指标

（1）CPU 利用率：指 CPU 有效工作时间占总时间的比例。

（2）系统吞吐量：单位时间内完成作业的数量。

（3）周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

包括四个部分：①作业在外存后备队列上等待作业调度（高级调度）的时间、②进程在就绪队列上等待进程调度（低级调度）的时间、③进程在 CPU 上执行的时间、④进程等待 I/O 操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。

周转时间 = 作业完成时刻 - 作业提交时刻

但在周转时间相同的情况下，运行时间不同的作业，给用户的感觉是不一样的，因此引入了带权周转时间。

带权周转时间 = 作业周转时间 ÷ 作业实际运行时间。

（4）等待时间：指进程/作业处于等待处理机状态时间之和。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间内其实进程也是在被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

衡量一个调度算法的优劣，常常只需简单地考察等待时间。因为 CPU 调度算法只影响作业在就绪队列中等待所花的时间，不影响作业执行或 I/O 操作的时间。

（5）响应时间：指从用户提交请求到首次产生响应所用的时间。

5.CPU 调度算法

（1）先来先服务（FCFS）调度算法

算法思想：主要从公平的角度考虑。

算法规则：按照作业/进程到达的先后顺序进行服务。

用于作业/进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。

是否可抢占：非抢占式算法。

优点：公平、算法实现简单。

缺点：效率低。对长作业比较有利，但对短作业不利；有利于 CPU 繁忙型作业，而不利于 I/O 繁忙型作业。

是否会饥饿（饥饿指某进程/作业长期得不到服务）：不会。

（2）短作业优先（SJF）调度算法

算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间。

算法规则：最短的作业/进程优先得到服务（所谓最短，是指要求服务时间最短）。

用于作业/进程调度：既可用于作业调度，也可用于进程调度。用于进程调度时称为**短进程优先（SPF）**算法。

是否可抢占：SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本，即最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）。

最短剩余时间优先算法：每当有新进程加入，就绪队列改变时就需要调度，如果新到达的进程剩余事件比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

相较于非抢占式的 SJF，抢占式的 SRTN 的平均等待时间、平均周转时间、平均带权周转时间更低。但是，有些时候，我们依旧说，SJF 算法的平均等待时间、平均周转时间、平均带权周转时间是最少的。

优点：最短的平均等待时间、平均周转时间。

缺点：①对短作业有利，对长作业不利。②完全未考虑作业的紧迫程度，不能保证紧迫性作业被及时处理。③作业的长短是根据用户所提供的估计执行时间而定的，而用户又可能有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

是否会饥饿：会。如果源源不断有短作业/进程到来吗，可能使长作业/进程长时间得不到服务，产生饥饿现象。如果一直得不到服务，则称为饿死。

（3）高响应比优先（HRRN）调度算法

算法思想：要综合考虑作业/进程的等待时间和要求服务的时间

算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。

响 应 比 = \frac{等 待 时 间 + 要 求 服 务 时 间}{要 求 服 务 时 间}

用于作业/进程调度：既可用于作业调度，也可用于进程调度。

是否可抢占：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。

优点：综合考虑了等待时间和运行时间（要求服务时间）。①等待时间相同时，要求服务时间短的优先（SJF 的优点）。②要求服务时间相同时，等待时间长的优先（FCFS 的优点）。③对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

是否会饥饿：不会

注意：前三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心 “响应时间”，也并不区分任务的紧急程序，因此对于用户来说，交互性很糟糕。一般只适用于早期的批处理系统。

（4）时间片轮转（RR）调度算法

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如 100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列尾重新排队；若一个时间片尚未用完而当前进程已运行完成，则调度程序会被立即激活（主动放弃处理机）。

用于作业/进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）。

是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 CPU 时间片已到。

优点：公平；响应快，适用于分时操作系统。

缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程序。

是否会饥饿：不会

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法；若时间片过小，则 CPU 将在进程间过于频繁地切换，使 CPU 的开销增大，而真正用于运行用户进程的时间片将减小。

注意：如果某一时刻，进程 a 下处理机，同时新进程 b 到达，则默认新到达的进程先进入就绪队列。如果一个进程时间片用完但未运行结束，且此时就绪队列为空，则会让该进程继续执行一个时间片（是否会发生调度呢？如果说了队列为空的话，应该是默认不会调度，否则验严格按照规则来，下处理机后，立刻放到就绪队列，然后检测就绪队列。就绪队列不可能为空，至少有一个它自己。个人看法）。

（5）优先级调度算法

算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程序来决定处理顺序。

算法规则：调度时选择优先级最高的作用/进程。

用于作业/进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于之后会学习的 I/O 调度中。

是否可抢占：两种都有。

非抢占式优先级调度算法：当一个进程正在 CPU 上运行时，即使有某个优先级更高的进程进入就绪队列，仍让正在运行的进程继续运行，直到由于其自身的原因让出 CPU 时（任务完成或等待事件），才将 CPU 分配给就绪队列中优先级最高的进程。
抢占式优先级调度算法：当一个进程正在 CPU 上运行时，若有某个优先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将 CPU 分配给优先级更高的进程。

补充：就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种：

静态优先级：优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。优点是简单易行，系统开销小；缺点是不过精确，可能出现优先级低的进程长期得不到调度的情况。
动态优先级：创建进程时先赋予进程一个有优先级，但优先级会随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，规定优先级随等待时间的增加而提高，于是，对于优先级初值较低的进程，在等待足够长的时间后也可获得 CPU。

进程优先级的设置规则：

系统进程 > 用户进程
交互型进程 > 非交互型进程（或前台进程 > 后台进程）
I/O 型进程 > 计算型进程（前者指频繁使用 I/O 设备的进程，后者指频繁使用 CPU 的进程，因为 I/O 设备的处理速度要比 CPU 慢得多，让其尽早开始工作，可以提升系统整体效率）

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

是否会饥饿：会

（6）多级队列调度算法

系统中按进程类型设置多个队列，进程创建成功后插入某个队列：

队列之间可以采取固定优先级或时间片划分：

固定优先级：高优先级空时低优先级进程才能被调度（可能导致低优先级进程饥饿）。
时间片划分：如三个队列分配时间 50%、40%、10%。

各队列内可采用不同的调度策略，如：系统进程队列采用优先级调度；交互式队列采用 RR；批处理队列采用 FCFS。

（7）多级反馈队列调度算法

算法思想：对其他调度算法的折中权衡

算法规则：

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片。

用于作业/进程调度：用于进程调度。

是否可抢占：抢占式的算法。在 k 级队列的进程运行过程中，若更上级的队列（1~k-1 级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾（抢占后计时重置）。

优点：①对各类型进程相对公平（FCFS 的优点）。②每个新到达的进程都可以很快就得到响应（RR 的优点）。③短进程只用较少的时间就可完成（SPF 的优点）。④不必事先估计进程的运行时间（避免用户作假）。⑤可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，而不是放到下一级队列，从而 I/O 型进程就可以保持较高优先级）。

是否会饥饿：会

注意：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而时间片轮转、优先级调度、多级反馈队列这三种算法能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。

总结

先来先服务算法和短作业优先算法无法保证及时地接收和处理问题，因此无法保证在规定的时间间隔内响应每个用户的需求，也同样无法达到实时操作系统的及时性需求。
优先级调度算法按照任务的优先级进行调度，对于更紧急的任务给予更高的优先级，适合实时操作系统。
高响应比优先调度算法、时间片轮转算法、多级反馈队列调度算法都能保证每个任务在一定时间内分配到时间片，并轮流占用 CPU，适合分时操作系统。

（8）基于公平原则的调度算法

两种相对公平的调度算法：

①保证调度算法：向用户做出明确的性能保证，而非优先运行保证。一种很实际且很容易实现的保证是：若系统中有 n 个用户登录，则每个用户都能保证获得 1/n 的 CPU 时间；又如，若在单用户系统中有 n 哥进程正在运行，则每个进程都保证获得 1/n 的 CPU 时间。

②公平分享调度算法：保证每个用户能获得相同的 CPU 时间。无论用户启动多少进程，都能保证每个用户分配到应得的 CPU 份额（保证对进程公平并不意味着对用户也公平，因为每个用户所拥有的进程数可能不同）。

6.多处理机调度机制

多处理机系统的调度与系统结构有关：

非对称处理机（Asymmetric MultiProcessing，AMP）：大多采用主从式操作系统，内核驻留在主机上，而从机上只运行用户程序，进程调度由主机负责。当从机空闲时，便向主机发送一个索求进程的信号，在主机中有一个就绪队列，主要队列不空，主机便从队首摘下一个进程分配给索求进程的从机。

特点：分配方式实现简单，但是主机太忙，容易成为系统瓶颈。

对称多处理机（Symmetric MultiProcessing，SMP）：的所有处理机都是相同的，因此由调度程序将任何一个进程分配给任何一个 CPU。

（1）亲和性和负载平衡

当一个进程从一个 CPU 移到其他 CPU 上时，应将第一个 CPU 的缓存设置为无效，然后重新填充第二个 CPU 的缓存，这种操作的代价较高，因此系统应尽量避免将一个进程从一个 CPU 移到另一个 CPU，而应试图让一个进程运行在同一个 CPU 上，这称为处理器亲和性。

对于 SMP 系统，应尽量保证所有 CPU 的负载平衡（也称负载均衡），即设法将负载平均分配到 SMP 系统的所有 CPU 上，以便充分利用多处理机的优点。

然而，负载平衡通常会抵消处理器亲和性带来的好处，在某些系统中，只有当不平衡达到一定程度后才移动进程。

（2）多处理机调度方案

方案一：公共就绪队列

系统中仅设置一个公共就绪队列，所有 CPU 共享一个就绪队列。这种方案很好地实现了负载均衡，缺点是进程可能频繁地在不同的 CPU 上运行，处理器亲和性不好。

提升处理器亲和性的方法有两种：软亲和和硬亲和

软亲和：指由调度程序尽量保持一个进程到某个 CPU 上，但这个进程也可以迁移到其他 CPU 上。
硬亲和：指由用户进程通过系统调用，主动请求系统分配到固定的 CPU 上。

Linux 系统实现了软亲和，也支持硬亲和的系统调用。

方案二：私有就绪队列

系统为每个 CPU 设置一个私有就绪队列，当 CPU 空闲时，就从各自的私有就绪队列中选择一个进程运行。这种方案很好地实现了处理器亲和性，缺点是必须进行负载平衡。

平衡负载的方法通常有两种：推迁移和拉迁移

对于推迁移，一个特定的系统程序周期性检查每个 CPU 的负载，若发现不平衡，则从超载 CPU 的就绪队列中 “推” 一些进程到空闲 CPU 的就绪队列，从而平均分配负载。若一个 CPU 负载很低，则从超载 CPU 的就绪队列中 “拉” 一些进程到自己的就绪队列，发生拉迁移。在系统中，推迁移和拉迁移常被并行实现。

三、同步与互斥

1.同步与互斥的基本概念

同步：亦称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要协调它们的运行次序而等待、传递信息所产生的制约关系。同步关系源于进程之间的相互合作。

互斥：也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此临界资源。

为了保证临界资源的访问，必须互斥地进行，可将临界资源的访问过程分为四个部分：

临界区是进程中访问临界资源的代码段，进入区和退出区是负责实现互斥的代码段。

临界区也称为临界段。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区，防止进程无限等待（饥饿）。
让权等待（原则性上应该遵循，但并非必须）。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

2.进程互斥的软件实现方法

（1）单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

P0 进程在执行②的过程中如果时间片用完，下处理机，此时 P1 进程依旧无法访问临界资源。只有 P0 进程完成对临界区域的使用后，执行③，让出临界资源的使用权后，P1 进程才能访问临界资源。

该算法可以实现每次只允许一个进程进入临界区，但两个进程必须交替使用临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区，违背了空闲让进原则。

（2）双标志先检查法

算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标志各进程想进入临界区的意愿。每个进程在进入临界区之前先检查当前有无别的进程想进入临界区，如果没有，则把自身对应的标志设为 true，之后开始访问。

在两个进程并发运行的情况下，如果按照①⑤②⑥③⑦的顺序执行，两个进程将会同时访问临界区，违背了忙则等待原则。原因在于进入区的检查和上锁两个处理不是一气呵成的。

（3）双标志后检查法

算法思想：双标志先检查法的改版，先上锁再检查。

若按照①⑤②⑥的顺序执行，两个进程将都无法进入临界区，虽然解决了忙则等待的问题，但是又违背了空闲让进和有限等待原则，会因各进程都长期无法访问临界资源而产生饥饿现象。