操作系统-第3章(2)(第四版)

1、第三章处理机调度与死锁 3.4实实 时时 调调 度度 一、实现实时调度的基本条件一、实现实时调度的基本条件提供必要的信息；提供必要的信息； 就绪时间、截止时间、处理时间、资源要求、优先级；就绪时间、截止时间、处理时间、资源要求、优先级；系统处理能力强；系统处理能力强； 对单处理机对单处理机： m m个周期性硬实时任务；处理时间：个周期性硬实时任务；处理时间：CiCi；周期时间：；周期时间：PiPi 满足：满足：采用抢占式调度机制；采用抢占式调度机制；具有快速切换机制：具有快速切换机制： 对外部中断的快速响应能力。对外部中断的快速响应能力。( (具有快速硬件中断机构具有快速硬件中断机构) ) 快

2、速的任务分派能力。（快速任务切换，减少任务切换时间）快速的任务分派能力。（快速任务切换，减少任务切换时间） 11miiiPC第三章处理机调度与死锁 二、实时调度算法的分类（二、实时调度算法的分类（调度方式的不同调度方式的不同）1 1非抢占式调度算法非抢占式调度算法-适用：不太严格，小型实时系统适用：不太严格，小型实时系统1) 1) 非抢占式轮转调度算法非抢占式轮转调度算法 适用：适用：工业生产的群控系统，不太严格实时系统；响应：数秒工业生产的群控系统，不太严格实时系统；响应：数秒数十秒数十秒计算计算机机对象对象实时实时任务任务轮轮 转转第三章处理机调度与死锁 2) 2) 非抢占式优先调度算法非

3、抢占式优先调度算法适用：较严格实时系统；响应：数百毫秒适用：较严格实时系统；响应：数百毫秒调用调用就绪队列就绪队列新新任务任务插入队首插入队首当前任务当前任务CPU完成或终完成或终止被调用止被调用优先优先级高级高第三章处理机调度与死锁 2 2抢占式调度算法抢占式调度算法- -适用：较严格实时系统适用：较严格实时系统基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法 适用：大多数实时系统；响应：几十毫秒适用：大多数实时系统；响应：几十毫秒 几毫秒几毫秒 新新任务任务当前任务当前任务CPU产生时钟产生时钟中断抢占中断抢占优先级高优先级高等等待待时钟中断时钟中断第三章处理机调度与死

4、锁 2) 2) 立即抢占立即抢占(Immediate Preemption)(Immediate Preemption)的优先权调度算法的优先权调度算法 适用：大多数实时系统；响应：几毫秒适用：大多数实时系统；响应：几毫秒100100微秒微秒 只要当前任务未处于临界区，便立即剥夺当前任务的执行。只要当前任务未处于临界区，便立即剥夺当前任务的执行。第三章处理机调度与死锁 三、常用的几种实时调度算法三、常用的几种实时调度算法1 1最早截止时间优先即最早截止时间优先即EDF(Earliest Deadline First)EDF(Earliest Deadline First)算法算法算法：算法：根

5、据任务的开始截止时间来确定任务的优先级。截止时间愈早，根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。其优先级愈高。 要求：要求：系统中保持一个实时任务就绪队列，该队列按各任务截止时间系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序；的早晚排序； 适用：适用：抢占式调度、非抢占式调度。抢占式调度、非抢占式调度。 第三章处理机调度与死锁 该算法用于该算法用于非抢占式调度方式非抢占式调度方式示例。在该例子中具有四个非周期示例。在该例子中具有四个非周期任务，它们先后到达。任务，它们先后到达。 任务1任务执行任务到达任务任务1 1t图图3-9 DEF3-9 DEF

6、算法用于非抢占式调度方式算法用于非抢占式调度方式任务3任务4任务2任务任务2任务任务3任务任务4开始截止时间开始截止时间： 任务1的任务3的 任务4的任务2的结束结束下下一一步步下下一一步步第三章处理机调度与死锁 2 2最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)LLF(Least Laxity First)算法算法算法：算法：根据根据任务紧急任务紧急( (或松弛或松弛) )的程度，来确定任务的优先级。的程度，来确定任务的优先级。 任务的紧急程度愈高，优先级就愈高。任务的紧急程度愈高，优先级就愈高。 例如：例如：一个任务在一个任务在200 ms200 ms时必

