Selfish RR(SRR, **, SRR, **)自私的时间片轮转

SRR是一种抢占式调度策略，在这种策略中，非阻塞（即就绪和运行）进程被分为两个类：被接受的进程-使用RR调度；其他的进程-在被接受之前不会运行。(也许SRR应该代表自私的RR)。

------------   被接受的 RR   +a  priority

------------   不被接受的 Wait  +b

• 一个新的进程的优先级为0；
• 一个可被接受进程的优先级以 的速率增加；
• 一个不可被接受进程的优先级以 的速率增加；
• 当一个不可被接受进程的优先级达到可被接收进程的优先级时它就会转变成一个可被接受的进程（如果当前没有可被接受的进程并且某个进程是所有其余进程中优先级最高的，那么他将被转为可被接受的进程）；
• 因此一旦一个进程可被接受，那么他将一直被接受，直到它终止或阻塞，此外，所有的可被接受的进程视为拥有相同的优先级；
• 当唯一被接受的进程终止或阻塞时所有下一个优先级最高的进程将被接受；

 

SRR的行为取决于a、b和0之间的关系。有四种情况。

• 如果a=0，变成RR，所有可接受的进程优先级都不再增加，那么只要是个进程就可以进入RR开始轮转；
• 如果a>b>0，变成FCFS，显然任何一个不可被接受的进程永远也追不上可被接受的；
• 如果a>b=0，变成批处理RR，很简单的理解就是只有当同一批进程处理完毕之后下一批优先级等于0的进程才会被接受，开始增加；

 

 

• 如果b>a>0，就产生有趣的情况了，会出现优先级的抢占；

  

这张图，b=0时batches，a=0时RR，a>b时FCFS，a<b时Interesting。

 

当进程阻塞时，不清楚该如何处理优先级，有以下几种可能性：

A. 当进程被阻塞时，将优先级重置为零。在这种情况下，unblock就优先级而言相当于create。

B. 将优先级冻结在其当前值。当它解除阻塞时，进程将具有与它被阻塞时相同的优先级。

C. 让优先级继续增长，就像进程没有被阻塞一样。生长速率可以是a或b，取决于在堵塞时该进程是否被接受。假设在阻塞期间，如果当前正在运行的其他进程终止，则这个进程是可以被转为被接受的。

第三种可能性似乎有点奇怪。我们将采用第一种方式（重置为零），因为它似乎是最简单的。

 

Approximating the Behavior of SFJ and PSJF近似SFJ和PSJF的行为

回想一下，SFJ/PSFJ在最小化平均等待时间方面做得很好。它们的问题是，很难确定哪个任务的下一次CPU突发最少，那我们现在学习三种调度算法来尝试确定最小的CPU突发时间。第一个算法是静态的，大概需要一些手动的帮助；另外两个是动态的，全自动的。

 

Multilevel Queues (**, **, MLQ, **) 多级队列调度算法

        将不同类别的进程被放在不同的队列中（对我来说，队列意味着FIFO），该方法可以应用优先老化来防止进程饥饿，但是并不能保证一定能服务到位于后端队列中的进程。

• 进程被分配到一个队列后就不会从当前队列转移到另一个队列；
• 队列间必须制定一个策略，例如存在两个队列分别是前端队列和后端队列，我们给定前端队列的绝对优先级一定比后端队列高，这样的话调度程序每次就会取前端队列的头部任务，直到前端队列为空后才会从后端队列的头部取任务；
• 另一种可能的队列策略是对每个队列都应用RR算法，但是每个大循环遍历高优先级队列两次，然后遍历低优先级队列一次；
• 必须为每个队列设置调度策略，这些策略在每个队列上可以是不同的，例如高优先级队列使用RR，而低优先级队列使用FCFS。优先级越高的队列的RR可以把q设置的更小一些。

 

Multiple Queues (FB, MFQ, MLFBQ, MQ) 多级反馈队列优先调度算法

和MLQ类似，该方法中仍然会有很多队列，但是现在允许进程从一个队列移动到另一个队列，试图动态的将批处理类进程与交互进程分离开，以便于我们更倾向于选择交互式进程进行处理。SJF和PSJF的特性带来了很低的平均等待时间，多队列调度方法尝试动态确定哪些进程是交互式的（即具有很短的CPU Burst的进程）。

• 使用RR调度算法从优先级最高的非空队列中运行进程，当一个进程完整的使用了它的时间片时意味着他是一个长CPU绑定任务，此时把这个进程移动到一个低优先级队列；
• 反之，当一个进程没有完整的使用完它的时间片时，例如产生了一系列的硬件设备中断和I/O中断，那么它更像是一个交互进程，需要将他移动到一个更高优先级的队列；
• 因此带来的一个问题是，一个频繁产生I/O的CPU绑定型任务可能会被保留在高优先级的队列中；
• 低优先级队列会应用FCFS调度算法；
• 同样的，使用优先老化的方式可以用来预防进程饥饿；

