第2章进程的描述与控制(part5)

1、第二章 进 程 管 理 Heb Nomal University Department of Computer Science1第二章第二章 进程的描述与控制进程的描述与控制 2.1 2.1 前驱图和程序执行前驱图和程序执行 2.2 2.2 进程进程 的描述的描述2.3 2.3 进程控制进程控制 2.4 2.4 进程同步进程同步 2.5 2.5 经典进程的同步问题经典进程的同步问题 2.6 2.6 进程通信进程通信 2.7 2.7 线程的基本概念线程的基本概念 2.8 2.8 线程的实现线程的实现 第二章 进 程 管 理 Heb Nomal University Department of C

2、omputer Science2 关 于 进程同步 P.V操作必须成对出现 当为互斥互斥操作时，它们同处于同一进程 当为同步同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。第二章 进 程 管 理 Heb Nomal University Department of Computer Science3掌握信号量的物理意义掌握信号量的物理意义（1 1）一般考查对记录型信号量的理解。）一般考查对记录型信号量的理解。 信号量的物理含义：信号量的物理含义：S-value0S-value0表示有表示有S-valueS-value个资源可用；个资源可用；

3、S-value=0S-value=0表示无资源可用；表示无资源可用；S-valuevaluevalue|S-value|表示等待队列中的进程个数。表示等待队列中的进程个数。说明：根据以上信号量的物理意义，可以计算信号量的变说明：根据以上信号量的物理意义，可以计算信号量的变化范围。化范围。（2 2）S-valueS-value的初值的初值 表示系统中某类资源的数目，称为资源信号量。表示系统中某类资源的数目，称为资源信号量。若若S-valueS-value的初值为的初值为1 1，表示只允许一个进程访问，此时信，表示只允许一个进程访问，此时信号量转化为互斥信号量。号量转化为互斥信号量。（3 3）对信

4、号量只能执行）对信号量只能执行waitwait、signalsignal操作操作wait(S)wait(S)表示申请一个资源表示申请一个资源 ；signal(S)signal(S)表示释放一个资源。表示释放一个资源。注意：整型信号量不会取负值，可由此判断题目中的信号注意：整型信号量不会取负值，可由此判断题目中的信号量是整型信号量还是记录型信号量。量是整型信号量还是记录型信号量。第二章 进 程 管 理 Heb Nomal University Department of Computer Science4semaphore empty=1, full=0;item buffer;void pro

5、ducer() do wait(empty); putdata; signal(full); while(1); void consumer() do wait(full); getdata; signal(empty); while(1); void main()cobegin producer();consumer();coend说明：对资源信号量说明：对资源信号量emptyempty和和fullfull的的waitwait和和signalsignal操作，操作，同样需要成对地出现，但处于不同的程序中。同样需要成对地出现，但处于不同的程序中。1. 利用记录型信号量解决生产者利用记录型信号量

6、解决生产者消费者问题消费者问题 设置设置2个信号量个信号量full和和empty。 Full:表示表示buffer中有数据的缓冲区个数，初值为中有数据的缓冲区个数，初值为0； Empty:表示表示buffer中空缓冲区的个数，初值为中空缓冲区的个数，初值为1; 取值范围都是取值范围都是-1，1。 buffer生产者消费者第二章 进 程 管 理 Heb Nomal University Department of Computer Science5l复杂情况（既有同步，又有互斥）：复杂情况（既有同步，又有互斥）：一个一个buffer，n个生产者，个生产者，m个消费者个消费者，生产者不断地生产，消

7、费者不生产者不断地生产，消费者不断地消费。只有断地消费。只有buffer为空时生产者才能进行为空时生产者才能进行putdata操作，只有操作，只有buffer有数据有数据时消费者才能进行时消费者才能进行getdata操作。操作。buffer变成了临界资源，不允许多个进程同时操作buffer。即不允许多个生产者同时进行putdata操作，也不允许多个消费者同时进行getdata操作。与简单情况相比，需要增加一个信号量mutex来实现对buffer的互斥访问，其初始值为1。 信号量full和empty的变化范围与简单情况有所不同。full初值仍然为0，变化范围：-m-m，11，n是消费者进程总数量

8、；empty初值仍然为1，变化范围：1-n1-n，11，m是生产者进程总数量。 buffer生产者消费者第二章 进 程 管 理 Heb Nomal University Department of Computer Science6semaphore empty=1, full=0,mutex=1;item buffer;void producer() do wait(empty); putdata; signal(full); while(1); void consumer() do wait(full); getdata; signal(empty); while(1); void mai

9、n()cobegin producer();consumer();coendwait(mutex);signal(mutex);wait(mutex);signal(mutex);说明：说明：（1）在生产者进程和消费者进程中，）在生产者进程和消费者进程中，V操作的次序无关紧要，但操作的次序无关紧要，但两个两个P操作操作的次序却不能颠倒，否则可能导致死锁，的次序却不能颠倒，否则可能导致死锁，即，应即，应先执行对资源信号量的先执行对资源信号量的wait操操作，再执行对互斥信号量的作，再执行对互斥信号量的wait操作操作。（2）由于）由于buffer只有一个，只有一个，full和和empty就可以保

