软件技术基础处理机管理

1、2.2 处理机管理 进程的概念进程的概念 进程的控制进程的控制 进程的调度进程的调度 进程的互斥与同步进程的互斥与同步 进程的通信进程的通信 死锁死锁1多道程序系统多道程序系统程序程序A程序程序BOS调度调度I/O AI/O Bt1t2如何把如何把CPUCPU合理地分配给某个需要的程序，合理地分配给某个需要的程序，并在其用完后予以回收。并在其用完后予以回收。合理利用及减少开销合理利用及减少开销! !分配分配回收回收处理机管理的核心问题22.2.1 进程的概念一、程序与进程程序：程序：由若干条具有一定功能的机器指令所组成由若干条具有一定功能的机器指令所组成的解题顺序和步骤。的解题顺序和步骤。顺序

2、执行顺序执行（单道系统）（单道系统）并发执行并发执行（多道系统）（多道系统）顺序性顺序性封闭性封闭性可再现性可再现性程序执行严格按照一定顺程序执行严格按照一定顺序，不受外界因素影响，序，不受外界因素影响，结果只由初始条件决定结果只由初始条件决定相互约束相互约束资源争夺资源争夺与共享与共享程序执行是相互交替穿插进程序执行是相互交替穿插进行，执行次序每次变化；受行，执行次序每次变化；受外界影响，结果与速度有关外界影响，结果与速度有关3前驱图前驱图 有向无环图有向无环图 节点：表示一条语句，或一段程序节点：表示一条语句，或一段程序 有向线段：表示语句之间的顺序关系有向线段：表示语句之间的顺序关系 无

3、环：当程序中出现循环时，一般将整个无环：当程序中出现循环时，一般将整个循环作为一个节点循环作为一个节点a1 = 5;b1 = a1 + 5 ;print(b1);I1C1P1InputCalculatePrint4a1 = 5;b1 = a1 + 5;print( b1 )；a3 = 5;b3 = a3 10;print( b3 )；a2 = 5;b2 = a2 + 6;print( b2 )；I1C1P1程序程序1程序程序2程序程序3I2C2P2I3C3P3程序程序1程序程序2程序程序35I1I2C1I3C2P1C3P2t1t2t3t4t7t5t6t8P3t96I1P3t1t2t3t4t5I

4、2C1I3C2P1C3P27程序顺序执行与并发执行例：程序顺序执行与并发执行例：程序程序1x 3 ；yx2 ；printf（y）；）；程序程序2x 1 ；yx5 ；printf（y）；）；8x =3y=x+2printf(y)x =1y=x+5printf(y)顺序执行顺序执行t2t1t3t4t5t6顺序执行顺序执行结果：结果： y = 5 y = 69并发执行（一）并发执行（一）x =3y=x+2printf(y)x =1y=x+5printf(y)并发执行并发执行t2t1t3t4t5t6结果：结果： y = 3 y = 310并发执行（二）并发执行（二）x =3y=x+2printf(y)

5、y =x5 x =1printf(y)并发执行并发执行t2t1t3t4t5t6结果：结果： y = ？ y = 311可见：可见： 程序的概念已无法描述动态执行过程中程序的概念已无法描述动态执行过程中的并发活动，解决办法？的并发活动，解决办法？引入引入进程进程来描述程序的一次执行，来描述程序的一次执行，使并发执行的程序保持使并发执行的程序保持“可再现性可再现性”。进程包括：执行现场的保留、资源的分进程包括：执行现场的保留、资源的分配情况、程序的执行位置等。配情况、程序的执行位置等。12进程的定义：进程是可并发执行的程序在给定数据进程是可并发执行的程序在给定数据集合上的一次执行过程；是系统进行集

