2.1 知识要点总结

一、进程与线程

1．进程概念

（1）进程的引入

程序顺序执行时具有顺序性、封闭性、以及可再现性。但在多道程序环境下，可以有多个程序并发执行，此时它们封闭性和可再现性被破坏，具有间断性及不可再现性的特征。并且并行执行的程序共享系统资源，将产生相互制约关系，程序与CPU执行的活动之间也将不再一一对应。所以为了更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性，引入了进程（Process）的概念。

（2）进程的定义

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

①进程是程序的一次执行

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

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

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

（3）进程的特征

进程是由多道程序的并发执行而引出的，它和程序是两个截然不同的概念。进程的特点包括：动态性、并发性、独立性、异步性和结构性。

①动态性，进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。进程实体有一定的生命期，故进程动态性表现在：“它由创建而产生，由调度而执行，由撤消而消亡”。

②并发性，指多个进程实体同存于内存中，且能在一段时间内同时运行。并发性既是进程的重要特征也是操作系统的重要特征。

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

④异步性，指进程按各自独立的、不可预知的速度向前推进。

⑤结构性，指为了程序能并发执行，为其配置进程控制块即PCB（ProcessControlBlock），由程序段、相关的数据段和PCB三部分便构成了进程实体。

（4）进程控制块PCB

进程控制块PCB也叫做进程描述符（ProcessDescriptor），用于记录进程的运行变化过程。PCB是进程存在的唯一标识，它包含了进程的描述信息和管理控制信息，是进程动态特性的集中表现。操作系统依据进程控制块来管理和调度系统中的进程。所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB。

进程控制块包含的内容有：①进程标识数；②进程的状态以及调度和存储器管理信息；③进程使用的资源信息；④CPU现场保护区；⑤记账信息以及进程的链接指针。

（5）进程与程序的联系与区别

①进程是程序的一次执行，它是一个动态的概念；程序是完成某个特定功能的指令的有序序列，它是一个静态的概念；

②进程是系统进行资源分配和调度的一个独立单位，程序则不是；

③进程是具有结构的，程序没有结构。

【例】下面对进程的描述中，错误的是（　）。

A．进程是有生命期的

B．进程是动态的概念

C．进程是指令的集合

D．进程执行需要处理机

【答案】C

【解析】进程可以理解为：可并发执行的程序在一个数据集上的运行过程，是系统进行资源（如：CPU、内存、设备、文件、数据等）分配和调度的独立单位；进程的存在有一定的时间周期，它是一个动态的概念，有三种状态：执行状态、就绪状态和等待状态；当除CPU外其他资源都就绪时，进程处于就绪状态，当进程得到CPU时（根据进行调度算法，得到CPU），在得到的CPU时间片中，处于执行状态；当CPU时间片用完或其他资源不就绪时，进入等待状态；由此可见进程是抽象的，和程序不同，不是指令的集合。

2．进程的状态与转换

进程在其生命周期内，由于系统中各进程之间的相互制约关系及系统的运行环境的变化，使得进程的状态也在不断地发生变化，为了表示这些不同状态，为进程定义了五种状态：就绪状态、运行状态、阻塞状态、创建状态以及结束状态，其中前三种是进程的基本状态。

（1）进程的状态

①就绪状态，是指进程已分配到除CPU以外的所有必要资源，就只需等待CPU，一旦获得CPU，便可立即执行。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。

②运行状态，又称执行状态，指进程已经获得CPU，其程序正在执行。需要注意的是在单处理机系统中，每个时刻最多只有一个进程处于运行状态；而在多处理机系统中，则可以有多个处于运行状态的进程。

③阻塞状态，又称等待状态，指进程因为发生某事件而暂时无法继续执行不得不放弃处理机所进入的状态，致使进程进入阻塞的典型事件有：请求I/O、申请缓冲空间等。当进程所等待的事件完成后，进程将进入就绪状态。在一个系统中处于阻塞状态的进程可能有多个，通常将它们排成一个队列，称为阻塞列列。

④创建状态，进程被创建时的状态，在该状态下，主要的操作有申请空白PCB，根据进程信息向PCB中填写控制和管理该进程的信息，以及由系统为该进程分配所必需的资源。

⑤结束状态，进程从系统中消亡时的状态，在该状态下，主要的操作有回收进程的资源，清除进程相关信息。

（2）进程状态的转换

一个进程从无到有，执行完任务而消亡，通常经历创建态、就绪态、运行态、等待态和终止态5个状态的变换。进程五种状态间的转换如图2-1所示：

①就绪态→运行态，处于就绪队列中的进程通过进程调度获得CPU进入运行状态。

②运行态→阻塞态。当进程请求某一资源（如外设）的使用和分配或等待某一事件的发生（如I/O操作的完成）时，它就从运行状态转换为阻塞状态。

③运行态→就绪态。运行态进入就绪态有两种情况：

a．处于运行状态的进程时间片用完了，进入就绪态等待下一次的调度；

b．剥夺式调度中，当有更高优先级的进程就绪时，当前正在运行的进程让出CPU给高优先级进程，自己进入就绪状态。

④阻塞态→就绪态。阻塞进程等待的某个事件发生了，则该进程被唤醒进入就绪状态。如I/O操作完成或中断结束时，则应把因其阻塞的进程唤醒进入就绪状态。

