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

1、计算机操作系统电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院李玉军李玉军:调度scheduling死锁deadlock同步synchronization进程process: 日常生活现象 过十字路口 理发店理发 银行取钱 足球比赛 为什么需要“规则和秩序”？ 个体自主性 异步车辆，行人，顾客） 资源稀缺性 独占十字路口，理发师，ATM） 任务需合作 协作进球）: 多道程序设计为什么需要同步？ 进程是计算机中的独立个体，且具有异步性、并发性 资源是计算机中的稀缺个体，需共享，如CPU、内存、I/O设备 进程之间可能需要协作完成任务 进程同步的主要任务 使并发执行的诸进程之间能有

2、效地共享资源和相互合作，从而使程序的执行具有可再现性。: 并发控制示例1 两个用户分别采用存折和储蓄卡对同一帐户余额为5000元同时办理两笔存款业务，分别存入1000元和2000元。 从系统的角度看，有两个进程将同时对储户余额等数据进行修改。 储户余额可能是6000元、7000元或8000元。 缘由：两个进程同时修改同一数据，而没有进行有效控制。 正确的方法：对两个进程进行控制，一次仅允许一个进程全部完成读数据、修改数据、写数据事件以后，才允许别的进程对同一数据的读、修改和写操作。 :并发控制示例2 系统中有两个进程P1、P2和P3，共享一个缓冲区，P1和P2负责向缓冲区中写数据，P3负责取出

3、缓冲区中的数据。某时刻，P1和P2都准备将数据送往缓冲区，考虑可能出现的情况。若计算进程P1、P2的推进速度远远低于P3进程的推进速度，考虑可能出现的情况，反之呢？012345678n-1outin: 进程间的制约关系 间接制约 资源共享互斥 直接制约 进程合作同步 临界资源Critical Resouce ） 必须互斥使用的资源为临界资源。账户账户余额余额: 临界区critical section） 访问临界资源的那段代码称为临界区。 进入区 进程 临界区 退出区: 竞争临界资源引起的问题忙等、饥饿和死锁RP0P1R1P0P1R2RP0P2P1:空闲让进 如临界区空闲，则有进程申请就立即进入

4、。忙则等待 每次只允许一个进程处于临界区。有限等待 保证进程在有限时间内能进入临界区。让权等待 进程在临界区不能长时间阻塞等待某事件。 临界区使用原则互斥条件）:策略软件硬件信号量管程消息传递: 软件方法 由进程通过执行相应的程序指令，实现与其他进程的互斥与同步。难以实现且开销大。 硬件方法 通过屏蔽中断单CPU或采用专门的机器指令控制互斥与同步。硬件约束条件强且可能导致进程饥饿与死锁现象。 操作系统或专门的程序设计语言提供的特别支持 信号量方法已成为通用方法 管程方法 消息传递方法: 软件方法 在进入区设置和检查一些标志来标明是否有进程在临界区。若已有进程在临界区，则在进入区通过循环检查进行

5、等待，进程离开临界区后则在退出区修改标志。 初步设想轮换使用临界区int trun = 0; /共享的全局变量共享的全局变量进程进程P0do while (turn != 0) ; /进入区进入区 进程进程P0的临界区代码；的临界区代码； /临界区临界区 turn = 1; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 while (true)进程进程P1do while (turn != 1) ; /进入区进入区 进程进程P1的临界区代码；的临界区代码； /临界区临界区 turn = 0; /退出区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (t

6、rue)备注：备注：严格轮换，实现了严格轮换，实现了互斥访问。互斥访问。即使在临界区外失即使在临界区外失败也会影响另进败也会影响另进程的执行。程的执行。违反了违反了“空闲让进空闲让进准绳。准绳。忙等。忙等。: 第一次改进设置临界区状态标志boolean flag2 = false, false; /共享的全局变量共享的全局变量进程进程P0do while (flag1) ; /进入区进入区 flag0 = true; /进入区进入区 进程进程P0的临界区代码；的临界区代码； /临界区临界区 flag0 = false; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 whil

