操作系统（ 第三章）知识点总结

3.处理机调度与死锁

3.1 处理机调度

  处理机是计算机系统的中的重要资源。

  处理机调度算法对整个计算机系统的综合性能指标有重要影响

  处理机调度的三个层次：高级调度（作业）、中级调度、低级调度（进程）

  进程调度要解决的问题：

  WHAT：按什么原则分配CPU——调度算法

  WHEN：何时分配CPU——调度的时机 （一个进程运行完毕或因某种错误终止运行、一个进程从运行态变为等待态（等待I/O）、分时系统中的时间片到、有一个优先级更高的进程就绪（抢占式）、执行中的进程执行了某种原语操作（阻塞原语））

  HOW：如何分配CPU——CPU调度过程（进程的上下文切换）

进程切换步骤：1.保存当前进程CPU的上下文（PC，寄存器）以及相关信息到运行中PCB中去

                 2.把该进程移至合适的队列——就绪、阻塞

                 3.从被选中的PCB中重装入CPU上下文

  选择调度方式和调度算法的准则

  面向系统：系统吞吐量高、处理机利用率好、各类资源的平衡利用、公平

  面向用户：周转时间短、响应时间快、截止时间的保证、优先权准则

 最优准则：最大的CPU利用率、 最大的吞吐量、最短的周转，等待，响应时间

周转时间：结束-进入  带权周转：周转/运行

  进程优先级：静态优先级、动态优先级  （与进程类型、进程对资源要求、用户要求有关）

  抢占/非抢占：可抢占式（有比正在运行进程优先级更高进程就绪时，系统可强行剥夺正在运行的CPU），不可抢占式

3.2 调度算法

  指根据系统资源分配所规定的资源分配算法

.先来先服务（FCFS）：按进程就绪的先后顺序来调度进程，分配处理机。

    有利于长作业（进程），不利于短作业。

.短作业优先(SJF)：能有效降低作业的平均等待时间，提高系统的吞吐量

对长作业不利、未考虑作业的紧张程度，作业的估计运行时间不准确

短进程优先调度算法（SPF）

.优先权调度算法(HPF)：非抢占式优先权算法（批处理系统、对实时性要求不高）、抢占式优先权算法（要求严格实时系统，性能要求较高的分时、批处理系统）。

高响应比优先调度算法(HRP)

  响应比：作业周转时间/作业处理时间

  优点：若作业等待时间相同，则处理时间越短，响应比越高，有利于短作业

        对于长作业，随等待时间增加，响应比增高，同样可获得处理机

        若处理时间相同，等待时间越长，响应比越高，为先来先服务

.时间片轮转调度算法(RR)

 多级反馈队列调度算法(MFQ)

  等待进程被唤醒时，进入原来的就绪队列（可能被抢占）

  当进程第一次就绪时，进入第一级队列

  多级反馈队列算法的性能：能较好满足各种类型用户的需要 （终端型用户、短批处理作业用户、长批处理作业用户）

短优先。输入/输出进程优先。运算型进程有较长的时间片。采用了动态优先级。采用了可变时间片。

3.3 实时调度 

 实现实时调度的基本条件

  1.提供必要的信息  2.系统处理能力强  3.采用抢占式调度机制  4.具有快速切换的机制 （要求快速硬件中断机构、允许中断的时间短）

  实时调度算法的分类

     按任务性质：硬实时和软实时

     按调度方式：非抢占和抢占

     按调度时间：静态和动态

  非抢占式调度算法：

     1.非抢占式轮转调度算法 （响应时间在几秒到数十秒之间，用于不太严格的实时控制系统，比如工业生产群控系统）

     2.非抢占式优先调度算法 （实时任务到达，放在就绪队列队首，等待当前任务的自我终止或运行完成，响应时间数百毫秒，用于较为严格的实时系统）

     3.基于时钟中断的抢占式优先权调度算法 （优先级高于当前任务的实时任务到达，则等到下一个时钟中断，抢占当前时钟处理机。响应时间：几到几十ms，应用于较严格的实时系统）

     4.立即抢占的优先权调度算法 （一旦出现请求中断的紧急任务，只要当前任务未在临界区，立即抢占它的CPU。响应时间100微秒到几毫秒，系统必须具有快速响应外部中断能力）

  常用的两种实时调用算法

   最早截止时间优先算法EDF （以开始截止时间确定优先级，可用于抢占式/非抢占式调度）