需要注意的是，一个进程从运行状态变成阻塞状态是一个主动的行为，而从阻塞状态变到就绪状态是一个被动的行为，需要其他相关进程的协助。

【例】进程从运行状态进入就绪状态的原因可能是（　）。

A．被选中占有处理机

B．等待某一事件

C．等待的事件已发生

D．时间片用完

【答案】D

【解析】进程被选中占用处理机是进入运行状态。进程等待某一事件发生会进入阻塞状态。等待的事件已发生会促使进程由阻塞状态进入就绪状态。时间片用完时，进程会进入就绪状态，等待调度程序的下一次时间片分配。

3．进程控制

系统中的进程在运行过程中不断地产生和消亡。或者说，进程生命周期包括产生、存在、进程状态转换、消亡而最终撤离系统的，整个过程是由进程控制来管理和实现的。进程控制功能是由操作系统内核中的原语来实现的。进程控制包括进程的创建、进程的撤销、进程的阻塞、进程的唤醒、进程的挂起和激活以及进程的切换等。

（1）原语的概念

原语是机器指令的延伸，是由若干条机器指令构成、运行在核心态的、用以实现特定功能的一段程序。为了保证操作的正确性，原语在执行的过程中是不可分割的，也即其执行过程是不允许中断的，换言之原语操作要么不做要么全做。

（2）进程的创建

①引起进程创建的典型事件

在操作系统中，引起创建进程的典型事件有：a．用户登录；b．作业调度；c．提供服务；d．应用请求。其中前三种情况都是由系统内核为创建一个新进程，而d类事件应用进程自己创建一个新进程，以便使新进程以并发运行方式完成特定任务。由此可以看出操作系统是允许一个进程创建另一个进程的，创建者称为父进程，被创建的进程称为子进程。子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，也必须同时撤销其所有的子进程。

②创建进程所做的操作即进程创建原语

a．申请空白PCB；

b．为新进程分配资源；

c．初始化进程控制块PCB，填写一些控制和管理进程的信息；

d．将新进程插入就绪队列。

（3）进程的撤销

①引起进程撤销的原因

在操作系统中，引起进程撤销的原因有：

a．正常结束，正常结束即表示进程已经运行完成；

b．异常结束，异常结束是指在进程运行期间，出现某些错误和故障而迫使进程终止，这类异常事件很多，常见的有下述几种：越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错以及I/O故障；

c．外界干预，而外界干预是指进程因外界的请求而终止运行，常见的干预有：操作员或操作系统干预、父进程请求、以及父进程终止。

②撤销进程所做的操作即进程撤销原语

a．从PBC集合中检索出待消亡进程的PCB；

b．若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真以指示新的进程调度；

c．若被终止进程有子孙进程，应终止其子孙进程，以防其成为不可控的进程；

d．收回被终止进程所占资源，若其有父进程则归还给父进程，否则归还给系统；

e．将被终止进程从所在队列中移出。

（4）进程的阻塞

①引起进程阻塞的事件

在操作系统中，引起进程阻塞的事件有：

a．请求系统服务，正在执行的进程请求操作系统提供服务，由于某种原因，操作系统并不立即满足该进程的要求时，该进程只能转变为阻塞状态来等待；

b．启动某种操作，当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行，则必须先使该进程阻塞，以等待该操作完成；

c．新数据尚未到达，对于相互合作的进程，如果其中一个进程需要先获得另一（合作）进程提供的数据后才能对数据进行处理，则只要其所需数据尚未到达，该进程只有（等待）阻塞；

d．无新工作可做，系统往往设置一些具有某特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。

②阻塞进程所做的操作即进程阻塞原语如下：

a．从PCB集合中检索到相应PCB；

b．若该进程为运行状态，则立即停止执行保护现场，将相应PCB中的现行状态由“执行”改为“阻塞”；

c．把该PCB插入到相应事件的等待队列中去。

（5）进程的唤醒

当被阻塞进程所等待的事件发生时，如其所期待的数据已经到达或是I/O操作完成，则应调用唤醒原语wakeup（　）将等待该事件的进程唤醒。

唤醒进程所做的操作即进程唤醒原语如下：

①在该事件的等待队列中检索到相应进程的PCB。

②将其从等待队列中移出，并将相应PCB中的现行状态由“阻塞”改为“就绪”；

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

需要注意的是，Block（　）原语和Wakeup（　）原语是一对作用刚好相反的原语，必须成对使用。否则被阻塞进程将会因不能被唤醒而长久地处于阻塞状态，从而再无机会继续运行。

（6）进程的挂起和激活

①引起进程挂起的原因

在操作系统中，引起进程阻塞的事件有：

a．用户进程请求将自己挂起；

b．父进程请求将自己的某个子进程挂起；

c．系统将利用挂起原语suspend（　）将指定进程或处于阻塞状态的进程挂起。

②进程挂起的所做的操作即进程挂起原语如下：

a．从PCB集合中检索到相应PCB；

b．检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。

③进程的激活

当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的该进程换入内存。系统将利用激活原语active（　）将指定进程激活，其过程如下：

a．从PCB集合中检索到相应PCB；

b．检查被激活进程的状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。

（7）进程的切换

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

①进程切换的所做的操作如下：

a．保存处理机上下文，主要是相关寄存器的内容比如程序计数器；