7、e (true)进程进程P1do while (flag0) ; /进入区进入区 flag1 = true; /进入区进入区 进程进程P1的临界区代码；的临界区代码； /临界区临界区 flag1 = false; /退出区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (true)备注：备注：忙等忙等违反了违反了“忙则等待准绳，互斥访问未实现忙则等待准绳，互斥访问未实现: 第一次改进设置临界区状态标志续）P0中断P1中断中断临界区临界区: 第二次改进预先表明进入临界区的态度boolean flag2 = false, false; /共享的全局变量共享的全局变量进程进程P

8、0do flag0 = true; /进入区进入区 while (flag1) ; /进入区进入区 进程进程P0的临界区代码；的临界区代码； /临界区临界区 flag0 = false; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 while (true)进程进程P1do flag1 = true; /进入区进入区 while (flag0) ; /进入区进入区 进程进程P1的临界区代码；的临界区代码； /临界区临界区 flag1 = false; /退出区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (true)备注：备注：实现了互斥访问。实现了

9、互斥访问。违反了违反了“空闲让进准绳，可能导致死锁。空闲让进准绳，可能导致死锁。: 第二次改进预先表明进入临界区的态度续）P0中断P1中断: 第三次改进预先表明进入临界区的态度+谦让boolean flag2 = false, false; /共享的全局变量共享的全局变量进程进程P0do flag0 = true; while (flag1) flag0 = false; ； flag0 = true; 进程进程P0的临界区代码；的临界区代码； /临界区临界区 flag0 = false; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 while (true)进程进程P1d

10、o flag1 = true; while (flag0) flag1 = false; ； flag1 = true; 进程进程P1的临界区代码；的临界区代码； /临界区临界区 flag1 = false; /退出区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (true)备注：备注：实现了互斥访问实现了互斥访问非死锁，但可能长时间僵持非死锁，但可能长时间僵持:P0中断P1中断中断中断中断中断中断中断:boolean flag2 = false, false; /共享的全局变量共享的全局变量int turn = 1; /共享的全局变量共享的全局变量进程进程P0do f

11、lag0 = true; /进入区进入区 while (flag1) if (turn = 1) flag0 = false; while (turn = 1) ; flag0 = true; /进入区进入区 进程进程P0的临界区代码；的临界区代码； /临界区临界区 turn = 1; flag0 = false; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 while (true)进程进程P1do flag1 = true; /进入区进入区 while (flag0) if (turn = 0) flag1 = false; while (turn = 0) ; fla

12、g1 = true; /进入区进入区 进程进程P1的临界区代码；的临界区代码； /临界区临界区 turn = 0; flag1 = false; /退出区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (true)给定序号避免给定序号避免“过分谦让过分谦让”:flag0:=trueflag0:=falseturn01turn01flag0:=trueflag1falseP0进入临界区进入临界区退出临界区退出临界区turn:=1flag0:=false其余部分其余部分true进程进程P0do flag0 = true; /进入区进入区 while (flag1) if (t

13、urn = 1) flag0 = false; while (turn = 1) ; flag0 = true; /进入区进入区 进程进程P0的临界区代码；的临界区代码； /临界区临界区 turn = 1; flag0 = false; /退出区退出区 进程进程P0的其它代码的其它代码 /剩余区剩余区 while (true):进程进程P1do flag1 = true; /进入区进入区 turn = 0; /进入区进入区 while (flag0 & turn = 0) ; /进入区进入区 进程进程P1的临界区代码；的临界区代码； /临界区临界区 falg1 = false; /退出

14、区退出区 进程进程P1的其它代码的其它代码 /剩余区剩余区 while (true): 软件方法特点 软件方法始终不能解决“忙等景象，降低系统效率。 采用软件方法实现进程互斥使用临界资源是很困难的，它们通常能实现两个进程的互斥，很难控制多个进程的互斥。 算法设计需要非常小心，否则可能出现死锁，或互斥失败等严重问题。:硬件方法屏蔽中断机器指令Test & SetExchange: 屏蔽中断：避免进程切换，实现互斥访问。 屏蔽中断的缺点 系统无法响应外部请求 无法接受异常，处理系统故障 无法切换进程性能下降 不支持多处理机while (true ) disable interrupt /屏

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

