操作系统原理第二章

1

计算机操作系统主讲:四川大学计算机学院

刘循liuxun@2

第2章进程的描述与控制

为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。3本章内容:进程的基本概念进程控制进程同步经典进程的同步问题管程机制进程通信线程42.1进程的基本概念前驱图程序顺序执行及其特征程序并发执行及其特征程序的特征与状态进程控制块5

前驱图是一个有向无循环图.

图中每个结点可用于表示一条语句、一个程序段或进程；

结点间的有向边则表示在两结点之间存在的偏序或前趋关系“→”,如果Pi→Pj,称Pi是Pj的前趋，而Pi是Pj的直接后继.2.1.1前驱图6123456

在前趋图中，没有前趋的结点称为初始站点(InitialNode)，没有后继的结点称为终止结点(FinalNode)。

每个结点还具有一个重量(Weight)，它可用该结点所含的程序量或结点的执行时间来计量。2.1.1前驱图72.1.2程序顺序执行及其特征1程序的顺序执行

s1:a:=x+y;s2:b:=a-5;s3:c:=b+1;程序按固定的流程执行下去：S1S2S382程序顺序执行的特征：(1)顺序性-完成前一操作才能进入下一操作；(2)封闭性-运行时独占资源,结果不受外界影响；(3)可再现性-多次执行结果一致。I1C1P1I2C2P22.1.2程序顺序执行及其特征92.1.3程序并发执行及其特征1.程序的并发执行三个进行输入﹑计算﹑打印的程序并发执行：I1I2I3I4C1C2C3C4P1P2P3P410s1:a:=x+2;s2:b:=y+4;s3:c:=a+b;s4:d:=c+b;2.1.3程序并发执行及其特征S1S3S4S2112.程序并发执行时的特征间断性；失去封闭性；不可再现性。2.1.3程序并发执行及其特征12例:程序A和B，如果A:N=N+1,B:Print(N)，

N的初始值为n

若执行顺序为:

N:=N+1;print(N);N:=0;则N值为n+1,n+1,0;

若执行顺序为:

print(N);

N:=N+1;N:=0;则N值为n,n+1,0;

若执行顺序为:

print(N);N:=0;

N:=N+1;为则N值为n,0,1;

可见并发执行时程序结果不可再现.2.1.3程序并发执行及其特征13程序并发执行的条件

程序并发执行，虽然能有效地提高资源利用率和系统的吞吐量，但必须采取某种措施，以便并发程序能保持其“可再现性”。

2.1.3程序并发执行及其特征14

定义符号：R(Pi)＝{a1,a2…,am},用以表示程序A在执行期间所需参考的所有变量的集合，称为“读集“;W(pi)＝{b1,b2…,bn},是程序pi在执行期间要改变的所有变量的集合，称为“写集”。 若两个程序P1和p2能满足下述条件，它们便能并发执行，且具有可再现性。该条件在1966年首先由Bernstein提出．又称为Bernstein条件：R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={}。2.1.3程序并发执行及其特征15

例:有四条语句:

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1S1:a:=x+y的读集为R(S1)={x,y},写集为W(S1)={a};S2:b:=z+1的读集为R(S2)={z},写集为W(S2)={b};S3:c:=a–b的读集为R(S3)={a,b},写集为W(S3)={c};S4:w:=c+1的读集为R(S4)={c},写集为W(S4)={w};16可见:R(S1)∩W(S2)∪R(S2)∩W(S1)∪W(S1)∩W(S2)={},S1与S2可以并发;R(S1)∩W(S4)∪R(S4)∩W(S1)∪W(S1)∩W(S4)={},S1与S4可以并发;R(S1)∩W(S3)∪R(S3)∩W(S1)∪W(S1)∩W(S3)≠{},S1与S3不可并发;R(S2)∩W(S3)∪R(S3)∩W(S2)∪W(S2)∩W(S3)≠{},S2与S3不可并发;172.2进程的描述进程的定义和特征进程的基本状态及转换挂起操作和进程状态的转换进程管理中的数据结构182.2.1进程的定义和特征

它对应虚拟处理机、虚拟存储器和虚拟外设等资源的分配和回收；引入多进程，提高了对硬件资源的利用率，但又带来额外的空间和时间开销，增加了OS的复杂性.

1进程的定义定义：可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。192.进程的特征动态性：进程是程序的执行过程,创建而产生﹑调度而执行﹑撤消而消亡；独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性:进程可以并发执行,而程序却不能.异步性：“虚拟”；结构特征：进程实体由程序段、数据段和进程控制快组成,统称为“进程映像”。2.2.1进程的定义和特征201进程的三种基本状态