10、证对就可以保证对buffer的互斥操作，故的互斥操作，故mutex也可以省略，但如果也可以省略，但如果buffer有多个，则有多个，则mutex不能省略。不能省略。第二章 进 程 管 理 Heb Nomal University Department of Computer Science7l一般意义的一般意义的“生产者生产者消费者消费者”问题：问题：N个个buffer，多个生产者，多个消费者多个生产者，多个消费者，循环存取，循环存取buffer。 l(教材上的教材上的)buffer生产者消费者bufferbufferbufferbuffer第二章 进 程 管 理 Heb Nomal Univ

11、ersity Department of Computer Science81. 利用记录型信号量解决生产者消费者问题 假定：在P-C之间的公用缓冲池中，具有n个缓冲区；利用互斥信号量mutex实现各进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。full是“满”缓冲区数目，初值为0，empty是“空”缓冲区数目，初值为N。实际上，full和empty是同一个含义：full + empty = N初值为1第二章 进 程 管 理

12、 Heb Nomal University Department of Computer Science9P(full);P(mutex); one unit buffer;V(mutex);V(full);Producer每个进程中各个每个进程中各个P操作的次序很重要：操作的次序很重要： 先检查资源数目，再检查是否互斥先检查资源数目，再检查是否互斥否则可能否则可能死锁死锁第二章 进 程 管 理 Heb Nomal University Department of Computer Science10semaphore mutex=1, empty=n, full=0; /互斥信号量初值为1；

13、/资源信号量empty表示空缓冲区个数，初值为n/full表示满缓冲区个数，初值为0 item buffern; int in=0, out=0; void proceducer( ) do producer an item nextp; wait(empty); wait(mutex); bufferin = nextp; in = (in+1) % n; signal(mutex); signal(full); while(True); void consumer( ) do wait(full); wait(mutex); nextc = bufferout; out = (out+1)

14、 % n; signal(mutex); signal(empty); consumer the item in nextc; while(true);void main( ) cobegin proceducer(); consumer( ); coend第二章 进 程 管 理 Heb Nomal University Department of Computer Science11l在 每 个 程 序 中 用 于在 每 个 程 序 中 用 于 实 现 互 斥 的实 现 互 斥 的 w a i t ( m u t e x ) 和和signal(mutex)必须成对必须成对地出现；地出现； l

15、对对资源信号量资源信号量empty和和full的的wait和和signal操作，同样需操作，同样需要成对地出现要成对地出现，但它们分别处于不同的程序中。但它们分别处于不同的程序中。 例如，例如，wait(empty)在计算进程中，而在计算进程中，而signal(empty)则在打印进程中，则在打印进程中，计算进程若因执行计算进程若因执行wait(empty)而阻塞，而阻塞， 则以后将由打印进程将它唤醒；则以后将由打印进程将它唤醒；l在每个程序中的在每个程序中的多个多个wait操作顺序不能颠倒。应先执行操作顺序不能颠倒。应先执行对资源信号量的对资源信号量的wait操作，然后再执行对互斥信号量的操

16、作，然后再执行对互斥信号量的wait操作，操作，否则可能引起进程死锁否则可能引起进程死锁。 在生产者消费者问题中应注意：Why?第二章 进 程 管 理 Heb Nomal University Department of Computer Science12 生产者消费者问题生产者消费者问题 哲学家就餐问题 读者写者问题 理发师问题第二章 进 程 管 理 Heb Nomal University Department of Computer Science132.5.2 哲学家进餐问题哲学家进餐问题 哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之

17、间放一只筷子。 每个哲学家的行为是思考，感到饥饿，然后吃通心粉。 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子 1. 利用记录型信号量解决哲学家进餐问题利用记录型信号量解决哲学家进餐问题 经分析可知，放在桌子上的经分析可知，放在桌子上的筷子是临界资源筷子是临界资源，在一段，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用，可以为每一只筷子设置一个信号量（取筷子执行为每一只筷子设置一个信号量（取筷子执行P操作，操作，放下筷子执行放下筷子执行V操作），由这五个信号量构成信号量数组。操作），

18、由这五个信号量构成信号量数组。其描述如下：其描述如下： semaphore chopstick5= 1,1,1,1,1; 所有信号量均被初始化为所有信号量均被初始化为1 第二章 进 程 管 理 Heb Nomal University Department of Computer Science14第第i位哲学家的活动可描述为：位哲学家的活动可描述为： do wait(chopsticki); /取左边筷子取左边筷子 wait(chopstick(i+1) % 5); /取右边筷子取右边筷子 eat; signal(chopsticki); /放下左边筷子放下左边筷子 signal(chops

19、tick(i+1) % 5); /放下右边筷子放下右边筷子 think; while(True); 可能出现死锁可能出现死锁第二章 进 程 管 理 Heb Nomal University Department of Computer Science15 可采取以下几种解决方法：可采取以下几种解决方法： (1) 至多只允许有四位至多只允许有四位哲学家同时去拿左边的筷子，哲学家同时去拿左边的筷子，最最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。两只筷子，从而使更多的哲学家能够进餐。