b．更新被调度出进程的PCB信息；

c．把被调度出进程的PCB根据进程状态移入相应的队列，如就绪、在某事件阻塞等队列；

d．选择另一个进程执行，并更新其PCB；

e．更新内存管理的数据结构；

f．恢复处理机上下文。

【例】一个进程被唤醒意味着（　）。

A．该进程马上占有CPU

B．进程状态变为就绪

C．进程的优先权变为最大

D．其PCB移至就绪队列的队首

【答案】B

【解析】进程占有CPU是处于运行态。进程被唤醒，是指当进程需等待的事件发生时，进程会由挂起或阻塞态转变为就绪态，根据相应的调度算法插入到就绪队列的相应位置，不一定插在队首，进程的优先权可能会发生变化，也可能不变。

4．进程组织

为了便于管理和调度，系统常常把各个进程的控制块用某种方法组织起来，常用的组织方式有两种：链接方式和索引方式。

（1）链接方式

这是把具有同一状态的PCB，用其中的链接字链接成一个队列，例如就绪队列、阻塞队列等。其中的就绪队列常按进程优先级的高低排列，而阻塞队列也可以根据阻塞原因的不同形成不同的阻塞队列。

（2）索引方式

系统根据所有进程的状态建立几张索引表，例如就绪索引表、阻塞索引表等，而当系统要查找相关进程的PCB时则在相关索引表里进行索引。

5．进程通信

在操作系统中，进程主要通过三种方式来进行通信：共享存储系统、消息传递系统以及管道通信。

（1）共享存储系统

基于共享存储系统的通信方式可分为两种：共享数据结构方式和共享存储区的方式。

①共享数据结构的通信方式，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。这种方式中的公用数据结构的设置及对进程间同步的处理，都是程序员的职责。因此，这种通信方式是低效的，只适于传递相对少量的数据。

②共享存储区的通信方式，为了传输大量数据，在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。

需要注意的是在共享存储系统中，通信进程对共享空间需要使用同步互斥工具（比如PV操作）来对共享空间的写/读进行控制。

（2）消息传递系统

在消息传递机制中，进程间的数据交换是以格式化的消息（message）为单位的。在这种方式中，程序员可以直接利用操作系统提供的一组通信命令（原语），实现大量数据的传递的同时隐藏了通信的实现细节，故该方式获得了广泛的应用。因其实现方式的不同可分为直接通信方式和间接通信方式两种。

①直接通信方式

该方式是指指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程，并将它挂在接收进程的消息缓冲队列上，接收进程只需从消息缓冲队列中取得消息。不过这种方式要求发送进程和接收进程都以显式方式提供对方的标识符。

②间接通信方式

该方式发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。需要注意的是信箱可由操作系统创建，也可由用户进程创建。

（3）管道通信

管道通信是消息传递的一种特殊方式。管道（pipe）是指用于连接一个写进程和一个读进程按照先进先出方法实现它们之间通信的共享文件，又称为pipe文件。它由操作系统核心管理的缓冲区来实现，是单向的通信方式。

发送进程以字符流的形式将大量的数据源源不断地写入管道，接收进程从管道中接收数据。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。需要注意的是从管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放间以便写更多的数据。管道只能采用半双工通信，即某一时刻只能单向传输。

6．线程概念与多线程模型

（1）线程的引入

因为进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之付出较大的时空开销。为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性，所以在操作系统中引入了线程，实现更轻量级的处理机调度。

（2）线程的定义

线程最直接的理解就是“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，是被系统独立调度和分派的基本单位．线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。

需要注意的是引入线程后，进程的内涵发生了改变，进程只作为除处理机以外系统资源的分配单元，线程则作为处理机的分配单元。

（3）线程与进程的区别

为了更好地认识进程和线程，下面从拥有的资源、调度和并发性诸方面对两者进行比较。

①调度，在没有引入线程的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。在引入线程的操作系统中，则把线程作为调度和分派的基本单位，把资源拥有和处理机调度两个属性分开。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。

②并发性，在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，使得操作系统具有更好的并发性。

③拥有资源，无论在何种操作系统中，进程都是系统中拥有资源的一个基本单位。线程只拥有自己必不可少的一点资源，它可以访问其隶属进程的资源。

④系统开销，因为进程是系统资源分配的基本单位，所以创建或撤销进程时，系统都要为之创建和回收进程控制块，分配或回收资源，因此操作系统所付出的开销远大于创建或撤销线程时的开销。并且线程切换时只需保存和设置少量寄存器内容，开销很小。

⑤通信，由于一个进程中的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易。

⑥地址空间和其他资源，进程的地址空间之间互相独立，同一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见。

【例】进程与线程的根本区别是（　）。

A．进程要占用一个进程控制块，开销较大，而线程无此开销

B．进程增加会增加死锁的机会，而线程有效避免了这一问题

C．进程是资源分配单位，而线程是调度和执行的单位

D．进程是调度和执行单位，而线程是资源分配单位

【答案】C

【解析】线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。线程和进程的区别在于，子进程和父进程有不同的代码和数据空间，而多个线程则共享数据空间，每个线程有自己的执行堆栈和程序计数器为其执行上下文．多线程主要是为了节约CPU时间。

（4）线程的属性