16、: begin 3: if i = 0 then 4: begin 5: i := 1; 6: testset := true; 7: end 8: else testset := false; 9: end :1: program mutualexclusion; 2: const n.; * 进程数 * 3: var bolt: integer； 4: procedure P(i:integer)； 5: begin 6: repeat 7: repeat do no-op until testset(bolt); * 当bolt为0时，进入临界区* 8: ; 9: bolt := 0;

17、10: ; 11: forever 12:end; 13:begin * main program * 14: bolt := 0; 15: parbegin 16: P(1); P(2); . P(n); 17: parend 18:end 例如: 原子性地交换寄存器和内存的值 X86: XCHG1: procedure exchange(var r: register; var m: memory); 2: var temp; 3: begin 4: temp := m; 5: m := r; 6: r := temp; 7: end :1: program mutualexclusion

18、； 2: const n=.; *number of processes* 3: var bolt: integer;4: procedure P(i: integer); 5: var key: integer; 6: begin7: repeat 8: key := 1; 9: repeat exchange(key, bolt) until key=0; 10: ; 11: exchange(key，bolt); 12: ;13: forever 14: end; 15: begin *main program* 16: bolt:= 0; 17: parbegin 18: P(1);

19、P(2); . P(n); 19: parend 20: end 例如:忙等现象饥饿现象死锁现象不足支持多处理机简单，易证明支持多临界区优点: 交通信号灯：红灯停，绿灯行交通信号灯：红灯停，绿灯行: 信号量实现进程互斥的基本原理 两个或多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行阻塞等待），直到它收到一个可以“向前推进的信号被唤醒）。 将实现信号灯作用的变量称为信号量，常定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待该信号量的阻塞进程通常为FIFO）。: 信号量定义type semaphore = record count : integer; qu

20、eue : list of processend;var s: semaphore;: 信号量的两个原子操作：wait(s)和signal(s)，有时也称作P(s)和V(s)。var s: semaphore;wait(s): s.count := s.count 1; if s.count 0 then begin 进程阻塞； 进程进入s.queue队列； end;var s: semaphore;signal(s): s.count := s.count + 1; if s.count = 0 then begin 唤醒队首进程； 将进程从s.queue阻塞队列中移出； end;: 信号量

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

22、阻塞，并插入到s.queue队列排队。 一旦其它某个进程执行了signal(s)原语中的s.count + 1操作后，发现s.count 0，即阻塞队列中还有被阻塞进程，则调用唤醒原语，把s.queue中第一个进程修改为就绪状态，送就绪队列，准备执行临界区代码。 不占不占CPU时间，时间，非非“忙等忙等”: 利用信号量实现互斥的通用模式 1: var mutex semaphore := 1; 2: 3: procedure P(i: integer): 4: begin 5: repeat 6: wait(mutex); 7: ; 8: signal(mutex); 9: ; 10: for

23、ever 11: end 12: 13: parbegin 14: P(1); P(2); .; P(n); 15: parend S:1P0P1S:0P1等待队列P1S:-1: 利用信号量实现前趋关系示例 P1、P2、P3、P4、P5和P6为一组合作进程，其进程前趋图如下所示，试用P、V操作实现这六个进程的同步。P1P2P3P4P5P6: 利用信号量实现前趋关系示例(续1)P1P2P3P4P5P6semaphore s12 = 0; semaphore s13 = 0;semaphore s24 = 0; semaphore s25 = 0;semaphore s36 = 0;semapho

24、re s46 = 0; semaphore s56 = 0;main() cobegin /P1-P6进程并发执行 P1(); P2(); P3(); P4(); P5(); P6(); coend : 利用信号量实现前趋关系示例(续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); : 信号量的类型：依据使用方式互斥信号量资源信号量: 互斥

25、信号量 用于申请或释放资源的使用权，通常初始化为1 资源信号量 用于申请或归还资源，可以初始化为大于1的正整数，表示系统中某类资源的可用个数。: 互斥信号量的取值范围及含义 两个并发进程共享临界资源 s.count=1,表示无进程进入临界区 s.count=0，表示已有一个进程进入临界 s.count= - 1,则表示已有一进程正在等待进入临界区 n个进程共享临界资源 -(n-1)s.count 1 资源信号量的取值范围 依赖于临界资源数量和并发进程数量: 管程的引入 信号量为实施互斥及进程间合作提供一种原始但功能强大且灵活的工具。 信号量的P、V操作可能分散在整个程序中，使用难度高。 管程是

26、一个程序设计语言结构，采用了集中式的进程同步方法，提供了与信号量同样的功能，但更易于控制。 很多程序设计语言都支持管程，如Pascal、Java等。 管程有多种实现方式 使用信号Hoare） 使用通知和广播: 管程的组成 管程的概念 一个管程定义了一个数据结构和能为并发进程所执行在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据。（C. A. R. Hoare & Per Brinch Hansen）局部数据过程初始化序列: 管程的特点 局部数据变量只能被管程的过程访问，任何外部过程都不能访问。 一个进程通过调用管程的一个过程进入管程。 在任何时候，只能有一个进程正在管程执

27、行，调用管程的任何其它进程都被阻塞，以等待管程可用。互斥: 问题 若由于某种原因，一个正在管程中执行的进程必须阻塞，该如何处理？释放管程供其它进程使用同步机制: 管程中的同步机制 管程通过使用条件变量提供对同步的支持。 条件变量包含在管程中，只能在管程中访问。 操作条件变量的两个函数 cwait(c) 调用进程的执行在条件c上阻塞，管程可供其它进程使用。 csignal(c) 恢复某个阻塞进程，若不存在阻塞进程，则什么都不做。: 管程的结构局部于管程的数据局部于管程的数据条件变量条件变量过程过程1过程过程m初始化代码初始化代码 条件条件c1wait （c1)条件条件cnwait(cn)紧急队列

28、紧急队列signal等待进入管程等待进入管程的进程队列的进程队列入口入口出口出口管程等待区管程等待区: 经典同步问题生产者/消费者理发师读/写者哲学家就餐: 荷兰计算机科学家E. W. Dijkstra把广义同步问题抽象成一种“生产者与消费者问题” Producer Consumer Problem Bounded-Buffer Problem: 生产者与消费者是一个广义的概念，可以代表一类具有相同属性的进程如游戏中的金币、血）。 生产者和消费者进程共享一个大小固定的缓冲区。 一个或多个生产者生产数据，并将生产的数据存入缓冲区。 一个或多个消费者从缓冲区中取数据，即消费数据。: 假设缓冲区的大

29、小为n存储单元的个数），它可以被生产者和消费者循环使用。 分别设置两个指针in和out，指向生产者将存放数据的存储单元和消费者将取数据的存储单元。123N-20N-1inout使用方向供应方向: 生产者/消费者模型 缓冲区：固定大小 生产者：满则等待，空则填充 消费者：空则等待，有则获取P1P2PnC1C2Cninout: 各个生产者、消费者独立自主向前推进 指针in和out初始化指向缓冲区的第一个存储单元。 生产者通过in指针向存储单元存放数据，一次存放一条数据。 每存放一条数据后，in指针向后移一个位置。 消费者从缓冲区中逐条取走数据，一次取一条数据，相应的存储单元变为“空”。 每取走一条

30、数据后，out指针向后移一个存储单元位置。 试想，将会产生什么结果？: 生产者/消费者必须互斥 生产者和消费者不能同时读/写一个存储单元 多个生产者不能同时写缓冲区 多个消费者不能同时取缓冲区数据 生产者/消费者必须同步 生产者不能向满缓冲区写数据 消费者也不能在空缓冲区中取数据:(a) (a) 生产者生产者(b) (b) 消费者消费者无无阻塞阻塞等待资源等待资源被唤醒被唤醒否否被唤醒被唤醒是否有数是否有数据单元据单元消费数据消费数据能否能否可用可用取一条数据取一条数据有有是是归还使用权归还使用权空单元加空单元加1 1唤醒一个生产者唤醒一个生产者阻塞阻塞等待资源等待资源阻塞阻塞等待使用权等待使

