操作系统（7）处理机调度

前言

操作系统中的处理机调度是一个核心概念，它涉及如何从就绪队列中选择进程并将处理机分配给它以运行，从而实现进程的并发执行。

一、调度的层次

高级调度（作业调度）：

调度对象：作业（包含程序、数据以及作业说明书）。
功能：从外存上处于后备队列的作业中挑选一个或多个作业，给它们分配内存等必要资源，并建立相应的进程（建立PCB），以使它们获得竞争处理机的权利。
特点：高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

中级调度（内存调度）：

目的：提高内存利用率和系统吞吐量。
功能：决定将哪个处于挂起状态的进程重新调入内存。挂起态是指暂时被调到外存中等待的进程状态。
特点：中级调度发生的频率比高级调度高，因为进程可能会被多次调出、调入内存。此外，中级调度引入了虚拟存储技术，可将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。

低级调度（进程调度）：

调度对象：进程。
功能：从就绪队列中按照某种方法和策略选取一个进程，将处理机分配给它。低级调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
机制：低级调度包含三个基本机制，即排队器（系统中的所有就绪进程都应按照一定的方式进行排序）、分派器（取出选中进程，进行上下文切换，后分配处理机资源）和上下文切换（对处理机进行切换时，需要进行两对上下文切换）。

二、调度的时机与方式

调度时机：

进程状态发生变化时（如从就绪态到运行态、从运行态到阻塞态或从运行态到结束态）会触发调度。
硬件时钟提供周期性中断时，也可以触发调度。

调度方式：

非抢占式调度：挑选一个进程，然后让该进程运行直到被阻塞或退出，才会调用另外一个进程。这种调度方式下，进程不会因为时钟中断而被抢占。
抢占式调度：挑选一个进程，然后让该进程只运行某段时间（称为时间片）。如果在该时段结束时，该进程仍然在运行时，则会把它挂起，接着调度程序从就绪队列挑选另外一个进程。这种调度方式需要时钟中断来将CPU控制返回给调度程序进行调度。

三、调度算法及其评价指标

调度算法：

先来先服务（FCFS）：按照进程进入就绪队列的先后顺序进行调度。这种算法对长作业有利，但可能导致短作业长时间等待。
最短作业优先（SJF）：选择估计运行时间最短的进程进行调度。这种算法有助于提高系统吞吐量，但对长作业不利。SJF可以分为抢占式和非抢占式两种。
高响应比优先（HRRN）：权衡了短作业和长作业。每次进行进程调度时，先计算响应比优先级，然后把响应比优先级最高的进程投入运行。响应比优先级的计算公式为：响应比=（等待时间+要求服务时间）/要求服务时间。
时间片轮转（Round Robin, RR）：每个进程被分配一个时间段（称为时间片），允许该进程在该时间段中运行。如果时间片用完，进程还在运行，则将其从CPU释放出来，并把CPU分配给另外一个进程。时间片轮转算法是最古老、最简单、最公平且使用最广的算法之一。
优先级调度：根据进程的优先级进行调度。优先级可以是静态的（在创建进程时确定，并在执行过程中不会改变），也可以是动态的（根据进程的动态变化调整优先级）。

评价指标：

CPU利用率：CPU忙碌时间占总时间的比例。
系统吞吐量：单位时间内完成的作业数量。
周转时间：从作业被提交给系统开始到作业完成为止的这段时间间隔。
等待时间：进程或作业处于等待处理机状态的时间之和。
响应时间：用户提交请求到首次产生响应所需要的时间。

四、实时调度与死锁

实时调度：
实时系统中需要及时反馈，因此前面的算法可能不能满足实时系统对调度的要求。实时调度算法需要满足实时任务的时间约束，常见的实时调度算法有最早截止时间优先（EDF）和最低松弛度优先（LLF）等。

死锁：
死锁是指两个或多个进程因争夺资源而无限期地阻塞、相互等待的一种状态。产生死锁的原因包括竞争资源、进程间推进顺序非法等。预防死锁的方法包括摒弃“请求和保持条件”、摒弃“不可剥夺条件”和摒弃“环路等待条件”等。