计算机操作系统第三章（上） 处理机调度与死锁知识梳理与脑图

第三章（上）处理机调度与死锁知识梳理

一、 处理机调度的基本概念与层次

处理机调度是操作系统的核心功能之一，其核心目标是在多道程序环境下，合理地分配和回收处理机资源，以提高系统效率和资源利用率，满足不同用户和任务的需求。

1. 调度的三个层次：

• 高级调度（作业调度）：
• 对象： 作业（Job）。

• 功能： 决定将外存上处于后备队列的哪些作业调入内存，为其创建进程、分配必要的资源，并放入就绪队列。

• 发生频率： 低，通常几分钟一次。

• 中级调度（内存调度）：
• 对象： 进程。

• 功能： 将暂时不能运行的进程（如因等待I/O）调至外存等待（挂起状态），当内存有富余或进程具备运行条件时，再重新调入内存。目的是提高内存利用率和系统吞吐量。

• 发生频率： 中等。

• 低级调度（进程调度）：
• 对象： 进程（或内核级线程）。

• 功能： 按照某种算法，从就绪队列中选取一个进程，将处理机分配给它。这是操作系统中最基本、最频繁的调度。

• 发生频率： 很高，几十毫秒一次。

二、 进程调度

1. 进程调度的任务与机制：
任务： 保存当前进程的现场信息，按算法选择新进程，恢复新进程的现场并使其运行。
机制： 包括排队器（组织就绪队列）、分派器（切换上下文）、上下文切换器。

2. 调度方式：
非抢占式（非剥夺式）： 一旦把处理机分配给某进程，该进程会一直运行直至完成或发生阻塞事件主动让出。实现简单，但无法处理紧急任务。
抢占式（剥夺式）： 允许调度程序根据某种原则（如优先级、时间片）暂停正在执行的进程，将处理机分配给更重要的进程。能提供更好的响应性和公平性，是现代系统的主流方式。

3. 进程切换与上下文切换：
进程切换必然发生上下文切换，但上下文切换不一定是由进程切换引起（也可能是同一进程内的线程切换）。

三、 调度算法（本章重点）

调度算法的评价指标：CPU利用率、系统吞吐量、周转时间、等待时间、响应时间。

1. 先来先服务（FCFS）：
规则： 按作业/进程到达的先后顺序进行服务。
特点： 算法简单，公平。但不利于短作业，平均等待时间较长。

2. 短作业优先（SJF）/短进程优先（SPF）：
规则： 对预计运行时间最短的作业/进程优先服务。
特点： 能获得最小的平均等待/周转时间。但可能导致长作业“饥饿”，且运行时间难以准确预估。

3. 高响应比优先（HRRN）：
规则： 在每次调度时，计算每个就绪作业的响应比 R = (等待时间 + 要求服务时间) / 要求服务时间，选择R最高的作业。
特点： 是FCFS和SJF的折中，既考虑了等待时间（防止饥饿），又考虑了运行时间。

4. 时间片轮转（RR）：
规则： 将所有就绪进程按FCFS原则排成一个队列，每次调度将CPU分配给队首进程，但仅执行一个时间片。时间片用完后，由计时器发出时钟中断，调度程序将该进程送到就绪队列末尾，并让新的队首进程执行。
特点： 专为分时系统设计，公平、响应快。时间片大小是关键：太大退化为FCFS；太小则上下文切换开销过大。

5. 优先级调度算法（PSA）：
规则： 为每个进程赋予一个优先级，调度时选择优先级最高的进程。优先级可以静态设定或动态调整（如根据等待时间增长而提高）。
特点： 可用于实时系统。可能导致低优先级进程饥饿。

6. 多级队列调度算法（MQ）：
* 规则： 将就绪队列划分为多个独立队列，每个队列有自己的调度算法（如系统进程队列用RR，交互进程队列用FCFS）。队列之间通常采用固定优先级或时间片划分的方式进行调度。

7. 多级反馈队列调度算法（MFQ）：
规则： 是MQ与时间片轮转的结合与进化。设置多个优先级不同的队列，新进程进入最高优先级队列。每个队列的时间片大小不同，优先级越高的队列时间片越小。进程在当前队列的一个时间片内未完成，则被降级到下一级队列。只有高优先级队列为空时，才调度低优先级队列的进程。
特点： 是公认的综合性较好的一种调度算法，能较好地满足各种类型用户的需求：短作业优先完成、长作业不会长期得不到服务、I/O密集型进程能获得较高响应优先级。

四、 死锁概述

1. 死锁的定义：
在多道程序系统中，由于竞争资源或进程间通信不当，导致一组进程中的每一个进程都在无限期地等待被该组中另一个进程所占有的资源，从而导致所有进程都无法向前推进的现象。

2. 产生死锁的必要条件（四个，必须同时成立）：
互斥条件： 资源在一段时间内只能被一个进程使用。
请求和保持条件（占有并等待）： 进程在持有至少一个资源的又请求新的资源，而该资源被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
不可剥夺条件（非抢占）： 进程已获得的资源在未使用完之前，不能被其他进程强行夺走，只能由该进程主动释放。
循环等待条件： 存在一个进程-资源的环形等待链。

3. 处理死锁的基本方法：
预防死锁： 破坏死锁四个必要条件中的一个或多个（静态策略）。
破坏“请求和保持”：一次性申请所有资源（资源预分配）。

• 破坏“不可剥夺”：允许剥夺资源。

• 破坏“循环等待”：对资源类型进行线性排序，要求进程按序申请。

• 避免死锁： 在资源动态分配过程中，用某种方法（如银行家算法）防止系统进入不安全状态（动态策略）。
• 检测与解除死锁： 允许死锁发生，通过检测机构及时发现，并采取撤销进程或剥夺资源等措施解除死锁。
• 忽略死锁： 如大多数操作系统对死锁问题采取不理睬的策略，因为死锁并非频繁发生，且预防和避免的代价较高。

---

本章（下）预告： 将深入讲解银行家算法的原理与示例、死锁的检测与解除的具体方法，并结合实例进行综合分析。

---

脑图关键词索引：
调度层次（高/中/低） -> 进程调度（任务/方式/切换） -> 调度算法（FCFS, SJF, HRRN, RR, PSA, MQ, MFQ） -> 死锁（定义，四必要条件，处理策略：预防/避免/检测解除/忽略）。