进程在运行中不断地改变其运行状态。通常，一个运行进程必须具有以下三种基本状态:

(1)就绪状态(Read)-得到除处理机外所有资源; (2)执行状态(Run)-获得了处理机; (3)阻塞状态(Block)-因某事件暂停执行;

如果再加上”新(New)状态”,”终止(Terminated)状态”共有5种状态。2.2.2进程的基本状态及转换21进程的状态及其转换IO请求或其他事件运行就绪阻塞进程调度中断等待的事件完成新进程结束2.2.2进程的基本状态及转换2三种基本状态的转换22

1进程的挂起状态

(1)挂起状态的引入:终端用户的需要:发现运行情况时终端用户希望程序停下来.父进程的需要:父进程要协调各子进程之间关系.操作系统的需要:挂起进程检查资源使用情况.对换的需要:挂起对换的进程.负荷调节的需要:挂起进程减轻负荷.2.2.3挂起操作和进程状态的转换23进程的状态及其转换IO请求或其他事件

运行活动就绪活动阻塞进程调度中断等待的事件完成(2)引入挂起状态的转换图静止阻塞静止就绪创建结束等待的事件完成挂起挂起释放释放2.2.3挂起操作和进程状态的转换

2引入挂起原语操作后三个进程状态的转换242.2.4进程管理中的数据结构1.操作系统中用于管理控制的数据结构在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。OS管理这些数据结构一般分为以下四类：内存表设备表文件表用于进程管理的进程表252.2.4进程管理中的数据结构2.进程控制块PCB的作用为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块（PCB-ProcessControlBlock）,它是由OS维护的用来记录进程相关信息的唯一标志，当OS创建一个进程时，就为该进程创建了一个PCB。263.进程控制块中的信息:进程标识符信息(内-外标识符);处理机状态信息(通用寄存器﹑指令寄存器﹑程序状态字﹑用户栈指针);进程调度信息(进程状态﹑进程优先级﹑进程调度所需的其它信息﹑事件----阻塞因);进程控制信息(程序和数据地址﹑进程同步和进程通信机制﹑资源清单﹑链接指针).2.2.4进程管理中的数据结构274.进程控制块的组织方式链接方式：各状态的进程形成不同的链表：就绪链表、阻塞链表.索引方式：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表,各状态的运行形成不同的索引表：就绪索引表、阻塞索引表.2.2.4进程管理中的数据结构28作业：P84:2,4,7,8292.3进程控制

操作系统内核进程的创建进程的终止进程的阻塞与唤醒进程的挂起与激活302.3进程控制

为了提供对PCB(和OS其它数据)的保护,通常将处理机的执行状态分为系统态和用户态两种:系统态:又称作特权方式，内核方式，管理方式,控制方式.用户态:通常用户程序运行在用户态.31

将一些与硬件紧密相关的模块:中断处理程序，各种常用设备的驱动程序，以及运行频率较高的模块都安排在紧靠硬件的软件层次中，并使它们常驻内存，以便提高OS的运行效率,并对它们加以特殊的保护。通常把这一部分称为OS的内核。2.3.1操作系统内核321支撑功能中断处理时钟管理原语操作2.3.1操作系统内核332资源管理功能进程管理存储器管理设备管理2.3.1操作系统内核34

2.3.2进程的创建1.进程的层次结构

在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。子进程可以创建跟多的孙进程，由此便形成了一个进程的层次结构。352.3.2进程的创建2.进程图ABCDEFGHIJBCBCBC362.3.2进程的创建3引起进程创建的事件:

--用户登陆

--作业调度

--提供服务

--应用请求

372.3.2进程的创建4进程的创建步骤

--申请空白PCB --为新进程分配资源

--初始化进程控制块

--将新进程插入就绪队列381.引起进程终止的事件

--正常结束

--异常结束:越界﹑保护错﹑特权指令错﹑非法指令错﹑运行超时﹑等待超时﹑算术运算错﹑I/O故障

--外界干预:操作员或操作系统﹑父进程请求﹑父进程终止2.3.3进程的终止392.进程的终止过程：(1)根据被终止进程的标识符．从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即中止该进程的执行．并设置调度标志为真．用于指示该进程被终止后应重新进行调度．选择——新进程，把处理机分配结它。2.3.3进程的终止402.进程的终止过程：(3)若该进程还有子、孙进程，还将其所有子孙进程予以终止，以防它们成为不可控的。(4)将该进程所拥行的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。2.3.3进程的终止412.3.4进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件:请求系统服务;启动某种操作;新数据尚未到来;无新工作可做.422.进程阻塞过程:

正在执行的进程，当发现引起进程阻塞的事件时，无法继续执行，便停止执行﹑改PCB中状态﹑插入到阻塞队列﹑保留处理机状态.3.进程唤醒过程:

阻塞的进程，当发现引起进程阻塞的事件已经完成时，便从阻塞队列中移出﹑改PCB中状态﹑插入就绪队列.2.3.3进程的阻塞与唤醒432.3.5进程的挂起与激活

用户请求将自己挂起或父进程请求将自己的某个子进程挂起时，系统利用挂起原语，将进程挂起。父进程或用户请求激活指定的进程时，用激活原语激活进程。进程的挂起过程:原语:suspend();进程的激活过程:原语:active();挂起激活Active()Suspend()442.4进程的同步引入进程同步的主要任务:

使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。即保证诸进程互斥地访问临界资源。452.4.1进程同步的基本概念1.两种形式的制约关系(1)间接相互制约关系多进程资源共享（互斥):

例如：打印机中打印进程A，B.(2)直接相互制约关系:

表现为多进程执行顺序有先后关系。buffer生产者进程消费者进程462.4.1进程同步的基本概念2临界资源

定义:

在某一时刻只能一个进程独占的资源.

例如:

硬件:打印机,绘图仪,扫描仪等.

软件:数据变量﹑参数等。47生产者——消费者问题:

有n个缓冲区的缓冲池;in指示下一个可投放消息的缓冲区,生产者进程生产并投放一个消息后in+1;out指示下一个可获取消息缓冲区,消费者进程消费并取走一个消息后out+1;

循环缓冲池:in:=(in+1)modn;out:=(out+1)modn;2.4.1进程同步的基本概念482.4.1进程同步的基本概念共享下列变量:varn,integer;typeitem=…;varbuffer:array[0,1,…,n-1]ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;in,out初始化为1;当两个进程单独执行时没有问题:492.4.1进程同步的基本概念

Producer:Repeat

……

produceaniteminnexto;

…….whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;Untilfalse;

502.4.1进程同步的基本概念Consumer:Repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumetheiteminnextc;Untilfalse；51当两个进程并发执行时可能按以下顺序发生:register1:=counter;register2:=counter;register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;

当counter=5时上面执行后正确答案为5(生产一个,消费一个);2.4.1进程同步的基本概念52但是也可以按以下顺序发生:(同样counter=5)register1:=counter;(register1=5)register1:=register1+1;(register1=6)register2:=counter;(register2=5)register2:=register2-1;(register2=4)counter:=register1;(counter=6)counter:=register2;(counter=4)

结果counter=4,与前面的结果不一致,程序并发执行的结果不可再现.原因是变量counter是一个临界资源,应互斥访问.53

3临界区（Criticalsection）

每个进程中访问临界资源的代码段就是临界区.

repeatentrysection;(进入区)

criticalsection;(临界区)

exitsection;(退出区)

remaindersection

（剩余区）

untilfalse

2.4.1进程同步的基本概念544同步机制应遵循的准则

(1)空闲让进

(2)忙则等待

(3)有限等待

(4)让权等待2.4.1进程同步的基本概念55用软件方法解决进程互斥问题(1)算法1:

变量turn表示允许进入临界区的进程编号

repeatwhileturn≠idono-op;criticalsection;turn:=j;remaindersectionuntilfalse;

存在问题是:同一进程不能连续的进入临界区.违背空闲让进的原则.2.4.1进程同步的基本概念56算法2:设置一个数组flag[i];flag[i]=true进程Pi正在临界区;

初始值flag[i]=false所有进程未进入临界区;varflag:array[0,1,…,n]ofboolean;

2.4.1进程同步的基本概念57repeatwhileflag[j]dono-op;flag[i]:=true;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

存在问题:多个进程都看到对方没进临界区而决定进去时则会发生冲突,互不相让.违背忙则等待的原则.2.4.1进程同步的基本概念58算法3:设置一个数组flag[i];flag[i]=true进程Pi希望进入临界区;

同时满足flag[j]=false时才进入临界区;varflag:array[0,1,…,n]ofboolean;2.4.1进程同步的基本概念59repeatflag[i]:=true;whileflag[j]dono-op;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

存在问题:多个进程首先表示自己要进入临界区,再去判断其余进程是否会进入临界区,结果是都认为对方会进入临界区而谦让,都不进去.违背空闲让进的原则.2.4.1进程同步的基本概念602.4.1进程同步的基本概念算法4:设置一个数组flag[i]和一个变量turn;

一个进程为了进入临界区flag[i]=true,turn=j;

