【学习笔记】计算机操作系统（三）—— 处理机调度与死锁

第三章 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。

处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。

3.1.1 处理机调度的层次

1、高级调度(High Level Scheduling)

• 高级调度又称作业调度 或 长程调度，它的调度对象是作业。

• 主要功能是根据某种算法，决定将外存上处于后备队列中的作业调入内存，为它们创建进程、分配必要的资源，并将它们放入就绪队列。

  每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

• 高级调度主要用于多道批处理系统中，而在分时和实时系统中不设置高级调度。

2、低级调度(Low Level Scheduling)

• 低级调度又称为进程/处理机调度 或 短程调度，其所调度的对象是进程(或内核级线程)。
• 主要功能是根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
• 进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的系统中，都必须配置这级调度。

3、中级调度(Intermediate Scheduling)

• 中级调度又称为内存调度 或 中程调度。
• 中级调度实际上就是存储器管理中的对换功能。
• 引入中级调度的主要目的是，提高内存利用率和系统吞吐量。
• 把那些暂时不能运行的进程，调至外存等待，此时进程的状态称为就绪驻外存状态(或挂起状态)。
• 当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。

长程调度：为避免调度本身占用太多的CPU时间，不宜使进程调度算法太复杂。作业调度往往是发生在一批作业已运行完毕并退出系统，又需要重新调入一批作业进入内存时，作业调度的周期较长，大约几分钟一次，因此又称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。

短程调度：进程调度的运行频率最高，在分时系统中通常仅10~100ms便进行一次进程调度，因此又称为短程调度。

中程调度：中级调度的运行频率基本上介于上述两种调度之间，因此又称为中程调度。

	要做什么	调度发生在…	发生频率	对进程状态的影响
高级调度(作业调度)	按照某种规则，从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存→内存 (面向作业)	最低	无→创建态→就绪态
中级调度(内存调度)	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存→内存 (面向进程)	中等	就绪挂起态→就绪态 阻塞挂起态→阻塞态
低级调度(进程调度)	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

3.1.2 处理机调度算法的目标

1、处理机调度算法的共同目标

• 资源利用率。提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态
  $$CPU的利用率=\frac{忙碌的时间}{总时间}=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$$

• 公平性。公平性是指应使诸进程都获得合理的CPU 时间,不会发生进程饥饿现象。公平性是相对的：

  • 对于相同类型的进程应获得相同的服务;
  • 对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。

• 平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

• 策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

2、批处理系统的目标

• 平均周转时间短。

  所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间:

  • 作业在外存后备队列上等待(作业)调度的时间，
  • 进程在就绪队列上等待进程调度的时间，
  • 进程在CPU上执行的时间，
  • 进程等待 I/O 操作完成的时间。

  $$(作业)周转时间=作业完成时间-作业提交时间$$

  应使作业周转时间和作业的平均周转时间尽可能短。
  $$平均周转时间T=\frac{各个作业周转时间之和}{作业数}=\frac{1}{n}[\sum _{i=1}^n{T}_i]$$

  $$\begin{gathered} 带权周转时间W=\frac{作业的周转时间T}{系统为它提供服务的时间T_s}=\frac{作业的完成时间-作业提交时间}{作业实际运行时间} \\ W必然\ge 1 \end{gathered}$$

  $$平均带权周转时间W=\frac{各个作业带权周转时间之和}{作业数}=\frac{1}{n}\sum _{i=1}^n\frac{T_i}{T_s}$$

• 系统吞吐量高。吞吐量是指在单位时间内系统所完成的作业数，与批处理作业的平均长度有关。
  $$系统吞吐量【一秒完成几道作业】=\frac{总共完成作业数}{总共花费的时间}$$

• 处理机利用率高。

3、分时系统的目标

• 响应时间快。所谓响应时间，是从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。【从用户提交请求到首次产生响应所用的时间】它包括三部分时间:
  • 请求信息从键盘输入开始，直至将其传送到处理机的时间;
  • 处理机对请求信息进行处理的时间;
  • 将所形成的响应信息回送到终端显示器的时间。
• 均衡性。是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。

4、实时系统的目标

• 截止时间的保证。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。避免丢失数据。

• 可预测性。在多媒体系统中避免品质降低。

  可预测性的例子：在多媒体系统中，电影或电视剧都应是连续播放的。连续播放无卡顿——可预测性

  直接单缓冲处理：

  读帧i → 播放帧i → 读帧i+1 → 播放帧i+1 → ...
  

  问题：读取帧（I/O操作）耗时不确定，可能导致播放不连续（如磁盘忙时帧延迟）。

  双缓冲（Double Buffering）处理:

  双缓冲通过并行处理读取和播放，分离两个任务：

  • Buffer A：用于播放当前帧（帧i）。
  • Buffer B：后台异步读取下一帧（帧i+1）。

  双缓冲的时序流程：

  • 初始状态：
    • Buffer A 已加载 帧1，开始播放。
    • Buffer B 异步加载 帧2（I/O操作）。
  • 播放 帧1 时：
    • Buffer B 完成 帧2 的读取（提前准备）。
  • 切换到 帧2：
    • 播放器切换至 Buffer B 播放 帧2。
    • Buffer A 立即开始异步加载 帧3（覆盖旧的 帧1）。
  • 循环往复：播放和读取永远交错进行，互不阻塞。

3.2 作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。

操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。

3.2.1 批处理系统中的作业

1、作业和作业步

