操作系统26课件

操作系统

第三章并发控制----互斥与同步

并发原理

互斥——软件解决方法

互斥——硬件解决方法

信号量

经典的进程同步问题

管程消息传递1、并发原理单处理机:插入执行

P1P2P3

procedureecho；varout,in:character；begininput(in,keyboard);out:=in;output(out,keyboard);end

input(in,keyboard);p1input(in,keyboard);p2out:=in;p1output(out,keyboard);p1out:=in;p2output(out,keyboard);p2单处理机多道程序多处理机多道程序处理机1处理机2input(in,keyboard);……input(in,keyboard);out:=in;….output(out,keyboard)out:=in;output(out,keyboard)

进程间的相互作用进程间的相互竞争进程间的相互合作互斥的要求进程间的相互作用觉察程度相互关系一进程对其它进程的影响潜在控制问题互不觉察间接觉察直接觉察竞争通过共享合作通过通信合作一进程独立于其它进程进程的执行时间将被影响一进程依赖于从其它进程得到的信息进程的执行时间将被影响互斥、死锁、饥饿互斥、死锁、饥饿、数据不一致死锁、饥饿进程间的相互竞争进程间的竞争面临3个控制问题：互斥死锁饥饿死锁当多个进程因竞争资源而造成的一种僵局,如无外力推动,这些进程永远无法向前推进饥饿系统并没有发生死锁，但某些进程得到资源的几率非常小，进程可能会长时间等待进程间的相互合作通过共享合作通过通信合作通过共享合作这些进程并不是通过名字察觉到对方，而是通过共享访问间接察觉。进程间通过共享方式进行合作。除互斥、死锁和饥饿外，保证数据的一致性也是一个潜在的控制问题。互斥的要求空闲让进忙则等待有限等待让权等待2、互斥——软件解决方法Dekker算法Peterson算法Dekker算法小屋协议：这个小屋本身和它的入口都非常小，以至于在给定的任何时刻，只有一个人可以呆在屋内，屋内有一块只能写一个号码的黑板协议内容：一个希望进入临界段的进程进入小屋并查看黑板，若黑板上写着自己的号码，就离开小屋并执行它的临界段，若黑板上写着他人的编号，就离开小屋并等待，然后不时地进屋查看黑板，直至允许进入自己的临界段。Dekker算法2.第2种途径这种解决方法依赖于进程执行的相对速度

共享的全局变量是：varflag:array[0..1]ofboolean;它被初始化为falsePROCESS0 PROCESS1……whileflag[1]do{nothing}; whileflag[0]do{nothing};flag[0]:=true;flag[1]:=true;〈criticalsection〉; 〈criticalsection〉;flag[0]:=false; flag[1]:=false;… …Dekker算法3.第3种途径这种方法保证了互斥但会导致死锁问题。

PROCESS0 PROCESS1……flag[0]:=true; flag[1]:=true;whileflag[1]do{nothing}; whileflag[0]do{nothing};〈criticalsection〉; 〈criticalsection〉;flag[0]:=false; flag[1]:=false;… …

Dekker算法4.第4种途径PROCESS0 PROCESS1… …flag[0]:=true; flag[1]:=true;whileflag[1]do{nothing}; whileflag[0]do{nothing};beginbeginflag[0]:=false; flag[1]:=false;〈delayforashorttime〉; 〈delayforashorttime〉;flag[0]:=true; flag[1]:=true;end;end;〈criticalsection〉; 〈criticalsection〉;flag[0]:=false； flag[1]:=false;… …Peterson算法

Dekker算法可以解决互斥问题，但是，其复杂的程序难于理解，其正确性难于证明。Peterson给出了一个简单的方法。下面是一个两进程互斥的简单解决方法，进一步可将Peterson算法推广到多个进程的情况。

varflag:array[0..1]ofboolean; flag[1]:=true;turn:0..1; turn:=0;procedureP0; whileflag[0]andturn=0do{nothing};begin 〈criticalsection〉;repeat flag[1]:=false;flag[0]:=true; 〈remainder〉turn:=1; foreverwhileflag[1]andturn=1do{nothing};end;〈criticalsection〉; beginflag[0]:=false; flag[0]:=false;〈remainder〉 flag[1]:=false;forever turn:=1;end; parbeginprocedureP1; P0;P1begin parendrepeatend.使用机器指令1.特殊的机器指令testandsetexchange