同时满足flag[j]=false或者turn=i时才进入临界区;varflag:array[0,1,…,n]ofboolean;

61repeatflag[i]:=true;turn:=j;while(flag[j]andturn=j)dono-op;

criticalsection;

flag[i]:=false;remaindersectionuntilfalse;

不存在问题.2.4.1进程同步的基本概念622.4.2硬件同步机制

1关中断

关中断试试先互斥的最简单的方法之一。在进入锁测试之前关闭中断，知道完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。

缺点：滥用关中断权力可能导致严重后果。关中断时间过长会影响系统效率。关中断方法不适用与多CPU系统。632.4.2硬件同步机制

2利用Test-and-Set指令实现互斥指令:FunctionTS(varlock:boolean):booleanbeginTS:=lock;lock:=ture;end;64利用TS实现进程互斥:repeatwhileTS(lock)doskip;criticalsectionlock:=false;remaindersectionuntilfalse;2.4.2硬件同步机制652.4.2硬件同步机制3利用Swap指令实现互斥Swap指令:ProcedureSwap(vara,b:boolean)vartemp:boolean;begintemp:=a;a:=b;b:=temp;end;662.4.2硬件同步机制利用Swap实现进程互斥:repeatkey:=true;repeatSwap(lock,key);untilkey=false;criticalsectionlock:=false;remaindersectionuntilfalse;672.4.3信号量机制Dijkstra把互斥的关键含义抽象成信号量（semaphore)概念，并引入wait、signal操作作为同步源语。信号量是被保护的量，只有wait、signal操作和信号量初始化操作才能访问和改变它的值。

681整形信号量(1)Wait(s)、signal(s)操作定义wait（S）:whiles≤0dono-ops:=s-1;Signal(s)s=s+1;

注意:Wait(s)、signal(s)是两个原子操作。整形信号量s的值为0还是1，当s<=0时，Wait(s)操作会不停的进行测试.并为遵循让权等待。2.4.3信号量机制692.记录型信号量2.4.3信号量机制Wait(s)、signal(s)操作定义typesemaphore=recordvalue:integer;L:Listofprocess;end;

702.4.3信号量机制2.记录型信号量proceduresignal（s）

vars:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S,L)end;712.4.3信号量机制procedurewait（s）

vars:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S,L)end;2.记录型信号量722.4.3信号量机制2.记录型信号量

在记录型信号量中，S.value的初值表示系统中某类资源的数目。因而又称为资源信号量。当S.value0<0时，表示资源已经分配完毕，进程调用block原语进入阻塞状态。

732.4.3信号量机制

ProducerA:ProducerB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);但是A进程B按下述次序交替进行：ProducerA:wait(Dmutex),Dmutex=0;ProducerB:wait(Emutex),Emutex=0;ProducerA:wait(Emutex),Emutex=-1,A阻塞;ProducerB:wait(Dmutex),Dmutex=-1,B阻塞;最后AB两进程都处于僵持状态。3.AND型信号量742.4.3信号量机制

基本思想:将进程在整个运行过程中所需的所有临界资源,一次性的全部分配给进程,待该进程使用完后再一起释放.

3.AND型信号量752.4.3信号量机制Swait（S1,S2,…,Sn）

ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endfor;else

…….endif;3.AND型信号量762.4.3信号量机制Ssignal（S1,S2,…,Sn）

fori:=1tondoSi:=Si+1;

……endfor;3.AND型信号量772.4.3信号量机制4.信号量集一次需要N个某类临界资源时:Swait（S1,ti,d1,…Sn,tn,dn）

ifS1≥t1and…andSn≥tnthenfori=:=1tondoSi:=Si-di;endfor;else

…….endif;782.4.3信号量机制Ssignal（S1,d1,…Sn,dn）

fori:=1tondoSi:=Si+di;

……endfor;4.信号量集792.4.3信号量机制讨论:Swait(S,d,d),此时在信号量集中只有一个信号量,但允许每次申请d个资源,当发现资源少于d时,不予分配;Swait(S,1,1),此时在信号量为记录型信号量或互斥信号量.Swait(S,1,0),此时在信号量为可控开关.4.信号量集802.4.4信号量的应用1.利用信号量实现互斥生产者-消费者问题:Varmutex:semaphore:=1;beginparbegin81Process1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;end2.4.4信号量的应用1.利用信号量实现互斥822.4.4信号量的应用1.利用信号量实现互斥process2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse；

end;parend832.利用信号量来描述前趋关系S1S2S3S4S5S62.4.4信号量的应用842.4.4信号量的应用vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbeginS1;signai(a);signai(b);end;beginwait(a);S2;signai(c);signai(d);end;beginwait(b);S3;signai(e);end;beginwait(c);S4;signai(f);end;beginwait(d);S5;signai(g);end;beginwait(e);wait(f);wait(g);S6;end;parend;end;852.4.5管程机制1.管程的定义