7、须完成，它本身所需的运行时间有时必须完成，它本身所需的运行时间有100 100 msms，该任务的紧急程度，该任务的紧急程度( (松弛程度松弛程度) )为为100 ms100 ms。 实现：实现： 一个按松弛度排序的实时任务就绪队列；一个按松弛度排序的实时任务就绪队列； 松弛度最低（最紧迫）的任务排在队列最前面；松弛度最低（最紧迫）的任务排在队列最前面； 调度程序选择就绪队列中的队首任务执行。调度程序选择就绪队列中的队首任务执行。 适用：适用：可抢占调度可抢占调度第三章处理机调度与死锁 例：一个实时系统中有两个例：一个实时系统中有两个周期性实时任务周期性实时任务，A和和B，任务，任务A要求要求

8、每每20ms执行一次执行一次，执行时间为，执行时间为10ms；任务；任务B只要求每只要求每50ms执行一次执行一次，执行时间执行时间25ms。 对于对于A，合适截止时间依次为，合适截止时间依次为20、40、60、80、100 ; 对于对于B，合适截止时间依次为合适截止时间依次为50、100、150 ; 图图3-11 给出了给出了A和和 B截止的时间点。截止的时间点。 图图3-11 A3-11 A和和B B任务每次必须完成的时间任务每次必须完成的时间0 20 40 60 80 100 120 140 160 180 200A A A A A A A A A A t B B B B第三章处理机调度

9、与死锁 松弛度松弛度=必须完成的时间点必须完成的时间点 - 本身所需运行时间本身所需运行时间 - 当前时间当前时间:A1(10)B1(20) 0 10 20 30 40 50 60 70 80 90 100 t1 t2 t3 t4 t5 t6 t7 t8 t 图图3-12 3-12 利用利用LLFLLF算法对两个周期性实时任务进行调度算法对两个周期性实时任务进行调度A2(10) A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0时刻，计算A，B松弛度：A1= 20 10 0 = 10B1= 50 25 0 = 25t=10时刻，计算A，B松弛度：A2= 40 10 10 =

10、 20B1= 50 25 10 = 15t=30时刻，计算A，B松弛度：A2= 40 10 30 = 0B1= 50 5 30 = 15t=40时刻，计算A，B松弛度：A3= 60 10 40 = 10B1= 50 5 40 = 5t=45时刻，计算A，B松弛度：A3= 60 10 45 = 5B2= 100 25 45 = 30t=55时刻，计算A，B松弛度：A4= 80 10 55 = 35B2= 100 25 55 = 20t=70时刻，计算A，B松弛度：A4= 80 10 70 = 0B2= 100 10 70 = 20t=80时刻，计算A，B松弛度：A5= 100 10 80 = 1

11、0B2= 100 10 80 = 10结束结束下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步下下一一步步最低松弛度优先（最低松弛度优先（LLF） 第三章处理机调度与死锁 3.5产生死锁的原因和必要条件产生死锁的原因和必要条件 一、一、死锁的概念死锁的概念1.1.死锁问题死锁问题第三章处理机调度与死锁 2.2.死锁概念死锁概念 指多个进程因竞争指多个进程因竞争共享资源共享资源而造成的一种僵局，若无外力作用，这而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。些进程都将永远不能再向前推进。 即：一组进程中，每个进程都无限等待被该组进程中另一进程所

12、占即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。进程就称为死锁进程。 3.3.关于死锁的一些结论关于死锁的一些结论 1) 1) 参与死锁的进程最少是两个。参与死锁的进程最少是两个。 2) 2) 参与死锁的进程至少有两个已经占有资源。参与死锁的进程至少有两个已经占有资源。 3) 3) 参与死锁的所有进程都在等待资源。参与死锁的所有进程都在等待资源。 4) 4) 参与死锁的进程是当前系统中所有进程的子集。参与死锁的进程是当前系统中所有进程的子集

13、。 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。第三章处理机调度与死锁 4. 4.永久性资源和临时性资源永久性资源和临时性资源永久性资源：永久性资源：可以被多个进程多次使用（可再用资源）可以被多个进程多次使用（可再用资源）可抢占资源可抢占资源( (可剥夺可剥夺) )；如：主存、；如：主存、CPUCPU不可抢占资源（不可剥夺）；如：打印机不可抢占资源（不可剥夺）；如：打印机临时性资源：临时性资源：只可使用一次的资源；如信号量，中断信号，同步信号只可使用一次的资源；如信号量，中断信号，同步信号（可消耗性资源）（可消耗性资源） “