20、(2) 仅当哲学家的左、右两只筷子均可用时，才允许仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。他拿起筷子进餐。 (3) 规定规定奇数号哲学家先拿他左边的筷子，然后再去奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反拿右边的筷子；而偶数号哲学家则相反。按此规定，将是按此规定，将是1、 2号哲学家竞争号哲学家竞争1号筷子；号筷子；3、4号哲学家竞争号哲学家竞争3号筷子。即五位哲学家号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。位哲学家能获

21、得两只筷子而进餐。 第二章 进 程 管 理 Heb Nomal University Department of Computer Science16semaphore chopstick5=1，1，1，1，1;semaphore count=4;void philosopher_i( )while(true)think();wait(count); /请求进入房间进餐请求进入房间进餐wait(chopsticki); /请求左手边的筷子请求左手边的筷子wait(chopstick(i+1)%5); /请求右手边的筷子请求右手边的筷子eat();signal(chopstick(i+1)%5)

22、; /释放右手边的筷子释放右手边的筷子signal(chopsticki); /释放左手边的筷子释放左手边的筷子signal(count); /退出房间释放信号量退出房间释放信号量room 解法一：解法一：第二章 进 程 管 理 Heb Nomal University Department of Computer Science17解法二：解法二：semaphore chopstick5=1，1，1，1，1;integer i=0,1,4;void philosopher_i( ) while(true) if(i%2=0)then P(chopsticki); P(chopstick(i+

23、1)%5);eating; V(chopsticki); V(chopstick(i+1)%5);else P(chopstick(i+1)%5); P(chopsticki);eating; V(chopstick(i+1)%5); V(chopsticki);第二章 进 程 管 理 Heb Nomal University Department of Computer Science18AND型信号量 在两个进程中都要包含两个对在两个进程中都要包含两个对Dmutex和和Emutex的操作，的操作， 即即process A: process B:wait(Dmutex); wait(Emut

24、ex);wait(Emutex); wait(Dmutex);若进程若进程A和和B按下述次序交替执行按下述次序交替执行wait操作：操作：process A: wait(Dmutex); 于是于是Dmutex=0process B: wait(Emutex); 于是于是Emutex=0process A: wait(Emutex); 于是于是Emutex=-1 A阻塞阻塞process B: wait(Dmutex); 于是于是Dmutex=-1 B阻塞阻塞 2. 利用利用AND信号量机制解决哲学家进餐问题信号量机制解决哲学家进餐问题(回到回到2.4.3) 第二章 进 程 管 理 Heb No

25、mal University Department of Computer Science19 AND同步机制的基本思想是：同步机制的基本思想是：将进程在整个运行过程将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。用完后再一起释放。只要尚有一个资源未能分配给进程，只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取若干个临界资源的分配，采取原子操作方式：要么全部分原子操作方式：要么全部分配到进程，要么

26、一个也不分配配到进程，要么一个也不分配。 由死锁理论可知，这样就可避免上述死锁情况的发生。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在为此，在wait操作中，增加了一个操作中，增加了一个“AND”条件，故称为条件，故称为AND同步，或称为同时同步，或称为同时wait操作，操作， 即即Swait(Simultaneous wait)定义如下：定义如下： 第二章 进 程 管 理 Heb Nomal University Department of Computer Science20Swait(S1, S2, , Sn) while(1) if( S1 =1 & & S

27、n =1) for(i=1;i=n ; i+) Si -; break; else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation Ssignal(S1, S2, , Sn) for(i=1;i=n;i+) Si +; Remove all the process waiting in the queue associat

28、ed with Si into the ready queue. 第二章 进 程 管 理 Heb Nomal University Department of Computer Science21利用AND信号量机制解决哲学家进餐问题 在哲学家进餐问题中，在哲学家进餐问题中，要求每个哲学家先获得两个临界要求每个哲学家先获得两个临界资源资源(筷子筷子)后方能进餐，这在本质上就是前面所介绍的后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用同步问题，故用AND信号量机制可获得最简洁的解法。信号量机制可获得最简洁的解法。Semaphore chopsiick 5 =1,1,1,1,1; do

29、 think; Swait(chopstick(i+1) % 5, chopsticki); eat; Ssignal(chopstick (i+1) % 5, chopsticki); while(True); 第二章 进 程 管 理 Heb Nomal University Department of Computer Science22Semaphore mutex=1, empty=n, full=0; item buffer n ; int in=0, out= 0; void producer( ) do produce an item in nextp; Swait(empty,

30、 mutex); buffer(in) =nextp; in =(in+1) % n; Ssignal(mutex, full); while(True); void consumer( ) do Swait(full, mutex); nextc =buffer(out); out =(out+1) % n; Ssignal(mutex, empty); consumer the item in nextc; while(True); 利用AND信号量解决生产者消费者问题 第二章 进 程 管 理 Heb Nomal University Department of Computer Science23在一辆公共汽车上，司机和售