《处理机调度算法详解》由会员分享，可在线阅读，更多相关《处理机调度算法详解（5页珍藏版）》请在金锄头文库上搜索。
1、关于处理机调度算法操作系统教材中，介绍了常用的作业调度算法和进程调度算法。其中先来先服务法 (FCFS)和优先级法对作业调度和进程调度都适用，时间片轮转法(RR)适用于进程调度。 此外，还介绍了其他调度算法，如短作业优先法、最短剩余时间优先法、多级队列法和多级 反馈队列法，这 4 个算法不是课程的重点内容，不作为考核要求。需要指出的是：(1)在作业调度和进程调度中同时出现的算法，如FCFS、优先级法， 其使用原理是基本相同的；(2)作业调度算法和进程调度算法应严格与存储管理中的“请求 淘汰换页算法”相区别，注意不要混淆。下面，结合具体的例题，详解调度算法：1.先来先服务法(FCFS) 算法描述
2、：每次调度时，从后备作业队列或就绪队列中选择一个最先进入该队列的作业 或进程。【例1】下表给出作业1，2, 3的到达时间和运行时间。采用先来先服务调度算法，试 问作业调度的次序和平均周转时间各为多少？(时间单位：小时，以十进制进行计算。)作业号到达时间运行时间10.08.020.44.031.01.0分析 解题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。我们可以用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。先来先服务调度算法是按照作业到达的先后次序挑选作业，先进入的作业优先被挑选。 即按照“排队买票”的办法，依次选择作业。其作业执行时间图如下：作业作
3、业3作业2作业10 0.4 1.0作业提交时间8.012.0 13.0时间各作业陆续完成时间或者简化为下图：作业1作业2作业3I111k-时间081213由于作业1， 2， 3是依次到来的，所以刚开始时系统中只有作业1，于是作业1被选中。 在8.0时刻，作业1运行完成，这时作业2和作业3已经到达，都在系统中等待调度，按照 先来先服务法的规定，每次调度最先进入就绪队列中的作业，由于作业2比作业3先到达， 于是作业2被优先选中运行。待作业2运行完毕，最后运行作业3。因此，作业调度的次序是 1 ， 2 ， 3 。 另外，要记住以下周转时间和平均周转时间的算术公式： 作业i的周转时间片=作业i的完成时
4、间一作业i的提交时间系统中n个作业的平均周转时间T = （ T ） x 1 ,其中Ti为作业i的周转时间。ini = 1解：采用先来先服务调度策略,作业调度次序为 l、2、3。作业号到达时间运行时间开始时间完成时间周转时间10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周转时间 T=(8+11.6+12) /3 = 10.53思考题 1在某操作系统中,设有三个批处理作业,所需执行时间分别为 2 小时, 1 小时和25 分 钟,相继到达时间分别为 6：00、6：10 和6：25。若对这三个批处理作业采用调试算法S1,其执行情况如下：作
5、业号到达时间开始执行时间执行结束时间16：006：008：0026：108：009：0036：259：009：25则调试算法 S1 属于（）。A.优先级法B.先来先服务法C.短作业优先法D.时间片轮转法2.时间片轮转法（RR） 算法描述：用于分时系统中的进程调度。每次调度时,总是选择就绪队列的队首进程, 让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程，返 回到绪队列末尾重新排队,等待下一次调度。【例2】进程A、B、C、D需要运行的时间分别为20ms、10 ms、15 ms、5 ms，均在0 时刻到达。到达的先后次序为ATBTCTD。如果时间片分别为1 ms和5ms
6、,计算各个进 程的带权周转时间和平均带权周转时间。分析 在掌握了时间片轮转法概念的基础上，我们可以用一个执行时间图来形象地表示 作进程的执行情况，帮助我们理解此题。具体如下：根据执行时间图就可以计算各个进程的带权周转时间和平均带权周转时间了。这里要注意的是，要记住带权周转时间和平均带权周转时间的算术公式：带权周转时间W,即：W= TR其中T为周转时间，R为实际运行时间。 平均带权周转时间为：0 T 11J _TTX R丿ni = 1i解：采用时间片轮转法进行调度，算法的性能指标如下：到达时间进 程 名到达时间运行时间开始时间完成时间周转时间带权周转时间时间片=1A020050502.5B010
7、134343.4C015245453.0D05320204.0平均周转时间；=37.25平均带权周转时间W =3.225时间片=5A020050502.5B010530303.0C0151045453.0D051520204.0平均周转时间；=36.25平均带权周转时间W =3.125感兴趣的同学还可以根据时间片从110 的变化，多计算几次，并分析每次计算得到的 平均周转时间，做一条平均周转时间随时间片变化的曲线，来体会时间片的变化对平均周转 时间的影响，并分析原因。思考题 2时间片轮转调度算法是为了（ ）。A.多个终端都能得到系统的及时响应B.先来先服务C.优先级高的进程先使用CPUD.紧急
8、事件优先处理3. 优先级法 算法描述：优先级调度算法总是从后备作业队列或进程就绪队列中选中优先级最高的作 业或进程。【例3】设有进程A、B、C、D依次进入就绪队列（相隔一个时间单位），它们的优先 级（数值大的优先级高）如下表所示：进程运行时间优先级A203B151C84D103试问采用“静态优先级”调度算法，选中进程的执行次序。分析 关于优先级和优先数优先级一般用某个固定范围内的整数表示，例如07或04095中的某一个数。这种 整数称作优先数。值得注意的是，优先级与优先数的对应关系因系统而异，在有些系统中优 先数越大，优先级越高；而另外一些系统则恰恰相反，优先数越小，优先级越高，如 UNIX/
9、Linux 系统就是这样。本书采用“优先数小、优先级高”的表示方式。为了简化优先 级的表示，避免优先级和优先数混淆，我们约定：在练习和考试中不使用优先数，直接用数 值表示优先级，数值大的表示优先级高。以本题为例，按照约定，进程 C 的优先级最高， 进程B的优先级最低。此外，静态优先级的含义是在进程运行期间，其优先级保持不变。而动态优先级往往是 根据系统的情况不断改变的，本题采用静态优先级使得问题的描述相对简单了。解：采用静态优先级，进程A最先就绪，在0时刻先占有CPU运行，随后1时刻进程 B进入就绪队列，2时刻进程C进入就绪队列，3时刻进程D进入就绪队列。由于采用静态 优先级，不容许随时间的推
10、移改变进程的优先级，所以当进程A运行结束时，系统的就绪 队列中有B、C、D三个进程，而进程C优先级最高，于是选中C；这样分析下去，进程的 执行次序是 A-C-D-B。思考题 3假定在单CPU条件下有下列要执行的作业：作业到达时间运行时间优先级1010221433235作业优先级从高到低的次序是5， 3， 2。在采用非抢占式优先级算法时，请计算各个作业的周转时间、平均周转时间、带权周转时间和平均带权周转时间。4三种调度算法的比较算法优点缺点先来先服务法简单易用，公平；有利于CPU繁忙型作业； 有利于长作业（或进程）；不利于I/O型繁忙型作业； 不利于短作业（或进程）； 效率低；时间片轮转法用于分
11、时系统，满足交互时间片的设置成为瓶颈，短了切换频 繁，降低CPU效率；长了影响交互 请求。优先级法在综合考虑各种因素的基础上， 急事先办如果优先级不能动态改变，低优先级 进程可能会“饥饿”值得注意的是，上面这些常用的调度算法常常结合使用，如时间片轮转法通常与先来 先服务法和优先级法结合使用。还有一些调度算法本身就包含着几种基本调度算法。不同的 系统和系统目标，采用的调度算法也不相同。思考题参考解答思考题 1：B 思考题 2：A 思考题 3：作业到达时间运行时间完成时间周转时间带权周转时间101010101.021417164.032313113.7平均周转时间12.3平均带权周转时间2.9说明：以上内容仅作为教学辅导材料，不作为考核内容。
