操作系统设计/进程调度/抢占

抢占在操作系统中的使用是指操作系统能够抢占（即停止或暂停）当前调度的任务以支持更高优先级的任务。被调度的资源可以是处理器或 I/O，以及其他资源。

例如，在处理中断时会发生不可抢占性。在这种情况下，调度会等到中断处理完成才会继续。

大多数现代操作系统中使用的调度器，例如各种 Unix 版本，可以抢占用户进程。这被称为抢占式多任务处理，与合作式多任务处理形成对比，在合作式多任务处理中，进程通过使用内核资源或专门调用内核例程来允许其他进程运行时间，从而“放弃”其时间。

历史

一些操作系统的调度器（包括 Linux 2.6 系列）能够在进程处理系统调用时抢占进程（可抢占内核）。

Sinclair QDOS 是首个可供家庭用户使用的抢占式多任务系统（1984 年）。其他抢占式操作系统包括 AmigaOS、Windows NT 家族（包括 XP 或 Vista）、Linux、*BSD 和 Mac OS X。合作式操作系统的例子包括 Windows for Workgroups（也称为 Windows 3.1 或 95）、NetWare 和 Mac OS 9.x 版本。

Linux 2.6 之前的 Linux 内核也是不可抢占的，但后来的版本实现了抢占式模型。几个商业版本的 UNIX 是抢占式的，包括 Solaris 和 IRIX。

类比

当前在收银台的人可能被打断，必须在完成之前等待另一个顾客。

实现

在 Linux 内核中，调度器在每次定时器中断后被调用（即每秒多次）。它根据各种因素确定接下来要运行的进程，包括优先级、已运行时间等。其他内核中抢占的实现可能类似。

优点和缺点

使调度器可抢占的优点是更好的系统响应能力和可扩展性，但缺点是存在竞态条件（正在执行的进程在另一个被抢占的进程完成使用之前访问了相同的资源）。

循环抢占式调度

最简单的抢占式调度算法是循环调度。循环调度器将所有可运行的进程保存在一个循环队列中。每次硬件定时器中断当前运行的进程时（或当该进程自愿放弃控制时），调度器会将该进程放到队列的末尾。然后，调度器会获取队列头部的进程并运行它。

优先级抢占式调度

(FIXME：考虑将此部分拆分到一个单独的“优先级抢占式调度”页面)

几乎所有现代操作系统都使用优先级抢占式调度。

大多数实时计算机系统使用固定优先级抢占式调度 - 通常是速率单调调度或截止日期单调调度。

固定优先级抢占式调度

速率单调调度：激活频率较低的作业比（因此会被）所有激活频率较高的作业赋予较低的优先级。如果 CPU 利用率小于 $\ln 2\approx 0.693147\ldots$.

截止日期单调调度：作业的优先级与其相对截止日期成反比。（在每个作业的相对截止日期等于其周期的特殊情况下，截止日期单调调度等效于速率单调调度）。

动态优先级抢占式调度

最早截止日期优先调度：作业的优先级与其绝对截止日期成反比。截止日期单调调度和最早截止日期优先调度之间的区别在于，DM 是一种静态优先级算法，EDF 是一种动态优先级算法。 EDF 可以保证所有截止日期都能够满足，前提是总的 CPU 利用率小于 $1$.

固定 vs 动态 vs 循环

动态优先级算法的优点是它们可以成功地调度一些会导致静态优先级算法失败（即错过截止日期）的作业集（即不会错过任何截止日期）。

固定优先级算法相对于动态优先级算法的优势在于，如果系统在某个优先级级别上遇到过载——因此在该优先级上调度了太多作业，以至于任何调度程序都无法满足所有作业的截止期限——固定优先级调度程序仍然可以保证所有较高优先级的作业将仍然被调度，并且仍然能够满足其截止期限。^[3] 固定优先级算法的另一个优势是更容易实现。

实现基于优先级的调度程序的人需要担心两个潜在的问题

• 进程饥饿：如果一个进程请求所有它能获得的 CPU 时间——由于意外过载或恶意拒绝服务攻击——所有较低优先级的进程将被锁定。^[4]
• 优先级反转：(FIXME:)

循环调度程序的优势在于不会出现这些与优先级相关的问题。

混合调度

一些调度程序实现了上述调度算法的混合。

自适应分区调度程序在系统没有处于满负荷时使用基于优先级的调度，但也保证即使在系统负载很重的情况下，低优先级服务也能获得最小的 CPU 时间^[4][5]，使用类似循环的算法。

许多实时系统都有一个最低优先级的“后台任务”，它没有硬实时截止期限，系统只在所有实时任务完成后的闲置时间运行它。^[6][7]

这些系统中有一些使用“双内核”，整个通用操作系统（如 Linux）及其调度程序作为单个最低优先级任务运行在硬实时内核之上。^[8]（当实时内核使用速率单调调度时，该非实时任务至少可以获得 $0.3$ 的 CPU 时间）。

中断延迟

除了定时器滴答中断外，大多数系统还有其他硬件中断。(FIXME: 关于临界区的某些内容)(FIXME: 关于确定性响应时间与抖动的某些内容)(FIXME: 关于流式音频数据的一些内容)最坏情况下的中断延迟至少是内核中最长临界区的时间。^[6]

一些高可用性操作系统支持虚拟设备驱动程序——以最高优先级运行并直接操作硬件（如中断服务例程）的代码量最小化；大多数设备驱动程序工作由用户空间中的二级中断处理程序处理。^[7](FIXME: 可能关于硬件中断触发一级中断处理程序，以及定时器滴答中断运行调度程序，它可能会运行二级中断处理程序？或者这已经由嵌入式系统/中断 涵盖了吗？)

我们将在后面的章节中详细讨论各种硬件中断，操作系统设计/进程/中断。

硬实时调度程序

许多计算机系统设计为随时接受新任务。如果只有一个任务在运行——或者如果所有其他任务都适合该任务无法做任何有用的事情的时间（因为它正在等待磁盘旋转，网络卡完成数据包等）——那么该任务将在最短时间内完成。但是，随着其他任务被添加到系统中，这些任务会抢占该任务，完成任务所需的时钟时间将变得无界。(FIXME: 在这里谈论“无饥饿”的某些内容)

硬实时计算机系统设计为故意拒绝接受新任务。程序员仔细设计实时任务，使其相对容易计算最坏情况下的运行时间（即避免停机问题）。有了这个运行时间、任务所需的截止期限以及任务本身，就可以使用速率单调分析来确定在将该任务添加到已添加到系统的所有其他任务之后，是否不仅可以满足该任务所需的截止期限，还可以继续满足之前所有任务所需的截止期限——如果无法保证所有这些截止期限将继续得到满足，则拒绝接受该新任务。有些人构建允许新任务呈现给系统的系统，并设计系统自动执行 RMA 分析，然后系统决定是否接受这个新任务。其他人手动执行 RMA 以决定允许系统中的哪些任务，然后将系统硬连线到只运行这些任务——这些系统更简单。

构建硬实时系统的人认为，偶尔拒绝接受一些新任务非常值得保证之前所有任务都能满足其截止期限。