操作系统原理与实训教程

第2章处理机管理(重难点之一)

2.1多道程序设计

程序并发执行时的特征：间断性程序在并发执行时，由于共享资源，或者需要相互合作，致使相互间产生了制约关系，呈“走走停停”的间断执行特征。失去封闭性程序并发执行时的系统环境（主要指各程序所共享的系统资源的状态）是由多个程序来改变的，因而失去了封闭性。不可再现性程序在并发执行时的结果与其执行速度等有关，从而不可再现。I1I2I3I4C1C2C4C3P1P2P3P4程序并发执行的条件(Bernstein,1966)定理：如果两个程序P1和P2满足下述条件，它们便能并发执行，否则不能

R(P1)∩W(P2)∪R(P2)∩W(P1)∪W(P1)∩W(P2)={}即当两个程序的读集与写集的交集以及写集与写集的交集都为空集时，它们可以并发执行，否则不行。该定理也称Bernstein条件。

操作系统中许多任务不满足Bernstein条件，它们不能并发执行吗？怎么办？这涉及后面重点讲的进程同步问题。2.2进程的描述2.1进程的基本概念1.进程（P26）及进程实体（P27）的概念进程是对正在运行的程序的抽象，是OS最核心的概念。计算机上所有可运行的软件，包括OS，被组织成若干顺序进程，简称进程。进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。生活例子：一人按菜谱做菜。

进程实体由程序段、相关数据段和进程控制块构成。进程的其他定义

“进程”这一术语，在60年代初期，首先在美国MIT的MULTICS系统和IBM公司的CTSS/360系统中引入。其中能反映进程实质的定义有：

（1）进程是程序的一次执行。（2）进程是可以和其他计算并发执行的计算。（3）进程是一个程序及其数据在处理机上顺序执行时发生的活动。（4）进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。（5）进程是进程实体的一次活动。

程序任意并发执行具有一些新的特征（间断性、无封闭性、不可再现性），旧的程序的概念已不足以刻画这种并发执行的程序及其执行所产生的新特征。为使程序能并发执行，且为了能对并发执行的程序加以描述和控制而引入进程。简言之，为了实现程序的并发执行。前趋图（P23）在此是一种可用于描述进程间执行的时序关系（前趋后继关系）的DAG。DAG在编译原理、数据结构和人工智能等课程/学科中都有用。2.进程的引入（P26）进程的特性：动态性：指进程是程序或进程实体的一次执行过程，生命周期短暂。

并发性：指多个进程实体同存于内存中，且能在一段时间内同时运行。

独立性：指进程是系统分配资源和调度运行的一个基本单位。

异步性：指进程的推进速度是各自独立、不可预知的。

结构特性：从结构上看，进程由程序段、相关数据段和进程控制块三部分组成。此即进程实体。3.进程的特性及其与程序的区别（P26~P27）提示：可从二者的定义上、进程的特征上（结构特征单列）和二者对应数目关系上等几方面分析。另外，进程可真实地描述并发，而程序不能。注意：

在OS中，作业、进程、程序和线程是几个相似但又不同的概念！进程与程序的区别与联系从定义上看，进程是程序处理数据的过程，而程序是一组指令的有序集合；进程具有动态性、并发性、独立性和异步性等，而程序不具有这些特性；从进程结构特性上看，它包含程序（以及数据和PCB）；进程和程序并非一一对应。

执行态阻塞态就绪态调度I/O请求时间片完I/O完成为了更好地描述进程的动态存在，设计者常常给进程定义三种基本状态：就绪态(Ready)、执行态(Running)和阻塞(Blocked)状态。其转换方向和常见的转换原因如下图所示：4.进程的三种基本状态及其转换图说明：1)在引入挂起功能的系统中，进程状态可至5个。2)在实际的OS中，进程的状态会更多。比如UNIXSV中有9种，Linux中有6种，Windows2000中有7种。另外，系统引入挂起功能的原因要了解（P29，为满足系统和用户两方面的需求，如：换入换出、调整负荷、解救死锁、父进程请求等）。5.PCB（ProcessControlBlock）及其组织方式

PCB：系统中用于存放进程的描述和控制信息的数据结构。它是进程存在于系统的唯一标志。PCB作用(P29)：（1）标识进程的存在；（2）为系统提供可并发执行的独立单位；（3）为系统控制和管理进程提供所需的一切信息。PCB中的主要内容(见P30)：

进程的标识信息、处理机的状态信息、进程调度信息、进程的控制信息等。。PCB的组织方式：

一般线性表、链接表(多队列)、索引表。空闲PCB队列头指针阻塞进程队列头指针就绪进程队列头指针执行进程指针PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9430879015….PCB链接队列示意图：进程控制的主要任务是对进程生命周期进程控制，即要负责进程的创建、撤消以及实现进程的状态转换和进程通信等功能。这是系统的基本功能，由内核中相应的原语完成。要求了解各个进程控制原语的算法思想和引起这些控制原语执行的常见原因。原语(primitiveoratomicaction)：

是OS内核中由若干多机器指令构成的完成某种特定功能的一段程序，其执行具有不可分割性，即原子特征。亦即原语的执行必须是连续的，不能是并发或被中断的。单机系统中的实现方式之一：屏蔽中断。2.3进程控制1.进程创建原语Creat()引起创建进程的事件：用户登录作业调度提供服务应用请求进程创建的主要步骤：申请空白PCB为新进程分配资源初始化PCB的内容将新进程插入就绪队列2.进程阻塞原语Block()引起进程阻塞的事件：请求系统服务启动某种操作新数据尚未到达无新工作可作进程阻塞的过程：发现阻塞事件，调用阻塞原语把自己阻塞，停止进程的执行，修改PCB的状态信息，将其插入到相应的阻塞队列。最后转调度程序，将处理机分配给另一个就绪进程。注意：进程的阻塞是进程自身的一种主动行为2.4进程的互斥