系统中的各种硬件资源和软件资源均可用数据结构抽象得描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。因此，可以利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。进程对共享资源的申请、释放和其他操作必须通过这组过程，有效得实现进程互斥。

代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称之为管程。862.4.5管程机制2.条件变量

同常，一个进程被阻塞或者挂起的条件可有多个，因此在管程中设置了多个条件变量。

管程中的条件变量都须予以说明，其形式为：conditionx,y；对条件变量的操作仅仅是wait和signal，因此条件变量也是一个抽象得数据类型。(1)x.wait:正在调用管程的进程因条件x需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其他进程可以使用该管程。(2)x.signal:正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择其中一个，如果没有，继续执行原进程，不产生任何结果。87

2.5经典进程同步问题生产者——消费者问题哲学家进餐问题读者写者问题882.5.1生产者——消费者问题

生产者—消费者是同步与互斥的抽象.在前面已对该问题作了描述,但未考虑进程的互斥与同步问题,造成了数据counter的不确定性.下面用信号量机制解决该问题.89

设:生产者和消费者之间的共用缓冲池中具有n个缓冲区,利用互斥信号量mutex使两进程实现对缓冲区的互斥利用.利用资源信号量empty和full分别表示缓冲池中空缓冲区和缓冲池中满缓冲区的数量.生产者和消费者相互等效,只要缓冲池未满,生产者可向缓冲池中送入消息;只要缓冲池未空,消费者可从缓冲池中取走消息;1利用记录型信号量解决生产者---消费者问题2.5.1生产者——消费者问题90varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin1利用记录型信号量解决生产者---消费者问题2.5.1生产者——消费者问题91Producer:beginrepeat

…produceraniteminnextp;

…wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;signal(mutex);signal(full);untilfalse;end;92Consumer:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);consumetheiteminnextc;untilfalse；

end;93parend;End;1利用记录型信号量解决生产者---消费者问题2.5.1生产者——消费者问题94

在本类问题中要注意对互斥信号量mutex的操作wait(mutex)和signal(mutex)必须成对出现:对资源信号量empty和full的操作wait(empty)和signal(empty)﹑wait(full)和signal(full)必须成对出现,但分别处于不同的进程程序中.如生产者进程wait(empty)处于阻塞等待时,则消费者进程signal(empty)将生产者进程唤醒.在生产者进程中的wait(empty)和wait(mutex)﹑消费者进程中的wait(full)和wait(mutex)的前后顺序不能写反,否则会引起两个进程死锁.先释放互斥信号量mutex,后释放资源信号量有利于提高两个进程访问临界资源(缓冲区)的速度.95用Swait(empty,mutex)代替wait(empty)和wait(mutex);用Ssignal(mutex,full)代替signal(mutex)和signal(full);用Swait(full,mutex)代替wait(full)和wait(mutex);用Ssignal(mutex,empty)代替signal(mutex)和signal(empty);2.利用AND信号量解决生产者---消费者问题2.5.1生产者——消费者问题96varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,1,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin2.利用AND信号量解决生产者---消费者问题2.5.1生产者——消费者问题97Producer:beginrepeat

…produceraniteminnextp;

…Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;end;98Consumer:beginrepeatSwait(full,mutex);nextc:=buffer(out);out:=(out+1)modn;Ssignal(mutex,empty);consumetheiteminnextc;untilfalse；

end;parend;End;99生产者—消费者进程:(1)建立管程:

为管程命名为PC,定义数据结构如下:

变量count表示缓冲池中已有的消息数目.put(item)过程:当count≥n,表示缓冲池满,生产者等待.get(item)过程:当count≤0,表示缓冲池空,消费者等待.2.5.1生产者——消费者问题2.利用管程解决生产者---消费者问题100PC管程描述如下:typeproducer-consumer=monitorvarin,out,count:integer;buffer:array[0,1,…,n-1]ofitem;notfull,notempty:condition;

procedureentryput(item)beginifcount≥nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;end;101procedureentryget(item)beginifcount≤0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;end;

beginin:=out:=0;count:=0;end;102(2)应用管程:

producer:beginrepeatproduceaniteminnextp;

PC.put(item);untilfalse;end;consumer:beginrepeat

PC.get(item);consumetheiteminnextc;untilfalse;end;103

如图:哲学家平时在思考，当感到饿时就拿起左右两边的筷子用餐，用餐完毕放下筷子。只有在拿到两支筷子时才能进餐。进餐完毕放下筷子继续思考。2.5.2哲学家就餐问题104

