民第三章作业、处理机调度.ppt

死锁的原因和必要条件 预防死锁 资源独占(静态分配） 资源顺序分配 资源受控动态分配 （避免死锁） 发现死锁 （死锁检测） 解除死锁 八、死锁 进程P1 进程P2 ： ： 申请文件F 申请磁带机T r1 ：申请磁带机T … … r2: 申请文件F 释放磁带机T … 释放文件F 释放文件F … 释放磁带机T … 死锁例子 P1 P2 F 申请不同类型的资源 T 简单的死锁例子 F T P2 P1 请 求 已 分 配 请 求 配 分 已 进程资源图 原因：系统资源不足、进程推进顺序不合适； 必要条件 互斥条件 不剥夺条件 请求和保持条件 环路等待条件 产生死锁的原因和必要条件： 预防死锁 1、资源独占 静止分配方法，预先分配所有资源给请求进程，而且在请求的进程在获取资源运行后一直处于独占资源的状态。（破坏互斥） 缺点：资源利用率低、使用不方便。 2、资源顺序分配法 对系统提供的资源按编号顺序申请或释放（破坏环路等待） 缺点：资源利用率低、使用不方便。 ………. L2 L1 Lj Lmax 申请 释放 3、资源受控动态分配 分配给要运行的进程所需要资源的最大申请量，动态分配。 缺点：事先获取资源的最大需求量。 ? 资源 R1 R2 … Rj … Rm P1 a11 a12 … a1j … a1m P2 a21 a22 … a2j … a2m … … … … … … … Pi ai1 ai2 … aij … aim … … … … … … … Pn an1 an2 ? … anj … anm 进程 死锁检测 资源分配表: 进程 资源 P 1 P 2 … P j … P n R1 b11 b21 … b1j … bn1 R2 b12 b22 … b2j … bm2 … … … … … … … Rj b1j b2j … bij … bnj … … … … … … … Rm bm1 bm2 ? … bmj … bmn 进程等待表: 等待资源计数器C: 引起相应进程被阻塞的资源数目。 C1，C2，…….Cn 未阻塞队列L： 未阻塞的进程 检测算法如下: (1) 把未阻塞(Ci=0)的进程Pi记录在L表中(其全部资源请求已得到满足的进程)； (2) 从L表中选择一进程，根据资源分配表S释放分配给该进程的所有资源； (3) 由进程等待表W依次检查和修改需要该进程释放资源的每一个进程的等待计数器Cj； (4) 若Cj=0，则表示该进程所请求的资源已得到满足，不再阻塞，将Pj记入L表中； (5)再从L表中选取另一进程，重复上述操作； (6) 若所有的进程都记入L表中，则系统初始状态为非死锁状态，否则为死锁状态。 解除死锁：释放进程或资源1、资源剥夺法 以花费最小资源数为依据，强行剥夺足够数量的资源给死锁进程。 还原算法、建立检查点2、撤消进程法 按照某种顺序逐渐地撤消已死锁的进程，直到获得为解除死锁所需要的足够可用的资源为止。 撤消代价最小的进程 小结: 进程：定义、状态、与程序的区别、与线程 的区别。 同步与互斥 同步原语P、V操作的定义、信号量概念 经典的同步与互斥问题 消息缓冲区的send和receive的实现 死锁问题 并发程序设计 （1）按先来先服务原则计算T、W 作 业 号? ? 1 ? ?2 ? 3 ?? ? 4 ?? 到达时间 8.00 8.50 9.00 9.50 运行时间 2.00 0.50 0.10 0.20 （2）按最短作业优先法计算T、W 作 业 号? ? 1 ? ?2 3 ??? ? 4 ?? 到达时间 8.00 8.50 9.00 9.50 运行时间 2.00 0.50 0.10 0.20 （3）按时间片轮转调度算法T、W（取时间片=4） 进??程??? ?P1 ??? P2????? P3 下一个CPU周期 ?? 24???? ??3 ????? 3 实验： 设计一个有N个进程并行的进程调度程序。进程调度调度算法：采用最高优先数法。每个进程有一个进程控制块（PCB ）表示，包括进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等。 开始 初始化PCB、输入信息 按优先数排列 队列空 结束 就绪队列首进程投入运行 时间片到，运行进程已占用CPU