——你需要，我也需要

多道程序设计带来的问题：

并发执行的多个进程可能产生互斥或同步的相互制约关系，不采取措施，可能导致结果的不可再现性。影响系统效率，而且还可以导致系统崩溃。

为此，现代操作系统都在内核中设有进程的互斥同步机制，即同步机构（硬件指令/信号量机制/管程机制等），使并发执行的诸进程之间能有效地共享资源和相互合作，并使程序的执行具有可再现性。一、互斥的定义所谓进程互斥，指的是对某个系统资源，一个进程正在使用它，另外一个想用它的进程就必须等待，而不能同时使用。即排他性地用。进程互斥是多道程序系统中进程间存在的一种源于资源共享的制约关系，也称间接制约关系，主要是由被共享资源的使用性质所决定的。限定进程只能互斥地访问它的资源叫临界资源（指一次仅允许一个进程使用的资源）。

临界资源也是不可剥夺性资源。例：打印机、共享变量或表格等。类似生活中的试衣室、电话间等。计算机系统中可剥夺性使用的资源主要有CPU、内存和磁盘等。类似生活中的点歌簿、电话本等。临界区：进程中访问临界资源的那段程序代码称为临界区或临界段。使用同一临界资源的不同进程中的临界区称为同类临界区或相关临界区。临界区的使用原则，即“空则让进，忙则等待，等则有限，等则让权”。

二、上锁和开锁原语

现代操作系统用来实现进程的互斥、同步的工具有多种，如上锁与开锁原语、信号灯机制、管程机制等。

上锁与开锁是一种最简单的进程互斥方法，它使用一个锁变量W来表示某种临界资源的状态，W=0表示资源空闲可用W=1表示资源正被使用

1．上锁原语：LOCK（W）L1：如果

W=1那么转向L1;否则W=1返回voidlock(锁变量w){test:if(w为1)

gototestelsew=1;/*上锁*/}

/*lock(w)*/1.考察锁位的值；2.如果原来的值为0，将锁位置1；3.如果为1，则返回第一步再次考察2．开锁原语：UNLOCK（W）

W=0;返回voidunlock(锁变量w){w=0;/*开锁*/}/*unlock(w)*/当进程使用完资源后，它必须将锁位置成“0”，称为开锁操作。三、用开关锁原语实现进程互斥

任何欲进入临界区的进程，必须先执行上锁原语。若上锁原语顺利通过，则进程可进入临界区；当完成对临界区资源的访问后再执行开锁原语，以释放该临界资源。

即在相关进程的程序里由上锁和开锁原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。

例如，甲、乙两进程要访问同一类临界资源

甲进程：其他代码；

LOCK（W）；

甲进程的临界区；

UNLOCK（W）；

其他代码；乙进程：其他代码；

LOCK（W）；

乙进程的临界区；

UNLOCK（W）；

其他代码；用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等”。

2.5信号量机制荷兰著名科学家，1972年计算机图灵奖获得者，E.W.Dijkstra于1965年利用火车控制系统中信号灯的概念，提出了用作进程同步工具的信号量（semaphore）机制，它最初由一个表示资源可用数目或状态的整型量（信号量）和唯一能改变这个信号量值的P、V原子操作组成，是一种简单成效的进程互斥同步工具，已广泛用于现代计算机系统中。信号量机制的基本原理是：

两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。经典的整型信号量＝》记录型信号量＝》信号量集机制CPU忙等无忙等，若使用不当，可能造成死锁不易死锁，可能导致资源利用率低一、记录型信号量的概念

记录型信号量是个复合类型的量，其一个分量是个整型分量S，另一个分量是个进程的等待队列指针Q

。Pascal的记录相当于C的结构体。记录型信号量机制无进程的“忙等”现象，其整型分量相当于最早的整型信号量，其值只能由P、V操作改变。记录型信号量的整型分量S的值的物理含义当S≥0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；当S＜0时，其绝对值表示信号量S的阻塞队列L中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。

记录型信号量机制的另一构件P、V操作的定义如下：

二、P、V操作原语

P代表荷兰语的proberen，意为“测试”；V代表荷兰语的verhogen，意为“增加”。

国外文献现在流行使用wait操作和signal操作(或down操作和up操作)代替P操作和V操作。P(S)、V(S)原语操作的算法描述：

P(S):（1）S.S减1；（2）若S.S<0，则Block(S.Q)。V(S):（1）S.S加1；（2）若S.S0，则Wakeup(S.Q)。P（S）和V（S）操作的物理含义：

P（S）操作表示“等信号”，即测试一个要等的信号是否到达；V（S）操作表示“发信号”。这个信号在实现同步时就是“合作者的伙伴进程已完成前趋任务”，在实现互斥时就是“临界资源可用”。另外，在互斥问题中，每执行一次P（S）操作的含义，也可理解为进程请求一个单位的S类资源；每执行一次

V（S）操作的含义，也可理解为进程释放一个单位的S类资源。

三、用P、V操作原语实现进程的互斥

用P、V操作原语实现进程的互斥也一样简单，只需在相关进程的临界区的前后分别施以P操作和V操作即可，即在相关进程的程序里由P操作和V操作原语紧夹着临界区，就能保证这些进程互斥地进入各自的临界区。这里所用信号量的初值一般为1，表示临界资源未被占用，且其可用数目为1。

