王道-操作系统-ch2-进程管理

王道

进程管理

【考纲内容】

(一）进程与线程

1. 进程与 $\color{green}{\text{线程}}$ 的基本概念
2. 进程/ $\color{red}{\text{线程的状态与转换}}$
3. $\color{green}{\text{线程的实现}}$ （内核支持的线程，线程库支持的线程）
4. 进程与 $\color{red}{\text{线程的组织与控制}}$
5. 进程间的通信（共享内存，消息传递，管道）

(二）CPU调度与上下文切换

1. 调度的基本概念
2. $\color{green}{\text{调度的目标}}$
3. $\color{green}{\text{调度的实现}}$ （ $\color{red}{\text{调度器/调度程序}}$ （scheduler），调度的时机与调度方式（抢占式/非抢占式）， $\color{red}{\text{闲逛进程}}$ ， $\color{red}{\text{内核级线程与用户级线程调度}}$ ）
4. 典型调度算法（先来先服务调度算法；短作业（短进程、短线程)优先调度算法;时间片轮转调度算法;优先级调度算法;高响应比优先调度算法; $\color{red}{\text{多级队列调度算法}}$ ;多级反馈队列调度算法。）
5. $\color{green}{\text{上下文及其切换机制}}$

(三）进程同步

1. 进程同步的基本概念
2. 基本实现方法（软件方法，硬件方法）
3. $\color{red}{\text{锁}}$
4. 信号量
5. $\color{red}{\text{条件变量}}$
6. 经典同步问题（生产者-消费者问题；读者-写者问题；哲学家进餐问题）

(四）死锁

1. 死锁的概念
2. 死锁处理策略
3. 死锁预防
4. 死锁避免
5. 死锁的检测和解除

【知识框架】

• 进程
  • 概念:与程序的区别
  • 特征:动态性、并发性、独立性、异步性、结构性
  • 状态:运行、就绪、阻塞、创建、结束
  • 控制:创建、终止、阻塞和唤醒、切换
  • 组织:进程控制块PCB、程序段、数据段
  • 通信:共享存储、消息传递、管道通信
• 线程
  • 概念、与进程的比较、属性
  • 线程的实现方式
• 处理机调度
  • 概念、三级调度:作业调度、中级调度、进程调度调度方式:剥夺式、非剥夺式
  • 调度准则:CPU利用率、吞吐量、周转时间、等待时间、响应时间
  • 算法:先来先服务、短作业(SJF）优先、优先级、高响应比优先、时间片轮转、多级反馈队列
• 进程同步
  • 概念:临界资源、同步、互斥
  • 实现方法:软件实现的几种算法、硬件实现
  • 信号量:整型、记录型
  • 经典问题:生产者-消费者问题、读者-写者问题、哲学家进餐问题、吸烟者问题
• 死锁
  • 定义
  • 原因:系统资源竞争、进程推进顺序非法
  • 条件:互斥、不剥夺、请求和保持、循环等待
  • 策略:预防死锁、避免死锁、死锁的检测与解除

【复习提示】

进程管理是操作系统的核心，也是每年必考的重点。其中，进程的概念、进程调度、信号量机制实现同步和互斥、进程死锁等更是重中之重，必须深入掌握。需要注意的是，除选择题外，本章还容易出综合题，其中信号量机制实现同步和互斥、进程调度算法和银行家算法都是可能出现的综合题考点，如利用信号量进行进程同步就在往年的统考中频繁出现。

进程:process

进程与线程

在学习本节时，请读者思考以下问题:

1）为什么要引入进程?

2）什么是进程?进程由什么组成?

3）进程是如何解决问题的?

希望读者带着上述问题去学习本节内容，并在学习的过程中多思考，从而更深入地理解本节内容。进程本身是一个比较抽象的概念，它不是实物，看不见、摸不着，初学者在理解进程概念时存在一定困难，在介绍完进程的相关知识后，我们会用比较直观的例子帮助大家理解。

进程的概念和特征

进程的概念

在多道程序环境下，允许多个程序并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。为此引入了进程（Process）的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性)。

为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block，PCB)。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。相应地，由程序段、相关数据段和PCB三部分构成了进程映像（进程实体)。所谓创建进程，实质上是创建进程映像中的PCB;而撤销进程,实质上是撤销进程的PCB。值得注意的是，进程映像是静态的，进程则是动态的。

注意:PCB是进程存在的唯一标志!

从不同的角度，进程可以有不同的定义，比较典型的定义有:

1）进程是程序的一次执行过程。

2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

3）进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

引入进程实体的概念后，我们可以把传统操作系统中的进程定义为:“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。”

读者要准确理解这里说的系统资源。它指处理机、存储器和其他设备服务于某个进程的“时间”，例如把处理机资源理解为处理机的时间片才是准确的。因为进程是这些资源分配和调度的独立单位，即“时间片”分配的独立单位，这就决定了进程一定是一个动态的、过程性的概念。

进程的特征

进程是由多道程序的并发执行而引出的，它和程序是两个截然不同的概念。进程的基本特征是对比单个程序的顺序执行提出的，也是对进程管理提出的基本要求。

1）动态性。进程是程序的一次执行，它有着创建、活动、暂停、终止等过程，具有一定的生命周期，是动态地产生、变化和消亡的。动态性是进程最基本的特征。

2）并发性。指多个进程实体同时存于内存中，能在一段时间内同时运行。并发性是进程的重要特征，同时也是操作系统的重要特征。引入进程的目的就是使程序能与其他进程的程序并发执行，以提高资源利用率。

3）独立性。指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序，都不能作为一个独立的单位参与运行。

4）异步性。由于进程的相互制约，使得进程具有执行的间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此在操作系统中必须配置相应的进程同步机制。

5）结构性。每个进程都配置一个PCB对其进行描述。从结构上看，进程实体是由程序段、数据段和进程控制块三部分组成的。

通常不会直接考查进程有什么特性，所以读者对上面的5个特性不求记忆，只求理解。

并发和异步的区别

进程的状态与转换

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化(一个进程会经历若干不同状态)。通常进程有以下5种状态，前3种是进程的基本状态。

1）运行态。进程正在处理机上运行。在单处理机环境下，每个时刻最多只有一个进程处于运行态。

2）就绪态。进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。

3）阻塞态，又称等待态。进程正在等待某一事件而暂停运行，如等待某资源为可用（不包括处理机）或等待输入/输出完成。即使处理机空闲，该进程也不能运行。

4）创建态。进程正在被创建，尚未转到就绪态。创建进程通常需要多个步骤:首先申请一个空白的 PCB，并向PCB中填写一些控制和管理进程的信息;然后由系统为该进程分配运行时所必需的资源;最后把该进程转入就绪态。

5）结束态。进程正从系统中消失，可能是进程正常结束或其他原因中断退出运行。进程需要结束运行时，系统首先必须将该进程置为结束态，然后进一步处理资源释放和回收等工作。

注意区别就绪态和等待态:就绪态是指进程仅缺少处理机，只要获得处理机资源就立即运行;而等待态是指进程需要其他资源（除了处理机）或等待某一事件。之所以把处理机和其他资源划分开，是因为在分时系统的时间片轮转机制中，每个进程分到的时间片是若干毫秒。也就是说，进程得到处理机的时间很短且非常频繁，进程在运行过程中实际上是频繁地转换到就绪态的;而其他资源（如外设）的使用和分配或某一事件的发生（如IO操作的完成）对应的时间相对来说很长，进程转换到等待态的次数也相对较少。这样来看，就绪态和等待态是进程生命周期中两个完全不同的状态，显然需要加以区分。

图2.1说明了5种进程状态的转换，而3种基本状态之间的转换如下:

• 就绪态→运行态:处于就绪态的进程被调度后，获得处理机资源（分派处理机时间片)，于是进程由就绪态转换为运行态。
• 运行态→就绪态:处于运行态的进程在时间片用完后，不得不让出处理机，从而进程由运行态转换为就绪态。此外，在可剥夺的操作系统中，当有更高优先级的进程就绪时，调度程序将正在执行的进程转换为就绪态，让更高优先级的进程执行。
• 运行态→阻塞态:进程请求某一资源（如外设）的使用和分配或等待某一事件的发生(如I/O操作的完成）时，它就从运行态转换为阻塞态。进程以系统调用的形式请求操作系统提供服务，这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式。
• 阻塞态→就绪态:进程等待的事件到来时，如IO操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞态转换为就绪态。

图2.1 5种进程状态的转换

需要注意的是，一个进程从运行态变成阻塞态是 $\color{green}{\text{主动}}$ 的行为，而从阻塞态变成就绪态是 $\color{green}{\text{被动}}$ 的行为，需要其他相关进程的协助。

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。

进程的创建

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

在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。操作系统创建一个新进程的过程如下（创建原语):
1）为新进程分配一个唯一的进程标识号，并申请一个空白的 PCB (PCB是有限的)。若申请失败，则创建失败。