本方法拥有很多变体：a. 在某些情况下可能不产生降级或升级，仍然会回到当前所属队列的尾部；b. 只认为鼠标键盘的I/O中断导致的时间片未运行完成使其升级，忽略I/O对进程造成的中断。

 

Shortest Process Next最短进程优先算法

        最短进程优先算法是将SJF算法应用于交互式系统进程调度的一种尝试，其需要的是对进程一般会运行多长时间的有效估计（在阻塞前或时间片用完前）。一种方法是在进程开始时做一些初始估计，然后在进程阻塞时使用下面的公式计算一个新的估计值：

NewEstimate=A * OldEstimate + (1 - A) * LastBurst

式中：0 < A < 1， 是上一次进程CPU Burst的实际时间。

 

Highest Penalty Ratio Next最高惩罚比优先算法

        优先运行受伤hurt最严重的进程。

• 对每个进程而言，设定 ，T是这个进程从启动开始到现在的总时间，t是这个进程从启动开始的运行时间；例如 表明这个任务已经运行了 的时间。
• 我们将 称之为惩罚比，然后选择 值最大的进程开始运行；
• 为了让 不产生除以0的错误，新生成的进程的 值被设定为Max/1，说明优先级最高；
• HPRN被认为是非抢占式的，但是它有一个类似的变体：a. 当进程进入运行态时计算一下它会在什么时候不再具有最大的受伤程度，并按这个时间设置计时器；b. 当进程进入就绪态时计算它的 值并准备抢占。

 

Guaranteed Scheduling保证调度

        HPRN的一个变种，惩罚值与HPRN不同，可以理解为上述惩罚比的倒数：

r = t / (T / n)

式中：n是多道编程的道数，如果n是一个常数，这个比值是常数乘上 ，我们选择去运行这个值最小的进程。

 

Lottery Scheduling彩票调度

每个进程获得固定数量的票证，在每个调度事件中抽取一个随机票证（带有替换），持有该票证的进程在下一个时间间隔（可能是一个类似于RR的时间片长度q）运行。平均而言，拥有P %票证的进程将获得P %的CPU（假设没有阻塞）。

 

Fair-Share Scheduling公平分享调度

如果你公平地对待进程，你可能就没有公平地对待系统用户，因为拥有许多活动进程的用户将比拥有较少进程的用户获得更多的服务，显然此时是不公平的。假设系统中有两个用户存在，则公平分享调度首先将会分配给每个用户50%的CPU时间，那么无论一个用户开辟了多少个进程，他也不会得到属于另一个用户的50%的CPU时间。

例如，linux有用于相关目的的cgroups。调度器首先跨cgroups进行调度，所以如果一个大的任务有很多进程在同一个cgroup中，它将被视为只有一个进程的任务。已经实现了一些更新颖的方法，为用户组提供了一些公平。假设一组人支付了电脑成本的30%。如果该组至少有一个活动的进程，它将有权获得30%的cpu周期。此外，当一个组没有活动的流程时，它会获得一些积分。

 

Medium-Term Scheduling中期调度

除了我们已经讨论过的短期调度外，我们还考虑了中期调度，在中期调度中，决策是在较粗的时间尺度上做出的。回想一下我最喜欢的图表，在右边再次显示。中期调度决定了从顶部三角形到底部行的转换。如果内存被过度使用，我们挂起（交换）某个进程，在图中删除（就绪或阻塞）进程。我们还需要恢复过渡以返回顶部三角形的过程。

选择暂停受害人的准则包括：

• 上次暂停多久了?
• 最近使用了多少CPU时间。
• 它使用多少内存。
• 外部优先(支付更多，交换更少)。

当我们学习内存管理和理解什么是内存过度使用时，我们将再次讨论中期调度。

Long Term Scheduling长期调度

        有时也被称为作业调度。

• 系统决定何时启动作业，也就是说并不一定在作业提交之后就被立即启动；
• 适用于超级计算机站点；

 

Review Homework

Assigned Last Time回顾作业

Process	CPU Time	Start Time	Blocks after/for
P0	10	0	5	9
P1	11	4	4	6
P2	9	4	never

考虑下面与作业相同类型的问题。在这个例子中，我们有q=3且上下文切换时间为零的RR调度。系统包含三个进程。它们的相关特征见右表。注意，在本例中，只处理该块一次。

下图给出了一个详细的解决方案。水平线上方的数字表示执行间隔开始和结束时剩余的CPU时间。水平线下面的数字表示执行间隔的长度。红线表示进程受阻。我们看到P2在时间21结束，P0在时间23结束，P1在时间30结束。

 

有几个问题可以思考一下，也是计算这种题目通常忽略的一些条件

1.      进程本质上只能Fork()出来，那么是不是当一个进程Arrive的时候应当产生一次调度？

2.      当一个进程的I/O结束时会向CPU发送中断信号，此时是否应当执行一次调度？

Process	CPU Time	Start Time	Blocks after/for
P0	10	0	5	9
P1	11	4	4	6
P2	9	4	never

Q=3

 

1. 新进程进入不调度；
2. 硬盘I/O不调度；
3. 多个进程同时进入就绪态按202规则，按字母序排列；