OS-04进程同步与互斥

操作系统原理金海溶blue1879@办公室：2A314操作系统设计中的核心问题是关于进程和线程的管理多道程序技术 管理单处理器系统中的多个进程多处理技术 管理多处理器系统中的多个进程分布处理技术 管理多台分布式计算机系统(集群)中多个进程的执行§4.1并发进程进程并发要解决的主要问题互斥：进程之间的间接制约关系。当一个进程使用某资源时，另一个进程必须等待——并发的基本需求实现互斥包括软件方法(“忙等待”技术)和支持互斥的硬件机制等同步：进程间的的直接制约关系，进程间的活动有相互依赖和合作的关系通信：不同进程之间传播或交换信息进程并发顺序执行的特性

顺序性，资源独占，可再现性

并发执行的特点：

不可再现性

制约性

资源共享

回顾顺序执行和并发执行的特点并发的例子及并发后的问题并发

在同一时间段内，多个进程同时运行；宏观上并发，微观上顺序执行。并发后产生了资源的竞争和共享问题，而且进程的执行速度及进程的执行序列都是不可预测的一个例子与时间有关的错误考虑下面一个字符回显的的过程voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}从键盘获得输入，每击一下键，输入字符就保存在变量chin中，然后处理后传送给变量chout，并回送显示器任何程序可以重复地调用此过程，接收用户输入，并在用户的屏幕上显示与时间有关的错误考虑一个支持单用户单处理器、多道程序设计系统将其当作一个共享过程，载入到所有应用程序公用的全局存储区中。这样每个应用程序都能使用这个过程，由于每个应用程序只需使用echo过程的一个副本，从而节省空间进程间共享主存是非常有用的，它允许进程间有效而紧密的交互，有利于进程的相互通信。但是，共享也可能会带来一些问题与时间有关的错误

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}考虑下面的顺序进程P1调用echo过程，并在getchar函数结束后立即被中断，此时，最近输入的字符x被保存在变量chin中进程P2被激活并调用echo过程，echo过程运行得出结果，输入然后在屏幕上显示单个的字符y进程P1被恢复。此时chin中值x被写覆盖，因此已丢失，而chin中的值y被传送给chout并显示出来第一个字符丢失，第2个字符被显示了两次与时间有关的错误

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

getchar（）chinchout

putchar（）P1P2getchar（）XXgetchar（）YYYputchar（）YYY？echo与时间有关的错误错误原因之1：进程执行交叉;错误原因之2：涉及公共变量(chin和chout)。解决方案：一次只允许一个进程调用echo过程：进程P1调用echo过程，并在getchar函数结束后立即被中断，此时，最近输入的字符x被保存在变量chin中进程P2被激活并调用echo过程。但是，由于P1仍然在echo过程中，尽管当前P1处于就绪状态，P2仍被阻塞，不能进入这个过程。因此，P2被阻塞，等待echo过程可用一段时间后进程P1被恢复，完成echo的执行，显示出正确的字符xP1退出echo后，解除了P2的阻塞，P2被恢复，成功地调用echo过程与时间有关的错误

voidecho()

{chin=getchar();

chout=do(chin);

putchar(chout);}

P1

voidecho()

{chin=getchar();chout=do(chin);

putchar(chout);}

调用echo超时，就绪P2调用echo资源正忙阻塞状态调度运行释放echo唤醒获取资源就绪状态调度运行由此可见，解决共享资源的保护，唯一的办法是互斥的使用共享资源（如变量，代码等）即：一次只允许一个进程访问共享资源临界资源和临界区：临界资源

某些在一段时间内只允许一个进程使用的共享资源称为临界资源临界区（段）访问临界资源的程序段称为临界区。即互斥执行的程序段进程同步与互斥进程P1和P2共享同一打印机资源，其操作流程如下：

