详解进程及其调度算法
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将结果反馈给用户，则该进程开始逐步回升到高优先级队列中。只有当最高优先级队列中进程临时用尽时，才有机会执行低级队列中的进程。由于进程的优先级根据其行为动态变化，因此该算法灵活性得到保证。