对问题的解决方案：筷子作为临界资源,在一段时间内只允许一个哲学家使用,用一个信号量表示一只筷子,五支筷子用五个信号量,五个信号量构成信号量数组:chopstick[1],chopstick[2],chopstick[3],chopstick[4],chopstick[5];1.利用记录型信号量解决哲学家进餐问题2.5.2哲学家就餐问题105varchopstick:array[0,…,4]ofsemaphore;chopstick[i]=1;Repeatwait(chopstick[i]);wait(chopstick[(i+1)MOD5]);

…eat；

…signal(chopstick[i]);signal(chopstick[(i+1)MOD5);

…think；Untilfalse；106由于哲学家是围着圆桌吃饭,5支筷子编号为1,2,3,4,5.所以要用mod运算.哲学家先拿左边的筷子再拿右边的筷子,成功后便可进餐,进餐后先放左边的筷子再放右边的筷子,该方法可以保证不会有两个相邻的哲学家同时进餐,但可能引起死锁.因为假如五个哲学家同时拿起左边的筷子时,会因每个无第二只筷子可拿而无限等待,产生死锁.107避免哲学家就餐死锁的方法:最多只允许四个哲学家同时进餐,保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使其他哲学家进餐.当哲学家左右两支筷子均可用时,才允许他拿起筷子进餐.规定奇数号哲学家先拿左边的筷子再拿右边的筷子;偶数号哲学家相反.1和2号哲学家竞争1号筷子,1和2号哲学家竞争3号筷子.即都先竞争奇数号筷子,再竞争偶数号筷子,最后总有一个哲学家可以获得两支筷子而进餐.1082.利用AND信号量机制解决哲学家进餐问题varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processirepeatthink;Swait(chopstick[(i+1)MOD5],chopstick[i]);eat；

Ssignal(chopstick[(i+1)MOD5],chopstick[i]);Untilfalse；2.5.2哲学家就餐问题109问题的引出：一个数据文件或记录(数据库中的对象,如表或行)可供若干进程共享，其中有些进程要求读;而另一些进程要求写或修改.把要求读的进程称为“reader进程”,把要求写或修改的进程称为“writer进程”.由于读操作不会引起数据文件混乱,允许多个reader进程同时读一个数据对象,但不会允许一个writer进程和其它writer进程或reader进程同时读一个数据对象(可以用Bernstein条件验证).2.5.3读者——写者问题110用互斥信号量wmutex实现reader进程与writer进程的读或写的互斥;用整形变量readcount表示正在读的进程数目,由于进入读和离开读的进程都要写改变量,该变量是临界资源,用信号量rmutex实现互斥;只有readcounter=0时,writer进程才能写或修改.1.利用记录型信号量解决读者---写者问题2.5.3读者——写者问题111varrmutex,wmutex:semaphore:=1,1;readcouner:integer:=0;beginparbegin1.利用记录型信号量解决读者---写者问题2.5.3读者——写者问题112reader:beginrepeatwait(rmutex);ifreadcounter=0thenwait(wmutex);readcounter:=readcounter+1;signal(rmutex);

…performreadoperation;

…wait(rmutex);readcounter:=readcounter-1;ifreadcounter=0thensignal(wmutex);signal(rmutex);untilfalse;end;113writer:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse；

end;parend;End;1142.利用信号量集机制解决读者---写者问题增加一限制:最多只允许RN个读者同时读;引入信号量L,初值为RN;通过执行wait(L,1,1)操作,控制读者的数目,每当有一个读者进入时,都要先执行wait(L,1,1)操作,使L的值减1,当有RN个读者进入读后,L便减为0,第RN+1个读者要进入读时必然会因wait(L,1,1)操作失败而阻塞.2.5.3读者——写者问题115varRNinteger;L,mx:semaphore:=RN,1;beginparbegin2.利用信号量集机制解决读者---写者问题2.5.3读者——写者问题116reader:beginrepeatSwait(L,1,1);Swait(mx,1,0);

…performreadoperation;

…Ssignal(L,1);untilfalse;end;117writer:beginrepeatSwait(mx,1,1;L,RN,0);performwrteoperation;Ssignal(mx,1);untilfalse；

end;parend;End;118其中,Swait(mx,1,0)语句起着开关的作用;只要无writer进程进入写,mx=1,reader进程就都可以进入读;只要一旦有进程进入写时,其mx=0,则任何reader进程都无法进入读;Swait(mx,1,1,L,RN,0)语句表示仅当即无writer进程写(mx=1)﹑又无reader进程在读(L=RN)时,write进程才能写入临界区写.2.利用信号量集机制解决读者---写者问题2.5.3读者——写者问题119信号量其它应用问题

(1)下图给出了四个进程合作完成某个任务的前趋图，试说明这四个进程间的同步关系，并用程序来实现。S3S1S2S4abcd120vara,b,c,d:semaphore:=0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);end;beginwait(b);S3;signal(d);end;beginwait(c);wait(d);S4;end;parend;end;121(2)设有8个程序prog1,prog2,prog3,…,prog8。它们在并发系统中执行时有如图所示的控制关系，试用信号量机制实现这些程序间的同步。prog1prog2prog3prog4prog5prog6prog7prog8122得到相应的前驱图并设置信号量如下:prog1prog2prog3prog4prog5prog6prog7prog8S13S14S15S23S24S25S36S48S57S78S68123本题是进程同步问题.beginS13,S14,S15,S23,S24,S25,S36,S57,S68,S48,S78

