计算机操作系统第三版ppt_重难点3.ppt

例如，以下四个作业先后到达系统进入调度： 作业名 到达时间 所需CPU时间 作业1 0 20 作业2 5 15 作业3 10 5 作业4 15 10 最短作业优先法 SJF的作业调度顺序为作业1、3、4、2， 平均作业周转时间T = (20+15+20+45)/4 = 25 平均带权作业周转时间W = (20/20+15/5+25/10+45/15)/4 = 2.25 FCFS调度算法 如果对它们施行FCFS调度算法， 平均作业周转时间T = (20+30+30+35)/4 = 28.75 平均带权作业周转时间W = (20/20+30/15+30/5+35/10)/4 = 3.13 高响应比优先算法 ?开始只有作业1，被选中执行时间20； ?作业1执行完毕，响应比依次为1+15/15、1+10/5、1+5/10，作业3被选中，执行时间5； ?作业3执行完毕，响应比依次为1+20/15、1+10/10，作业2被选中，执行时间15； ?作业2执行完毕，作业4被选中，执行时间10； 平均作业周转时间T = (20+15+35+35)/4 = 26.25 平均带权作业周转时间W = (20/20+15/5+35/15+35/10)/4 = 2.42 死锁的定义 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为进程死锁，这一组进程就称为死锁进程 关于死锁的一些结论 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃 练习：有三类资源A(17)、B(5)、C(20)。有5个进程P1—P5。T0时刻系统状态如下： 问(1)、T0时刻是否为安全状态，给出安全系列。 (2)、T0时刻，P2: Request(0,3,4)，能否分配，为什么？ (3)、在(2)的基础上P4：Request(2,0,1)，能否分配，为什么？ (4)、 在(3)的基础上P1：Request(0,2,0)，能否分配，为什么？ 解：(1) T0时刻的出安全系列 (2) P2: Request(0,3,4) 因（ Available =2 3 3） Request(0,3,4) 所以不能分配 (3) P4：Request(2,0,1) (4) P1：Request(0,2,0) (4) P1：Request(0,1,0) ? P0请求：Reqest(0,1,0) 试探分配后 有安全系列如下 思考题 1、 一台计算机共8台磁带机，由N个进程共享，每个进程最多要3台，问N为多少时不会有死锁，为什么？ 2、有R1(2)、R2(1)两类资源和两个进程P1、P2，两个进程均以 申请R1?申请R2?申请R1?释放R1?释放R2?释放R1 顺序使用资源，求可能达到的死锁点，并画出此时的资源分配图。 解 当两个进程都执行完第1步后，无论哪个进程执行完第2步，以后，这两个进程再申请资源时就会死锁。 有环无死锁 3. 死锁检测中的数据结构 (1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。 (2) 把不占用资源的进程(向量Allocation∶=0)记入L表中， 即Li∪L。 (3) 从进程集合中找到一个Requesti≤Work的进程，做如下处理：① 将其资源分配图简化，释放出资源，增加工作向量Work∶=Work+Allocationi。 ② 将它记入L表中。 (4) 若不能把所有进程都记入L表中， 便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 Work ∶=Available; L∶={Li|Allocationi=0∩Requesti=0} for all Li  L do begin for all Requesti≤Work do begin Work∶=Work+Allocationi; Li∪L; end end deadlock := ﹁ (L={p1, p2, …, pn}); 3.7.2 死锁