6、合上的一次执行过程；是系统进行资源分配和调度的一个独立的基本单资源分配和调度的一个独立的基本单位和实体；是指执行一个映象程序的位和实体；是指执行一个映象程序的总环境。总环境。131、是指令的集合，是静态概念是指令的集合，是静态概念是程序的执行过程，是动态概念是程序的执行过程，是动态概念2、可作为软件资源长期保存可作为软件资源长期保存只是一次短暂活动或过程只是一次短暂活动或过程3、一个、一个可对应多个进程可对应多个进程一个一个可包含多段程序可包含多段程序程序与进程比较14二、进程的特征动态性动态性并发性并发性独立性独立性异步性异步性具备生命周期，可以被建立、挂起、撤销具备生命周期，可以被建立、挂

7、起、撤销进程执行时间重叠进程执行时间重叠资源分配的基本单位，相对独立资源分配的基本单位，相对独立速度不可预知，速度不可预知， “走走停停走走停停”15三、进程的描述PCB数据数据程序程序进程的结构：进程的结构：进程控制块进程控制块（ Process Control Block ）：）：操作系统用来描述进程执行情况操作系统用来描述进程执行情况和状态变化的一种专门数据结构。和状态变化的一种专门数据结构。内容：调度信息和现场信息内容：调度信息和现场信息16典型的进程控制块典型的进程控制块PCB结构结构进程标识符进程标识符进程状态进程状态CPU现场（现场（程序状态字、寄存器内容等）程序状态字、寄存器内

8、容等）资源清单资源清单优先级优先级队列指针、家族关系队列指针、家族关系通信机制（信箱或消息队列）通信机制（信箱或消息队列）同步机制（信号量）同步机制（信号量）存储位置存储位置17进程标识符进程标识符 识别进程的唯一标志。 内部标识符：一串数值，供系统识别 外部标识符：一串字符，供操作员识别 例：使用Windows任务管理器观察进程外部标识符。 例：使用visual studio调试工具spy观察进程内部标识符1819CPU现场CPU现场： 程序指令计数器 各种寄存器：AX，BX，bp栈顶寄存器等 程序状态字 。CPU现场就像一个工作环境， 当我们阻塞一个进程使其等待时，我们需要记录下这个环境的

9、各种参数， 以便将来进程恢复执行时，系统根据记录，恢复现场， 使进程感觉像从来没有离开过20PCB的作用的作用PCB可唯一标识一个进程可唯一标识一个进程PCB中的信息为进程的控制提供依据中的信息为进程的控制提供依据PCB将程序变成了进程将程序变成了进程PCB是进程在系统中存在的唯一标志。是进程在系统中存在的唯一标志。PCB进程进程一一对应一一对应21PCBs的组织方式的组织方式 系统如何管理多个进程的系统如何管理多个进程的? 将各进程的将各进程的PCB以一定的方式组织起来以一定的方式组织起来124101522四、进程的三种基本状态就绪状态就绪状态( Ready)执行状态执行状态( Execut

10、ing)等待状态等待状态( Wait)获得了除了获得了除了CPU外的一切所需资外的一切所需资源，具备执行条件源，具备执行条件占有占有CPU，正在执行。（唯一的），正在执行。（唯一的）因等待某种事件而暂时不能执行因等待某种事件而暂时不能执行23进程状态的转换新进程新进程就绪就绪执行执行结束结束阻塞阻塞接纳接纳进程调度进程调度中断或中断或时间片用完时间片用完完成完成I/OI/O请求或请求或等待某事件等待某事件I/OI/O完成或完成或事件发生事件发生24新进程新进程就绪就绪执行执行结束结束阻塞阻塞进入进入就绪队列就绪队列分配分配CPUCPU使用权使用权强制放弃强制放弃CPUCPU回到就绪队列回到就绪

11、队列释放所有释放所有资源资源进程主动放弃进程主动放弃CPUCPU进入阻塞等待队列进入阻塞等待队列进程被释放进程被释放回到就绪队列回到就绪队列25进程状态转换归纳：新进程新进程就绪状态就绪状态事件事件动作动作接纳接纳进入就绪队列进入就绪队列就绪就绪执行执行进程调度进程调度分配分配CPU执行执行结束结束完成完成释放资源释放资源执行执行阻塞阻塞时间片到时时间片到时高优先中断高优先中断系统剥夺系统剥夺CPU执行执行就绪就绪I/O请求请求等待某事件等待某事件进程放弃进程放弃CPU进入阻塞等待队列进入阻塞等待队列阻塞阻塞就绪就绪阻塞事件释放阻塞事件释放进程进入就绪队列进程进入就绪队列26注意：注意：就绪就

