电子科技大学计算机操作系统第2章 并发与进程-同步

计算机操作系统电子科技大学计算机科学与工程学院李玉军主要内容调度

scheduling死锁deadlock同步

synchronization进程

process2.6进程并发控制:互斥与同步日常生活现象过十字路口理发店理发银行取钱足球比赛为什么需要“规则和秩序”？个体自主性

异步（车辆，行人，顾客）资源稀缺性独占（十字路口，理发师，ATM）任务需合作协作（进球）2.6进程并发控制:互斥与同步多道程序设计为什么需要同步？进程是计算机中的独立个体，且具有异步性、并发性资源是计算机中的稀缺个体，需共享，如CPU、内存、I/O设备进程之间可能需要协作完成任务进程同步的主要任务使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。2.6.1并发控制并发控制示例1两个用户分别采用存折和储蓄卡对同一帐户（余额为5000元）同时办理两笔存款业务，分别存入1000元和2000元。从系统的角度看，有两个进程将同时对储户余额等数据进行修改。储户余额可能是6000元、7000元或8000元。原因：两个进程同时修改同一数据，而没有进行有效控制。正确的方法：对两个进程进行控制，一次仅允许一个进程全部完成读数据、修改数据、写数据事件以后，才允许别的进程对同一数据的读、修改和写操作。2.6.1并发控制并发控制示例2系统中有两个进程P1、P2和P3，共享一个缓冲区，P1和P2负责向缓冲区中写数据，P3负责取出缓冲区中的数据。某时刻，P1和P2都准备将数据送往缓冲区，考虑可能出现的情况。若计算进程P1、P2的推进速度远远低于P3进程的推进速度，考虑可能出现的情况，反之呢？…012345678n-1outin2.6.1并发控制——竞争资源进程间的制约关系间接制约

资源共享

互斥直接制约

进程合作

同步临界资源（CriticalResouce）必须互斥使用的资源为临界资源。P1P2生产者消费者P1P2账户余额2.6.1并发控制——竞争资源临界区（criticalsection）访问临界资源的那段代码称为临界区。进入区进程

临界区退出区2.6.1并发控制——竞争资源竞争临界资源引起的问题——忙等、饥饿和死锁RP0P1R1P0P1R2忙等死锁饥饿RP0P2P1空闲让进如临界区空闲，则有进程申请就立即进入。忙则等待每次只允许一个进程处于临界区。有限等待保证进程在有限时间内能进入临界区。让权等待进程在临界区不能长时间阻塞等待某事件。效率公平2.6.1并发控制——竞争资源临界区使用原则（互斥条件）2.6.2互斥与同步的解决策略策略软件硬件信号量管程消息传递2.6.2互斥与同步的解决策略软件方法由进程通过执行相应的程序指令，实现与其他进程的互斥与同步。难以实现且开销大。硬件方法通过屏蔽中断（单CPU）或采用专门的机器指令控制互斥与同步。硬件约束条件强且可能导致进程饥饿与死锁现象。操作系统或专门的程序设计语言提供的特别支持信号量方法——已成为通用方法管程方法消息传递方法2.6.3软件方法软件方法在进入区设置和检查一些标志来标明是否有进程在临界区。若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。初步设想——轮换使用临界区inttrun=0;//共享的全局变量进程P0do{while(turn!=0);//进入区进程P0的临界区代码；//临界区