在多线程OS中，通常是在一个进程中包括多个线程，每个线程都是作为利用CPU的基本单位，是花费最小开销的实体，线程具有下述属性：

①轻型实体，线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证其独立运行的资源，比如控制线程的线程控制TCB，用于指示被执行指令序列的程序计数器，保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。

②独立调度和分派的基本单位，在多线程OS中，线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位，并且线程的切换非常迅速且开销小。

③可并发执行，在一个进程中的多个线程之间可以并发执行；同样，不同进程中的线程也能并发执行。

④共享进程资源，在同一进程中的各个线程都可以共享该进程所拥有的资源，所有线程都具有相同的地址空间（进程的地址空间）。

（5）线程的实现方式

系统对线程的实现方式有3种：用户级线程、内核级线程和两级组合方式。

①用户级线程，用户级线程仅存在于用户空间中，它是由用户程序通过调用用户态运行的线程库完成的，线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现，系统内核并不知道线程的存在。

②内核级线程，内核级线程是在内核的支持下运行的，内核空间为每一个内核线程设置一个线程控制块，内核是根据该控制块而感知某线程的存在，并对其加以控制，他们的创建、撤消和切换等也是依靠内核。

③组合方式，组合方式线程系统中，内核支持多内核级线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。组合方式多线程机制能够结合内核级和用户级两者的优点，并克服了其各自的不足。

（6）多线程模型

引入线程后，进程只作为操作系统中进行保护和资源分配的单位，允许一个进程有多个线程并发执行，线程切换不必通过进程调度，多线程借助共享内存区实现通信，通信容易实现。这大大减少了系统开销和提高了系统效率。

多线程引入，在单处理机和多处理机系统中，一个进程内的多线程不仅可以并发执行，而且可以被调度到不同的处理机，进程中的多线程还可以并行运行，大大加快了进程的完成速度，多线程模型有如下几种：

①多对一模型，将多个用户级线程映射到一个内核级线程，为了方便管理，这些用户线程一般属于一个进程，线程管理在该进程的用户空间完成。当用户线程需要访问内核时，才将其映射到内核线程上，用户级线程对操作系统透明。这种方式的优点是效率比较高，但是当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。

②一对一模型，为每一个用户线程都设置一个内核线程与之连接。这种方式的优点是：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强；缺点是：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。

③多对多模型，该模型综合上述两种模型的优点，将n个用户级线程映射到m个内核级线程上，要求m≤n。内核控制线程的数目可以根据应用进程和系统的不同而变化。

二、处理器调度

1．调度的基本概念

在多道程序系统中，进程的数量往往多于处理机的个数，进程争用处理机的情况就在所难免，所以引入了处理机调度。调度按照调度对象的不同可以分为高级、中级和低级调度。

（1）高级调度

高级调度又称为作业调度，根据作业控制块中的信息，按照一定算法从外存上处于后备状态的作业中挑选某些作业调入内存，为它们创建进程，分配必要资源，然后再将新创建进程插入就绪队列。简言之，就是内存与辅存之间的调度。对于每个作业只调入一次、调出一次。

（2）中级调度

中级调度又称内存调度，是将那些暂时不能运行的进程调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。而当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

（3）低级调度

低级调度又称进程调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，可分为非抢占方式和抢占方式两种。

（4）三级调度的联系

处理机的三级调度关系图如下图所示：

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

2．调度时机、切换与过程

（1）进程的调度时机

进程调度的时机，是指什么时候引起进程调度程序工作。由上述的调度方式．可以得出如下调度的时机：

①现行进程完成执行或由于某种错误而中止运行；

②正在执行的进程提出I/O请求，等待I/O完成；

③在分时系统，按照时间片轮转，分给进程的时间片用完；

④优先级调度，由更高优先级进程变为就绪；

⑤进程执行了某种操作原语，如阻塞原语或唤醒原语时，都可能引起进程调度。

（2）进程调度的切换过程

处理机调度工作是通过处理机调度程序来完成的。处理机调度程序的主要功能可描述如下：

①保存被中断进程的处理机现场信息；

②修改被中断进程的进程控制块的有关信息，如进程状态等。

③把被中断进程的进程控制块插入有关队列；

④选择一个进程占有CPU；

⑤修改被选中进程的进程控制块的有关信息，如进程状态等；

⑥根据被选中进程的进程控制块的处理机现场信息恢复处理机现场。

3．调度的基本准则

不同的操作系统，其处理机调度依据的准则不同，采用的调度算法也不同。一个好的调度算法，应该使系统的性能更好。其中主要考虑的因素有：资源利用率、吞吐量、周转时间、等待时间和响应时间。

（1）资源利用率

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

（2）吞吐量

吞吐量表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理机时间，因此会降低系统的吞吐量。而对于短作业，它们所需要消耗的处理机时间较短，因此能提高系统的吞吐量。根据调度算法的不同，对系统吞吐量会产生较大的影响。

（3）周转时间

周转时间是指从作业提交到作业完成所经历的时间，包括作业等待、在就绪队列中排队、在处理机上运行以及进行输入/输出操作所花费时间的总和。

（4）等待时间

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

（5）响应时间

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

