操作系统课件第二章

1、$第二章第二章 进程管理进程管理第二章第二章 进程管理进程管理 Process Management 在传统的操作系统中，作为资源分配和在传统的操作系统中，作为资源分配和独立运行的基本单位是独立运行的基本单位是进程进程。OSOS所具有的所具有的四大特征也都是基于进程而形成的。四大特征也都是基于进程而形成的。 $第二章第二章 进程管理进程管理$第二章第二章 进程管理进程管理2.4 经典进程同步问题 Classical process synchronization problem一、生产者一、生产者-消费者问题消费者问题(producer and consumer problem)(produc

2、er and consumer problem)若干进程通过有限的共享缓冲区（缓冲池）交换数据。若干进程通过有限的共享缓冲区（缓冲池）交换数据。“生产者生产者”进程不断进程不断将信息放入缓冲区将信息放入缓冲区;“消费者消费者”进程不断进程不断从缓冲区中取出信息从缓冲区中取出信息；共享缓冲区共有共享缓冲区共有N个；个；任何时刻只能有一个进程可对共享缓任何时刻只能有一个进程可对共享缓冲区进行操作冲区进行操作。设缓冲池为循环存储结构。设缓冲池为循环存储结构$第二章第二章 进程管理进程管理r 1）缓冲池不满就可放入，不空就可取出；）缓冲池不满就可放入，不空就可取出；r 2）不允许消费者到空缓冲中取消息

3、（判空，则阻塞）；）不允许消费者到空缓冲中取消息（判空，则阻塞）；r 3）不允许生产者向满缓冲中放消息（判满，则阻塞）；）不允许生产者向满缓冲中放消息（判满，则阻塞）；r 4）对缓冲池的操作要求互斥。）对缓冲池的操作要求互斥。供应方供应方向向使用方向使用方向主要考虑的问题：主要考虑的问题： 缓冲区满或空；缓冲区满或空； 竞争条件。竞争条件。$第二章第二章 进程管理进程管理 (2)(3)要求同步要求同步，需设置，需设置私有信号量私有信号量:n empty生产者进程的私用信号量（初值为生产者进程的私用信号量（初值为n)；n full消费者进程的私用信号量（初值为消费者进程的私用信号量（初值为0）

4、(4)要求互斥要求互斥，设置，设置公用信号量公用信号量n mutex保证生产者进程和消费者进程之间的互斥保证生产者进程和消费者进程之间的互斥（初值为（初值为1）。）。 $第二章第二章 进程管理进程管理生产者消费者动画演示（1）$第二章第二章 进程管理进程管理生产者消费者动画演示（生产者消费者动画演示（2）$第二章第二章 进程管理进程管理生产者消费者动画演示（生产者消费者动画演示（3）$第二章第二章 进程管理进程管理生产者消费者动画演示（生产者消费者动画演示（4）$第二章第二章 进程管理进程管理produce(data)；Begin wait(empty); wait(mutex); 送数据入缓

5、冲区单元送数据入缓冲区单元 Signal(mutex)； Signal(full);End；consume(data)；Begin wait(full); Wait(mutex); 消费；消费； signal(mutex); Signal(empty)；End；各生产者进程使用的过程各生产者进程使用的过程produce (data)各消费者使用的过程各消费者使用的过程consume (data)可描述如下：可描述如下：$第二章第二章 进程管理进程管理注：注：一般说来：一般说来：singalsingal原语是释放资源原语是释放资源的，可以任意顺序出现，的，可以任意顺序出现，waitwait原语不

6、然，原语不然，如果次序混乱将造成如果次序混乱将造成死锁死锁。$第二章第二章 进程管理进程管理设有设有n个缓冲区，为实现对缓冲池的互斥操作：个缓冲区，为实现对缓冲池的互斥操作：l互斥信号量互斥信号量mutex；资源信号量资源信号量empty表示空缓冲的个表示空缓冲的个数，数，full表示满缓冲的个数；表示满缓冲的个数；l 定义数组定义数组buffer 表示缓冲区。表示缓冲区。l 输入指针输入指针in指示下一个可放消息的缓冲区；指示下一个可放消息的缓冲区；输出指针输出指针out指示下一个可取消息的缓冲区。指示下一个可取消息的缓冲区。var mutex,empty,full：semaphore ：1

7、，n，0； buffer：array0，n-1 of item; in , out : integer：=0，0；$第二章第二章 进程管理进程管理parbegin producer:begin repeat producer an item in nextp; wait(empty); wait(mutex) ; buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full) ; until false; endconsumer: begin repeat wait(full) ; wait(mutex); nextc:=buf