2.机器指令方法的特性优点：可用于含有任意数量进程的单处理机或共享主存的多处理机；比较简单，易于验证；可支持多个临界段，每个临界段用各自的变量加以定义。缺点：采用busy-waiting技术，进程等待进入临界段时耗费处理机时间；可能产生饥饿；可能产生死锁。4、信号量信号量概念信号量及同步原语信号量的应用

信号量的概念同步机构概念：是一个确切的二元组（S，L），S是一个非负初值的整形变量，L为初始状态为空的队列。（S表示资源实体，L表示等待该资源的队列。）对信号量的操作有两个：WAITSIGNAL

信号量及同步原语二元信号量：它允许取值仅为0，1，主要用于互斥。一般信号量：它允许取值为整数，主要用于进程间的同步。信号量的操作有两种：阻塞等待方式，忙等待方式。阻塞等待方式WAIT（S）或P（S）

判断S进程继续阻塞该进程将进程插入S的等待队列中L，重新调度SIGNAL（S）或V（S）S=S+1判断Sq继续唤醒队列L中的进程。S>0S<0S<=0

S=S-1一般信号量的同步原语S>=0忙等待方式一般信号量的同步原语二元信号量的同步原语WAIT（S）或P（S）WAITB（S）

S0SS-1N

S=0

SS-1NSIGNAL（S）或V（S）SIGNALB（S）SS+1SS+1YY忙等待方式和阻塞方式的差别在于不会出现负值。阻塞等待方式适用于单处理机方式。忙等待方式适用于多处理机方式。同步原语的不可分割性信号量上的同步原语应该是原子的操作保证进程间互斥地使用同步原语整体操作、不可分割、也就是不可打断其执行或者说不可中断同步原语使用不当会造成死锁A进程 B进程WAIT(S1) WAIT(S2)WAIT(S2) WAIT(S1)SIGNAL(S2) SIGNAL(S1)SIGNAL(S1) SIGNAL(S2)

信号量应用用信号量实现进程间的互斥用信号量实现进程间的同步描述前趋问题用信号量实现进程间的互斥假如进程A的程序段CSA和进程B的程序段CSB共用某个变量（即CSA和CSB对应进程A和进程B是临界段）用WAIT和SIGNAL操作实现进程的互斥。设MUTEX为互斥信号量：令MUTEX=1进程A：进程B：WAIT（MUTEX）WAIT（MUTEX）CSACSBSIGNAL（MUTEX）SIGNAL（MUTEX）用信号量实现进程间的同步进程P1、P2共享单缓冲区P1：写数据 P2：读数据同步关系：P1-P2-P1-P2用信号量实现进程间的同步

信号量：S1=0、S2=1P1：P2:

WAIT(S2)送数据SIGNAL(S1)WAIT(S1)取数据SIGNAL(S2)

描述前趋问题

PbPcPaSF图aPaPbPcSF图bPA:

signal(Sab)signal(Sac)PB:wait(Sab)PC:wait(Sac)Sab=Sac=0图aPA:signal(Sac)PB:signal(Sbc)PC:wait(Sac)wait(Sbc)

Sac=Sbc=0图b有A，B两进程共享一临界资源，下面是二进程的进程同步原语，试问有否错？如有错，错在哪里？设SA=SB=0进程A：使用临界资源进程B:wait(SB)signal(SB)使用临界资源wait(SA)signal(SA)

若进程A和B在临界段上互斥，那么当A位于临界段内时，不能打断它的操作信号量是一个初值为非负的整型变量，可在其上做加1和减1操作信号量是一个整型变量，在其上只能进行WAIT和SIGNAL操作经典的进程同步问题1、生产者和消费者问题2、阅读者和写入者问题3、哲学家就餐问题4、嗜睡的理发师生产者和消费者问题通过一个有界缓冲区把一群生产者P1，P2…Pm和消费者C1,C2…Ck联系起来。P1C1P2C2PmCkn个缓冲区生产者和消费者的同步：禁止生产者向满的缓冲区送产品禁止消费者向空的缓冲区取产品信号量的设置应具备如下功能：跟踪资源的生产和消费计数器协调资源的生产者和消费者间同步设置三个信号量：EMPTY-BUF说明空缓冲区的数目{初值=N}FULL-BUF说明满缓冲区的数目{初值=0}MUTEX互斥信号量{初值=1}