14、“申请申请-分配分配-使用使用-释放释放”模式模式第三章处理机调度与死锁 二、产生死锁的原因二、产生死锁的原因 产生的根本原因产生的根本原因是系统能够提供的资源数少于需要该资源的进是系统能够提供的资源数少于需要该资源的进程数程数(系统资源不足系统资源不足)。 1） 竞争系统资源竞争系统资源(不可剥夺不可剥夺)。 2） 进程的推进顺序不当进程的推进顺序不当 。 死锁起因是并发进程的资源竞争，死锁起因是并发进程的资源竞争，但资源竞争并不一定产生死锁但资源竞争并不一定产生死锁。第三章处理机调度与死锁 1. 竞争系统资源（竞争系统资源（非可剥夺）非可剥夺） 若系统中只有一台打印机若系统中只有一台打印机

15、R1和一台磁带机和一台磁带机R2，可供，可供进程进程P1和和P2共享。若形成环路，这样会产生死锁。共享。若形成环路，这样会产生死锁。 实质：可共享资源不足。实质：可共享资源不足。第三章处理机调度与死锁 2.进程的推进顺序不当进程的推进顺序不当 在进程在进程P1和和P2并发执行时，按照左图曲线所示顺序推进时，并发执行时，按照左图曲线所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线的顺序两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线的顺序推进时，进入不安全区推进时，进入不安全区D内，两进程再推进会产生死锁。内，两进程再推进会产生死锁。第三章处理机调度与死锁 三、产生死

16、锁的必要条件三、产生死锁的必要条件 1 1）互斥条件。）互斥条件。进程对其所要求的资源进行排它性控制，即一次只有一进程对其所要求的资源进行排它性控制，即一次只有一个进程可以使用一个资源。个进程可以使用一个资源。 2 2）请求和保持条件。请求和保持条件。进程已经保持了至少一个资源，但又提出了新的进程已经保持了至少一个资源，但又提出了新的资源请求。资源请求。 3 3）不剥夺条件。不剥夺条件。进程所获得的资源在未被释放之前，不能被其它进程进程所获得的资源在未被释放之前，不能被其它进程强行剥夺。强行剥夺。 4 4）环路条件。）环路条件。在发生死锁时，必然存在一个进程资源的循环等待链，在发生死锁时，必然

17、存在一个进程资源的循环等待链， P1P1P2P2 R1 R1 R2 R2被占有被占有 被占有被占有 请求请求 请求请求 第三章处理机调度与死锁 四、处理死锁的基本方法四、处理死锁的基本方法 1. 预防死锁预防死锁 原理：原理：设置某些限制条件，破坏产生死锁的四个必要条件中的一个或设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。几个条件，来预防发生死锁。 优点：优点：较简单、直观的。较简单、直观的。 缺点：缺点：导致系统资源利用率和系统吞吐量降低。导致系统资源利用率和系统吞吐量降低。 1) 1) 弃弃“互斥条件互斥条件”。 为了破坏资源使用的互斥条件，就要允许多个

18、进程同时访问共享资源。为了破坏资源使用的互斥条件，就要允许多个进程同时访问共享资源。但是这种方法受到资源本身固有特性的限制，对某些资源是行不通的。例但是这种方法受到资源本身固有特性的限制，对某些资源是行不通的。例如打印机，就不允许多个进程在其运行期间交替打印数据，打印机只能互如打印机，就不允许多个进程在其运行期间交替打印数据，打印机只能互斥使用。而文件，可能允许多个进程对其进行读访问，但只允许互斥地写斥使用。而文件，可能允许多个进程对其进行读访问，但只允许互斥地写访问。访问。 总之：由于受限于资源本身，互斥条件难以破坏。总之：由于受限于资源本身，互斥条件难以破坏。 第三章处理机调度与死锁 2)

