哈工程考研课件-第3讲处理机调度.ppt

第三章 处理机调度(CPU调度) 3.1 处理机调度的基本概念 3.1.1 高级、低级和中级调度 3.1.2. 调度队列模型 3.1.3. 调度算法的评价准则 3.3 实时调度 3.4 CPU调度的实现 3.5死锁 死锁的基本概念 死锁的解决方案 （预防，避免，检测及解除） 资源分配图 3.5.1 死锁的基本概念 3.5.2产生死锁的四个必要条件 3.6 死锁的预防 3.6.1 强限制预防 3.6.2 避免死锁的银行家算法 3.7 死锁的检测与解除 3.7.1死锁的检测 3.7.2死锁的解除 课后题 3.破坏“循环等待”条件 采用资源有序分配法:允许进程动态申请资源, 对系统中所有资源编号, 进程申请资源时应严格按资源编号递增次序进行,否则不予分配。 P1： 申请1 申请3 申请4 … P2： 申请2 申请4 申请8 … Pn： 申请1 申请2 申请8 … … 缺点: 资源利用仍不充分 前面的三种方法由于限制太强, 资源利用率都不太高。能否放宽限制条件？ E.W.Dijkstra于1968年提出银行家算法, 此算法要事先知道每个进程对资源的最大需求量; 算法的基本思路:允许进程动态申请资源,但在每次分配资源前先对本次分配的安全性进行检查, 以判断这种分配是否可能导致死锁, 若分配可能导致系统死锁, 则不予分配, 否则分配该资源。(检查每次分配后是否仍存在安全分配序列) 显然, 此法避免了死锁且资源利用率高。 1. 安全序列： 如果进程序列{P1，…，Pn}对每个Pi(1≤i≤n)进程, 它以后尚需要的资源量不超过系统当前剩余资源量与所有Pj (j i ) 进程当前占有资源量之和, 则系统处于安全状态 (不会发生死锁),称此序列为安全序列。若系统不存在这样一个安全序列, 则称系统处于不安全状态,不安全状态可能引起系统死锁。 例如: 避免死锁的实质是如何使系统不进入不安全状态。 安全序列: P2, P1, P3 进程 最大需求 已分配 尚需要 可用 P1 10 5 5 3 P2 4 2 2 P3 9 2 7 2. 银行家算法(发贷款检查安全性, 先给能及时还贷者) 算法使用的数据结构： n:系统中进程的总数; m:资源类总数 当前可用向量 Available: ARRAY[1..m] of integer; 最大需求矩阵 Max:ARRAY[1..n,1..m] of integer; 已分配矩阵 Allocation: ARRAY[1..n,1..m] of integer; 尚需求矩阵 Need: ARRAY[1..n,1..m] of integer; Need[i,j]=MAX[i,j]-Allocatin[i,j] 本次请求向量 Request: ARRAY[1..m] of integer; 进程Pi的资源向量为： Max[i], Allocation[i], Need[i] 算法: 当进程Pi提出资源申请Request时, 执行下列步骤: (1). 若Request≤Need[i],转(2)否则错误返回 (2). 若Request≤Available, 转(3)否则进程等待 (3). 系统试探分配资源, 修改数据,则有: Available:=Available-Request; Allocation[i]:=Allocation[i]+Request; Need[i]:=Need[i]-Request; (4).系统执行安全性算法,检查如果按此分配后,系统新状态是安全的, 则将资源正式分配给进程Pi , 若新状态是不安全的, 则恢复原状态 进程Pi等待 3.安全性算法 设置工作向量 Work:系统可供给进程继续运行所需的m类资源数目 Finish:能执行完标志(可提供足够资源使进程完成) 安全性检查的步骤： (1) 初值: Work:=Available; Finish[ ]:=false; (2) 寻找满足条件的Pk： Finish[k]==false; 且 Need[k]≤Work;(向量比较) 如果不存在，则转(4) (3) Work:=Work+Allocation[k]; Finish[k]: