第三章处理机调度与死锁
第三章 处理机调度与死锁
3.1处理机调度的层次
1.高级调度（HLS）：又称作业调度或长程调度(LTS)。功能：把外存上处于后备队列中的那些作业调入内存。调度对象是作业。
2.低级调度（LLS）：又称进程调度或短程调度（STS）。功能：（1）保存处理机的现场信息。（2）按某种算法选取进程。（3）把处理器分配给进程。调度对象是进程（或内核级线程）。
进程调度中的三种机制：（1）排队器。（2）分派器（分派程序）。（3）上下文切换机制。
进程调度的方式：非抢占方式和抢占方式。非抢占方式的优点：实现简单、系统开销小。适用于批处理系统环境，不适于实时系统中。抢占方式的优点：可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务。适用于实时系统。缺点是：开销大。抢占的原则：（1）优先权原则。（2）短作业（进程）有限原则。（3）时间片原则。
3.中级调度（ILS）又称中程调度（MTS）。功能是：提高内存利用率和系统吞吐量。适用于分时系统中。
选择调度算法和调度方式的准则面向系统的有：系统吞吐量高、处理机利用率好、各类资源的平衡利用。面向用户的有：周转时间短、响应时间快、截止时间的保证和优先权原则。
3.2调度队列模型和调度准则
1.调度队列模型的种类：（1）仅有进程调度的调度队列模型。（2）具有高级和低级调度的调度队列模型。（3）同时具有三级调度的调度队列模型。
周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔（称作业周转时间）。是评价批处理系统的性能。带权周转时间=（运行的时间+等待的时间）/运行时间
响应时间：是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。是评价分时系统的性能。
截止时间:是指某任务必须开始执行的最迟时间，或必须完成的必须时间。是评价实时系统的性能。
3.3调度算法
1.调度算法：是指根据系统的资源分配策略所规定的资源分配算法。
2.先来先服务和短作业（进程）优先调度算法。（1）先来先服务算法（FCFS）(FIFO)。既可用于作业调度，也可用于进程调度。有利于长作业（进程），不利于短作业（进程）只能采用非抢占调度方式。（2）短作业（进程）优先算法(SJF)(SPF).可以用于作业调度和进程调度。批处理系统多用此方法。其优点：能有效地降低作业的平均等待时间、提高系统吞吐量。缺点：不利于长作业。
3.高优先权优先调度算法（FPF）。常用于批处理系统中和实时系统中。
(1)优先权调度算法的类型：非抢占式优先权算法（主要用于批处理系统
中）。抢占式优先权调度算法（常用于较严格的事实系统和对性能要求较高的批处理和分时系统中）。
（2）优先权的类型：静态优先权和动态优先权。确定进程优先权的依据：（1）进程类型（2）进程对资源的要求（3）用户要求。
（3）高响应比优先调度算法：响应比=优先权=（等待时间+要求服务时间）/要求服务时间=响应时间/要求服务时间。优点：既照顾了短作业，又考虑了作业到达的先后顺序，不会使长作业长期得不到服务。
4.时间片轮转法：不适合作业调度，只能采用抢占方式。
5.多级反馈队列调度算法。
3.4实时调度
1.实时调度应具备的条件：（1）提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。
（2）系统处理能力：处理时间/周期时间<=1
（3）采用抢占式调度机制
（4）具有快速切换机制：对外部中断的快速响应能力、快速的任务分派能力。
2.实时调度算法的分类：（1）非抢占式调度算法：非抢占式轮转调度算法和非抢占式优先调度算法
（2）抢占式调度算法：基于时钟中断的抢占式优先权调度算法和立即抢占的优先权调度算法。
3.常用的几种实时调度算法：（1）最早截止时间优先（EDF）算法：既可用于抢占式调度，也可用于非抢占式调度方式中。包括：非抢占式优先调度算法用于非周期实时任务、抢占式调度方式用于周期实时任务。
（2）最低松弛度优先（LLF）算法：主要用于可抢占调度方式中。
3.5 产生死锁的原因和必要条件
1.死锁（deadlock）:指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，他们都将无法再向前推进。
2.产生死锁的原因：（1）竞争资源。（2）进程间推进顺序非法。
3.2.1竞争资源引起的进程死锁：（1）可剥夺和非剥夺性资源（2）竞争非剥夺性资源。（3）竞争临时性资源。
3.产生死锁的必要条件：（1）互斥条件（2）请求和保持条件。（3）不剥夺条件。（4）环路等待条件。
4.处理死锁的基本方法：（1）预防死锁。（2）避免死锁。（3）检测死锁。（4）解除死锁。
3.6 预防死锁的方法
1.预防死锁的方法有：（1）摒弃“请求和保持条件”：优点：简单、易于实现、安全。缺点：资源严重浪费、使进程延迟运行。
（2）摒弃“不剥夺条件”。缺点：实现复杂、延长进程周转时间、增加系统开销、降低系统吞吐量。
（3）摒弃“环路等待”条件。
2.安全状态：是指系统能按某
种进程顺利，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大要求，使每个进程都可顺利地完成。
3.7 死锁的检测与解除
1.常用解除死锁的方法：（1）剥夺资源。（2）撤消进程。