Multilevel feedback queue

Last updated

In computer science, a multilevel feedback queue is a scheduling algorithm. Scheduling algorithms are designed to have some process running at all times to keep the central processing unit (CPU) busy. [1] The multilevel feedback queue extends standard algorithms with the following design requirements:

Contents

  1. Separate processes into multiple ready queues based on their need for the processor.
  2. Give preference to processes with short CPU bursts.
  3. Give preference to processes with high I/O bursts. (I/O bound processes will sleep in the wait queue to give other processes CPU time.)

The multilevel feedback queue was first developed by Fernando J. Corbató (1962). [2] For this accomplishment, the Association for Computing Machinery awarded Corbató the Turing Award. [3]

Process scheduling

Whereas the multilevel queue algorithm keeps processes permanently assigned to their initial queue assignments, the multilevel feedback queue shifts processes between queues. [4] The shift is dependent upon the CPU bursts of prior time-slices. [5]

Algorithm

Multiple FIFO queues are used and the operation is as follows:

  1. A new process is inserted at the end (tail) of the top-level FIFO queue.
  2. At some stage the process reaches the head of the queue and is assigned the CPU.
  3. If the process is completed within the time slice of the given queue, it leaves the system.
  4. If the process voluntarily relinquishes control of the CPU, it leaves the queuing network, and when the process becomes ready again it is inserted at the tail of the same queue which it relinquished earlier.
  5. If the process uses all the quantum time, it is pre-empted and inserted at the end of the next lower-level queue. This next lower-level queue will have a time quantum that is more than that of the previous higher-level queue.
  6. This scheme will continue until the process completes or it reaches the base-level queue.
  • At the base level queue the processes circulate in round robin fashion until they complete and leave the system. Processes in the base level queue can also be scheduled on a first come first served basis. [6]
  • Optionally, if a process blocks for I/O, it is promoted one level, and placed at the end of the next-higher queue. This allows I/O bound processes to be favored by the scheduler and allows processes to escape the base-level queue.

For scheduling, the scheduler always starts picking up processes from the head of the highest-level queue. Only if the highest-level queue has become empty will the scheduler take up a process from the next lower-level queue. The same policy is implemented for picking up in the subsequent lower-level queues. Meanwhile, if a process comes into any of the higher-level queues, it will preempt a process in the lower-level queue.

Also, a new process is always inserted at the tail of the top-level queue with the assumption that it will complete in a short amount of time. Long processes will automatically sink to lower-level queues based on their time consumption and interactivity level. In the multilevel feedback queue a process is given just one chance to complete at a given queue level before it is forced down to a lower-level queue.

Scheduling parameters

In general, a multilevel feedback queue scheduler is defined by the following parameters: [6]

See also

Related Research Articles

<span class="mw-page-title-main">FIFO (computing and electronics)</span> Scheduling algorithm, the first piece of data inserted into a queue is processed first

In computing and in systems theory, first in, first out, acronymized as FIFO, is a method for organizing the manipulation of a data structure where the oldest (first) entry, or "head" of the queue, is processed first.

<span class="mw-page-title-main">Operating system</span> Software that manages computer hardware resources

An operating system (OS) is system software that manages computer hardware and software resources, and provides common services for computer programs.

In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.

A real-time operating system (RTOS) is an operating system (OS) for real-time computing applications that processes data and events that have critically defined time constraints. A RTOS is distinct from a time-sharing operating system, such as Unix, which manages the sharing of system resources with a scheduler, data buffers, or fixed task prioritization in a multitasking or multiprogramming environment. Processing time requirements need to be fully understood and bound rather than just kept as a minimum. All processing must occur within the defined constraints. Real-time operating systems are event-driven and preemptive, meaning the OS can monitor the relevant priority of competing tasks, and make changes to the task priority. Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts.

<span class="mw-page-title-main">Process (computing)</span> Particular execution of a computer program

In computing, a process is the instance of a computer program that is being executed by one or many threads. There are many different process models, some of which are light weight, but almost all processes are rooted in an operating system (OS) process which comprises the program code, assigned system resources, physical and logical access permissions, and data structures to initiate, control and coordinate execution activity. Depending on the OS, a process may be made up of multiple threads of execution that execute instructions concurrently.

In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows.

<span class="mw-page-title-main">Round-robin scheduling</span> Algorithm employed by process and network schedulers in computing

Round-robin (RR) is one of the algorithms employed by process and network schedulers in computing. As the term is generally used, time slices are assigned to each process in equal portions and in circular order, handling all processes without priority. Round-robin scheduling is simple, easy to implement, and starvation-free. Round-robin scheduling can be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an operating system concept.

