第3章处理机管理2PPT课件

1、2021/6/71 第3章处理机管理2 进程通信 2021/6/72 八、进程通信 n同步、互斥 n进程通信原理和通信工具 n临界区管理 n信号量与PV操作 2021/6/73 同步、互斥 n进程运行中的关系：互相协作和互相竞争 n进程互斥：具有某限制条件，进程间不可同时 进行同一操作。例如： nA申请打印机打印释放打印机 nB申请打印机打印释放打印机 n进程同步：进程间必须合作的协同工作关系。 例如： n计算进程结果送缓冲区通知打印进程 n打印进程取走缓冲区数据通知计算进程 2021/6/74 进程通信原理和通信工具 n通信原理：使用信号灯 n通信工具：原语 n开锁、关锁 nPV操作 n消息

2、缓冲 低级通信原语 高级通信原语 2021/6/75 临界区管理 n临界资源：某段时间内只允许一个进程 使用的资源。 n临界区：进程访问临界资源的那段代码 2021/6/76 例题： nLock和Unlock X：代表临界资源状态 X0表示资源可用；X1表示资源正在使用 Lock(x) L: if x=1 then goto L;/*正在使用,继续测试*/ else x:=1;/*占用资源*/ Unlock(x) x:=0;/*使用完毕,释放资源*/ 2021/6/77 信号量与PV操作概念(1) n信号量：一种软资源 n原语：内核中执行时不可被中断的过程 nP操作原语和V操作原语 n信号量和

3、P、V操作 ，将交通管制中多种颜色 的信号灯管理交通的方法引入操作系统，让两 个或多个进程通过特殊变量展开交互。 2021/6/78 信号量与PV操作概念(2) n一个进程在某一特殊点上被迫停止执行直到接 收到一个对应的特殊变量值，这种特殊变量就 是信号量(semaphore)，复杂的进程合作需求 都可以通过适当的信号结构得到满足。 n通过信号量传送信号，进程使用P、V两个特 殊操作来发送和接收信号，如果进程相应的信 号仍然没有送到，进程被挂起直到信号到达为 止。 2021/6/79 信号量与PV操作概念(3) n操作系统中，信号量表示物理资源的实 体，它是一个与队列有关的整型变量。 n实现时

4、，信号量是一种记录型数据结构， 有两个分量：一个是信号量的值，另一 个是信号量队列的队列指针。 2021/6/710 图示： 信号量的值(-2) 信号量队列指针 2021/6/711 信号量与PV操作概念(4) n信号量按其用途分为 n公用信号量 n私有信号量 n信号量按其取值分为 n二元信号量 n一般信号量 2021/6/712 信号量与PV操作整型信号量 n设s为一个整型量，除初始化外，仅能通 过P、V操作访问，P和V操作原语定义： P(s)：while s0 do null operation /*执行空指令,等待唤醒*/ s:=s-1；/*占用一个资源*/ V(s)：s:=s+1；/*

5、释放一个资源*/ 2021/6/713 信号量与PV操作记录型信号量(1) n设s为一个记录型数据结构,一个分量 为整形量value,另一个为信号量队列 queue, P和V操作原语定义： nP(s)；将信号量s减去l，若结果小于0， 则调用P(s)的进程被置成等待信号量s 的状态。 nV(s)：将信号量s加1，若结果不大于0， 则释放一个等待信号量s的进程。 2021/6/714 信号量与PV操作记录型信号量(2) n推论1：若信号量s为正值，则该值等于在封锁 进程之前对信号量s可施行的P操作数、亦等于 s所代表的实际还可以使用的物理资源数 n推论2：若信号量s为负值，则其绝对值等于登 记排

6、列在该信号量s队列之中等待的进程个数、 亦即恰好等于对信号量s实施P操作而被封锁起 来并进入信号量s队列的进程数 n推论3：通常，P操作意味着请求一个资源，V 操作意味着释放一个资源。在一定条件下，P 操作代表挂起进程操作，而V操作代表唤醒被 挂起进程的操作 2021/6/715 例题1：苹果桔子问题 n桌上有一只盘子，每次只能放入一只水果；爸 爸专向盘子中放苹果(apple)，妈妈专向盘子 中放桔于(orange)，一个儿子专等吃盘子中的 桔子，一个女儿专等吃盘子里的苹果。 plate:integer; sp:semaphore;/* 盘子里可以放几个水果 */ sg1:semaphore;

7、 /* 盘子里有桔子 */ sg2:semaphore;/* 盘子里有苹果 */ sp:= 1;/* 盘子里允许放一个水果*/ sg1:= 0;/* 盘子里没有桔子 */ sg2:= 0;/* 盘子里没有苹果*/ 2021/6/716 cobegin process father begin L1:削一个苹果； P(sp); 把苹果放入plate； V(sg2); goto L1; end; process mother begin L2:剥一个桔子； P(sp); 把桔子放入plate； V(sg1); goto L2; end; process son begin L3: P(sg1);