• 作业(Job)。一个具体的任务：包含了程序和数据以及一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
• 作业步(Job Step)。通常在作业运行期间，每个作业都必须经过若干个相对独立,又相互关联的顺序加工步骤才能得到最终结果。我们把其中的每一个加工步骤称为一个作业步。各作业步之间存在着相互联系，往往是上一个作业步的输出作为下一个作业步的输入。

作业：编译运行一个C程序

作业步：

编辑代码 → 编译 → 链接 → 运行

• 独立：每个步骤是明确的（比如编辑代码和编译是两件事）。
• 关联：必须按顺序来，上一步的输出是下一步的输入（比如没编辑代码就不能编译，编译好的才能链接）。
• 最终结果：所有步骤完成后，才能得到最终结果。

2、作业控制块(Job Control Block，JCB)

• 为了管理和调度作业，每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息
• 通常在JCB中包含的内容有:作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。
• 步骤：
  • 每当一个作业进入系统时，便由“作业注册”程序为该作业建立一个作业控制块JCB。
  • 再根据作业类型，将它放到相应的作业后备队列中等待调度。
  • 调度程序依据一定的调度算法来调度它们，被调度到的作业将被装入内存。
  • 在作业运行期间，系统就按照JCB中的信息和作业说明书对作业进行控制。
  • 当一个作业执行结束进入完成状态时，系统负责回收已分配给它的资源，撤销该作业控制块。

3、作业运行的三个阶段和三种状态

需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。

• 收容阶段。操作员把用户提交的作业通过某种方式输入到硬盘上，再为该作业建立JCB，并把它放入作业后备队列中。此时作业的状态为“后备状态”。
• 运行阶段。当作业被作业调度选中后，便为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，直到它运行结束前，在此期间都处于“运行状态”。
• 完成阶段。当作业运行完成、或发生异常情况而提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。此时系统中的“终止作业”程序将会回收已分配给该作业的作业控制块和所有资源，并将作业运行结果信息形成输出文件后输出。

3.2.2 作业调度的主要任务

作业调度也称为接纳调度(Admission Scheduling)，主要任务是：

• 根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，
• 以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，
• 并为它们创建进程、分配必要的资源。
• 然后再将新创建的进程排在就绪队列上等待调度。

在每次执行作业调度时，都需做出以下两个决定:

• 接纳多少个作业

  在每一次进行作业调度时，应当从后备队列中选取多少作业调入内存，取决于多道程序度(Degree of Multiprogramming)，即允许多少个作业同时在内存中运行。
  多道程序度的确定是根据计算机的系统规模、运行速度、作业大小，以及能否获得较好的系统性能等情况作出适当的抉择的。

• 接纳哪些作业
  应选择后备队列中的哪些作业调入内存，取决于所采用的调度算法。

  • 最简单的是先来先服务调度算法，它是将最早进入外存的作业优先调入内存。
  • 较常用的一种算法是短作业优先调度算法，是将外存上所需执行时间最短的作业优先调入内存。
  • 另一种较常用的是基于作业优先级的调度算法，该算法是将外存上作业优先级最高的作业优先调入内存。
  • 比较好的一种算法是“响应比 高者优先”的调度算法。

在批处理系统中，作业进入系统后，总是先驻留在外存的作业后备队列上，因此需要有作业调度，以便将它们分批地装入内存。

在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都被直接送入内存，因而无需配置上述的作业调度机制，但也需要有某种接纳控制措施来限制进入系统的用户数目。

在实时系统中也不需要作业调度，而必需具有接纳控制措施。

3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法

1、先来先服务(first-come first-served，FCFS)调度算法 - 非抢占式

FCFS 算法既可用于作业调度，也可用于进程调度。

• 当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度【或者说它是优先考虑在系统中等待时间最长的作业】，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

• 当在进程调度中采用该算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其它进程。

FCFS算法在单处理机系统中已很少作为主调度算法，但经常把它与其它调度算法相结合使用，形成一种更为有效的调度算法。

优缺点：

• 优点: 公平、算法实现简单，不会出现饥饿现象。
• 缺点：排在长作业(进程)后面的短作业(进程)需要等待很长时间，带权周转时间很大。即FCFS算法对长作业有利，对短作业不利

2、短作业优先(short job first，SJF)的调度算法 - 非抢占式

• SJF算法是以作业所要求的运行时间的长短来计算优先级，作业越短，其优先级越高。
• SJF算法: 可以分别用于作业调度和进程调度【短进程优先(SPF,Shortest Process First)算法】。
• SJF/SPF算法: 每次调度时选择当前已到达且运行时间最短的作业/进程
• SJF算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
• SJF和SPF是非抢占式的算法。但是也有抢占式的 – 最短剩余时间优先算法(SRTN,Shortest Remaining Time Next)
• 优缺点：
  • 优点：“最短的”平均等待时间、平均周转时间
  • 缺点：
    • 必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间，但很难准确估计，而且是由用户提供的，不一定真实。
    • 对长作业非常不利，长作业的周转时间会明显地增长。可能使作业等待时间过长，会出现饥饿现象。
    • 人一机无法实现交互。
    • 完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

3.2.4 优先级调度算法和高响应比优先调度算法

1、优先级调度算法(priority-scheduling algorithm，PSA)

• 对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。
• 对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。
• 对于优先级调度算法，是基于作业的紧迫程度，由外部赋予作业相应的优先级，调度算法是根据该优先级进行调度的。可以保证紧迫性作业优先运行。
• 优先级调度算法可作为作业调度算法，也可作为进程调度算法。
• 用于作业调度时，系统是从后备队列中选择若干个优先级最高的作业装入内存。