2）为进程分配资源，为新进程的程序和数据及用户栈分配必要的内存空间（在PCB中体现)。注意，若资源不足（如内存空间)，则并不是创建失败，而是处于阻塞态，等待内存资源。

3）初始化 PCB，主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。

4）若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。

进程的终止

引起进程终止的事件主要有:①正常结束，表示进程的任务已完成并准备退出运行。②异常结束，表示进程在运行时，发生了某种异常事件，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O故障等。③外界干预，指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。

操作系统终止进程的过程如下（撤销原语):

1）根据被终止进程的标识符，检索PCB，从中读出该进程的状态。

2）若被终止进程处于执行状态，立即终止该进程的执行，将处理机资源分配给其他进程。

3）若该进程还有子孙进程，则应将其所有子孙进程终止。

4）将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。

5）将该PCB从所在队列（链表）中删除。

进程的阻塞和唤醒

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作可做等，由系统自动执行阻塞原语（Block)，使自己由运行态变为阻塞态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程(获得CPU才可能将其转为阻塞态。阻塞原语的执行过程如下:

1）找到将要被阻塞进程的标识号对应的PCB。

2）若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。3）把该PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程。

当被阻塞进程所期待的事件出现时,如它所启动的IO操作已完成或其所期待的数据已到达，由有关进程（比如，释放该IO 设备的进程，或提供数据的进程）调用唤醒原语（Wakeup)，将等待该事件的进程唤醒。唤醒原语的执行过程如下:

1）在该事件的等待队列中找到相应进程的PCB。

2）将其从等待队列中移出，并置其状态为就绪态。

3）把该PCB插入就绪队列，等待调度程序调度。

需要注意的是，Block原语和 Wakeup原语是一对作用刚好相反的原语，必须成对使用。Block原语是由被阻塞进程自我调用实现的，而 Wakeup原语则是由一个与被唤醒进程合作或被其他相关的进程调用实现的。

进程切换

对于通常的进程而言，其创建、撤销及要求由系统设备完成的I/O操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程切换同样是在内核的支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

进程切换是指处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。进程切换的过程如下:

1））保存处理机上下文，包括程序计数器和其他寄存器。

2）更新PCB信息。

3）把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。

4）选择另一个进程执行，并更新其PCB。

5）更新内存管理的数据结构。

6）恢复处理机上下文。

注意，进程切换与处理机模式切换是不同的，模式切换时，处理机逻辑上可能还在同一进程中运行。若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的程序运行，则操作系统只需恢复进程进入内核时所保存的CPU现场，而无须改变当前进程的环境信息。但若要切换进程，当前运行进程改变了，则当前进程的环境信息也需要改变。

进程的组织

进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位。它由以下三部分组成，其中最核心的是进程控制块（PCB)。

进程控制块

进程创建时，操作系统为它新建一个PCB，该结构之后常驻内存，任意时刻都可以存取，并在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。

进程执行时，系统通过其 PCB 了解进程的现行状态信息，以便对其进行控制和管理;进程结束时，系统收回其PCB，该进程随之消亡。操作系统通过PCB表来管理和控制进程。

当操作系统欲调度某进程运行时，要从该进程的PCB中查出其现行状态及优先级;在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据;进程在运行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问PCB;当进程由于某种原因而暂停运行时，又需将其断点的处理机环境保存在PCB中。可见，在进程的整个生命期中，系统总是通过PCB对进程进行控制的，亦即系统唯有通过进程的PCB才能感知到该进程的存在。

表2.1是一个PCB 的实例。PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息等。各部分的主要说明如下:

表2.1 PCB通常包含的内容

1）进程描述信息。进程标识符:标志各个进程，每个进程都有一个唯一的标识号。用户标识符:进程归属的用户，用户标识符主要为共享和保护服务。

2）进程控制和管理信息。进程当前状态:描述进程的状态信息，作为处理机分配调度的依据。进程优先级:描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机。

3）资源分配清单，用于说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息。

4）处理机相关信息，主要指处理机中各寄存器的值，当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时，能从断点继续执行。

在一个系统中，通常存在着许多进程的PCB，有的处于就绪态，有的处于阻塞态，而且阻塞的原因各不相同。为了方便进程的调度和管理，需要将各进程的PCB用适当的方法组织起来。目前，常用的组织方式有链接方式和索引方式两种。链接方式将同一状态的PCB链接成一个队列,不同状态对应不同的队列，也可把处于阻塞态的进程的PCB，根据其阻塞原因的不同，排成多个阻塞队列。索引方式将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，不同状态对应不同的索引表，如就绪索引表和阻塞索引表等。

程序段

程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可被多个进程共享，即多个进程可以运行同一个程序。

数据段

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

进程的通信

进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式。高级通信方法主要有以下三类。

共享存储

在通信的进程之间存在一块可直接访问的共享空间,通过对这片共享空间进行写/读操作实现进程之间的信息交换，如图2.2所示。在对共享空间进行写/读操作时，需要使用同步互斥工具(如Р操作、V操作)，对共享空间的写/读进行控制。共享存储又分为两种:低级方式的共享是基于数据结构的共享;高级方式的共享则是基于存储区的共享。操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。

注意，用户进程空间一般都是独立的，进程运行期间一般不能访问其他进程的空间，要想让两个用户进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。

简单理解就是，甲和乙中间有一个大布袋，甲和乙交换物品是通过大布袋进行的，甲把物品放在大布袋里，乙拿走。但乙不能直接到甲的手中拿东西，甲也不能直接到乙的手中拿东西。

消息传递

在消息传递系统中，进程间的数据交换是以格式化的消息（Message）为单位的。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

1）直接通信方式。发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息，如图2.3所示。

图片详情

2）间接通信方式。发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。

这种中间实体一般称为信箱，这种通信方式又称信箱通信方式。该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。
简单理解就是，甲要告诉乙某些事情，就要写信，然后通过邮差送给乙。直接通信就是邮差把信直接送到乙的手上;间接通信就是乙家门口有一个邮箱，邮差把信放到邮箱里。

管道通信

管道通信是消息传递的一种特殊方式（见图2.4)。所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程（即写进程)，以字符流形式将大量的数据送入(写）管道;而接收管道输出的接收进程（即读进程）则从管道中接收（读）数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力:互斥、同步和确定对方的存在。

图片详情

下面以Linux中的管道为例进行说明。在Linux 中，管道是一种使用非常频繁的通信机制。从本质上说，管道也是一种文件，但它又和一般的文件有所不同，管道可以克服使用文件进行通信的两个问题，具体表现如下:

1）限制管道的大小。实际上，管道是一个固定大小的缓冲区。在 Linux中，该缓冲区的大小为4KB，这使得它的大小不像文件那样不加检验地增长。使用单个固定缓冲区也会带来问题，比如在写管道时可能变满，这种情况发生时，随后对管道的 write()调用将默认地被阻塞，等待某些数据被读取，以便腾出足够的空间供 write()调用写。

2）读进程也可能工作得比写进程快。当所有当前进程数据已被读取时，管道变空。当这种情况发生时，一个随后的read()调用将默认地被阻塞,等待某些数据被写入,这解决了read()调用返回文件结束的问题。

注意:从管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放空间以便写更多的数据。管道只能采用半双工通信，即某一时刻只能单向传输。要实现父子进程双方互动通信，需要定义两个管道。

管道可以理解为共享存储的优化和发展,因为在共享存储中，若某进程要访问共享存储空间则必须没有其他进程在该共享存储空间中进行写操作，否则访问行为就会被阻塞。而管道通信中存储空间进化成了缓冲区，缓冲区只允许一边写入、另一边读出，因此只要缓冲区中有数据，进程就能从缓冲区中读出，而不必担心会因为其他进程在其中进行写操作而遭到阻塞，因为写进程会先把缓冲区写满，然后才让读进程读，当缓冲区中还有数据时，写进程不会往缓冲区写数据。当然，这也决定了管道通信必然是半双工通信。

线程概念和多线程模型

线程的基本概念

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

线程最直接的理解就是“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。线程也有就绪、阻塞和运行三种基本状态。

引入线程后，进程的内涵发生了改变，进程只作为除CPU外的系统资源的分配单元，而线程则作为处理机的分配单元。由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。

线程与进程的比较

1）调度。在传统的操作系统中，拥有资源和独立调度的基本单位都是进程。在引入线程的操作系统中，线程是独立调度的基本单位，进程是拥有资源的基本单位。在同一进程中,线程的切换不会引起进程切换。在不同进程中进行线程切换，如从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。

2）拥有资源。不论是传统操作系统还是设有线程的操作系统，进程都是拥有资源的基本单位，而线程不拥有系统资源（也有一点儿必不可少的资源)，但线程可以访问其隶属进程的系统资源。要知道，若线程也是拥有资源的单位，则切换线程就需要较大的时空开销，线程这个概念的提出就没有意义。