p1:entrycode使用打印机exitcodep2:entrycode使用打印机exitcode系统打印机即为——临界资源P1和p2的访问临界资源打印机的代码即为——临界区进程同步与互斥进程互斥的实现Repeat

临界区

其余代码Untilfalseentrysectionexitsection例：司机-售票员问题司机活动：售票员活动：

do{do{

启动车辆关车门正常行驶售票到站停车开车门

}while(1)}while(1)同步的例子互斥：软件方法Peterson算法Dekker算法Lamport面包店算法Eisenberg/Mcguire算法进程同步与互斥互斥：硬件的支持中断禁用在单处理器机器中，并发进程不能重叠,只能交替。此外，一个进程将一直运行，直到它调用了一个操作系统服务或被中断。因此，为保证互斥，只需要保证一个进程不被中断就可以当一个计算机系统包括多个处理器时，在这种情况下，禁止中断不能保证互斥进程同步与互斥互斥：硬件的支持专门的机器指令在硬件级，对存储器单元的访问排斥到相同单元的其他访问。基于这一点，处理器的设计者提出了一些机器指令，用于保证两个动作的原子性，如在一个取指令周期中对一个存储器单元的读和写或者读和测试。由于这些动作在一个指令周期中执行，它们不会受到其他指令的干扰如：test-and-set指令，swap指令等进程同步与互斥信号量（Semaphore）管程(monitor)事件典型同步机制Lock和unlock关锁和开锁是加锁机制的2个基本操作。在其中设置一公共变量x代表某个临界资源的状态

X＝1表示资源可用

X＝0表示资源正在被使用进程使用临界资源必须做如下三个不可分割的操作

进程同步与互斥1)检查x的值。x=0，资源正在使用，返回继续进行检查；

x=1，资源可以使用，置x为0(关锁)2)进入临界区，访问临界资源3)释放资源,退出临界区，置x为1(开锁)通过分析，给出关锁和开锁操作的描述关锁lock[x] L:ifx=0thengotoLelsex:=0;开锁unlock[x] x:=1;Lock和unlock缺点：使用了忙等待，当一个进程在等待资源时，依然会消耗CPU时间可能会发生饥饿，有些进程由于长时间得不到资源。可能无法彻底实现互斥，有可能2个及以上的进程进入临界区。可能死锁。当低优先级进程获取资源的情况下，被高优先级进程抢占cpu，且高优先级进程申请同一资源，由于互斥机制，高优先级进程会进入永远的忙等待。Lock和unlock信号量（semaphore）：一个与资源有关的，初值为非负数的整型变量称为信号量。用S表示，初值和资源有关信号量是一种特殊的变量，只能由semWait，semSignal原语进行操作访问。信号量机制semWait原语（P原语）——semWait（S）/

P(S)S:=S-1；如果S>=0，则表示有资源，该进程继续执行；如果S<0，则表示已无资源，执行原语的进程被置成阻塞状态，并使其在S信号量的队列中等待，直至其他进程在S上执行semSignal操作释放它为止信号量机制semSignal原语（V原语）——semSignal（S）/V(S)S:=S+1如果S>0，则该进程继续执行如果S<＝0，说明有进程被挂起，则唤醒一阻塞进程，即从S信号量的等待队列首摘下一个PCB，将其置为就绪状态，执行semSignal(S)者继续执行semWait操作可能会引起进程的阻塞，semSignal操作不会引起本身进程状态的变化，但可能唤醒其他进程，使其从阻塞状态转变到就绪状态信号量机制semWait/semSignal原语都是低级通信原语，一个正在执行semWait/semSignal

操作的进程，不允许任何其他进程中断它的操作，这样就保证了同时只能有一个进程对信号量S施行semWait或semSignal实现互斥的例子与分析

打印机是一种临界资源，必须互斥使用，则：

semWait(S)使用打印机semSignal(S)信号量机制P1P2P3P4关于s信号量的阻塞队列