2、高响应比优先调度算法(HighestResponse Ratio Next，HRRN) - 非抢占式

• 既考虑了作业的等待时间，又考虑作业运行时间的调度算法
• 既可用于作业调度，也可用于进程调度
• 为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。

$$响应比R_P=优先权=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$$

特点：

• ① 如果 作业的等待时间相同 ，则要求服务的时间愈短，其优先权愈高，因而类似于 SIF 算法，有利于短作业。

• ② 当 要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于 FCFS 算法。

• ③ 对于 长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。

• 实现了较好的折中。

• 不会出现饥饿现象。

缺点：在利用该算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

3.3 进程调度

进程调度是系统中必不可少的一种调度。因此在三种类型的系统中，都无一例外地配置了进程调度。

进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程调度的时机：

• 需要进行进程调度与切换的情况：

  • 当前运行的进程主动放弃处理机

    • 进程正常终止
    • 运行过程中发生异常而终止
    • 进程主动请求阻塞(如等待I/O)

  • 当前运行的进程被动放弃处理机

    • 分给进程的时间片用完
    • 有更紧急的事需要处理(如I/O中断)
    • 有更高优先级的进程进入就绪队列

• 不能进行进程调度与切换的情况：

  • 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  • 进程在操作系统内核程序临界区中。【进程处于临界区时不能进行处理机调度 - 这是错误的❌ - 必须是操作系统内核程序临界区】
  • 在原子操作过程中(原语)。原子操作不可中断，要一气呵成 (如修改PCB中进程状态标志，并把PCB放到相应队列)

  临界资源: 一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
  临界区：访问临界资源的那段代码。
  内核程序临界区：一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)

3.3.1 进程调度的任务、机制和方式

1、进程调度的任务

• 保存处理机的现场信息。在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。

• 按某种算法选取进程。调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。

• 把处理器分配给进程。由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。

2、进程调度机制

调度程序（scheduler）

• 排队器。事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。
• 分派器。分派器依据进程调度程序所选定的进程，将其从就绪队列中取出（新进程），并分配CPU资源给新进程。
• 上下文切换器。会发生两对上下文的切换操作:
  • 第一对上下文切换是OS将保存当前进程的上下文，即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元*。
  • 第二对上下文切换是移出分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。

调度程序工作内容

• 调度算法：应该让谁运行
• 时间片大小：运行多长时间

什么事件会触发“调度程序”?

• 创建新进程
• 进程退出
• 运行进程阻塞
• I/O中断发生(可能唤醒某些阻塞进程)
• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

闲逛进程

没有其他就绪进程时，运行闲逛进程(idle) —— 具有以下特点：

• 优先级最低
• 可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
• 能耗低

3、进程调度方式

非抢占方式(Non-preemptive Mode) - 非剥夺调度方式

• 只允许进程主动放弃处理机。除非该进程终止或发生异常而终止或主动要求进入阻塞态（如等待I/O），才能把处理机分配给其他进程。

• 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

抢占方式(Preemptive Mode) - 剥夺调度方式 - Linux 进程是抢占式的

• 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

• 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统

• “抢占”必须遵循一定主要原则：

  • 优先权原则，指允许优先级高的新到进程抢占当前进程的处理机。
  • 短进程优先原则，指允许新到的短进程(运行的时间短)可以抢占当前长进程的处理机。
  • 时间片原则，即各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。

3.3.2 时间片轮转调度算法(RR, Round-Robin) - 抢占式

• 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
• 用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
• 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到
• 不会出现饥饿现象。
• 优缺点
  • 优点: 公平; 响应快，适用于分时操作系统;
  • 缺点: 由于高频率的进程切换，因此有一定开销; 不区分任务的紧急程度。
• 时间片选取：
  • 一般来说，设计时间片时要让切换进程的开销占比不超过1%
  • 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。
  • 如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换(开销大)，从而导致实际用于进程执行的时间比例减少。

3.3.3 优先级调度算法

• 算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

• 既可用于作业调度，也可用于进程调度，也 可用于I/O调度 。

• 抢占式、非抢占式都有

• 就绪队列未必只有一个，可以按照不同优先级来组织。

• 也可以把优先级高的进程排在更靠近队头的位置

• 优先级分类：

  • 静态优先级:创建进程时确定，之后一直不变。
  • 动态优先级:创建进程时有一个初始值，之后会根据情况动态地调整优先级。
    • 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
    • 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
    • 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

• 优先级设置：

  • 系统进程优先级 高于 用户进程
  • 前台进程优先级 高于 后台进程
  • 操作系统更偏好 I/O型进程(或称 I/O繁忙型进程) 【与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)】
    I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

• 优缺点：

  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
  • 缺点：若源源不断地有高优先级进程到来，则**可能导致饥饿**

  

3.3.4 多队列调度算法

算法规则：

• 队列之间：可采取固定优先级，或时间片划分
  • 固定优先级:高优先级空时低优先级进程才能被调度
  • 时间片划分:如三个队列分配时间50%、40%、10%
• 队列之内：各队列可采用不同的调度策略，如：系统进程队列采用优先级调度；交互式队列采用RR；批处理队列采用FCFS

3.3.5 多级反馈队列(MLFQ, Multi-Level Feedback Queue)调度算法 - 抢占式

• 算法规则：
  • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  • 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  • 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
• 用于进程调度
• 抢占式。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
• 优缺点：
  • 优点：
    • 对各类型进程相对公平(FCFS的优点)
    • 每个新到达的进程都可以很快就得到响应(RR的优点)
    • 短进程只用较少的时间就可完成(SPF的优点)，且不必实现估计进程的运行时间(避免用户作假)
    • 可灵活地调整对各类进程的偏好程度，比如I/O密集型进程(可以将因I/O而阻塞的进程重新放回原队列，这I/O型进程就可以保持较高优先级)
  • 缺点：可能会出现饥饿现象

3.3.6 多处理机调度

单处理机调度 vs 多处理机调度

单处理机调度：一个CPU - 只需决定让哪个就绪进程优先上处理机即可。

多处理机调度：多个CPU - ① 用调度算法决定让哪个就绪进程优先上处理机; ②还需决定被调度的进程到底上哪个处理机

目标：

• 负载均衡：尽可能让每个CPU都同等忙碌
• 处理机亲和性：尽量让一个进程调度到同一个CPU上运行，以发挥CPU中缓存的作用(Cache)

1、公共就绪队列

• 所有CPU共享同一个就绪进程队列(位于内核区)
• 每个CPU空闲时运行调度程序，从公共就绪队列中选择一个进程运行，
• 每个CPU访问公共就绪队列时需要上锁(确保互斥)
• 优点: 可以天然地实现负载均衡
• 缺点: 各个进程频繁地换CPU运行，亲和性不好

如何提升处理机亲和性?

• 软亲和: 由进程调度程序尽量保证亲和性
• 硬亲和: 由用户进程通过系统调用，主动要求操作系统分配固定的CPU，确保亲和性

2、私有就绪队列

• 每个CPU都有一个私有就绪队列
• CPU空闲时运行调度程序，从私有就绪队列中选择一个进程运行

如何实现负载均衡?

• 推迁移(Push)策略:
  一个特定的系统程序周期性检查每个处理器的负载，如果负载不平衡，就从忙碌CPU的就绪队列中“推”一些就绪进程到空闲CPU的就绪队列
  推迁移 = 有一个包工头专门负责派活
• 拉迁移(pull)策略:
  周期性检查自身负载每个CPU运行调度程序时，与其他CPU负载。如果一个CPU负载很低，就从其他高负载CPU的就绪队中“拉”一些就绪进程到自己的就绪队列
  拉迁移 = 一群互帮互助的同事(看到其他同事很忙主动揽活过来，分担任务)

如何实现处理机亲和性?

• 私有就绪队列天然地实现了“处理机亲和性”
• 硬亲和: 由用户进程通过系统调用，主动要求操作系统分配固定的CPU，确保亲和性

3.3.7 基于公平原则的调度算法

1、保证调度算法 - 针对进程

性能保证：处理机分配公平 - 如果在系统中有n个相同类型的进程同时运行，须保证每个进程都获得相同的处理机时间1/n。

在实施公平调度算法时系统中必须具有这样一些功能:

• 跟踪计算每个进程自创建以来已经执行的处理时间。
• 计算每个进程应获得的处理机时间，即自创建以来的时间除以n。
• 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
• 比较各进程获得处理机时间的比率。
• 调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

2、公平分享调度算法 - 针对用户

使所有用户能获得相同的处理机时间，或所要求的时间比例。

例子：用户1有4个进程A、B、C、D，用户2只有1个进程E。

• 为保证两个用户能获得相同的处理机时间，则必须执行如下所示的强制调度序列: A E B E C E D E A E B E C E D E （用户1 用户2 用户1 用户2 …）
• 如果希望用户1所获得的处理机时间是用户2的两倍，则必须执行如下所示的强制调度序列: A B E C D E A B E C D E A B E （用户1 用户1 用户2 用户1 用户1 用户2 …）

3.4 实时调度

在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务（硬实时任务） 和 SRT任务（软实时任务），它们都联系着一个截止时间。

3.4.1 实现实时调度的基本条件

1、提供有关任务的必要的信息

• 就绪时间，是指某任务成为就绪状态的起始时间。
• 开始截止时间和完成截止时间。
• 处理时间，一个任务从开始执行，直至完成时所需的时间。
• 资源要求，任务执行时所需的一组资源。
• 优先级，
  • 如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对”优先级;
  • 如果其开始截止时间的错过，对任务的继续运行无重大影响，则可为其赋予“相对”优先级，供调度程序参考。

2、系统处理能力强

处理时间 C_i 【任务从开始到完成 实际占用的 CPU 时间】;
周期时间 P_i 【表示该任务**连续两次被激活（或释放）之间的固定时间间隔**，决定了任务的执行频率】;
截止时间 D_i 【任务从激活（Release Time）到必须完成的 最晚时间限制】

• 处理时间 C_i ≤ 周期时间 P_i 【如果 C_i > P_i ，任务会无法按时完成，导致 死线错过（Deadline Miss）】
• 截止时间 D_i ≤ 周期时间 P_i
  【若 D_i > P_i ，下一次任务可能在上一个任务未完成时 被释放，此时：
  • HRT（硬实时）系统 → 可能导致 瞬时超载（Overload），直接违反了硬实时任务的关键约束。
  • SRT（软实时）系统 → 可能会出现 任务延迟累积（Latency Accumulation），最终导致性能下降或抖动（Jitter）。】

例如：

• P_i = 10 ms（每 10ms 执行一次）
• D_i = 8 ms（必须在 8ms 内完成）
• C_i = 3 ms（实际运行时间 3ms）

✅ 3ms ≤ 8ms ≤ 10ms，系统可调度。