19、 2) 弃弃“请求和保持请求和保持”条件条件 第一种协议：第一种协议： 策略：策略：资源一次性分配。资源一次性分配。(资源的静态分配策略资源的静态分配策略) 优点：优点：简单、易于实现，且很安全。简单、易于实现，且很安全。 缺点：缺点： （1 1）资源严重浪费。一个进程一次获得其所需的全部资源且独占，）资源严重浪费。一个进程一次获得其所需的全部资源且独占，其中可能有些资源其中可能有些资源很少使用很少使用，甚至在整个运行期间都，甚至在整个运行期间都未使用未使用，这就严重地，这就严重地恶化了系统资源利用率。恶化了系统资源利用率。 （2 2）进程延迟运行。仅当进程获得其所需全部资源后，方能开始运）进

20、程延迟运行。仅当进程获得其所需全部资源后，方能开始运行，但可能有许多资源长期被其它进程占用，致使进程推迟运行，这往往行，但可能有许多资源长期被其它进程占用，致使进程推迟运行，这往往要经过很长的时延。（饥饿现象）要经过很长的时延。（饥饿现象）第三章处理机调度与死锁 第二种协议：第二种协议： 策略：策略：一个进程只获得初期所需资源后，开始运行。运行过程逐步释一个进程只获得初期所需资源后，开始运行。运行过程逐步释放已分配、已用完的全部资源，再请求新的所需资源。放已分配、已用完的全部资源，再请求新的所需资源。 如进程任务如进程任务: :（1 1）数据从磁带机复制到磁盘文件；（）数据从磁带机复制到磁盘文

21、件；（2 2）对磁盘文件进）对磁盘文件进行排序；（行排序；（3 3）打印机打印结果；）打印机打印结果； 分析：分析： 按第一协议必须开始请求获得按第一协议必须开始请求获得磁带机、磁盘文件、打印机磁带机、磁盘文件、打印机；打印机最；打印机最后用，即影响效率又影响其他进程运行，还有可能打印机得不到，推迟运后用，即影响效率又影响其他进程运行，还有可能打印机得不到，推迟运行。行。 按第二协议开始只需请求磁带机和磁盘文件，便可运行。等任务前按第二协议开始只需请求磁带机和磁盘文件，便可运行。等任务前（1 1）、（）、（2 2） 完成后释放磁带机和磁盘文件，再请求磁盘文件和打印机。完成后释放磁带机和磁盘文件

22、，再请求磁盘文件和打印机。可以提高设备利用率和减少进程饥饿现象。可以提高设备利用率和减少进程饥饿现象。 第三章处理机调度与死锁 3 3）弃）弃“不剥夺不剥夺”条件条件 策略：策略：申请未果，则放弃。申请未果，则放弃。 问题：问题： 1 1）实现比较复杂，代价很大。）实现比较复杂，代价很大。 2 2）一个资源在使用一段时间后被释放，可能会造成前阶段工作的失）一个资源在使用一段时间后被释放，可能会造成前阶段工作的失效，即使采取某些防范措施，也还会使前后两次运行的信息不连续。效，即使采取某些防范措施，也还会使前后两次运行的信息不连续。 3 3）还可能由于反复地申请和释放资源，使进程的执行无限推迟。这

23、）还可能由于反复地申请和释放资源，使进程的执行无限推迟。这不仅延长了进程的周转时间，还增加了系统开销，又降低了系统吞吐量。不仅延长了进程的周转时间，还增加了系统开销，又降低了系统吞吐量。第三章处理机调度与死锁 4 4）弃）弃“环路等待环路等待”条件条件 策略：策略：资源资源有序有序分配策略。分配策略。 做法：做法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。求资源，释放则相反。 编号的原则：编号的原则：较为紧缺的资源给以一个较大的序号。较为紧缺的资源给以一个较大的序号。 优点：优点：较前两种策略，资源利用率

24、和系统吞吐量，都有显著的改善。较前两种策略，资源利用率和系统吞吐量，都有显著的改善。 问题：问题： a. a. 限制了新设备类型的增加；限制了新设备类型的增加； b. b. 发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源发生作业使用资源的顺序与系统规定顺序不同的情况，造成资源的浪费，如：某进程先用磁带机，后用打印机，但按系统规定，它应先申的浪费，如：某进程先用磁带机，后用打印机，但按系统规定，它应先申请打印机，后申请磁带机，致使打印机长期闲置。请打印机，后申请磁带机，致使打印机长期闲置。 c. c. 限制了用户简单、自由的编程。限制了用户简单、自由的编程。第三章处理机调度与死锁 2.

