Scheduling algorithm

In computer science, a scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or achieve a target quality of service. The need for a scheduling algorithm arises from the requirement for most modern systems to perform multitasking (execute more than one process at a time) and multiplexing (transmit multiple flows simultaneously).

In computing and multitasking

The algorithm used may be as simple as round-robin in which each process is given equal time (for instance 1 ms, usually between 1 ms and 100 ms) in a cycling list. So, process A executes for 1 ms, then process B, then process C, then back to process A.

More advanced algorithms take into account process priority, or the importance of the process. This allows some processes to use more time than other processes. It should be noted that the kernel always uses whatever resources it needs to ensure proper functioning of the system, and so can be said to have infinite priority. In SMP(symmetric multiprocessing) systems, processor affinity is considered to increase overall system performance, even if it may cause a process itself to run more slowly. This generally improves performance by reducing cache thrashing.

In computer networks and multiplexing

In packet-switched computer networks and other statistical multiplexing, the notion of a scheduling algorithm is used as an alternative to first-come first-served queuing of data packets. In advanced packet radio wireless networks such as HSDPA (High-Speed Downlink Packet Access ) 3.5G cellular system, channel-dependent scheduling may be used to take advantage of favourable channel conditions to increase the throughput and system spectral efficiency. The simplest best-effort scheduling algorithms are round-robin, fair queuing (a max-min fair scheduling algorithm), proportionally fair scheduling and maximum throughput. If differentiated or guaranteed quality of service is offered, as opposed to best-effort communication, weighted fair queuing may be utilized.

In computer I/O

Determines the order in which disk I/O requests are pushed to the disk device.

See also

• Scheduling (computing)
• Job Shop Scheduling
• Scheduling (communications)
• I/O scheduling
• Atropos scheduler
• Dynamic priority scheduling
• Multilevel feedback queue
• Round-robin scheduling
• Completely Fair Scheduler
• Least slack time scheduling
• O(1) scheduler

External links

• Josh Aas' introduction to the Linux 2.6.8.1 CPU scheduler implementation
• Peter Brucker, Sigrid Knust. Complexity results for scheduling problems [1]
• TORSCHE Scheduling Toolbox for Matlab is a toolbox of scheduling and graph algorithms.