第二章进程管理(2)3备课讲稿.ppt

第二章进程管理(2)第二章进程管理(2)2.4进程同步2.5管程机制2.6进程通信2.4 进程的同步 在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系 进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作， 进程的同步机制信号量及P.V操作（解决进程同步互斥问题）相互感知程度 交互关系 一个进程对其他进程的影响 相互不感知(完全不了解其它进程的存在) 竞争(competition) 一个进程的操作对其他进程的结果无影响 间接感知(双方都与第三方交互，如共享资源) 通过共享进行协作 一个进程的结果依赖于从其他进程获得的信息 直接感知(双方直接交互，如通信) 通过通信进行协作 一个进程的结果依赖于从其他进程获得的信息 2. 进程的同步（直接作用） 指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态 由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。

临界资源： 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量3. 进程的互斥（间接作用）4. 基本概念 进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问 进程同步：指多个相关进程在执行次序上的协调 临界资源:一次仅供一个进程使用的资源 在进程中涉及到临界资源的程序段叫临界区 多个进程的临界区称为相关临界区5.使用互斥区的原则 空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 忙则等待：不允许两个以上的进程同时进入互斥区 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法: 由竞争各方平等协商 引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程解决，但常常忙等待）6.进程互斥的软件方法 通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志软件解法的缺点： 1. 忙等待 2. 实现过于复杂 3. 需要高的编程技巧软件解法 (1)free: 表示临界区标志 true: 有进程在临界区 false:无进程在临界区(初值) . while (free); free = false; 临界区 free = true;软件解法 (2)turn: true P进入临界区 false Q进入临界区 .P: while (not turn); 临界区 turn = false;Q: while (turn); 临界区 turn = true;软件解法(3)pturn,qturn: 初值为falseP进入临界区的条件: pturn not qturnQ进入临界区的条件: not pturn qturn P . Q . pturn = true; pturn = true; while (qturn); while (pturn); 临界区 临界区 pturn = false; qturn = false; . .硬件解法 (1) “测试并设置”指令 boolean TS (boolean *lock) boolean old; old = *lock; *lock = true; while TS(&lock); 临界区 lockfalse;硬件解法 (2) “交换”指令voidSWAP(int*a,int*b)inttemp;temp=*a;*a=*b;*b=temp; key = true; do SWAP(&lock,key); while(key); 临界区 lock:=false;硬件解法 (3) “开关中断”指令进入临界区前执行： 执行“关中断”指令离开临界区后执行： 执行“开中断”指令7 进程的同步机制信号量及P.V操作（解决进程同步）同步机制： 信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中） 描述能力 可以实现 效 率 高 使用方便1)同步机制应满足的基本要求2)解决互斥的锁机制 实现互斥的一种软件方法是采用锁机制，即提供一对上锁(Lock)和开锁(UnLock)原语，以及一个锁变量W。

进程进入临界区前，通过锁变量来判断临界资源是否被占用 3) 信号量机制 信号量机制是一种卓有成效的进程同步工具，被广泛应用于单处理机和多处理机系统，以及计算机网络中 锁机制仅能表示“开”与“关”两种状态；开、关锁原语必须作为原子操作来进行；关锁原语言中反复测试状态，浪费了处理机的时间；锁机制只能解决互斥，不能用于同步信号量同步机制能完满地解决上述问题信号量：semaphore 是一个数据结构 定义如下： struc semaphore int value;pointer_PCB queue; 信号量说明： semaphore s;P操作P(s) s.value = s.value -; if (s.value 0) 该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue; 操作 意味着请求分配一个单位资源V操作V(s) s.value = s.value +; if (s.value 0表示有S个资源可用 S=0表示无资源可用 S=1 & S2 = 1 & & Sn = 1)/满足资源要求时的处理； for (i = 1; i = n; +i) -Si; /注：与P的处理不同，这里是在确信可满足 / 资源要求时，才进行减1操作；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);一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况： Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配 Swait(S,1,1)表示互斥信号量 Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0时，禁止任何进程进入临界区）【思考题】1.用P.V操作解决下图之同步问题:getcopyputfstg用P.V操作解决司机与售票员的问题司机进程：while (true)启动车辆正常驾驶到站停车售票员进程：while (true)关门售票开门10. 经典问题1)读者写者问题 有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待第一类读者写者问题的解法读者：while(true)P(mutex);readcount+;if(readcount=1)P(w);V(mutex);读P(mutex);readcount-;if(readcount=0)V(w);V(mutex);写者：while(true)P(w);写V(w);第一类读者写者问题的解法（一般信号量集）读者：swait(wmutex,1,1;rcount,R,0);写；ssignal(wmutex,1);写者：swait(rcount,1,1;wmutex,1,0);写；ssignal(rcount,1);2)哲学家就餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子#defineN5voidphilosopher(inti)while(true)思考；取forki;取fork(i+1)%5；进食；放forki;放fork(i+1)%5；为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿3)第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）第二章进程管理2.5管程机制 1. 管程的提出 采用P-V同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中 缺点： （）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序 （）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局 （）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的2.管程概念 概念：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作。

系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性3.管程的组成管程的四个组成部分： 名称 数据结构说明 对该数据结构进行操作的一组过程/函数 初始化语句 局部于管程的数据结构，仅被局部于管程的过程访问局部于管程的过程，也仅能访问管程内的数据结构 管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来 管程：一种同步机制 系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性管程的形式TYPEmonitor_name=MONITOR;共享变量说明define本管程内所定义、本管程外可调用的过程（函数）名字表use本管程外所定义、本管程内将调用的过程（函数）名字表PROCEDURE过程名（形参表）；过程局部变量说明；BEGIN语句序列；END;.FUNCTION函数名（形参表）：值类型；函数局部变量说明；BEGIN语句序列；END;.BEGIN共享变量初始化语句序列；END; 模块化:一个管程是一个基本程序单位，可以单独编译 抽象数据类型:管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码 信息掩蔽:管程是半透明的，管程中的外部过程（函数）实现了某些功能，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的4.管程的三个主要的特性 管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量 为了保证管程共享变量的数据完整性，规定管程互斥进入 管程通常是用来管。