数学建模社区-数学中国

标题: 进程调度算法（全网最细） [打印本页]

作者: 杨利霞 时间: 2021-4-9 15:33
标题: 进程调度算法（全网最细）

进程调度算法（全网最细）

写在前面：我是【程序员宝藏】的宝藏派发员，致力于创作原创干货。我热爱技术、热爱开源与分享，创作的【计算机基础面试问题】系列文章和【计算机基础主干知识】系列文章广受好评！后期会创作更多优质原创系列文章！如果您对计算机基础知识、编程等感兴趣，可以关注我，我们一起成长！

本人力荐：如果觉得CSDN排版不够美观，欢迎来我的个人原创公zong号【程序员宝藏】（号如其名，诚不欺你！）查看有红色重点标记和排版美观的全系列文章（不细你来找我要红包）
参考链接：TCP三次握手四次挥手

好多同学问我要pdf版，我干脆把全部文章都整理成了pdf直接打印版，在公zong号后台回复关键字【宝藏】即可免费带回家慢慢看！

相关系列文章：

TCP三次握手和四次挥手加拓展面试题（全网最细）
介质访问控制全网最细没有之一
路由算法（全网最细）
各层网络协议加面试拓展（全网最细）
各层网络设备加拓展（全网最细）
线程|进程|程序比较总结（全网最细）
死锁加拓展问题（全网最细）
文章目录
@[toc]
正文开始
1.前导知识简述
调度的基本评价准则
2.先来先服务调度算法（FCFS)
3.短进程优先调度算法（SPF）
4.优先级调度算法
5.时间片轮转调度算法
6.高响应比优先调度算法
7.多级反馈队列调度算法
正文开始
1.前导知识简述
【问】：为什么要进行处理机调度？
若没有处理机调度，同意味着要等到当前运行的进程执行完毕后，下一个进程才能执行，而实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的速度与处理机相比是非常缓慢的，若让处理机总是等待外部设备，则对处理机的资源是极大的浪费。而引进处理机调度后，可在运行进程等待外部设备时，把处理机调度给其他进程，从而提高处理机的利用率。用一句简单的话说，就是为了合理地处理计算机的软／硬件资源。

所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机。通常有以下两种进程调度方式：

非剥夺调度方式，又称非抢占方式。非剥夺调度方式是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程。
这种方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。

剥夺调度方式，又称抢占方式。剥夺调度方式是指当一个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程。采用剥夺式的调度，对提高系统吞吐率和响应效率都有明显的好处。
但“剥夺”不是一种任意的行为，必须遵循一定的原则，主要有优先权、段进程优先和时间片原则等

调度的基本评价准则
CPU利用率
系统吞吐量：单位时间内CPU完成作业的数量
周转时间：作业完成时间 - 作业提交时间
等待时间：等待时间指进程处于等处理机状态的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不影响作业执行或输入／输出操作的时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间。
响应时间：响应时间指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不可能是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。
2.先来先服务调度算法（FCFS)
FCFS 调度算法是一种最简单的调度算法，它既可用于作业调度，又可用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或儿个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

在过程调度中， FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。

FCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面的许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。

FCFS 调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SPF和高响应比）；有利于CPU繁忙型作业，而不利于I/0繁忙型作业。【跨考解答】：为什么CPU繁忙型是长作业，因为长短是使用CPU的长短，I/O繁忙型使用CPU比较短。

3.短进程优先调度算法（SPF）
短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短进程优先(SPF) 调度算法从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。（每次调度都选就绪队列中最短的）

SPF调度算法也存在不容忽视的缺点：1) 该算法对长作业不利。更为严重的是，若有一长进程进入就绪队列，由于调度程序总是优先调度那些（即使是后来进来的）短作业，将导致长作业长期不被调度（饥饿）。
2）该算法完全未考虑作业的紧迫程度，因而不能保证紧追性作业会被及时处理。
3）由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无
意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

【注意】 SPF调度算法的平均等待时间、平均周转时间最少。

4.优先级调度算法
在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为如下两种：

非剥夺式优先级调度算法。当一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。
剥夺式优先级调度算法。当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。
而根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：

静态优先级。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。
动态优先级。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据有进程占有CPU 时间的长短、就绪进程等待CPU 时间的长短。
一般来说，进程优先级的设置可以参照以下原则：

系统进程＞用户进程。系统进程作为系统的管理者，理应拥有更高的优先级。
交互型进程＞非交互型进程（或前台进程＞后台进程）。大家平时在使用手机时，在前台运行的正在和你交互的进程应该更快速地响应你，因此自然需要被优先处理，即要有更高的优先级。
I/0 型进程＞计算(CPU)型进程。我们知道， I/0 设备（如打印机）的处理速度要比CPU 慢得多，因此若将I/0 型进程的优先级设置得更高，就更有可能让I/0 设备尽早开始工作，进而提升系统的整体效率。
5.时间片轮转调度算法
时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间
的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如l00ms 。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。

在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。若时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此，时间片的大小应选择适当。

时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理
能力。

6.高响应比优先调度算法
高响应比优先调度算法是对FCFS调度算法和SPF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。响应比的变化规律可描述为:
响应比＝(等待时间＋要求服务时间)/要求服务时间
根据公式可知：

作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业。
要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。
7.多级反馈队列调度算法
多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展，如下图所示。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/0 设备利用率和缩短响应时间而照顾I/0 型进程；同时，也不必事先估计进程的执行时间。

多级反馈队列调度算法的实现思想如下：

设置多个就绪队列，并为各个队列赋予不同的优先级，第1 级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。
赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。例如，第2级队列的时间片要比第1级队列的时间片长1倍。
一个新进程进入内存后，首先将它放入第1 级队列的末尾，按FCFS 原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；若它在一个时间片结束时尚未完成，调度程序便将该进程转入第2 级队列的末尾，再同样按FCFS 原则等待调度执行；若它在第2 级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……
仅当第1 级队列为空时，调度程序才调度第2 级队列中的进程运行；仅当第1~(i-1)级队列均为空时，才会调度第i 级队列中的进程运行。若处理机正在执行第i 级队列中的某进程，这时又有新进程进入优先级较高的队列［第1~(i-1)中的任何一个队列］，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回第i 级队列的末尾，把处理机分配给新到的更高优先级的进程。
多级反馈队列的优势有以下几点：1) 终端型作业用户：短作业优先。2) 短批处理作业用户：周转时间较短。3) 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。

不要忘记去我的个人原创公zong号【程序员宝藏】----专注于计算机基础、编程、分享，获取【宝藏】哦！

————————————————
版权声明：本文为CSDN博主「程序员宝藏」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_42648261/article/details/106062122

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)