用P、V操作原语实现进程互斥的效率更高一些，因为P操作中引入了阻塞机制，所以消除了CPU忙等现象。P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3互斥区一个简化的异地售票程序，假设几乎同时两地有两个乘客要购买同一班次的车票各一张

两个终端售票程序都要访问存放该次车票的数据单元Pk假设它们都要对Pk做如下的访问操作“若Pk≥1，则将Pk的值减1，卖出一张票，返回否则打印‘无票’信息，返回”如果不加任何限制让这两个程序并发执行的话，结果可能会导致错误，甚至两地各卖出一张重票的现象例2.1试用P、V操作实现火车联网订票系统中北京、天津两地的两个终端售票进程发售同一班次车票的过程。

主要步骤是：

（1）分析清楚题目涉及的进程间的制约关系。（2）设置信号量（包括信号量的个数和初值，对于同步问题还要写出信号量的物理含义）。（3）给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。

北京售票终端进程：

①根据顾客订票要求找到公共数据单元PK；②P（S）；③把PK的值读到工作寄存器R1中；④根据顾客订票数修改R1；⑤将R1的值回写到PK中；

⑥V（S）；⑦售出顾客所订的票，返回；

天津售票终端进程：

①根据顾客订票要求找到公共数据单元PK；②P（S）；③把PK的值读到工作寄存器R2中；④根据顾客订票数修改R2；⑤将R1的值回写到PK中；⑥V（S）；⑦售出顾客所订的票，返回；关于此算法的2个问题：①如何解决“票已售完”？②用类Pascal语言怎样描述？

——留作课后思考练习！

2.6进程的同步

——你等我，我也等你

相关的并发进程间可能有互斥制约关系，也可能有同步制约关系所谓进程同步，指的是合作完成同一个任务的两个或多个进程，在执行速度或某些时序点上必须相互协调，以同步推进的合作关系。这是一种源于相互合作的直接制约关系。即一个进程的执行依赖于另一个进程的消息，当它到达某一确定点而没有得到合作者发来的“已完成前驱操作”的消息时必须等待。生活中对弈双方、医生与化验员之间都有同步关系系统中父子进程之间通常属于合作（同步）关系注意：互斥也可以看成是一种特殊的同步关系。用记录型信号量机制实现进程同步一般的解题步骤（同进程互斥的实现）：(1)分析题设中各进程间的制约关系；(2)按(1)的结果设置相应信号量（包括信号量的名字、个数和初值及其物理含义（仅限同步问题））注意：对于互斥问题，一般只设1个信号量，且置初值1；而对于同步问题，合作进程间需要收发几条消息相应就设置几个信号量，且同步信号量的初值一般为0，表示消息尚未产生。(3)把P、V操作加到进程代码的适当处，用类Pascal或C语言给出算法描述；注意P(S)、V(S)操作出现的形式特点一般地，P(S)、V(S)操作总是同时/配对出现的，但具体描述进程互斥时，P(S)、V(S)操作出现在同一进程中(且分别紧挨在临界区前后)；而具体描述进程同步时，P(S)、V(S)操作常出现在不同的进程中，且一个进程发送消息时用V(S)，而它的合作者进程接收此消息时用P(S)。例2.2用信号量机制解决生产者-消费者问题（P43，经典IPC问题之一，也叫有界缓冲区问题）问题描述：一组消费者进程一组生产者进程如何编程？

具有n个单元的环型缓冲池生产者-消费者问题是对相互合作的进程之间同步问题的一种抽象，例如，在输入和计算进程间，计算进程是消费者；而在计算和打印进程间，计算进程是生产者。问题分析：①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。

②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

问题解答：①所用信号量设置如下：

Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。Ⅲ）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池。

②用信号量机制解决生产者—消费者问题的算法描述如下(类Pascal语言描述见后)：生产者i

生产出一产品；

P（empty）；

P（mutex）；

将该产品放入缓冲区；

V（mutex）；

V（full）；

消费者j

P（full）；

P（mutex）；

从缓冲区取出一产品；

V（mutex）；

V（empty）；

消费该产品；

Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem; in,out:integer:=0,0;begin parbegin

producer:begin repeat produceanitemnextp;

P(empty);

P(mutex); buffer(in):=nextp; in:=(in+1)modn;

V(mutex);

V(full); untilfalse;

end

consumer:begin repeat

P(full);

P(mutex); nextc:=buffer(out); out:=(out+1)modn;

V(mutex);

V(empty); consumetheiteminnextc; untilfalse;

end parendend问题思考：如果某进程中的P操作顺序颠倒了，会怎么样？如果某程序员漏写了一个V操作，会怎么样？例2.3用信号量机制解决读者-写者问题（P44,经典IPC问题之一,Courtois,1971

）问题描述：一组读者与一组写者循环访问共享的同一个数据对象。规定：多个读者可以同时读这个数据对象，但决不允许多个写者同时对它进行写操作，也不允许读者、写者同时访问它。如何对读者、写者编程？

哲学家进餐问题对多进程互斥访问有限资源这一类问题的建模很有用。另一著名问题就是读者-写者问题，它为数据库访问建立了一个模型，是对进程间一类互斥问题的抽象。问题分析①读者—写者之间的互斥关系：

由于共享的数据对象是临界资源，故可设一个公用的初值为1的互斥信号量RW_mutex，以保证同时只有1个读者或者写者进程进入临界区访问该数据对象。但是，这样做不仅实现了写者与写者的互斥、写者与读者的互斥，而且也实现了读者与读者的互斥。其实，只有第1个到来的读者和最后1个离开的读者需要与写者进行互斥通信。为此，引入一个读者计数器变量RC。

