【操作系统】课程 4调度与死锁 同步测练 章节测验

4.1知识点导图

处理机调度与死锁相关内容的文字整理：

基本准则

• 资源利用率：使系统中的处理机和其他所有资源都尽可能地保持忙碌状态。
• 系统吞吐量：单位时间内系统所完成的作业数。
• 公平性：使各进程都获得合理的CPU时间，而不会发生进程饥饿现象。
• 响应时间：要尽可能短。
• 周转时间：周转时间和带权周转时间要尽可能短。

调度层次

• 高级调度：作业调度。
• 中级调度：内存调度。
• 低级调度：进程调度。

进程调度方式

• 非抢占调度方式。
• 抢占调度方式：
  • 优先级原则。
  • 短进程优先原则。
  • 时间片原则。

调度算法

• 先来先服务：按照作业到达的先后次序调度。
• 短作业优先：作业越短，优先级越高。
• 优先级：基于作业的紧迫程度由外部赋予优先级。
• 高响应比优先：响应比 = (等待时间 + 要求服务时间) / 要求服务时间。
• 轮转：就绪队列上的每个进程每次仅运行一个时间片。
• 多级反馈队列：划分多个就绪队列，不同队列的优先级不同。

死锁

• 死锁产生的原因：竞争资源，进程推进顺序非法。
• 死锁产生的必要条件：
  • 互斥条件。
  • 请求和保持条件。
  • 不可抢占条件。
  • 循环等待条件。

死锁预防

• 抛弃“请求和保持”条件。
• 抛弃“不可抢占”条件。
• 抛弃“循环等待”条件。

死锁避免

• 利用银行家算法避免死锁。

死锁的处理方法

• 检测死锁：保存有关资源的请求和分配信息，提供一种算法，利用上述信息检测系统是否已进入死锁状态。
• 解除死锁：
  • 抢占资源。
  • 终止死锁进程。

4.2调度类型与准则

【本章学习目标】

（1）了解实时调度；死锁的检测和与解除。

（2）理解处理机调度的层次和调度算法的目标；进程调度的机制和方式；死锁产生的原因。

（3）掌握常用的进程调度算法；死锁产生的必要条件和处理方法；银行家算法的实现。

【本节知识点】

在多道程序环境下，进程的数目往往大于处理机的数目，致使进程争抢处理机。这就要求系统按照某种算法，动态地分配处理机，使进程顺利运行，分配处理机的任务由进程调度程序完成。

（1）三级调度：对于进程的执行，操作系统必须进行3种类型的调度策略。高级调度确定何时允许一个新进程进入系统；中级调度完成的是内存、外存之间的对换；低级调度确定哪个处于就绪状态的进程可以得到处理机二运行。

（2）进程调度方式

• 可剥夺方式（抢占方式）：当一个进程正在处理机上运行，若有更较高优先级的进程需要进行处理，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。

• 不可剥夺方式（非抢占式）：当一个进程正在处理机上运行，若有更高优先级的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程主动让出处理机或结束，再将处理机分配给更高优先级的进程。

（3）调度性能的评价由“平均周转时间”和“平均带权周转时间”来衡量。

• 周转时间=完成时间-到达系统时间

• 带权周转时间=周转时间/有效运行时间

【章节测试】

一. 单选题（共4题）

1. 【单选题】 设有4个作业同时到达，每个作业执行时间是2min,它们在一台处理机按单道方式运行，则平均周转时间为（ ）。

   • A、1min
   • B、5min
   • C、2.5min
   • D、8min
   • 正确答案： B
   • 解析： 单道方式运行意味着一次只能运行一个作业。4个作业的总执行时间是8分钟，平均周转时间是总执行时间除以作业数，即8min / 4 = 2min。但这里的平均周转时间实际上是指从第一个作业到达开始到最后一个作业完成的总时间除以作业数，即(0+2+4+6)min / 4 = 5min。

2. 【单选题】 作业从提交到完成的时间间隔称为作业的（ ）。

   • A、周转时间
   • B、响应时间
   • C、等待时间
   • D、运行时间
   • 正确答案： A
   • 解析： 周转时间是指从作业提交到作业完成的总时间间隔，包括等待时间、运行时间等。

