目录
1.先来先服务调度算法（FCFS）2.优先级调度算法3.最短作业优先调度算法（SJF）4.最高响应比优先调度算法（HRRN）5.轮转调度算法（RR）6.多级反馈轮转调度算法7.实时系统的调度算法
1.先来先服务调度算法（FCFS）
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 先来先服务（First-Come-First-served）调度算法是最简单的非抢占的调度算法。
∙
\bullet
∙ 它通过管理一个FIFO就绪队列来实现，从前到后按顺序将CPU分配给进程。
举例：
{\color{Violet}举例：}
举例：
∙
\bullet
∙ 现在有如下一组进程：
进程执行时间P130P25P32
所以执行顺序为
<
P
1
、
P
2
、
P
3
>
所以可以计算求得三个进程的平均等待时间为：
0
+
30
+
35
3
≈
21.7
{\color{Red}\frac{0+30+35}{3}≈21.7}
30+30+35≈21.7
特点：
{\color{Violet}特点：}
特点：
∙
\bullet
∙ FCFS调度算法对短进程不利，尤其当一个短进程跟在长进程后面时，它需要等待很长的时间。有时候会导致CPU和设备的利用率很低，在实际情况中，FCFS算法通常与其他算法结合使用。
2.优先级调度算法
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 由用户或者系统按照某种原则给进程一个优先级，系统总是调度优先级最高的那个进程运行。
∙
\bullet
∙ 优先级可以分为静态优先级和动态优先级。静态优先级就是指优先级确定以后就不再改变，比如说按照它们的执行时间长短来确定等等；动态优先级会随着进程的不断执行而发生改变，比如说可以按照等待时间的长短划分优先级等等。
∙
\bullet
∙ 对优先级动态调整可以改善系统性能，但是动态优先级调度算法会增加系统开销。
举例：
{\color{Violet}举例：}
举例：
∙
\bullet
∙ 现在有如下一组进程（采用静态优先级调度算法）：
进程执行时间优先级P195P241P323P414
所以执行顺序为
<
P
2
、
P
3
、
P
4
、
P
1
>
所以可以计算求得四个进程的平均等待时间为：
0
+
4
+
6
+
7
4
=
4.25
{\color{Red}\frac{0+4+6+7}{4}=4.25}
40+4+6+7=4.25
特点：
{\color{Violet}特点：}
特点：
∙
\bullet
∙ 可能会出现“饥饿”现象，就是优先级低的进程会一直等待CPU，未来避免这种问题的出现，我们可以采用“老化”的策略，就是按一定时间间隔提高等待进程的的优先级数值。
∙
\bullet
∙ 我们假设它们几乎同时到达，但是实际情况中总会有先后顺序，在支持抢占的系统中，当新进程进入就绪队列时，如果它的优先级高于当前运行进程的优先级，那么就会抢占CPU；在非抢占系统中，只是将新进程加入了就绪队列中。
3.最短作业优先调度算法（SJF）
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 最短作业优先（Shortest-Job First）调度算法克服了FCFS的对短进程不利的缺点，它在就绪队列中选择处理时间最短的进程，如果时间相同则可以按照FCFS准则来处理。
∙
\bullet
∙ 它提高了系统的吞吐量，但是反过来又对长进程不利。
∙
\bullet
∙ 它分为抢占式和非抢占式两种情况
举例：
{\color{Violet}举例：}
举例：
∙
\bullet
∙ 现在有如下一组进程，假设它们同时到达（非抢占式）：
进程执行时间P15P24P39P43
所以执行顺序为
<
P
4
、
P
2
、
P
1
、
P
3
>
0
+
3
+
7
+
12
4
=
5.5
{\color{Red}\frac{0+3+7+12}{4}=5.5}
40+3+7+12=5.5
∙
\bullet
∙ 现在有如下一组进程，假设它们不同时到达（抢占式）：
进程到达时间执行时间P108P214P329P435
最初只有P1进程，那么执行P1进程；当时间1时P2到达，此时P1剩余执行时间为7，P2执行时间为4，那么执行P2进程；当时间2时，P3到达，此时最短执行时间仍然为P2；时间3时，P4到达，此时P2执行时间为2，P4也为2，所以先让P2执行完在让P4执行，然后再让P1执行，最后在让P3执行。
所以执行顺序为 KaTeX parse error: Expected 'EOF', got '}' at position 31: …{4}、P_{1}、P_{3}}̲>，我们画出它的甘特图如下：
所以可以计算求得三个进程的平均等待时间为：
(
(
10
−
1
)
+
0
+
(
17
−
2
)
+
(
5
−
3
)
)
4
=
6.5
{\color{Red}\frac{((10-1)+0+(17-2)+(5-3))}{4}=6.5}
4((10−1)+0+(17−2)+(5−3))=6.5
分母上面的式子为每个进程开始执行的时间减去开始等待的时间之和。
特点：
{\color{Violet}特点：}
特点：
∙
\bullet
∙ 对于非抢占的SJF调度算法，可以看作是优先级调度算法的一种特例。
4.最高响应比优先调度算法（HRRN）
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 最高响应比（Highest Response Ratio Next）调度算法集合了FCFS算法和非抢占SJF算法的优点，使用响应比R来表征，即：
R
=
W
+
S
S
(
W
为等待时间、
S
为预计执行时间
)
R = \frac{W+S}{S} \ (W为等待时间、S为预计执行时间)
R=SW+S (W为等待时间、S为预计执行时间)
∙
\bullet
∙ 在该算法下，等待时间相同的时候短进程响应比高于长进程，短进程优先被调度；而随着等待时间增长，进程的响应比增加，长进程被调度的可能性也会增加。
举例：
{\color{Violet}举例：}
举例：
∙
\bullet
∙ 现在有如下一组进程如下：
进程到达时间执行时间P1010P211P322P431P545
∙
\bullet
∙ 0时刻P1运行，10时刻P1运行完毕，此时P2 ~ P5的响应比为：
P
2
:
1
+
9
1
=
10
;
P
3
:
2
+
8
2
=
5
;
P_{2}:\frac{1+9}{1}=10 ;\ \ \ P_{3}:\frac{2+8}{2}=5;
P2:11+9=10; P3:22+8=5;
P
4
:
1
+
7
1
=
8
;
P
5
:
5
+
6
5
=
2.2
;
P_{4}:\frac{1+7}{1}=8 ;\ \ \ P_{5}:\frac{5+6}{5}=2.2;
P4:11+7=8; P5:55+6=2.2;
∙
\bullet
∙ 所以P2运行，直到11时刻运行结束，此时P3 ~ P5的响应比为：
P
3
:
2
+
9
2
=
5.5
;
P
4
:
1
+
8
1
=
9
;
P
5
:
5
+
7
5
=
2.4
;
P_{3}:\frac{2+9}{2}=5.5 ;\ \ \ P_{4}:\frac{1+8}{1}=9; \ \ \ P_{5}:\frac{5+7}{5}=2.4;
P3:22+9=5.5; P4:11+8=9; P5:55+7=2.4;
∙
\bullet
∙ 所以P4运行，直到12时刻运行结束，此时P3 和 P5的响应比为：
P
3
:
2
+
10
2
=
6
;
P
5
:
5
+
8
5
=
2.6
;
P_{3}:\frac{2+10}{2}=6 ;\ \ \ P_{5}:\frac{5+8}{5}=2.6;
P3:22+10=6; P5:55+8=2.6;
∙
\bullet
∙ 所以先执行P3，后执行P5。
∙
\bullet
∙ 所以执行顺序为 KaTeX parse error: Expected 'EOF', got '}' at position 31: …{4}、P_{3}、P_{5}}̲>，我们画出它的甘特图如下：
所以可以计算求得五个进程的平均等待时间为：
(
0
+
(
10
−
1
)
+
(
11
−
2
)
+
(
12
−
3
)
+
(
14
−
4
)
)
5
=
7.4
{\color{Red}\frac{(0+(10-1)+(11-2)+(12-3)+(14-4))}{5}=7.4}
5(0+(10−1)+(11−2)+(12−3)+(14−4))=7.4
5.轮转调度算法（RR）
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 轮转（Round Robin）调度算法是一种基于抢占的调度策略，在分时系统中，每个进程会被分配一个固定的时间片，就绪队列中的进程按顺序依此调度运行。
∙
\bullet
∙ 时间片过短会使进程切换过于频繁，增加系统开销；时间片过长会使进程响应时间增加。
举例：
{\color{Violet}举例：}
举例：
∙
\bullet
∙ 现在有如下一组进程如下：
进程执行时间P124P23P33
这里时间片我们选择为4，按照原理可得甘特图如下： 所以可以计算求得三个进程的平均等待时间为：
6
+
4
+
7
3
≈
5.67
{\color{Red}\frac{6+4+7}{3}≈5.67}
36+4+7≈5.67
6.多级反馈轮转调度算法
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 是对简单轮转调度算法的改进，它把新就绪的进程和被抢占后回到就绪队列的进程加以区分，将它们放入不同优先级的就绪队列中；
∙
\bullet
∙ 被抢占后放回就绪队列的进程优先级会降低，但是运行的时间片长度会增加。
7.实时系统的调度算法
原理：
{\color{Violet}原理：}
原理：
∙
\bullet
∙ 在实时系统中会给出一个最后期限，最后期限指定任务开始或结束的时间，任务必须严格按照最后期限执行。