25、2.避免死锁避免死锁( (允许动态申请资源允许动态申请资源) ) 预防死锁的几种策略问题：预防死锁的几种策略问题：严重地损害了系统性能。严重地损害了系统性能。 死锁避免定义：死锁避免定义： 在系统运行过程中，对进程发出的每一个在系统运行过程中，对进程发出的每一个系统能够满足的资源申请系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。发生死锁，则不予分配，否则予以分配。 由于在避免死锁的策略中，由于在避免死锁的策略中，允许进程动态地申请资源允许进程动态地申请资源。因

26、而，系统。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。系统进入不安全状态，则将资源分配给进程；否则，进程等待。 其中最具有代表性的避免死锁算法是其中最具有代表性的避免死锁算法是银行家算法银行家算法。第三章处理机调度与死锁 P进程进程R资源资源动态动态申请申请系统是否满足系统是否满足申请资源要求？申请资源要求？否否不予不予分配分配检查检查是是试分试分配配新状态新状态系统进入系统进入新状态是否新状态是否安全？安全？检查检查不分配不分配等待等待不安全不安全

27、允许最允许最终分配终分配安全安全系统可用资源系统可用资源=申请资源申请资源思考：思考：1、什么是安全状态？、什么是安全状态？第三章处理机调度与死锁 1）安全状态与不安全状态）安全状态与不安全状态 安全状态安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。称系统处于不安全状态。 关键：关键：寻找一个进程推进安全序列。寻找一个进程推进安全序列。 结论：结论： a. a. 安全状态一定是没有

28、死锁发生的。安全状态一定是没有死锁发生的。 b. b. 并非所有的不安全状态都必然会转为死锁状态。并非所有的不安全状态都必然会转为死锁状态。 c. c. 避免死锁的实质：避免死锁的实质： 系统在进行资源分配时，如何使系统不进入不安全状态。系统在进行资源分配时，如何使系统不进入不安全状态。 第三章处理机调度与死锁 2 2) ) 安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P P1 1、P P2 2和和P P3 3，共有，共有1212台磁带机。进程台磁带机。进程P P1 1总共要总共要求求1010台磁带机，台磁带机，P P2 2和和P P3 3分别要求分别要求4 4台和台和9

29、9台。假设在台。假设在T T0 0时刻，进程时刻，进程P P1 1、P P2 2和和P P3 3已分别获得已分别获得5 5台、台、2 2台和台和2 2台磁带机，尚有台磁带机，尚有3 3台空闲未分配。台空闲未分配。进 程 最大需求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 T0 ： 共有共有1212台，可用台，可用3 3台台寻找到安全序列：寻找到安全序列： 结论：系统在结论：系统在T0时刻是安全的。时刻是安全的。第三章处理机调度与死锁 由安全状态向不安全状态的转换由安全状态向不安全状态的转换 例如：在例如：在T0时刻以后，时刻以后，P3又请求又请求1台磁带机；台磁带机；

30、T0 ：转变转变新状态：新状态：结论：无法找到安全序列；系统在新状态下是不安全的。结论：无法找到安全序列；系统在新状态下是不安全的。 P3请求请求1台磁带机后系统进入不安全状态，不可对其分配。台磁带机后系统进入不安全状态，不可对其分配。第三章处理机调度与死锁 4 4）利用银行家算法避免死锁）利用银行家算法避免死锁a a银行家算法中的数据结构银行家算法中的数据结构(1) (1) 可利用资源向量可利用资源向量Available。含有。含有m m个元素的数组。如：个元素的数组。如：Availablej=K，表示系，表示系统中现有统中现有Rj类资源类资源K个。个。初始值是系统中所配置的该类全部可用资源

31、的数目。初始值是系统中所配置的该类全部可用资源的数目。(2) (2) 最大需求矩阵最大需求矩阵MaxMax。这是一个这是一个n nm m的矩阵，系统中的矩阵，系统中n n个进程中的每一个进程对个进程中的每一个进程对m m类资源的最大需求。如：类资源的最大需求。如：Maxi,j=KMaxi,j=K，表示进程，表示进程i i需要需要RjRj类资源的最大数目为类资源的最大数目为K K。 (3) (3) 分配矩阵分配矩阵AllocationAllocation。这也是一个这也是一个n nm m的矩阵，系统中每一类资源当前已分配的矩阵，系统中每一类资源当前已分配给每一进程的资源数。如给每一进程的资源数。