显然这些因素相互之间是矛盾的，因此在设计操作系统时，应根据类型不同进行权衡，以达到较好的效果。对批处理系统，主要考虑作业的周转时间和带权周转时间。周转时间越短，系统的吞吐量越大。根据作业的性质，均衡调度作业，会大大提高系统资源的利用。对于分时系统，则更多考虑的是响应时间。在此基础上，才考虑资源的利用。对于实时系统，则更多考虑的是对外部事件的及时响应和处理以及系统的安全可靠性，在此基础上，才考虑资源的利用。

4．调度方式

进程调度是操作系统中最基本的一种调度，可分为非抢占方式和抢占方式两种。

（1）非抢占方式

在采用非抢占调度方式时，调度程序一旦把CPU分配给某一进程后便让它一直运行下去，直到进程完成或发生某事件（比如时间片用完、阻塞等待I/O完成等）而不能运行时。可能引起进程调度的因素可归结为这样几个：

①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；

②执行中的进程因提出I/O请求而暂停执行；

③在进程通信或同步过程中执行了某种原语操作。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。

（2）抢占方式

在采用抢占调度方式时，当一个进程正在执行时，系统可以基于某种策略剥夺CPU给其他进程。进行抢占的原则有：①优先权原则；②短作业（进程）优先原则；③时间片原则。这种调度方式更多用在分时系统和实时系统中，以便及时响应各进程的执行。

5．典型调度算法

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

先来先服务调度算法是系统维护一个FIFO队列，它按照作业或进程到达队列的先后次序顺序调度运行。FCFS调度算法属于不可剥夺算法，其优点是节省机器时间，但效率不高。其主要缺点是容易被大作业进程垄断，使得平均等待时间很长。

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

短作业优先算法要求每个作业的进程提供所需的运行时间，每次调度时总是选取运行时间最短的进程运行。这种算法对于运行时间短的进程有利，进程的平均等待和周转时间最佳，也容易实现，但容易出现长作业得不到运行而饿死的现象。

（3）时间片轮转调度算法

时间片轮转法通常用在分时系统中，它轮流地调度系统中所有就绪进程。在实现时，它利用一个定时时钟，使之定时地发出中断。时钟中断处理程序在设置新的时钟常量后，即转入进程调度程序，选择一个新的进程占用CPU。时间片长短的确定遵循这样的原则：既要保证系统各个用户进程及时地得到响应，又不要由于时间片太短而增加调度的开销，降低系统的效率。

（4）优先级调度算法

优先级调度算法调度时，总是将CPU分配给就绪队列中优先级最高的进程。通常确定优先级的方法有两种，即静态优先级法和动态优先级法。

①静态优先级法。它依据进程的类型是用户进程还是系统进程。通常赋予系统进程较高优先级；对于用户进程，根据申请资源的多少，申请资源量少的赋予较高优先级。

②动态优先级法，是指进程在开始创建时，根据某种原则确定一个优先级后，随着进程执行时间的变化，其优先级不断地进行动态调整。

（5）高响应比优点调度算法

响应比高者优先调度法兼顾了短作业和长作业。每当调度作业时，都要计算各个作业的响应比，总是选择响应比高的作业运行。虽然该算法兼顾了短作业和长作业，但是由于每当进行作业调度时，系统都需要花费大量时间计算响应比，故系统开销比较大。

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

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

多级反馈队列调度算法的操作过程如下所示：

①应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。

②当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，„„，如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。

③仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～（i-1）队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列（第1～（i-1）中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

多级反馈队列的优势有：①终端型作业用户，短作业优先。②短批处理作业用户，周转时间较短。③长批处理作业用户，经过前面几个队列得到部分执行，不会长期得不到处理。

三、进程同步与互斥

1．进程同步的基本概念

（1）临界资源和临界区的概念

①临界资源：指系统中仅允许一个进程使用的资源，若几个进程同时使用，可能会造成资源状态出现错误。这些资源既包括慢速的硬件设备，如打印机等资源，也包括软件资源，如共享变量、各种队列、各种表格、共享文件等。

②临界区：并发进程访问临界资源的那段代码。

（2）同步和互斥的概念

在多道程序环境下，进程是并发执行的，系统中的并发进程之间存在的两种相互制约关系：分别是协作（又叫同步）和竞争（又叫互斥）。

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

②互斥，是指进程由于共享系统资源而引起的一种间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

（3）同步机制应遵循的准则

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

①空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

②忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

③有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。

④让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

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

实现临界区互斥的方法分为两种：软件实现方式和硬件实现方法。

（1）软件实现方式

软件实现方式为了实现互斥，在进入区设置和检查一些标志来标明是否有进程在临界区中，如果已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

软件方式的实现过程为：当进程Pi想进入自己的临界区时，会把自己的标志位置inside-i置为true，然后继续执行并检查对方的标志位。若对方的标志位为false，则表明对方不在也不想进入临界区，进程Pi可以立即进入的临界区；否则，咨询指指示器turn。若turn为i，那么Pi知道应该自己进入，从而反复测试Pj的标志位inside-j; Pj注意到应该礼让对方Pi，故其把自己的标志位inside-j置为false，允许进程Pi进入临界区。在进程Pi退出临界区时，把自己的标志位置位false，且把turn置为j，从而把进入临界区的权利交给进程Pj，从而实现了互斥。

（2）硬件实现方法

用关中断、测试和设置指令（testandset）、交换指令等硬件指令可解决进程之间的互斥。分为中断屏蔽方法以及硬件指令方法。