12、绪阻塞阻塞 阻塞阻塞执行执行执行执行就绪就绪 进程从执行态到阻塞态是主动的进程从执行态到阻塞态是主动的 进程发现需要等待某一事件，主动向系统申请进入阻塞进程发现需要等待某一事件，主动向系统申请进入阻塞态态 进程从阻塞态到就绪态是被动的进程从阻塞态到就绪态是被动的 当系统（或其它进程）发现阻塞进程阻塞的条件已释放，当系统（或其它进程）发现阻塞进程阻塞的条件已释放，向系统申请将该阻塞进程置为就绪态向系统申请将该阻塞进程置为就绪态272.2.2 进程的控制 进程的控制进程的控制控制进程在其生命周期的各种控制进程在其生命周期的各种活动及状态转换。活动及状态转换。 通过操作系统的原语（通过操作系统的原语

13、（primitive）来实现。）来实现。原语原语：用以完成特定功能的不可分割的一段程序，：用以完成特定功能的不可分割的一段程序，原语的执行过程是不可中断的。原语的执行过程是不可中断的。创建原语创建原语撤销原语撤销原语阻塞原语阻塞原语唤醒原语唤醒原语28一、创建原语：实质是创建进程控制块申请空闲申请空闲 PCB1向向 PCB 填入信息填入信息2设置进程为就绪状态设置进程为就绪状态3进程进入就绪队列进程进入就绪队列4进程创建步骤29二、撤销原语进程撤销步骤检索检索 PCB，找到，找到1撤销改进程及其子进程撤销改进程及其子进程2释放资源释放资源3撤销撤销 PCB4进程完成任务或异常中断30三、阻塞原

14、语阻塞阻塞执行执行阻塞原语引发阻塞的事件引发阻塞的事件启动启动 I/OI/O操作操作等待新数据等待新数据无工作可做无工作可做请求系统服务请求系统服务31中断中断 CPU 工作工作1保存保存CPU信息到信息到PCB中中2设为阻塞态设为阻塞态3PCB进入阻塞队列进入阻塞队列4进程阻塞步骤32四、唤醒原语就绪就绪等待等待唤醒原语引发唤醒的事件引发唤醒的事件服务完成服务完成新数据到达新数据到达新任务下达新任务下达I/OI/O操作完成操作完成33在等待队列查找在等待队列查找1设置进程设置进程PCB为就绪态为就绪态2从等待队列撤销从等待队列撤销3PCB进入就绪队列进入就绪队列4进程唤醒步骤34（1）内核是

15、）内核是OS的控制和协调中心，由它组织、的控制和协调中心，由它组织、启动和协调系统中各种活动。启动和协调系统中各种活动。 内核包括：中断处理程序、常用设备驱动软内核包括：中断处理程序、常用设备驱动软件、时钟管理、进程管理、存储器管理及公件、时钟管理、进程管理、存储器管理及公用基本操作等用基本操作等 内核常驻内存以提高效率。内核常驻内存以提高效率。（2）内核通常由各种）内核通常由各种原语原语构成。构成。补充：操作系统内核内核中的程序是系统的基本功能单元，一般不允内核中的程序是系统的基本功能单元，一般不允许被打断，否则将造成系统性能不稳定。许被打断，否则将造成系统性能不稳定。35（3）中断处理）中

16、断处理 中断机制是中断机制是OS内核最重要的功能之一。系内核最重要的功能之一。系统中的所有中断都由内核响应。中断是进程统中的所有中断都由内核响应。中断是进程并发执行的基础，并发执行的基础， OS是由中断驱动的。是由中断驱动的。t1t236关于中断机制关于中断机制向向CPU发发出中断出中断保护保护CPU现场现场识别中断源识别中断源恢复恢复CPU现场现场37（4）时钟管理）时钟管理 OS的许多重要操作，如：按时间片轮转调的许多重要操作，如：按时间片轮转调度，实时系统中的截止时间控制等，都依赖度，实时系统中的截止时间控制等，都依赖于时钟管理。于时钟管理。t时钟中断时钟中断时间片轮转时间片轮转382.