32、如:Allocationi,j=K:Allocationi,j=K，则表示进程，则表示进程i i当前已分得当前已分得R RJ J类资源的数类资源的数目为目为K K。(4) (4) 需求矩阵需求矩阵NeedNeed。这也是一个这也是一个n nm m的矩阵，表示每一个进程尚需的各类资源数。的矩阵，表示每一个进程尚需的各类资源数。如果如果Needi,j=KNeedi,j=K，则表示进程，则表示进程i i还需要还需要R R j j类资源类资源K K个，才能完成其任务。个，才能完成其任务。上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi, j=Maxi, j-Allocationi,

33、j Needi, j=Maxi, j-Allocationi, j 第三章处理机调度与死锁 b b安全性算法安全性算法判断状态是否安全。判断状态是否安全。 关键：关键：寻找一个进程安全的推进序列。寻找一个进程安全的推进序列。 描述如下：描述如下：(1) (1) 设置两个向量：设置两个向量： 工作向量工作向量WorkWork，表示系统可提供表示系统可提供给进程继续运行给进程继续运行所需的各类资源数所需的各类资源数目，它含有目，它含有m m个元素，在执行安全算法开始时，个元素，在执行安全算法开始时，Work:=AvailableWork:=Available。 FinishFinish，它表示系统

34、是否有它表示系统是否有足够的资源分配足够的资源分配给进程，使之运行完成。给进程，使之运行完成。开始时先做开始时先做Finishi:=falseFinishi:=false；当有足够资源分配给进程时，再令；当有足够资源分配给进程时，再令Finishi:=trueFinishi:=true。第三章处理机调度与死锁 (2) (2) 算法算法 从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程： Finishi=falseFinishi=false； 未推进的进程未推进的进程 Needi,jWorkjNeedi,jWorkj；若找到，执行步骤；若找到，执行步骤(3)(3

35、)，否则，执行步骤，否则，执行步骤(4)(4)。当进程当进程PiPi获得资源后，可顺利执行，直至完成，并释放出分配给它获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：的资源，故应执行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=true；go to step 2go to step 2； 如果所有进程的如果所有进程的Finishi=trueFinishi=true都满足，则表示系统处于安全状态；都满足，则表示系统处于安全状态；否则，系统处于不安全状态。否则，系统处于

36、不安全状态。第三章处理机调度与死锁 例：判断当前状态是否是否安全的。例：判断当前状态是否是否安全的。假定系统中有五个进程假定系统中有五个进程PP0 0，P P1 1，P P2 2，P P3 3，P P4 4 和三类资源和三类资源AA，B B，CC，各种资源的数量分别为各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如图所示。时刻的资源分配情况如图所示。 图图3-16 T0时刻的资源分配表时刻的资源分配表第三章处理机调度与死锁 T T0 0时刻的安全性：时刻的安全性：安全的。安全的。 安全的进程推进序列：安全的进程推进序列：P1-P3-P4-P2-P0P1-P3

37、-P4-P2-P0图图3-17T0时刻的安全序列时刻的安全序列 第三章处理机调度与死锁 c c银行家算法银行家算法 当当P Pi i发出资源请求后发出资源请求后, , 如如: : Request ij=K，表示进程表示进程P P i i需要需要K K个个R R j j类类型的资源，系统按下述步骤进行：型的资源，系统按下述步骤进行： (1)(1)检查两前提检查两前提 如果如果Request ijNeedi,j 申请申请需要需要 如果如果RequestijAvailablej 申请申请可用可用 (2) (2) 系统试探系统试探分配分配资源给进程资源给进程P P i i，修改下面数据结构中的数值：，

38、修改下面数据结构中的数值：Availablej:= Availablej-RequestAvailablej:= Availablej-Request i ijj；Allocationi,j:= Allocationi,j+RequestAllocationi,j:= Allocationi,j+Request i ijj；Needi,j:= Needi,j-RequestNeedi,j:= Needi,j-Request i ijj；(3) (3) 系统执行安全性算法。系统执行安全性算法。若安全，才正式将资源分配给进程若安全，才正式将资源分配给进程P Pi i，以，以完成本次分配；否则，将本