31、用权被唤醒被唤醒否否被唤醒被唤醒是否有空是否有空存储单元存储单元生产一条数据生产一条数据能否能否可用可用有有存入一条数据存入一条数据归还使用权归还使用权是是数据单元加数据单元加1 1唤醒一个消费者唤醒一个消费者无无阻塞阻塞等待使用权等待使用权:program producer_consumer;const sizeofbuffer =; /* 缓冲区大小缓冲区大小 */var s: semaphore(:= 1); /* 互斥信号量互斥信号量s，初始化为，初始化为1 */ n : semaphore(:= 0); /* 资源信号量资源信号量n，数据单元，初始化为，数据单元，初始化为0 */ e

32、 : semaphore(:= sizeofbuffer); /* 资源信号量资源信号量e，空存储单元，空存储单元 */procedure producer ; procedure consumer ;begin begin repeat repeat 生产一条数据生产一条数据; wait(n); wait(e); wait(s); wait(s); 取一条数据；取一条数据； 存入一条数据存入一条数据; signal(s); signal(s); signal(e); signal(n)； 消费数据；消费数据； forever forever end; end;begin /* 主程序主程序

33、*/ parbegin producer ; consumer ; parendend.: 留意(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) 同一进程中的多对wait与sign

34、al语句只能嵌套，不能交叉?Consumer：Producer：wait(e) ;wait(s);存入一条数据;signal(n);signal(s);wait(s);wait(n);取一条数据;signal(s);signal(e);: 留意(3) 对于同一个信号量的wait与signal操作，既可以出现在同一个进程中，也可以出现在不同进程中。Consumer：Producer：wait(e) ;wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);: 留意(4) 对任何信号量的wait与si

35、gnal操作必须配对。 Consumer：Producer：wait(e) ;wait(s);存入一条数据;signal(s);signal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);: 留意(5) wait与signal语句不能颠倒顺序，wait语句一定先于signal语句？(应为：在进入临界区前必须先执行wait操作，退出临界区后必须执行signal操作。对于同一信号量而言，既有可能先执行wait操作，也有可能先执行signal操作。)Consumer：Producer：wait(e) ;wait(s);存入一条数据;signal(s);si

36、gnal(n);wait(n);wait(s);取一条数据;signal(s);signal(e);: 生产者/消费者问题的管程解决方法monitor boundedbuffer;char buffern; int nextin, nextout; int count;cond notfull, notempty;void append(char x) if (count = N) cwait(notfull); buffernextin = x; nextin = (nextin + 1) % N; count+; csignal(notmpty);void take(char x) if

37、(count = 0) cwait(notemptyl); x = buffernextout; nextout = (nextout + 1) % N; count-; csignal(notfull); nextin = 0; nextout = 0; count = 0; void producer() char x; while (true) produce(x); append(x); void consumer char x; while (true) take(x); consume(x); : 生产者/消费者问题示例 三个进程P1、P2、P3互斥使用一个包含NN0个单元的缓冲区

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

39、pty。:semaphore mutex = 1; /缓冲区操作互斥信号量缓冲区操作互斥信号量semaphore odd = 0, even = 0; /奇数、偶数进程的同步信号量奇数、偶数进程的同步信号量semaphore empty = N; /空缓冲区单元个数信号量空缓冲区单元个数信号量P1() while (true) number = produce(); P(empty); /递减空缓冲区的单元个数递减空缓冲区的单元个数 P(mutex); /互斥访问缓冲区互斥访问缓冲区 put(); V(mutex); /恢复访问缓冲区恢复访问缓冲区 if (number % 2 = 0) /为

