进程管理三互斥和同步二计算机软件及应用it计算机专业资料ppt课件

1 2.3 进程互斥和同步 复习 临界资源、临界区定义， 同步机制遵循的原则 记录型的信号量内部成员 的意义 signal wait操作含义 怎样利用信号量解决进程之间的前趋关系 ？ 2 临界区(critical section)：进程中访问临界资 源的一段代码。 进入区(entry section)：在进入临界区之前 ，检查可否进入临界区的一段代码。如果 可以进入临界区，通常设置相应“正在访问 临界区“标志 退出区(exit section)：用于将“正在访问临界 区“标志清除。 剩余区(remainder section)：代码中的其余 部分。 返回 3 2.3.1 基本概念-临界区 2、临界区：每个进程中访问临界资源的那段 程序段称为临界区（临界段）。 4 2.3.1 基本概念-临界区的访问过程 临界区的访问过程 返回 进入区 退出区 临界区 5 同步机制应遵循的准则 空闲让进：其他进程均不处于临界区； 忙则等待：已有进程处于其临界区； 有限等待：等待进入临界区的进程不能“ 死等“； 让权等待：不能进入临界区的进程，应释 放CPU（如转换到阻塞状态） 返回 6 2.3.2 信号量(semaphore) 需要一个地位高于进程的管理者来解决公有资源的使用问题。 OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提 供的管理公有资源的有效手段。 1965年，由荷兰学者Dijkstra提出（所以P、V分别 是荷兰语的test(proberen)和increment(verhogen)）， 是一种卓有成效的进程同步机制。 信号量是一个被保护的变量，被初始化之后，只有 wait操作、signal操作才能访问和改变它的值。信 号量代表可用资源实体的数量。 wait操作、signal操作又称为P、V操作。它们都是 原子操作（原语） 7 2.3.2 信号量(semaphore) 一、整型信号量 整型信号量是表示共享资源状态且只能由特 殊的原子操作改变的整型量。 想法：定义一个整型变量，用整形变量值来标记资 源 使用情况：如整型量0,说明有可用资源;整型量 0说明资源忙，进程必须等待。 对于一次只允许一个进程访问的临界资源 ，可定义一个用于互斥的整型信号量，并初始化为1 。 8 2.3.2 信号量(semaphore) 一、整型信号量 利用整型信号量实现互斥方法： 想法：为必须互斥访问的CS定义一个互斥信 号量mutex，初始值为1，然后将CS放入 wait(mutex)和signal(mutex)之间，当CS可 访问时，wait(mutex)才能正常结束使进程 进入CS。 9 三、利用信号量来协调进程执行的顺序 例1：P1、P2两个进程， P1 中有语句S1，P2 中有语句S2，要求S2必须在S1结束后执行 ,为此，设置一个信号量S,初始值为0。 parbegin P1： S1; Signal(s); P2: Wait(s); S2 ; parend 10 三、利用信号量来描述前趋关系 例2：有P1，P2两个进程：S1，S2，SS6分 别是P1、P2中的语句，我们要求它们的执 行顺序如下图所示 : 11 f S1 S2 S5S4 S3 S6 g b d a c e 12 利用整型信号量来描述前趋关系-例2 Semaphore a,b,c,d,e,f,g=0,0,0,0,0,0; cobegin begin s1; signal(a); signal(b); end; begin wait(a); s2;signal(c); signal(d); end; begin wait(b); s3;signal(g); end; begin wait(c); s4;signal(e); end; begin wait(d); s5;signal(f); end; begin wait(e); wait(f); wait(g); s6; end. coend 13 记录型信号量和wait、signal原语 信号量是一个确定的二元组（value, list）， value 是一个具有非负初值的整型变量，list 是一个初始状态为空的队列。 value代表资源的实体。在实际应用中应准确地说 明s的意义和初值; 初始化指定一个非负整数值，表示空闲资源总数（又称为“资源信号量 ”）若为非负值表示当前的空闲资源数，若为负值其绝对值表示当 前等待临界区的进程数 List：每个信号量的相关队列，表示因得不到临界资 源而阻塞的进程，其初始状态为空。 14 2.3.2.1 信号量和wait、signal原语 信号量只能通过初始化和两个标准的原语来访问 作为OS核心代码执行，不受进程调度的打断 在实际操作系统中，一般情况下是由机器硬件提供P、V操 作的指令，当然是原子操作，若机器不提供P、V操作的指 令，则操作系统提供P、V操作原语。 信号量的形式化定义： typedef struct int value; struct process_control_block *list; semaphore; 1. wait原语 15 wait(semaphore *S) S-value-； /表示申请一个资源; if S-valuelist)； /如果没 有空闲资源，调用进程进入和信号量S相关的等 待队列 s.L; 阻塞调用wait 的进程 2. V原语(signal) procedure signal(S) var S: semaphore； begin S.value:=S.value+1； /表示释放一个资源 ； if S.value=1 i = ti时，表示可用资源数量大于ti，才分配资源， 否则便不予分配），占用值为di（用于信号量的增减 ，即 分配资源时Si = Si di 释放资源时Si = Si + di） Swait(S1, t1, d1; .; Sn, tn, dn); Ssignal(S1, d1; .; Sn, dn); 一般信号量集用于同时需要多种资源、每种占用的数目不同、 且可分配的资源还存在一个临界值时的处理； 46 Swait(S1, S2, , Sn)/P原语； while (TRUE) if (S1 =1 i =1时，允许多个进程进入临界区； 当S=0时，禁止任何进程进入临界区； 一般“信号量集“未必成对使用Swait和Ssignal ：如：一起申请，但不一起释放； 49 2. 读者写者问题(the readers-writers problem) 问题描述 写者向数据区放 数据，读者从数 据区获取数据 多个读者可同时 读取数据 多个写者不能同 时写数据 读者和写者的控 制策略变化多端 50 读者写者问题的信号量解法 互斥关系分析 读者和写者不能同时进入共享数据区 多个写者不能同时进入共享数据区 多个读者可以同时进入共享数据区 同步关系分析 读者进入缓冲区，写者必须等待 写者进入缓冲区，读者必须等待 三种类型： 读者优先：一旦有读者进入，则后续读者均可进入 合理顺序：读者在先来的写者之后 写者优先：只要有写者等待，则后续读者必须等待 写-写互斥 读-写互斥 51 当读者进程到来时，三种情况： 1）无读者、写者：新读者可以读 2）有写者等待，但有其它读者正在读：新读者也 可以读 3）有写者写：新读者等 当写者进程到来时，三种情况： 1）无读者、其他写者：新写者可以写 2）有读者：新写者等待 3）有其它写者：新写者等待 读-写互斥 读-写互斥 写-写互斥 读-写互斥 读-写互斥 写写互斥： 互斥信号量 Wmutex 怎样判断有没有读者在读？ 52 增加一个公共变量Readcount，表示当前有 几个读者进程在读。 新来一个读者进程，Readcount加1； 撤销一个读者进程，Readcount减1； 第一个读者：阻塞所有写者进程；允许其他读者进程执行 。 最后一个读者：唤醒可能的写者进程。 Readcount成为临界资源，必须互斥访问： 增加互斥信号量Rmutex 53 采用信号量机制： 两种进程： Reader、Writer 两个信号量 Wmutex表示读者和写者之间互斥，初值是1。 公共变量Readcount表示“正在读”的进程数，初值是0； Rmutex表示读者对Readcount的互斥操作，初值是1。 Readcount0时允许写 分析小结 54 wait(rmutex); If readcount=0 then wait(wmutex); Readcount:=readcount+1; signal(rmutex); 执行读取操作 wait(rmutex); Readcount:=readcount-1 if readcount=0 then signal(wmutex); signal(rmutex); 读者-写者问题 读者部分 第一个读者要阻塞 所有后来的写者 最后一个读者要唤 醒所有阻塞的写者 55 wait(wmutex); 执行写操作 signal(wmutex); 写者部分 56 增加限制条件，即同时读取的读者数不能超过RN L,mx:=RN,1 信号量集： Swait(S,d,t); Ssignal(S,d) S为信号量，d为需求量，t为下限值 写者： Swait(mx,1,1;L,RN,0); 执行写操作 Ssignal(mx,1); 读者-写者问题 一般“信号量集“机制 读者： Swait(L,1,1); Swait(mx,1,0); 执行读取操作 Ssignal(L,1); If（L=1）L=L- 1; If（mx=1） mx=mx; If（mx=1 L=L; 57 3. 哲学家进餐问题 (the dining philosophers problem) 问题描述：（由Dijkstra首先提出并解决）5个 哲学家围绕一张圆桌而坐，桌子上放着5支筷 子，每两个哲学家之间放一支；哲学家的动作 包括思考和进餐，进餐时需要同时拿起他左边 和右边的两支筷子，思考时则同时将两支筷子 放回原处。如何保证哲学家们的动作有序进行 ？如：不出现相邻者同时要求进餐；不出现有 人永远拿不到筷子； 58 59 1.利用记录型信号量机制解决 2.利用AND型信号量机制解决 2.4.2哲学家就餐问题 60 哲学家就餐问题 问题分析： 筷子是临界资源：每根有多于一个哲学家要用 ，而且同时只能有一个哲学家使用 5根筷子可以用5个信号量表示。形成信号量数 组： var chopstick:array0,4of semaphore； 所有信号量初值为1，表示未被使用。 61 哲学家就餐问题解决方法 第i位哲学家的活动描述为： Repeat wait(chopsticki); wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1)mod 5); think; Until false; parbegin philosopher (0)； philosopher (1)； philosopher (2)； philosopher (3)； philosopher (4)； parend 62 不足之处及改进方法 可能产生死锁： 五位哲学家同时饥饿，各自拿起左边的筷子时，会使 得所有信号量的值为0，再试图拿起右边的筷子时，都 将拿不到筷子。 解决死锁的方法： 至多允许四个哲学家同时进餐。 仅当哲学家的左右两支筷子均可用时，才进餐。（用 AND信号量机制解决哲学家进餐问题。） 奇数号哲学家先拿左边的筷子，偶数号哲学家先拿右 边的筷子。 63 AND型信号量机制解决哲学家 就餐问题 要求哲学家同时获得两根筷子，否则一根也不拿。 var chopstick:array0,4of semaphore:=(1,1,1,1,1); /第i位哲学家进程： Repeat think; Sswait(chopstick(I+1)mod 5),chopstickI); Eats; Ssignal(chopstick(I+1)mod 5),chopstickI); until false; 64 思考： 用其余两种思路，怎样解决哲学家就餐 问题？ 65 10. 有一阅览室，读者进入时必须先在一张登记表上 进行登记，该表为每一座位列一表目，包括座号 和读者姓名。读者离开时要消掉登记信号，阅览 室中共有100个座位，请问： (1) 为描述读者的动作，应编写几个程序？设置 几个进程？进程与程序间的对应关系如何？ (2) 用类Pascal语言和Wait, Signal操作写出这些进 程间的同步算法。 66 答：(1) 应编写1个程序；设置2个进程； 进程与程序间的对应关系是：多对1。 (2) begin S1:=100 (有100个座位) S2:=0 (没有阅读者) mutex: =1 cobegin P1: repeat P(S1); P(mutex); 登记信息; V(muetx); V(S2)就座，阅读； until false coend end P2: repea