8、从plate中取桔子； V(sp); 吃桔子； goto L3; end; process daughter begin L4: P(sg2); 从plate中取苹果； V(sp); 吃苹果； goto L4; end; coend 2021/6/717 例题2：哲学家吃通心面问题 n有五个哲学家围坐在一 圆桌旁，桌中央有一盘 通心面，每人面前有一 只空盘于，每两人之间 放一把叉子。每个哲学 家思考、饥饿、然后吃 通心面。为了吃面，每 个哲学家必须获得两把 叉子，且每人只能直接 从自己左边或右边去取 叉子 。 2021/6/718 var forki:array0.4 of semaphore

9、; forki:=1; cobegin process Pi /*i=0,1,2,3,4*/ begin L1: 思考； P(forki); P(fork(i+1)mod 5); 吃通心面； V(forki); V(fork(i+1)mod 5); goto L1; end; coend 2021/6/719 例题3：生产者与消费者问题 n生产者与消费者可以通过一 个环形缓冲池联系起来，环 形缓冲池由几个大小相等的 缓冲块组成，每个缓冲块容 纳一个产品。 n每个生产者可不断地每次往 缓冲池中送一个生产产品， 而每个消费者则可不断地每 次从缓冲池中取出一个产品。 n指针i和指针j分别指出当前的

10、第一个空缓冲块和第一个满 缓冲块。 0 3 2 1 7 6 54 缓冲区缓冲区 j i 2021/6/720 分析： n既存在合作同步问题，也存在临界区互斥问题 n合作同步：当缓冲池全满时，表示供过于求，生产者必须 等待，同时唤醒消费者；当缓冲池全空时，表示供不应求， 消费者应等待，同时唤醒生产者。 n互斥：缓冲池显然是临界资源，所在生产者与消费都要使 用它，而且都要改变它的状态。 n基于环形缓冲区的生产者与消费者关系形式描 述： n公用信号量mutex：初值为1，用于实现临界区互斥 n生产者私用信号量empty：初值为n，指示空缓冲块数目 n消费者私用信号量full：初值为0，指示满缓冲块数

11、目 n整型量i和j初值为0，i指示首空缓冲块序号，j指示首满缓 冲块序号 2021/6/721 var mutex,empty,full:semaphore; i,j:integer;buffer:array0.n-1 of item; i:=j:=1; Procedure producer; begin while true do begin produce a product; P(empty); P(mutex); buffer(i):=product; i:=(i+1) mod n; V(mutex); V(full); end; end; Procedure consumer; be

12、gin P(full); P(mutex); goods:=buffer(j); j:=(j+1) mod n; V(mutex); V(empty); consume a product; end; end; 2021/6/722 例题4：读者与写者问题 n有两组并发进程：读者和写者，要求： n允许多个读者同时执行读操作 n任一写者在完成写操作之前不允许其它读者 或写者工作 n写者执行写操作前，应让已有的写者和读者 全部退出 n分析： n读者之间不必互斥，可同时读文件。 n写者之间必须互斥。 n读、写者之间互斥。 2021/6/723 var mutex,wrt:segaphore; rea

13、dcount:interger; begin seminit; readcount:=0 cobegin Procedure writer; begin P(wrt) writing is performing; V(wrt); end; procedure reader; begin P(mutex); readcount:=readcount+1; if readcount=1 then P(wrt); V(mutex); reading is performing; P(mutex); readcount:=readcount-1 if readcount=0 then V(wrt);

14、V(mutex); end; coend; end; 2021/6/724 例题5：理发师问题 n理发店理有一位理发师、一把理发椅和n 把供等候理发的顾客坐的椅子。 n如果没有顾客，理发师便在理发椅上睡 觉。 n一个顾客到来时，它必须叫醒理发师。 n如果理发师正在理发时又有顾客来到， 则如果有空椅子可坐，就坐下来等待， 否则就离开。 2021/6/725 var waiting: integer;/*等候理发的顾客数*/ CHAIRS: integer; /*为顾客准备的椅子数*/ customers, barbers, mutex : semaphore; customers := 0; b

15、arbers := 0; waiting := 0; mutex := 1; Procedure barber; begin while(TRUE);/*理完一人,还有顾客吗?*/ P(cutomers);/*若无顾客,理发师睡眠*/ P(mutex);/*进程互斥*/ waiting := waiting 1;/*等候顾客数少一个*/ V(barbers);/*理发师去为一个顾客理发*/ V(mutex);/*开放临界区*/ cut-hair( );/*正在理发*/ end; procedure customer begin P(mutex);/*进程互斥*/ if waitingCHAIRS begin/*看看有没有空椅子*/ waiting := waiting+1;/* 等候顾客数加1*/ V(customers);/*必要的话唤醒理发师*/ V(mutex);/*开放临界区*/ P(barbers);/*无理发师, 顾客坐着养神*/ get-haircut( );/*一个顾客坐下等理发*/ end; else V(mutex);/*人满了,走吧!*/ end. 2021/6/726 习题： n爷爷将蛋糕放入空盒子，孙子取 走盒子中间的蛋糕，盒子内只允 许放入1个蛋糕，试写出PV操作代 码。 （思考：如果放入的蛋糕