3）并发性。在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也可以并发执行，从而使操作系统具有更好的并发性，提高了系统的吞吐量。

4）系统开销。由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、IO设备等，因此操作系统所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程CPU 环境的保存及新调度到进程CPU环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。此外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。

5）地址空间和其他资源（如打开的文件)。进程的地址空间之间互相独立，同一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见。

6）通信方面。进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以直接读/写进程数据段（如全局变量）来进行通信。

线程的属性

多线程操作系统把线程作为独立运行（或调度）的基本单位，此时的进程已不再是一个基本的可执行实体，但它仍具有与执行相关的状态。所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。线程的主要属性如下:

1）线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态。

2）不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。

3）同一进程中的各个线程共享该进程所拥有的资源。

4）线程是处理机的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU;在多CPU的计算机系统中，各线程可同时占用不同的CPU,若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。

5）一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。

为什么线程的提出有利于提高系统并发性?可以这样来理解:由于有了线程，线程切换时，有可能会发生进程切换，也有可能不发生进程切换，平均而言每次切换所需的开销就变小了，因此能够让更多的线程参与并发，而不会影响到响应时间等问题。

线程的实现方式

线程的实现可以分为两类:用户级线程(User-Level Thread，ULT)和内核级线程(Kernel-LevelThread，KLT)。内核级线程又称内核支持的线程。

在用户级线程中，有关线程管理（线程的创建、撤销和切换等）的所有工作都由应用程序完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。图2.5(a)说明了用户级线程的实现方式。

在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成。图2.5(b)说明了内核级线程的实现方式。

有些系统中使用组合方式的多线程实现。线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用程序中的多个用户级线程被映射到一些(小于等于用户级线程的数目）内核级线程上。图2.5(c)说明了用户级与内核级的组合实现方式。

图片详情

多线程模型

有些系统同时支持用户线程和内核线程，由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。

1）多对一模型。将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明)。

优点:线程管理是在用户空间进行的，因而效率比较高。

缺点:一个线程在使用内核服务时被阻塞，整个进程都会被阻塞;多个线程不能并行地运行在多处理机上。

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

优点:当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。

缺点:每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。

3）多对多模型。将n个用户级线程映射到m个内核级线程上，要求m≤n。

特点:多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。

此外，还拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。

本节小结

为什么要引入进程?

在多道程序同时运行的背景下，进程之间需要共享系统资源，因此会导致各程序在执行过程中出现相互制约的关系，程序的执行会表现出间断性的特征。这些特征都是在程序的执行过程中发生的，是动态的过程，而传统的程序本身是一组指令的集合，是一个静态的概念，无法描述程序在内存中的执行情况，即我们无法从程序的字面上看出它何时执行、何时停顿，也无法看出它与其他执行程序的关系，因此，程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序动态执行过程的性质乃至更好地支持和管理多道程序的并发执行，人们引入了进程的概念。

什么是进程?进程由什么组成?

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码本身，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。

一个进程实体由程序段、相关数据段和 PCB三部分构成，其中 PCB是标志一个进程存在的唯一标识，程序段是进程运行的程序的代码，数据段则存储程序运行过程中相关的一些数据。

进程是如何解决问题的?

进程把能够识别程序运行态的一些变量存放在 PCB中，通过这些变量系统能够更好地了解进程的状况，并在适当时进行进程的切换，以避免一些资源的浪费，甚至划分为更小的调度单位一线程来提高系统的并发度。

本节主要介绍什么是进程，并围绕这个问题进行一些阐述和讨论，为下一节讨论的内容做铺垫，但之前未学过相关课程的读者可能会比较费解，到现在为止对进程这个概念还未形成比较清晰的认识。接下来，我们再用一个比较熟悉的概念来类比进程，以便大家能彻底理解本节的内容到底在讲什么，到底解决了什么问题。

我们用“人的生命历程”来类比进程。首先，人的生命历程一定是一个动态的、过程性的概念，要研究人的生命历程，先要介绍经历这个历程的主体是什么。主体当然是人，相当于经历进程的主体是进程映像，人有自己的身份，相当于进程映像里有PCB;人生历程会经历好几种状态:出生的时候、弥留的时候、充满斗志的时候、发奋图强的时候及失落的时候，相当于进程有创建、撤销、就绪、运行、阻塞等状态，这几种状态会发生改变，人会充满斗志而转向发奋图强，发奋图强获得进步之后又会充满斗志预备下一次发奋图强，或者发奋图强后遇到阻碍会进入失落状态，然后在别人的开导之下又重新充满斗志。类比进程，会由就绪态转向运行态，运行态转向就绪态，或者运行态转向阻塞态，然后在别的进程帮助下返回就绪态。

若我们用“人生历程”这个过程的概念去类比进程，则对进程的理解就会更深一层。前面生活化的例子可以帮我们理解进程的实质，但它毕竟有不严谨的地方。一种较好的方式是，在类比进程和“人生历程”后，再看一遍前面较为严谨的书面阐述和讨论，这样对知识的掌握会更加准确而全面。

这里再给出一些学习计算机科学知识的建议。学习科学知识时，很多同学会陷入一个误区，即只注重对定理、公式的应用，而忽视对基础概念的理解。这是我们从小到大为了应付考试而培养出的一个毛病，因为熟练应用公式和定理对考试有立竿见影的效果。公式、定理的应用固然重要，但基础概念的理解能让我们透彻地理解一门学科，更利于我们产生兴趣，培养创造性思维。

处理机调度

在学习本节时，请读者思考以下问题:

1）为什么要进行处理机调度?

2）调度算法有哪几种?结合第1章学习的分时操作系统和实时操作系统，思考哪种调度算法比较适合这两种操作系统。

希望读者能够在学习调度算法前，先自己思考一些调度算法，在学习的过程中注意把自己的想法与这些经典的算法进行比对，并学会计算一些调度算法的周转时间。

调度的概念

调度的基本概念

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度是多道程序操作系统的基础，是操作系统设计的核心问题。

调度的层次

一个作业从提交开始直到完成，往往要经历以下三级调度，如图2.6所示。

1） $\color{green}{\text{作业调度}}$ 。又称高级调度，其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个(或多个）作业，给它（们）分配内存、输入/输出设备等必要的资源，并建立相应的进程，以使它（们）获得竞争处理机的权利。简言之，作业调度就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。
多道批处理系统中大多配有作业调度，而其他系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。

2） $\color{green}{\text{中级调度}}$ 。又称内存调度，其作用是提高内存利用率和系统吞吐量。为此，应将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。

3） $\color{green}{\text{进程调度}}$ 。又称低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

图2.6处理机的三级调度

三级调度的联系

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

1）作业调度为进程活动做准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。

2）作业调度次数少，中级调度次数略多，进程调度频率最高。

3）进程调度是最基本的，不可或缺。

调度的时机、切换与过程

进程调度和切换程序是操作系统内核程序。请求调度的事件发生后，才可能运行进程调度程序，调度了新的就绪进程后，才会进行进程间的切换。理论上这三件事情应该顺序执行，但在实际设计中，操作系统内核程序运行时，若某时发生了引起进程调度的因素，则不一定能够马上进行调度与切换。

现代操作系统中，不能进行进程的调度与切换的情况有以下几种:

1）在 $\color{green}{\text{处理中断}}$ 的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。

2）进程在操作系统 $\color{red}{\text{内核程序}}$ $\color{green}{\text{临界区}}$ 中。进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放。

3）其他需要完全屏蔽中断的 $\color{green}{\text{原子操作}}$ 过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。

若在上述过程中发生了引起调度的条件，则不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。

应该进行进程调度与切换的情况如下:

1）发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是 $\color{green}{\text{非剥夺调度}}$ 。

2）中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了 $\color{green}{\text{剥夺方式}}$ 的调度。

进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

进程调度方式

所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。

通常有以下两种进程调度方式:

1）非剥夺调度方式，又称非抢占方式。非剥夺调度方式是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。

在非剥夺调度方式下，一旦把CPU分配给一个进程，该进程就会保持CPU直到终止或转换到等待态。这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统但它不能用于分时系统和大多数的实时系统。

2）剥夺调度方式，又称抢占方式。剥夺调度方式是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。但“剥夺”不是一种任意性行为，必须遵循一定的原则，主要有优先权、短进程优先和时间片原则等。

调度的基本准则

不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，人们提出了很多评价准则，下面介绍其中主要的几种:

1） $\color{green}{\text{CPU利用率}}$ 。CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使CPU保持“忙”状态，使这一资源利用率最高。

2） $\color{green}{\text{系统吞吐量}}$ 。表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间,因此会降低系统的吞吐量。而对于短作业，它们所需要消耗的处理机时间较短，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。

3） $\color{green}{\text{周转时间}}$ 。周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及进行输入/输出操作所花费时间的总和。

作业的周转时间可用公式表示如下:

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

平均周转时间是指多个作业周转时间的平均值:

平均周转时间=（作业1的周转时间+…+作业 $n$ 的周转时间）/ $n$

$\color{red}{\text{带权周转时间}}$ 是指 $\color{green}{\text{作业周转时间}}$ 与 $\color{green}{\text{作业实际运行时间}}$ 的比值:

$\text{带权周转时间}=\dfrac{\text{作业周转时间}}{作业实际运行时间}$

$\color{red}{\text{平均带权周转时间}}$ 是指多个作业带权周转时间的平均值:

平均带权周转时间=（作业1的带权周转时间+..+作业 $n$ 的带权周转时间）/ $n$

4）等待时间。等待时间指进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。

5）响应时间。响应时间指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。

要想得到一个满足所有用户和系统要求的算法几乎是不可能的。设计调度程序，一方面要满足特定系统用户的要求（如某些实时和交互进程的快速响应要求)，另一方面要考虑系统整体效率（如减少整个系统的进程平均周转时间)，同时还要考虑调度算法的开销。