17、2.3 进程的调度含义：含义：目的：目的：对象：对象：处理机调度。为各个进程分配处理机处理机调度。为各个进程分配处理机使每个进程都能合理的使用处理机，得使每个进程都能合理的使用处理机，得到及时的响应到及时的响应处于就绪队列的进程处于就绪队列的进程 进程调度的任务是控制协调进程对进程调度的任务是控制协调进程对CPUCPU的竞争，的竞争，即按一定的调度算法从就绪队列中选中一个即按一定的调度算法从就绪队列中选中一个进程，把进程，把CPUCPU的使用权交给被选中的进程。的使用权交给被选中的进程。3940一、进程调度的原因进程执行完毕；进程等待某个事件阻塞；进程的时间片用完；有新进程（高优先级或其他）进

18、入就绪队列；41剥夺式（抢占式）非剥夺式（非抢占式） 系统按照某种原系统按照某种原则剥夺现行进程的则剥夺现行进程的CPU使用权，并使用权，并交给其他进程交给其他进程 现行进程的现行进程的CPU使用权使用权无法剥夺，除非由于时间无法剥夺，除非由于时间片完或者进程自身原因才片完或者进程自身原因才能交出能交出CPU使用权。使用权。高优先权短进程二、进程调度的方式42三、进程调度的功能记录系统中所有记录系统中所有进程的执行情况进程的执行情况1确定分配确定分配处理机的原则处理机的原则2处理机的处理机的分配与回收分配与回收3 记录系统中各进程的执行情记录系统中各进程的执行情况和环境状态，以便在处理机空况和

19、环境状态，以便在处理机空闲的时候选择合适的进程执行。闲的时候选择合适的进程执行。 选择合适的选择合适的调度算法调度算法以选择以选择合适的进程执行。合适的进程执行。 在执行（撤销）进程时装入在执行（撤销）进程时装入（释放）（释放）PCB信息。信息。43四、进程调度的过程记录进程的相关信息记录进程的相关信息选取适当的进程执行选取适当的进程执行为进程分配处理机为进程分配处理机进程本身信息进程本身信息和环境信息和环境信息进程调进程调度算法度算法恢复进程的恢复进程的现场信息现场信息44五、进程调度的算法算法设计的准则：用户用户周转时间周转时间响应时间响应时间优先权优先权系统系统系统吞吐量系统吞吐量处理机

20、效率处理机效率资源利用的资源利用的平衡平衡截止时间截止时间45简单的调度算法简单的调度算法先来先服务算法先来先服务算法短进程优先短进程优先轮转法轮转法等时间片轮转等时间片轮转不等时间片轮转不等时间片轮转优先权法优先权法抢占式优先权抢占式优先权非抢占式优先权非抢占式优先权静态优先权静态优先权动态优先权动态优先权多级反馈队列算法多级反馈队列算法算法的分类：46（1）先到先服务（）先到先服务（FCFS）算法）算法常用算法 按照就绪进程进入就绪队列的先后顺序调度，先进入先服务。算法简单，易于实现算法简单，易于实现对长进程有利对长进程有利短进程服务质量差短进程服务质量差47（2）短进程优先（）短进程优先

21、（SCBF）算法）算法按照就绪进程对系统服务时间的需求确定优先权，服务时间需求短进程优先被调度。需要进行进程时间估计需要进行进程时间估计对短进程有利对短进程有利长进程可能得不到调度长进程可能得不到调度n+1nnt （1 ） 48调度算法评价指标调度算法评价指标例例ABCWT101030ST210010TT1211040ATT54QTT61.14AQTT3.749 例：例：A请求系统服务时间请求系统服务时间5s，B请求系统请求系统服务时间为服务时间为100s，设第设第0到第到第5秒前，秒前，CPU运行运行C进程。进程。第第1秒时秒时B进入系统内存，第进入系统内存，第2秒时秒时A进入内存进入内存当

