OSTEP [虚拟] Chapt. 07-11 调度算法

分类:Operating System, 发布于:2019-04-16 18:21:17, 更新于:2019-04-19 00:09:40。 评论

7.1 Workload Assumptions

我们针对进程(任务)做出以下(理想化的)假设:

  1. 每个任务可以执行相同的时间;
  2. 所有任务同时到来;
  3. 一旦开始,任务一直执行到结束;
  4. 所有任务只使用CPU(不进行I/O操作);
  5. 每个任务的运行时间是相同的。

7.2 Scheduling Metrics

对调度方法的评判标准简化为使用turnaround time进行比较,定义为 $$T_{turnaround} = T_{completion} - T_{arrival}$$ 因为假设所有任务同时到来,$T_{arrival} = 0$,且$T_{turnaround} = T_{completion}$

Turnaround time是性能评估标准,而不是公平性评估标准。

7.3 First In, First Our (FIFO)

FIFO又名First Come, First Served (FCFS)。其具有一些优点:简单、易于实现,且在假设条件下效果不错。

在上面的例子中,平均完成时间为10s。

但如果每个任务所需时间不同,FIFO的效果就很差。如上面这个例子的平均完成时间为110s。这个问题叫做护卫效应(convoy effect),大部分小的任务排在了一个大任务的后面。

7.4 Shortest Job First (SJF)

耗时(开销)小的任务先来,以此类推。在上面的例子中,平均完成时间降低到了50s。

因为我们假设所有任务同时到来,所以在这个条件下可以保证SJF是最优调度算法(贪心)。

如果A比BC先到来,上面的运行时间就又增长回103.33s。

7.5 Shortest Time-to-Completion First (STCF)

为了解决这个问题,可能需要具有一些机能的调度器。例如:当BC到来时,OS可以抢占运行权力,暂停A,让BC先执行。

只需要给SJF加上抢占能力,就可以得到STCF调度器(又称Preemptive Shortest Job First, PSJF调度器)。

每当新任务到来,STCF判断谁最先完成,然后调度到该任务继续执行。上图中总时间变回了50s。

7.6 A New Matric: Response Time

响应时间定义为从任务到来到第一次执行它之间的时间间隔。 $$T_{response} = T_{firstrun} - T_{arrival}$$ 例如在Figure 7.5中,AB的等待时间为0,C的等待时间为10s。

7.7 Round Robin

Round Robin(RR)调度算法的想法是:每次花一段时间(time slice/scheduling quantum)执行一个任务,然后切换到队列的下一个任务。因此,RR也被叫做time-slicing

对于RR算法来说,决定一次运行的时间是非常重要的。运行时间越短,在响应时间标准下RR效果越好,但切换上下文的开销会拖累总体的性能。因此,时间切片的长度是一个trade-off,时间长可以均摊(amortize)切换上下文的开销。

TIP: Amortization Can Reduce Costs

The general technique of amortization is commonly used in systems when there is a fixed cost to some operation. By incurring that cost less often (i.e., by performing the operation fewer times), the total cost to the system is reduced. For example, if the time slice is set to 10 ms, and the context-switch cost is 1 ms, roughly 10% of time is spent context switching and is thus wasted. If we want to amortize this cost, we can increase the time slice, e.g., to 100 ms. In this case, less than 1% of time is spent context switching, and thus the cost of time-slicing has been amortized.

但是RR在完成时间上并不是一个高效的策略,甚至比FIFO还差。

笼统地说,任何通过划分CPU执行时间来保持公平的调度算法都在完成时间上效果不咋地。实际上,这是一个内在的trade-off:如果你要不公平,你可以让跑得快的任务早点完成,但是响应时间就很长;否则,你要减少响应时间,完成时间就会很长。此类trade-off在系统中非常常见,鱼和熊掌不可兼得。

至此,共有两类调度算法:第一类(SJF, STCF)优化完成时间,但响应时间高;第二类(RR)优化响应时间,但完成时间长。

7.8 Incorporating I/O

任务执行I/O操作时会被阻塞,直到I/O操作完成。如果进行硬件读写,就可能会导致几毫秒的等待。因此,调度算法必须在I/O操作出现时合理的切换到别的任务。

当I/O操作完成时,会产生硬件中断,此时OS接管并将发起请求的进程调回ready状态。

TIP: Overlap Enables Higher Utilization

When possible, overlap operations to maximize the utilization of systems. Overlap is useful in many different domains, including when performing disk I/O or sending messages to remote machines; in either case, starting the operation and then switching to other work is a good idea, and improves the overall utilization and efficiency of the system.

一种通常的解决方法是把进程的每一个部分都当作一个独立的任务。如果进程发起I/O请求,那么这个子任务就结束,OS可以切换到下一个任务。这样做出现了重叠(overlap),CPU可以在等待I/O的时间内执行另一个任务,更好地利用资源。