最低松弛度优先算法LLF （以任务紧急程度确定优先级，松弛度：必须完成时间-还需运行时间-当前时间，用于可抢占式）

 1.如果为每一个作业,只建立一个进程,则为了照顾短作业用户,应采用(         B),为照顾紧急作业的用户,应采用(  E  ),为能实现人机交互作用,应采用(C    ),而能使短作业,长作业及交互作业用户都比较满意时,应采用(D  )。

A.FCFS调度算法             B.短作业优先调度算法

C.时间片轮转法              D.多级反馈队列调度算法    E.基于优先权调度算法

2.作业调度是从(             后备作业队列        )中选出一批作业,为它们分配(   资源   ),并为它们创建(    进程   )。

3.最有利于提高系统吞吐量的作业调度算法是(       短作业优先              ),能对紧急作业进行及时处理的调度算法是(               优先权高者优先算法                          )。

4.在高响应比优先的调度算法中,当各个作业的等待时间相同时,( 短作业)将得到优先调度,当各个作业要求的运行时间相同时,(最先到达者(或等待时间最长的)      )将得到优先调度。.

5.下面     cd     算法与作业的执行时间有关。

a. 优先级调度    b. 时间片轮转

c. 短作业优先    d. 响应比高者优先      e.先来先服务

6.下面关于优先级的论述中，正确的是              。

a. 计算型作业的优先级高于I/O型作业的优先级

b. 短作业的优先级应高于长作业的优先级

c. 用户进程的优先级应高于系统进程的优先级

d. 作业对资源要求多的优先级应高于对资源要求少的优先级

e. 动态优先级调度中，作业优先级随着执行时间的增加而降低

7.如果系统中所有作业是同时到达的，则使作业平均周转时间最短的作业调度算法是   短作业优先        。

8. 确定作业调度算法时应注意系统资源的均衡使用，使   cpu繁忙   作业和   I/o 繁忙     作业搭配运行。

9.响应比调度算法综合考虑了作业的    等待       时间和      计算       时间

3.4 死锁的概念

在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等。而系统的运行性能在很大程序上取决于调度，因此调度便成为多道程序的关键。

       在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，多个进程的并发执行也带来了新的问题----死锁。

  定义：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源

  产生原因：1.竞争资源引起进程死锁（资源分配策略）   

            2.进程推进顺序不当引起死锁

  结论：1.参与死锁的进程最少是两个

        2.参与死锁是进程至少有2个已经占有资源

        3.参与死锁的所有进程都在等待资源

        4.参与死锁的进程是当前系统中所有进程的子集

       （死锁发生，会浪费大量系统资源，甚至导致系统崩溃！）

  产生死锁的必要条件

    互斥条件      （涉及的资源是非共享的）

    不剥夺条件    （不能剥夺进程拥有资源）

    请求保持条件  （进程在等待一新资源时继续占有已分配的资源）

    环路条件      （存在一种循环链，链中每一个进程已获得的资源同时被链中的下一个进程所请求）

   处理死锁的基本方法

    A.预防死锁  （设置某些限制条件，破坏死锁四个必要条件中的一个或多个）（较易实现，可能导致系统资源利用率和系统资源吞吐量降低）

    B.避免死锁  （在资源动态分配过程中，用某种方法去防止系统进入不安全状态）（实现较难）

  C.检测死锁   （事先不采取任何限制，不检查系统是否进入不安全区，允许发生死锁，可及时检测出死锁发生，精确确定发生死锁的进程和资源，采取适当措施，将系统中发生的死锁清除掉）