22、当CPU空闲，需要调度进程时根据不同的算法空闲，需要调度进程时根据不同的算法选择选择A或或B。问：分别计算问：分别计算FCFS算法下和算法下和SCBF算法下，算法下，A和和B的周转时间，带权周转时间和系统平均周的周转时间，带权周转时间和系统平均周转时间？转时间？50FCFS算法先来先服务算法先来先服务 A：周转时间为：周转时间为 3+100+5108s 带权周转时间为带权周转时间为108/5 20.4 B：周转时间为：周转时间为 4+100104s 带权周转时间为带权周转时间为104/100 1.04 平均带权周转时间为平均带权周转时间为(20.4 +1.04)2 10.72SCBF算法短进程

23、优先算法短进程优先 A：周转时间为：周转时间为 3+58s 带权周转时间为带权周转时间为8/5 1.6 B：周转时间为：周转时间为 4+ 5+100109s 带权周转时间为带权周转时间为109/100 1.09 平均带权周转时间为平均带权周转时间为(1.6+1.09)2 1.345先调度先调度B后调度后调度A先调度先调度A后调度后调度B51（3）等时间片轮转（）等时间片轮转（ERR）算法）算法按照按照FCFSFCFS算法从就绪队列调度调入进程算法从就绪队列调度调入进程为每个进程分配相同的时间片，并执行为每个进程分配相同的时间片，并执行时间片完，进程时间片完，进程执行完，调度下执行完，调度下一个

24、进程一个进程时间片完，进程时间片完，进程未执行完，进程未执行完，进程进入就绪队尾，进入就绪队尾，等待下一次调度等待下一次调度52时间片选取原则：时间片选取原则：q q：时间片大小：时间片大小T T：响应时间：响应时间N N：就绪队列进程数：就绪队列进程数q NT= 时间片选取过大或者过小有什么后果？ 应该按什么原则选取时间片？时间片长度公式：时间片长度公式： 公平性的保证公平性的保证响应及时性的保证响应及时性的保证ERR优点：优点：53（4）不等时间片轮转（）不等时间片轮转（ERR）算法）算法 在保证及时响应的基础上，为不同的需求分配大小不等的时间片降低周转时间。长进程长进程短进程短进程I/O

25、频繁型频繁型CPU密集型密集型长时间片长时间片短时间片短时间片54（5）最高优先权（）最高优先权（HPF）算法）算法 按照就绪队列中进程的优先级进行调度，高优先级的进程优先被调度。优先级确定原则：优先级确定原则：进程类型：系统进程类型：系统用户，前台用户，前台后台，实时后台，实时一般一般资源需求：需求小资源需求：需求小需求大需求大到达时间：先到到达时间：先到后到后到用户类型：用户自己确定用户类型：用户自己确定55A. 静态优先级算法静态优先级算法优先级算法优先级算法静态优先级算法静态优先级算法动态优先级算法动态优先级算法 进程的优先级在进程创建时确定，不再更改。进程的优先级在进程创建时确定，不

26、再更改。算法简单算法简单系统开销相对动态优先级小系统开销相对动态优先级小低优先级进程可能得不到调度低优先级进程可能得不到调度56B. 动态优先级算法动态优先级算法 在创建进程时确定一个基本优先级，在进在创建进程时确定一个基本优先级，在进程执行过程中按照一定原则动态改变。程执行过程中按照一定原则动态改变。* * 就绪等待进程优先级随等待时间增加而就绪等待进程优先级随等待时间增加而升高升高* * 执行进程的优先级随执行进程的优先级随CPUCPU占用时间增加而占用时间增加而下降下降算法复杂算法复杂系统开销相对静态优先级大系统开销相对静态优先级大调度效果优于静态优先级调度效果优于静态优先级57（6）多

