操作系统原理-处理机管理-第二章分析.ppt

第2章 处理机管理;2.1 多道程序设计;前驱（趋）图;2.2.1程序的顺序执行;2.2.1程序的并发执行;程序并发执行时的特征;2.1.3程序并发的条件;Bernstein条件;异地售票例子;2.2 进程的描述;进程的特性;进程的特性(续);进程的概念;进程的概念;进程的概念;进程与程序的区别;2.2.3进程的基本状态及其转换;参考：引入挂起功能系统中的状态;2.2.4 PCB;PCB（续）;2.2.5 进程的队列;空闲PCB队列头指针;2.3 进程控制;1.进程创建原语;2.进程撤销原语;3.进程阻塞原语;4.进程唤醒原语;2.4 进程的互斥—你需要，我也需要;2.4.1互斥的定义;两种形式的制约关系;临界资源;临界区;临界区的使用原则;2.4.2上锁和开锁原语;上锁原语：LOCK（W）;开锁原语：UNLOCK（W）;2.4.3用开关锁原语实现进程互斥 ;例：甲、乙两进程要访问同一类临界资源 ;售票的例子;互斥使用不当，易造成死锁;2.5信号量机制 ;几种类型的信号量;2.5.1 （记录型）信号量的概念 ;2.5.2 P、V操作原语 ;定义在信号量S上的P(S)原语操作 ;定义在信号量S上的V(S)原语操作 ;P(S)和V(S)的物理含义;用P、V操作原语实现进程的互斥 所用信号量的初值设为1，表示临界资源未被占用 在相关临界区的前后分别施以P操作和V操作，即在相关进程的程序里由P操作和V操作原语紧夹着临界区，保证这些进程互斥地进入各自的临界区 用P、V操作原语实现进程互斥的效率更高，因为P操作中引入了阻塞机制，消除了“CPU忙等”现象，符合“等则放权”的原则。;;异地售票的例子;Step1：分析清楚题目设计的进程间的制约关系 终端售票进程对服务器上的Pk访问是互斥关系 Step2：设置信号量（包括信号量的个数和初值，写出信号量的含义） 设置一个信号量，初值为1 信号量在这里代表的就是一把锁 Step3：给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。 ;北京售票终端进程： ;天津售票终端进程： ;解决无票可售的问题： ;参考：经典的整型信号量;参考：信号量用于互斥死锁;参考：AND型信号量;2.5 进程的同步—你等我，我也等你;进程同步典型例子;2.6.2 用P、V操作原语实现进程的同步;例2.2 生产者—消费者问题;问题分析：制约关系;问题解答：设置信号量;用信号量机制解决生产者—消费者问题的算法：;P(S)、V(S)注意事项：; 生产者i 生产出一产品； P（empty）； P（mutex）； 将该产品放入缓冲区； V（mutex）； V（full）； ;例2.3 读者-写者问题;问题分析：制约关系;问题解答：设置信号量及变量; 算法描述：;例2.4 试用用信号量机制描述两人下象棋的过程;问题分析：制约关系;问题解答：设置信号量;红黑双方下象棋过程如下： ;另一种解法：设置信号量;另一种解法：红黑双方下象棋过程如下： ;例2.5 用信号量机制描述进程的前趋后继关系(补充例1);Var s12,s13,s24,s25,s36,s46,s56 : semaphore :=0,0,0,0,0,0,0; begin parbegin process 1: begin S1;V(s12);V(s13) end; process 2: begin P(s12);S2;V(s24);V(s25) end; process 3: begin P(s13);S3;V(s36) end; process 4: begin P(s24); S4;V(s46) end; process 5: begin P(s25); S5;V(s56) end; process 6: begin P(s36); P(s46); P(s56); S6 end; parend end;例2.6 用信号量机制解决睡眠的理发师问题（补充例2，经典IPC问题之一）;问题分析：制约关系;问题解答：设置信号量;理发师问题解法一：by Tanenbaum semaphore customers, barbers, mutex = 0, 0, 1; int waiting = 0; /* i.e. customers are waiting */ ;理发师问题解法（二）：by J.A.Harris 何炎详;理发师问题解法（三）：by 谢青松;某小型超级市场，可容纳50人同时购物。入口处有篮子，每个购物者可拿一只篮子入内购物。出口处结帐，并归还篮子（出、入口禁止多人同时通过）。试用信号量和P、V操作写出购物者的同步算法。;问题解答:设置信号量;购物者i进程（解法一）：