:semaphore:=0,0,0,0,0,0,0,0,0,0,0;parbeginbeginprog1;signal(S13);signal(S14);signal(S15);end;beginprog2;signal(S23);signal(S24);signal(S25);end;beginwait(S13);wait(S23);prog3;signal(S36);end;beginwait(S14);wait(S24);prog4;signal(S48);end;beginwait(S15);wait(S25);prog5;signal(S57);end;beginwait(S36);prog6;signal(S68);end;beginwait(S57);prog7;signal(S78);end;beginwait(S68);wait(S48);wait(S78);prog8;end;parend;end;124

(3)有三个进程PI﹑PC﹑PO协作解决打印问题:PI将文件从磁盘读入主存缓冲区1,每执行一次读一个记录;PC将缓冲区1的内容复制到缓冲区2,每执行一次复制一个记录;PO将缓冲区2的内容打印出来,每执行一次打印一个记录;

缓冲区的大小等于一条记录的大小.用信号量机制解决进程同步.125缓冲区1缓冲区2输入打印PIPCPO126PI与PC共用缓冲区1,PC与PO共用缓冲区2,缓冲区是临界资源.PI与PC不可能同时申请缓冲区1,因为缓冲区1为空时,只有PI可申请并使用;缓冲区1为满时,只有PC可申请并使用.只用同步机制便可使PI与PC互斥使用缓冲区1,设置信号量empty1,full1用于缓冲区1的访问.

同理对PC与PO,设置信号量empty2,full2用于缓冲区2的访问.127varempty1,full1,empty2,full2:semaphore:=1,0,1,0;beginparbeginPI:beginrepeatwait(empty1);puttobuffer1;signal(full1);untilfalse;end;128PC:beginrepeatwait(full1);getfrombuffer1;signal(empty1);wait(empty2);puttobuffer2;signal(full2);untilfalse;end;129PO:beginrepeatwait(full2)getfrombuffer2;signal(empty2);untilfalse;end;parend;end;130

(4)有一个仓库，可以存放A和B两种产品。但要求：每次只能存入一种产品（A或者B）；

-N<(A产品数量-B产品数量)<M.

其中,N和M是正整数.试用P,V操作描述A和B的如库过程.

解答:该题是一个典型的生产者与消费者进程同类的问题；从-N<(A产品数量-B产品数量)<M得:A产品数量-B产品数量<MB产品数量-A产品数量<N131

若只放入A产品而不放入B产品,则A最多可放M-1次便被阻塞,即A进程每操作一次就应当将计数器减1,当计数器值为0时,进程A被阻塞;计数器Sa为资源信号量，初值为M-1.

若只放入B产品而不放入A产品,则B最多可放N-1次便被阻塞,即B进程每操作一次就应当将计数器减1,当计数器值为0时,进程B被阻塞;计数器Sb为资源信号量，初值为N-1.每当放入一个A产品,可令B产品的计数器加1，表示B产品可以多一次放入产品的机会．仓库是临界资源，设置信号量mutex控制两进程的互斥访问．132var

mutex,Sa,Sb:semaphore:=1,M-1,N-1;beginparbeginA产品:beginrepeatwait(Sa);

wait(mutex);

A入库

signal(mutex);

signal(Sb);untilfalse;end;133B产品:beginrepeatwait(Sb);

wait(mutex);

B入库

signal(mutex);

signal(Sa);untilfalse;end;parend;end;134

(5)进程A1,A2,…,An1通过m个缓冲区向进程B1,B2,…,Bn2不断的发送消息．发送和接受工作遵循如下规则：每个发送进程一次发送消息，写入一个缓冲区，缓冲区大小与消息长度一样；对每个消息，B1,B2,…,Bn2都需各接受一次，读入各自的数据区内；

