`
haoningabc
  • 浏览: 1483064 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

反转楼梯最后期限调度算法

阅读更多
http://lwn.net/Articles/224865/


CPU scheduling seems to be one of those eternally unfinished jobs. Developers can work on the CPU scheduler for a while and make it work better, but there will always be workloads which are not served as well as users would like. Users of interactive systems, in particular, tend to be sensitive to scheduler latencies. In response, the current scheduler has grown an elaborate array of heuristics which attempt to detect which processes are truly interactive and give them priority in the CPU. The result is complicated code - and people still complain about interactive response.
Enter Con Kolivas, who has been working on improving interactivity for some time. His latest proposal is the Rotating Staircase Deadline Scheduler (RSDL), which attempts to provide good interactive response with a relatively simple design, complete fairness, and bounded latency. This work takes ideas from Con's earlier staircase scheduler (covered here in June, 2004), but with a significantly different approach.

Like many schedulers, the RSDL maintains a priority array, as is crudely diagrammed to the left. At each level there is a list of processes currently wanting to run at that priority; each process has a quota of time it is allowed to execute at that priority. The processes at the highest priority are given time slices, and the scheduler rotates through them using a typical round-robin algorithm.

When a process uses its quota at a given priority level, it is dropped down to the next priority and given a new quota. That process can thus continue to run, but only after the higher-priority processes have had their turn. As processes move down the staircase, they increasingly must contend with the lower-priority processes which have been patiently waiting on the lower levels. The end result is that even the lowest-priority processes get at least a little CPU time eventually.

An interesting feature of this scheduler is that each priority level has a quota of its own. Once the highest priority level has used its quota, all processes running at that level are pushed down to the next-lower level, regardless of whether they have consumed their individual CPU time quotas or not. As a result of this "minor rotation" mechanism, processes waiting at lower priority levels need only cool their heels for a bounded period of time before all other processes are running at their level. The maximum latency for any process waiting to run is thus bounded, and can be calculated; there is no starvation with this scheduler.

As processes use up their time, they are moved to a second array, called the "expired" array; there they are placed back at their original priority. Processes in the expired array do not run; they are left out in the cold until no more processes remain in the currently active array - or until all processes are pushed off the bottom of the active array as a result of minor rotations. At that point, a "major rotation" happens: the active and expired arrays are switched and the whole series of events restarts from the beginning.

The current scheduler tries to locate interactive tasks by tracking how often each process sleeps; those seen to be interactive are then rewarded with a priority boost. The RSDL does away with all that. Instead, processes which sleep simply do not use all of their time at the higher priority levels. When they run, they are naturally advantaged over their CPU-hungry competition. If a process sleeps through a major rotation, its quota goes back into the run queue's priority-specific quota value. Thus, it will be able to run at high priority even if other high-priority processes, which have been running during this time, have been pushed to lower priorities through minor rotations. All of this should add up to quick response from interactive applications.

A few benchmarks posted by Con show that systems running with RSDL perform slightly better than with the stock 2.6.20 scheduler. The initial reports from testers have been positive, with one person urging that RSDL go into 2.6.21. That will not happen at this point in the release cycle, but Linus is favorable to including RSDL in a future kernel:

I agree, partly because it's obviously been getting rave reviews so far, but mainly because it looks like you can think about behaviour a lot better, something that was always very hard with the interactivity boosters with process state history.
Con has recently been heard to complain about difficulties getting his interactivity improvements into the mainline. This time around, however, he may find the course of events to be rather more gratifying.
分享到:
评论

相关推荐

    模拟进程优先级调度算法

    根据给定的信息,我们可以深入探讨进程优先级调度算法的相关知识点。 ### 进程优先级调度算法概述 在操作系统中,进程调度是一项核心功能,它决定了系统如何分配处理器资源给各个进程。优先级调度算法是一种常用的...

    选择一个调度算法,实现处理器调度

    在众多的调度算法中,优先数调度算法和时间片轮转法是两种常见且广泛应用于实际系统中的方法。本文将围绕这两种算法的实现原理和程序设计进行深入探讨。 首先,让我们来认识优先数调度算法。优先数调度算法的核心...

    CPU 调度算法实现

    本主题将深入探讨CPU调度算法的实现,特别是时间片调度算法和优先级调度算法。 时间片调度算法,也称为轮转调度,是将所有就绪进程按一定顺序放入一个队列中,然后为每个进程分配一个固定的时间片(如10毫秒或100...

    编写程序实现基于优先级的时间片轮转调度算法

    6. **优先级反转和死锁预防**:在优先级调度中,需要考虑优先级反转(低优先级进程持有高优先级进程所需的资源)和死锁(多个进程互相等待对方释放资源)的问题。可以通过优先级继承或资源预分配等策略来解决。 在...

    轮转调度算法和优先调度算法的C++实现.rar

    操作系统中的调度算法是管理CPU执行任务的关键部分,它决定了如何有效地分配处理器资源。本文将详细介绍两种常见的调度算法——轮转调度(Round Robin Scheduling, RR)和优先级调度(Priority Scheduling),并结合...

    操作系统实验:最高优先级/优先级调度算法+先来先服务算法 ;最先适应算法+最佳适应算法+最坏适应算法 ;安全性算法+银行家算法

    最后,我们关注“安全性算法”和“银行家算法”,它们是用于内存管理的重要策略。安全性算法检查系统当前状态是否有可能在不引起死锁的情况下满足所有进程的资源需求。如果可以,系统是安全的;否则,需要采取预防...

    驱动调度电梯算法

    驱动调度电梯算法是一种在操作系统中用于管理磁盘I/O操作的策略,它的主要目标是高效地安排磁盘读写请求,以最小化磁头移动时间,从而提高整体系统性能。在给定的描述中,提到的"pcbIO"可能是"进程控制块IO"的简称,...

    作业调度算法.rar

    在操作系统中,作业调度算法作为资源分配和管理的核心部分,对于系统的性能和任务执行效率具有决定性的影响。操作系统需要公平且高效地分配处理器时间,确保各作业按照一定的顺序和优先级完成。在对作业调度算法的...

    多级反馈队列调度算法

    多级反馈队列调度算法(Multilevel Feedback Queue Scheduling,MLFQ)是一种在操作系统中用于进程调度的策略,其目标是优化系统的整体性能,兼顾各种类型的任务,确保响应时间和吞吐量的平衡。该算法的核心思想是将...

    c语言实现磁盘调度算法

    根据给定的信息,本文将详细解释如何在C语言中实现三种磁盘调度算法:先来先服务(FCFS)、最短寻道优先(SSTF)以及电梯算法(SCAN)。这些算法是操作系统中的核心概念之一,用于管理磁盘读写请求的处理顺序,从而...

    CPU调度算法(操作系统实验)

    最后,为了评估算法性能,可以记录并分析各种性能指标,如平均等待时间、周转时间、带权周转时间和系统吞吐量。 通过这个实验,你可以深入理解各种CPU调度算法的原理,了解它们对系统性能的影响,并且提升C++编程...

    模拟的进程调度程序,采用“最高优先数优先”调度算法

    在分析和实现过程中,我们还可以考虑其他因素,例如抢占(即正在运行的低优先级进程被更高优先级进程中断)和优先级反转(可能导致优先级高的进程被优先级低的进程阻塞),这些复杂的调度问题在实际操作系统中是常见...

    计算机操作系统中电梯调度算法

    根据提供的信息,我们可以深入探讨计算机操作系统中的电梯调度算法这一主题。该题目主要涉及的是操作系统中的磁盘调度算法,其中电梯算法是最为常见的方法之一。在理解这部分内容时,我们需要掌握以下几个核心概念:...

    操作系统实验报告(调度算法)

    调度算法在操作系统中扮演着至关重要的角色,它决定了进程如何在处理器上执行,从而影响到系统的性能、响应时间和吞吐量。本实验报告将深入探讨调度算法的原理与实践。 一、调度算法概述 调度算法的主要任务是决定...

    RR_HPF.rar_HPF_HPF调度_基于优先级_时间片轮转算法_调度算法

    尽管基于优先级的调度算法能够提供更好的响应时间和适应性,但它也可能引发优先级反转和饥饿问题。优先级反转是指低优先级进程持有资源,导致高优先级进程等待,这可能会降低系统效率。饥饿则是指某些进程由于较低的...

    按优先数调度算法实现处理器调度

    8. **调度开销**:调度过程本身也需要占用处理器时间,因此设计算法时需要平衡调度效率和调度开销。优化算法以减少不必要的上下文切换,有助于提高系统性能。 总之,按优先数调度算法是实现处理器调度的一种有效...

    main_进程调度_操作系统优先级进程调度算法_

    本文将深入探讨“非抢占式优先级进程调度算法”,并结合`main.c`源代码进行详细阐述。 首先,我们要理解什么是进程调度。在多任务环境下,操作系统必须管理多个并发运行的进程,确保每个进程都能公平地获取计算资源...

    进程调度模拟实验 先来先服务调度算法等

    在这个“进程调度模拟实验”中,我们将深入探讨三种基本的调度算法:先来先服务(FCFS)、基于高优先级的调度以及短作业优先(SJF)调度算法。 **一、先来先服务调度算法(FCFS)** FCFS调度算法是最简单的调度策略...

    进程调度算法模拟程序设计

    优先级调度需要注意防止低优先级进程永远等待(优先级反转)和高优先级进程长时间占用CPU(优先级继承)的问题。 6. **多级反馈队列(MLFQ,Multi-Level Feedback Queue)**:结合了多种调度策略,设置多个队列,每...

    进程调度算法的模拟实现

    本主题将深入探讨五种常见的进程调度算法:优先级调度、最短进程算法(Shortest Process Next, SPN)、最短剩余时间算法(Shortest Remaining Time First, SRTF)、先来先服务(First-Come, First-Served, FCFS)...

Global site tag (gtag.js) - Google Analytics