3. 【单选题】 下面选择调度算法的准则中不正确的是（ ）。

   • A、尽快响应交互式用户的请求
   • B、尽量提高处理机的利用率
   • C、尽可能提高系统的吞吐量
   • D、尽量增加进程的等待时间
   • 正确答案： D
   • 解析： 调度算法的目标之一是减少进程的等待时间，以提高效率和响应速度。

4. 【单选题】 下面（ ）说法是对可剥夺系统的正确描述。

   • A、时间片轮转法是一种可剥夺式调度
   • B、进程因等待某一事件而引起系统调度是一种可剥夺式调度
   • C、实时系统采用可剥夺式调度
   • D、优先级低的进程放弃CPU，让优先级高的进程运行
   • 正确答案： D
   • 解析： 可剥夺式调度是指当一个更高优先级的进程准备好时，当前运行的进程可以被剥夺CPU。选项D描述了可剥夺式调度的一个典型场景。

二. 判断题（共3题）

1. 【判断题】 当进程调度程序未能选中一个进程时，就绪队列和阻塞队列一定为空。

   • 正确答案： 错
   • 解析： 进程调度程序未能选中一个进程可能是因为所有进程都在阻塞队列中等待资源，此时就绪队列可能为空，但阻塞队列不一定为空。

2. 【判断题】 当进程调度程序未能选中一个进程时，就绪队列一定为空。

   • 正确答案： 对
   • 解析： 如果就绪队列不为空，调度程序总能从中选择一个进程来执行。

3. 【判断题】 在分时系统中，当用户数一定时，影响响应时间的主要因素是时间片。

   • 正确答案： 对
   • 解析： 时间片的大小直接影响了进程的响应时间，较小的时间片可以提供更快的响应，但可能会增加上下文切换的开销。

4.3调度算法

【本节知识点】

调度算法的好与否直接影响系统的性能，因此操作系统的研究者开发了许多调度算法，在一个实际的操作系统中可以根据需要和实现的复杂度考虑使用何种调度算法。

（1）先来先服务（FCFS）调度算法：按照进程进入就绪队列的先后次序来分配处理机。该算法采用不可剥夺方式，对短进程不利。适用于批处理系统，在其他类型的操作系统中，一般作为一种辅助的调度算法使用。

（2）短进程优先（SPN）调度算法：选择就绪队列中估计运行时间最短的进程分配处理机。该算法一般采用不可剥夺方式，适用于批处理系统。它能有效地缩短进程的平均周转时间，提高系统的吞吐量，但不利于长进程或紧急进程。

（3）优先权（Priority)调度算法：最常用的调度算法，选择就绪队列中优先权最高的进程分配处理机。可采用可剥夺方式，也可采用不可剥夺方式。

• 静态优先权：依据进程的类型、请求资源的情况、估计运行时间等因素，在进程创建时确定优先权，在进行整个运行期间不再改变。

• 动态优先权：创建进程时确定初始先权，在进程运行过程中，根据进程已占用处理机时间、等待时间等因素动态调整进程优先权。

（4）响应比高者优先（HRRN）调度算法：动态计算进程的响应比，选择响应比高的进程分配处理机。

• 响应比=（等待时间+运行时间）/ 运行时间

（5）时间片轮转（RR）算法：依次给就绪队列中的每个进程分配一定的时间（时间片），当执行完一个时间片后，进行如果没结束，就重新回到就绪队列尾部排队等待下一轮调度。时间片的大小受当前用户数和响应时间要求等因素的影响。该算法是分时系统采用的主要调度算法。

（6）多级反馈队列（MFQ）调度算法：均衡考虑各种因素进行进程调度的一种算法。

• 设置多个就绪队列，第一个就绪队列的优先级最高，其余就绪队列优先级依次降低。优先级越高的队列中，进程获得的时间片越短。

• 新进程进入第一个就绪队列，按先来先服务原则调度；若在给定的一个时间片内执行没结束，就进入第二个就绪队列，如此类推；在最后一个就绪队列中采用时间片轮转法调度。

