计算机操作系统第03章进程同步与通信ppt课件

1、第三章第三章 进程的同步与通讯进程的同步与通讯3.1 进程同步的根本概念举例：例一：搬椅子和坐椅子同窗甲同窗乙. if 有空椅子 then 坐下 if 有空椅子 then 搬走.例二：民航售票X为某航班的票数主机终端终端终端终端ABCD例三：交通流量的统计S表示经过的车辆数主程序主程序S：=0；Delay(600)；write(S)；中断处置程序中断处置程序S：S1；当延时了当延时了10分钟后分钟后S=200，在刚刚打，在刚刚打印终了时经过了一印终了时经过了一辆车辆车例四：存储器管理的内存分配与回收X为可分配的空间大小，恳求及回收的空间大小为B分配进程回收进程.if XB then 等待； X

2、：XB； X：XB；唤醒；.例五：公交司机和售票员司机的活动售票员的活动 启动车辆关车门正常行驶售票到站停车开车门 例六：计算进程与打印进程计算进程打印进程数据计算从缓冲区取数据将结果送缓冲区打印计算进程计算进程缓冲区缓冲区打印进程打印进程进程间的关系资源共享关系间接作用：进程间要经过某种中介发生联络，是无认识安排的，可发生在相交进程之间，也可发生在无关进程之间相互协作关系(直接作用：进程间的相互联络是有认识的安排的，直接作用只发生在相交进程间相互感知程度 交互关系 一个进程对其他进程的影响 相互不感知(完全不了解其它进程的存在) 竞争(competition) 一个进程的操作对其他进程的结果

3、无影响 间接感知(双方都与第三方交互，如共享资源) 通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息 直接感知(双方直接交互，如通信) 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息 进程的互斥间接作用 由于各进程要求共享资源，而有些资源需求互斥运用，因此各进程间竞争运用这些资源，进程的这种关系为进程的互斥。临界资源：系统中某些资源一次只允许一个进程运用，称这样的资源为临界资源或互斥资源或共享变量进程的同步直接作用 指系统中多个进程中发生的事件存在某种时序关系，需求相互协作，共同完成一项义务。详细说，一个进程运转到某一点时要求另一同伴进程为它提供音讯，在未获得音讯之前，该

4、进程处于等待形状，获得音讯后被唤醒进入就绪形状。例如接力赛跑根本概念进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进展访问。进程同步：指多个相关进程在执行次序上的协调。临界资源:一次仅供一个进程运用的资源。在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区进入区和退出区以及剩余区进程P1.A:=a1;Print a.进程P2.A:=a1;Print a.进程P3.If a0 thena:=a1;elsea:=a1;.程 序 段1程 序 段2程 序 段n共 享 变 量同步机制应遵照的准那么空闲让进：当无进程在互斥区时，任何有权运用互斥区的进程可进入忙那么等待：不允许

5、两个以上的进程同时进入互斥区有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待形状的进程应放弃占用CPU，以使其他进程有时机得到CPU的运用权运用临界区的原那么：前提：任何进程无权停顿其它进程的运转 进程之间相对运转速度无硬性规定进程互斥的处理有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的运用详细方法：硬件当一个进程进入临界区,就屏蔽一切中断，但本钱高软件用编程处理，但经常忙等待进程互斥的软件方法经过平等协商方式实现进程互斥的最初方法是软件方法 其根本思绪是在进入区检查和设置一些标志，假设已有进程在临界区，那么在进入区经过循环检查进展等待

6、；在退出区修正标志 其中的主要问题是设置什么标志和如何检查标志软件解法的缺陷： 1. 忙等待 2. 实现过于复杂 3. 需求高的编程技巧软件解法 (1)turn: true 进程P进入临界区 false 进程Q进入临界区 .P: while (not turn); 临界区 turn = false;Q: while (turn); 临界区 turn = true;问题：问题：1、交替、交替2、某进程失败、某进程失败软件解法 (2)free: 表示临界区标志 true: 有进程在临界区 false:无进程在临界区(初值) . while (free); free = true; 临界区 free

7、 = false;问题：能够会呵斥多个进程同时进入临界区的景象。软件解法 (2)的改良Flag0：进程0的临界区标志Flag1：进程1的临界区标志进程0进程1 while (flag1)； while (flag0)；Flag0：=ture； Flag1：=ture；临界区临界区Flag0：false； Flag1：false；软件解法 (3)pturn,qturn: 初值为falseP进入临界区的条件: pturn not qturnQ进入临界区的条件: not pturn qturn P . Q . pturn = true; qturn = true; while (qturn); wh

8、ile (pturn); 临界区 临界区 pturn = false; qturn = false; . .软件解法 (3)的改良进程0进程1 Flag0：=ture； Flag1：=ture；while (flag1) while (flag0) flag0：false； flag1:false； 等一会 等一会 flag0：ture； flag1：ture； ； ；临界区临界区Flag0：false； Flag1：false；在解法3的根底上引入了turn的Dekker算法turn的初值恣意进程进程P 进程进程Qwhile true while truepturn：true； qturn：

9、true；while qturn while qturnif turn2) if turn1)pturn：false； qturn：false；while turn2)； while turn1)；pturn：true; qturn：true;临界区临界区 临界区临界区turn：2； turn：1；pturn：false； qturn：false； 软件解法 (4)进程P 进程Q pturn：true； qturn：true；turn：2； turn：1；whileqturn & turn=2whileqturn & turn=1临界区 临界区pturn：false； qtur