m个缓冲区满时，发送进程等待；没有可读的消息时，接受进程等待．试用信号量机制组织正确的发送和接受操作．135解答:某Ai往buffer中写消息，必须向所有Bj发信号；每个Bj读出消息后都应向发送该消息的Ai回信号，Ai在收到所有Bj的回答时,才可以认为该消息被取走,即缓冲区空出一个.所以一个Ai同所有Bj之间都有单独的同步信号.

设mutex为缓冲区访问的互斥信号量;empty[i]为发送进程i可向缓冲区发送的消息数量;full[i]为接受进程i可从缓冲区接收的消息数量.136var

mutex:semaphore:=1;Fori:=1ton2dobeginempty[i]:=m;/*信号量empty[i]置初值*/full[i]:=0;/*信号量full[i]置初值*/end;

beginparbegin137Ai发送:beginfori:=1ton1dowait(empty[i]);wait(mutex);

发送消息;signal(mutex);fori:=1ton1dosignal(full[i]);end;138Bj接收消息:beginforj:=1ton2dowait(full[j])wait(mutex);

接收消息;signal(mutex);forj:=1ton2dosignal(empty[j]);end;parend;End;139

(6)进程之间存在哪几种相互制约关系？各是什么原因引起？下列活动分别属于那种制约关系？若干同学去图书馆借书；两对举行篮球比赛；流水线生产的各道工序；商品生产和社会消费。

解答:若干同学去图书馆借书；(互斥)

两对举行篮球比赛；(互斥)

流水线生产的各道工序；(同步)

商品生产和社会消费。(同步)140(7)有一阅览室,读者进入阅览室必须先在一张登记表(TB)上登记,该表为每一座位设一个表目,读者离开时要消掉其登记信息,阅览室共有100个座位,为了描述读者的动作,请写用信号量机制写出进程间同步算法。约定:(1)flag为0表示座位空闲,1表示座位被占用。

(2)用语句i=getflag(0)可搜索到一个空座位i,

用语句i.flag=0或1可给标志位赋值。

(3)用i=getname(readname)可搜索到某读者所登记的座位号i;

用=0或=readname可给姓名字段赋值，0表示清除读者姓名。

(4)记数信号量用count,互斥信号量用mutex。141

解答：进入阅览室，首先检查是否有空位子，无则等待有则登记。设置信号量count控制各进程对座位的争夺，读者离去时，便可以释放该座位。登记时要对座位表中各量进行修改，该过程相对于各进程而言为互斥操作，设信号量mutex，控制读者进入和离去时对表的互斥修改。题目所提供的各种语句只是用在修改登记表时所进行的具体操作，对本题的同步互斥问题无任何影响，照抄即可。142varcount,mutex:semaphore:=100,1;

读者进程:begin

进入阅览室

wait(count); wait(mutex); i:=getflag(0); i.flag:=1;:=readname;signal(mutex);143

坐下看书

wait(mutex);i:=getname(readname);:=0;i.flag=0;signal(mutex);signal(count);

离开

end;

144

2.6进程通信进程通信的类型消息传递通信的实现方式直接消息传递系统实例1452.6.1进程通信的类型1共享存储系统（Shared-MemorySystem)

基于共享数据结构的通信方式:

需要程序员直接设置公用数据结构及读写操作﹑进程同步.

低级通信,效率低.

基于共享存储区的通信方式:

在存储器中化出一块共享存储区,进程可以对共享存储区中的数据进行读写.程序员只需向系统申请共享区,并指定共享区的关键字.系统返回申请成功则可直接使用.

高级通信,效率较高.1462.6.1进程通信的类型2管道(pipe)通信系统

所谓管道，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道（共享文件）提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道；而接收管道输出的接受进程（即读进程）则从管道中接收数据。由于发送进程和接收进程是利用管道进行通信的，又称为管道进程。1472.6.1进程通信的类型3消息传递系统（MessagepassingSystem）进程间的数据交换以消息(message)为单位.message是一个报文.OS提供一组发送和接受原语send,receive。实现方式的不同又可分为:

直接通信:直接发送和接收消息.

间接通信:通过邮箱。(3)管道通信（pipe)

协调:互斥,同步,双方存在.1482.6.1进程通信的类型4客户机-服务器系统（Client-Serversystem）这种通信机制，在网络环境的各种应用领域已经成为当前主流的通信机制，主要实现方法分为三类：（1）套接字（socket）（2）远程过程调用（3）远程方法调用1492.6.2消息传递通信的实现方