-
Notifications
You must be signed in to change notification settings - Fork 32
/
4、CPU 调度算法与实现.md
189 lines (111 loc) · 11.5 KB
/
4、CPU 调度算法与实现.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
# CPU 调度
## 含义与算法准则
含义
* CPU 调度就是在就绪线程/进程队列中选择一个合适的线程/进程，再通过切换机制将 CPU 资源分配给选择出来的线程/进程。
* 如果操作系统支持线程，线程是 CPU 调度的基本单位，否则进程就是 CPU 调度的基本单位。
准则
* CPU 调度的关键在于如何确定哪一个任务更合适
* 是目前为止最先来的任务呢？
* 还是在其他特性上满足一定条件的后到任务？
* CPU 调度是一个没有对错的算法，只要从就绪队列中选择出来一个任务就是正确的调度算法
* CPU 调度只有好坏之分，即给出的调度选择是否更加合适。
* 要确定“是否更加合适？”，就要定义出一个标准来度量调度算法的“合适性”。因此，要想设计、实现出好的 CPU 调度算法，首先需要定义明确的算法度量标准。
* 不同场景下的操作系统任务调度，调度策略的目标不同，调度算法的设计和实现原则也不同。
* 因此没有必要追求“尽量多地学习各种具体的 CPU 调度策略”，而应该学会针对一种工作场景能深入分析，设计出合适的 CPU 调度算法，并能在遇到其它具体工作场景时做到举一反三。
PC 机上的任务调度策略主要考虑如下三个基本准则：
* 任务的周转时间，是任务从新建进入操作系统到该任务完成离开操作系统所经历的全部时间。
* 任务的响应时间，是从用户向某程序发起一个交互操作到该任务响应这个操作之间经历的时间，例如从点击菜单到菜单弹出的这段时间。
* 系统吞吐量，是一段时间区域内计算机系统能完成的任务总数。
交互式任务和非交互式任务
* 在 PC 机上，交互式任务和非交互式同时存在，而且这两种任务有各自的目标
* 交互式任务不关心周转时间，强调响应时间；
* 非交互式任务关心周转时间，在执行过程中无需交互。
* 这两个目标背后存在着一定的矛盾，是不可能同时优化的
* 例如为了提高交互式任务的响应时间，就要提高这些任务的优先级，这会导致非交互任务得到的 CPU 资源少，其周转时间必然要增多，等等。
* 在两类任务同时存在的背景下，给出能有效折中的任务调度策略就成为通用操作系统在实现 CPU 调度时要分析的核心问题
## 若干基本算法
1、 先来先服务调度，FCFS
* 先来先服务调度（First Come, First Served，简称 FCFS），算法非常简单，就是选择就绪队列头部的那个任务调度执行。
* 这个算法除了简单、易于实现以外，还有一个重要特性 公平
* 绝对公平地对待所有任务导致 FCFS 算法无法利用任务特征实现任务调度的整体优化
* 例如对于一个简单询问的银行业务，可让其优先执行，这会让所有任务的平均周转时间变短。
* 提供绝对公平是没有必要的，而通过适当改变任务的调度顺序来实现多个任务的总体优化，如最小化平均周转时间是很有意义的。
* 让一个任务执行时间短的任务 短作业提前执行，那么这个任务后面的其它任务就有可能早一点开始执行，当然其周转时间会变小，将这个思想一般化以后就是短作业优先调度算法。
2、短作业优先调度，SJF
* 短作业优先调度（Shortest Job First，简称 SJF）的算法思想也很简单，就是按照任务的执行时间从小到大排序，任务按照这个顺序依次调度执行。
* 在实际环境中，任务不可能一下子都出现在零时刻，所以短作业优先调度只具有理论意义。实际环境中可以工作的是剩余短作业优先调度算法（Shortest Remaining Time First，简称 SRTF）。
* 每次新任务到达时，选择当前剩余执行时间最短的那个任务调度执行
* SRTF 调度是一种可抢占式调度，即不是由于任务自身主动让出 CPU才引起的调度；也不是发生诸如当前任务结束、当前任务阻塞时间才引起的调度。只要有新任务出现，就有可能出现这个任务抢占当前任务的 CPU
3、轮转调度，RR
* 在通用操作系统中，除了非交互式任务以外，也存在交互式任务
* 在 SRTF 中，任何任务要等到前面的任务全部执行完成以后才被调度，所以最差的用户响应时间就可能很大。
* 而且真正实现 SRTF 算法，需要知道“任务执行时间”这个参数。任务执行时间是任务得到 CPU 以后将会执行的时间长度，只有任务执行完成以后才能知道。所以 SRTF 所需参数“任务执行时间”是不可能准确已知的，最多只能近似。
* 时间片轮转调度（Round Robin，简称 RR）的基本思想：
* 将一段时间等分的分割给每个任务，即给每个分配一个执行时间片，当前任务的时间片用完时就切换到下一个任务，下一个任务的时间片用完时再切换，这样一段时间内让所有任务都有机会向前运行。
* RR 调度时的用户响应时间（Response Time，简称 RT）满足条件：RT ≤ N × τ
* 可以保证用户响应时间的上界。比如规定一个操作系统中最多可创建 100 个任务，并且想让最大响应时间保证在 1 秒内（1 秒内的响应延迟用户几乎觉察不到），则 τ ≤ 1s/100 ≤ 0.01s ≤ 10ms。
* 通过对操作系统参数的合理设计，RR 调度算法可以保证用户的响应时间，因此 RR 是交互式任务调度的解决方案。
4、多级队列调度
* 如何组合 RR 和 SRTF 来处理交互任务和非交互任务同时存在的情况
* 引入两个就绪队列，交互任务队列和非交互任务队列，由于任务是和用户进行交互，所以该任务队列通常也被称为是前台任务队列，相应的非交互任务队列被称为是后台任务队列。
* 两个队列分别采用两个不同的调度策略：前台队列采用 RR 调度，后台队列采用 SRTF 调度。
* 还需要定义各级任务队列之间之间的关系，常用的方式是定义一个优先关系
* 通常让前台队列具有更高的优先级，即如果前台队列中存在就绪任务，就一直采用 RR 调度处理这个队列中的任务。
5、多级反馈队列调度
* 第一个问题：多级队列调度，不能造成的饥饿
* 如果采用非抢占式调用，此时一旦后台任务调度得到CPU，就只能等到执行完后才能释放 CPU，这段时间到达的前台任务其最差响应时间就可能很长。
* 而如果采用抢占式调度，即只要有前台任务出现，就必须切换到前台任务队列，而且要一直等到前台队列中没有任务才能调度到后台队列
* 解决这个两难问题的方法是：即使有前台任务后台任务也能调度到 CPU，但又不能等待后台任务执行完成才让出 CPU
* 第二个问题：前台任务和后台任务区分
* 如何知道哪些任务是前台任务，哪些任务是后台任务
* 另外前后台任务也不是一成不变的，一个编辑文本的任务看起来是前台任务，但文本编辑器执行文本检查时还算是前台任务吗？编译任务看起来是后台任务，但是在编译过程中用 CTRL+C 中断编译过程难道就不算是用户交互吗？
* 所以多级队列调度中的任务类型不应该是在任务创建时就固定下来的，应该能根据任务在执行过程的具体表现而动态调整
* 因此，如何动态调整就成为多级反馈队列调度的核心。比较容易想到的动态调整方案有按照 **I/O 动态调整**和**按照执行时长动态调整**
* 按 I/O 动态调整的方案可以近似解决前台任务识别的问题，因为交互的含义就是“和用户通过 I/O 进行交互”。
* 如果一个任务最近一段时间发生了 I/O，根据局部性原理，最近发生了 I/O，接下来也很可能会发生 I/O，这个任务将要表现出交互式任务的特征，可以认为该任务是前台任务，将其放在高优先级队列中
* 如何识别发生了 I/O 动作呢？一个简单而可行的方法是记录阻塞态，因为发生 I/O 动作通常总会引起进程阻塞。
* 按照执行时长进行调整，具体来说，如果一个任务在执行完一个时间片以后仍然要继续执行，说明该任务最近没有发生 I/O 操作，也没有执行完成。
* “没发生 I/O 操作”可以近似认定这个任务是一个非交互任务
* “没执行完成”可以近似认定这个是一个长作业，此时就将这个任务的优先级降低。
* 总的来说，多级反馈队列调度：
* （1）有效地综合了交互式任务的调度和非交互式任务的调度；
* （2）针对任务周转时间进行了适当优化；
* （3）任务的响应时间可以保证在一个用户可以接受的范围内；
* （4）在实际环境中可行，不需要用户定义任务的种类，不需要输入任务时长等苛刻的参数。因此多级反馈队列调度比较适合在 PC 等机器上的通用操作系统上工作
## 多级反馈队列实现
在这个 schedule() 函数中，针对每个任务只用维护一个 counter 变量，而不用维护多个队列，算法很简单，可以高效地的执行。
```c
void Schedule(void)
{
while(1)
{
c=-1; next=0; i=NR_TASKS;
p=&task[NR_TASKS];
// 遍历所有 task
while(--i)
{
// 每次调度都要从就绪队列中找到 counter 值最大的那个任务，一旦找到就切换到那个任务。
if((*p->state == TASK_RUNNING && (*p)->counter>c)
c=(*p)->counter, next=i;
}
// 如果找到就推出
if(c) break;
for(p=&LAST_TASK; p>&FIRST_TASK; -–p)
// 如果是时间片用完的任务，其时间片会被重置为 priority。
// 而对于阻塞任务，阻塞时其 counter 必定大于 0，所以阻塞以后的任务经过
// (*p)->counter=((*p)->counter»1)+(*p)->priority 调整以后，其 counter 必然大于 priority
// 即:阻塞任务的优先级一定会大于那些没有经过阻塞的任务，实现了“交互式前台任务的优先级更高”
(*p)->counter=((*p)->counter»1)+(*p)->priority;
}
switch_to(next);
}
```
控制这个调度算法的关键是 counter 变量，
* counter 的第一个作用是时间片
* 因为 counter 还要出现在另一个地方 时钟中断中，时钟中断（在该计算机系统中对应 0x20 号中断）的处理函数被初始化为 `set_intr_gate(0x20, &timer_interrupt`。
* 每次时钟中断，timer_interrupt 都会将当前任务的 counter 减 1，如果当前任务的 counter 被减为0，就调用 schedule() 函数进行线程切换，`if((–current->counter == 0) schedule();`
* counter 还有另外一个作用，那就是任务的优先级，
* counter 最大，对应的任务优先级就最大，这是多级反馈队列调度的另一个基础 优先队列。
充当优先级的 counter 在动态调整时仍然能完成时间片目标
* 因为必须经过一个完整的轮转周期之后，才会给所有任务一起重新计算优先级