信号量S的初值为：2semWait(s)S=s-1=1semWait(s)S=s-1=0semWait(s)S=s-1=-1P3semWait(s)S=s-1=-2P4semSignal(s)S=s+1=-1唤醒就绪semSignal(s)S=s+1=0唤醒就绪semSignal(s)S=s+1=1semSignal(s)S=s+1=2用信号量实现同步的例子：司机-售票员问题：司机活动：售票员活动：

Do{Do{

关车门启动车辆正常行驶售票到站停车

开车门

}While(1)

}While(1)信号量机制设置信号量S1,初值为0，用于司机“启动汽车”和售票员“关车门”的同步设置信号量S2,初值为0，用于司机“到站停车”和售票员“开车门”的同步信号量机制（这里我们用pv描述）例子：司机-售票员问题：VARs1,s2:semaphore;(initialvalue0)司机活动：售票员活动：

Do{Do{

P(S1)

关车门

启动车辆V(S1)

正常行驶售票到站停车P(S2)

V(S2)开车门

}While(1)}While(1)分析：从以上几个例子可以看出在semWait中S:=S-1表示进程请求获得一个资源当信号量S>0时，S的值表示某类资源可用的数量S<0

表示无资源分配给请求的进程，于是将它排在信号量S的等待队列Q中，这时S的绝对值正好等于信号量队列Q上的进程数目semSignal中的S:=S+1可知进程释放了一个资源信号量机制信号量需要使用队列来保存在信号量上等待的进程，进程按照某个顺序从队列中移出最公平的策略是先进先出(FIFO):被阻塞时间最久的进程最先从队列释放，定义中包括这个策略的信号量称为强信号量没有规定进程从队列中移出顺序的信号量称为弱信号量强信号量保证不会饿死，是操作系统提供的典型的信号量形式信号量机制一个强信号量的例题：现有四个进程A、B、C、D，进程A、B、C依赖于进程D的结果，且进程D的一个计算结果只能作为A、B、C进程其中一个的输入数据分析：进程A、B、C与进程D之间有相互协作关系——同步对于进程D的同一个计算结果，只能给进程A、B、C中的一个使用——某种意义上也是互斥设置信号量S，表示现有资源数（即可用的D的计算结果，设s当前值为1）信号量机制//A、B、C的程序伪代码whiletruedo{semWait(S);

取得一个D的输出数据；

处理数据；

一次处理完毕，sleep(2)；}信号量机制//D的程序伪代码

whiletruedo{处理数据；输出一数据

semSignal(S);

一次任务完成，sleep(2)；}DCA处理器信号量Bs=0②就绪队列阻塞队列semWait(S)semWait(S)处理器①信号量s=1阻塞队列ABDC就绪队列BDCAs=0

AS=-1BABD处理器信号量Cs=0④就绪队列阻塞队列semSignal(S)semWait(S)处理器③信号量s=-1阻塞队列CA就绪队列DBBs=0DBDs=-1CsemWait(S)As=-2ADBs=-2处理器⑤信号量s=-2阻塞队列DB就绪队列ACsemSignal(S)处理器⑥信号量s=-2阻塞队列B就绪队列DACS=-1ABC生产者/消费者问题是著名的进程同步问题p109问题描述有一组生产者进程和一组消费者进程。生产者进程生产物品（某种类型的数据）；消费者进程消费物品。为使生产者和消费者进程并发执行，在它们之间设置了一个具有n个缓冲区的缓冲池。生产者将他们生产的物品放入一个缓冲区中，消费者每次从一个缓冲区中取一个物品进行消费。生产者和消费之间必须保持一定的同步关系：不允许消费者进入空的缓冲池取物品，也不允许生产者向已满的缓冲池中放物品。生产者/消费者问题p1p2p3p4pic1c2c3c4ci......生产者/消费者问题p1p2p3p4pic1c2c3c4ci......生产者/消费者问题管理员，怎么没东西！消费者对生产者有依赖关系：只有生产者生产出产品，才能给消费者提供产品消费p1p2p3p4pic1c2c3c4ci......生产者/消费者问题生产者对消费者有依赖关系：只有消费者消费掉产品，才能给生产者提供存放产品的空间p1p2p3p4pic1c2c3c4ci......生产者/消费者问题p1c1同一时刻只允许一个生产者或者一个消费者进入缓冲池（仓库）分析生产者与生产者之间——互斥消费者与消费者之间——互斥生产者与消费者之间——即有同步又有互斥设置信号量（设初始缓冲池为空，共有n个缓冲区）用于互斥的公共信号量：s＝1，表示缓冲池可用-仓库