生产一个产品WAIT（FULL-BUF）WAIT（EMPTY-BUF）WAIT(MUTEX)WAIT(MUTEX)从缓冲区取产品

送入缓冲区SIGNAL(MUTEX)SIGNAL(MUTEX)SIGNAL(EMPTY-BUF)SIGNAL(FULL-BUF)消费产品设置四个信号量：EMPTY-BUF说明空缓冲区的数目{初值=N}FULL-BUF说明满缓冲区的数目{初值=0}MUTEX1互斥信号量{初值=1}MUTEX2互斥信号量{初值=1}

生产一个产品WAIT（FULL-BUF）WAIT（EMPTY-BUF）WAIT(MUTEX2)WAIT(MUTEX1)从缓冲区取产品送入缓冲区SIGNAL(MUTEX2)SIGNAL(MUTEX1)SIGNAL(EMPTY-BUF)SIGNAL(FULL-BUF)消费产品问题：为什么要设置互斥信号量两个WAIT和两个SIGNAL操作可否交换？阅读者和写入者问题概念：保证一个写者必须与其它进程互斥地访问共享对象的进程同步问题。第一类读者-写者问题：读者无须等待，除非某个写者访问共享对象。第二类读者-写者问题：一旦某个写者进程就绪，则尽可能执行它的写操作。第一类读者-写者问题信号量设置：读互斥信号量：RMUTEX{=1}用于读者互斥地访问共享变量READCOUNT。写互斥信号量：WMUTEX{=1}用于写者和其它进程互斥地访问数据对象。READCOUNT普通整形变量。{=0}

WAIT（RMUTEX）READCOUNT：=READCOUNT+1IFREADCOUNT=1THENWAIT（WMUTEX）SIGNAL（RMUTEX）访问共享变量WAIT（RMUTEX）READCOUNT：=READCOUNT-1IFREADCOUNT=0THENSIGNAL（WMUTEX）SIGNAL（RMUTEX）

读者进程写者进程

WAIT（WMUTEX）对共享信息修改SIGNAL（WMUTEX）

当读者正在访问，写者在哪个信号量上被阻塞当写者在访问，其它的写者又是在哪个信号量上被阻塞当写者在访问，第一个读者在哪个信号量被阻塞，后续读者又是如何被阻塞哲学家就餐问题有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，周围放有五张椅子，每人坐一张，在圆桌上有五个碗和五只筷子。当哲学家思考时，他不与同事交谈。饥饿时，便试图取用左，右最靠近他的筷子，他可能一支拿不到，只有在他拿到两支筷子时，方能就餐，餐毕，又继续思考。信号量设置为每支筷子设置信号量：VARChopstrick:array[0..4]ofsemaphore信号量的初值均为1。第i个哲学家的活动

WAIT(Chopstrick[i])WAIT(Chopstrick[(i+1)mod5])

吃SIGNAL(Chopstrick[i])SIGNAL(Chopstrick[(i+1)mod5])

思考嗜睡的理发师理发店由一个等候室（其中有N把椅子）和一个理发室（其中有一把理发椅子）组成，如果没有顾客理发，理发师就在理发椅子上睡觉，如果一个顾客走进理发店但等候室中所有椅子已坐满，该顾客就离开理发店，如果理发师忙于理发，那么该顾客就坐在一个空椅子上等候，若理发师在睡觉，顾客就唤醒他，用信号量解决其同步问题。Varbarber,wait:semaphore;{=0}entry:semaphore;{=1}count:integer;{=0}理发师repeatwait(barber)“shave”wait(wait);untilfalseend顾客wait(entry);elsesignal(entry);ifcount=nthenexit;signal(barber);count:=count+1“shave”;ifcount>1thenwait(entry);begincount:=count-1;signal(entry);ifcount>0thensignal(wait);signal(entry)作业1：有父母子女四人围坐一起吃水果，父亲不断削苹果往盆中放，母亲不断削梨往盆中放，女儿则从盆中取苹果吃，儿子则从盆中取梨吃，假如盆中最多只能放N只水果，试用P、V操作协调他们的关系。解设S=N，S1=0，S2=0父：母：女：儿：