典型的调度算法

先来先服务(FCFS)调度算法

FCFS 调度算法是一种最简单的调度算法，它既可用于作业调度，又可用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

在进程调度中，FCFS 调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

下面通过一个实例来说明FCFS调度算法的性能。假设系统中有4个作业，它们的提交时间分别是8,8.4,8.8,9，运行时间依次是2,1,0.5,0.2，系统采用FCFS调度算法，这组作业的平均等待时间、平均周转时间和平均带权周转时间见表2.2。

表2.2 FCFS调度算法的性能

FCFS 调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。

FCFS 调度算法的特点是算法简单，但效率低;对长作业比较有利，但对短作业不利（相对SJF和高响应比);有利于CPU繁忙型作业，而不利于I/O繁忙型作业。

短作业优先(SJF)调度算法

短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短作业优先（SJF)调度算法从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行;短进程优先(SPF）调度算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。

例如，考虑表2.2中给出的一组作业，若系统采用短作业优先调度算法，其平均等待时间、平均周转时间和平均带权周转时间见表2.3。

表2.3SJF调度算法的性能

SJF调度算法也存在不容忽视的缺点:

1）该算法对长作业不利，由表2.2和表2.3可知，SJF调度算法中长作业的周转时间会增加更严重的是，若有一长作业进入系统的后备队列，由于调度程序总是优先调度那些（E使是后进来的）短作业，将导致长作业长期不被调度（“饥饿”现象，注意区分“死锁”后者是系统环形等待，前者是调度策略问题)。

2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。

3）由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

注意，SJF调度算法的平均等待时间、平均周转时间最少。

优先级调度算法

优先级调度算法又称优先权调度算法，它既可用于作业调度，又可用于进程调度。该算法中的优先级用于描述作业运行的紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为如下两种:

1） $\color{green}{\text{非剥夺式优先级调度算法}}$ 。当一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件)，才把处理机分配给更为重要或紧迫的进程。

2） $\color{green}{\text{剥夺式优先级调度算法}}$ 。当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。

而根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种:

1） $\color{green}{\text{静态优先级}}$ 。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。

2） $\color{green}{\text{动态优先级}}$ 。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

一般来说，进程优先级的设置可以参照以下原则:

1） $\color{green}{\text{系统进程}}$ > $\color{green}{\text{用户进程}}$ 。系统进程作为系统的管理者，理应拥有更高的优先级。

2） $\color{green}{\text{交互型进程}}$ > $\color{green}{\text{非交互型进程}}$ （或前台进程>后台进程)。大家平时在使用手机时，在前台运行的正在和你交互的进程应该更快速地响应你，因此自然需要被优先处理，即要有更高的优先级。

3） $\color{green}{\text{I/O型进程}}$ > $\color{green}{\text{计算型进程}}$ 。所谓IO型进程，是指那些会频繁使用IO设备的进程，而计算型进程是那些频繁使用CPU的进程（很少使用I/O设备)。我们知道，IO设备（如打印机）的处理速度要比CPU慢得多，因此若将IO型进程的优先级设置得更高，就更有可能让IO设备尽早开始工作，进而提升系统的整体效率。

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。

$\color{red}{\text{响应比}}$ 的变化规律可描述为

$\text{响应比}R_p=\dfrac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}$

根据公式可知：
1）作业的等待时间相同时，要求服务时间越短，响应比越高，有利于 $\color{green}{\text{短作业}}$ 。

2）要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高,因而它实现的是 $\color{green}{\text{先来先服务}}$ 。

3）对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了 $\color{green}{\text{饥饿状态}}$ ，兼顾了长作业。

时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。

在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。若时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此，时间片的大小应选择适当。

时间片的长短通常由以下因素确定:系统的响应时间、就绪队列中的进程数目和系统的处理能力。

多级反馈队列调度算法（融合了前几种算法的优点）

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展，如图2.7所示。通过动态调整进程优先级和时间片大小,多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的IO设备利用率和缩短响应时间而照顾IO型进程;同时，也不必事先估计进程的执行时间。

图片详情

多级反馈队列调度算法的实现思想如下:

1）设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。

2）赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。例如，第2级队列的时间片要比第1级队列的时间片长1倍……第 $i$ +1级队列的时间片要比第 $i$ 级队列的时间片长1倍。

3）一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统;若它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样按FCFS原则等待调度执行;若它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 $n$ 级队列后，在第 $n$ 级队列中便采用时间片轮转的方式运行。

4）仅当第1级队列为空时，调度程序才调度2级队列中的进程运行;仅当第1~( $i$ -1)级队列均为空时，才会调度第 $i$ 级队列中的进程运行。若处理机正在执行第 $i$ 级队列中的某进程，这时又有新进程进入优先级较高的队列〔第1～( $i$ -1)中的任何一个队列]，则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

多级反馈队列的优势有以下几点:

1）终端型作业用户:短作业优先。

2）短批处理作业用户:周转时间较短。

3）长批处理作业用户:经过前面几个队列得到部分执行，不会长期得不到处理。

本章小结

本节开头提出的问题的参考答案如下。

为什么要进行处理机调度?

若没有处理机调度，同意味着要等到当前运行的进程执行完毕后，下一个进程才能执行，而实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的速度与处理机相比是非常缓慢的，若让处理机总是等待外部设备，则对处理机的资源是极大的浪费。而引进处理机调度后，可在运行进程等待外部设备时，把处理机调度给其他进程，从而提高处理机的利用率。用一句简单的话说，就是为了合理地处理计算机的软/硬件资源。

调度算法有哪几种?结合第1章学习的分时操作系统和实时操作系统，思考有没有哪种调度算法比较适合这两种操作系统。

本节介绍的调度算法有先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法6种。

先来先服务算法和短作业优先算法无法保证及时地接收和处理问题，因此尤法休证仕规疋时时间间隔内响应每个用户的需求，也同样无法达到实时操作系统的及的性而水。优兀级A度开仫按照任务的优先级进行调度，对于更紧急的任务给予更高的优先级，适合实时操作系统。

高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法都能保证每个任务在一定时间内分配到时间片，并轮流占用CPU，适合分时操作系统。

本节主要介绍了处理机调度的概念。操作系统主要管理处理机、内存、文件、设备几种资源，只要对资源的请求大于资源本身的数量，就会涉及调度。例如，在单处理机系统中，处理机只有一个，而请求服务的进程却有多个，所以就有处理机调度的概念出现。而出现调度的概念后，又有了一个问题，即如何调度、应该满足谁、应该让谁等待，这是调度算法所回答的问题;而应该满足谁、应该让谁等待，要遵循一定的准则，即调度的准则。调度这一概念贯穿于操作系统的始终，读者在接下来的学习中，将接触到几种资源的调度问题和相应的调度算法。将它们与处理机调度的内容相对比，将会发现它们有异曲同工之妙。

进程同步

在学习本节时，请读者思考以下问题:

1）为什么要引入进程同步的概念?

2）不同的进程之间会存在什么关系?

3）当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗?

用PV操作解决进程之间的同步互斥问题是这一节的重点，考试已经多次考查过这一内容，读者务必多加练习，掌握好求解问题的方法。

• 大题中遇到相关的题目，信号量的类型直接定义为semaphore

进程同步的基本概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。下面举一个简单的例于米帮大豕理解赵个概念。例如，让系统计算1+2x3，假设系统产生两个进程:一个是加法进程，一个是乘法进程。要让计算结果是正确的，一定要让加法进程发生在乘法进程之后，但实际上操作系统具有异步性，若不加以制约，加法进程发生在乘法进程之前是绝对有可能的，因此要制定一定的机制去约束加法进程，让它在乘法进程完成之后才发生，而这种机制就是本节要讨论的内容。

临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可把临界资源的访问过程分成4个部分:

1） $\color{green}{\text{进入区}}$ 。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。

2） $\color{green}{\text{临界区}}$ 。进程中访问临界资源的那段代码，又称临界段。