8、fer(out); out:=(out+1) mod n; signal(mutex); signal(empty); until false; endParend$第二章第二章 进程管理进程管理1）wait(mutex)和和signal(mutex)必成对出现必成对出现2）empty和和full的的wait和和signal操作也必成对出现，操作也必成对出现，但是在不同的进程中。但是在不同的进程中。3）wait原语顺序不能颠倒，原语顺序不能颠倒，signal原语顺序可任意。原语顺序可任意。思考：思考： P82P82习题习题2323、2424 $第二章第二章 进程管理进程管理parbegin p

9、roducer:begin repeat producer an item in nextp; buffer(in):=nextp; in:=(in+1) mod n; until false; endconsumer: begin repeat nextc:=buffer(out); out:=(out+1) mod n; until false; endParend$第二章第二章 进程管理进程管理二、哲学家进餐问题二、哲学家进餐问题（Dining Philosopher Problem）准备进餐准备进餐进进餐餐准备进餐准备进餐进餐进餐 五个哲学家，共用一张五个哲学家，共用一张圆桌，五支筷子

10、。圆桌，五支筷子。 哲学家有两种状态：哲学家有两种状态：“思考思考”和和“进餐进餐”。 进餐时只能取靠近他的进餐时只能取靠近他的左右的筷子，而且拿到两左右的筷子，而且拿到两支时才可进餐。完后，放支时才可进餐。完后，放下筷子继续思考。下筷子继续思考。$第二章第二章 进程管理进程管理r 基本工作：思考，进餐。基本工作：思考，进餐。r 同步？同步？r 互斥？互斥？ 临界资源为筷子。一只筷子临界资源为筷子。一只筷子(编号为编号为i) 一个互斥信号量一个互斥信号量 可定义一个信号量数组来描述五支筷子。可定义一个信号量数组来描述五支筷子。 var chopstick:array0.4 of semapho

11、re 所有信号量初值为所有信号量初值为1， :=1, 1, 1, 1, 1;$第二章第二章 进程管理进程管理Var chopstick: array 0.4 of semaphore:=1, 1, 1, 1, 1; Begin Parbegin process i ( i=0, 1, 2, 3, 4): begin Repeat until false; end parendend哲学家进餐活动可描述为：哲学家进餐活动可描述为： Think； wait(chopsticki)； wait(chopsticki+1 mod 5)； eat ； signal(chopsticki； signal(

12、chopsticki+1 mod 5)；此算法有无问题？此算法有无问题？$第二章第二章 进程管理进程管理r 1) 规定在拿到左筷子后，先检查右筷子是否可用。若不可规定在拿到左筷子后，先检查右筷子是否可用。若不可 用，则先放下左筷子，等一段时间再重复整个过程。用，则先放下左筷子，等一段时间再重复整个过程。 但该方法可能出现但该方法可能出现“饥饿饥饿”现象现象哲学家进餐哲学家进餐“死锁死锁”问题解决方法问题解决方法r 2）至多允许四个人同时进餐，保证至少一个能进餐。）至多允许四个人同时进餐，保证至少一个能进餐。 设一个信号量设一个信号量v，初值为，初值为4。r 3）规定奇数号人先拿左筷子，后拿右筷

13、子；偶数号人先拿）规定奇数号人先拿左筷子，后拿右筷子；偶数号人先拿右筷子，后拿左筷子。五个哲学家都先竞争奇数号筷子，获右筷子，后拿左筷子。五个哲学家都先竞争奇数号筷子，获得后再竞争偶数号筷子。最后总有一个哲学家能获得两只筷得后再竞争偶数号筷子。最后总有一个哲学家能获得两只筷子。子。$第二章第二章 进程管理进程管理0123401234r 4）用）用AND信号量机制信号量机制可获得最简洁解法。可获得最简洁解法。$第二章第二章 进程管理进程管理$第二章第二章 进程管理进程管理AND信号量实现哲学家就餐描述信号量实现哲学家就餐描述var chopstick:array 0,4 of semaphore

14、:=(1,1,1,1,1);process i repeat think; eat; until false; 哲学家问题对于多个竞争进程互斥地访问有限资源哲学家问题对于多个竞争进程互斥地访问有限资源( (如如I/OI/O设备设备) )这一类问题的建模十分有用。这一类问题的建模十分有用。 $第二章第二章 进程管理进程管理 一个数据对象被多个进程共享。其中有些进程要求读，另一个数据对象被多个进程共享。其中有些进程要求读，另一些进程要求写或修改。要求读的进程称为一些进程要求写或修改。要求读的进程称为“reader进程进程”；其它的称为其它的称为“writer进程进程”。允许多个允许多个reader

15、进程同时执行；不进程同时执行；不允许一个允许一个writer进程和其它进程和其它reader进程或进程或writer进程同时访问进程同时访问共享对象。共享对象。l a、多个、多个reader可同时访问这组共享数据可同时访问这组共享数据并发并发；l b、多个、多个writer不可同时访问这组共享数据不可同时访问这组共享数据互斥；互斥；l c、reader与与writer不可同时访问这组共享数据不可同时访问这组共享数据互斥互斥 它为数据库访问建立了一个模型。它为数据库访问建立了一个模型。 三、读者三、读者-写者问题写者问题（Reader/Writer ProblemReader/Writer Pr