①中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，首先关中断防止其他进程再进入其临界区访问。因为CPU只在发生中断时引起进程切换，这样关中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为：

关中断；

临界区；

开中断；

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

②硬件指令方法

硬件指令方法由硬件逻辑直接实现的，不会被中断。实现互斥常用的硬件指令有两种TestAndSet指令和Swap指令。

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

                    boolean TestAndSet（boolean &target）{
                      boolean rv=target；
                      target=true；
                      return rv；
                  }

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

                While（TestAndSet（lock））；
                  进程的临界区代码段；
                      lock=false；
                  进程的其他代码；

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

              void Swap（boolean &a, boolean &b）{
                      boolean temp=a；
                      a=b；
                      b=temp；
                    }

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

                      key=true;
                    while（key==true）
                     Swap（lock, key）;
                    进程的临界区代码段；
                      lock=false;
                    进程的其他代码；

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

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

3．信号量

信号量表示资源的物理实体，信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait（S）和signal（S）来访问，也可以记为“P操作”和“V操作”。常用的信号量整型信号量、记录型信号量以及AND型信号量。

（1）常用信号量

①整型信号量

整型信号量是把信号量定义为一个整型量，仅能通过两个标准的原子操作（AtomicOperation）wait（S）和signal（S）来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述如下：

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

②记录型信号量

整型信号量机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但是会出现多个进程等待访问同一临界资源的情况，所以除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程，记录型信号量是由于采用了记录型的数据结构而得名的。记录型信号量可描述为：

相应的wait（S）和signal（S）的操作如下：

③AND型信号量

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有能为之分配的资源，也不分配给他。对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。相应的Swait（S）和Ssignal（S）的操作如下：

（2）利用信号量实现同步

利用信号量解决临界区同步问题时，设S为实现进程Pl、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程Pl中语句x的运行结果，所以只有当语句x执行完成之后语句v才可以执行。其实现进程同步的算法如下：

若P2先执行到P（S）时，S为0，执行P操作会把进程P2阻塞，并放入阻塞队列中，当进程P1中的x执行完后，执行V操作，把P2从阻塞队列中放回就绪队列，当P2得到处理机时，就得以继续执行。

（3）利用信号量实现进程互斥

利用信号量解决临界区互斥问题时，设置一个公用信号量MUTEX，信号量的值初始化为1，表示该临界资源空闲未被占用（或临界区无进程在执行）。进程使用共享资源前调用P（S）尝试自己是否可使用共享资源，当无进程在使用共享资源时，调用P（S）操作成功，于是就去使用该共享资源，否则进程执行P操作时将会被阻塞，直至在临界区中的进程退出。对共享资源使用结束后调用V（S）归还对共享资源的使用权，以便其他进程可以使用该共享资源。任何要使用临界资源的进程只需把涉及临界区的代码置于P（S）和V（S）之间，即可实现进程互斥。其算法如下：

（4）利用信号量实现前驱关系

信号量也可以用来描述程序之间或者语句之问的前驱关系。下图给出了一个前驱图，其中Sl, S2, S3, „, S6是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为0的信号量（为每条边设置一个信号量），如a, b, c, d, e, f, g。

利用这些信号量实现各语句前驱关系的算法如下：

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

①关系分析，根据给出的各操作确定相应的进程数，并分析它们之间的同步和互斥关系；

②理清思路，根据问题关键点以及各进程的关系，找出解决的思路，并根据各进程的操作流程以及确定P操作、V操作的大致顺序；

③设置信号量并书写PV操作，根据各进程的同步和互斥关系以及解决问题的思路，设置需要的信号量，确定初值。

【例】有两个并发进程如下面所示，对于这段程序的运行，正确的说法是（　）。

A．程序能正确运行，结果唯一。

B．程序不能正确运行，可能有两种结果。

C．程序不能正确运行，结果不确定。

D．程序不能正确运行，可能会死锁。

【答案】C

【解析】本题考查进程的并发执行。本题中两个进程不能正确地工作，运行结果有多种可能性，请见下面说明。

不确定的原因是由于使用了公共的变量x，考察程序中与x变量有关的语句共四处，若执行顺序是1）→2）→3）→4）→5）→6）→7）→8）时，结果是y=1, z=1, t=2, u=2, x=0；当并发执行过程为1）→2）→3）→4）→5）→6）→7）→8）时，结果是y=0, z=0, t=2, u=2, x=0；若执行顺序是5）→6）→7）→8）→1）→2）→3）→4）时，结果是y=1, z=1, t=2, u=2, x=1；当并发执行过程为5）→6）→1）→2）→7）→8）→3）→4）时，结果是y=1, z=1, t=0, u=0, x=1。可见结果有多种可能性。

4．管程

（1）管程的定义

管程提供了与信号量同样的功能，但使用更方便和容易控制。其基本思想是将共享变量以及对共享变量能够进行的所有操作过程集中在一个模块中进行管理。管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。管程的示意图如下图所示：

（2）管程的组成

管程由三部分组成：①局部于管程的共享变量说明；②对该数据结构进行操作的一组过程；③对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。

（3）管程的特点

管程有如下特点：

①管程内定义的局部变量只能被管程内定义的过程访问，不能被管程外的过程直接访问；

