前面操作系统基础8和操作系统基础10已经学习关于进程和线程的的基础知识，本次我们继续学习关于操作系统中调度的概念。

前面学习了线程相关内容，我们知道对于支持线程的操作系统，操作系统实际调度的是内核级线程而非进程。对于术语进程调度(process scheduling)或线程调度(thread scheduling)常常交替使用，在一般说到调度概念时，采用进程调度。

调度基本概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

调度队列

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

就绪队列通常用链表实现；其头节点有两个指针，用于指向链表的第一个和最后一个 PCB 块；每个 PCB 还包括一个指针，指向就绪队列的下一个 PCB

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

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

最初，新进程被加到就绪队列；它在就绪队列中等待，直到被选中执行或被分派。当该进程分配到 CPU 并执行时，以下事件可能发生：

• 进程可能发出 I/O 请求，并被放到 I/O 队列。
• 进程可能创建一个新的子进程，并等待其终止。
• 进程可能由于中断而被强制释放 CPU，并被放回到就绪队列。

对于前面两种情况，进程最终从等待状态切换到就绪状态，并放回到就绪队列。进程重复这一循环直到终止；然后它会从所有队列中删除，其 PCB 和资源也被释放。

调度的三个层次

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。

• 高级调度(作业调度)

按一定的原则从外存上处于后备队列的作业中挑选一个(或多个)作业，给它们分配内存等必要资源，并建立相应的进程(建立PCB)，以使它(们)获得竞争处理机的权利。高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

• 中级调度(内存调度)

中级调度就是要决定将哪个处于挂起状态的进程重新调入内存。 一个进程可能会多次被调入、调出内存，因此中级调度发生的频率要比高级调度更高。暂时调到外存等待的进程状态为挂起状态，PCB并不会一起调到外存，而是会常住内存。PCB会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中

• 低级调度(进程调度)

低级调度主要任务是按某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般都是毫秒级。

进程调度的时机

• 什么时候需要进程调度？

1. 主动放弃：

(1)进程正常终止

(2)运行过程中发送异常而终止

(3)主动阻塞(如 等待I/O)

2.被动放弃：

(1)分给进程的时间片用完

(2)有更紧急的事情需要处理(如I、O中断)

(3)有更高级的进程进入就绪队列

• 什么时候不能进行进程调度？

1. 在处理中断的过程中
2. 进程在操作系统内核程序临界区
3. 原子操作过程中(原语)

进程调度的方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机。该方式实现简单，系统开销小但是无法及时处理紧急任务，早期的批处理系统采用该方式。

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。该方式可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合与分时操作系统，实时操作系统。