16、oblem）$第二章第二章 进程管理进程管理r1r2rnwRreadcount信号量设置信号量设置 Wmutex：W/R和和W/W的互斥。的互斥。 Rmutex：读者对读者对readcount的互斥操作。的互斥操作。控制变量设置：控制变量设置：Readcount 记录读的个数。记录读的个数。$第二章第二章 进程管理进程管理申请申请Rmutex若若readcount=0申请申请Wmutexreadcount+1 读操作读操作释放释放Rmutex申请申请Rmutexreadcount1若若readcount=0释放释放Wmutex释放释放Rmutexvar rmutex,wmutex:semaph

17、ore:=1,1 readcount:integer:=0;parbegin reader:begin wait(rmutex) if readcount=0 then wait(wmutex) readcount:=readcount+1 signal(rmutex) 读操作读操作 wait(rmutex) readcount:=readcount-1 if readcount=0 then signal(wmutex) signal(rmutex)endwriter:begin wait(wmutex) 写操作写操作 signal(wmutex) EndParend 读者写者问题描述读者写

18、者问题描述$第二章第二章 进程管理进程管理问？若一个若一个Writer进程正在写，则进程正在写，则Reader进程和其他进程和其他Writer进程的状态和所进程的状态和所执行到的位置？执行到的位置？本算法为读者优先算法，即当读者进行读时，写者必须等待，直到所本算法为读者优先算法，即当读者进行读时，写者必须等待，直到所有读者均离开，写者才能进入。存在的问题是什么？有读者均离开，写者才能进入。存在的问题是什么？写者优先：写者优先：如果一个读者申请进行读操作时已有另一写者在等待访问如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操共享资源，

19、则该读者必须等到没有写者处于等待状态后才能开始读操作。存在的问题是什么？作。存在的问题是什么？公平策略：规则公平策略：规则l 1：在一个读序列中，若有写者等待，则不允许新来读者开始执行。：在一个读序列中，若有写者等待，则不允许新来读者开始执行。l 2：在一个写操作结束时，所有等待读者应比下一个写者有更高优：在一个写操作结束时，所有等待读者应比下一个写者有更高优先权。先权。问：对于该公平策略，应如何予以解决呢？问：对于该公平策略，应如何予以解决呢？$第二章第二章 进程管理进程管理var RN integer; L,mx:semaphore:=RN,1; begin parbegin reader

20、: begin repeat Swait(L,1,1)； Swait(mx,1,0); perform read operation Ssignal(L,1); until false; endwriter:begin repeat Swait(mx,1,1;L,RN,0);perform write operation Ssignal(mx,1);until false;endparendend 信号量集机制解决读者写者问题信号量集机制解决读者写者问题$第二章第二章 进程管理进程管理四、打瞌睡的理发师问题四、打瞌睡的理发师问题 理发店里有一位理发师，一把理理发店里有一位理发师，一把理发椅和发

21、椅和N N把供等候理发的顾客坐的把供等候理发的顾客坐的椅子椅子； 理发师为理发椅上的顾客理发，理发师为理发椅上的顾客理发，没有顾客就在理发椅上睡觉；没有顾客就在理发椅上睡觉； 第一个顾客到来第一个顾客到来，他必须先唤醒，他必须先唤醒理发师理发师； 如如果顾客来时理发师正在果顾客来时理发师正在忙忙，若若有空椅子有空椅子，则则坐下来等；否则离开坐下来等；否则离开。$第二章第二章 进程管理进程管理说说 明：明：理发师和每位顾客都分别是一个进程。理发师和每位顾客都分别是一个进程。r 理发师：理发师：看是否有顾客，若没有，在理发椅上睡觉；否则，看是否有顾客，若没有，在理发椅上睡觉；否则，为等待最久的顾客

22、服务，等待人数减为等待最久的顾客服务，等待人数减1。r 顾客：顾客：先看有无空座位先看有无空座位(等候的顾客数是否少于椅子数等候的顾客数是否少于椅子数)，若，若有则等，等待人数加有则等，等待人数加1；若理发师正瞌睡，则将其唤醒；否；若理发师正瞌睡，则将其唤醒；否则，离开。则，离开。r 理发师和顾客的关系？理发师和顾客的关系？l 变量变量waiting，用于记录等候的顾客数，初值为，用于记录等候的顾客数，初值为0。由于它不。由于它不是信号量，因此可对其进行增减等操作。是信号量，因此可对其进行增减等操作。l 设顾客座椅数（设顾客座椅数（chairs）为常量）为常量5。$第二章第二章 进程管理进程管