• 仅当第1到第i-1个队列空闲时，调度程序才调度第i个队列中的进程。

【章节测试】

一. 单选题（共8题）

1. 【单选题】既考虑进程的等待时间，又考虑进程执行时间的调度算法是（ ）。

   A. 响应比高者优先

   B. 短进程优先

   C. 最短剩余时间优先

   D. 先来先服务

   正确答案：A

   解析： 响应比高者优先调度算法综合考虑了进程的等待时间和执行时间。响应比是等待时间与执行时间之和除以执行时间，因此该算法能够平衡长等待时间和短执行时间的进程.

2. 【单选题】下述（ ）调度算法要事先估计进程的运行时间。

   A. 响应比高者优先

   B. 短进程优先

   C. 优先级调度

   D. 先来先服务

   正确答案：B

   解析： 短进程优先调度算法需要事先估计进程的运行时间，以便根据进程的执行时间长短进行调度，优先调度执行时间短的进程.

3. 【单选题】如果所有进程同时到达，下述（ ）算法使进程的平均周转时间最短。

   A. 响应比高者优先

   B. 短进程优先

   C. 优先级调度

   D. 先来先服务

   正确答案：B

   解析： 短进程优先调度算法在所有进程同时到达的情况下，能够使进程的平均周转时间最短。因为它优先调度执行时间短的进程，从而减少了其他进程的等待时间.

4. 【单选题】下述（ ）调度算法适用分时系统。

   A. 时间片轮转

   B. 短进程优先

   C. 优先级调度

   D. 先来先服务

   正确答案：A

   解析： 时间片轮转调度算法适用于分时系统，因为它通过为每个进程分配一个固定的时间片，使得多个进程能够交替运行，从而提高了系统的响应性.

5. 【单选题】下列关于优先级设定的说法，（ ）正确。

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

   B. 资源要求多的进程的优先级应高于资源要求少的进程的优先级

   C. 随着进程的执行时间的增加，进程的优先级应降低

   D. 随着进程的执行时间的增加，进程的优先级应提高

   正确答案：C

   解析： 随着进程的执行时间的增加，进程的优先级应降低。这是因为长时间运行的进程可能已经得到了足够的CPU时间，降低其优先级可以让其他进程有机会运行，从而提高系统的公平性.

6. 【单选题】响应比高者优先作业调度算法，除了考虑进程在CPU上的运行时间，还考虑（ ）因素。

   A. 输入时间

   B. 完成时间

   C. 周转时间

   D. 等待时间

   正确答案：D

   解析： 响应比高者优先调度算法不仅考虑进程在CPU上的运行时间，还考虑进程的等待时间。响应比是等待时间与运行时间之和除以运行时间，因此该算法能够平衡长等待时间和短运行时间的进程.

7. 【单选题】设有3个作业，它们到达系统的时间和执行时间如下表。它们在一台处理机上按单道运行并采用短作业优先调度算法，则3个作业的执行次序是（ ）。

   作业名	到达时间	执行时间
   J1	8:00	2小时
   J2	8:00	1小时
   J3	8:30	0.2小时

   A. J1、J2、J3

   B. J2、J3、J1

   C. J3、J2、J1

   D. J2、J1、J3

   正确答案：B

   解析： 短作业优先调度算法根据作业的执行时间进行调度，优先执行执行时间短的作业。在本例中，J2的执行时间最短，其次是J3，最后是J1，因此执行次序为J2、J3、J1.

8. 【单选题】下述（ ）调度算法有利于CPU繁忙的进程，而不利于I/O繁忙的进程。

   A. 时间片轮转法

   B. 短进程优先

   C. 优先级调度

   D. 先来先服务

   正确答案：D

   解析： 先来先服务调度算法按照进程到达的顺序进行调度，有利于CPU繁忙的进程，因为这些进程通常会连续占用CPU。而I/O繁忙的进程在I/O操作期间会释放CPU，因此不利于它们的调度.

二. 判断题（共2题）

1. 【判断题】在分时系统中，当用户数一定时，影响响应时间的主要因素是时间片。

   正确答案：对

   解析： 在分时系统中，时间片的大小直接影响系统的响应时间。较小的时间片可以提高系统的响应性，因为进程能够更频繁地获得CPU时间，但同时也可能导致系统开销增加.

