2.5 多处理机调度与实时调度

2.5.2 实时调度

　　实时计算可以分为两种类型：硬实时计算与软实时计算。硬实时计算用于在保证的时间内完成关键性的任务。通常进程在提交时伴随着一个说明了时间量的语句，进程需要在这个时间内完成或执行I/O 操作。然后，调度程序接纳这个进程并保证它按时间完成或者是拒绝这个请求（认为在这个时间内完成是不可能的），这被称为资源预留（resource reservation）。为了完成这样的需求，调度程序必须要知道每种类型的操作系统操作执行所需的准确时间，所以必须确保每个操作所需的一个最大的时间。在具备了辅助存储器或虚拟内存的系统中是不可能做出这种保证的，如我们在稍后的几章中说明的，这些子系统在执行具体的进程时会在时间上造成不可避免且无法预料的偏差。所以，硬实时计算是由运行在硬件上的专用软件组成的，而且缺乏一些现代计算机和操作系统的功能。
　　软实时计算受到的约束就少一些。要确保其关键性进程的优先级要高于其他进程的优先级。虽然为分时系统添加软实时功能对一些进程来说会导致不公平的资源分配和更长的延时，甚至是饥饿，但至少是可以实现的。结果，通用计算机也能够支持多媒体、高速交互式图表及各种各样在不支持软实时计算的环境中不能实现的任务。实现软实时系统功能需要仔细地设计调度程序和操作系统的相关方面。首先，系统必须要具备优先调度，并且实时进程必须要有最高的优先级。而且实时进程的优先级不会随着时间而降低，而非实时进程的优先级可以降低；其次，调度时间必须很短。调度时间越短，实时进程就绪后就可以更快地开始运行。
　　对前面提到的属性的管理就相对简单一些。例如，我们可以禁止老化实时进程，这样就可以确保不改变各种进程的优先级。然而，管理稍后提到的属性就更加棘手了。问题是一些操作系统在进行上下文转换前必须等待系统调用或I/O 操作的完成。在这样的系统中，调度时间可能会很长，因为有些系统调用很复杂，有些I/O设备很慢。
　　为了保持较低的调度时间，需要允许系统调用可被抢占。有几种方法可以实现。一种处理抢占的方法是在持续时间较长的系统调用中插入抢占点，在抢占点检查是否有高优先级进程需要运行。如果有，就进行一个上下文转换，当高优先级进程结束时，被中断的进程继续运行。可以只把抢占点设在内核中的“安全”地带——在这些地方内核数据结构没有正在进行修改。即使是利用抢占点调度时间也可能会非常大，因为事实上只有很少的抢占点可以添加到内核中。另一种处理抢占的方法是使整个内核可以抢占。利用这种方法，内核总是可以被抢占，因为所有正在更新的内核数据受到保护而免于高优先权进程的修改。这是一种最为高效（也最复杂）的方法，应用非常广泛。
　　但是如果优先级更高的进程需要读取或修改其他优先级更低的进程正在访问的内核数据时，情况会怎样呢？高优先级进程将等待更低优先级进程结束。这被称为优先级反转。事实上，在高优先级进程需要时可能会有很多个进程正在访问该资源，这时可以通过优先级继承协议来解决这个问题，所有进程继承高优先级，直到它们利用该资源完成工作为止。当它们完成时，它们的优先级复原。