turn=1;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{while(turn!=1);//进入区进程P1的临界区代码；//临界区

turn=0;//退出区进程P1的其它代码//剩余区}while(true)备注：严格轮换，实现了互斥访问。即使在临界区外失败也会影响另进程的执行。违反了“空闲让进”原则。忙等。2.6.3软件方法第一次改进——设置临界区状态标志booleanflag[2]={false,false};//共享的全局变量进程P0do{while(flag[1]);//进入区

flag[0]=true;//进入区进程P0的临界区代码；//临界区

flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{while(flag[0]);//进入区

flag[1]=true;//进入区进程P1的临界区代码；//临界区

flag[1]=false;//退出区进程P1的其它代码//剩余区}while(true)备注：忙等违反了“忙则等待”原则，互斥访问未实现2.6.3软件方法第一次改进——设置临界区状态标志（续）P0Ifflag[1]=falsewhile(flag[1]);中断P1Ifflag[0]=falsewhile(flag[0]);flag[0]=true;中断中断flag[1]=true;临界区2.6.3软件方法第二次改进——预先表明进入临界区的态度booleanflag[2]={false,false};//共享的全局变量进程P0do{flag[0]=true;//进入区while(flag[1]);//进入区进程P0的临界区代码；//临界区

flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{flag[1]=true;//进入区while(flag[0]);//进入区进程P1的临界区代码；//临界区

flag[1]=false;//退出区进程P1的其它代码//剩余区}while(true)备注：实现了互斥访问。违反了“空闲让进”原则，可能导致死锁。2.6.3软件方法第二次改进——预先表明进入临界区的态度（续）P0flag[0]=true;中断P1flag[1]=true;中断while(flag[1]);while(flag[0]);忙等忙等死锁2.6.3软件方法第三次改进——预先表明进入临界区的态度+谦让booleanflag[2]={false,false};//共享的全局变量进程P0do{flag[0]=true;while(flag[1]){

flag[0]=false;<随机延迟一小段时间>；

flag[0]=true;}进程P0的临界区代码；//临界区

flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{flag[1]=true;while(flag[0]){

flag[1]=false;

<随机延迟一小段时间>；

flag[1]=true;}进程P1的临界区代码；//临界区

flag[1]=false;//退出区进程P1的其它代码//剩余区}while(true)备注：实现了互斥访问非死锁，但可能长时间僵持2.6.3软件方法——第三次改进（续）P0flag[0]=true中断P1flag[1]=true中断whileflag[1]中断whileflag[0]中断flag[0]

=false延迟一段时间中断flag[1]

=false延迟一段时间中断flag[0]=trueflag[1]=true中断中断{}{}booleanflag[2]={false,false};//共享的全局变量intturn=1;//共享的全局变量进程P0do{flag[0]=true;//进入区while(flag[1]){if(turn==1){flag[0]=false;while(turn==1);flag[0]=true;}}//进入区进程P0的临界区代码；//临界区

turn=1;flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{flag[1]=true;//进入区while(flag[0]){if(turn==0){flag[1]=false;while(turn==0);flag[1]=true;}}//进入区进程P1的临界区代码；//临界区

turn=0;flag[1]=false;//退出区进程P1的其它代码//剩余区}while(true)2.6.3软件方法—Dekker互斥算法给定序号避免“过分谦让”2.6.3软件方法—Dekker互斥算法（续）flag[0]:=trueflag[0]:=falseturn01turn01flag[0]:=trueflag[1]falseP0进入临界区退出临界区turn:=1flag[0]:=false其余部分true进程P0do{flag[0]=true;//进入区while(flag[1]){if(turn==1){flag[0]=false;while(turn==1);flag[0]=true;}}//进入区进程P0的临界区代码；//临界区

turn=1;flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)2.6.3软件方法——Peterson互斥算法booleanflag[2]={false,false};//共享的全局变量intturn;//共享的全局变量进程P0do{flag[0]=true;//进入区turn=1;//进入区while(flag[1]&&turn==1);//进入区进程P0的临界区代码；//临界区

flag[0]=false;//退出区进程P0的其它代码//剩余区}while(true)进程P1do{flag[1]=true;//进入区

turn=0;//进入区while(flag[0]&&turn==0);//进入区进程P1的临界区代码；//临界区

falg[1]=false;//退出区进程P1的其它代码//剩余区}while(true)软件方法特点软件方法始终不能解决“忙等”现象，降低系统效率。采用软件方法实现进程互斥使用临界资源是很困难的，它们通常能实现两个进程的互斥，很难控制多个进程的互斥。算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。2.6.3软件方法2.6.4硬件方法硬件方法屏蔽中断机器指令Test

&

SetExchange2.6.4硬件方法——屏蔽中断屏蔽中断：避免进程切换，实现互斥访问。屏蔽中断的缺点系统无法响应外部请求无法接受异常，处理系统故障无法切换进程

性能下降不支持多处理机while(true){

disableinterrupt//屏蔽中断

criticalsection//临界区enableinterrupt//启用中断remainder//其余部分}2.6.4硬件方法——专用机器指令专用机器指令在多处理器环境中，几个处理器共享访问公共主存；处理器表现出一种对等关系，不存在主／从关系；处理器之间没有支持互斥的中断机制；处理器的设计者提出了一些机器指令，用于保证两个动作的原子性如在一个周期中对一个存储器单元的读和写；这些动作在一个指令周期中执行，不会被打断，不会受到其他指令的干扰。2.6.4硬件方法——TestandSet测试某个变量的值，如果满足条件，则置位X86:TEST1:functiontestset(vari:integer)

:boolean;

2:begin

3:

ifi=

0

then

4:

begin

5:

i

:=

1;

6:

testset:=true;

7:

end

8:

elsetestset:=false;

9:end

2.6.4硬件方法——TestandSet（续）1:programmutualexclusion;

2:

constn＝...;

{*进程数*}

3:

varbolt:integer；4:procedureP(i:integer)；5:begin

6:

repeat

7:

repeat

{dono-op}

untiltestset(bolt);

{*当bolt为0时，进入临界区*}

8:

<criticalsection>;

9:

bolt:=

0;

10:

<remainder>;

11:

forever12:end;

13:begin

{*mainprogram*}

14:

bolt:=

0;

15:

parbegin16:

P(1);P(2);

...P(n);

17:

parend18:end

示例2.6.4硬件方法——Exchange原子性地交换寄存器和内存的值X86:XCHG1:procedureexchange(varr:register;

varm:memory);

2:

vartemp;

3:

begin

4:

temp:=m;

5:

m:=r;

6:

r:=temp;

7:

end

2.6.4硬件方法——Exchange（续）1:programmutualexclusion；2:constn=...;

{*numberofprocesses*}

3:varbolt:

integer;4:procedureP(i:integer);

5:varkey:integer;

6:begin7:

repeat

8:

key:=1;

9:

repeat

exchange(key,bolt)

untilkey=0;

10:

<criticalsection>;

11:

exchange(key，bolt);

12:

<remainder>;13:

forever14:end;

15:begin

{*mainprogram*}

16:

bolt:=

0;

17:

parbegin18:

P(1);P(2);

...P(n);

19:

parend20:end

示例2.6.4硬件方法不足忙等现象饥饿现象死锁现象?优点支持多处理机简单，易证明支持多临界区2.6.5信号量方法交通信号灯：红灯停，绿灯行2.6.5信号量方法信号量实现进程互斥的基本原理两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以“向前推进”的信号（被唤醒）。将实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待该信号量的阻塞进程（通常为FIFO）。2.6.5

信号量方法信号量定义typesemaphore=recordcount:integer;queue:listofprocessend;vars:semaphore;2.6.5

信号量方法信号量的两个原子操作：wait(s)和signal(s)，有时也称作P(s)和V(s)。vars:semaphore;wait(s):s.count:=s.count–1;ifs.count<0thenbegin

进程阻塞；进程进入s.queue队列；

end;vars:semaphore;signal(s):s.count:=s.count+1;ifs.count<=0thenbegin

唤醒队首进程；将进程从s.queue阻塞队列中移出；

end;2.6.5

信号量方法信号量的物理意义s.count＞0表示目前临界资源的可用数量，即还可执行wait(s)而不会阻塞的进程数。每执行一次wait(s)操作，意味着请求分配一个单位的资源。s.count≤0表示已无可用的临界资源，请求该资源的进程被阻塞。此时，s.count的绝对值等于该信号量阻塞队列中的等待进程数。执行一次signal操作，就意味着释放一个单位的资源。若s.count≤0，表示s.queue队列中还有被阻塞的进程，需要唤醒该队列中的第一个进程，将它转移到就绪队列中。2.6.5

信号量方法wait、signal的应用进程进入临界区之前，首先执行wait(s)原语，若s.count<0,则进程调用阻塞原语，将自己阻塞，并插入到s.queue队列排队。一旦其它某个进程执行了signal(s)原语中的s.count+1操作后，发现s.count≤0，即阻塞队列中还有被阻塞进程，则调用唤醒原语，把s.queue中第一个进程修改为就绪状态，送就绪队列，准备执行临界区代码。不占CPU时间，非“忙等”2.6.5

信号量方法利用信号量实现互斥的通用模式

1:varmutexsemaphore:=

1;

2:

3:procedureP(i:integer):

4:begin

5:

repeat

6:

wait(mutex);

7:

<criticalsection>;

8:

signal(mutex);

9:

<remaindersection>;

10:

forever11:end

12:13:parbegin14:

P(1);P(2);

...;P(n);

15:parendS:1P0P1S:0P1等待队列P1S:-12.6.5

信号量方法利用信号量实现前趋关系示例P1、P2、P3、P4、P5和P6为一组合作进程，其进程前趋图如下所示，试用P、V操作实现这六个进程的同步。P1P2P3P4P5P62.6.5

信号量方法利用信号量实现前趋关系示例(续1)P1P2P3P4P5P6semaphores12=0;semaphores13=0;semaphores24=0;semaphores25=0;semaphores36=0;semaphores46=0;semaphores56=0;main(){cobegin//P1-P6进程并发执行

P1();P2();P3();P4();P5();P6();coend}

2.6.5

信号量方法利用信号量实现前趋关系示例(续2)P1P2P3P4P5P6P1(){

…V(s12);V(s13);}

P2(){P(s12);

…V(s24);V(s25);}P3(){P(S13);

…V(s36);}P4(){P(s24);

…V(s46);}P5(){P(s25);

…V(s56);}

P6(){P(s36);P(s46);P(s56);

…}信号量的类型：依据使用方式互斥信号量资源信号量2.6.5

信号量方法2.6.5

信号量方法互斥信号量用于申请或释放资源的使用权，通常初始化为1资源信号量用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数。2.6.5

信号量方法互斥信号量的取值范围及含义两个并发进程共享临界资源

s.count=1,表示无进程进入临界区s.count=0，表示已有一个进程进入临界s.count=-1,则表示已有一进程正在等待进入临界区n个进程共享临界资源

-(n-1)≤s.count≤1资源信号量的取值范围

依赖于临界资源数量和并发进程数量2.6.6

管程管程的引入信号量为实施互斥及进程间合作提供一种原始但功能强大且灵活的工具。信号量的P、V操作可能分散在整个程序中，使用难度高。管程是一个程序设计语言结构，采用了集中式的进程同步方法，提供了与信号量同样的功能，但更易于控制。很多程序设计语言都支持管程，如Pascal、Java等。管程有多种实现方式使用信号（Hoare）使用通知和广播2.6.6

管程管程的组成管程的概念一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。（C.A.R.Hoare&PerBrinchHansen）局部数据过程初始化序列2.6.6

管程管程的特点局部数据变量只能被管程的过程访问，任何外部过程都不能访问。一个进程通过调用管程的一个过程进入管程。在任何时候，只能有一个进程正在管程执行，调用管程的任何其它进程都被阻塞，以等待管程可用。互斥2.6.6

管程问题若由于某种原因，一个正在管程中执行的进程必须阻塞，该如何处理？释放管程供其它进程使用同步机制2.6.6

管程管程中的同步机制管程通过使用条件变量提供对同步的支持。条件变量包含在管程中，只能在管程中访问。操作条件变量的两个函数cwait(c)

调用进程的执行在条件c上阻塞，管程可供其它进程使用。csignal(c)恢复某个阻塞进程，若不存在阻塞进程，则什么都不做。2.6.6

管程管程的结构局部于管程的数据条件变量过程1过程m初始化代码条件c1wait（c1)条件cnwait(cn)紧急队列signal等待进入管程的进程队列入口出口管程等待区2.7生产者/消费者问题经典同步问题生产者/消费者理发师读/写者哲学家就餐2.7生产者/消费者问题荷兰计算机科学家E.W.Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”ProducerConsumerProblemBounded-BufferProblem2.7生产者/消费者问题生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程（如游戏中的金币、血）。生产者和消费者进程共享一个大小固定的缓冲区。一个或多个生产者生产数据，并将生产的数据存入缓冲区。一个或多个消费者从缓冲区中取数据，即消费数据。2.7生产者/消费者问题假设缓冲区的大小为n（存储单元的个数），它可以被生产者和消费者循环使用。分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取数据的存储单元。123…N-2…0N-1…inout使用方向供应方向2.7生产者/消费者问题生产者/消费者模型缓冲区：固定大小生产者：满则等待，空则填充消费者：空则等待，有则获取P1P2…PnC1C2…Cninout2.7生产者/消费者问题各个生产者、消费者独立自主向前推进指针in和out初始化指向缓冲区的第一个存储单元。生产者通过in指针向存储单元存放数据，一次存放一条数据。每存放一条数据后，in指针向后移一个位置。消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”。每取走一条数据后，out指针向后移一个存储单元位置。试想，将会产生什么结果？2.7生产者/消费者问题生产者/消费者必须互斥生产者和消费者不能同时读/写一个存储单元多个生产者不能同时写缓冲区多个消费者不能同时取缓冲区数据生产者/消费者必须同步生产者不能向满缓冲区写数据消费者也不能在空缓冲区中取数据2.7生产者/消费者问题

(a)生产者(b)消费者无阻塞等待资源被唤醒否被唤醒是否有数据单元消费数据是否可用取一条数据有是归还使用权空单元加1唤醒一个生产者阻塞等待资源阻塞等待使用权被唤醒否被唤醒是否有空存储单元生产一条数据是否可用有存入一条数据归还使用权是数据单元加1唤醒一个消费者无阻塞等待使用权2.7生产者/消费者问题

programproducer_consumer;constsizeofbuffer=…;/*缓冲区大小*/vars:semaphore(:=1);/*互斥信号量s，初始化为1*/

n:semaphore(:=0);/*资源信号量n，数据单元，初始化为0*/

e:semaphore(:=sizeofbuffer);/*资源信号量e，空存储单元*/procedureproducer; procedureconsumer;begin beginrepeat repeat

生产一条数据; wait(n);

wait(e); wait(s);wait(s); 取一条数据；存入一条数据; signal(s);signal(s); signal(e);

signal(n)；消费数据；

foreverforeverend;end;begin/*主程序*/parbeginproducer;consumer;parendend.2.7生产者/消费者问题注意(1)应先申请资源信号量，再申请互斥信号量，顺序不能颠倒。Consumer：Producer：wait(e);wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);当n=0,s=1时，执行顺序：Consumer.wait(s);Consumer.wait(n);Producer.wait(e);Producer.wait(s);2.7生产者/消费者问题注意(2)同一进程中的多对wait与signal语句只能嵌套，不能交叉?Consumer：Producer：wait(e);wait(s);存入一条数据;signal(n);signal(s);wait(s);wait(n);取一条数据;signal(s);signal(e);2.7生产者/消费者问题注意(3)对于同一个信号量的wait与signal操作，既可以出现在同一个进程中，也可以出现在不同进程中。Consumer：Producer：wait(e);wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);2.7生产者/消费者问题注意(4)对任何信号量的wait与signal操作必须配对。

Consumer：Producer：wait(e);wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);2.7生产者/消费者问题注意(5)wait与signal语句不能颠倒顺序，wait语句一定先于signal语句？(应为：在进入临界区前必须先执行wait操作，退出临界区后必须执行signal操作。对于同一信号量而言，既有可能先执行wait操作，也有可能先执行signal操作。)Consumer：Producer：wait(e);wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);2.7生产者/消费者问题生产者/消费者问题的管程解决方法monitorboundedbuffer;charbuffer[n];intnextin,nextout;intcount;condnotfull,notempty;voidappend(charx){

if(count==N)cwait(notfull);

buffer[nextin]=x;

nextin=(nextin+1)%N;

count++;

csignal(notmpty);}voidtake(charx){

if(count==0)cwait(notemptyl);

x=buffer[nextout];

nextout=(nextout+1)%N;

count--;

csignal(notfull);}{nextin=0;nextout=0;count=0;}voidproducer(){

charx;while(true){

produce(x);

append(x);

}}voidconsumer{

charx;while(true){

take(x);

consume(x);}}2.7生产者/消费者问题生产者/消费者问题示例三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区的某一空单元中；P2每次用getodd()从该缓冲区取出一个奇数并用countodd统计奇数个数；P3每次用geteven()从缓冲区取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。2.7生产者/消费者问题生产者/消费者问题示例——分析缓冲区是一互斥资源，故设置互斥信号量mutexP1、P2因为奇数的放置与取用而同步，设置同步信号量odd；P1、P3因为偶数的放置与取用而同步，设置同步信号量even；P1、P2、P3因为共享缓冲区，设置同步信号量empty。2.7生产者/消费者问题