时间轴（ms）	任务状态	说明
0 ms	任务激活并开始执行	任务被调度器触发 - 第一个周期开始
3 ms	任务完成	正常结束
3~10 ms	系统空闲/执行其他低优先级任务	等待下一个周期
10 ms	任务再次激活，开始新一次执行	新的周期（T=10ms）- 第一个周期结束，第二个周期开始
17 ms	任务完成	在截止时间规定前结束，但没有超过第二周期的时间
…	…	…
20 ms	任务再次激活，开始新一次执行	新的周期（T=10ms）- 第二个周期结束，第三个周期开始

假定系统中有m个周期性的硬实时任务HRT

• 在单处理机情况下,【须增强处理能力，以显著地减少对每一个任务的处理时间】
  $$\sum _{i=1}^m\frac{C_i}{P_i}\le 1$$

• 在多处理机情况下，假定系统中的处理机数为 N，
  $$\sum _{i=1}^m\frac{C_i}{P_i}\le N$$

3、采用抢占式调度机制

• 在含有HRT 任务的实时系统中，广泛采用抢占机制。可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那个开始截止时间即将到达的任务。

• 对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，以简化调度程序和在任务调度时所花费的系统开销。

4、具有快速切换机制

快速切换机制应具有如下两方面的能力:

• 对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。

• 快速的任务分派能力。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

3.4.2 实时调度算法的分类

1、非抢占式调度算法

(1)非抢占式轮转调度算法。由一台计算机控制若干个相同的(或类似的)对象，为每个被控对象建立一个实时任务，并将它们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾等待，调度程序再选择下一个队首任务运行。可用于要求不太严格的实时控制系统中。

(2)非抢占式优先调度算法。当实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，便可去调度执行队首的高优先进程。可用于有一定要求的实时控制系统中。

2、抢占式调度算法

可根据抢占发生时间的不同分成以下两种调度算法:
(1)基于时钟中断的抢占式优先级调度算法。在优先级高于当前任务的优先级的实时任务到达后，这时并不立即抢占当前任务的处理机，而是等到时钟中断发生时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先级任务。可用于大多数的实时系统中。

(2)立即抢占(Immediate Preemption)的优先级调度算法。在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力。一旦出现外部中断，只要当前任务未处于临界区,便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。

3.4.3 最早截止时间优先EDF(Earliest Deadline First)算法

根据任务的截止时间确定任务的优先级，任务的截止时间愈早，其优先级愈高，具有最早截止时间的任务排在队列的队首。

调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机。

最早截止时间优先算法既可用于抢古式调度方式中，也可用于非抢占式调度方式中。

1、非抢占式调度方式用于非周期实时任务

2、抢占式调度方式用于周期实时任务

3.4.4 最低松弛度优先 LLF(Least Laxity First)算法

根据的是任务的紧急(或松弛)程度确定任务的优先级。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。主要用于可抢占调度方式中。

例子：假如在一个实时系统中有两个周期性实时任务A和 B，任务A要求每 20ms执行一次，执行时间为10ms，任务B要求每50ms执行一次，执行时间为25ms。

3.4.5 优先级倒置(priority inversion problem)

高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。

假如有三个完全独立的进程P₁、P₂和P₃，P₁的优先级最高，P₂次之，P₃最低。P₁和P₃通过共享的一个临界资源进行交互。

解决办法

建立在动态优先级继承基础上的：当低优先级任务持有高优先级任务所需的资源时，临时提升其优先级至等待该资源的最高优先级任务的级别。

3.5 死锁概述

两个进程都被阻塞，双方都希望对方能释放出自己所需要的资源，但它们谁都因不能获得自己所需的资源去继续运行，从而无法释放出自己占有的资源，并且一直处于这样的僵持状态而形成死锁。

3.5.1 资源问题

1、可重用性资源和可消耗性资源

可重用性资源

定义：可重用性资源是一种可供用户重复使用多次的资源。

性质：

• 每一个 可重用性资源中的单元 只能分配给一个进程使用，不允许多个进程共享。
  【每个单元代表资源的最小可分配或可管理部分——资源类型:网络端口 - 单元示例:端口号（如80）- 管理方式:套接字API（bind()）】

• 进程在使用可重用性资源时，须按照这样的顺序:

  • ①请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。
  • ②使用资源。进程对资源进行操作，如用打印机进行打印;
  • ③释放资源。当进程使用完后自己释放资源。

  对资源的请求和释放通常都是利用系统调用来实现的

  • 对于设备，一般用request/release;
  • 对于文件，可用open/close。
  • 对于互斥访问的资源，进程可以用信号量的wait/signal操作来完成。

• 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。

实现流程（示例：打印机管理）

与临界资源（Critical Resource）的关系

(1) 可重用性资源是否是临界资源？

• 是：当多个进程竞争访问且修改资源状态时（如共享内存写操作）。
• 否：若仅只读或不涉及状态变更（如静态配置表 - 是一种在程序初始化阶段加载后不再修改的只读数据结构，通常用于存储程序的配置信息、预设参数或映射关系。）。

(2) 关键区分标准

场景	是否临界资源	原因
多进程写同一文件	✔️	需互斥避免数据竞争
多线程读取常量全局变量	❌	无状态修改

可消耗性资源

特点：

• 可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的

• 可消耗性资源通常是由生产者进程创建，由消费者进程消耗。最典型的可消耗性资源就是用于进程间通信的消息等。

性质：

• 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的,有时它可以有许多，有时可能为0;
• 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。
• 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。

2、可抢占性资源和不可抢占性资源

可抢占性资源