②读者—读者之间新增的互斥关系：读者需互斥地访问RC，故需再设一个初值为1的互斥信号量R_mutex。问题解答：

①所用信号量和其他变量设置如下：

Ⅰ）互斥信号量RW_mutex，初值为1，用于实现写者与其他写者或读者互斥地访问共享的数据对象。Ⅱ）互斥信号量R_mutex，初值为1，用于实现诸读者互斥地访问读者计数器变量RC。Ⅲ）整型变量RC，初值为0，用于对读者进行记数。

②算法描述(类Pascal语言描述见下)：

读者：P（R_mutex）；若RC=0则

P（RW_mutex）；RC加1；V（R_mutex）；读数据对象；P（R_mutex）；RC减1；若RC=0则

V（RW_mutex）；V（R_mutex）；

写者：P（RW_mutex）；对数据对象进程写操作；V（RW_mutex）；

用信号量机制实现的读写问题的类Pascal描述：VarRW_mutex,R_mutex:semaphore:=1,1;RC:integer:=0;begin parbegin

Readeri:begin repeat

P(R_mutex); ifRC=0thenP(RW_mutex); RC:=RC+1;

V(R_mutex); performreadoperation;

P(R_mutex); RC:=RC-1; ifRC=0thenV(RW_mutex);

V(R_mutex); untilfalse;

end parendendWriterj:begin repeat P(RW_mutex);performwriteoperation;V(RW_mutex);untilfalse;end例2.4试用用信号量机制描述两人下象棋的过程两人下象棋的过程可以概括为：一开始只能是“红先黑后”，以后两人要循环轮流走子，直至某一方获胜或双方和棋为止。这是个只有一个生产者和一个消费者的生产者——消费者问题，是个典型的“你等我，我也等你”的问题。红方是总的前趋任务——生产者进程，黑方是总的后继任务——消费者进程，但由于下棋过程必须轮流走子，所以红黑双方的生产者消费者身份会轮流改变。棋盘则是生产者与消费者共享的缓冲。

解答：①所用信号量设置如下：Ⅰ）同步信号量hei，初值为1，表示黑方已走子,开始时可使红方先行不受阻。

Ⅱ）同步信号量hong，初值为0，表示红方尚未走子，开始时可使黑方先行受阻。②红黑双方下象棋过程如下：

红方：P（hei）；若被黑方将死，则投子认负，结束；若同意与黑方作和，则结束；否则，根据棋局思考后走一子；V（hong）；黑方：P（hong）；若被红方将死，则投子认负，结束；若同意与红方作和，则结束；否则，根据棋局思考后走一子；V（hei）；此例的类Pascal语言描述留作课后练习还有其他解法吗？例2.5用信号量机制描述进程的前趋后继关系(补充例1)说明：这是一种类型的同步问题，解法也较固定：初始结点对应的操作可直接执行，然后用V操作给其各个后继结点分别发送一条“已完成前趋操作”的消息；终止结点对应的操作则必须在该结点分别用P操作收到其各个前趋结点“已完成前趋操作”的消息后才能执行；各个中间结点对应的操作，执行前需用P操作接受其前趋结点“已完成前趋操作”的消息，执行后还需用V操作给其各个后继结点分别发送一条“已完成前趋操作”的消息。上述前趋图中各结点对应的操作的并发执行情况描述如下：Vars12,s13,s24,s25,s36,s46,s56:semaphore:=0,0,0,0,0,0,0;begin

parbegin

process1:beginS1;V(s12);V(s13)end;

process2:beginP(s12);S2;V(s24);V(s25)end;

process3:beginP(s13);S3;V(s36)end;

process4:beginP(s24);S4;V(s46)end;

process5:beginP(s25);S5;V(s56)end;

process6:beginP(s36);P(s46);P(s56);S6end;

parendend

s1s2s3s4s5s6例2.6用信号量机制解决睡眠的理发师问题（补充例2，经典IPC问题之一）问题描述：理发店里有1位理发师、1把理发椅和n把顾客椅。若无顾客，理发师便在理发椅上睡觉；当1顾客到来时，他必须先叫醒理发师；若理发师正在理发时又有顾客到来，则如果有空椅子，他们就坐下来等，否则就离开。如何对理发师和顾客编程来描述他们的行为，要求不能带竞争条件？这主要是个同步问题，理发师是循环进程，顾客不是。问题分析：①顾客—理发师之间的同步关系表现为：若无顾客，理发师便在理发椅上睡眠，等待。顾客到来时，先看等候的顾客数是否少于顾客椅子数，不是则离开，否则就留下来，声称要理发，并且等理发师醒来或闲下来，再理发。

②顾客—理发师之间还有互斥关系：由于等候的顾客数变量是临界资源，所以顾客进屋后对该变量进行的加1操作以及理发师起身准备给顾客理发时对该变量进行的减1操作必须互斥。

AsolutiontothesleepingbarberproblembyTanenbaumsemaphorecustomers,barbers,mutex=0,0,1;intwaiting=0;/*i.e.customersarewaiting*/voidbarber(void){while(TRUE){

P(customers);

P(mutex);

waiting=waiting-1;

V(barbers);

V(mutex);

cuthair();}}voidcustomer(void){

P(mutex);

if(waiting<CHAIRS){waiting=waiting+1;

V(customers);

V(mutex);

P(barbers);

gethaircut();}else{V(mutex);}}该解法中，理发师早晨工作时先执行过程barber，阻塞在信号量customers上，于是在理发椅中睡觉，直至有顾客到来。理发师问题解法（二）