semaphoremutex=1;//缓冲区操作互斥信号量semaphoreodd=0,even=0;//奇数、偶数进程的同步信号量semaphoreempty=N;//空缓冲区单元个数信号量P1(){while(true){number=produce();P(empty);//递减空缓冲区的单元个数

P(mutex);//互斥访问缓冲区

put();V(mutex);//恢复访问缓冲区if(number%2==0)//为偶数

V(even);//允许取偶数

else//为奇数

V(odd);//允许取奇数

}}2.7生产者/消费者问题

P2(){while(true){P(odd);//互斥取奇数P(mutex);//互斥访问缓冲区

getodd();V(mutex);//恢复访问缓冲区V(empty);//递增空缓冲区的单元个数

countodd();}}2.7生产者/消费者问题

P3(){while(true){P(even);//互斥取偶数P(mutex);//互斥访问缓冲区

geteven();V(mutex);//恢复访问缓冲区V(empty);//递增空缓冲区的单元个数

counteven();}}main()/*主程序*/{cobeginP1();P2();P3();coend}2.8读者和写者问题问题描述多个进程访问一个共享数据区为数据库、文件、内存区及一组寄存器等的数据访问问题建立了一个通用模型。其中若干读进程只能读数据，若干写进程只能写数据。示例——联网售票系统、12306在该系统中，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改（读/写）其中某一条数据的情形。2.8读者和写者问题读者/写者进程满足的条件允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据，即只能互斥写数据；若有写者进程正在写数据，则不允许读者进程读数据——互斥读写。2.8读者和写者问题如何控制读者和写者？采用生产者/消费者问题解决方法