2. 【判断题】多级反馈队列属于不可剥夺调度算法，只有一个进程运行完毕时，其他进程才可运行。

   正确答案：错

   解析： 多级反馈队列属于可剥夺调度算法。它通过设置多个队列和不同的时间片，根据进程的行为动态调整其优先级和队列位置，允许进程在运行过程中被抢占，从而提高系统的响应性和公平性.

4.4死锁的基本概念

【本节知识点】

（1）死锁：一组竞争系统资源或相互通信的进程相互的永久阻塞。若无外力作用，这组进程将永远不能继续执行。处理死锁的方法通常有：预防、避免、检测和解除。

（2）产生死锁的原因：系统资源不足；进程推进顺序非法。

（3）产生死锁的四个必要条件：

• 互斥：进程竞争的资源是临界资源。

• 请求与保持：进程因请求新的资源被阻塞，同时不释放已分配到的资源。

• 不可剥夺：进程没使用完资源之前，不能被其他进程强行剥夺。

• 环路：一组进程对资源的请求和等待形成循环。

【章节测试】

一. 单选题（共4题）

1. 【单选题】若系统中有8台绘台仪，有多个进程均需要使用两台，规定每一个进程一次允许申请一台，则至多允许多少个进程参与竞争，则不会发生死锁。（ ）

   A. 5

   B. 6

   C. 7

   D. 8

   正确答案：C

   解析： 为了避免死锁，必须确保在最坏情况下，每个进程都能获得其所需的资源。假设每个进程最多需要2台绘台仪，且每次只能申请1台。如果有7个进程参与竞争，最坏情况下，每个进程都申请了1台绘台仪，此时还剩下1台绘台仪。此时，任何一个进程都可以获得其所需的第二台绘台仪，从而完成任务并释放资源，不会发生死锁。但如果超过7个进程，就有可能出现每个进程都申请了1台绘台仪，但无法获得第二台绘台仪的情况，从而导致死锁.

2. 【单选题】产生系统死锁的原因可能是（ ）。

   A. 一个进程死循环

   B. 多个进程竞争资源出现了循环等待

   C. 进程释放资源

   D. 多个进程竞争共享型设备

   正确答案：B

   解析： 死锁是由于多个进程竞争资源并出现循环等待的情况所导致的。在这种情况下，每个进程都在等待其他进程释放资源，但由于资源的分配形成了一个循环等待链，导致所有进程都无法继续执行.

3. 【单选题】以下关于死锁的叙述，（ ）是正确的。

   A. 死锁的产生只与资源的分配策略有关

   B. 死锁的产生只与并发进程的执行速度有关

   C. 死锁是一种僵持状态，发生时系统任何进程都无法继续执行

   D. 竞争互斥资源是进程产生死锁的根本原因

   正确答案：D

   解析： 死锁的根本原因是多个进程竞争互斥资源，并且这些资源的分配形成了循环等待。虽然资源的分配策略和进程的执行速度也会影响死锁的发生，但竞争互斥资源是导致死锁的根本原因.

4. 【单选题】关于死锁的现象，描述正确的是（ ）。

   A. 多个进程共享某一资源

   B. 多个进程竞争某一资源

   C. 每个进程等待着某个不可能得到的资源

   D. 每个进程等待着某个可能得到的资源

   正确答案：C

   解析： 在死锁状态下，每个进程都在等待某个不可能得到的资源，因为这些资源已经被其他进程占用，并且这些进程也在等待其他资源，形成了一个循环等待链，导致所有进程都无法继续执行.

二. 判断题（共5题）

1. 【判断题】死锁只发生在相互竞争资源的进程之间。

   正确答案：对

   解析： 死锁是由于多个进程竞争资源并出现循环等待的情况所导致的，因此只发生在相互竞争资源的进程之间.

2. 【判断题】锁死是指系统中所有进程都处于阻塞状态。

   正确答案：错

   解析： 锁死（死锁）是指一组进程因竞争资源而相互等待，导致这些进程都无法继续执行。系统中可能存在其他进程仍然正常运行，因此锁死并不意味着所有进程都处于阻塞状态.