3） $\color{green}{\text{退出区}}$ 。将正在访问临界区的标志清除。

4） $\color{green}{\text{剩余区}}$ 。代码中的其余部分。

代码详情

do{
  entry section; //进入区
  critical section; //临界区
  exit section;//退出区
  remainder section;//剩余区
} while (true)

同步

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

例如，输入进程A通过单缓冲向进程B提供数据。当该缓冲区空时，进程B不能获得所需数据而阻塞，一旦进程A将数据送入缓冲区，进程B就被唤醒。反之，当缓冲区满时，进程A被阻塞，仅当进程B取走缓冲数据时，才唤醒进程A。

互斥

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

例如，在仅有一台打印机的系统中，有两个进程A和进程B，若进程A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程唤醒，并将其由阻塞态变为就绪态。

为禁止两个进程同时进入临界区，同步机制应遵循以下准则:

1） $\color{green}{\text{空闲让进}}$ 。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

2） $\color{green}{\text{忙则等待}}$ 。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

3） $\color{green}{\text{有限等待}}$ 。对请求访问的进程，应保证能在有限时间内进入临界区。

4） $\color{green}{\text{让权等待}}$ 。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

实现临界区互斥的基本方法

软件实现方法

在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

1）算法一:单标志法。该算法设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号，即若turn=0，则允许 $P_0$ 进程进入临界区。该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”)。这样很容易造成资源利用不充分。若 $P_0$ 顺利进入临界区并从临界区离开，则此时临界区是空闲的，但 $P_1$ 并没有进入临界区的打算，turn=1一直成立， $P_0$ 就无法再次进入临界区（一直被while死循环困住)。

图片详情

2）算法二:双标志法先检查。该算法的基本思想是在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问，该进程需等待;否则，进程才进入自己的临界区。为此，设置一个数据flag[ $i$ ]，如第i个元素值为FALSE，表示 $P_i$ 进程未进入临界区，值为TRUE，表示P进程进入临界区。

图片详情

优点:不用交替进入，可连续使用;缺点: $P_i$ 和 $P_j$ ,可能同时进入临界区。按序列①② ${\textstyle\unicode{x2462}}$ ${\textstyle\unicode{x2463}}$ 执行时，会同时进入临界区（违背“忙则等待”)。即在检查对方的 flag 后和切换自己的flag前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

3）算法三:双标志法后检查。算法二先检测对方的进程状态标志，再置自己的标志，由在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后同时进入临界区。为此，算法三先将自己的标志设置为 TRUE，再检测对方的状态标志，若对方标志为TRUE，则进程等待;否则进入临界区。

图片详情

两个进程几乎同时都想进入临界区时，它们分别将自己的标志值 flag 设置为 TRUE，并且同时检测对方的状态（执行while语句)，发现对方也要进入临界区时，双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

4）算法四:Peterson’s Algorithm。为了防止两个进程为进入临界区而无限期等待，又设置变量 turn，每个进程在先设置自己的标志后再设置turn标志。这时，再同时检测另一个进程状态标志和不允许进入标志，以便保证两个进程同时要求进入临界区时，只允许个进程进入临界区。

图片详情

具体如下:考虑进程 $P_i$ ，一旦设置flag[ $i$ ] = true，就表示它想要进入临界区，同时turn =j,此时若进程 $P_j$ 已在临界区中，符合进程 $P_i$ 中的while循环条件，则 $P_i$ 不能进入临界区。若 $P_j$ 不想要进入临界区，即 flag[ $j$ ] = false，循环条件不符合，则 $P_i$ 可以顺利进入，反之亦然。本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。

理解Peterson’s Algorithm的最好方法就是手动模拟。

• $\color{red}{\text{Q：}}$ 如果一个进程执行一行语句，就转到另一个进程里面，不就会执行出错吗（一些讨论，虽然和我的问题不太一样）

硬件实现方法

理解本节介绍的硬件实现，对学习后面的信号量很有帮助。计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。

