计算机操作系统教案-第03章-处理调试与死锁.ppt

计算机操作系统教案第3章　处理机调度与死锁 郭霞 2010?中山 第三章 处理机调度与死锁 教学要求： 1、理解和掌握：处理机调度的基本概念，FCFS和SJ(P)F调度算法，高优先权优先调度算法，基于时间片的轮转调度算法，产生死锁的原因、必要条件和处理死锁的基本方法，预防死锁的方法，利用银行家算法避免死锁。 2、理解：最低松弛度优先LLF算法，系统安全状态。 3、了解：实时调度，多处理机系统中的调度(成组调度)，死锁的检测与解除。 Outline 处理机调度的基本概念 调度算法 实时调度 多处理机系统中的调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除 时间片大小的确定 选择小的时间片，有利于短作业，但会频繁发生中断、进程上下文的切换，增加系统的开销 选择太长的时间片，每一个进程都能在一个时间片内完成，退化为FCFS,无法满足交互式要求 *选择大多数进程可在一个时间片内完成 例子：P95 本章小结 本章主要讲述了处理机调度的一些基本概念，3种调度队列模型，选择调度方式和算法的准则，介绍了FCFS、SJ(P)F优先调度算法，高优先权调度算法和基于时间片的轮转调度算法(着重要掌握多级反馈队列调度算法)，产生死锁的原因和必要条件，预防死锁的方法(银行家算法)及其死锁的检测与解除。同时简略地介绍了实时调度的相关算法和多处理机系统中的调度。 习题 1、考虑下面的进程集合.列出先来先服务、短作业优先、高优先级三种算法，如图3-4的表。 习题 2、考虑下面的进程集合.列出先来先服务、短作业优先、高优先级三种算法，如图3-4的表。 习题 3、5个批作业A.B.C.D.E，同时到达计算机中心。他们的估计运行时间分别为15,9,3,6,12分钟，他们的优先级（外部定义）6,3,7,9,4(值越小，表示的优先级越高)。对下面的几种调度算法，确定每个进程的周转时间和所有作业的平均周转时间，并解释是如何得到这个结果的。对于最后三种情况，假设一次只有一个作业运行直到它结束，并且所有作业都完全是受处理器限制的。 时间片为3分钟的循环算法 优先级调度 FCFS(A->B->C->D->E) 最短作业优先 4、假设系统中有M个可用资源, N 个进程，设每个进程需要的资源数为 W。 请按以下给出的 M、N 和 W ，哪些情况不会出现死锁？ M=3,N=2,W=3; 2）M=5,N=3,W=2; 3）M=6,N=3,W=3 5.假定某计算机系统有R1设备3台，R2设备4台，他们被P1,P2,P3,P4这4个进程互斥共享，且已知这4个进程均以下面所示的顺序使用现有设备： 申请R1?申请R2?申请R1?释放R1?释放R2?释放R1 请问系统中是否会发生死锁？如果有可能，请列举出一种情况，并画出表示死锁状态的进程-资源图。 实 验 1、用程序实现银行家算法。 2、用程序实现死锁检测算法。 进阶 1、用程序模拟一个单道批处理操作系统。 2、用程序模拟一个多道批处理操作系统。 3、用程序模拟一个分时操作系统。 4、用程序模拟一个实时操作系统。 5、模拟实现各种进程调度算法。 9 3 D 1 2 C 9 1 B 1 0 A 处理时间 到达时间 进程名 图 3-13 进程之间通信时的死锁 竞争临时性资源 不可能死锁 P1:Release(S1);Request(S3) P2:Release(S2);Request(S1) P3:Release(S3);Request(S2) 可能的死锁 P1: Request(S3);Release(S1) P2: Request(S1);Release(S2) P3: Request(S2) ;Release(S3) 2. 进程推进顺序不当引起死锁 1) 进程推进顺序合法 图 3-14 进程推进顺序对死锁的影响 2) 进程推进顺序非法 若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1, P2保持了资源R2, 系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2: Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁。 3.5.2 产生死锁的必要条件 互斥条件 ：一次只有一个进程可以使用一个资源。 (2) 请求和保持条件 ：当一个进程等待其他资源， 可以占有已分配的资源。 (3) 不剥夺条件 ：不能从已经占有资源的进程中剥夺该资源 (4) 环路等待条件 ：存在一个封闭的进程链，使得每一个 进程至少占有链中下一个进程所需