严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。允许同时读，但不允许同时写、读写。2.8读者和写者问题读者和写者问题——描述图读者/写者问题描述三种角色读进程写进程共享数据三个条件同时读互斥写互斥读写2.8读者和写者问题读者和写者问题——解决策略读者/写者问题解决策略严格互斥任意两个进程互斥任意两个写者进程，读、写进程读者优先写者优先公平优先2.8读者和写者问题读者优先一旦有读者正在读数据，则允许随后的读者进入读数据。只有当全部读者退出，才允许写者进入写数据。导致写者饥饿读者优先的变量设置wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writersreadcount：统计同时读数据的Readers个数mutex：对变量readcount互斥算术操作voidreader(){while(1){P(mutex);

readcount++;

if(readcount==1)P(wsem);V(mutex);READ;P(mutex);

readcount--;

if(readcount==0)V(wsem);V(mutex);}}2.8读者和写者问题voidwriter(){while(1){P(wsem);WRITE;V(wsem);}}intreadcount=0；semaphoremutex=1,wsem=1;序列：RRRWWWRWRRWRWRRWWRWRRWwriter饥饿2.8读者和写者问题公平优先写过程中，若其它读者、写者到来，则按到达顺序处理。公平优先的变量设置wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writersreadcount：统计同时读数据的Readers个数mrc：对变量readcount互斥算术操作wrsem：互斥信号量，确定Writer、Reader请求顺序2.8读者和写者问题intreadcount=0,semaphoremrc=l,wrsem=1,wsem=l;voidreader(){while(true){P(wrsem);P(mrc);readercount++;

if(readercount==1)

P(wsem);

V(mrc);

V(wrsem);READ;

P(mrc);

readercount--;

if(readercount==0)

V(wsem);

V(mrc);}}voidwriter(){while(true){P(wrsem);P(wsem);WRITE;V(wsem);V(wrsem);}}序列：R,R,R,W,R,R,R,W,R…2.8读者和写者问题写者优先只要有一个写者申请写数据，则不再允许新的读者进入读数据。解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差。写者优先的变量设置rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据writecount：用于控制rsem信号量mwc：对变量writecount互斥算术操作2.8读者和写者问题intreadcount=0,writecount=0;semaphoremrc=l,mwc=1,wsem=1,rsem=l;voidreader()

{while(1){

P(rsem);

P(mrc);

readcount++;

if(readcount==1)P(wsem);

V(mrc);

V(rsem)；READ;

P(mrc);

readcount--;

if(readcount==0)

V(wsem);

V(mrc);

}}voidwriter(){

while(1){

P(mwc);

writecount++;

if(writecount==1)P(rsem);

V(mwc);

P(wsem);

WRITE;

V(wsem);

P(mwc);

writecount--;

if(writecount==0)V(rsem);

V(mwc);

}}序列：WRRWWRRRRRRRW1.RRWR2.8读者和写者问题intreadcount=0,writecount=0;semaphoremrc=l,mwc=1,z=1,wsem=1,rsem=l;voidreader()

{while(1){

P(z);

P(rsem);

P(mrc);

readcount++;

if(readcount==1)P(wsem);

V(mrc);

V(rsem)；

V(z);

READ;

P(mrc);

readcount--;

if(readcount==0)

V(wsem);

V(mrc);

}}voidwriter(){

while(1){

P(mwc);

writecount++;

if(writecount==1)P(rsem);

V(mwc);

P(wsem);

WRITE;

V(wsem);

P(mwc);

writecount--;

if(writecount==0)V(rsem);

V(mwc);

}}RRRRRW2.8读者和写者问题写者优先的思考教材中描述“z信号量的好处是：限制了rsem阻塞队列的长度”，“无法唤醒全部阻塞读者”P(z)和P(rsem)能否互换位置？理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他就离开。补充——理发师睡觉问题理发师和顾客工作流程补充——理发师睡觉问题voidcustomer(){P(mutex);//互斥waiting变量的操作

if(waiting<6)//有空椅子则坐下等待

waiting++;//等待顾客数增1else离开；V(mutex);//允许waiting变量的操作P(wchair);//找一个空椅子坐下

P(bchair);//再找理发椅坐下

V(wchair);//允许其他人坐空椅子

V(ready);//该顾客准备好了

P(finish);//等待理发师完成理发

V(bchair);//离开理发椅

P(mutex);//互斥waiting变量的操作

waiting--;//等待顾客数减1V(mutex);//允许waiting变量的操作}补充——理发师睡觉问题intwaiting=0;//等待的顾客,含正在理发的人数semaphoremutex=1;//waiting的互斥信号量semaphorebchair=1;//理发椅的个数semaphorewchair=5;//空椅子的个数semaphoreready

=0;//是否有顾客准备好semaphorefinish=0;//理发师是否完成理发main(){cobeginbaber();customer();coend}voidbaber()//理发师进程{while(true){P(ready);//有顾客准备好了理发；V(finish);//允许其他顾客理发}}某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：cobegin{process顾客i{从取号机上获取一个号码；等待叫号；获取服务；}process营业员{while(true){叫号；为顾客服务；}}}

请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完成的过程，说明信号量的含义并赋初值。补充——理发师睡觉问题的类似问题semaphoremutex=1;//互斥使用取号机的信号量semaphoreempty=10;//空座位的数量信号量semaphorefull=0;//已占座位的数量信号量semaphoreservice

=0;//等待叫号信号量补充——理发师睡觉问题的类似问题process顾客i{P(empty);P(mutex);

从取号机获得一个号；

V(mutex);V(full);P(service);//等待叫号}process营业员{while(true){

P(full);V(empty);V(service);//叫号为顾客服务;}}2.9消息传递进程通信(InterProcessCommunication,IPC)

进程之间的信息交换进程通信方式低级通信以信号、信号量作为通信工具，由于其所交换的信息量少而被归结为低级通信。高级通信

指用户可直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。2.9消息传递电子邮件的发送与接收过程发送进程接收进程邮件服务器接收进程发送进程终端用户邮件邮件发送进程接收进程邮件服务器接收进程发送进程终端用户邮件2.9.1

进程通信的方式共享存储区消息传递2.9.2

共享存储区方式共享数据结构（程序员控制）共享存储区（操作系统控制）正文数据栈共享存储区正文数据栈进程A的虚空间内存空间进程B的虚空间AA`BB`2.9.3

消息传递机制数据交换以格式化的消息为单位消息的一般格式消息类型目的端地址源端地址消息长度控制信息消息内容消息头消息体2.9.3

消息传递机制消息传递的同步两条通信原语

Send(destination,message)Receive(source,message)消息传递的同步当发送进程调用Send原语发送消息时，若没有空闲的消息缓冲区，则发送进程塞阻。当接收进程调用Receive原语接收消息时，如果没有消息可接收，则接收进程阻塞，直到一条消息到达。2.9.3

消息传递机制三种同步方式阻塞发送阻塞接收不阻塞发送阻塞接收

不阻塞发送不阻塞接收2.9.3

消息传递机制不阻塞发送如打印服务，每当进程需要打印时，都可以以消息形式发出请求，然后继续执行，无须阻塞等待打印完成。“不阻塞发送”方式容易导致消息的无限发送。必须在程序中考虑让接收进程发回应答消息，证实其是否收到消息——增加了并发程序的设计难度。阻塞接收并发程序设计中常采用该方式。若消息丢失，或发送进程发送消息之前失败，则接收进程将永久阻塞。2.9.3

消息传递机制消息传递中的寻址寻址方式：直接寻址和间接寻址。若采用直接寻址，send原语中必须指定目标进程的具体标识号receive原语中的source地址有两种处理方法：接收进程显式地指定发送方进程标识号，这就要求接收进程必须事先清楚将接收哪个进程发来的消息。接收进程可以不必指定接收哪个进程的消息2.9.3

消息传递机制间接寻址采用间接寻址传递消息时，消息不再从发送方直接发送到接收方，而是通过发送进程与接收进程共享的一个数据结构进行中转，该数据结构通常称为邮箱。发送进程将消息发送到指定的邮箱中，接收进程从邮箱中接收消息。2.9.3

消息传递机制邮箱不限制进程数，允许多个发送进程向邮箱发送消息，同时，也允许多个接收进程从邮箱接收消息邮箱R1SnS1Rn发送进程接收进程2.9.4利用消息传递实现互斥互斥不允许两个或两个以上的进程同时进入临界区如何利用消息传递实现互斥？多个并发执行的发送进程和接收进程共享一个邮箱box，且box的初始状态为仅包含一条空消息；采用“不阻塞发送，阻塞接收”方式传递消息；若邮箱中存在一条消息，则允许一个进程进入临界区。若邮箱为空，则表明有一个进程位于临界区，其它试图进入临界区的进程必须阻塞。只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使用临界资源。voidP(inti){

messagemsg;while(true){

receive(box,msg);/*从邮箱接收一条消息*/

<临界区>;

send(box,msg);

/*将消息发回到邮箱*/

<其余部分>

}}/*programmutualexclusion

*/constintn=/*进程数*/;voidmain(){

create_mailbox(box);/*创建邮箱*/

send(box,null);

/*初始化，向邮箱发送一条空消息*/

parbegin(P(1),

P(2),

…,P(n));}生产者/消费者模型缓冲区：固定大小生产者：满则等待，空则填充消费者：空着等待，有则获取P1P2…PnC1C2…Cninout2.9.5利用消息传递解决生产者/消费者问题

2.9.5利用消息传递解决生产者/消费者问题

如何采用消息传递的方法实现生产者/消费者同步？使用capacity条消息，其作用类似于缓冲区的大小；capacity条消息的初始状态为“空”消息，类似于缓冲区的初始状态为空（未填充生产数据）；生产者生产一条数据后，取一条“空”消息，并发送回一条填充了数据的消息；消费者消费一条数据后，取一条填充了数据的消息，并发送回一条“空”消息；若生产者速度快于消费者消速度，则因无“空”消息可用而阻塞；若消费者速度快于生产者消速度，则因无填充了数据的消息可用而阻塞。voidproducer(){

messagepmsg;while(true){

receive(mayproduce,pm