27、级队列反馈算法）多级队列反馈算法设置多个就绪队列，各队列优先级不同设置多个就绪队列，各队列优先级不同从高优先级队列开始调度，采用时间片原则从高优先级队列开始调度，采用时间片原则高优先级队列调度完毕，继续调高优先级队列调度完毕，继续调度下一优先级队列度下一优先级队列58注意：注意：优先级越高的队列，分配越短的时间片优先级越高的队列，分配越短的时间片1进程的优先级是动态变化的进程的优先级是动态变化的2如果进程的时间片用完而进程还未执行如果进程的时间片用完而进程还未执行完，则进程回到的是下一优先级队列的完，则进程回到的是下一优先级队列的队尾队尾3长进程的在等待长时间后将获得长时间长进程的在等待长时间

28、后将获得长时间片，使周转时间减少片，使周转时间减少4592.2.4 进程的互斥与同步进程的并发执行进程的并发执行资源的竞争资源的竞争结果的不可再现结果的不可再现进程同步进程同步目标：目标：实现资源的有效共享，保证结果的可再现。60进程间的同步关系例1：正常行车正常行车到站停车到站停车开车开车售票售票开车门开车门关车门关车门司机司机售票员售票员合作合作合作合作61进程间的同步关系例2：打印进程打印进程1 1打印进程打印进程2 2打印打印打印打印互斥互斥获得打印数据获得打印数据获得打印数据获得打印数据62进程间的同步关系例3：计算进程计算进程打印进程打印进程计算结果送到计算结果送到Buffer从从

29、Buffer中取数中取数Buffer互斥互斥完成数据计算完成数据计算打印打印通知打印进程打印通知打印进程打印通知计算进程通知计算进程送下一个数送下一个数合作合作63进程同步时面临的两种主要关系：相互合作相互合作竞争资源竞争资源司机与售票员司机与售票员多个打印者多个打印者计算者与打印计算者与打印者者进程的同步：进程的同步：完成同一任务的进程间，由于需要在某些位置上协调它们的工作而相互等待，相互交换信息所产生的制约关系。进程的互斥：进程的互斥：由于多个进程共享同一资源而产生的相互制约的关系。同步机制：同步机制： 实现进程互斥与同步的机制。64临界资源与临界区：以互斥关系共享的资源。临界资源：临界资

30、源：critical source一次（一个时刻）只允许一个一次（一个时刻）只允许一个进程访问（排他性）进程访问（排他性）临界区：临界区：进程中访问临界资源的代码区。进入区：进入区：退出区：退出区：释放临界资源申请进入临界区剩留区：剩留区：代码的其它部分65进程代码的组成：66同步机制应遵循的原则空闲让进空闲让进忙则等待忙则等待有限等待有限等待让权等待让权等待无进程处于临界区，可让一新无进程处于临界区，可让一新进程进入进程进入有进程处于临界区，其余进程有进程处于临界区，其余进程必须等待必须等待进程进入临界区的要求必须在进程进入临界区的要求必须在有限时间内满足有限时间内满足等待进入临界区的进程，

31、其等待进入临界区的进程，其CPU占用必须释放占用必须释放67临界资源锁机制为临界为临界资源加资源加一个一个“锁锁”锁变量锁变量LockTrue 资源在用资源在用False资源空闲资源空闲q每个进程必须按照以下过程操作临界资源：.关锁关锁进入临界区进入临界区开锁开锁.68例：例：.check: if ( Lock ! = 0)goto check; else Lock = 1;临界区临界区Lock进程进程1 1进程进程2 2unlock( Lock );.check: if ( Lock ! = 0)goto check; else Lock = 1;临界区临界区unlock( Lock);.6

32、9临界资源锁的特点：实现了进程互斥访问临界资源。实现了进程互斥访问临界资源。不遵循让权等待原则不遵循让权等待原则忙等：忙等：不断调用TS查询，占用处理机关锁操作不可被打断关锁操作不可被打断原语原语（例：引入（例：引入TSTS指令：关锁操作在一个指令周期内完成）指令：关锁操作在一个指令周期内完成）70信号量与P、V操作信号量是对具体共享资源的抽象描述；信号量是对具体共享资源的抽象描述；信号量的值为整数，表示资源使用情况；信号量的值为整数，表示资源使用情况；不同共享资源可以用不同的信号量表示。不同共享资源可以用不同的信号量表示。P操作操作申请分配一个资源申请分配一个资源V操作操作释放一个资源释放一