(1）中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入其临界区进行访问的最简方法是，禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。其典型模式为

图片详情

这种方法限制了处理机交替执行程序的能力，因此执行的效率会明显降低。对内核来说，在它执行更新变量或列表的几条指令期间，关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。

(2）硬件指令方法

TestAndSet 指令:这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下:

图片详情

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态: true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock;若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下:

图片详情

Swap指令:该指令的功能是交换两个字（字节）的内容。其功能描述如下:

图片详情

注意:以上对TestAndSet和Swap指令的描述仅是功能实现，而并非软件实现的定义。事实上，它们是由硬件逻辑直接实现的，不会被中断。

应为每个临界资源设置一个共享布尔变量lock，初值为false;在每个进程中再设置一个局部布尔变量 key，用于与lock交换信息。在进入临界区前，先利用Swap 指令交换lock 与 key的内容，然后检查key 的状态;有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下:

图片详情

硬件方法的优点:适用于任意数目的进程，而不管是单处理机还是多处理机;简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

硬件方法的缺点:进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

无论是软件实现方法还是硬件实现方法，读者只需理解它的执行过程即可，关键是软件实现方法。实际练习和考试中很少让读者写出某种软件和硬件实现方法，因此读者并不需要默写或记忆。以上的代码实现与我们平时在编译器上写的代码意义不同，以上的代码实现是为了表述进程实现同步和互斥的过程，并不是说计算机内部实现同步互斥的就是这些代码。

信号量

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的 $\color{green}{\text{原语}}$ wait(S)和 signal(S)访问，也可记为“P操作”和“V操作”。

原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。例如,前述的Test-and-Set和Swap指令就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。

原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。若能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，wait和 signal操作可描述为

图片详情

wait 操作中，只要信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量value 外，再增加一个进程链表L，用于链接所有等待该资源的进程。记录型信号量得名于采用了记录型的数据结构。记录型信号量可描述为

图片详情

相应的 wait(S)和 signal(S)的操作如下:

图片详情

wait操作，S.value—表示进程请求一个该类资源，当S.value <0时，表示该类资源已分配完毕，因此进程应调用block 原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列S.L，可见该机制遵循了“让权等待”的准则。

图片详情

signal操作,表示进程释放一个资源,使系统中可供分配的该类资源数增1,因此有S.value ++。若加1后仍是S.value≤0，则表示在S.L中仍有等待该资源的进程被阻塞，因此还应调用wakeup原语，将S.L中的第一个等待进程唤醒。

利用信号量实现同步

信号量机制能用于解决进程间的各种同步问题。设S为实现进程 $P_1$ , $P_2$ 同步的公共信号量，初值为0。进程 $P_2$ 中的语句y要使用进程 $P_1$ 中语句x的运行结果，所以只有当语句x执行完成之后语句y 才可以执行。其实现进程同步的算法如下:

图片详情

若 $P_2$ 先执行到P(S)时，S为0，执行Р操作会把进程 $P_2$ 阻塞，并放入阻塞队列;当进程 $P_1$ 中的x执行完后，执行V操作，把 $P_2$ 从阻塞队列中放回就绪队列，当 $P_2$ 得到处理机时，就得以继续执行。

利用信号量实现进程互斥

信号量机制也能很方便地解决进程互斥问题。设S为实现进程 $P_1$ , $P_2$ 互斥的信号量，由于每次只允许一个进程进入临界区﹐所以S的初值应为1(即可用资源数为1)。只需把临界区置于P(S)和V(S)之间，即可实现两个进程对临界资源的互斥访问。其算法如下:

图片详情

当没有进程在临界区时，任意一个进程要进入临界区，就要执行Р操作，把S的值减为0，然后进入临界区;当有进程存在于临界区时，S的值为0，再有进程要进入临界区，执行Р操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。

互斥是不同进程对同一信号量进行P,V操作实现的，一个进程成功对信号量执行了Р操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行V操作，表示当前没有进程进入临界区，可以让其他进程进入。

下面简单总结一下PV操作在同步互斥中的应用:在同步问题中，若某个行为要用到某种资源，则在这个行为前面Р这种资源一下;若某个行为会提供某种资源，则在这个行为后面V这种资源一下。在互斥问题中，P, V操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

利用信号量实现前驱关系

图片详情

信号量也可用来描述程序之间或语句之间的前驱关系。图2.8给出了一个前驱图，其中 $S_1$ , $S_2$ , $S_3$ ,… , $S_6$ 是最简单的程序段(只有一条语句)。为使各程序段能正确执行，应设置若干初始值为“0”的信号量。例如，为保证 $S_1$ → $S_2$ , $S_1$ → $S_3$ 的前驱关系，应分别设置信号量al, a2。同样，为保证 $S_2$ → $S_4$ , $S_2$ → $S_5$ , $S_5$ → $S_6$ , $S_4$ → $S_6$ , $S_5$ → $S_6$ ，应设置信号量b1, b2,c, d,e。

图片详情

分析进程同步和互斥问题的方法步骤

1）关系分析。找出问题中的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。

2）整理思路。找出解决问题的关键点，并根据做过的题目找出求解的思路。根据进程的操作流程确定Р操作、V操作的大致顺序。

3）设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理。

这是一个比较直观的同步问题，以 $S_2$ 为例，它是 $S_1$ 的后继，所以要用到 $S_1$ 的资源，在前面的简单总结中我们说过，在同步问题中，要用到某种资源，就要在行为（题中统一抽象成L)前面Р这种资源一下。 $S_2$ 是 $S_4$ ， $S_5$ 的前驱，给 $S_4$ ， $S_5$ ,提供资源，所以要在L行为后面V由 $S_4$ 和 $S_5$ 代表的资源一下。

管程

在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是，便产生了一种新的进程同步工具-管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。

管程的定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。

利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程( monitor )。管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据。

由上述定义可知，管程由4部分组成:

①管程的名称;
${\textstyle\unicode{x2461}}$ 局部于管程内部的共享结构数据说明;

${\textstyle\unicode{x2462}}$对该数据结构进行操作的一组过程(或函数);

${\textstyle\unicode{x2463}}$ 对局部于管程内部的共享数据设置初始值的语句。

管程的定义描述举例如下:

图片详情

熟悉面向对象程序设计的读者看到管程的组成后，会立即联想到管程很像一个类(class)。

1）管程把对共享资源的操作封装起来，管程内的共享数据结构只能被管程内的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享资源。对于上例，外部进程只能通过调用take_away()过程来申请一个资源;归还资源也一样。

2）每次仅允许一个进程进入管程，从而实现进程互斥。若多个进程同时调用take_away(),give_back()，则只有某个进程运行完它调用的过程后，下个进程才能开始运行它调用的过程。也就是说，各个进程只能串行执行管程内的过程，这一特性保证了进程“互斥”访问共享数据结构S。

条件变量

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量condition。通常，一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即 wait和 signal。

x.wait:当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。

x.signal: x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程。下面给出条件变量的定义和使用:

图片详情

条件变量和信号量的比较:

相似点:条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。

不同点:条件变量是“没有值”的，仅实现了“排队等待”功能;而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

经典同步问题

生产者-消费者问题

问题描述:一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待;只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

问题分析:

1）关系分析。生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。

2）整理思路。这里比较简单，只有生产者和消费者两个进程，正好是这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。

3）信号量设置。信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1;信号量full用于记录当前缓冲池中的“满”缓冲区数，初值为0。信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为 $n$ 。

我们对同步互斥问题的介绍是一个循序渐进的过程。上面介绍了一个同步问题的例子和一个互斥问题的例子，下面来看生产者-消费者问题的例子是什么样的。

生产者-消费者进程的描述如下:

图片详情

该类问题要注意对缓冲区大小为n的处理，当缓冲区中有空时，便可对empty变量执行Р操作，一旦取走一个产品便要执行V操作以释放空闲区。对empty和 full变量的Р操作必须放在对mutex 的P操作之前。若生产者进程先执行P(mutex)，然后执行P(empty)，消费者执行P(mutex),然后执行 P(full)，这样可不可以﹖答案是否定的。设想生产者进程已将缓冲区放满，消费者进程并没有取产品，即 empty =0，当下次仍然是生产者进程运行时，它先执行P(mutex)封锁信号量,再执行P(empty)时将被阻塞，希望消费者取出产品后将其唤醒。轮到消费者进程运行时，它先执行P(mutex)，然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，因此陷入了无休止的等待。同理，若消费者进程已将缓冲区取空，即 full = 0，下次若还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex, full 先释放哪一个无所谓，消费者先释放mutex 或empty都可以。

根据对同步互斥问题的简单总结，我们发现，其实生产者-消费者问题只是一个同步互斥问题的综合而已。

下面再看一个较为复杂的生产者-消费者问题。

问题描述:桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果;仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

问题分析:

1）关系分析。这里的关系要稍复杂一些。由每次只能向其中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发，如图2.9所示。

2）整理思路。这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。

3）信号量设置。首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple = 1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange =1表示可以取。

图2.9进程之间的关系

解决该问题的代码如下:

图片详情

进程间的关系如图2.9所示。dad()和 daughter()、mom()和 son()必须连续执行，正因为如此，也只能在女儿拿走苹果后或儿子拿走橘子后才能释放盘子，即V(plate)操作。

读者-写者问题

问题描述:有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让已有的读者和写者全部退出。

问题分析:

1）关系分析。由题目分析读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题。

2）整理思路。两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的Р操作、V操作即可解决。读者的问题比较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步，因此简单的一对Р操作、V操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时，这里不同读者对计数器的访问也应该是互斥的。

3）信号量设置。首先设置信号量count为计数器，用于记录当前读者的数量，初值为0;设置mutex为互斥信号量，用于保护更新count变量时的互斥;设置互斥信号量rw，用于保证读者和写者的互斥访问。

代码如下:

图片详情

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的 writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决程序。

图片详情

这里的写进程优先是相对而言的，有些书上把这个算法称为读写公平法，即读写进程具有-一样的优先级。当一个写进程访问文件时，若先有一些读进程要求访问文件，后有另一个写进程要求访问文件，则当前访问文件的进程结束对文件的写操作时，会是一个读进程而不是一个写进程占用文件(在信号量w的阻塞队列上，因为读进程先来，因此排在阻塞队列队首，而V操作唤醒进程时唤醒的是队首进程)，所以说这里的写优先是相对的，想要了解如何做到真正写者优先，

可参考其他相关资料。

读者-写者问题有一个关键的特征，即有一个互斥访问的计数器count，因此遇到一个不太好解决的同步互斥问题时，要想一想用互斥访问的计数器count能否解决问题。

哲学家进餐问题

图片详情

问题描述:一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图2.10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子(一根一根地拿起)。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。

问题分析:

1）关系分析。5名哲学家与左右邻居对其中间筷子的访问是互斥关系。

2）整理思路。显然，这里有5个进程。本题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法有两个:一是让他们同时拿两根筷子;二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。

3）信号量设置。定义互斥信号量数组chopstick[ 5 ]={1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号为0～4，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为(i +1)%5。

图片详情

该算法存在以下问题:当5名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完wait(chopstick[ i]);）筷子已被拿光,等到他们再想拿右边的筷子时（执行wait(chopstick[(i + 1)%5]);）就全被阻塞，因此出现了死锁。
为防止死锁发生，可对哲学家进程施加一些限制条件，比如至多允许4名哲学家同时进餐;仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子;对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。

制定的正确规则如下:假设采用第二种方法，当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。

图片详情

此外，还可采用AND型信号量机制来解决哲学家进餐问题，有兴趣的读者可以查阅相关资料，自行思考。

熟悉ACM或有过相关训练的读者都应知道贪心算法，哲学家进餐问题的思想其实与贪心算法的思想截然相反，贪心算法强调争取眼前认为最好的，而不考虑后续会有什么后果。若哲学家进餐问题用贪心算法来解决，即只要眼前有筷子能拿起就拿起的话，就会出现死锁。然而,若不仅考虑眼前的一步，而且考虑下一步，即不因为有筷子能拿起就拿起，而考虑能不能一次拿起两根筷子才做决定的话，就会避免死锁问题，这就是哲学家进餐问题的思维精髓。

大部分练习题和真题用消费者-生产者模型或读者-写者问题就能解决，但对于哲学家进餐问题和吸烟者问题仍然要熟悉。考研复习的关键在于反复多次和全面，“偷工减料”是要吃亏的。

吸烟者问题

问题描述:假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中,第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。

问题分析:
1）关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥（或由三个抽烟者轮流抽烟得知)。

2）整理思路。显然这里有4个进程。供应者作为生产者向三个抽烟者提供材料。

3）信号量设置。信号量offer1, offer2, offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。

代码如下:

图片详情

本节小结

本节开头提出的问题的参考答案如下。

为什么要引入进程同步的概念?

在多道程序共同执行的条件下，进程与进程是并发执行的，不同进程之间存在不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

不同的进程之间会存在什么关系?

进程之间存在同步与互斥的制约关系。

同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗?

当两个或两个以上的进程在执行过程中，因占有一些资源而又需要对方的资源时，会因为争夺资源而造成一种互相等待的现象，若无外力作用，它们都将无法推进下去。这种现象称为死锁，具体介绍和解决方案请参考下一节。

死锁

在学习本节时，请读者思考以下问题:

1）为什么会产生死锁?产生死锁有什么条件?

2）有什么办法可以解决死锁问题?

学完本节，读者应了解死锁的由来、产生条件及基本解决方法，区分死锁的避免和死锁的预防。

死锁的概念

死锁的定义

在多道程序系统中，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力。然而，多个进程的并发执行也带来了新的问题—死锁。所谓死锁，是指多个进程因竞争资源而造成的一种僵局（互相等待)，若无外力作用，这些进程都将无法向前推进。

下面通过一些实例来说明死锁现象。