40、偶数为偶数 V(even); /允许取偶数允许取偶数 else /为奇数为奇数 V(odd); /允许取奇数允许取奇数 :P2() while (true) P(odd); /互斥取奇数互斥取奇数 P(mutex); /互斥访问缓冲区互斥访问缓冲区 getodd(); V(mutex); /恢复访问缓冲区恢复访问缓冲区 V(empty); /递增空缓冲区的单元个数递增空缓冲区的单元个数 countodd(); :P3() while (true) P(even); /互斥取偶数互斥取偶数 P(mutex); /互斥访问缓冲区互斥访问缓冲区 geteven(); V(mutex); /恢复访问缓

41、冲区恢复访问缓冲区 V(empty); /递增空缓冲区的单元个数递增空缓冲区的单元个数 counteven(); main() /* 主程序主程序 */ cobegin P1() ; P2() ; P3(); coend: 问题描述 多个进程访问一个共享数据区 为数据库、文件、内存区及一组寄存器等的数据访问问题建立了一个通用模型。其中若干读进程只能读数据，若干写进程只能写数据。 例如联网售票系统、12306 在该系统中，数据的查询和更新非常频繁，不可避免会出现多个进程试图查询或修改读/写其中某一条数据的情形。:读者/写者进程满足的条件允许多个读者进程可以同时读数据；不允许多个写者进程同时写数据

42、，即只能互斥写数据；若有写者进程正在写数据，则不允许读者进程读数据互斥读写。 : 如何控制读者和写者？ 采用生产者/消费者问题解决方法 严格互斥任何读者和写者进程，可以保证数据更新操作的正确性。 允许同时读，但不允许同时写、读写。: 读者和写者问题描述图读者/写者问题描述三种角色读进程写进程共享数据三个条件同时读互斥写互斥读写: 读者和写者问题解决策略读者/写者问题解决策略严格互斥任意两个进程互斥任意两个写者进程，读、写进程读者优先写者优先公平优先: 读者优先 一旦有读者正在读数据，则允许随后的读者进入读数据。 只有当全部读者退出，才允许写者进入写数据。 导致写者饥饿 读者优先的变量设置 ws

43、em：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writers readcount：统计同时读数据的Readers个数 mutex：对变量readcount互斥算术操作:void reader() while (1) P(mutex); readcount+; if (readcount=1) P(wsem); V(mutex); READ; P(mutex); readcount-; if (readcount=0) V(wsem); V(mutex); void writer() while (1) P(wsem); WRITE; V(ws

44、em); int readcount=0；semaphore mutex = 1, wsem=1;序列：R R RW W WR WR R WR W R RW W RW R R W: 公平优先 写过程中，若其它读者、写者到来，则按到达顺序处理。 公平优先的变量设置 wsem：互斥信号量，用于Writers互斥Writers和Readers，以及第一个Reader互斥Writers readcount：统计同时读数据的Readers个数 mrc：对变量readcount互斥算术操作 wrsem：互斥信号量，确定Writer 、Reader请求顺序:int readcount=0, semaphor

45、e mrc=l, wrsem=1, wsem=l;void reader() 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); void writer() while (true) P(wrsem); P(wsem); WRITE; V(wsem); V(wrsem); 序列：R, R, R, W, R, R, R, W, R:

46、写者优先 只要有一个写者申请写数据，则不再允许新的读者进入读数据。 解决了写者饥饿问题，但降低了并发程度，系统的并发性能较差。 写者优先的变量设置 rsem：互斥信号量，当至少有一个写者申请写数据时互斥新的读者进入读数据 writecount：用于控制rsem信号量 mwc：对变量writecount互斥算术操作:int readcount = 0, writecount = 0;semaphore mrc=l, mwc= 1, wsem=1, rsem=l;void reader( ) while (1) P(rsem); P(mrc); readcount+; if (readcount

47、=1) P(wsem); V(mrc); V(rsem)； READ; P(mrc); readcount-; if (readcount =0) V(wsem); V(mrc); void writer( ) 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); 序列：序列：3. W R R W2.W R R4.R R R R R W1. R R W R

