《操作系统教程 教学课件 ppt 作者 柯丽芳 第5章-2》由会员分享，可在线阅读，更多相关《操作系统教程 教学课件 ppt 作者 柯丽芳 第5章-2（33页珍藏版）》请在金锄头文库上搜索。
1、5.2 用信号量机制 实现进程的同步与互斥,5.2.1 信号量机制 5.2.2 利用信号量机制实现进程互斥 5.2.3 利用信号量机制解决进程的同步 5.2.4 经典的同步与互斥问题,5.2.1信号量机制,1.信号量的含义 2.P、V操作的定义 3.信号量和P、V操作的物理意义,1.信号量的含义,操作系统中，信号量是表示物理资源的实体，它是一个与队列有关的整型变量。实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,信号量按其用途分为两类：,公用信号量：与公用信号量联系的一组并发进程均可对它实施P、V操作。 私有信号量：只允许信号量的拥有者进程对它
2、实施P操作，与信号量的拥有者进程合作的进程对它实施V操作。,2.P、V操作的定义 设S为信号量，q为对资源S操作的进程，Q为S的等待队列。,（1）P操作原语P(S)可描述为： S=S-1； 若S0，则调用P（S）的进程q继续运行； 若S0，则调用P（S）的进程q将进入阻塞状态，并放入S的等待队列Q中。 （2）V操作原语V(S)可描述为： S=S+1； 若S0，则调用V（S）的进程q继续运行； 若S0，则从S的等待队列中唤醒头一个进程，然后，调用V（S）的进程q继续运行。,3.信号量和P、V操作的物理意义（1）,信号量（用S表示）是代表资源的实体，是一个与进程队列Q有关的整形变量，除信号量的非负
3、初值外，信号量的值只能由P操作和V操作来改变。 操作系统利用信号量实施对进程的控制和对资源的管理。,3.信号量和P、V操作的物理意义（2）,信号量S的取值表示系统中某类资源的数目。 当S0时： 其值表示系统中当前可用的某类资源数量； 当S=0时： 表示系统中当前已无某类资源可用； 当S0时： 其绝对值表示系统中因请求该类资源而被阻塞的进程数量或登记排列在该信号量s队列之中等待的进程个数。,3.信号量和P、V操作的物理意义（3）,通常，P操作意味着请求一个资源，因此描述为S=S-1；V操作意味着释放一个资源，因此描述为S=S+1。 在一定条件下（S=0时），P操作的结果将会引起进程阻塞；在一定条
4、件下（S0时）,V操作的结果可以唤醒某个阻塞进程；,3.信号量和P、V操作的物理意义（4）,P操作原语为请求资源而设，V操作原语为释放资源而设； P操作即可充当资源申请原语的作用，也可以充当进程阻塞原语的作用； V操作即可充当资源释放原语的作用，也可以当作进程唤醒原语的作用； 在整个系统中，P、V操作必须成对出现。,5.2.2 利用信号量机制 实现进程互斥的模型,设n个进程P1，P2， ，Pn的相关临界区分别为CS1，CS2，CSn，只要在每个进程的临界区两端放上P、V操作原语即可实现临界区互斥。 假设信号量S的初值为1，则，互斥的模型如下： Pi（i=1,2,3,n） P（S） Csi(临界
5、区) V（S） ,利用信号量机制实现进程互斥的模型：,s : semaphore; s := 1; cobegin process Pi begin P(s); 临界区； V(s); end; coend;,例5-5（互斥问题）,民航售票系统有n个售票处，各个售票处均需访问公共数据区存放的现有票数。试用信号量和P、V操作控制n个并发的售票进程的正确执行。 分析：假定公共数据区Aj(j=1,2,m)存放X月X日X次航班的现有票数，那么，只要把公共数据区Aj当作临界资源对待，n个并发售票进程互斥访问临界区即可。,信号量和PV操作解决机票问题,Var A : ARRAY1m OF integer;
6、S : semaphore; S:= 1; cobegin process Pi（I=1,2,n) var Xi:integer; begin L1: 按旅客定票要求找到Aj； P(S) Xi := Aj; if Xi=1 then begin Xi:=Xi-1; Aj:=Xi; V(S);输出一张票； end; else begin V(S);输出票已售完； end; goto L1; coend;,5.2.3 利用信号量机制 解决进程的同步模型,设信号量S的初值为0，P1与P2同步的模型如下：,说明：进程P1在L1点完成了P2等待的事件，调用V（S）操作； 进程P2在L2点检测事件是否发生
7、调用P（S）操作。,例5-6：(同步问题）,设3个合作进程P1，P2，P3。要求P1和P2可以并发执行，但P1，P2结束以后，P3才可以执行。用信号量机制实现P1，P2，P3的同步。 为了描述方便，可以用一个图来表示进程集合的执行次序。其中S表示系统中某一任务的开始，F表示系统中某一任务的完成。如图5.5所示。用信号量机制实现P1，P2，P3的同步描述如下：,Begin S1=S2=0; Cobegin Process P1 Begin do all work V(S1) End Process P2 Begin do all work V(S2) End Process P3 Begin P
8、(S1) P(S2) do all work End Coend End,5.2.4 经典的IPC问题,1.生产者-消费者问题 有界缓冲区问题的建模 2.读者-写者问题 数据库互斥访问问题的建模 3.理发师问题 CS模式进程同步问题的建模 4.哲学家进餐问题 多进程同步导致死锁问题的建模,进程通信（IPC）,进程间的关系 完全无关（异步）：不同进程间无任何关联 使用共享数据（互斥）：应有效保护各个进程的正确运行 存在先后顺序（同步）：应保证进程运行顺序的正确 进程通信需要考虑的问题 如何实现两个进程间的信息传递 如何协调两个或者多个进程之间的互斥和同步情况 问题难点分析 金字塔法则：20的简单
9、问题80的困难问题 难点：临界区的保护,进程通信,IPC问题分析,多进程分时运行的临界情况 正常情况下不存在任何问题 临界情况下将产生不可预知的后果（墨菲法则） 解决的关键 保持进程之间正确的运行顺序 OS与普通应用程序设计都需要考虑 解决机制：提升系统运行的稳定性,进程通信,问题建模,建模原因 用抽象、独立的事例描述现实世界中大量存在的同类问题 对问题进行清晰界定，进而给出合理的解决办法 解决现实问题时，合理的套用模型，提高解决的效率 建模要素 问题清晰定义 案例清晰描述 解法清晰实现,进程通信,问题建模的目标,进程通信,模 型,方 法,技 术,自然世界,现实问题,改,造,世,界,界,世,识
10、,认,描述问题,根据对问题的描述提出解决问题的方法，搭建系统,结合现实需要，基于现有的各种方法，实现处理目标,1.生产者-消费者问题,生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。 在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。 解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,生产者消费者问题描述,一个有限空间的共享缓冲区，负责存放货物 生产者向缓冲区中放物品，缓冲区满则不能放 消费者从缓冲区中拿物品，缓冲区空则不能拿,进程通信,生产者-消费者问题表述,有m个生产者和k个消费者，连接在一个有n个单
11、位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,生产者与消费者问题的抽象化模型,生产者 进程Pi,信号量的设置 Mutex=1 缓冲区是临界资源 Empty=n 缓冲区中的空单元数目 Full=0 缓冲区中的产品数目,信号量机制解决生产者消费者问题,互斥信号量 mutex：防止多个进程同时进入临界区 同步信号量 empty和full：保证事件发生的顺序 缓冲区满时，Producer停止运行 缓冲区空时，Consumer停止运行 概念差别互斥与同步（并发的两个要素） 互斥：保护临界
12、区，防止多个进程同时进入 同步：保证进程运行的顺序合理,进程通信,生产者消费者问题的几种情况,1个生产者、1个消费者共享1个单元缓冲区 1个生产者、1个消费者共享n个单元缓冲区 m个生产者、k个消费者共享n个单元缓冲区,1个生产者、1个消费者共享1个单元缓冲区的解,var B : integer; empty:semaphore; /* 可以使用的空缓冲区数 */ full:semaphore; /* 缓冲区内可以使用的产品数 */ empty := 1; /* 缓冲区内允许放入一件产品 */ full := 0; /* 缓冲区内没有产品 */ cobegin Process producer
13、 process consumer begin begin L1: L2: Produce a product; P(full); P(empty); Product:= B; B := product; V(empty); V(full); Consume a product; Goto L1; Goto L2; end; end; coend,1个生产者、1个消费者共享n个单元缓冲区的解,var B : array0n-1 of integer; empty:semaphore; /* 代表缓冲区 */ full:semaphore; /*代表缓冲区内的产品 */ empty := n;
14、/* 缓冲区的空单元数*/ full := 0; /* 缓冲区内产品数 */ in:= out:=0 cobegin Process producer process consumer begin begin L1:produce a product; L2:P(full); P(empty); Product:= Bout; Bin := product; out:=(out+1) mod n; in:=(in+1) mod n; V(empty); V(full); Consume a product; Goto L1; Goto L2; end; end; coend,m个生产者、k个消
15、费者、共享n个单元缓冲区,In=(in+1)mod n out=(out+1)modn,m个生产者、k个消费者、共享n个单元缓冲区的解,var B : array0n-1 of integer; empty:semaphore:=n; /* 可以使用的空缓冲区数 */ full:semaphore:=0; /* 缓冲区内可以使用的产品数 */ mutex :semaphore:=1; in , out:integer:= 0; /* 放入/取出缓冲区指针*/ cobegin process producer_I(I=1,2,m) process consumer_j (j=1,2,k) Begin begin L1:produce a product; L2:P(full); P(empty); P(mutex); P(mutex); Product:= Bout; Bin := product; out:=(out+1) mod n; in:=(in+1) mod n; V(mutex); V(mutex); V(empty); V(full);