10、n：false； Peterson算法算法软件解法的缺陷忙等待whiledo；实现过于复杂，需求很高的编程技巧硬件解法 (1)“测试并设置指令 boolean TS (boolean boolean TS (boolean * *lock) lock) boolean old; boolean old; old = old = * *lock;lock; * *lock = true;lock = true; while TS(&lock); while TS(&lock); 临界区临界区 lock lockfalse;false;TS前往值为前往值为old硬件解法 (2)“交

11、换指令void SWAP(int *a, int *b)int temp;temp = *a;*a = *b;*b = temp; key = true; key = true; do do SWAP(&lock,key); SWAP(&lock,key); while(key); while(key); 临界区临界区 lock:=false; lock:=false;硬件解法 (3) “开关中断指令进入临界区前执行： 执行“关中断指令分开临界区后执行： 执行“开中断指令此方法会降低系统的并行程度，因此运用得此方法会降低系统的并行程度，因此运用得较少。较少。进程的同步机制信号量

12、及P.V操作处理进程同步同步机制： 信号量及P、V操作；管程；条件临界域；途径表达式等用于集中式系统中会合；通讯顺序进程；分布进程；远程过程调用等适用于分布式系统中1)同步机制应满足的根本要求描画才干可以实现效 率 高 运用方便2)处理互斥的锁机制实现互斥的一种软件方法是采用锁机制，即提供一对上锁(Lock)和开锁(UnLock)程序，以及一个锁变量W。进程进入临界区前，经过锁变量来判别临界资源能否被占用。 3.2信号量机制信号量机制是一种卓有效果的进程同步工具，被广泛运用于单处置机和多处置机系统，以及计算机网络中。锁机制仅能表示“开与“关两种形状；上锁程序中反复测试形状，浪费了处置机的时间；