TIP: Learn From History

The multi-level feedback queue is an excellent example of a system that learns from the past to predict the future. Such approaches are common in operating systems (and many other places in Computer Science, including hardware branch predictors and caching algorithms). Such approaches work when jobs have phases of behavior and are thus predictable; of course, one must be careful with such techniques, as they can easily be wrong and drive a system to make worse decisions than they would have with no knowledge at all.

第8章介绍了最常见的算法之一:多级反馈队列(Multi-level Feedback Queue, MLFQ)。

8.1 MLFQ: Basic Rules

MLFQ有一些不同的队列(queue),每个都有不同的优先级(priority level)。在任意时刻,一个即将运行的任务只会在一个队列中。MLFQ利用优先级来决定运行谁:选择一个具有更高优先级(位于更高队列中)的任务继续执行。

当然,一个队列可能有多个任务,它们有同样的优先级。此时利用RR来进行调度。

MLFQ的基本规则为:

  • 规则1:如果A的优先级大于B的优先级,运行A;
  • 规则2:如果A、B优先级相同,用RR调度它们。

MLFQ根据它观察到的进程行为来区分进程之间的优先级。例如,一个不断主动放弃CPU等待键盘输入的进程会拥有高优先级;而长时间使用CPU计算的进程的优先级会被降低。MLFQ会尝试学习运行的进程的历史,来决定它未来的行为。

8.2 Attempt #1: How To Change Priority

我们认为负载有两种:一种是运行时间短,需要交互(可能经常主动放弃CPU)的任务;另一种是长时间占用CPU,响应时间不重要的任务。对此,优先级调整算法如下:

  • 规则3:当一个程序进入系统,默认优先级是最高的。
  • 规则4a:如果程序使用了整段运行时间,降低优先级;
  • 规则4b:如果程序在时间结束前主动放弃CPU,保持优先级不变。

对一个单独的进程来说,每10ms一次的时间都会用满,很快他就被降低到了最低优先级。

如果任务A运行途中加入了一个响应式的任务B(灰色部分),B的优先级更高,于是先运行。20ms后B结束退出,此时继续执行优先级最低的任务A。

MLFQ会先假设程序运行时间短,给予最高优先级;如果假设不成立,优先级会逐步降低,最后MLFQ发现程序的运行时间长,优先级为最低。此时MLFQ的行为更像SJF。

如果任务A需要较长时间,任务B每次只需要1ms就会主动放弃,那么MLFQ就会保持B的高优先级。

但是,这样的MLFQ会带来一个问题:如果系统中有太多交互型的程序,他们的优先级高,会保持对CPU的占用,那么低优先级的程序就永远无法得到CPU时间(starve)。

其次,恶心人的用户会破坏调度算法的合理性(game the scheduler),在时间截止前进程发起一个(不关心结果的)I/O请求来放弃CPU,就可以保持在同一个优先级队列中,获得更多的CPU时间。

最后,进程的行为可能随时间改变,一个计算型程序可能会变为交互型程序。此时这个程序无法重新获得优先级,响应时间高。

TIP: Scheduling Must Be Secure From Attack

