操作系统--------调度算法篇

目录

一.先来先服务调度算法（FCFS）

二.短作业优先调度算法（SJF）

2.1.SJF调度算法缺点

三.优先级调度算法

3.1优先级调度算法的类型

1.非抢占优先级调度算法

2.抢占优先级调度算法

3.2优先级的类型

3.1静态优先级

3.2动态优先级

3.3高响应比优先调度算法（HRRN）

四.轮转调度算法（RR）

4.1进程切换时机

例题

---

一.先来先服务调度算法（FCFS）

该算法可用于作业调度，也可用于进程调度

当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它会有限考虑在系统中等待时间最长的作业，而不管作业执行时间的长短

补充说明，FCFS调度算法在单处理机系统中已很少作为主要调度算法了，但通常会将它与其他调度算法结合使用，进而形成一种更为有效的调度算法

二.短作业优先调度算法（SJF）

SJF调度算法是以作业的长短来计算优先级的，作业越短，其优先级越高；作业的长短是以作业所要求的运行时间来衡量的

当SJF调度算法用于进程调度时，它将从就绪队列中选择估计运行时间最短的进程，并为之分配CPU运行

2.1.SJF调度算法缺点

1.必须预先知道作业的运行时间

2.对长作业非常不利，长作业的周转时间会明显增强

3.当采用SJF调度算法时，无法实现人机交互

4.SJF调度算法完全没有考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理

三.优先级调度算法

基于进程的紧迫程度，由外部赋予进程相应的优先级的，会根据该优先级进行调度。这样可以保证紧迫性进程优先运行。

优先级调度算法可用于作业调度，也可用于进程调度。当该算法用于作业调度时，系统将从后备队列中选择优先级最高的作业装入内存；当该算法用于进程调度时，系统将从就绪队列中选择具有最高优先级的进程在CPU运行

3.1优先级调度算法的类型

1.非抢占优先级调度算法

该算法规定，一旦把处理机分配给就绪队列中优先级最高的进程，在进程便会一直执行下去，直至完成或者当该进程因发生某事件而放弃处理器时，系统方将处理机重新分配给优先级次高的进程

2.抢占优先级调度算法

该算法规定再把处理机分配给优先级最高的进程，并使之执行时只要出现另一个优先级更高的进程，调度程序就会将处理机分配给新到的优先级更高的进程

3.2优先级的类型

3.1静态优先级

静态优先级是在创建进程时确定的，其在进程的整个运行期间保持不变，优先级是利用某一范围内的一个整数（如0~255的某一整数）来表示的，我们把该整数称为优先数

确定进程优先级大小的依据有3个:

1.进程类型，通常系统进程( 如接收进程，对换进程等)的优先级要高于一般用户进程的优先级

2.进程对资源的需求，对资源要求少的进程应被赋予较高的优先级

3.用户要求,根据进程的紧迫程度以及用户所付费用的多少，确定优先级

3.2动态优先级

动态优先级是在创建进程之初先赋予进程一个优先级，然后优先级会随进程的推进或等待时间的增加而改变，以便获得更好的调度性能

3.3高响应比优先调度算法（HRRN）

高响应比优先调度算法是优先级调度算法的一个特例，通常用于作业调度调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间，因此其既照顾了短作业，又不会致使长作业的等待时间过长，从而改善了处理机调度的性能

优先级的变化规律可表示为:
                                              优先级=（等待时间+要求服务时间）/ (除以) 要求服务时间

由于等待时间与要求服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比   =（等待时间+要求服务时间）/ 要求服务时间

            =   响应时间 / 要求服务时间

由上式可以看出 : 1.如果作业的等待时间相同，则要求服务时间越短，优先级越高，有利于短作业  2.当作业的要求服务时间相同时，其优先级又取决于等待时间 3.对于长作业的优先级，其可随等待时间的增加而提高，当作业的等待时间足够长时，其也可获得处理机

四.轮转调度算法（RR）

在分时系统中，最简单也是最常用的进程调度算法是基于时间片的轮转调度算法

4.1进程切换时机

在RR调度算法中，应在何时进行进程切换，可分为两种情况。①若一个时间片尚未用完而正在运行的进程便已经完成，则立即激活调度程序，将已经运行完成的进程从就绪队列中删除，再调度就绪队列中新的队首进程运行，并启动一个新的时间片。②当一个时间片用完时，计时器中断处理程序会被激活，此时，如果进程尚未运行完毕，调度程序就把它送往就绪队列的末尾

例题

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

带权周转时间=周转时间 / 服务时间

先来先服务 (FCFS)

进程	A	B	C	D	E	平均
到达时间	0	2	4	6	8
服务时间	3	6	4	5	2
完成时间	3	9	15	20	11
周转时间	3	2	11	14	3	8.6
带权周转时间	1	0.33	2.75	2.8	1.5	2.56

短作业优先（SJF）

非抢占

进程	A	B	C	D	E	平均
到达时间	0	2	4	6	8
服务时间	3	6	4	5	2
完成时间	3	9	13	18	20
周转时间	3	7	9	12	12	7.6
带权周转时间	1	1.17	2.25	2.4	6	1.84

抢占

进程	A	B	C	D	E	平均
到达时间	0	2	4	6	8
服务时间	3	6	4	5	2
完成时间	3	15	8	20	10
周转时间	3	13	4	14	2	7.2
带权周转时间	1	2.16	1	2.8	1	1.59

高响应比优先 （HRRN）

进程	A	B	C	D	E	平均
到达时间	0	2	4	6	8
服务时间	3	6	4	5	2
完成时间	3	9	13	20	15
周转时间	3	7	9	14	7	8
带权周转时间	1	1.17	2.25	2.8	3.5	2.14

时间片轮转（RR，q=1） 

进程	A	B	C	D	E	平均
到达时间	0	2	4	6	8
服务时间	3	6	4	5	2
完成时间	4	18	17	20	15
周转时间	4	16	13	14	7	10.8
带权周转时间	1.33	2.67	3.25	2.8	3.5	2.71

博主是从学校老师那里学的操作系统，还有很多不足之处，以上只是博主自己的理解

不足之处，还望大佬补充，我一定加以修改

博主会更加努力去学习操作系统，请期待博主下一篇文章 

猫猫跟你说，每天进步一点点，在未来的某一天，一定会看到见到！！

人只有坚持把自己变好，就真的会越来越好！！

让我们一起加油吧！！！！