生产者的私有信号量：empty＝n，表示可用缓冲区-空位

消费者的私有信号量：full＝0，表示可用数据-物品伪代码实现生产者/消费者问题Procedureproducer(){//生产者进程程序代码

whiletruedo{producenextproduct;

semWait(empty);

semWait(s);buffer(in):=product;in:=(in+1)modn;

semSignal(full);

semSignal(s);}}生产者/消费者问题Procedureconsumer(){//消费者进程程序代码whiletruedo{

semWait(full);

semWait(s);goods:=buffer(out);out:=(out+1)modn;

semSignal(empty);

semSignal(s);consumeproduct}}生产者/消费者问题ParbeginProcedureproducer()；Procedureconsumer()；parend生产者/消费者问题生产者和消费者中的两个semWait语句分别可以互换吗，为什么？

semWait(empty);semWait(full);semWait(s);semWait(s);生产者/消费者问题想一想读者和写者问题一个文件或记录（即数据对象）可被多个进程共享。有些进程只要求读—reader；有些进程要修改内容—writer。允许多个reader进程同时读一个共享对象；但不允许writer进程和其他writer进程或reader进程同时访问共享数据对象分析：对于writer，只需在访问数据对象前，对信号量做semWait操作，释放数据对象时，做semSignal操作。对于reader，第一个访问数据对象者，要对信号量做一个semWait操作，而semSignal操作，则由最后一个释放对象的执行读者和写者问题因此设置一个变量readcount，以表示正在进行读操作的进程数目，初值为0。则进入：每增加一个reader进程，readcount＝readcount+1

readcount＝1，reader进程对读写互斥信号量执行

semWait操作退出：

每个reader进程退出，则readcount＝readcount-1readcount＝0，reader进程执行semSignal操作读者和写者问题设置信号量写者与其它写者和读者的互斥信号量：wrt初值为1；读者对于readcount的互斥信号量：x,初值为1实现同步互斥关系

读者和写者问题§4.2进程的同步与互斥—信号量writer：P（wrt）writingV（wrt）Reader:P(x)Readcount++P(wrt)V(x)readingP(x)Readcount--V(x)V(wrt)=1!=1=0!=0writer；beginsemWait（wrt）；

writingisperforming；

semSignal（wrt）；

end；读者和写者问题reader；

begin

semWait（x）；Readcount＝readcount+1；

ifreadcount==1then

semWait(wrt);

semSignal（x）；

readingisperfoming；

semWait（x）；Readcount＝readcount-1；

ifreadcount==0then

semSignal(wrt);

V（x）；beginreadcount=0;wrt.value=1;x.value=1;cobeginr1:reader;……;rm:reader;w1:writer;……;wn:writer；coendend读者和写者问题问题：读者源源不断，read_count不归0，写者会被饿死。策略：一旦有写者等待，新到达读者等待，等正在读的读者都结束后，写者先进入，即写者优先。实现代码如下：读者和写者问题reader：BeginsemWait(z);semWait(rsem);semWait(x);readcount++;if(readcount==1)semWait(wsem);

semSignal(x);semSignal(rsem);semSignal(z);READUNIT();semWait(x);readcount--;if(readcount==0)

semSignal(wsem);semSignal(x);endwriter：Begin

semWait(y);

writecount++;