You might think that a scheduling policy, whether inside the OS itself (as discussed herein), or in a broader context (e.g., in a distributed storage system's I/O request handling), is not a security concern, but in increasingly many cases, it is exactly that. Consider the modern datacenter, in which users from around the world share CPUs, memories, networks, and storage systems; without care in policy design and enforcement, a single user may be able to adversely harm others and gain advantage for itself. Thus, scheduling policy forms an important part of the security of a system, and should be carefully constructed.

8.3 Attempt #2: The Priority Boost

我们可以间歇性地提高所有任务的优先级,书中采用的方法是把所有的任务放到最高优先级的队列中:

  • 规则5:经过一段时间$S$后,把系统中的所有任务移动到最高优先级队列中。

这条新的规则解决了两个问题:首先,低优先级的程序不会被高优先级的阻塞掉;其次,能够处理程序行为的变化。

John Ousterhout, a well-regarded systems researcher, used to call such values in systems voo-doo constants, because they seemed to require some form of black magic to set them correctly.

如何决定$S$的值呢?如果$S$太高,低优先级程序可能很长时间都无法运行;如果太小,交互型程序可能无法获得足够的运行时间。

8.4 Attempt #3: Better Accounting

如何阻止用户恶意利用调度规则?解决方案是让调度算法对CPU使用时间做出更好的统计。

  • 规则4:一旦程序用完了对应优先级允许的运行时间(无论放弃了多少次CPU),都把它移动到次优先级。

书本8.5节是MLFQ调整参数的讨论和各种实现的介绍,不抄了。

第9章介绍了一种公平的调度算法:彩票(?)调度法(lottery scheduling)。Fair-share的调度算法不考虑完成或者响应时间,而是保证每个任务都获得一定的CPU使用时间比例。

9.1 Basic Concept: Tickets Represent Your Share

彩票调度算法的核心概念是:(彩)票(tickets)。彩票用来表示进程拥有资源的权重(share of resource)。进程拥有的彩票的比例代表它对系统资源占有的比例。

TIP: Use Randomness

One of the most beautiful aspects of lottery scheduling is its use of randomness. When you have to make a decision, using such a randomized approach is often a robust and simple way of doing so.

Random approaches has at least three advantages over more traditional decisions. First, random often avoids strange corner-case behaviors that a more traditional algorithm may have trouble handling. For example, consider the LRU replacement policy (studied in more detail in a future chapter on virtual memory); while often a good replacement algorithm, LRU attains worst-case performance for some cyclic-sequential workloads. Random, on the other hand, has no such worst case.

Second, random also is lightweight, requiring little state to track alternatives. In a traditional fair-share scheduling algorithm, tracking how much CPU each process has received requires per-process accounting, which must be updated after running each process. Doing so randomly necessitates only the most minimal of per-process state (e.g., the number of tickets each has). Finally, random can be quite fast.

As long as generating a random number is quick, making the decision is also, and thus random can be used in a number of places where speed is required. Of course, the faster the need, the more random tends towards pseudo-random.

调度者必须知道总共有多少张彩票(比如说100张),然后选一张中奖的彩票(0-99号),假设A拥有0-74、B拥有75-99号彩票,那么这张中奖彩票就决定谁的程序可以运行。

彩票中奖的随机性保证了概率上资源共享比例的正确性。系统处理任务的时间越长,资源共享的比例越接近理论值。

9.2 Ticket Mechanisms

彩票调度的方法也提供了控制彩票的几种有效方式。其中一种使用了彩票货币(ticket currency)的概念:拥有很多彩票的用户把彩票分配给自己的进程;然后系统把这些彩票转换成一个全局值。

例如,用户A有1000张彩票,均分给A1、A2两个进程,用户B只有10张彩票,全部分给B1。操作系统进行货币转换后,A1、A2各有50张全局彩票,B1有100全局彩票(OS总共有200张)。

另一个有效的机制是彩票交♂易(ticket transfer),允许进程之间相互交换彩票。这种能力在client-server关系中非常有用,客户端想要干活,就让服务端给他点彩票增加占有CPU的概率,干完活之后把彩票还回去。

最后,另一种有效的机制是通货膨胀(ticket inflation)。一个进程可以暂时的增加或者减少他所拥有的彩票数,而不告诉其他的进程,但这种手段仅在相互信任的程序之间可以使用

9.3 Implementation

实现一个彩票抽奖调度系统最重要的就是用一个好的随机数发生器来抽取中奖的彩票,一个数据结构来记录系统中的进程(比如链表)以及所有彩票的总数。

例如,在链表实现中,抽取一张彩票号码,按链表顺序彩票为$0, 1, \dots, N$号,已经知道每个节点拥有的彩票数,直接遍历找到对应的节点即可。为了使得这个过程更加高效,可以对进程链表排序,拥有彩票多的靠前。

书本9.4说明当运行时间长后,彩票足够公平; 9.5提出了如何分发彩票的疑问,不抄了。

9.6 Why Not Deterministic?

在短时间内,利用随机的彩票方法无法达到公平,所以有另外一种决定性的公平方法:步长调度(stride scheduling)。

每个进程拥有一个步长(stride),和它持有的彩票数成反比。每次一个进程运行,给属于它的计时器(叫做进程的pass value)加上步长值来记录运行的全局进度。

调度算法利用步长和pass决定下一次运行谁。基本的想法是:在某一个时间,选择拥有最低的pass值的进程运行,运行时增加它的pass。

curr = remove_min(queue);   // pick process with min pass
schedule(curr);             // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr);        // return curr to queue

为什么有了步长,还要用随机的彩票方法呢?彩票方法可以处理一个特别的问题:步长调度中,当一个新进程进入的时候,pass的初始值决定了它是否能够霸占CPU;而在彩票方法中,添加一个新进程并不会影响其他进程的执行。彩票方法更容易处理新的进程。

9.7 The Linux Completely Fair Scheduler (CFS)

CFS实现了公平调度,并且效率高,可扩展性强。然而这玩意太高级了还用到了红黑树让我当场去世,请点击Wikipedia来学习。

最后,第10章介绍了高级多处理器调度算法(Advanced Topic)我*,CFS都不算高级课题的吗,第11章是无聊聊天内容,所以不抄了有兴趣自己看去吧!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

评论