D.解除死锁    （将进程从死锁状态解脱出来）（撤销或挂起一些进程，回收一些资源，再将它们分配给处于阻塞状态的进程，使之转为就绪状态，实现难度大）

死锁的预防

 通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁。

1．互斥条件 ：无法破环，资源本身固有特性限制

2．破坏“请求和保持”条件 ：采用预先分配的策略

3．破坏“循环等待”条件：采用有序分配的策略

 4．破坏“非剥夺”条件 ：可以收回已分给进程且尚未使用完毕的资源。采用策略

 预先分配策略

系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要有一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源。

   缺点：资源严重浪费

        进程延迟进行

   安全状态：如果系统能按某种顺序为每个进程分配其所需的资源，直至所有进程都能运行完成，称系统处于安全状态，否则处于不安全状态

  处于不安全状态不一定会发生死锁，处于安全状态一定不会发生死锁！

  保证死锁不发生：r>=(m-1)*p+1 

  利用银行家算法避免死锁

死锁的避免定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。

最具有代表性的避免死锁算法是银行家算法（ Banker’s Algorithm） 。

   Available  可利用资源向量   MAX 最大需求矩阵   分配矩阵 ALLocation  需求矩阵 Need

1. 高级调度与低级调度的主要任务是什么?为什么要引入中级调度?

a. 作业调度又称宏观调度或高级调度，其主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存，输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利.

b. 进程调度又称微观调度或低级调度，其主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它.

c. 为了提高内存利用率和系统吞吐量，引入了中级调度.

 2. 在作业调度中需做出哪两个决定?

a. 接纳多少个作业;

b. 接纳哪些作业.

3. 选择调度方式和调度算法时，应遵循的准则是什么?

a. 面向用户的准则有周转时间短，响应时间快，截止时间的保证，以及优先权准则.

b. 面向系统的准则有系统吞吐量高，处理机利用率好，各类资源的平衡利用.

 4、在按时间片轮转调度算法中，在确定时间片的大小时，应考虑哪些因素?

a. 系统对响应时间的要求；

b. 就绪队列中进程的数目；

c. 系统的处理能力.

5、为什么说多级反馈队列能较好地满足各种用户的需要?

a. 对于终端型作业用户，由于终端型作业用户所提交的作业，大都属于交互型作业，系统只要能使这些作业(进程)在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意.

b. 对于短批处理作业用户，很短的批处理型作业如果仅在第一队列中执行一个时间片即可完成，便可获得与终端型作业一样的相应时间.对于稍长的作业，通常也只需在第二队列和第三队列中各执行一个时间片即可完成，其周转时间仍然很短.

c. 对于长批处理作业用户，用户也不必担心其作业长期得不到处理.

6、为实现实时调度，对实时系统提出了哪些要求?

a. 要提供必要的调度信息；

b. 在调度方式上要具体情况具体分析；

c. 要具有快速响应外部中断的能力；

d. 快速任务分派.

7、目前常用的调度方式和算法，能否应用到实时系统中?

a. 对于时间片轮转调度算法，是一种常用于分时系统的调度算法;

b. 对于非抢占式优先权调度算法，可用于要求不太严格的实时控制系统中;

c. 对于基于时钟中断抢占的优先权调度算法，有很好的响应效果，可用于大多数的实时系统中;

d. 对于立即抢占(Immediate Preemption)的优先权调度，要求操作系统具有快速响应外部时间的能力.

8、何谓死锁?产生死锁的原因和必要条件是什么?

a. 死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进;

b. 产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；

c. 必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件.

9、在解决死锁问题的几个方法中，哪种方法最容易实现?哪种方法使资源的利用率最高?

a. 解决死锁可归纳为四种方法: 预防死锁，避免死锁，检测死锁和解除死锁；

b. 其中，预防死锁是最容易实现的；

c. 避免死锁使资源的利用率最高.