先看生活中的一个实例。在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行。若有两辆汽车分别从桥的左右两端驶上该桥，则会出现下述冲突情况:此时，左边的汽车占有桥面左边的一段，要想过桥还需等待右边的汽车让出桥面右边的一段;右边的汽车占有桥面右边的一段，要想过桥还需等待左边的汽车让出桥面左边的一段。此时，若左右两边的汽车都只能向前行驶，则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如，某计算机系统中只有一台打印机和一台输入设备，进程 $P_1$ 正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程 $P_2$ 所占用，而 $P_2$ 在未释放打印机之前，又提出请求使用正被 $P_1$ 占用的输入设备。这样，两个进程相互无休止地等待下去，均无法继续执行，此时两个进程陷入死锁状态。

死锁产生的原因

系统资源的竞争

通常系统中拥有的不可剥夺资源，其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局，如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争是不会引起死锁的。

进程推进顺序非法

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁。例如，并发进程 $P_1$ , $P_2$ 分别保持了资源 $R_1$ , $R_2$ ，而进程 $P_1$ 申请资源 $R_2$ 、进程 $P_2$ 申请资源 $R_1$ 时，两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息，也会使得这些进程间无法继续向前推进。例如，进程A等待进程B发的消息，进程B又在等待进程A发的消息，可以看出进程A和B不是因为竞争同一资源，而是在等待对方的资源导致死锁。

死锁产生的必要条件

产生死锁必须同时满足以下4个条件，只要其中任意一个条件不成立，死锁就不会发生。

互斥条件:进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

不剥夺条件:进程所获得的资源在未使用完之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。

请求并保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

循环等待条件:存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待态的进程集合{ $P1$ , $P_2$ ,…, $P_n$ }，其中 $P_i$ 等待的资源被 $P{i+1}$ ( $i$ =0,1,… , $n$ -1）占有， $P_n$ 等待的资源被 $P_0$ 占有，如图2.11所示。

直观上看，循环等待条件似乎和死锁的定义一样，其实不然。按死锁定义构成等待环所要求的条件更严，它要求 $Pi$ 等待的资源必须由 $P{i+1}$ 来满足，而循环等待条件则无此限制。例如，系统中有两台输出设备， $P_0$ 占有一台， $P_K$ 占有另一台，且K不属于集合{0,1，…, n}。 $P_n$ 等待一台输出设备，它可从 $P_0$ 获得，也可能从 $P_K$ 获得。因此，虽然 $P_n$ , $P_0$ 和其他一些进程形成了循环等待圈,但 $P_K$ 不在圈内，若 $P_K$ 释放了输出设备，则可打破循环等待，如图2.12所示。因此循环等待只是死锁的必要条件。

图2.11和图2.12

资源分配图含圈而系统又不一定有死锁的原因是，同类资源数大于1。但若系统中每类资源都只有一个资源，则资源分配图含圈就变成了系统出现死锁的充分必要条件。

要注意区分不剥夺条件与请求并保持条件。下面用一个简单的例子进行说明:若你手上拿着一个苹果（即便你不打算吃)，别人不能把你手上的苹果拿走，则这就是不剥夺条件;若你左手拿着一个苹果，允许你右手再去拿一个苹果，则这就是请求并保持条件。

死锁的处理策略

为使系统不发生死锁，必须设法破坏产生死锁的4个必要条件之一，或允许死锁产生，但当死锁发生时能检测出死锁，并有能力实现恢复。

• 预防和避免的区别：参考文献

死锁预防

设置某些限制条件，破坏产生死锁的4个必要条件中的一个或几个，以防止发生死锁。

避免死锁

在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而避免死锁。

死锁的检测及解除

无须采取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生，然后采取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低;避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。

死锁的几种处理策略的比较见表2.4。

表2.4 死锁处理策略的比较

死锁预防

防止死锁的发生只需破坏死锁产生的4个必要条件之一即可。

破坏互斥条件

若允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。

破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着，一个进程已占有的资源会被暂时释放，或者说是被剥夺，或从而破坏了不剥夺条件。

该策略实现起来比较复杂，释放已获得的资源可能造成前一阶段工作的失效，反复地申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如 CPU的寄存器及内存资源，一般不能用于打印机之类的资源。

破坏请求并保持条件

采用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行，这些资源就一直归它所有，不再提出其他资源请求，这样就可以保证系统不会发生死锁。

这种方式实现简单，但缺点也显而易见，系统资源被严重浪费，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。而且还会导致“饥饿”现象，由于个别资源长期被其他进程占用时，将致使等待该资源的进程迟迟不能开始运行。

破坏循环等待条件

为了破坏循环等待条件，可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源一次申请完。也就是说，只要进程提出申请分配资源 $R_i$ ，则该进程在以后的资源申请中就只能申请编号大于 $R_i$ 的资源。

这种方法存在的问题是，编号必须相对稳定，这就限制了新类型设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序，但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费;此外，这种按规定次序申请资源的方法，也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样属于事先预防策略，但并不是事先采取某种限制措施破坏死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可以获得较好的系统性能。

系统安全状态

避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态，则允许分配;否则让进程等待。

所谓安全状态，是指系统能按某种进程推进顺序( $P_1$ , $P_2$ ,…, $P_n$ )为每个进程 $P_i$ 分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称 $P_i$ ， $P_2$ .…， $P_n$ 为安全序列。若系统无法找到一个安全序列，则称系统处于不安全状态。

假设系统中有三个进程 $P_1$ , $P_2$ ,和 $P_3$ ，共有12台磁带机。进程 $P_1$ 共需要10台磁带机， $P_2$ 和 $P_3$ 分别需要4台和9台。假设在 $T_0$ 时刻，进程 $P_1$ ， $P_2$ 和 $P_3$ 已分别获得5台、2台和2台，尚有3台未分配，见表2.5。

表2.5 资源分配

在 $T_0$ 时刻是安全的，因为存在一个安全序列 $P_2$ , $P_1$ , $P_3$ ，只要系统按此进程序列分配资源，那么每个进程都能顺利完成。也就是说，当前可用磁带机为3台，先把3台磁带机分配给 $Р_2$ 以满足其最大需求， $P_2$ 结束并归还资源后，系统有5台磁带机可用;接下来给 $P_1$ 分配5台磁带机以满足其最大需求， $P_1$ 结束并归还资源后，剩余10台磁带机可用;最后分配7台磁带机给 $P_3$ ，这样$P_3$也能顺利完成。

若在 $T_0$ 时刻后，系统分配1台磁带机给 $P_3$ ，系统剩余可用资源数为2，此时系统进入不安全状态，因为此时已无法再找到一个安全序列。当系统进入不安全状态后，便可能导致死锁。例如，把剩下的2台磁带机分配给 $P_2$ 这样， $P_2$ 完成后只能释放4台磁带机，既不能满足 $P_1$ 又不能满足 $P_3$ ，致使它们都无法推进到完成，彼此都在等待对方释放资源，陷入僵局，即导致死锁。

并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态;反之，只要系统处于安全状态，系统便可避免进入死锁状态。

银行家算法

银行家算法是最著名的死锁避免算法，其思想是:把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

数据结构描述

可利用资源向量Available:含有m个元素的数组，其中每个元素代表一类可用的资源数目。Available[ j ]=K表示系统中现有 $R_j$ 类资源K个。

最大需求矩阵 Max: n×m 矩阵，定义系统中 $n$ 个进程中的每个进程对 $m$ 类资源的最大需求。简单来说，一行代表一个进程，一列代表一类资源。Max[ i,j ]=K表示进程i需要 $R_j$ 类资源的最大数目为K。

分配矩阵Allocation: $n \times m$ 矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation[ i,j ]=K表示进程 $i$ 当前已分得 $R_j$ 类资源的数目为K。初学者容易混淆Available向量和Allocation矩阵，在此特别提醒。

需求矩阵Need: $n \times m$ 矩阵，表示每个进程接下来最多还需要多少资源。Need[ i,j ]=K表示进程i还需要 $R_j$类资源的数目为K。

上述三个矩阵间存在下述关系:

Need= Max- Allocation

一般情况下，在银行家算法的题目中，Max矩阵和Allocation矩阵是已知条件，而求出 Need矩阵是解题的第一步。

银行家算法描述

银行家算法描述

安全性算法举例

图片详情

银行家算法举例

图片详情

死锁检测和解除

前面介绍的死锁预防和避免算法，都是在为进程分配资源时施加限制条件或进行检测，若系统为进程分配资源时不采取任何措施，则应该提供死锁检测和解除的手段。

资源分配图

系统死锁可利用资源分配图来描述。如图2.13所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为 $\color{green}{\text{请求边}}$ ，表示该进程申请一个单位的该类资源;从资源到进程的边称为 $\color{green}{\text{分配边}}$ ，表示该类资源已有一个资源分配给了该进程。