23、理# define CHAIRS 5 /*为等待的顾客准备的椅子数为等待的顾客准备的椅子数*/semaphore customers=0; /*等待服务的顾客数等待服务的顾客数*/ semaphore barbers=0; /*等待顾客的理发师数等待顾客的理发师数*/ semaphore mutex=1; /*用于互斥用于互斥*/ int waiting=0; /*等待的顾客等待的顾客(还没理发的还没理发的)*/ 三个信号量三个信号量nCustomers：用来记录等候理发的顾客数用来记录等候理发的顾客数(不包括正在理不包括正在理发的顾客发的顾客)，初值为，初值为0；nBarbers：等候顾客的

24、理发师数，初值为等候顾客的理发师数，初值为0；nMutex：用于对用于对waiting 变量的互斥。变量的互斥。信号量设置和变量定义信号量设置和变量定义$第二章第二章 进程管理进程管理Void customers(void) wait(mutex); /*互斥进入临界区互斥进入临界区*/ If(waiting0 S0 表示有表示有S S个资源可用个资源可用S=0 S=0 表示无资源可用表示无资源可用S0 S0 则则| S | S |表示表示S S等待队列中的进程个数等待队列中的进程个数P(S): P(S): 表示申请一个资源表示申请一个资源 V(S)V(S)： 表示释放一个资源。表示释放一个资

25、源。信号量的初值应该大于等于信号量的初值应该大于等于0 01 信号量的物理含义：信号量的物理含义：$第二章第二章 进程管理进程管理l 当为当为互斥操作互斥操作时，它们同处于时，它们同处于同一进程同一进程; ;l 当为当为同步操作同步操作时，则时，则不在同一进程不在同一进程中出现中出现; ;l 如果如果P(S1)P(S1)和和P(S2)P(S2)两个操作在一起，那么两个操作在一起，那么P P操作的顺操作的顺序至关重要序至关重要, ,一个同步一个同步P P操作与一个互斥操作与一个互斥P P操作在一起操作在一起时时同步同步P P操作在互斥操作在互斥P P操作前操作前；l 而两个而两个V V操作的顺序

26、无关紧要。操作的顺序无关紧要。2 P.V操作必须成对出现操作必须成对出现:$第二章第二章 进程管理进程管理优点：优点： 简单，而且表达能力强简单，而且表达能力强（用（用P.V操作可解决任何同步互斥操作可解决任何同步互斥问题）。问题）。缺点：缺点： 不够安全；不够安全；P.V操作使用不当会出现死锁；遇到复杂同步操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。互斥问题时实现复杂。3 P.V操作的优缺点操作的优缺点$第二章第二章 进程管理进程管理2.5 管程机制 Monitor Mechanism 信号量机制为互斥、同步问题的解决提供了有效灵活的工信号量机制为互斥、同步问题的解决提供了有效灵

27、活的工具，但要求在访问临界资源的进程中自备具，但要求在访问临界资源的进程中自备wait和和signal操作，操作，加长了进程的长度，还易产生死锁。加长了进程的长度，还易产生死锁。signal(mutex) CSwait(mutex)wait(mutex) CSwait(mutex)遗漏了遗漏了wait或或signal例如：利用信号量实现互斥。例如：利用信号量实现互斥。$第二章第二章 进程管理进程管理 集中集中管理分散在进程中的临界段。管理分散在进程中的临界段。 1971年，年，Dijkstra提出，为每一临界资源设置一个提出，为每一临界资源设置一个“秘书秘书”进程。访问该临界资源的进程都需先报

28、告进程。访问该临界资源的进程都需先报告“秘秘书书”，由，由“秘书秘书”实现诸进程的同步。实现诸进程的同步。Hoare(1974)和和Hansen(1975)，发展为，发展为（Monitors）。）。 把并发进程间的操作，集中于相应的管程中。把并发进程间的操作，集中于相应的管程中。 管程与管程与信号量机制功能等价，且更容易控制。信号量机制功能等价，且更容易控制。解决方法：解决方法：$第二章第二章 进程管理进程管理一、管程的定义一、管程的定义（The definition of monitor）1 定义：定义： “2.5.1 管程的基本概念管程的基本概念The basic concepts of

29、monitor 2 基本思想：基本思想：把信号量及其操作原语封装在一个对象内部，即把信号量及其操作原语封装在一个对象内部，即将共享资源以及针对共享资源的所有操作集中在一个模块中。将共享资源以及针对共享资源的所有操作集中在一个模块中。可以函数库的形式实现。一个管程就是一个基本程序单位，可可以函数库的形式实现。一个管程就是一个基本程序单位，可以单独编译。以单独编译。$第二章第二章 进程管理进程管理 1) 管程名称；管程名称； 2) 局部于管程的共享变局部于管程的共享变量说明量说明(临界资源描述临界资源描述)； 3) 对该数据结构进行操对该数据结构进行操作的一组过程（即对临界作的一组过程（即对临界资

