李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 5 讲 进程管理(3) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/

Presentation on theme: "李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 第 5 讲 进程管理(3) 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 1/"— Presentation transcript:

1 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com
第 5 讲 进程管理(3) 李元金 计算机与信息工程学院 1/

2 经典进程同步问题 教学目标 掌握利用信号量机制解决经典的进程同步问题的方法； 教学内容 掌握P、V操作的实现。 共享缓冲区进程同步问题
掌握共享缓冲区进程同步问题的方法； 教学内容 共享缓冲区进程同步问题 经典进程的同步问题 计算机科学与技术系 信息与教育技术中心 2/

3 复习 进程同步的任务是什么？ 同步机制应遵循的规则是什么？ 信号量机制的种类有哪些？ 什么是管程？作用是什么？ 3/

4 经典进程同步问题 生产者－－消费者问题 哲学家进餐问题 读者－－写者问题 4/

5 生产者一消费者问题 Dijkstra把同步问题抽象成一种生产者和消费者关系，计算机系统中的许多问题都可以被归结为生产者和消费者关系，例如，生产者可以是计算进程，消费者是打印进程，输入时输入进程是生产者，计算进程是消费者。我们可以通过一个缓冲区把生产者和消费者联系起来。 5/

6 生产者一消费者问题 上述生产者--消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：
消费者想接收数据时，有界缓冲区中至少有一个单元是满的； 生产者想发送数据时，有界缓冲区中至少有一个单元是空的。 6/

7 生产者一消费者问题 由于有界缓冲区是临界资源，因此，各生产者进程和消费者进程之间必须互斥执行。
由以上分析我们设公用信号量mutex保证生产者进程和消费者进程之间的互斥，设信号量empty表示有界缓冲区中的空单元数，初值为n；信号量full表示有界缓冲区中的非空单元数，初值为0。信号量mutex表示有界缓冲区中的个数，初值为1。 7/

8 利用记录型信号量解决生产者一消费者问题 mutex：使诸进程互斥地访问缓冲区（n个缓冲区） empty、 full：空、满缓冲区数量。
Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,1,…,n-1] of item; in, out: integer: =0,0; begin parbegin producer: begin repeat … Produce an item in nextp; 8/

9 consumer:begin repeat wait(full); wait(empty); wait(mutex);
nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); Consumer the item in nextc; Until false; end parend wait(empty); wait(mutex); buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full); Until false; end 9/

10 思考 wait(empty)与wait(mutex) wait(full)与wait(mutex)是否可以互换？
在每个程序中的多个wait操作顺序不能颠倒，应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。 wait 与signal对信号量的操作应该成对出现。 10/

11 利用AND信号量解决生产者——消费者问题
var mutex, empty, full: semaphore:=1,n,0; buffer:array[0,…,n-1] of item; in out: integer :=0,0; begin parbegin 11/