39、次的试探分配作废，恢复原来的资源分配状态，完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程让进程P Pi i等待。等待。 第三章处理机调度与死锁 5 5）银行家算法之例）银行家算法之例假定系统中有五个进程假定系统中有五个进程PP0 0，P P1 1，P P2 2，P P3 3，P P4 4 和三类资源和三类资源AA，B B，CC，各种资源的数量分别为各种资源的数量分别为1010、5 5、7 7，在，在T T0 0时刻的资源分配情况如图所示。时刻的资源分配情况如图所示。 图图3-16 T0时刻的资源分配表时刻的资源分配表第三章处理机调度与死锁 (1) (1) T T0 0

40、时刻的安全性：安全的时刻的安全性：安全的图图3-17T0时刻的安全序列时刻的安全序列 第三章处理机调度与死锁 (2) P1发出请求向量发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：系统按银行家算法进行检查： Request1(1，0，2)Need1(1，2，2) Request1(1，0，2)Available1(3，3，2) 系统先试为系统先试为P1分配资源，并修改分配资源，并修改Available，Allocation1和和Need1向量，形成新状态。向量，形成新状态。 两前提两前提修改后修改后 再利用安全性算法检查此时系统是否安全。再利用安全性算法检查此时系统是否

41、安全。第三章处理机调度与死锁 图图 3-17 P1申请资源时的安全性检查申请资源时的安全性检查 结论：找到了一个安全序列，系统是安全的结论：找到了一个安全序列，系统是安全的 ，可以为，可以为P1 分配资源分配资源第三章处理机调度与死锁 (3) (3) P P4 4请求资源：请求资源：P P4 4发出请求向量发出请求向量RequestRequest4 4(3(3，3 3，0)0)，系统按银行家算系统按银行家算法进行检查：法进行检查： RequestRequest4 4(3(3，3 3，0)Need0)Need4 4(4(4，3 3，1)1)； RequestRequest4 4(3(3，3 3，

42、0)Available(20)Available(2，3 3，0)0)，让，让P P4 4等待。等待。图图 ：已分配了：已分配了P1的资源分配表的资源分配表第三章处理机调度与死锁 优点：能时刻保证系统处于安全状态。优点：能时刻保证系统处于安全状态。缺点：需要不断进行测试，需花费较多时间。缺点：需要不断进行测试，需花费较多时间。借助银行家算法预测系统的安全性：借助银行家算法预测系统的安全性： 例如，某系统有同类资源例如，某系统有同类资源m m个，可并发执行且共享该类个，可并发执行且共享该类资源的进程最多资源的进程最多n n个，而每个进程申请该类资源的最大量为个，而每个进程申请该类资源的最大量为x

43、 x（1xm1xm），只要不等式），只要不等式n n（x-1x-1）+1m+1m成立，则系统一成立，则系统一定不会发生死锁。定不会发生死锁。 例题例题: : 某系统中有某系统中有1111台打印机，台打印机，N N个进程共享打印机资个进程共享打印机资源，每个进程要求源，每个进程要求3 3台。但台。但N N的取值不超过的取值不超过( ( ) )时，系统时，系统不会发生死锁。不会发生死锁。 A A4 B4 B5 C5 C6 6 D D7 7第三章处理机调度与死锁 3. 死锁的检测和解除死锁的检测和解除 当系统为进程分配资源时，若未采取任何当系统为进程分配资源时，若未采取任何限制性措施限制性措施来保证

44、不进入来保证不进入死锁状态，则系统必须提供检测和解除死锁的手段。死锁状态，则系统必须提供检测和解除死锁的手段。 系统做到：系统做到： 1)1)保存有关资源的请求和分配信息；保存有关资源的请求和分配信息； 2)2)提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 发现死锁发现死锁是根据死锁状态的定义，利用死锁描述中介绍的资源分配是根据死锁状态的定义，利用死锁描述中介绍的资源分配图来考察某一时刻系统状态是否合理，即是否能使所有进程都得到它们所图来考察某一时刻系统状态是否合理，即是否能使所有进程都得到它们所申请的资源而运行结束。申请