——byJ.A.Harris&何炎详semaphorecutHair,waiting,mutex=0,0,1;intcount=0;/*i.e.customersthatareinthebarber*/voidbarber(){while(TRUE){

P(cutHair);Givehaircut();}}voidcustomer(){

P(mutex);

if(count==n+1){V(mutex);exit();}count=count+1;if(count>1){//takeachair

V(mutex);

P(waiting);}elseV(mutex);V(cutHair);

ReceiveHaircut();

P(mutex);

count=count-1;if(count>0)V(waiting);

V(mutex);}}该解法中，理发师与顾客，顾客与顾客之间都有同步关系，而只有顾客访问顾客计数器变量时需互斥。理发师问题解法（三）

——by谢青松semaphorecustomers,barber_chair,chairs=0,0,n+1;voidbarber(){while(TRUE){

P(customers);

V(barber_chair);

Givehaircut();}}voidcustomer(){

P(chairs);

//comein//takeachair

V(customers);P(barber_chair);ReceiveHaircut();

V(chairs);//goout;}该解法中，把顾客进入理发店、理发、出理发店的过程看做顾客进程的临界区，相应互斥信号量chairs初值为n+1,表示最多允许n+1个顾客同时进店。顾客与理发师之间有同步关系。以上解法有什么差异？该问题解法（四）更复杂，见汤子瀛、梁红兵《OS学习指导与题解》P44例2.7(P46选讲)某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。分析：这是个典型的进程互斥问题，超市内部及其出入口是临界资源，为此，若出入口为同一个，则需要设两个互斥信号量，否则需要设3个。解答:①所用信号量设置如下：Ⅰ）互斥信号量S，初值为50，用以保证最多可以有50个购物者同时进入超市。Ⅱ）互斥信号量mutex，初值为1，用以保证同时只能有一个购物者进程进入出入口拿起篮子或者结帐后放下篮子。②用信号量机制给出的每个购物者购物过程的算法描述如下：购物者i进程（解法一）：P（S）；P（S）；P（mutex）；P（mutex1）；从入口处进超市，并取一只篮子；同左；V（mutex）；V（mutex1）；

进超市内选购商品；同左；

P（mutex）；P（mutex2）；

到出口结帐，并归还篮子；同左

；

V（mutex）；V（mutex2）；

从出口离开超市；同左；

V（S）；V（S）；购物者i进程（解法二）：例2.8(P48选讲)桌上有个只能盛得下一个水果的空盘子。爸爸不断向盘中放苹果或桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定：当盘子空时，一次只能放入一个水果供吃者取用。试用信号量和P、V操作实现爸爸、儿子和女儿这三个循环进程之间的同步。

分析：本题属于生产者/消费者问题的变形，相当于一个能生产两种产品的生产者（爸爸）向两个消费者（儿子和女儿）提供产品的同步问题。因此，可参考生产者与消费者问题的解法。

注意，这里未把盘子看作临界资源。而南京大学2000年的一道考研题则是此例的变形，其答案把盘子看作了临界资源，变形部分是：盘子能盛2水果，爸爸放苹果，妈妈放桔子，要求实现4个进程的同步互斥关系。解答：①所用信号量设置如下：Ⅰ）同步信号量empty，初值为1，表示盘子是空的，即儿子或女儿已把盘中的水果取走。

Ⅱ）同步信号量orange，初值为0，表示爸爸尚未把桔子放入盘中。Ⅲ）同步信号量apple，初值为0，表示爸爸尚未把苹果放入盘中。

②用信号量描述的3个进程的同步过程：

爸爸进程：儿子进程：

女儿进程：

P（empty）；

P（orange）；

P（apple）；将水果放入盘中；

从盘中取出桔子；

从盘中取出苹果；若放入的是桔子，

V（empty）；V（empty）；则V（orange）；吃桔子；

吃苹果；否则，V（apple）；此例的类Pascal语言描述留作课后练习设A、B两点之间是一段东西向的单行车道，现在要设计一个AB路段自动管理系统，管理规则如下：当AB间有车辆在行驶时，同方向的车可以同时驶入AB段，但另一方向的车必须在AB段外等待；当AB段之间无车辆行驶时，到达AB段的任一方向的车都可进入AB段，但不能从两个方向同时驶入，即只能有一个方向的车驶入；当某方向在AB段行驶的车辆驶出了AB段且暂无车辆进入AB段时，应让另一方向等待的车辆进入AB段行驶。试用信号量和P、V操作管理AB路段车辆的行驶。

BA例2.9(P48选讲)分析：

本题属于读者写者问题的变形，相当于两组读者（即两个方向的车辆）使用同一个共享文件（即AB路段）的互斥问题。因此，可参考读者写者问题的解法。一个方向的车辆中只有第1辆驶入AB路段的和最后1辆驶出AB路段的需要与另一方向的车竞争和释放对AB路段的互斥使用权，为此需引入两个计数器变量，分别用来对驶入AB路段的两个方向的车辆进行计数，以确定哪辆车是第1辆驶入的，哪辆是该方向最后1辆驶出的。故共需3个互斥信号量。解答：①所用信号量和其他变量设置如下：

Ⅰ）整型变量Car_A，初值为0，用于对从A点（东）驶入AB段的车辆进行记数。Ⅱ）整型变量Car_B，初值为0，用于对从B点（西）驶入AB段的车辆进行记数。Ⅲ）互斥信号量mutex，初值为1，用于实现不同方向的第一辆车互斥驶入AB路段。Ⅳ）互斥信号量ma，初值为1，用于实现东西向的车互斥地访问计数器变量Car_A。Ⅴ）互斥信号量mb，初值为1，用于实现西东向的车互斥地访问计数器变量Car_B。

P（mb）；Car_B加1；若Car_B=1则

P（mutex）；V（mb）；车辆从B点通过AB路段到达A点；P（mb）；Car_B减1；

Car_B=0则

V（mutex）；

V（mb）；P（ma）；

Car_A加1；若Car_A=1则P（mutex）；V（ma）；车辆从A点通过AB路段到达B点；P（ma）；Car_A减1；若Car_A=0则

V（mutex）；V（ma）；东西向(即AB向)行驶的车辆i

西东向(即BA向)行驶的车辆j

此例的类Pascal语言描述留作课后练习2.7进程通信进程之间的信息交换称为进程通信。包括高、低级两种通信方式，本节介绍后者。合作进程间所交换的信息量，少则是一个状态或数据，多则成千上万字节的。两种进程通信方式/机制低级通信：只适于在进程间交换少量信息的通信方式/机制。该通信方式（如进程的同步和互斥工具）一般只传送一个和几个字节的信息，可方便有效地用于控制进程的执行速度，但它要作为可传输大量信息的通信工具则不够理想（效率低通信对用户不透明）。高级通信：用户可以直接利用操作系统所提供的一组通信命令（如send和receive），高效地传送大量数据的一种通信方式。它具有传输效率高，用户使用方便等优点，具体又可分为3大类：高级通信方式分类

共享存储器系统。指共享内存区通信方式。消息传递系统。包括基于消息缓冲的本地直接通信方式——消息缓冲通信和可用于异地通信的间接通信方式——信箱通信两种通信方式。管道通信方式。这是UNIX首创的基于共享文件的通信方式。大家记得DOS或UNIX中的管道线命令吗？消息缓冲区和信箱typebox=recordsize:integer:=N;

s1,s2:semaphore;mutex:semaphore;letter:array[1..N]ofmessage;

in,out:integer;endtypemessage-buffer=recordsender;size;text;next;EndPCB中相关数据项：

mq;mutex;sm;消息缓冲队列通信机制示意图： 进程A PCB(B) 进程B ……Send(B,a)Sender:ASize:6Text:Hello!Receive(b)Sender:ASize:6Text:Hello!Sender:ASize:6Text:Hello!Next:2Sender:?Size:?Text:xxxxNext:0……首指针：mq互斥：mutex队列资源：sm……A的发送区aB的接收区bBuffer1Buffern消息缓冲通信机制中的发送与接收原语Proceduresend(receiver,a)Begin

getbuf(a.size，i);i.senter:=a.senter;i.size:=a.size;i.text:=a.text;i.next:=0;

getid(PCBset，receiver，j);

P(j.mutex);insert(j.mq，i);

V(j.mutex);

V(j.sm);endProcedurereceive(b)Beginj:=internalname;

P(j.sm);

P(j.mutex);remove(j.mq，i);

V(j.mutex);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;

putbuf(i);end信箱通信机制中的发送与接收原语Proceduresend(varB:box,M:message)begin

P(B.s1);

P(B.mutex);B.letter[B.in]:=M;B.in:=(B.in+1)modN;{B.size}V(B.mutex);

V(B.s2);endProcedurereceive(varB:box,N:message)begin

P(B.s2);

P(B.mutex);N:=B.letter[B.out];B.out:=(B.out+1)modN;{B.size}V(B.mutex);

V(B.s1);end2.8

死锁问题死锁的概念产生死锁的原因产生死锁的必要条件解决死锁问题的基本方法1死锁的定义——“你不让，我也不让”死锁概念的提出1965年，Dijkstra研究银行家算法时提出，以后又由Havender、Lyach等人研究并发展。死锁（Deadlock，P55）：是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。称此时系统处于死锁状态或系统产生了死锁，称这些永远在互相等待的进程为死锁进程。我们在生产者消费者问题解法中若颠倒消费者中P操作顺序会导致死锁；“堵车”可看作生活中的死锁例子；下面的经典IPC问题——哲学家进餐问题的一个错误解法也会导致死锁。例2.7(3.0)用信号量机制解决哲学家进餐问题（P55，经典IPC问题之一，Dijkstra,1965）问题描述：5位哲学家围在餐桌旁，要么思考，要么饿了时拿起左右两把叉子吃通心粉(足够用的)。要求为每位哲学家写一段程序来描述其行为，但不能出现饿死现象（死锁或饥饿）。问题分析：相邻哲学家之间因竞争一把叉子而存在互斥关系。故需5个互斥信号量。一个关于第i号哲学家进餐过程的不正确的算法：哲学家i进程（i＝0，1，2，3，4） 思考； P(S[i]); 拿起左边的叉子； P(S[(i＋1)mod5])； 拿起右边的叉子； 吃通心粉； 放下左边的叉子； V(S[i]); 放下右边的叉子； V(S[(i＋1)mod5])；

对应类Pascal语言描述为（P48）:varchopstick:array[0,…,4]ofsemaphore:=1,1,1,1,1;Philosopheri(i=0,1,2,3,4):repeat thinking;

P(chopstick[i]);

P(chopstick[(i+1)mod5); …… eating; ……

V(chopstick[i]);

V(chopstick[(i+1)mod5); ……untilfalse;遗留问题：

——挑战同步原语的设计者五位哲学家可能同时拿起左边的叉子，则他们都拿不到右边的叉子，于是发生死锁，他们将饿死。解决的办法如下（第1种解法留作课后练习）：

1.

至多只允许四位哲学家同时去拿左边的叉子；2.仅当哲学家左右两边的叉子均可用时才允许他拿起叉子；(这更适于用AND型信号量集求解)3.规定奇数号哲学家先拿起他左边的叉子，而偶数号哲学家先拿起他右边的叉子。（1）竞争临界资源（即系统资源不足）

当系统中供多个进程共享的临界资源（如打印机、公用队列等）的数目不能满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。这个原因在多道程序系统中是无法解除的。

（2）进程推进顺序不当

进程在运行过程中，请求和释放资源的顺序不当，也同样会导致死锁的产生。这个原因在多道程序系统中是可以解除的。2产生死锁的原因（P57）思考题：（北大95研）一个OS有20个进程，竞争使用65个同类资源，申请方式是逐个进行的，一旦某个进程获得它所需要的全部资源，则立即归还所有资源。每个进程最多使用三个资源。若仅考虑这类资源，该系统有无可能产生死锁，为什么？答：不可能。因为死锁产生的原因有两点：系统资源不足或进程推进顺序不当，在本题中，进程所需的最大资源数为60，而系统共有该类资源65个，其资源数已足够系统内各进程使用。3产生死锁的必要条件

——Coffman,1971(P57)互斥条件(mutualexclusion)指进程排他性地使用所获资源，即一个资源一次只能被一个进程使用。占有并请求条件(Holdandwait)指进程保留已经得到的资源，还要求其它的资源。不可剥夺条件(Nopreemption)指进程已获得的资源，在未使用完之前，不能被其它进程强行抢占，只能在使用完时由自己释放。循环等待条件(Circularwait)指发生死锁时，资源分配图(resourceallocationgraph)中存在有向封闭环路。如下图所示。S1P1S2P3S3P2资源结点进程结点分配边请求边某时刻系统的资源分配图死锁必要条件的逆否命题预防死锁的方法。即只要死锁发生的四个必要条件之一不成立，则死锁一定不会发生。产生死锁的四个必要条件中，“互斥条件”由资源的固有特性所决定的，不仅不能改变，相反还应加以保证。实际上，“不剥夺条件”也很难破坏，故具体的预防死锁办法主要是通过破坏“占有并请求条件”和“循环等待条件”来实现的。死锁的必要条件的理论意义4处理死锁的基本方法

①预防死锁②避免死锁（银行家算法）③检测与解除死锁④置之不理（鸵鸟算法）①预防死锁预防死锁：通过在资源分配中设置某些限定条件，破坏产生死锁的四个必要条件之一来实现。但“互斥条件”和“不可剥夺条件”往往由资源的性质决定，很难破坏。所以，具体的预防死锁的方法主要有两种，分别是通过破坏“占有并保持”条件以及“循环等待”条件实现的。⑴静态资源分配法（摒弃“请求和保持条件”）

系统规定每一个进程在开始运行前，都必须一次性地申请其在整个运行过程所需的全部资源。此时，若系统有足够的资源，便把进程想要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它。这样，进程在运行过程中就不会再提出资源请求，从而破坏了请求和保持条件。

静态资源分配法的优缺点：

优点：简单、安全、易实现。(Simpleisbeautiful)（DBMS中进程更新记录前用的两阶段上锁法似此）缺点：

（1）资源被严重浪费（因为一个进程一次获得其所需的全部资源并且独占，其中有可能有些资源很少使用，严重恶化了资源利用率）。（2）进程延迟运行。（当且仅当进程获得其所需的全部资源后，才能开始运行，但有可能有些资源长期被其他进程占用，致使需要该资源的进程迟迟不能运行）

⑵有序资源使用法（摒弃“环路等待条件”）

系统中的所有资源按类都被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。即对同一个进程而言，它一旦申请了一个编号为i的资源，就不允许再申请编号比i小的资源了，因此，破坏了环路等待条件。优点：安全且资源利用率比静态资源分配法有所提高，因为它实际是一种半动态的资源分配法。缺点：实现较困难，不实用。因为很难给出合适的资源编号，不便于系统增添新设备，不便于用户编程，且仍有一定的资源浪费现象。②死锁的避免

死锁的避免是这样一种对付死锁的办法：系统在运行过程中采取动态的资源分配策略，保证系统不进入可能导致系统陷入死锁状态的所谓不安全状态，以避免死锁发生。常用的避免死锁的算法是“银行家算法”，系统采用此法给进程分配资源时，需先判断“如果分配，系统状态是否安全”，这很像银行家放贷前的思考过程。

(1)安全状态与安全序列

1)安全状态

若在某一时刻，系统能按某种进程顺序，如<P1,P2,…,Pn>，来为每个进程分配其所需的资源，直至最大需求，使每个进程均可顺利完成。则称此时系统的状态为安全状态，称这样的一个进程序列<P1,P2,…,Pn>为安全序列。2)不安全状态

若在某时刻，系统无法找到一个安全序列，则称系统处于不安全状态。安全序列的实质是：序列中的每一个进程Pi（i=1,2,…,n）到以后运行完成尚需要的资源量不超过系统当前剩余的资源量与所有在序列中排在它前面的进程当前所占有的资源量之和。安全状态的例子：例2.8假定系统中三个进程P1、P2和P3共享12台磁带机。P1总共要求10台，P2要4台，P3要9台。设在T0时刻，进程P1、P2和P3已经获得5台、2台和2台，还有3台空闲没有分配(如下图所示)。问T0时刻安全吗？解：经分析可知，T0时刻系统是安全的，因为这时存在一个安全序列<P2，P1，P3>。

注意：若把题中的12改为11，则T0时刻系统是不安全的，因为这时系统中虽有2台可用设备，但不存在安全序列。当然，若不按照安全序列分配资源，安全状态可能变为不安全状态，如本题中若下一时刻P3获得1台磁带机的情况。进程最大需求已分配可用P11053P2P34229注意：

（1）系统在某一时刻的安全序列可能不唯一，但这不影响对系统安全性的判断。（2）安全状态是非死锁状态，而不安全状态并不一定是死锁状态。即系统处于安全状态一定可以避免死锁，而系统处于不安全状态则仅仅有可能进入死锁状态。

安全状态不安全状态死锁状态(2)银行家算法银行家算法是最有代表性的避免死锁算法，是Dijkstra(1965)提出的。其模型基于一个小城镇的银行家的放贷行为。该银行家准备向N个客户贷款，他拥有的资金足以满足任一客户的最大资金需求，但不能同时满足所有客户的最大需求。他要求每个客贷款前必须说明自己所要的最大资金量，并且每次提出部分或全部（但不能同时提出全部）资金量申请。他只给有信誉和能力并承诺到期还本付息的客户贷款。该算法已扩充为多资源的银行家算法。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是动态地对每个客户进程每次的资源请求进行检查，看一下如果满足它是否会引起不安全状态。假如是，则不满足该请求；否则就满足它。1)可用资源向量Available[1×m]