48、 :int readcount=0,writecount=0; semaphore mrc=l, mwc= 1,z=1,wsem=1,rsem=l;void reader( ) 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); void writer( ) while (1) P(mwc); writecount+; if (write

49、count =1) P(rsem); V(mwc); P(wsem); WRITE; V(wsem); P(mwc); writecount-; if (writecount=0) V(rsem); V(mwc); R R R R R W: 写者优先的思考 教材中描述“z信号量的好处是：限制了rsem阻塞队列的长度”，“无法唤醒全部阻塞读者” P(z)和P(rsem)能否互换位置？: 理发店有一位理发师、一把理发椅和5把供等候理发的顾客坐的椅子。如果没有顾客，则理发师睡觉。当一个顾客到来时，他必须叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他就坐下来等。如果没有空椅子，他

50、就离开。: 理发师和顾客工作流程:void customer() P(mutex); /互斥互斥waiting变量的操作变量的操作 if (waiting 6) /有空椅子则坐下等待有空椅子则坐下等待 waiting+; /等待顾客数增等待顾客数增1 else 分开；分开； V(mutex); /允许允许waiting变量的操作变量的操作 P(wchair); /找一个空椅子坐下找一个空椅子坐下 P(bchair); /再找理发椅坐下再找理发椅坐下 V(wchair); /允许其他人坐空椅子允许其他人坐空椅子 V(ready); /该顾客准备好了该顾客准备好了 P(finish); /等待理发

51、师完成理发等待理发师完成理发 V(bchair); /离开理发椅离开理发椅 P(mutex); /互斥互斥waiting变量的操作变量的操作 waiting-; /等待顾客数减等待顾客数减1 V(mutex); /允许允许waiting变量的操作变量的操作int waiting = 0; /等待的顾客等待的顾客,含正在理发的人数含正在理发的人数semaphore mutex = 1; /waiting的互斥信号量的互斥信号量semaphore bchair = 1; /理发椅的个数理发椅的个数semaphore wchair = 5; /空椅子的个数空椅子的个数semaphore ready

52、= 0; /是否有顾客准备好是否有顾客准备好semaphore finish = 0; /理发师是否完成理发理发师是否完成理发main() cobegin baber(); customer(); coend void baber() /理发师进程理发师进程 while (true) P(ready); /有顾客准备好了有顾客准备好了 理发；理发； V(finish); /允许其他顾客理发允许其他顾客理发 : 某银行提供一个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服

53、务。顾客和营业员的活动过程描述如下： cobegin process 顾客i从取号机上获取一个号码；等待叫号；获取服务； process 营业员while (true) 叫号；为顾客服务； 请添加必要的信号量和P、V或wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完成的过程，说明信号量的含义并赋初值。:semaphore mutex = 1; /互斥使用取号机的信号量互斥使用取号机的信号量semaphore empty = 10; /空座位的数量信号量空座位的数量信号量semaphore full = 0; /已占座位的数量信号量已占座位的数量信号量semaphor

54、e service = 0; /等待叫号信号量等待叫号信号量process 顾客顾客i P(empty); P(mutex); 从取号机获得一个号；从取号机获得一个号； V(mutex); V(full); P(service); /等待叫号等待叫号process 营业员营业员 while (true) P(full); V(empty); V(service); /叫号叫号 为顾客服务为顾客服务; : 进程通信(Inter Process Communication, IPC) 进程之间的信息交换 进程通信方式 低级通信 以信号、信号量作为通信工具，由于其所交换的信息量少而被归结为低级通信。

55、 高级通信 指用户可直接利用操作系统所提供的一组通信命令， 高效地传送大量数据的一种通信方式。: 电子邮件的发送与接收过程发送进程发送进程接收进程接收进程邮件服务器邮件服务器接收进程接收进程发送进程发送进程终端用户终端用户邮件邮件邮件邮件发送进程发送进程接收进程接收进程邮件服务器邮件服务器接收进程接收进程发送进程发送进程终端用户终端用户邮件邮件:共享存储区消息传递: 共享数据结构程序员控制） 共享存储区操作系统控制） 正文数据栈共享存储区正文数据栈进程A的虚空间内存空间进程B的虚空间AABB: 数据交换以格式化的消息为单位 消息的一般格式消息类型消息类型目的端地址目的端地址源端地址源端地址消息