45、的资源而运行结束。 解除死锁：解除死锁：与检测死锁相配套的一种措施。与检测死锁相配套的一种措施。 方法：方法：剥夺资源、撤消进程剥夺资源、撤消进程 ； 死锁的检测和解除措施有可能死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐使系统获得较好的资源利用率和吞吐量量，但在实现上难度也最大。，但在实现上难度也最大。第三章处理机调度与死锁 一、调度的类型和层次一、调度的类型和层次1.1.调度层次调度层次 1 1）作业调度（高级调度）：批处理系统、运行频率低。）作业调度（高级调度）：批处理系统、运行频率低。 2 2）中级调度（交换调度）：解决内存紧张。）中级调度（交换调度）：解决内存紧张。 3

46、 3）进程调度（低级调度）：）进程调度（低级调度）：OSOS中必须配置、运行频率高。中必须配置、运行频率高。2 2、作业控制块、作业控制块JCBJCB：控制和管理作业运行。：控制和管理作业运行。 作业的作业的5 5个状态：个状态：“提交提交”、“后备后备”、“活动活动”、“完成完成”、“退出退出”。3 3、进程调度、进程调度 功能：功能： 1) 1) 保存处理机的现场信息。保存处理机的现场信息。 2) 2) 按某种算法选取进程。按某种算法选取进程。 3) 3) 把处理器分配给进程。由分派程序把处理器分配给进程。由分派程序(Dispatcher)(Dispatcher)把处理器分配给进程。把处理

47、器分配给进程。 从选中的进程从选中的进程PCBPCB中恢复处理机现场。中恢复处理机现场。 时机：时机： 1 1）进程运行结束；）进程运行结束； 2 2）执行中的进程发生某个等待事件；）执行中的进程发生某个等待事件； 3 3）分时系统时间片到；）分时系统时间片到； 4 4）在采用可抢占调度方式的系统中，当具有更高优先级的进程要求使用）在采用可抢占调度方式的系统中，当具有更高优先级的进程要求使用处理机。处理机。 总结：总结：第三章处理机调度与死锁 进程调度方式：进程调度方式： 1 1）非抢先调度方式）非抢先调度方式 2 2）可抢先调度方式）可抢先调度方式4 4、调度队列模型、调度队列模型 1 1、

48、2 2、3 3种。种。5 5、调度总则、调度总则 面向用户：面向用户： 1 1）周转时间短。评价批处理系统。）周转时间短。评价批处理系统。 2 2）响应时间快。评价分时系统。）响应时间快。评价分时系统。 3 3）截止时间的保证。评价实时系统。）截止时间的保证。评价实时系统。 4 4）优先权准则。都可遵循。）优先权准则。都可遵循。 面向系统：面向系统： 1 1）系统吞吐量高。）系统吞吐量高。 2 2）处理机利用率好。）处理机利用率好。 3 3）各类资源的平衡利用。）各类资源的平衡利用。第三章处理机调度与死锁 二、调二、调 度度 算算 法（法（重点重点）1.1.先来先服务调度算法先来先服务调度算法

49、(FCFS)(FCFS)： 适用：进程调度、作业调度适用：进程调度、作业调度 ，有利于长作业。，有利于长作业。2.2.短作业短作业( (进程进程) )优先调度算法（优先调度算法（SJ(P)FSJ(P)F） 适用：短作业，但会有适用：短作业，但会有“饿死饿死”现象。现象。3.3.高优先权优先调度算法（高优先权优先调度算法（HPFHPF） 适用：作业调度、进程调度适用：作业调度、进程调度 分类：分类： 1) 1) 非抢占式非抢占式 2 2）抢占式。）抢占式。 优先权的类型：优先权的类型： 1) 1) 静态优先权静态优先权 2 2）动态优先权）动态优先权4 4、高响应比优先调度算法（、高响应比优先调度算法（ HRP HRP ）5 5、基于时间片的轮转调度算法（、基于时间片的轮转调度算法（RRRR） 1 1）简单轮转法（固定时间片轮转法）简单轮转法（固定时间片轮转法） 2 2）多级反馈队列轮转法。）多级反馈队列轮转法。第三章处理机调度与死锁 三、实时调度三、实时调度1.1.实时调度的算法实时调度的算法 1 1）非抢占式轮转调度算法）非抢占式轮转调度