if(writecount==1)

semWait(rsem);

semSignal(y);semWait(wsem);WRITEUNIT();semSignal(wsem);semWait(y);

writecount--;

if(writecount==0)

semSignal(rsem);semSignal(y);endbeginreadcount=0;writecount=0;wsem.value=1;rsem.value=1;x.value=1;

y.value=1;cobeginr1:reader;……;rm:reader;w1:writer;……;wn:writer；coendend读者和写者问题理发室椅子入口出口等候室简单理发店问题一个理发店由一个有几张椅子的等候室、一个放有一张理发椅的理发室和一个理发师组成。若没有要理发的顾客，则理发师就去睡觉；若一顾客走进理发店且所有的椅子都被占用了，则该顾客就离开理发店；若理发师正在为人理发，则该顾客就找一张空椅子坐下等待;若理发师在睡觉，则顾客就唤醒他。简单理发店问题分析只有当顾客坐上理发椅，理发师才开始理发—同步当正在理发的顾客理好发，等待的顾客才能理发—同步同一时刻只有一个顾客能理发——互斥同一时刻只有有限的顾客能在等待室等待——互斥资源与信号量对于理发师：坐上理发椅的顾客，信号量barber＝0对于理完发的顾客：是否有顾客等待，信号量wait＝0对于进入的顾客：是否有人在理发，及等候室是否已满，变量count＝0保证对共享变量count的互斥访问的信号量：entry＝1简单理发店问题//共享数据结构：

varbarber,wait:semaphore;(初始值=0)

entry:semaphore; (初始值=1)

couter:integer; (初始值=0)//关于理发师的代码段：

whiletruedo{

P(barber);

“Shave”

}简单理发店问题//关于顾客的代码段：

P(entry);

ifcount=nthen

{V(entry);exit;

} count:=count+1;

ifcount>1then

{V(entry);

P(wait);}简单理发店问题elseV(entry);V(barber);

“Shave”

P(entry);

count:=count–1;

ifcount>0thenV(wait);

V(entry);理发室椅子入口出口等候室简单理发店问题barber信号量队列wait信号量队列entry信号量队列理发师理发师P（barber）P（entry）P（entry）count=0=1v（entry）唤醒count=1v（entry）Count=2P（wait）V（barber）QQ王国的简单理发店问题理发师barber信号量队列wait信号量队列entry信号量队列P（entry）count=5QQ王国的简单理发店问题V（entry）P（entry）count=5count=4V（entry）V（wait）V（barber）P（barber）

解:

vara,b,c,d,e,f,g,h:semaphore(初值=0)

parbegin

beginS1;V(a);V(b);V(c);end;

beginP(a);S2;V(d);V(e);end;

beginP(b);S3;V(f);end;

beginP(c);P(d);S4;V(g);end;

beginP(e);P(f);S5;V(h);end;

beginP(g);P(h);S6;end;

parend例:考虑右图所示的优先图，请用并发语句和信号量表达该优先图。习题S1S3S4S6S5S2abcdefhg桌上有一个空盘，允许存放一个水果。父亲可向盘中放苹果，也可向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时一次放一个水果供吃者取用，请用P，V原语实现父亲、儿子、女儿三个并发进程的同步。分析同步/互斥关系：父亲和儿子之间——同步父亲和女儿之间——同步习题设置信号量父亲的私有信号量s，表示盘子是否可用，初值为1儿子的私有信号量orange，表示是否有橘子可吃，初值为0女儿的私有信号量apple，表示是否有苹果可吃，初值为0习题father进程：L1：P(S)；将水果放入盘中；if(放入是橘子)

V(orange)；elseV(apple) ；

gotoL1；

习题daughter进程：L2：P(apple)；从盘中取出苹果；V(S)；吃苹果； gotoL2；

son进程：L3：P(orange)；从盘中取出橘子；V(S)；吃橘子； gotoL3；