记录系统中各类资源的当前可用数目。2)最大需求矩阵Max[n×m]

记录每个进程对各类资源的最大需求量。3)分配矩阵Allocation[n×m]

记录系统给每个进程分配的各类资源数目。4)需求矩阵Need[n×m]

记录每个进程尚需要的各类资源数目。

显然，Need=Max－Allocation。5)请求向量Request[1×m]

记录某个进程当前对各类资源的申请量，它是银行家算法的入口参数。

银行家算法所用的主要数据结构当Pi发出资源请求Requesti后，系统按下述步骤进行检查：step1.如果Requesti

>

Needi,则出错。step2.如果Requesti>Available,则Pi

阻塞；

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

Availablei=Availablei-Requesti;

Allocationi=Allocationi+Requesti; Needi

=Needi-Requesti;step4.

系统执行安全性检测子算法，检查如果实施此次资源分配后，系统是否会处于安全状态。若安全，则完成此次试分配，成功返回；否则，将撤消此次试分配，恢复step3中改过的数据，让进程Pi等待。

银行家算法描述(P60)安全性检测子算法描述(P60)

——此法与死锁检测算法很相似，可对照理解(1)初始化：work=available；/*work是available的影子变量*/

finish=false；/*finish是进程可完成标志向量*/(2)若按进程编号顺序找到了一个可加入安全序列的进程，即：满足条件finishi=false且needi≤work的进程Pi，

