[操作系统]Week 4 Note

3.优先级调度Priority Scheduling

该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两 种方法来确定进程的优先权：

• 静态优先权: 静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有： 进程类型、进程对资源的要求、用户要求的优先权。
• 动态优先权: 动态优先权是基于某种原则，使进程的优先权随时间改变而改变。

Default：数字越小，优先级越高

Example 1（非抢占）：

Example 2（抢占）：

需要实时判断优先级/不同时加入

缺点：饥饿（starvation）

方法：老化（aging）as time progresses increase the priority of the process.—动态优先级

4.时间片轮转调度 Round Robin (RR)

• 基本思路：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资 源利用率。
• RR算法：
  • 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
  • 每次调度时将CPU分派给队首进程，让其执行一个时间片 (time slice) 。时间片的长度从 几个ms到几百ms。
  • 在一个时间片结束时，发生时钟中断。
  • 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行 当前的队首进程。
  • 进程可以未使用完一个时间片，就出让CPU（如阻塞）。

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

如果就绪队列中有n个进程，并且时间量为q，则每个进程一次最多以q个时间单位的块获取CPU时间的1 / n。 没有进程等待超过（n-1）q个时间单位。

• Performance
  • q large ->FIFO//先到先服务
  • q small ->q must be large with respect to context switch, otherwise overhead is too high//利用率低
• 时间片长度的影响因素：
  • 就绪进程的数目：数目越多，时间片越小（当响应时间一定时）
  • 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平 均周转时间和平均带权周转时间延长。

Example with Time quantum = 20

5.多级队列调度 Multilevel Queue Scheduling

根据进程的性质或类型的不同，将就绪队列再分为若干个子队列。

每个作业固定归入一个队列。

各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等 。如：系统进程、用户交互进程、批处理进程等。

• Ready queue is partitioned into separate queues:
  • foreground (interactive) 前台（交互式）
  • background (batch) 后台 （批处理）
• Each queue has its own scheduling algorithm:
  • foreground – RR
  • background – FCFS

6.多级反馈队列 Multilevel Feedback Queue Scheduling

• 多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：
  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程
  • 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
  • 不必估计进程的执行时间，动态调节
• 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍
• 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按”时间片轮转”算法调度直到完成。
• 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢占执行新进程，并把被抢占的进程投入原队列的末尾。

I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。

计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。

I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。

为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级；

Example：

Q0 – time quantum 8 milliseconds

Q1 – time quantum 16 milliseconds

Q2 – FCFS

//对短进程友好