在图2.13所示的资源分配图中，进程 $P_1$ 已经分得了两个 $R_1$ 资源，并又请求一个 $R_2$ 资源;进程 $P_2$ ,分得了一个 $R_1$ 资源和一个 $R_2$ 资源，并又请求一个 $R_1$ 资源。

图2.13 资源分配示例

死锁定理

简化资源分配图可检测系统状态S是否为死锁状态。简化方法如下:

1）在资源分配图中，找出既不阻塞又不孤点的进程 $P_i$ (即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中己有的空闲资源数量，如在图2.13中， $R_1$ 没有空闲资源， $R_2$ 有一个空闲资源。若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配边，使之成为孤立的结点。在图2.14(a)中， $P_1$ 是满足这一条件的进程结点，将P的所有边消去，便得到图2.14(b)所示的情况。

这里要注意一个问题，判断某种资源是否有空间，应用它的资源数量减去它在资源分配图中的出度，例如在图2.13中， $R_1$ 的资源数为3，而出度也为3，所以 $R_1$ 没有空闲资源, $R_2$ 的资源数为2，出度为1，所以 $R_2$ 有一个空闲资源。

2）进程 $P_i$ 所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2.13中，进程 $P_2$ 就满足这样的条件。根据1)中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，如图2.14(c)所示。

图2.14 资源分配图的化简

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为 $\color{green}{\text{死锁定理}}$ 。

死锁解除

一旦检测出死锁，就应立即采取相应的措施来解除死锁。死锁解除的主要方法有:

1） $\color{green}{\text{资源剥夺法}}$ 。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。

2） $\color{green}{\text{撤销进程法}}$ 。强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

3） $\color{green}{\text{进程回退法}}$ 。让一（或多〉个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。

本节小结

本节开头提出的问题的参考答案如下。

1）为什么会产生死锁?产生死锁有什么条件?

由于系统中存在一些不可剥夺资源，当两个或两个以上的进程占有自身的资源并请求对方的资源时，会导致每个进程都无法向前推进，这就是死锁。死锁产生的必要条件有4个，分别是互斥条件、不剥夺条件、请求并保持条件和循环等待条件。

互斥条件是指进程要求分配的资源是排他性的，即最多只能同时供一个进程使用。

不剥夺条件是指进程在使用完资源之前，资源不能被强制夺走。

请求并保持条件是指进程占有自身本来拥有的资源并要求其他资源。

循环等待条件是指存在一种进程资源的循环等待链。

2）有什么办法可以解决死锁问题?

死锁的处理策略可以分为预防死锁、避免死锁及死锁的检测与解除。

死锁的预防是指通过设立一些限制条件，破坏死锁的一些必要条件，让死锁无法发生。

死锁的避免是指在动态分配资源的过程中，用一些算法防止系统进入不安全状态，从而避免死锁。

死锁的检测和解除是指在死锁产生前不采取任何措施，只检测当前系统有没有发生死锁，若有，则采取一些措施解除死锁。

本章疑难点

进程与程序的区别与联系

1）进程是程序及其数据在计算机上的一次运行活动，是一个动态的概念。进程的运行实体是程序，离开程序的进程没有存在的意义。从静态角度看，进程是由程序、数据和进程控制块（PCB）三部分组成的。而程序是一组有序的指令集合，是一种静态的概念。

2）进程是程序的一次执行过程，它是动态地创建和消亡的，具有一定的生命周期，是暂时存在的;而程序则是一组代码的集合，是永久存在的，可长期保存。

3）一个进程可以执行一个或几个程序，一个程序也可构成多个进程。进程可创建进程，而程序不可能形成新的程序。

4）进程与程序的组成不同。进程的组成包括程序、数据和PCB。

死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件，而该事件只能由这些等待进程之一来产生。这里的事件是V操作的执行（即释放资源)。出现这样的状态时，这些进程称为死锁(Deadlocked)。

为加以说明，考虑一个由两个进程 $P_0$ 和 $P_1$ 组成的系统，每个进程都访问两个信号量S和Q,这两个信号量的初值均为1。

图片详情

假设进程 $P_0$ 执行P(S)，接着进程 $P_1$ 执行P(Q)。当进程 $P_0$ 执行P(Q)时，它必须等待，直到进程 $P_1$ 执行V(Q)。类似地，当进程 $P_1$ 执行P(S)时，它必须等待，直到进程 $P_0$ 执行V(S)。由于这两个V操作都不能执行，因此进程 $P_0$ 和进程 $P_1$ 就死锁了。

一组进程处于死锁状态是指组内的每个进程都在等待一个事件，而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞（Indefinite Blocking）或饥饿(Starvation)，即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是:在一个动态系统中，对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的，即不能保证等待时间上界的存在。在这种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程“饥饿”，当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时，称该进程被“饿死”。

例如，当有多个进程需要打印文件时，若系统分配打印机的策略是最短文件优先，则长文件的打印任务将由于短文件的源源不断到来而被无限期推迟，导致最终“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定会死锁，但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别如下:

1）进入“饥饿”状态的进程可以只有一个，而因循环等待条件而进入死锁状态的进程却必须大于等于两个。

2）处于“饥饿”状态的进程可以是一个就绪进程，如静态优先权调度算法时的低优先权进程，而处于死锁状态的进程则必定是阻塞进程。

银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行分配，并对分配后的新状态进行安全性检查。若新状态安全，则正式分配上述资源，否则拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免了死锁现象的发生。

进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:一种是进程之间竞争使用临界资源，只能让它们逐个使用，这种现象称为互斥，是一种竞争关系;另一种是进程之间协同完成任务，在关键点上等待另一个进程发来的消息，以便协同一致，是一种协作关系。

作业和进程的关系

进程是系统资源的使用者，系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务，通常把用户要求计算机完成的这一串任务称为作业。

批处理系统中作业与进程的关系（进程组织)

批处理系统可以通过磁记录设备或卡片机向系统提交批作业，由系统的SPOOLing输入进程将作业放入磁盘的输入井，作为后备作业。作业调度程序（一般也作为独立的进程运行）每当选择一道后备作业运行时，首先为该作业创建一个进程（称为该作业的根进程)。该进程将执行作业控制语言解释程序，解释该作业的作业说明书。父进程在运行过程中可以动态地创建一个或多个子进程，执行说明书中的语句。例如，对一条编译的语句，该进程可以创建一个子进程执行编译程序对用户源程序进行编译。类似地，子进程也可继续创建子进程去完成指定的功能。因此,一个作业就动态地转换成了一组运行实体—进程族。当父进程遇到作业说明书中的“撤出作业”语句时，将该作业从运行态改变为完成态，将作业及相关结果送入磁盘上的输出井。作业终止进程负责将输出井中的作业利用打印机输出，回收作业所占用的资源，删除作业有关的数据结构,删除作业在磁盘输出井中的信息等。作业终止进程撤除一道作业后，可向作业调度进程请求进行新的作业调度。至此，一道进入系统运行的作业全部结束。

分时系统中作业与进程的关系

在分时系统中，作业的提交方法、组织形式均与批处理作业有很大差异。分时系统的用户通过命令语言逐条与系统应合八把武大系体自动时，系统为每个终端设备建立一个进程（称为终端统内部对应一个(以右T经程序，命令解释程序从终端设备读入俞令，解藉疯令是一茶后台命进程)，该进程执仃类令n可以创建一个子进程去具体执行。若当HPN根据需要创建子孙进程。条命令。对于每条终端命令，可以创建一个子进程去具体执行。若当前的终端命令是一条后台命令，则可以和下一条终端命令并行处理。各子进程在运行过程中完全可以根据需要创建子孙进程。终端命令所对应的进程结束后，命令的功能也相应处理完毕。用户本次上机完毕，用户通过一条登出命令即结束上机过程。

分时系统的作业就是用户的一次上机交互过程，可以认为终端进程的创建是一个交互作业的开始，登出命令运行结束代表用户交互作业的终止。

命令解释程序流程扮演着批处理系统中作业控制语言解释程序的角色，只不过命令解释程序是从用户终端接收命令。

交互地提交批作业

在同时支持交互和批处理的操作系统中，人们可以用交互的方式准备好批作业的有关程序、数据及作业控制说明书。比如，可用交互式系统提供的全屏幕编辑命令编辑好自编的一个天气预报程序，用编译及装配命令将程序变成可执行文件，用调试命令进行程序调试。调试成功后，用户每天都要做如下工作:准备原始天气数据，运行天气预报执行文件处理原始数据，把结果打印出来等。这时，用交互系统提供的全屏幕编辑命令编辑好将要提交的作业控制说明书文件，如Windows系统的 bat 文件和 Linux系统的sh文件。然后用一条作业提交命令将作业提交到系统作业队列中。系统有专门的作业调度进程负责从作业队列中选择作业，为被选取的作业创建一个父进程运行命令解释程序，解释执行作业控制说明书文件中的命令。

各种调度算法的特点

各种调度算法的特点