则①假设该进程不久将完成任务归还资源，于是置

work=work+allocationi；finishi=true；

②重复执行这一步，直至找不到一个这样的进程为止；(3)若所有进程的可完成标志finish为真，则返回逻辑真值

（表示系统将处于安全状态）；否则，返回逻辑假值（表示不安全）。从理论上讲，银行家算法能有效地避免死锁，而且还不需要死锁预防法中加上的种种限制，如重新运行进程或有序申请资源。但实际上，它缺乏实用价值。因为银行家算法的执行有个前提条件，即要求进程预先提出自己的最大资源请求，并且假设系统拥有的资源总量和支持的进程个数是固定的，而且进程之间是“无关”的。但很少有进程在运行前就知道其所需资源的最大量，而且进程数也不是固定的，而是不断变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。另外，不少进程间有同步要求。总之，死锁预防法过于严格，而死锁避免法更不实用。(3)银行家算法性能评价(4)银行家算法之例例2.9假定系统中有五个进程{P1、P2、P3、P4、P5}和三类资源{A，B，C}，资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示:进程资源情况431002433P4011211222P3600302902P2122200322P1332743010753P0ABCABCABC

ABCAvailableNeedAllocationMax1.T0时刻是否安全?2.Request1(1,0,2)能否响应?3.Request4(3,3,0)能否响应?4.Request0(0,2,0)能否响应?进程资源情况431002433P4011211222P3600302902P2122200322P1332743010753P0ABCABCABC

