第三章 处理机调度与死锁

---

3.1.1 处理机调度的基本概念

在多道程序环境下，内存中存在的进程数目往往多余处理机的数目，因此，需要通过处理机调度，动态的将 CPU 按某种算法分配给处于就绪状态的一个进程。

1. 处理机调度的层次

一个作业从提交时开始，需要进行三层调度。

2. 处理机调度的目标

调度方式和算法的选择取决与操作系统的类型及其目标，一般系统都要求调度能达到系统的吞吐量大、处理机的利用率高、各类资源能平衡利用以及对不同类型的作业具有公平性等目标。但是不同类型的系统通常还会又自己的要求，譬如，批处理系统希望周转时间短，分时系统要求相应时间快，而实时系统则要求能保证其截止时间等，因此它们将采用不同的调度方式和调度算法。

3.1.2 调度算法

1. FCFS

2. SJF

3. PSA

4. HRRN

5. RR

6. 多级队列调度

7. FB

3.1.3 实时调度

1. 实现实时调度的基本条件

实时系统中的任务通常都联系着一个截止时间，实时调度的关键时满足实时任务对截止时间的要求。

2. 实时调度方式和算法的选择

• 小型或要求不太严格的实时控制系统中，采用非抢占式轮转调度方式。
• 有一定要求的实时控制系统中，采用非抢占式优先权调度算法。
• 在要求比较严格的实时控制系统中，应采用比较复杂的抢占调度方式，如：基于时钟中断的抢占式优先权调度算法，立即抢占的优先权调度算法。

3. 常用的几种实时调度算法

• EDF
• LLF

4. 优先级倒置

优先级倒置指的是高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞的现象。

3.1.4 死锁的基本概念

1. 死锁的定义

2. 产生死锁的原因

3. 产生死锁的必要条件

3.1.5 处理死锁的基本方法

1. 预防死锁

预防死锁是通过破环产生死锁的某个必要条件来防止死锁的发生。四个必要条件中，后三个条件都可以被破坏，而第一个条件，即“互斥”条件，对某些像打印机这样的设备，可通过 Spooling 技术予以破坏，但其他资源，因受它们的固有特性的限制，不仅不能被破坏，反而应通过同步机制加以保证。

2. 避免死锁

在预防死锁的几种方法中，都施加了较强的限制条件，而在避免死锁的方法中，所施加的限制条件较弱，因而，有可能获得令人满意的性能。在该方法中，把系统的状态分为安全状态与不安全状态，只要能使系统始终都处于安全状态，便可避免死锁发生。

3. 死锁的检测与解除