②进程要进入管程，必须调用管程中的一个过程；

③一次只允许一个进程在管程内执行，其他要调用管程中过程的进程必须等待，直到管程可以进入。管程有效地实现了互斥。

5．经典同步问题

（1）生产者-消费者问题

①问题描述

有一群生产者进程和消费者进程共享一个具有n个缓冲区的缓冲池，当缓冲区没满时，生产者进程将它所生产的产品放入一个缓冲区中；当缓冲区没空时，消费者进程可从一个缓冲区中取走产品去消费。

②问题分析

a．关系分析。首先该问题只涉及2个进程即生产者和消费者，两个进程对缓冲区互斥访问是互斥关系，同时只有生产者生产了消费者才能消费，故他们又存在一种相互协作的关系即同步关系。

b．理清思路。问题的关键就是要解决生产者和消费者进程之间的互斥关系和同步关系，确定互斥和同步PV操作的位置。

c．设置信号量并书写PV操作。利用信号量mutex作为互斥信号量控制互斥访问缓冲池，互斥信号量初值为l；信号量full记录当前缓冲池中已放产品的缓冲区数，初值为0；信号量empty用于记录当前缓冲池中未放产品的缓冲区数，初值为n。具体的PV操作如下：

（2）读者—写者问题

①问题描述

有两组并发的读者和写者进程，共享一个文件F，共享的原则如下：a．读写互斥访问；b．写写互斥访问；c．允许多个读者同时对文件进行访问。请用PV操作解决读者和写者之间的同步问题。

②问题分析

a．关系分析。首先该问题只涉及2个进程即读和写者，它们的关系问题描述以及很清楚的给出了。

b．理清思路。问题的关键就是要解决读者和写者以及写者跟写者之间的互斥关系，需要注意的是读者和读者不存在互斥问题。最后确定互斥和同步PV操作的位置。

c．设置信号量并书写PV操作。首先设置信号量count为计数器，用来记录当前读者数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问。

具体的PV操作如下：

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

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

（3）哲学家进餐问题

①问题描述

设有5个哲学家，共享一张放有5把椅子的圆桌。每人分得1把椅子。但是，桌子上总共只有5把叉子，在每人两边分开各放一把。哲学家们在肚子饥饿时才试图分两次从两边捡起两支筷子就餐。哲学家进餐应满足的条件：

a．每个人只有拿到两支筷子时，哲学家才能吃饭；

b．如果筷子已在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子；

c．任性的哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。

②问题分析

a．关系分析

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

b．理清思路

该问题中共涉及5个进程，本题的关键是如何让一个哲学家拿到左右两个筷子而不造成死锁或者饥饿现象。解决方法有两个：一个是让他们同时拿两个筷子；二是对每个哲学家的动作制定规则，避免饥饿或者死锁现象的发生。

c．设置信号量

由问题描述可知筷子是临界资源，定义互斥信号量数组chopstick[5]={1,1,1, l,1}用于对5个筷子的互斥访问。对哲学家按顺序从0～4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为（i+1）5%。第i位哲学家活动的具体的PV操作如下：

该算法存在死锁问题，筷子已经被拿光了当五个哲学家都想要进餐，分别拿起他们左边筷子的时候等到他们再想拿右边筷子的时候就全被阻塞了。

为了防止死锁的发生，可以再加一些限制条件比如至多允许四个哲学家同时进餐；仅当一个哲学家左右两边的筷子都可用时才允许他抓起筷子；对哲学家顺序编号，要求奇数号哲学家先抓左边的筷子，然后再转他右边的筷子，而偶数号哲学家刚好相反。

四、死锁

1．死锁的概念

（1）死锁的定义

一组进程是死锁的，是指该组中的每个进程都正在等待这一组中的其他进程所占有资源而无法推进的错误现象。死锁状态下，所有的进程都在等待，没有一个进程能引用任何事件将该组中的其他任何成员唤醒，因此，所有进程永远处于等待状态。

（2）死锁生产的原因

死锁产生的原因有以下两个：①系统资源不足，这是根本原因。设计操作系统的其中一个主要目的就是使并发进程共享系统资源；②进程推进顺序不当。进程推进顺序不当是指各进程对系统资源的请求顺序是不一样的。

（3）死锁产生的必要条件

死锁产生的必要条件有4个：

①互斥条件。即某一资源仅为一个进程所占有，则其他请求进程只能等待；

②保持和等待条件；进程已经保持了至少一个资源，但又提出了新的资源请求，多个进程都不释放自己已有的资源，导则系统已无资源可分配，故请求进程被阻塞；

③不剥夺条件，进程已占有的资源，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放）；

④环路等待条件，存在一种进程资源的循环等待链，链中每一个进程己获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{P1, P2, „, Pn}，其中Pi等待的资源被P（i+1）占有（i=0, l, „, n-1）, Pn等待的资源被P0占有。

2．死锁处理策略

为使系统不发生死锁，必须设法破坏产生死锁的四个必要条件之一，或者允许死锁产生，但当死锁发生时能检测出死锁，并有能力解除死锁。死锁处理的策略一般有3种：预防死锁、避免死锁以及死锁的检测及解除。

（1）预防死锁

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

（2）避免死锁

在资源的动态分配过程中，用某种方法防止系统进入不安全状态（一般使用银行家算法），从而避免死锁。

