理想情况下，对操作系统中运行的进程作出如下假设：

1.每一个工作运行相同的时间

2.所有的工作同时到达

3.工作一旦开始，每个工作保持运行直到完成．

4.所有工作只是用的ＣＰＵ（即他们不执行ＩＯ操作）

5.每个工作的运行时间是已知的．

先放宽假设１，即任务的运行时间可以存在差异．最短任务优先调度策略是从运筹学中借鉴到计算机领域中的一种调度算法，它描述的策略可以简单概括为：先运行最短的任务，最后是次短的任务，如此下去。

假设存在任务Ａ，Ｂ，Ｃ同时在时刻到达，其中A执行需要100ms,B和Ｃ分别需要10ms.

则ＳＪＦ 调度策略可以表示为：

定义周转时间

周转时间 = 完成时间 - 到达时间

周转时间是一个性能指标，另一种指标是公平，性能和公平在调度系统中是矛盾的，如调度程序可以优化性能，但代价是阻止一些任务运行，这就降低了公平．

可以计算在这个例子中SJF调度策略的平均周转时间为：

事实上，考虑所有工作同时到达的假设，可以证明SJF确实是一个最优的调度算法，现在给出证明．

假设被调度进程集合有n个元素.对这n个进程的任意排列

,便是一种调度方案.

设Ｔ为任意一种调度策略产生的平均周转时间，则

Ｔi是第i+1个执行的进程的运行时间．

对T0,T1,...,Tn-1递增排序,得Tk0 ， Tk1， …… ，Tkn-1,设T'位SJF策略生成的调度方案的平均周转时间,则:

T' = [ Tk0 + (Tk0 + Tk1)+……+( Tk0 + Tk1 + ……+ Tkn-1)]/n

对比构成T和T'的每个累加项,后者永远不大于前者,T'是T中最小值.故,能够产生T'的调度方案必为理论最优,而T2调度方案是SJF生成的,得证.

因此，找到了一个用ＳＪＦ进行调度的好方法，但是所有任务同时到达仍然是不符合实际的，现在假设任务可以随时到达，而不在是同时到达，会导致什么问题呢？

假设A在t=0时刻到达，且需要运行100ms,而Ｂ和Ｃ在Ａ之后不久(t=10ms)到达，他们仍然被迫等到Ａ完成，从而遭遇到护航问题(与当前任务相比，后来到达的任务有比较短的执行时间).

为了解决这个问题，需要放宽条件（工作必须保持运行直到完成），还需要调度程序本身的一些机制，由于系统提供了时钟中断和上下文切换，当Ｂ和Ｃ到达时调度程序可以做一些事情，比如抢占Ａ，运行另外一个工作．根据前面的定义，工作一旦开始，必须继续直到完成，所以sjf是一种非抢占式的调度程序，因此存在上述问题．

所以这里就引出了另外一种调度程序，叫做(STCF, shortest-time  to completion First)或抢占式最短作业优先算法．每当新工作进入系统时，它就会确定剩余工作和新工作作用，谁的剩余时间最少，然后调度剩余时间最少的工作．因此，在stcf中，上面的例子将按照如下时间线运行：

平均周转时间变为:

和同时到达的sjf模式一样，考虑到新的假设，STCF可以证明是最优的．考虑到所有工作同时到达，SJF是最优的．所以可以看到，stcf的最优性是符合直觉的．

结束！

在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

一、衡量调度策略的指标

衡量调度策略的最常用的几个指标是：周转时间、吞吐率、响应时间以及设备利用率等。
周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。
吞吐率是指在给定的时间内，一个计算机系统所完成的总工作量。
响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。
设备利用率主要指输入输出设备的使用情况。
进程调度性能的衡量方法可分为定性和定量两种。

二、作业的状态及其转换

一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、收容、执行和完成等4个状态。
处理机调度可以分为4级：(1)作业调度：又称高级调度。(2)交换调度：又称中级调度。(3) 进程调度：又称低级调度。(4) 线程调度。

三、作业调度性能衡量

周转时间 = 运行时间 + 等待时间 = 作业完成时刻 - 作业到达时刻 ；
等待时间 = 上一个的周转时间 - 距离上一个的到达时间 = 上一个的等待时间 + 上一个的运行时间 - 距离上一个的到达时间
带权周转时间 = 周转时间 / 服务时间（运行时间）；
平均周转时间 = 作业周转总时间 / 作业个数；
平均带权周转时间 = 带权周转总时间 / 作业个数；
特别注意：作业到达时间不是作业进内存的时间，而是发出请求，提交就开始计时，如果无法安排进内存，那么就等待，等待的这部分时间也要计数。
任务同时到达时：

四、调度算法

1、先来先服务（FCFS）调度算法
2、轮转法（round robin）
轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程或作业。
时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。它可表示为： q=R/Nmax
UNIX系统中进程调度采用：多级反馈队列轮转法。
3、优先级法
系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。
4、最短作业优先法（shortest job first）
最短作业优先法（SJF）就是选择那些估计需要执行时间最短的作业投入执行，为它们创建进程和分配资源。

五、例题

（一）假设有4道作业，它们的提交时刻及执行时间由下表给出：

计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间，并指出它们的调度顺序。

答：（1）先来先服务调度顺序如下：

平均周转时间：T=(2+2.7+2.8+3)/4=2.625
平均带权周转时间：W=(2/2+2.7/1+2.8/0.5+3/0.3)/4=4.825
（2）最短作业优先调度顺序如下：

（二）有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10min，6min，2min，4min，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间(进程切换开销可不考虑)。
(1)先来先服务(按A，B，C，D，E)算法。
(2)优先级调度算法。
(3)短作业调度算法。