3. 【判断题】死锁的多个进程之间竞争资源或彼此通信而引起的一种临时性的阻塞现象。

   正确答案：错

   解析： 死锁是一种长期的阻塞现象，而不是临时性的。一旦发生死锁，除非采取措施解除，否则这些进程将无法继续执行.

4. 【判断题】死锁的发生不仅与资源分配策略有关，还与并发进程的执行速度有关。

   正确答案：对

   解析： 死锁的发生确实与资源分配策略有关，但并发进程的执行速度也会影响死锁的发生。例如，进程的执行速度不同可能导致资源的分配顺序发生变化，从而影响死锁的形成.

5. 【判断题】当进程数大于资源数时，进程竞争资源也不一定会产生死锁。

   正确答案：对

   解析： 进程数大于资源数时，进程竞争资源可能会导致死锁，但不一定会发生死锁。死锁的发生还取决于进程的资源申请顺序和资源的分配策略等因素.

三. 填空题（共3题）

1. 【填空题】产生死锁的原因是（ ）和（ ）。

   正确答案：

   • 第一空：资源不足；资源竞争；系统资源不足；资源的竞争；竞争资源
   • 第二空：进程推进顺序非法；进程推进顺序不当

   解析： 死锁的产生主要是由于资源不足或资源竞争，以及进程推进顺序不当或非法导致的.

2. 【填空题】解决死锁通常采用预防，避免，检测和解除等方法，其中银行家算法属于（ ），资源的有序分配属于（ ），剥夺资源属于（ ）。

   正确答案：

   • 第一空：避免死锁的方法；避免死锁；避免
   • 第二空：预防死锁的方法；预防死锁；预防
   • 第三空：解除死锁的方法；解除死锁；解除

   解析： 银行家算法是一种避免死锁的方法，通过在分配资源前进行安全性检查来避免死锁的发生。资源的有序分配是一种预防死锁的方法，通过规定资源的申请顺序来避免循环等待。剥夺资源是一种解除死锁的方法，通过从某些进程中强制收回资源并分配给其他进程来解除死锁.

3. 【填空题】产生死锁的4个必要条件是（ )、（ ）、（ ）和环路条件。

   正确答案：

   • 第一空：互斥；互斥条件
   • 第二空：请求与保持；请求和保持；请求和保持条件；请求与保持条件
   • 第三空：不可剥夺；不可剥夺条件；不可抢占；不可抢占条件；不剥夺

   解析： 产生死锁的四个必要条件是互斥条件、请求与保持条件、不可剥夺条件和环路条件。只有当这四个条件同时满足时，才会发生死锁.

4.5死锁的预防与避免

（1）预防死锁：通过破坏产生死锁的必要条件来实现。

• 互斥是资源本身固有的属性，不可破坏。

• 资源的分配采取预先静态分配方法，可破坏请求与保持条件。

• 指定可剥夺策略：若进程请求新的资源不能被满足，必须释放已获得的资源。该策略可破坏不可剥夺条件。

• 采用资源有序分配方法，可破坏环路条件。

（2）避免死锁：银行家算法是具有代表性的避免死锁的算法。

      银行家算法思想：进程发出资源请求后，系统按以下步骤检查：

• 检查进程请求资源数（Request）和已获得的资源（Allocation）之和是否超过其最大需求数（Need），若超过，系统出错。

• 检查进程请求资源数（Request）是否小于系统当前可分配资源数（Available）。若超过，系统不能满足请求，进程等待。

• 系统预分配进程所请求的资源，启用安全检查算法检测系统是否处于安全状态，若安全，则实际分配，如不安全，则撤销预分配。

【章节测试】

一. 单选题（共4题）

1. 【单选题】采用有序分配资源的策略可以破坏产生死锁的（ ）。

   A. 互斥条件

   B. 请求与保持条件

   C. 不可剥夺条件

   D. 环路条件

   正确答案：D

   解析： 有序分配资源的策略通过规定资源的申请顺序，使得资源分配图中不可能形成环路，从而破坏了产生死锁的环路条件。环路条件是死锁发生的必要条件之一，因此通过有序分配资源可以有效预防死锁的发生.