可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。对于这类资源是不会引起死锁的。

CPU和主存均属于可抢占性资源：

• 优先级高的进程可以抢占优先级低的进程的处理机。
• 可把一个进程从一个存储区转移到另一个存储区，在内存紧张时，还可将一个进程从内存调出到外存上，即抢占该进程在内存的空间。

不可抢占性资源

即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。

磁带机、打印机等也都属于不可抢占性资源。

3.5.2 计算机系统中的死锁

死锁的起因，通常是源于多个进程对资源【不可抢占资源 ➕ 可消耗资源】的争夺。

1、竞争不可抢占性资源引起死锁

例子：文件 - 可重用和不可抢占性资源

 ----------P1进程------------
Open(f1, w);
Open(f2, w);
 ----------P2进程------------
Open(f2, w);
Open(f1, w);

2、竞争可消耗资源引起死锁

例子：利用消息通信机制进行通信

 ----------P1进程------------
receive(p3, m3);
send(p2, m1);
 ----------P2进程------------
receive(p1, m1);
send(p3, m2);
 ----------P3进程------------
receive(p2, m2);
send(p1, m3);

// 三个进程就会永远阻塞在它们的receive操作上，等待一条永远不会发出的消息，于是发生了死锁

3、进程推进顺序不当引起死锁

进程推进顺序合法

进程推进顺序非法

3.5.3 死锁的定义、必要条件和处理方法

1、死锁的定义

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

• 这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。

• 这组死锁进程中的每个进程，所等待的事件是该组中其它进程释放所占有的资源。

• 由于所有这些进程已都无法运行，都不能释放资源，致使没有任何一个进程可被唤醒。这组进程只能无限期地等待下去。

死锁: 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿: 由于长期得不到想要的资源，某进程无法向前推进的现象。

死循环: 某进程执行过程中一直跳不出某个循环的现象。

	共同点	区别
死锁	都是进程无法顺利向前推进的现象(故意设计的死循环除外)	死锁一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态。
饥饿	都是进程无法顺利向前推进的现象(故意设计的死循环除外)	可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态(如长期得不到需要的I/O设备)，也可能是就绪态(长期得不到处理机)
死循环	都是进程无法顺利向前推进的现象(故意设计的死循环除外)	可能只有一个进程发生死循环。死循环的进程可以上处理机运行(可以是运行态)，只不过无法像期待的那样顺利推进。

死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。

死锁和饥饿是管理者(操作系统)的问题，死循环是被管理者的问题。

2、必要条件

必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生:

• 互斥条件。进程对所分配到的资源进行排它性使用，即在一段时间内，某资源只能被一个进程古用。如果此时还有其它进程请求该资源，则请求进程只能等待，直至占有该资源的进程用毕释放。

• 请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

• 不可抢占条件。进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。

• 循环等待条件。在发生死锁时，必然存在一个进程一资源的循环链，即进程集合{P₀,P₁,P₂…,P_n}中的 P₀正在等待一个P₁占用的资源，P₁正在等待P₂占用的资源，……P_n正在等待已被P₀占用的资源。【发生死锁时一定有循环等待，但是发生循环等待时未必死锁(循环等待是死锁的必要不充分条件)】

例子：哲学家进餐

3、处理死锁的方法

目前处理死锁的方法可归结为四种:

• 预防死锁。该方法是通过设置某些限制条件，去破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。

• 避免死锁。在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。

• 检测死锁。检测系统状态，以确定系统中是否发生了死锁。

• 解除死锁。当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。

上述四种方法，从(1)到(4)对死锁的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降(即并发程度提高)。

3.6 预防死锁

3.6.1 破坏“请求和保持”条件

系统必须保证做到: 当一个进程在请求资源时，它不能持有不可抢占资源。该保证可通过如下两个不同的协议实现:

第一种协议

规定：

• 破坏了“请求”条件：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。即该进程在整个运行期间，便不会再提出资源要求。
• 破坏了“保持”条件：在分配资源时，只要有一种资源不能满足进程的要求，即使其它所需的各资源都空闲也不分配给该进程，而让该进程等待。即该进程在等待期间未占有任何资源。

优缺点：

• 优点：简单、易行且安全
• 缺点：
  • 资源被严重浪费，严重地恶化了资源的利用率。进程在开始运行时就一次性地占用了整个运行过程所需的全部资源，其中有些资源可能仅在运行初期或运行快结束时才使用，甚至根本不使用。
  • 使进程经常会发生饥饿现象。因为仅当进程在获得了其所需的全部资源后才能开始运行，这样就可能由于个别资源长期被其它进程占用，而致使等待该资源的进程迟迟不能开始运行，而个别资源有可能仅在进程运行到最后才需要。

*第二种协议

该协议是 对第一种协议的改进，它允许一个进程**只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源**。

例子：有一个进程，它所要完成的任务是，先将数据从磁带上复制到磁盘文件上，然后对磁盘文件进行排序，最后把结果打印出来。

• 在采用第一种协议时，进程必须在开始时就请求磁带机、磁盘文件和打印机。然而打印机仅在最后才会用到，既影响到其利用率，还会影响到其它进程的运行。此外，又如磁带机和磁盘文件虽然空闲，但因打印机已分配给其它进程，因而进程还需要等待。
• 在采用第二种协议时，进程在开始时只需请求磁带机、磁盘文件，然后就可运行。等到全部磁带上的数据已复制到磁盘文件中并已排序好后, 便可将磁带机和磁盘文件释放掉，再去请求磁盘文件和打印机。