ABCAvailableNeedAllocationMax资源情况进程ABCABCABCABCFinishWork'AllocationNeedWorkP1332122200532

trueP3532011211743

trueP4743431002745

trueP0745743010755

trueP27556003021057

true解：1.由安检子算法知T0时刻存在安全序列：{P1,P3,P4,P0,P2}，故系统是安全的。P1发出资源请求request1（1,0,2），系统按银行家算法进行检查：

①request1（1,0,2）≤need1（1,2,2）；

②request1（1,0,2）≤available（3,3,2）；

③系统先假定可为P1分配资源，并修改available、allocation1和need1向量，结果资源试分配情况如下表所示：

2.进程资源情况431002433P4011211222P3600302902P2020302322P1

230

743010753P0ABCABCABC

ABCAvailableNeedAllocationMax④再利用安全性检测子算法检查此时系统是否安全，如下表所示：

资源情况进程ABCABCABCABCFinishWork'AllocationNeedWorkP1230020302532

trueP3532011211743

trueP4743431002745

trueP0745743010755

trueP27556003021057

true可知此时存在安全序列：{P1,P3,P4,P0,P2}，故系统是安全的，可立即将P1所申请的资源分配给它。当然{P1,P3,P4,P2,P0}也是一个安全序列。3.P4发出资源请求request4（3,3,0），系统按银行家算法进行检查：

①request4（3,3,0）≤need4（4,3,1）；