56、长度消息长度控制信息控制信息消息内容消息头消息头消息体消息体: 消息传递的同步 两条通信原语 Send(destination,message) Receive(source,message) 消息传递的同步 当发送进程调用Send原语发送消息时，若没有空闲的消息缓冲区，则发送进程塞阻。 当接收进程调用Receive原语接收消息时，如果没有消息可接收，则接收进程阻塞，直到一条消息到达。 : 三种同步方式 阻塞发送阻塞接收 不阻塞发送阻塞接收 不阻塞发送不阻塞接收: 不阻塞发送 如打印服务，每当进程需要打印时，都可以以消息形式发出请求，然后继续执行，无须阻塞等待打印完成。 “不阻塞发送方式容易导

57、致消息的无限发送。 必须在程序中考虑让接收进程发回应答消息，证实其是否收到消息增加了并发程序的设计难度。 阻塞接收 并发程序设计中常采用该方式。 若消息丢失，或发送进程发送消息之前失败，则接收进程将永久阻塞。 : 消息传递中的寻址 寻址方式：直接寻址和间接寻址。 若采用直接寻址，send原语中必须指定目标进程的具体标识号 receive原语中的source地址有两种处理方法： 接收进程显式地指定发送方进程标识号，这就要求接收进程必须事先清楚将接收哪个进程发来的消息。 接收进程可以不必指定接收哪个进程的消息: 间接寻址 采用间接寻址传递消息时，消息不再从发送方直接发送到接收方，而是通过发送进程与

58、接收进程共享的一个数据结构进行中转，该数据结构通常称为邮箱。 发送进程将消息发送到指定的邮箱中，接收进程从邮箱中接收消息。 : 邮箱 不限制进程数，允许多个发送进程向邮箱发送消息，同时，也允许多个接收进程从邮箱接收消息邮箱邮箱R1SnS1Rn发送进程发送进程接收进程接收进程: 互斥 不允许两个或两个以上的进程同时进入临界区 如何利用消息传递实现互斥？ 多个并发执行的发送进程和接收进程共享一个邮箱box，且box的初始状态为仅包含一条空消息； 采用“不阻塞发送，阻塞接收方式传递消息； 若邮箱中存在一条消息，则允许一个进程进入临界区。 若邮箱为空，则表明有一个进程位于临界区，其它试图进入临界区的进

59、程必须阻塞。 只要保证邮箱中最多只有一条消息，就能保证只允许一个进程进入临界区，从而实现进程互斥使用临界资源。:void P(int i) message msg; while (true) receive(box, msg); /* 从邮箱接收一条消息从邮箱接收一条消息 */ ; send(box, msg); /*将消息发回到邮箱将消息发回到邮箱*/ /* program mutualexclusion */const int n = /* 进程数进程数 */;void main() create_mailbox(box); /* 创建邮箱创建邮箱 */ send(box, null);

60、/* 初始化，向邮箱发送一条空消息初始化，向邮箱发送一条空消息 */ parbegin(P(1), P(2), , P(n);: 生产者生产者/消费者模型消费者模型 缓冲区：固定大小缓冲区：固定大小 生产者：满则等待，空则填充生产者：满则等待，空则填充 消费者：空着等待，有则获取消费者：空着等待，有则获取P1P2PnC1C2Cninout: 如何采用消息传递的方法实现生产者/消费者同步？ 使用capacity条消息，其作用类似于缓冲区的大小； capacity条消息的初始状态为“空音讯，类似于缓冲区的初始状态为空未填充生产数据）； 生产者生产一条数据后，取一条“空音讯，并发送回一条填充了数据的消息； 消费者消费一条