3.6.2 破坏“不可抢占”条件

规定：

当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。

缺点：

• 该方法实现起来比较复杂，且需付出很大的代价。
• 可能会造成进程前一阶段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。
• 可能因为反复地申请和释放资源致使进程的执行被无限地推迟 - 延长了进程的周转时间，增加了系统开销，降低了系统吞吐量。

3.6.3 破坏“循环等待”条件

对系统所有资源类型进行线性排序并赋予不同的序号：设 R=(R₁,R₂,R₃,…,R_m)为资源类型的集合，并为每个资源类型赋予唯一的序号。

排序后，

• 需要每个进程必须按序号递增的顺序请求资源。【例如，当某进程需要同时使用打印机和磁带机时，由于磁带机序号低，而打印机序号高，故必须先请求磁带机，再请求打印机。】

• 如果需要多个同类资源单元,则必须一起请求。

• 假如某进程已请求到一些序号较高的资源，后来它又想请求一个序号低的资源时，它**必须先释放所有具有相同和更高序号的资源后，才能申请序号低的资源**。

事实上，总有一个进程占据了较高序号的资源, 此后它继续申请的资源必然是空闲的，从而破坏了“循环等待”条件。

优缺点：

• 优点：资源利用率和系统吞吐量都有较明显的改善。
• 缺点：
  • 为系统中各类资源所规定的序号必须相对稳定，这就限制了新类型设备的增加;
  • 在为资源的类型分配序号时， 作业使用各类资源的顺序与系统规定的顺序不同，会造成对资源的浪费。
  • 系统对用户在编程时所施加的限制条件变多必然会限制用户简单、自主地编程。

3.6.4 破坏互斥条件

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如:SPOOLing技术。

缺点: 并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

3.7 避免死锁

3.7.1 系统安全状态

1、安全状态

安全状态 是指系统能按某种进程推进顺序(P₁,P₂…,P_n)为每个进程P_i分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称(P₁,P₂…,P_n)为安全序列【安全序列并不唯一】。

如果系统无法找到这样一个安全序列，则称系统处于 不安全状态。

• 允许进程动态地申请资源，但系统在**进行资源分配之前，应先计算此次资源分配的安全性**。
  • 若此次分配不会导致系统进入不安全状态，才可将资源分配给进程；
  • 若此次分配会导致系统进入不安全状态，令进程等待。
• 并非所有不安全状态都必然会转为死锁状态，但当系统 进入不安全状态后，就 有可能 进入 死锁 状态。
• 只要系统处于安全状态，系统便不会进入死锁状态。

2、安全状态之例

假定系统中有三个进程P₁、P₂和P₃，共有12台磁带机。进程P₁总共要求10台磁带机，P₂和P₃分别要求4台和9台。假设在T₀时刻，进程P₁、P₂和P₃已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示:

进 程	最大需求	已分配	可用
P1	10	5	3
P2	4	2
P3	9	2

此时（T₀ 时刻）系统是安全的 - 存在一个安全序列 (P₂, P₁, P₃):

• 将剩余的磁带机取 2 台分配给 P₂，使之继续运行，待 P₂ 完成便可释放出 4 台磁带机，于是可用资源增至 5 台;
• 再将这些全部分配给进程 P₁，使之运行，待 P₁ 完成后，将释放出 10 台磁带机;
• P₃ 便能获得足够的资源，从而使 P₁、P₂ 和 P₃每个进程都能顺利完成。

3、由安全状态向不安全状态的转换

进 程	最大需求	已分配	可用
P1	10	5	2
P2	4	2
P3	9	3

如果在T₀ 时刻，P₃ 又请求1台磁带机，若此时系统把剩余 3 台中的 1 台分配给 P₃，则系统便进入不安全状态 - 无法找到一个安全序列：

例如把其余的 2 台分配给 P₂ ，这样在 P₂ 完成后，只能释放出4台，既不能满足 P₁ 尚需 5 台的要求，也不能满足 P₃ 需要 6 台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，结果导致死锁。

3.7.2 利用Dijkstra的银行家算法避免死锁

算法思想：

• 每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。

• 当进程请求组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。【资源分配 = 有足够的资源分配给该进程 + 不会使系统处于不安全状态】

1、银行家算法中的数据结构

四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

• 可利用资源向量 Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[i]=K，则表示系统中现有R_j类资源K个。

• 最大需求矩阵 Max。这是一个n × m的矩阵，它定义了系统中n个进程中的每一个进程对 m 类资源的最大需求。如果 Max[i,i]=K，则表示进程 i需要 R_j 类资源的最大数目为 K。

• 分配矩阵 Allocation。这是一个n × m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,i]=K，则表示进程 i 当前已分得 R_j 类资源的数目为 K。

• 需求矩阵 Need。这是一个n × m的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need[i,j]=K，则表示进程 i 还需要 R_j 类资源 K 个方能完成其任务。

上述三个矩阵间存在下述关系: Need[i, j] = Max[i, j] - Allocation[i, j]

2、银行家算法

设 Request_i 是进程 P_i 的请求向量，如果 Request_i [j] = K, 表示进程 P_i 需要 K 个 R_j 类型的资源。

当 P_i 发出资源请求后，系统按下述步骤进行检查:

1. 判断请求资源的数量和需要资源的数量：如果 Request_i[j] ≤ Need[i, j], 便转向步骤(2); 否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
2. 判断请求资源的数量和可利用资源的求数量：如果 Request_i[j] ≤ Available[j]，便转向步骤(3);否则，表示尚无足够资源，P_i 须等待
3. 系统试探着把资源分配给进程P_i，并修改下面数据结构中的数值:
4. 可利用资源减少： Available[j]= Available[j] - Request_i [j] ;
5. 申请资源增加：Allocation[i, j]= Allocation[i, j] + Request_i [j] ;
6. 需要的资源减少: Need[i, j]= Need[i, j]- Request_i [j] ;
7. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。
8. 若**安全，才正式将资源分配**给进程 P_i，以完成本次分配;
9. 若**不安全，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P_i 等待**。

3、安全性算法

执行安全性算法之前，资源分配已经试探分配了

算法思想：

1. 设置两个向量:

2. 工作向量 Work, 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时 Work := Available;

3. Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] := false ; 当有足够资源分配给进程时，再令Finish[i] := true。

4. 从进程集合中找到一个能满足下述条件的进程:

5. Finish[i] = false;

6. Need[i, j] ≤ Work[j];

若找到，执行步骤(3)，否则，执行步骤(4)。

3. 当进程 P_i 获得资源后，可顺利执行，直至完成，并==释放出分配给它的资源==:

Work[j] = Work[j] + Allocation[i, j];
Finish[i] =true;
go to step 2;

4. 判断系统状态：如果所有进程的 Finish[i]=true 都满足，则表示系统处于安全状态; 否则，系统处于不安全状态。

4、银行家算法之例

假定系统中有五个进程{P₀, P₁, P₂, P₃, P₄} 和 三类资源 {A,B,C} ,各种 资源的数量分别为10、5、7，在T₀ 时刻的资源分配情况如图所示。

3.8 死锁的检测与解除

死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。

死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

3.8.1 死锁的检测

死锁检测前提: ①保存有关资源的请求和分配信息； ②提供一种算法利用这些信息来检测系统是否已进入死锁状态。

1、资源分配图(Resource Allocation Graph)

资源分配图是由一组结点 N 和一组边 E 构成的有向图，记作 G=(N,E)。

• 结点集 N = P ∪ R (N分为P、R两个互斥子集)
  • P：进程结点（Processes）
  • R：资源结点（Resources）
• 边集 E：
  • 请求边（P→R）：进程 P 正在请求资源 R。
  • 分配边（R→P）：资源 R 已分配给进程 P。

2、死锁定理

利用把资源分配图加以简化的方法，来检测当系统处于S状态时，是否为死锁状态。

简化方法：

若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的;

若不能通过任何过程使该图所有的进程结点都成为孤立结点，则称该图是不可完全简化的。- 连着消不掉的进程就是处于死锁状态的进程。

对于较复杂的资源分配图，可能有多个既未阻塞又非孤立的进程结点，会有不同的简化顺序，但所有的简化顺序都将得到相同的不可简化图。

S为死锁状态的充分条件【死锁定理】是：当且仅当S状态的资源分配图是不可完全简化的。

3、死锁检测中的数据结构

• 可利用资源向量 Available，它表示了m类资源中每一类资源的可用数目。
• 把不占用资源的进程(向量 Allocation=0)记入L 表中，即 L_i ∪ L。
• 从进程集合中找到一个Request_i ≤ Work的进程，做如下处理:
  • 将其资源分配图简化，释放出资源，增加工作向量 Work =Work+Allocation_i; 。
  • 将它记入L表中。
• 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。

# 初始化：
Work = Available;  
# 初始化安全列表 L：包含所有既不占用资源（Allocation_i=0）也不请求资源（Request_i=0）的进程（孤立点）
L = {L_i | Allocation_i == 0 ∩ Request_i == 0};  
                                                

# 算法核心：通过逐步检查能否满足进程请求，扩充安全列表 L
# 遍历所有未加入安全列表的进程
for (all L_i ∉ L):
{
    # 进程的请求可以被可用资源满足
    for (all Request_i ≤ Work):  
    {
        # 假设进程完成，释放其占用的资源
        Work = Work + Allocation_i;  
        # 将该进程加入安全列表 L
        L_i ∪  L;               
    }
}

# 最终判定：若 L 包含全部进程 → 无死锁（系统安全）
deadlock = (L == {P1, P2, ..., Pn}); 

3.8.2 死锁的解除

常采用解除死锁的方法是:

• 资源剥夺法 - 抢占资源。从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
• 终止(或撤消)进程法。终止(或撤消)系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。
  • 终止所有的死锁进程，该方法所付出的代价可能很大。
    • 有些进程可能已经运行了很长时间，已接近结束，一旦被终止还得从头再来。
  • 逐个终止进程：按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，把系统从死锁状态解脱出来为止。 该方法所付出的代价也可能很大。
    • 每终止一个进程，都需要用死锁检测算法确定系统死锁是否已经被解除，若未解除还需再终止另一个进程。
    • 在采取逐个终止进程策略时，还涉及到应采用什么策略【该策略主要依据 - 代价最小】选择一个要终止的进程。
• 进程回退法。让一个或多个死锁进程回退到某个安全的状态，释放它们在死锁形成后占用的资源。这种方法需要系统能够记录进程的执行历史和状态，设置还原点，以便能够正确地进行回退操作。

考虑因素

• 进程的优先级的大小;
• 进程已执行了多少时间，还需要多少时间方能完成?
• 进程在运行中已经使用资源的多少，以后还需要多少资源?
• 进程的性质是交互式的还是批处理式的?

---

参考：

教材：

计算机操作系统（第四版） (汤小丹) (Z-Library).pdf

视频：

王道计算机考研 操作系统