30、源进行操作的部分资源进行操作的部分)； 4) 对局部于管程的数据对局部于管程的数据设置初始值的语句。设置初始值的语句。二、二、 管程的组成管程的组成（The Composition of Monitor）$第二章第二章 进程管理进程管理type monitor-name=monitor variable declarations procedure entry P1(); beginend; procedure entry Pn(); beginend; begin initialization code end $第二章第二章 进程管理进程管理 1 1）局部于局部于管程的管程的数据结构数据结

31、构仅能被仅能被局部于局部于管程的管程的过程过程访问访问；反之，局部于管程的过程也仅能访问管程内的数据结构。；反之，局部于管程的过程也仅能访问管程内的数据结构。 2 2）一个进程通过）一个进程通过调用管程内调用管程内的一个的一个过程过程进入管程，因此进入管程，因此管程有很好的封装性。管程有很好的封装性。 3 3）为了保证共享变量的数据一致性，任一时刻管程中只）为了保证共享变量的数据一致性，任一时刻管程中只能有能有一个活跃的进程一个活跃的进程。其他调用该管程的进程都被挂起，等。其他调用该管程的进程都被挂起，等待管程变为可用，即：管程能有效实现进程互斥访问资源。待管程变为可用，即：管程能有效实现进程

32、互斥访问资源。 三、管程的特性三、管程的特性（ The peculiarity of monitor）$第二章第二章 进程管理进程管理 当一个已进入管程的进程等待时，释放管程的互斥使当一个已进入管程的进程等待时，释放管程的互斥使用权；当已进入管程的一个进程（用权；当已进入管程的一个进程（P）唤醒另一个进程）唤醒另一个进程(Q)时，两者必须有一个退出或停止使用管程。时，两者必须有一个退出或停止使用管程。处理方法有三种：处理方法有三种：等待，继续，直到等待或退出。等待，继续，直到等待或退出。等待，继续，直到退出或等待。等待，继续，直到退出或等待。规定规定P的唤醒操作为管程中最后一个可执行的操作。的

33、唤醒操作为管程中最后一个可执行的操作。Hoare采用采用Hansen建议建议说说 明明$第二章第二章 进程管理进程管理图图2 21111管管程程示示意意图图EntranceQueue ofEnteringProcessesMonitior Waiting Area Condition c1C1.wait. . . .condition cn. . . .Cn.waitUrgent Queuecsignal ExitM0NITOR Local DataCondition VariablesProcedure 1Procedure kInitialization Code$第二章第二章 进程管理进

34、程管理四、管程实现互斥和同步四、管程实现互斥和同步1 互斥互斥 管程的第三个特性，使他们能有效的完成互斥。进入管程管程的第三个特性，使他们能有效的完成互斥。进入管程的互斥由编译器负责，写管程的人无需关心。的互斥由编译器负责，写管程的人无需关心。2 同步同步 管程实现同步，需设置：管程实现同步，需设置：l 条件变量条件变量x，表示等待原因。，表示等待原因。l 利用利用wait和和signal操作表示因等待原因出现而等待、操作表示因等待原因出现而等待、唤醒一个某原因而等待的进程。唤醒一个某原因而等待的进程。$第二章第二章 进程管理进程管理& 设设var x:condition，则可有，则可有 x.

35、wait因等待因等待x而阻塞，直至其他进程执行而阻塞，直至其他进程执行x.signal。 x.signal唤醒一个因等待唤醒一个因等待x而阻塞的进程。而阻塞的进程。 如果如果x等待队列中无进程阻塞，该操作不产生任何作用。（与等待队列中无进程阻塞，该操作不产生任何作用。（与信号量的信号量的signal不同）不同）& 如：因共享资源忙而进程等待，条件变量可定义为：如：因共享资源忙而进程等待，条件变量可定义为：nonbusy：condiction。 则则wait为：为：nonbusy.wait，signal 为：为：nonbusy.signal条件变量和相关操作条件变量和相关操作$第二章第二章 进程

36、管理进程管理 首先建立管程名为首先建立管程名为PC，并定义其包含的两个过程：，并定义其包含的两个过程：1）put(item)为生产者放消息过程。为生产者放消息过程。count表示已有的消息数表示已有的消息数目。目。countn，表缓冲池已满。生产者需等待。，表缓冲池已满。生产者需等待。2）get(item)为消费者取消息过程。为消费者取消息过程。 count0，表缓冲池已空，表缓冲池已空，消费者等待。消费者等待。PC管程的描述为：管程的描述为：Type PC=monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull

37、,notempty:condition; 2.5.2 利用管程解决生产者利用管程解决生产者消费者问题消费者问题procedure entry put(item) begin if countn then notfull.wait bufferin:=nextp in:=(in+1) mod n count:=count+1 if notempty.quene then notempty.signal endprocedure entry get(item) begin if count0 then notempty.wait nextc:=bufferout out:=(out+1) mod

38、n count:=count-1 if notfull.queue then notfull.signal endbegin in:=out:=0; count:=0; end$第二章第二章 进程管理进程管理producer:begin repeat produce an item in nextp PC.put(nextp) until falseend consumer:begin repeat PC.get(item) consume the item in nextc until falseend$第二章第二章 进程管理进程管理练练 习习 1 设某计算机有两个设某计算机有两个I/OI/

39、O通道：分别挂一台输入机和一台通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区据逐一输入到缓冲区B1B1，然后再复制到缓冲区，然后再复制到缓冲区B2B2，并，并在打印机上打印出来。在打印机上打印出来。 问：系统可设哪些进程来完成这个任务？用问：系统可设哪些进程来完成这个任务？用P.VP.V原语写原语写这些进程的同步算法。这些进程的同步算法。 $第二章第二章 进程管理进程管理& 系统可设系统可设3 3个进程：输入进程个进程：输入进程R R、复制进程、复制进程C C、打印进程、打印进程P P；& 这些进程之间

40、的相互制约关系：这些进程之间的相互制约关系： R R受受C C的约束；的约束；C C受受R R、P P的约束；的约束；P P受受C C的约束。的约束。 & 信号量设置信号量设置 B1fullB1full：缓冲区：缓冲区B1B1满，初值满，初值0 0； B1emptyB1empty：缓冲区：缓冲区B1B1空，初值空，初值=1=1； B2fullB2full：缓冲区：缓冲区B2B2满，初值满，初值=0=0； B2emptyB2empty：缓冲区：缓冲区B2B2空，初值空，初值=1=1。 & 同步算法如下：同步算法如下：$第二章第二章 进程管理进程管理R进程进程P(B1empty)；输入信息到输入信

41、息到B1;V(B1full)；C进程进程P(B1full)；从从B1中取出信息中取出信息;V(B1empty)；P(B2empty)；加工信息加工信息结果送入结果送入B2;V(B2full)；P进程进程P(B2full)；从从B2取出信息打印取出信息打印;V(B2empty)；$第二章第二章 进程管理进程管理练练 习习 2 a,b 两点间是一段东西向的单行车道，现要设计一个自两点间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：动管理系统，管理规则如下：当当ab间有车行驶时，同向车可以同时驶入间有车行驶时，同向车可以同时驶入ab段，但段，但反向车必须在反向车必须在ab段外等待；

42、段外等待；当当ab间无车时，间无车时，a（或（或b）的车辆可以进入）的车辆可以进入ab段，但段，但不能从不能从a，b点同时驶入；点同时驶入； 请用请用wait,signal工具对工具对ab段实现正确管理。段实现正确管理。ab$第二章第二章 进程管理进程管理r 互斥：双方互斥进入单行道；互斥：双方互斥进入单行道；互斥信号量互斥信号量r 而同方向的车可同时进入，故每个方向等待进入车道的而同方向的车可同时进入，故每个方向等待进入车道的第一辆车需争夺进入权，一旦争得进入权，同方向的车第一辆车需争夺进入权，一旦争得进入权，同方向的车随意进入，否则需等对方的车都驶出后才能进入。为此，随意进入，否则需等对方

43、的车都驶出后才能进入。为此，双方均应设置双方均应设置计数器计数器记录该方向是否有车辆在行驶。斥记录该方向是否有车辆在行驶。斥进入的，进入的，r 保证计数器互斥使用的保证计数器互斥使用的互斥信号量互斥信号量。var mutex, ab,ba：Semaphore： 1,1,1$第二章第二章 进程管理进程管理Pab：Wait(ab) Ca+ If Ca=1 then wait(mutex);Signal(ab) enter; wait(ab)Ca- -; if Ca=0 then signal(mutex)；signal(ab);Pba:wait(ba)； Cb+; If Cb=1 then wai

44、t(mutex)；signal(ba)； enter;wait(ba)； Cb-; if Cb=0 then signal(mutex)signal(ba);$第二章第二章 进程管理进程管理练习练习3 图书馆问题图书馆问题l 图书馆有图书馆有100个座位，有一张登记表，要求：个座位，有一张登记表，要求： 阅读者进入时登记，取得座位号；阅读者进入时登记，取得座位号； 出来时，注销；出来时，注销； 登记表同时只能由一个人使用；登记表同时只能由一个人使用；l 用用P、V原语描述原语描述一个读者一个读者的使用过程。的使用过程。$第二章第二章 进程管理进程管理&一个读者有三种操作，一个读者有三种操作，进