In modern computers many processes run at once. Active processes are placed in an array called a run queue, or runqueue. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next. To ensure each program has a fair share of resources, each one is run for some time period (quantum) before it is paused and placed back into the run queue. When a program is stopped to let another run, the program with the highest priority in the run queue is then allowed to execute.

In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory and a free page cannot be used to satisfy the allocation, either because there are none, or because the number of free pages is lower than some threshold.

nice is a program found on Unix and Unix-like operating systems such as Linux. It directly maps to a kernel call of the same name. nice is used to invoke a utility or shell script with a particular CPU priority, thus giving the process more or less CPU time than other processes. A niceness of -20 is the lowest niceness, or highest priority. The default niceness for processes is inherited from its parent process and is usually 0.

The THE multiprogramming system or THE OS was a computer operating system designed by a team led by Edsger W. Dijkstra, described in monographs in 1965-66 and published in 1968. Dijkstra never named the system; "THE" is simply the abbreviation of "Technische Hogeschool Eindhoven", then the name of the Eindhoven University of Technology of the Netherlands. The THE system was primarily a batch system that supported multitasking; it was not designed as a multi-user operating system. It was much like the SDS 940, but "the set of processes in the THE system was static".

In computer science, an input queue is a collection of processes in storage that are waiting to be brought into memory to run a program. Input queues are mainly used in Operating System Scheduling which is a technique for distributing resources among processes. Input queues not only apply to operating systems (OS), but may also be applied to scheduling inside networking devices. The purpose of scheduling is to ensure resources are being distributed fairly and effectively; therefore, it improves the performance of the system.

<span class="mw-page-title-main">Shortest job next</span> Scheduling policy

Shortest job next (SJN), also known as shortest job first (SJF) or shortest process next (SPN), is a scheduling policy that selects for execution the waiting process with the smallest execution time. SJN is a non-preemptive algorithm. Shortest remaining time is a preemptive variant of SJN.

Lottery scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process. The distribution of tickets need not be uniform; granting a process more tickets provides it a relative higher chance of selection. This technique can be used to approximate other scheduling algorithms, such as Shortest job next and Fair-share scheduling.

Multi-level queueing, used at least since the late 1950s/early 1960s, is a queue with a predefined number of levels. Items get assigned to a particular level at insert, and thus cannot be moved to another level. Items get removed from the queue by removing all items from a level, and then moving to the next. If an item is added to a level above, the "fetching" restarts from there. Each level of the queue is free to use its own scheduling, thus adding greater flexibility than merely having multiple levels in a queue.

<span class="mw-page-title-main">I/O scheduling</span> Arbiter for mass storage access in an operating system

Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order I/O operations will be submitted to storage volumes. I/O scheduling is sometimes called disk scheduling.

<span class="mw-page-title-main">Completely Fair Scheduler</span> Linux process scheduler

The Completely Fair Scheduler (CFS) is a process scheduler that was merged into the 2.6.23 release of the Linux kernel and is the default scheduler of the tasks of the SCHED_NORMAL class. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.

In computer science for Operating systems, aging or ageing is a scheduling technique used to avoid starvation. Fixed priority scheduling is a scheduling discipline, in which tasks queued for utilizing a system resource are assigned a priority each. A task with a high priority is allowed to access a specific system resource before a task with a lower priority is allowed to do the same. A disadvantage of this approach is that tasks assigned with a lower priority may be starved when a large number of high priority tasks are queued. Aging is used to gradually increase the priority of a task, based on its waiting time in the ready queue.

<span class="mw-page-title-main">Brain Fuck Scheduler</span> Process scheduler in Linux

The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 based on earliest eligible virtual deadline first scheduling (EEVDF), as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by an experienced kernel programmer Con Kolivas.

Processor sharing or egalitarian processor sharing is a service policy where the customers, clients or jobs are all served simultaneously, each receiving an equal fraction of the service capacity available. In such a system all jobs start service immediately.

References

  1. ↑ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 131. ISBN   978-0-201-50480-4.
  2. ↑ Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962). "An experimental time-sharing system". Proceedings of the May 1-3, 1962, spring joint computer conference on - AIEE-IRE '62 (Spring). p. 335. doi:10.1145/1460833.1460871. S2CID   14363753.
  3. ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Multi-level Feedback Queue". Operating Systems: Three Easy Pieces (PDF). Arpaci-Dusseau Books.
  4. ↑ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 147. ISBN   978-0-201-50480-4.
  5. ↑ Silberschatz, Abraham (1994). Operating System Concepts, Fourth Edition. Addison-Wesley. p. 148. ISBN   978-0-201-50480-4.
  6. 1 2 Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Operating system concepts (8th ed.). Hoboken, N.J.: Wiley. p. 198. ISBN   978-0470128725.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.