33、个资源信号量是比锁更高级的资源抽象方式信号量是比锁更高级的资源抽象方式PV操作均操作均是原语是原语71（1）信号量同步机制）信号量同步机制通过信号量通过信号量S和基于和基于S的的P、V操作实现操作实现P( S )S= S - 1S 0 ?进程继续执行进程继续执行临界区临界区/ /资源访问区资源访问区进程进入进程进入阻塞队列阻塞队列NYV ( S )S= S + 1S 0表示有表示有S个资源可用个资源可用; S=0表示无资源可用表示无资源可用; S0则则| S |表示表示S等待队列中的进程个数。等待队列中的进程个数。P、V操作必须成对出现，有一个操作必须成对出现，有一个P操作就一定有操作就一定有

34、一个一个V操作；当实现互斥时，它们处于同一进程；操作；当实现互斥时，它们处于同一进程；当实现同步时，它们则不在同一进程中出现。当实现同步时，它们则不在同一进程中出现。如果两个如果两个P操作在一起，那么它们的顺序至关重操作在一起，那么它们的顺序至关重要：一个同步要：一个同步P操作应在一个互斥操作应在一个互斥P操作前。操作前。两个两个V操作顺序无关紧要。操作顺序无关紧要。优点：简单，而且表达能力强（用优点：简单，而且表达能力强（用P、V操作可操作可解决任何同步互斥问题）解决任何同步互斥问题）缺点：不够安全；缺点：不够安全；P、V操作使用不当会出现死操作使用不当会出现死锁；遇到复杂同步互斥问题时实现

35、复杂。锁；遇到复杂同步互斥问题时实现复杂。802.2.5 进程的通信进程的通信：进程的通信： 并发执行的进程之间所进并发执行的进程之间所进行的信息交换。行的信息交换。进程进程通信通信低级通信低级通信高级通信高级通信消息缓冲通信消息缓冲通信管道通信管道通信信箱通信信箱通信81一、消息缓冲通信方式：方式：通过系统的通过系统的公共消息缓冲区公共消息缓冲区实现信息交换实现信息交换（1）系统管理空白缓冲区）系统管理空白缓冲区（2）发送者向系统申请空白缓冲区）发送者向系统申请空白缓冲区（4）发送者将填有消息的缓冲区挂到）发送者将填有消息的缓冲区挂到接收者的消息队列接收者的消息队列（5）接收者在适当时候从消

36、息队列中读取数据）接收者在适当时候从消息队列中读取数据（3）发送者向空白缓冲区填入信息）发送者向空白缓冲区填入信息sendreceive系统提供消息通信原语：系统提供消息通信原语： Send、Receive82Send ( receiver , m ) 申请缓冲区申请缓冲区 ； P ( mutex ) ; 填入消息填入消息 ； 消息插入消息队列消息插入消息队列 ； V ( mutex ) ; V ( sm ) ; Receive ( n ) P ( sm ) ； P ( mutex ) ; 取消息取消息 ； 释放缓冲区释放缓冲区 ； V ( mutex ) ; Send 原语原语Receive

37、 原语原语把以把以m为首址的发送区为首址的发送区中的消息复制到消息缓存区中中的消息复制到消息缓存区中把第一个消息缓存区中的数据把第一个消息缓存区中的数据复制到以复制到以n为首址的接收区中为首址的接收区中83二、信箱通信进程进程A进程进程B进程进程C进程进程D进程进程E中间中间实体实体信箱头：信箱名等相关信息信箱头：信箱名等相关信息信箱体：传递的信息信箱体：传递的信息信箱头信箱头（信箱名、口令）（信箱名、口令）信信格格信信格格信信格格信信格格信信格格存放多种格式消息存放多种格式消息84三、管道通信管道：管道：连接接收进程和发送进程的共享文件连接接收进程和发送进程的共享文件管道通信：管道通信：两个