45、入进入、阅读、阅读、退出退出$ 其中，进入和退出操作要其中，进入和退出操作要互斥互斥使用登记卡，因此，使用登记卡，因此，登记卡作为临界资源。登记卡作为临界资源。$ 进入进入要申请座位，若座位已满，否则不能进入；要申请座位，若座位已满，否则不能进入；$ 退出退出要释放座位。要释放座位。& 有两个进程（进入和退出），设两个信号量：有两个进程（进入和退出），设两个信号量：$进入私有信号量进入私有信号量SN，表示座位数，初值为，表示座位数，初值为100；$互斥信号量互斥信号量mutex，初值为初值为1 。$第二章第二章 进程管理进程管理Reader(int i)BeginEnter()；阅读阅读;Ou

46、ter()EndEnter() Begin P(SN)； P(mutex)； 登记；登记； V(mutex)； End Outer() Begin P(mutex); 注销；注销； V(mutex); V(SN); End $第二章第二章 进程管理进程管理练练 习习 4三个进程三个进程R、W1、W2共享一个缓冲区共享一个缓冲区Buf。进程。进程R读入数据到读入数据到Buf中；中；若缓冲区中的数为奇数，则进程若缓冲区中的数为奇数，则进程W1将其取出显示；若缓冲区中的数将其取出显示；若缓冲区中的数为偶数，则进程为偶数，则进程W2将其取出显示。对它们有如下的限制条件：将其取出显示。对它们有如下的限制

47、条件： 1）缓冲区中每次只能存放一个数；）缓冲区中每次只能存放一个数； 2）仅当缓冲区中没有数，或）仅当缓冲区中没有数，或W1或或W2将数取走后，进程将数取走后，进程R才可以才可以将新读入的数放到缓冲区中；将新读入的数放到缓冲区中； 3）进程）进程W1或或W2对每次存入缓冲区中的数只能显示一次，且对每次存入缓冲区中的数只能显示一次，且W1和和W2都不能从空的缓冲区中取数。都不能从空的缓冲区中取数。假定开始时，缓冲区为空。利用记录型信号量及假定开始时，缓冲区为空。利用记录型信号量及wait、signal操作写出操作写出三个并发进程正确工作程序。三个并发进程正确工作程序。$第二章第二章 进程管理进

48、程管理var s,s1,s2:semaphore:=1,0,0begin parbegin PR:begin repeat 从输入设备读到一个数从输入设备读到一个数B; wait(s); 放入放入; if B=奇数奇数 then signal(s1); else signal(s2); until false; end; PW2:begin repeat wait(s2); y:=B; signal(s); 打印打印y； until false; end;parendPW1:begin repeat wait(s1); x:=B; signal(s); 打印打印x； until false;

49、end;$第二章第二章 进程管理进程管理苹果桔子问题苹果桔子问题 桌上有一只盘子，每次只能放入一只水桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果果；爸爸专向盘子中放苹果(apple)(apple)，妈妈，妈妈专向盘子中放桔子专向盘子中放桔子(orange)(orange)，一个儿子专，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。里的苹果。$第二章第二章 进程管理进程管理sp:semaphore； /* 盘子里可以放几个水果盘子里可以放几个水果 */sg1:semaphore； /* 盘子里有桔子盘子里有桔子 */sg2:semaph

50、ore； /* 盘子里有苹果盘子里有苹果 */信号量初值信号量初值n sp := 1; /* 盘子里允许放一个水果盘子里允许放一个水果*/n sg1 := 0; /* 盘子里没有桔子盘子里没有桔子 */n sg2 := 0; /* 盘子里没有苹果盘子里没有苹果*/$第二章第二章 进程管理进程管理cobegincobeginprocess fatherprocess father beginbegin repeat repeat 削一个苹果削一个苹果；P(sp);P(sp);把苹果放入把苹果放入plateplate；V(sg2);V(sg2); until false; until false;

51、end;end;process motherprocess mother beginbegin repeat repeat 剥一个桔子剥一个桔子；P(sp);P(sp);把桔子放入把桔子放入plateplate；V(sg1);V(sg1); until false; until false;end;end;process sonprocess son beginbegin repeat repeat P(sg1); P(sg1);从从plateplate中取桔子；中取桔子；V(sp);V(sp);吃桔子；吃桔子； until false;until false;end;end;process

52、daughterprocess daughter beginbegin repeat repeat P(sg2); P(sg2); 从从plateplate中取苹果；中取苹果； V(sp);V(sp); 吃苹果；吃苹果； until false;until false;end;end;coendcoend$第二章第二章 进程管理进程管理 void reader() while(1) wait(queue); wait(Rmutex); if(0 = readcount)wait(mutex); readcount = readcount + 1; signal(rdcntmutex); sig