13、锁机制只能处理互斥，不能用于同步。信号量同步机制能完美地处理上述问题。信号量：semaphore是一个数据构造定义如下： struc semaphore int value;/*整型变量，仅由P、V操作修正pointer_PCB queue; /*进程等待队列 信号量阐明： s：semaphore：;P操作即wait操作P(s)P(s)或或waitwaits s s.value = s.value -; s.value = s.value -; if (s.value 0) if (s.value 0) 该进程形状置为等待形状该进程形状置为等待形状 将该进程的将该进程的PCBPCB插入相应的等

14、待队列末尾插入相应的等待队列末尾s.queue;s.queue; 调用进程调度原语重新分配调用进程调度原语重新分配CPU；V操作即signal操作V(s)V(s) s.value = s.value +; s.value = s.value +; if (s.value = 0) if (s.value =1 & S2 = 1 & & Sn = 1)/满足资源要求时的处置；满足资源要求时的处置； for (i = 1; i = n; +i) -Si; /注：与注：与P的处置不同，这里是在确信可满足资源的处置不同，这里是在确信可满足资源要求时，才进展减要求时，才进展减1操

15、作；操作；break;else /某些资源不够时的处置；某些资源不够时的处置； 调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue; 阻塞调用进程阻塞调用进程; Ssignal(S1, S2, , Sn)for (i = 1; i = ti；即当资源数量低于；即当资源数量低于ti时，便不时，便不予分配予分配占用值为占用值为di表示资源的恳求量，即表示资源的恳求量，即Si = Si - di对应的对应的P、V原语格式为：原语格式为：Swait(S1, t1, d1; .; Sn, tn, dn);Ssignal(S1, d1; .; Sn, dn);普

16、通“信号量集可以用于各种情况的资源分配和释放，几种特殊情况：Swait(S, d, d)表示每次恳求d个资源，当少于d个时，便不分配Swait(S, 1, 1)表示互斥信号量与waitS，S1等价Swait(S, 1, 0)可作为一个可控开关当S1时，允许多个进程进入临界区；当S=0即当S1时时，制止任何进程进入临界区经典问题1)1)读者写者问题读者写者问题 有两组并发进程有两组并发进程: : 读者和写者读者和写者, ,共享一组数据区共享一组数据区 要求：要求： 允许多个读者同时执行读操作允许多个读者同时执行读操作 不允许读者、写者同时操作不允许读者、写者同时操作 不允许多个写者同时操作不允许

17、多个写者同时操作第一类：读者优先假设读者来：1无读者、写者，新读者可以读2有写者等，但有其它读者正在读，那么新读者也可以读3有写者写，新读者等假设写者来：1无读者，新写者可以写2有读者，新写者等待3有其它写者，新写者等待第一类读者写者问题的解法读者：读者： while (true) wait(mutex); readcount +; if (readcount=1) wait (w); signal(mutex); 读读 wait(mutex); readcount -; if (readcount=0) signal(w); signal(mutex); ;写者：写者： while (tru

18、e) wait(w); 写写 signal(w); ;第一类读者写者问题的解法普通讯号量集写者：swait(wmutex,1,1; rcount,R,0);写；ssignal(wmutex,1);读者：swait(rcount,1,1; wmutex,1,0);读；ssignal(rcount,1);2)哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思索，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必需拿到两只筷子，并且每个人只能直接从本人的左边或右边去取筷子#define N 5 void philosoph

19、er (int i) while (true) 思索； waitmi；取forki; waitm (i+1) % 5； 取fork(i+1) % 5； 进食； signalmi；放forki; signalm (i+1) % 5；放fork(i+1) % 5； 留意：此方法能够产生死锁留意：此方法能够产生死锁为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子给一切哲学家编号，奇数号的哲学家必需首先拿左边的筷子，偶数号的哲学家那么反之利用AND信号量机制处理哲学家进餐问题见书P78页3)3)第二类读者写者问题：第二类读者写者问题：写

20、者优先条件：1多个读者可以同时进展读2写者必需互斥只允许一个写者写，也不能读者写者同时进展3写者优先于读者一旦有写者，那么后续读者必需等待，唤醒时优先思索写者3.5 进程通讯1.进程通讯概述P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传送简单的信号控制信号，不能传送交换大量信息假设要在进程间传送大量信息那么要用Send / Receive原语高级通讯原语2.进程通讯的类型共享存储器方式：相互通讯的进程经过共享某些数据构造或存储区来进展通讯，可分为共享数据构造方式、共享存储区方式；音讯通讯方式：进程间的音讯交换以音讯或报文为单位，程序员利用一组通讯命令(原语)来实现通讯

21、，可分为直接、间接通讯方式；管道通讯：在UNIX系统中，利用一个翻开的共享文件来衔接两个相互通讯的进程，该共享文件称为管道，因此该方式又称为管道通讯。为了协调双方通讯，管道通讯必需提供三方面的协调才干：互斥、同步、对方能否存在。直接通讯和间接通讯直接通讯方式 指发送进程利用OS所提供的发送命令，直接把音讯发送给目的进程。 要求发送进程发音讯时要指定接纳进程的名字，反过来，接纳时要指明发送进程的名字 Send(receiver,message) Receiver(sender,message)间接通讯方式 发送进程发音讯时不指定接纳进程的名字，而是指定一个中间媒介，即信箱。进程间经过信箱实现通讯 发送原语：send(MB,Message) 接纳原语：receive(MB,Message