38、进程之间利用共享文件进行两个进程之间利用共享文件进行信息交换信息交换对于管道的读写是互斥访问的对于管道的读写是互斥访问的写后读、读后写的同步关系写后读、读后写的同步关系只有在管道双方都存在时才能通信只有在管道双方都存在时才能通信管道管道（共享文件）（共享文件）进程进程2读出读出 写入写入管道管道（共享文件）（共享文件）进程进程1写入写入进程进程3读出读出852.2.6 进程的死锁死锁：死锁：由于资源分配不当，造成多个进程阻由于资源分配不当，造成多个进程阻塞而无法被唤醒继续执行的现象。塞而无法被唤醒继续执行的现象。生产一个资源生产一个资源P(S)P(empty)放入消息放入消息V(S)V(ful

39、l)P(S)P(full)取出消息取出消息V(S)V(empty)死锁死锁86死锁的原因：死锁的原因：1、资源分配不当、资源分配不当 ；2、进程推进顺序不对、进程推进顺序不对 ；产生死锁的必要条件：产生死锁的必要条件：1 1、资源访问的互斥条件、资源访问的互斥条件资源一旦获得后在资源一旦获得后在V(S)之前不放弃之前不放弃3 3、不剥夺条件、不剥夺条件进程在需要时才申请资源进程在需要时才申请资源进程对资源的申请是分步的进程对资源的申请是分步的2 2、请求和保持条件（部分分配条件）、请求和保持条件（部分分配条件）进程在申请新资源时，对旧资源仍然保持占用进程在申请新资源时，对旧资源仍然保持占用4

40、4、环路等待条件、环路等待条件存在进程存在进程资源环形链资源环形链87进程资源环形链：进程进程1 1资源资源2 2资源资源1 1进程进程2 21 1、从资源出发的箭头表、从资源出发的箭头表示已分配该资源示已分配该资源2 2、从进程出发的箭头表示、从进程出发的箭头表示进程正在申请资源进程正在申请资源表示原则：表示原则：进程进程1 1等待进程等待进程2 2占有的资源（资源占有的资源（资源2 2）；）；进程进程2 2等待进程等待进程1 1占有的资源（资源占有的资源（资源1 1）；）；形成了一个进程等待资源的环路。形成了一个进程等待资源的环路。88一、死锁的预防（方法一、死锁的预防（方法1 1）破坏死

41、锁产生的必要条件，预防死锁产生破坏死锁产生的必要条件，预防死锁产生1 1、破坏请求和保持条件、破坏请求和保持条件( (破坏部分分配条件）破坏部分分配条件）资源预分配资源预分配2 2、破坏不剥夺条件、破坏不剥夺条件阻塞进程释放所有的资源阻塞进程释放所有的资源3 3、破坏环路等待条件、破坏环路等待条件资源按序分配资源按序分配简单方便，利用率低，延迟大简单方便，利用率低，延迟大效率高，复杂，开销大效率高，复杂，开销大资源利用率不高，可能有浪费资源利用率不高，可能有浪费89二、死锁的避免（方法二、死锁的避免（方法2 2）资源预测分配：资源预测分配：分配资源前，检分配资源前，检查分配的安全性查分配的安全

42、性系统状态不安全：不分配资源系统状态不安全：不分配资源系统状态安全：分配资源系统状态安全：分配资源安全状态：安全状态：在当前的状态下，能找到一个正确的推进顺序满在当前的状态下，能找到一个正确的推进顺序满足所有的进程的资源需求，将它们推进完毕足所有的进程的资源需求，将它们推进完毕安全状态检测安全状态检测银行家算法银行家算法假设本次分配，检测分配后的系统状态是否安全假设本次分配，检测分配后的系统状态是否安全90例：条件例：条件 P1、 P2、 P3三个进程对同类资源竞争。三个进程对同类资源竞争。P1最大需要最大需要10个该资源，个该资源，P2最大需要最大需要4个，个，P3为为9个。个。该资源总数为该资源总数为12个。个。 已知当前时刻，系统状态已知当前时刻，系统状态 1、当前是否为安全状态、当前是否