53、nal(queue); read . wait(Rmutex); readcount = readcount - 1; if(0 = readcount)signal(mutex); signal(Rmutex); void writer() while(1) wait(Wmutex); if(0 =writecount)wait(queue); writecount = writecount + 1; signal(Wmutex); wait(mutex); write . signal(mutex); wait(Wmutex); writecount = writecount - 1; i

54、f(0 = writecount)signal(queue); signal(Wmutex); semaphore mutex=1, Rmutex=1, Wmutex=1, queue=1;int readcount = 0, writecount = 0; $第二章第二章 进程管理进程管理 $第二章第二章 进程管理进程管理while(1) wait(z); /用来保证写者优先用来保证写者优先 wait(rsem); /判断有没有写进程在临界区，有则等待，否则拒绝新判断有没有写进程在临界区，有则等待，否则拒绝新的写进程进来的写进程进来 wait(x); /开始对开始对readcount的互斥访

55、问的互斥访问 readcount+; /更新读进程数量更新读进程数量 if (readcount=1) wait(wsem); /第一个读进程需要判断是第一个读进程需要判断是否有写进程在进行写操作，有的话需要等待，没有的话不让写进程进行否有写进程在进行写操作，有的话需要等待，没有的话不让写进程进行新写操作新写操作 signal(x); /结束对结束对readcount的互斥访问的互斥访问 signal(rsem); /归还锁，让写进程可以进临界区归还锁，让写进程可以进临界区 signal(z); Void reader () $第二章第二章 进程管理进程管理 doReading(); wait

56、(x); /开始对开始对readcount的互斥访问的互斥访问 readcount-; /更新读进程数量更新读进程数量 if (readcount=0) signal(wsem); /最后一个离开临界区的读进程需最后一个离开临界区的读进程需要归还锁，让写进程可以进行写操作要归还锁，让写进程可以进行写操作 signal(x); /结束对结束对readcount的互斥访问的互斥访问 $第二章第二章 进程管理进程管理void writer() while(1) wait(y); /开始对开始对writecount的互斥访问的互斥访问 writecount+; /更新写进程数量更新写进程数量 if (

57、writecount=1) wait(rsem); /第一个写进程需要判断是否有读进第一个写进程需要判断是否有读进程在临界区，有的话需要等待，没有的话不让新的读进程进来程在临界区，有的话需要等待，没有的话不让新的读进程进来 signal(y); /结束对结束对writecount的互斥访问的互斥访问 wait(wsem); /限制同一时刻只能有一个写进程进行写操作限制同一时刻只能有一个写进程进行写操作 doWriting(); $第二章第二章 进程管理进程管理 signal(wsem); /结束对写操作的限制结束对写操作的限制 wait(y); /开始对开始对writecount的互斥访问的互

58、斥访问 writecount-; /更新写进程数量更新写进程数量 if (writecount=0) signal(rsem); /最后一个离开临界区的写进程需要归最后一个离开临界区的写进程需要归还锁，让读进程可以进临界区还锁，让读进程可以进临界区 signal(y); /结束对结束对writecount的互斥访问的互斥访问 $第二章第二章 进程管理进程管理2.6 进程通信进程通信Process Communication$第二章第二章 进程管理进程管理The type of process communication$第二章第二章 进程管理进程管理(Shared-Memory System)

59、$第二章第二章 进程管理进程管理 .发送原语发送原语 .接收原语接收原语（Message Passing System)$第二章第二章 进程管理进程管理$第二章第二章 进程管理进程管理$第二章第二章 进程管理进程管理1间接通信：间接通信： 建立一个通信参与者共享的逻辑实体建立一个通信参与者共享的逻辑实体信箱信箱，发送发送者向信箱发送消息；接收者到信箱取消息。者向信箱发送消息；接收者到信箱取消息。用于联系不十分紧密的用于联系不十分紧密的进程之间。进程之间。 间接通信方式间接通信方式（Indirect Communication way）优点：优点：信箱可实现信箱可实现“实时实时”或或“非实时非实

60、时”通信。在读通信。在读/写时间上具有随机写时间上具有随机性。性。 共享的逻辑实体可以是操作系统在核心空间提供的一组数据结构，也共享的逻辑实体可以是操作系统在核心空间提供的一组数据结构，也可以磁盘上的文件为基础，其特点是不只属于通信中的任意一方，而是一可以磁盘上的文件为基础，其特点是不只属于通信中的任意一方，而是一个中间实体。个中间实体。ABCDESendReceive$第二章第二章 进程管理进程管理2信箱：信箱：包含有多个消息的队列。系统为信箱通信提供若干包含有多个消息的队列。系统为信箱通信提供若干条原语，实现对信箱的管理。条原语，实现对信箱的管理。1）信箱的创建和撤消）信箱的创建和撤消 进