（3）死锁的检测及解除

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

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

3．死锁预防

仅当死锁的4个必要条件同时具备时，死锁才会出现。死锁的预防就是设法破坏死锁的4个必要条件之一，就可以预防它的发生。

（1）破坏互斥条件。可以采用一些技术，如SPOOLING技术，将独占设备改造成多台设备，满足并发进程的需要，从而避免死锁。但不是对所有设备有效。

（2）破坏保持和请求条件。采用静态分配方法，运行前，一次分配所需的全部资源；或申请前释放其占有的资源。

（3）破坏非剥夺条件。一旦出现死锁，则强行从一些进程剥夺资源来恢复系统。

（4）破坏环路等待条件。可以采用资源的有序分配法，为系统中的资源进程编号使进程按照资源的编号或递增或递减的顺序申请资源。

4．死锁避免

死锁的避免就是在为进程分配资源时，每当完成分配后，立即检查系统是否仍处于安全状态。若是，则这次分配是成功的，否则该次的分配作废，让其阻塞等待。所谓系统的安全状态，是指系统在当前状态下，能按照某个顺序，为系统中的每个进程分配其所需资源，直至它的最大需求，最终使系统中的全部进程都能顺利完成。此时的系统状态是安全的。这就是著名的银行家算法。

需要注意的是虽然系统处于不安全状态时，不一定使系统进入死锁状态，但为了保证系统不进入死锁状态，必须保证系统处于安全状态。

（1）银行家算法

银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行加资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得当就会发生进程循环等待资源，以致进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制块中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数，银行算法进行资源分配可以避免死锁。

①数据结构描述

a．可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

b．最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i, j]=K，则表示进程i需要Rj类资源的最大数目为K。

c．分配矩阵Allocation。这也是一个n×m的矩阵，它定义了每个进程所获的各类资源的数目。如果Allocation [i, j]=K，则表示进程i当前已分得K个Rj类资源。

d．需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i, j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务，其中Need[i, j]=Max[i, j]-Allocation[i, j]。

②银行家算法描述

设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

a．如果Requesti[j]≤Need[i, j]，便转向步骤b；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

b．如果Requesti[j]≤Available[j]，便转向步骤c；否则，表示尚无足够资源，Pi须等待。

c．系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]∶=Available[j]-Requesti[j]；

Allocation[i, j]∶=Allocation[i, j]+Requesti[j]；

Need[i, j]∶=Need[i, j]-Requesti[j]。

d．系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

③安全性算法

a．设置两个向量：①工作向量Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available; ②Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。

b．从进程集合中找到一个能满足下述条件的进程：

Finish[i]=false；

Need[i, j]≤Work[j]；若找到，执行步骤c，否则，执行步骤d；

c．当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]= Work[i]+Allocation[i, j]；

Finish[i]= true；

Gotostep b；

d．如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

（2）银行家算法之例

①题目条件

假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如表2-1所示：

②银行家算法的执行

a．T0时刻的安全性，如表2-2所示：

b．P1请求资源：P1发出请求向量Request1（1,0,2），系统按银行家算法进行检查：

Request1（1,0,2）≤Need1（1,2,2）

Request1（1,0,2）≤Available1（3,3,2）

系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如表2-3中的圆括号所示。再利用安全性算法检查此时系统是否安全。

c．P4请求资源：P4发出请求向量Request4（3,3,0），系统按银行家算法进行检查：

Request4（3,3,0）＜Need4（4,3,1）；

Request4（3,3,0）＞Available（2,3,0），让P4等待。

d．P0请求资源：P0发出请求向量Requst0（0,2,0），系统按银行家算法进行检查：

Request0（0,2,0）＜Need0（7,4,3）；

Request0（0,2,0）＜Available（2,3,0）；

系统暂时先假定可为P0分配资源，并修改有关数据，如表2-4所示：

此时再利用安全性算法进行检查，发现此时的Available（2,1,0），已不能满足任何进程的需求，故系统进入不安全状态，此时系统不分配资源。

5．死锁的检测和解除

系统采用资源的动态分配方法。当进程请求分配资源时，只要系统有可用资源就分配。系统定期启动死锁检测算法，检查系统中的进程图或进程资源图是否存在了一个或多个环路。若存在，就有死锁发生。一旦检测出死锁，则立即进行系统恢复。

死锁恢复常用的方法有以下3种：

（1）撤销进程法：通过撤销一些或全部进程使系统恢复。

（2）进程回退法：通过使一些进程滚回到某个检查点使系统恢复。

（3）资源剥夺法：通过连续剥夺一些进程的资源使系统恢复。

死锁检测与恢复算法虽然有效，但消耗系统的时间太多，实际使用很少。往往采用简单的人工干预，来解除死锁。

【例】某系统有同类资源m个，可并发执行且共享该类资源的进程数为5个，每个进程最多需要3个该类资源，则系统一定不会发生死锁的最少资源配置是（　）。

A．10个

B．11个

C．12个

D．15个

【答案】B

【解析】为了避免死锁发生，每个进程获得的资源数比起所需的最大资源数少1，即5个进程每个分别获得了2个该类资源，只要还有一个剩余的同类资源，就不会发生死锁。因此所需的最少资源配置数为（3-1）×5+1=11。