本文摘自PHP中文网，作者巴扎黑，侵删。
处理机的调度
标签（空格分隔）： 进程调度 调度算法 操作系统
基本概念
定义
: 操作系统管理了系统的有限资源，当有多个进程（或多个进程发出的请求）要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程（请求）来占用资源, 我们称之为调度。
其目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。处理机调度的三个层次:
高级调度:作业调度, 调度对象为作业.
中级调度:内存调度(实质是存储器的对换功能)
低级调度:进程调度, 调度对象为进程或内核级线程
作业调度的算法也适用于进程调度
服务时间\(T_s\): 系统为作业或进程提供服务的时间
周转时间\(T_i\): 作业或进程被提交给系统到作业或进程完成为止的时间间隔.
通常包括:
作业在外存后备队列上等待调度的时间.
进程在就绪队列上等待进程调度的时间.
进程在cpu上执行的时间.
进程等待I/O操作完成的时间.
平均周转时间:
\[T = \frac{\sum_{i=1}^n T_i}{n}\]
带权周转时间: 作业的周转时间与为它提供服务的时间之比
\[W_i = \frac{T_i}{T_s}\]
平均带权周转时间:
\[W = \frac{\sum_{i=1}^n \frac{T_i}{T_s}}{n}\]
调度时机、切换与过程
进程调度和切换程序是操作系统内核程序。当请求调度的事件发生后，才可能会运行进程调度程序，当调度了新的就绪进程后，才会去进行进程间的切换。理论上这三件事情应该顺序执行，但在实际设计中，在操作系统内核程序运行时，如果某时发生了引起进程调度的因素，并不一定能够马上进行调度与切换。
现代操作系统中，不能进行进程的调度与切换的情况有以下几种情况:
在处理中断的过程中：中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
进程在操作系统内核程序临界区中：进入临界区后，需要独占式地访问共享数据，理论上必须加锁，以防止其他并行程序进入，在解锁前不应切换到其他进程运行，以加快该共享数据的释放。
其他需要完全屏蔽中断的原子操作过程中：如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。
如果在上述过程中发生了引起调度的条件，并不能马上进行调度和切换，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。
应该进行进程调度与切换的情况有：
当发生引起调度条件，且当前进程无法继续运行下去时，可以马上进行调度与切换。如果操作系统只在这种情况下进行进程调度，就是非剥夺调度。
当中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。如果操作系统支持这种情况下的运行调度程序，就实现了剥夺方式的调度。
进程切换往往在调度完成后立刻发生，它要求保存原进程当前切换点的现场信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将原进程的现场信息推入到当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。
调度的方式
非抢占方式
一旦处理机分配给某进程后, 就一直让它运行下去, 决不会因为时钟中断或任何其他原因取抢占当前正在运行进程的处理机, 直至该进程完成, 或发生某事件而被阻塞时, 才把处理机分配给其他进程.抢占方式
系统允许调度程序根据某种原则, 取暂停某个正在执行的进程, 将已分配个该进程的处理机重新分配给另一进程.
"抢占"时应遵循一定的原则:优先权原则
短进程优先原则
时间片原则
典型的调度算法
先来先服务调度算法(first-come first-served):
即FCFS调度算法, 既可用于作业调度, 也可用于进程调度. 系统按照作业到达的先后次序(优先考虑在就绪队列中等待时间最长的作业)进行调度.
缺点:未考虑作业的紧迫程度, 只能顺序运行
短作业(进程)优先的调度算法(short job first):
为短作业而设立, 因为操作系统中大多为短作业.系统在作业运行时, 选出运行时间最短的作业将其调入内存.
SJF(不可抢占):算法以作业的长短(作业需要运行的时间)来计算优先级, 作业越短, 其优先级越高.
SPF(可抢占):同上, 但是当有作业优先级较高时, 便可以抢占资源优先执行.
缺点:
必须预知作业的运行时间
对作业程不利
无法实现人机交互
没有考虑到作业的紧迫程度
优先级调度算法(priority-scheduling algorithm):
PSA算法基于作业的紧迫程度, 由外部赋予作业相应的优先级, 根据作业优先级进行调度.
高响应闭优先调度算法(highest request ratio next):
HRRN算法即考虑了作业的等待时间, 又考虑了作业运行时间. 为没有作业引入一个动态优先级:
优先权 = (等待时间+要求服务时间) / 要求服务时间
可缩写为:
R = 响应时间 / 要求服务时间
特点:
作业等待时间相同, 则要求服务时间越短, 优先权越高越, 类似于SJF算法, 有利于短作业
作业要求服务时间相同时, 则作业等待时间约长, 优先权越高, 类似于FCFS算法, 有利于长作业
对于长作业(要求服务时间长), 随着等待的时间足够长, 也可获得较高的优先级. 不会一直等下去.
时间片轮转调度算法(RR)
原理: 系统根据FCFS策略将所有的就绪进程排成一个就绪队列, 并设置每隔一段时间产生依次中断, 激活系统中的进程调度程序, 完成依次调度, 将cpu分配给新的队首进程(或新到达的紧迫进程).
相关阅读 >>
更多相关阅读请进入《操作系统》频道 >>