12 利用AND信号量解决生产者——消费者问题
Consumer: begin repeat Swait(full, mutex); nextc:=buffer(out); out:=(out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end Parend producer: begin repeat produce an item in nextp; … Swait(empty, mutex); buffer(in):=nextp; in:=(in+1) mod n; Ssingal(mutex, full); until false; end 12/

13 哲学家进餐问题 有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐，进餐完毕，放下筷子继续思考。 13/

14 利用记录型信号量解决哲学家进餐问题 Var chopstick: array[0, …, 4] of semaphore:=(1,1,1,1,1); repeat swait(chopstick[i]); wait(chopstick[(i+1)mod 5] ）; eat; signal(chopstick[i]) ; signal(chopstick[(i+1)mod 5] ）; think; Until false 14/

15 利用记录型信号量解决哲学家进餐问题 上述解决哲学家进餐问题的方法，可以保证不会有两个相邻的哲学家同时进餐，但是可能引起死锁。 解决方法
至多允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。 仅当哲学家的左右两只筷子均可用时，才允许他拿起筷子进餐。 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。 15/

16 利用AND信号量解决哲学家进餐问题 Var chopstick: array[0, …, 4] of semaphore:=(1,1,1,1,1); processi repeat think; Sswait(chopstick[(i+1)mod 5],chopstick[i]); eat Ssignal(chopstick[(i+1)mod 5],chopstick[i]); Until false 16/

17 读者—写者问题 一个数据文件或记录，可被多个进程共享，把只要求读该文件的进程成为“Reader进程”，其他进程则称为“Write进程”。
17/

18 利用记录型信号量解决读者——写者问题 var rmutex, wmutex: semaphore: =1,1;
readcount:integer: =0; begin parbegin reader: begin repeat wait(rmutex); if readcount=0 then wait(wmutex); readcount:=readcount+1; signal(rmutex); … perform read operation 18/

19 利用记录型信号量解决读者——写者问题 … wait(rmutex); readcount:=readcount-1;
if readcount=0 then signal(wmutex); signal(rmutex); until false; end 19/

20 利用记录型信号量解决读者——写者问题 writer: begin repeat wait(wmutex);
perform write operation; signal(wmutex); until false; end parend 20/

21 信号量集解决读者——写者问题 var RN integer; L, mx: semaphore: =RN, 1; begin
parbegin reader: begin repeat Swait(L,1,1); Swait(mx,1,0); … perform read operation; … Ssignal(L,1); until false; end 21/

22 信号量集解决读者——写者问题 writer: begin repeat Swait(mx,1,1; L,RN,0);
perform write operation; Ssignal(mx, 1); until flase; end parend 22/

23 信号量 一般说来，信号量的值与相应资源的使用情况有关。 信号量的值仅由P、V操作改变 P、V操作都是原语 P：申请一个单位资源
23/

24 P操作 P(s): 若S<0，入等待队列 若S>=0，继续 取s值减1 24/

25 V操作 V(s): 若S<=0，唤醒一等待队列进程 若S>0，继续 取s值加1 25/

26 信号量及P、V操作讨论 对于两个并发进程，互斥信号量的值仅取1、0和-1三个值 若ＭＵＴＥＸ＝1表示没有进程进入临界区
若ＭＵＴＥＸ＝0表示有一个进程进入临界区 若ＭＵＴＥＸ＝-1表示一个进程进入临界区，另一个进程等待进入。 26/

27 信号量及P、V操作讨论 信号量的物理含义： 信号量的初值应该大于等于0 S>0表示有S个资源可用 S=0表示无资源可用
P(S)：表示申请一个资源 V(S)：表示释放一个资源。 信号量的初值应该大于等于0 27/

28 信号量及P、V操作讨论 P、V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程
当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 两个V操作无关紧要 28/

29 信号量及P、V操作讨论 P、V操作的优缺点 优点： 缺点： 简单，而且表达能力强（用P、V操作可解决任何同步互斥问题）
遇到复杂同步互斥问题时实现复杂 29/

30 共享缓冲区的进程的同步 设某计算进程ＣＰ和打印进程ＩＯＰ共用一个单缓冲区，ＣＰ进程负责不断地计算数据并送入缓冲区Ｔ中，ＩＯＰ进程负责不断地从缓冲区Ｔ中取出数据去打印。 30/

31 共享缓冲区的进程的同步 通过分析可知，ＣＰ、ＩＯＰ必须遵守以下同步规则：
当ＣＰ进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印； 当IOP进程把缓冲区中的数据取出打印后，ＣＰ进程才能把下一个计算结果送入缓冲区。 31/

32 共享缓冲区的进程的同步 用P、V操作解决下图之同步问题 put copy get 提示：分别考虑对缓冲区S和T的同步，再合并考虑 S T
32/

33 共享缓冲区的进程的同步 设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0； while（1） P(Tout）;
copy： while（1） { P(Sout）; P(Tin）; 将数从S取出放入T; V(Tout); V(Sin); } get： while（1） { P(Tout）; 将数从T取走; V(Tin); } put： while（1） { P(Sin）; 将数放入S; V(Sout); } 33/

34 进程同步与互斥关系 进程同步与互斥都反映了在异步环境下并发进程间的相互制约关系。可归于同步范畴，但互斥是同步问题的一个特例，互斥解决临界区的使用，同步是并发进程在一些关键点上需互相等待互发消息。 34/

35 思考题 桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。
试用P、V操作实现爸爸、儿子、女儿三个并发进程的同步。 提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果 35/

36 S=1;So=0;Sa=0;(已经蕴含了儿子和女儿间的互斥关系)
Father() { while(1) { p(S); 将水果放入盘中; if(是桔子)v(So); else v(Sa); } Son() { while(1) { p(So) 取桔子 v(S); 吃桔子; Daughter() { p(Sa) 取苹果 吃苹果;

37 小结 利用信号量机制解决经典进程的同步问题。 P、V操作 37/

38 作业 P 38/