削苹果削梨wait(s1)wait(s2)wait(s)wait(s)拿苹果拿梨放苹果放梨signal(s)signal(s)signal(s1)signal(s2)吃苹果吃梨

作业2：有一仓库可以存放A，B两种物品，每次只能存入一物品（A或B）存储空间无限大，只是要求-n<A的件数-B的件数<m,其中n,m是正整数，试用存入A，存入B，和P，V操作描述物品A和物品B的入库过程。5、管程管程的定义用管程实现同步管程的定义管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并且提供了一个方便的阻塞和唤醒进程的机构。管程的基本特性：局部于管程的数据只能被局部于管程内的过程所访问一个进程只有通过调用管程内的过程才能进入管程访问共享数据每次只允许一个进程在管程内执行某个内部过程用管程实现同步管程的组成部分：局部数据条件变量初始化程序过程1，过程2···过程N（局部于该管程对数据结构进行规定的操作的若干过程）CWAIT(C)CSIGNAL(C)Cwait(C):等待操作，调用进程在条件C上挂起。Csignal(C):恢复某个由于该条件变量C上执行Cwait操作而被挂起阻塞的进程，从中选择一个挂起进程予以恢复。用管程实现生产者消费者局部数据：缓冲区条件变量：notfull(没满）,notempty（没空）对局部数据的操作：向缓冲区送物品从缓冲区取物品

programproducerconsumermonitorboundedbuffer;buffer:array[0..N]ofchar;nextin,nextout,count:integer;notfull,notempty:condition;procedureappend(x:char);beginifcount=Nthencwait(notfull);buffer[nextin]:=x;nextin:=nextin+1modN;count:=count+1;csignal(notempty);end;

proceduretake(x:char);beginifcount=0thencwait(notempty);x:=buffer[nextout];nextout:=nextout+1modN;count:=count-1;csignal(notfull);end;beginnextin:=0;nextout:=0;count:=0;end;6、进程的通信高级通信机构：消息缓冲通信管道通信信箱通信

系统管理若干消息缓冲器，用于存放消息。每当一个进程（发送进程）向另一个进程（接收进程）发送消息时，便申请一个消息缓冲，并把已准备好的消息送到缓冲区，然后把该消息缓冲器插入到接收进程的消息队列中，通知接收进程。接收进程收到发送进程发来的通知，从本进程的消队列中摘下该消息缓冲区，取出信息，把消息缓冲区还给系统。消息缓冲通信

消息传递原语原语：·send(destination,message)·receive(source,message)用消息传递实现同步

无论是发送方还是接收方都可能被阻塞。下面有三种最一般的组合，任何特定系统都实现了其中的一种或两种：阻塞发送，阻塞接收。无阻塞发送，阻塞接收。无阻塞发送，无阻塞接收。寻址方式1.直接寻址对直接寻址方式，send原语中明确标明了目的进程。receive原语有两种方式：第一种方式接收进程预先知道发送消息的源进程，另一种方式则不可能预先知道源进程。

2.间接寻址

消息不直接由发送方传给接收方，而是通过一个共享的数据结构----信箱进程1进程n消息….消息接受进程端口

消息格式支持变长消息的操作系统中的消息格式

排队规则

最简单的排队规则是先进先出，但这远远不够。一个改进的方法是由发送方或接收方基于消息的类型标明消息的优先权；另一个改进方法是允许接收方检查消息队列并选择要接收的消息。用消息传递实现互斥

假设使用阻塞receive原语和无阻塞send原语，并发进程集共享一个邮箱mutex，将邮箱初始化为仅包含一个空消息，欲进入临界段的进程首先要接收相应的消息，如果邮箱为空则该进程被阻塞，一旦进程得到消息它就执行其临界段，然后再将消息放回邮箱，这样消息就如同令牌一样在进程之间传递。用消息传递实现互斥

这种解决方法是，假设有多于一个进程并发执行receive操作，则有：·如果仅有一个消息，那么它只可传递给一个进程，其他进程将被阻塞。·如果邮箱为空，则所有的进程将被阻塞。当消息可用时，仅有一个阻塞进程被激活并得到消息。

Receive(mutex,msg)临界段Send(mutex,msg)Zq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjUmYp!t&w)w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s