详解进程及其调度算法
1 基本概念
进程与程序的关系是:程序是存储在文件中的、带有结构和顺序信息(用于控制指令执行次序)的指令列表,进程是程序的运行实例。通俗来讲,程序描述了如何处理一个事务,进程按程序的描述实际执行之。相同的程序可以多次执行,每次执行操作系统都将创建一个独立的进程,并开始读取指令列表。
进程更正式的定义是:计算机中的程序关于某数据集合的一次运行活动,是系统进行资源分配和调度的最小单位,是操作系统结构的基础。进程是线程的容器,同时包含了内存、句柄等计算机资源,如图1所示。
数据集合包括指令在内存中的版本、程序中使用的变量以及其他相关元数据。其中变量和元数据是可变的,称为进程状态。进程主要的五种状态如图2所示。
重点辨析就绪和阻塞状态。
就绪:进程分配的时间片已用完,或在中断机制下,有更高优先级的进程打入,此时进程进入就绪队列等待下一次被选中
阻塞:进程所需要的资源或某些事件不满足要求,如暂时不能访问某一资源、操作系统尚未完成服务、系统正在初始化I/O设备、等待用户的输入信息等,当这些系统资源被满足后,进程从阻塞队列出队而进入就绪队列等待CPU资源。
简言之,就绪状态等待CPU资源,而阻塞状态等待CPU以及所需的其他系统资源。
进程状态区分了同一程序的多道进程,操作系统级别用唯一进程标识符(Process IDentifier, PID)识别不同的进程。
2 进程调度
进程的运行,是其指令在CPU中执行的行为。CPU是系统最主要的资源,而操作系统最基本的作用是管理系统资源,因此操作系统负责管理系统进程,以及在任意给定的时间选择哪一个进程运行(仅考虑单核系统)。现代操作系统中,执行上述职能的部件是调度器。调度器选中某道进程后,由其子部件分派器将该进程由就绪状态引入到运行状态。因此调度是通过一定算法选择某道进程,并将其从就绪状态切换到运行状态的过程。
2.1 时间片管理
在抢占式调度器中,允许某个特定进程运行一段时间后,切换到就绪队列等待调度器下一次选中,而将另一个进程从就绪队列中引出,并设置为运行状态。这里的时间称为时间片。
由于调度器执行调度决策本身需要占用系统处理时间,这部分进程外的额外时间称为调度开销。调度开销中的最大成分是上下文切换,即CPU从执行一道进程或线程切换到执行另一道进程或线程的动作,如图3所示。上下文切换时要进行保护现场和恢复现场,即保存某道进程被抢占或阻塞前最后一次运行时的执行环境,和在下一次运行时复现,这里的执行环境包括堆栈、程序计数器以及其他操作系统结构等。
若时间片太短,由于调度开销的存在,操作系统将频繁执行调度活动,使系统处理资源被浪费;若时间片太长,则就绪队列的其他进程不得不在轮转期间等待更长的时间,表现出应用程序的未响应或缺乏响应状态。
时间片大小没有随看技术进步(主要指CPU处理速度)而大幅变化,原因在于:
(1) 人类对响应性的感知能力没有改变,没有必要为此缩短时间片;
(2) 系统的复杂性和在其上运行的应用程序的数量也在以高速率提升,以实现其丰富的功能,即相较原有系统多出的运算资源又被分配给了更多的进程,而非延长每一道进程的时间。
现代系统中时间片大小一般在大概10~200ms的范围内(Windows操作系统为10ms), 在非常快速的平台上时间片更小(低至约1ms)。
时间片大小的范围设定能够用作实现进程优先级的一种手段:高优先级的进程应该获得较大份额的可用处理资源。一种特例是,如果进程是IO密集型的,它们执行IO时会被堵塞而无视其优先级(分配的时间片再长也会进入阻塞队列)。
2.2 调度算法
在基础算法上,进行了调度算法的改进。
(1) 多级队列(MLQ, Multilevel Queue):按进程性质设置若干就绪队列,每个队列可执行不同调度算法。例如计算密集型进程队列中执行FCFS调度;系统进程队列执行RR调度等。根据系统的工作特点,为不同的进程队列分配不同的CPU处理时间。值得注意的是,每级队列执行的调度算法,不会影响到其他进程队列。
(2) 多级反馈队列(MLFQ, Multilevel Feed-back Queue):以MLQ为基础,但与之不同在于:进程能够在不同队列中移动以允许调度过程达到一种平衡——短期调度获得任务响应性,长期调度确保公平性和系统效率;队列按优先级组织。
进程移动的基本规则是:
①若进程用尽时间片仍未完成任务,则降到下一级进程队列;
②若进程在时间片内让出控制(如发生阻塞),则保留在该级队列;
③若进程因为执行IO而发生阻塞,则会提升到上一级进程队列。
以科学计算模拟为例,由于其计算时间较长以至于在若干个时间片内无法处理完毕,进程将逐次被降级,并留在较低级的进程队列中接受RR调度。当科学计算结束后,需要通过IO将结果反馈给用户,则该进程开始逐步回升到高优先级队列中。只有当最高优先级队列中进程临时用尽时,才有机会执行低级队列中的进程。由于进程的优先级根据其行为动态变化,因此该算法灵活性得到保证。