作系统课程第3章处理机调度.ppt

Page * * 11. 死锁的检测 允许死锁发生,OS应不断检测死锁是否发生 12. 资源分配图 结点集、边集、分配边、申请边 13. 死锁定理 资源分配图无环路, 则没有死锁, 有环路则可能存在死锁 若各资源类只含一个资源, 环路是死锁的充分必要条件 14. 资源分配图化简方法() (1)找只有分配边的进程结点,去掉分配边变为孤立结点 (2)把相应的资源分配给等待进程, 申请边变为分配边 重复(1) (2) 直到无法再化简, 若仍有环路则死锁发生 15. 死锁的解除(关键是代价最小)： 撤消进程、剥夺资源 课后题 三个进程共享四个资源, 这些资源的分配与释放只能一次一个, 已知每一进程 最多需要两个资源, 请问该系统会发生死锁码？试说明原因。 Page * 进程调度要解决的问题 处理机是计算机系统中的重要资源；处理机调度算法对整个计算机系统的综合性能指标有重要影响；可把处理机调度分成三个层次：高级调度、中级调度、低级调度 可把处理机调度分成三个层次 一般在批处理系统大多配有作业调度，而在其它系统中通常不需配置。它的执行效率较低，通常为几分钟调度一次 阻塞队列也可按阻塞原因设置多个 在引入中级调度后，可把就绪分为内存就绪和外存就绪（就绪挂起）；阻塞也可分为内存阻塞和外存阻塞（阻塞挂起） 选择什么样的调度策略取决于操作系统的类型及目标，用户的角度和系统的角度是不同的。 作业调度——FCFS，进程调度——FIFO 各进程为纯计算型，没有输入/输出 :注意：作业和进程调度的不同之处 （1）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；（2）仅当第1~(i-1) 队列均空时，才会调度第i队列中的进程运行 （3）如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程 How to Compute Safety Given: n kinds of resources p processes Set P of processes struct {resource needs[n], alloc[n]} ToDo[p] available[n] －－－－ while there exists a p in P such that for all i (ToDo[p].needs[i] available[i] ) { do for all i available[i] += ToDo[p].alloc[i]; P = P - p; } If P is empty then system is safe Page * * 因此 P1 申请 (1 0 2) 时安全 Page * * 若P0 继续申请2 B 假设分配2 B 给P0 Page * * 进行安全性检测 不安全！！ Page * * 银行家算法的特点 允许互斥、部分分配和不可抢占，可提高资源利用率； 要求事先说明最大资源要求，在现实中很困难； Page * * 1. 银行家算法中的数据结构 (1)可利用资源向量Available: ARRAY[1..m] of integer。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。 (2)最大需求矩阵Max: ARRAY[1..n,1..m] of integer 。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。 Page * * (3) 分配矩阵Allocation: ARRAY[1..n,1..m] of integer 。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need: ARRAY[1..n,1..m] of integer 。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Need[i,j]=Max[i