更为高级的同步机构中,最重要的是管程建立管程的基本理由：由于临界区的执行分散在各进程中，PV操作可能分布在各个程序中，很难看出在信号量上的操作所产生的整体效果；也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题，也不便于系统对临界资源的控制和管理开锁、关锁原语和信号量上的P、V操作，是低级的同步机构，很难表示更为复杂的并发性问题把分散的各同类临界区集中起来，并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问，这样既便于系统管理共享资源，又能保证互斥访问管程什么是管程？临界资源的管理者或封装者，进程必须通过管程访问临界资源管程主要由两部分组成：局部于该管程的共享数据，这些数据表示了相应的资源局部于该管程的局部过程，由这些过程对临界资源进行操作管程一次只允许一个进程进入其内（即访问管程内的某个过程）——这是由编译系统保证。管程对于cedure-name的调用都将保证如下操作：

semWait(mutex);

执行相应的过程或函数

semSignal（mutex）；

mutex是相对于某个管程的互斥信号量策略：当一个进程进入管程后由于某个原因被阻塞，应该立即释放管程。对于阻塞原因设置条件变量，退出管程的进程到相应条件变量的等待队列上排队管程用管程实现生产者和消费者问题：为生产者与消费者的共享缓冲区建立一个管程

monitorbuffer；

procedureentryput(item)；

beginifk=nthenfull.wait；

buffer（in）:=item；

k:=k＋1;in:=(in+1)modn;ifempty.queuethenempty.signal;end;管程procedureentryget(item)；

beginifk＝0thenempty.wait；

goods:=buffer（out）；

k:＝k-1;out:=(out+1)modn;iffull.queuethenfull.signal;end;p1p2p3p4pic2c3c4ci......生产者/消费者问题full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生产者/消费者问题full.queueempty.queuec1p1p2p3p4pic2c3c4ci......生产者/消费者问题full.queueempty.queuec1初值：k＝0；in＝0；out＝0；用管程实现生产者和消费者问题：Producer：beginrepeatproduceanitem；buffer.put（item）；

untilfalse；end；管程Consumer：beginrepeatbuffer.get（item）；

consumetheitem；

untilfalse；

End；进程通讯：进程同步，互斥及信息交换统称为进程通信低级通讯（简单信号）高级通讯（交换大宗的信息）进程高级通讯进程通讯模式共享内存模式消息传递模式进程psend发送区（消息）接收区（消息）进程qreceivehptrmutexsmPCBsptrnptrtextsptrnulltextaddpnulltextpaddpnulltextpnptr直接通信发送进程将消息连入接受方的消息队列中；接收进程按先来先服务原则处理消息队列中的消息。处理完一个消息之后，向发送进程回送一个“回答”信号为了能高效率地实现进程通信，操作系统设计了多种高级通信原语send(R,M)原语和receive(PID,N)原语直接通信send(R,M)(发送消息)原语send(R,M)原语用来发送消息，M是发送进程提供的发送信息send(R,M)原语先申请一个消息缓冲区，然后把发送区的内容复制到消息缓冲区中。然后找到接收进程的PCB，把消息缓冲区连入接收进程的消息缓冲区队列中代码直接通信proceduresend（R,M）；

benginnew（p）；//创建一个空消息缓冲区将信息写入消息缓冲区

寻找到接收者R的PCB;

semWait(mutex);

将消息加入R的消息队列;

semSignal(sm);semSignal(mutex);

end；发送原语Send(R,M)receive(PID,N)(读取消息)原语receive(PID,N)原语用来读取消息，A是接收进程提供的接收区起始地址receive(PID,N)原语把消息缓冲区中的消息内容、消息长度以及发送进程的名字读取到接收区，然后把消息缓冲区从链表中去掉，并释放消息缓冲区如果没有消息可读取，则阻塞接收进程，直至消息发送来为止直接通信procedurereceive（PID,N）

benginsemWait(Sm);semWait(mutex);