Scheduling (computing)

From Wikipedia, the free encyclopedia

Some of the information in this article or section may not be verified by reliable sources. It should be checked for inaccuracies and modified to cite reliable sources.

Scheduling is a key concept in computer multitasking and multiprocessing operating system design, and in real-time operating system design. It refers to the way processes are assigned priorities in a priority queue. This assignment is carried out by software known as a scheduler.

In general-purpose operating systems, the goal of the scheduler is to balance processor loads, and prevent any one process from either monopolizing the processor or being starved for resources. In operating systems designed from the ground up for critical application use, such as Solaris, AIX or z/OS, schedulers include "defensive" features. If a process (by design or accident) should attempt to aggressively grab all available processor resources, the system often reacts by slowing down to the point of being perceived as "locked". However there are third-party applications for Windows that add these protective measures, for example AppSense Performance Manager, Aurema ARMTech and Citrix Presentation Server 4.0 Enterprise. The latter uses a stripped down variant of Aurema ARMTech version 2.

In real-time environments, such as devices for automatic control in industry (for example robotics), the scheduler also must ensure that processes can meet deadlines; this is crucial for keeping the system stable.

Contents

[edit] Types of operating system schedulers

Operating systems may feature up to 3 distinct types of schedulers: a long-term scheduler (also known as an admission scheduler), a mid-term or medium-term scheduler and a short-term scheduler (also known as a dispatcher).

The long-term, or admission, scheduler decides which jobs or processes are to be admitted to the ready queue; that is, when an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler. Thus, this scheduler dictates what processes are to run on a system and the degree of concurrency to be supported at any one time - ie: whether a high or low amount of processes are to be executed concurrently, and how the split between IO intensive and CPU intensive processes is to be handled. Typically for a desktop computer, there is no long-term scheduler as such, and processes are admitted to the system automatically. However this type of scheduling is very important for a real time system, as the system's ability to meet process deadlines may be compromised by the slowdowns and contention resulting from the admission of more processes than the system can safely handle. [Stallings, 399]

The mid-term scheduler, present in all systems with virtual memory, temporarily removes processes from main memory and places them on secondary memory (such as a disk drive) or vice versa. This is commonly referred to as "swapping out" or "swapping in" (also incorrectly as "paging out" or "paging in"). The mid-term scheduler may decide to swap out a process which has not been active for some time, or a process which has a low priority, or a process which is page faulting frequently, or a process which is taking up a large amount of memory in order to free up main memory for other processes, swapping the process back in later when more memory is available, or when the process has been unblocked and is no longer waiting for a resource. [Stallings, 396] [Stallings, 370]

In many systems today (those that support mapping virtual address space to secondary storage other than the swap file), the mid-term scheduler may actually perform the role of the long-term scheduler, by treating binaries as "swapped out processes" upon their execution. In this way, when a segment of the binary is required it can be swapped in on demand, or "lazy loaded". [Stallings, 394]

The short-term scheduler (also known as the dispatcher) decides which of the ready, in memory processes are to be executed (allocated a CPU) next, following a clock interrupt, an IO interrupt, an operating system call or another form of signal. Thus the short-term scheduler makes scheduling decisions much more frequently than the long-term or mid-term schedulers - a scheduling decision will at a minimum have to be made after every time slice, and these are very short. This scheduler can be preemptive, implying that it is capable of forcibly removing processes from a CPU when it decides to allocate that CPU to another process, or non-preemptive, in which case the scheduler is unable to "force" processes off the CPU. [Stallings, 396].

[edit] Scheduling disciplines

Main article: Scheduling algorithm

Scheduling disciplines are algorithms used for distributing resources among parties which simultaneously and asynchronously request them. Scheduling disciplines are used in routers (to handle packet traffic) as well as in operating systems (to share CPU time among threads and processes).

The main purposes of scheduling algorithms are to minimize resource starvation and to ensure fairness amongst the parties utilizing the resources.

[edit] Common scheduling disciplines

The following is a list of common scheduling practices and disciplines:

[edit] Common disk scheduling disciplines

  • Random Scheduling (RSS)
  • First In, First Out (FIFO), also known as First Come First Served (FCFS)
  • Last In, First Out (LIFO)
  • Shortest seek first, also known as Shortest Seek / Service Time First (SSTF)
  • Elevator algorithm, also known as SCAN (including its variants, C-SCAN, LOOK, and C-LOOK)
  • N-Step-SCAN SCAN of N records at a time
  • FSCAN, N-Step-SCAN where N equals queue size at start of the SCAN cycle.
  • Highest Response Ratio Next, HRRN

[edit] Operating System scheduler implementations

Unsurprisingly, different computer operating systems implement different scheduling schemes.

Very early MS-DOS and Windows systems were non-multitasking, and as such did not feature a scheduler.

Windows 3.1-based operating systems use a simple non-preemptive scheduler which requires programmers to instruct their processes to "yield" (give up the CPU) in order for other processes to gain some CPU time. This provided primitive support for multitasking, and was not in any way an advanced scheduling system.

Windows NT 4.0-based operating systems use a simple round robin, preemptive scheduler with priorities. Priorities in Windows NT 4.0 based systems range from 1 through to 31, with priorities 1 through 15 being "normal" priorities and priorities 16 through 31 being "real time" priorities, requiring administrator privileges to assign (although "real time" is a misnomer given that no Windows scheduler has support for real-time scheduling, as is the case with most desktop operating systems). Users can select 5 of these priorities to assign to a running application from the system manager, accessed through the alt control delete key combination. When choosing a process to dispatch (allocate a CPU to) the Windows NT 4.0 scheduler will simply select the highest priority process that is ready to run as the next process to be given CPU time, in a round robin fashion (so if there are three processes of the same priority, A, B and C, and a process of lower priority, process D, process A will be allocated the CPU, followed by process B, followed by process C - process D will be allocated the CPU if the other processes are blocking on a resource or are not waiting for the CPU for some other reason). In order to avoid starving low priority threads of CPU time, the Windows NT 4.0 scheduler will give a process that has not been executed in over 3 seconds a temporary priority "boost", elevating it to the top of the queue of processes to run and giving it a longer timeslice (quantum) than is normal, ensuring that it is allocated CPU time for the next (longer) timeslice. Information on the Windows NT scheduler

Early Unix implementations use a scheduler with Multilevel Feedback Queues with round robin selections within each Feedback Queue. In this system, processes begin in a high priority queue (giving a quick response time to new processes, such as those involved in a single mouse movement or keystroke), and as they spend more time within the system, they are preempted multiple times and placed in lower priority queues. Unfortunately under this system older processes may be starved of CPU time by a continual influx of new processes, although if a system is unable to deal with new processes faster than they arrive, starvation is inevitable anyway. Process priorities could be explicitly set under Unix to one of 40 values, although most modern Unix systems have a higher range of priorities available (Solaris has 160). Instead of the Windows NT 4.0 solution to low priority process starvation (bumping a process to the front of the round robin queue should it be starving), early Unix systems used a more subtle aging system, to slowly increase the priority of a starving process until it was executed, whereupon its priority would be reset to whatever it was before it started starving.

[edit] References

[edit] See also

[edit] Further reading

Retrieved from "http://en.wikipedia.org../../../s/c/h/Scheduling_%28computing%29.html"