首页 > 编程笔记 > 操作系统笔记

什么是进程调度,进程调度的来龙去脉

多道程序设计的目标是,无论何时都有进程运行,从而最大化 CPU 利用率。分时系统的目的是在进程之间快速切换 CPU,以便用户在程序运行时能与其交互。

为了满足这些目标,进程调度器选择一个可用进程(可能从多个可用进程集合中)到 CPU上执行。如果有多个进程,那么余下的需要等待 CPU 空闲并能重新调度。

调度队列

进程在进入系统时,会被加到作业队列,这个队列包括系统内的所有进程。驻留在内存中的、就绪的、等待运行的进程保存在就绪队列上。

就绪队列通常用链表实现;其头节点有两个指针,用于指向链表的第一个和最后一个 PCB 块;每个 PCB 还包括一个指针,指向就绪队列的下一个 PCB,如图 1 所示。

系统还有其他队列。当一个进程被分配了 CPU 后,它执行一段时间,最终退出,或被中断,或等待特定事件发生如 I/O 请求的完成。假设进程向一个共享设备如磁盘发出 I/O 请求。由于系统具有许多进程,磁盘可能忙于其他进程的 I/O 请求,因此该进程可能需要等待磁盘。等待特定 I/O 设备的进程列表,称为设备队列。每个设备都有自己的设备队列(图 1)。

就绪队列和各种I/O设备队列
图 1 就绪队列和各种I/O设备队列

进程调度通常用队列图来表示,如图 2 所示。每个矩形框代表一个队列;这里具有两种队列:就绪队列和设备队列。圆圈表示服务队列的资源;箭头表示系统内的进程流向。

表示进程调度的队列图
图 2 表示进程调度的队列图

最初,新进程被加到就绪队列;它在就绪队列中等待,直到被选中执行或被分派。当该进程分配到 CPU 并执行时,以下事件可能发生:
对于前面两种情况,进程最终从等待状态切换到就绪状态,并放回到就绪队列。进程重复这一循环直到终止;然后它会从所有队列中删除,其 PCB 和资源也被释放。

调度程序

进程在整个生命周期中,会在各种调度队列之间迁移。操作系统为了调度必须按一定方式从这些队列中选择进程。进程选择通过适当调度器或调度程序来执行。

通常,对于批处理系统,提交的进程多于可以立即执行的。这些进程会被保存到大容量存储设备(通常为磁盘)的缓冲池,以便以后执行。长期调度程序(或作业调度程序)从该池中选择进程,加到内存,以便执行。短期调度程序(或 CPU 调度程序)从准备执行的进程中选择进程,并分配 CPU。

两种调度程序的主要区别是执行频率:
重要的是,长期调度程序进行认真选择。通常,大多数进程可分为 I/O 为主或 CPU 为主,I/O 密集型进程执行 I/O 比执行计算需要花费更多时间。相反,CPU 密集型进程很少产生 I/O 请求,而是将更多时间用于执行计算。

长期调度程序应该选择 I/O 密集型和 CPU 密集型的合理进程组合。因为如果 所有进程都是 I/O 密集型的,那么就绪队列几乎总是为空,从而短期调度程序没有什么可做。如果所有进程都是 CPU 密集型的,那么 I/O 等待队列几乎总是为空,从而设备没有得到使用,因而系统会不平衡。

有的系统,可能没有或极少采用长期调度程序。例如,UNIX 或微软 Windows 的分时系统通常没有长期调度程序,只是简单将所有新进程放于内存,以供短期调度程序使用。这些系统的稳定性取决于物理限制(如可用的终端数)或用户的自我调整。如果多用户系统性能下降到令人难以接受,那么有的用户就会退出。

有的操作系统如分时系统,可能引入一个额外的中期调度程序,如图 3 所示。

添加中级进程调度到队列图
图 3 添加中级进程调度到队列图

中期调度程序的核心思想是可将进程从内存(或从 CPU 竞争)中移出,从而降低多道程序程度。之后,进程可被重新调入内存,并从中断处继续执行。这种方案称为交换

通过中期调度程序,进程可换出,并在后来可换入。为了改善进程组合,或者由于内存需求改变导致过度使用内存从而需要释放内存,就有必要使用交换。

上下文切换

前面提过,中断会导致 CPU 从执行当前任务改变到执行内核程序。这种操作在通用系统中经常发生。当中断发生时,系统需要保存当前运行在 CPU 上的进程的上下文,以便在处理后能够恢复上下文,即先挂起进程,再恢复进程。

切换 CPU 到另一个进程需要保存当前进程状态和恢复另一个进程的状态,这个任务称为上下文切换

当进行上下文切换时,内核会将旧进程状态保存在其 PCB 中,然后加载经调度而要执行的新进程的上下文。上下文切换的时间是纯粹的开销,因为在切换时系统并没有做任何有用工作。上下文切换的速度因机器不同而有所不同,它依赖于内存速度、必须复制的寄存器数量、是否有特殊指令(如加载或存储所有寄存器的单个指令)。典型速度为几毫秒。

上下文切换的时间与硬件支持密切相关。例如,有的处理器(如 Sun UltraSPARC)提供了多个寄存器组,上下文切换只需简单改变当前寄存器组的指针。当然,如果活动进程数量超过寄存器的组数,那么系统需要像以前一样在寄存器与内存之间进行数据复制。

不仅如此,操作系统越复杂,上下文切换所要做的就越多,高级的内存管理技术在每次上下文切换时,所需切换的数据会更多。例如,在使用下一个进程的地址空间之前,需要保存当前进程的地址空间。如何保存地址空间,需要做什么才能保存等,取决于操作系统的内存管理方法。

所有教程

优秀文章