2. 【单选题】以下解决死锁的方法中，属于预防策略的是（ ）。

   A. 化简资源分配图

   B. 银行家算法

   C. 资源的有序分配

   D. 死锁检测法

   正确答案：C

   解析： 预防死锁的策略是在系统设计阶段就采取措施，防止死锁的发生。资源的有序分配是一种预防策略，通过规定资源的申请顺序，避免循环等待的发生，从而预防死锁。化简资源分配图和死锁检测法属于检测策略，银行家算法属于避免策略.

3. 【单选题】预防死锁不可以去掉以下（ ）条件。

   A. 互斥

   B. 请求与保持

   C. 不可剥夺

   D. 环路

   正确答案：A

   解析： 在大多数情况下，资源的互斥条件是无法去掉的，因为许多资源在使用时必须是互斥的，以保证数据的一致性和系统的稳定性。因此，预防死锁通常只能通过消除其他条件，如请求与保持条件、不可剥夺条件或环路条件，而不能去掉互斥条件.

4. 【单选题】以下关于安全状态的说法（ ）正确。

   A. 安全状态时没有死锁的状态，非安全状态时有死锁的状态。

   B. 安全状态是可能有死锁的状态，非安全状态也是可能有死锁的状态

   C. 安全状态是可能有死锁的状态，非安全状态是有死锁的状态

   D. 安全状态是没有死锁的状态，非安全状态是可能有死锁的状态

   正确答案：D

   解析： 安全状态是指系统能够按照某种顺序执行所有进程，而不会发生死锁的状态。在安全状态下，系统没有死锁。非安全状态是指系统可能无法找到一个安全的执行顺序，从而可能产生死锁的状态。因此，安全状态是没有死锁的状态，非安全状态是可能有死锁的状态.

二. 判断题（共2题）

1. 【判断题】当系统处于不安全状态时，就一定会产生死锁。

   正确答案：错

   解析： 不安全状态是指系统可能无法找到一个安全的执行顺序，从而可能产生死锁的状态。然而，处于不安全状态并不意味着一定会发生死锁，因为进程的执行顺序和资源的申请情况可能会影响死锁的发生。系统在不安全状态下仍然有可能避免死锁的发生.

2. 【判断题】银行家算法是一种检测死锁的算法。

   正确答案：错

   解析： 银行家算法是一种避免死锁的算法，而不是检测死锁的算法。它通过在分配资源前进行安全性检查，确保系统始终处于安全状态，从而避免死锁的发生。死锁检测算法是在死锁已经发生或可能发生时，检测系统是否存在死锁的算法.

三. 填空题（共1题）

1. 【填空题】资源预先静态分配方法和资源有序分配方法分别破坏了产生死锁的（ ）条件和（ )条件。

   正确答案：

   • 第一空：请求与保持
   • 第二空：环路

   解析： 资源预先静态分配方法通过在进程开始执行前分配所有所需的资源，使得进程在执行过程中不再请求额外的资源，从而破坏了请求与保持条件。资源有序分配方法通过规定资源的申请顺序，避免了资源分配图中形成环路，从而破坏了环路条件.

4.6死锁的检测与解除

【本节知识点】

（1）资源分配图：描述进程和资源之间申请和分配关系的有向图。

（2）资源分配图用于死锁检测：当且仅当系统中资源分配图不可完全简化的时候，系统处于死锁状态。

（3）解除死锁：一旦检测到系统出现死锁，就要解除死锁。一般有两种方法：

• 剥夺某些进程的资源

• 撤销某些进程

【章节测试】

【单选题】以下（ ）方法可以解除死锁。

A. 挂起进程

B. 剥夺资源

C. 提高进程优先级

D. 降低进程优先级

正确答案：B

解析：死锁是指多个进程在执行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法向前推进。解除死锁的方法之一是剥夺资源，即从引起死锁的进程中强制收回一些资源，然后将这些资源分配给其他进程，从而打破死锁状态。其他选项如挂起进程、提高或降低进程优先级并不能直接解除死锁，因为它们没有解决资源的分配问题。