Scheduling

Scheduling is the art of planning activities to achieve a goal within limited time and resources. It shows up anywhere multiple tasks compete for the same limited capacity — from coordinating a large space mission to preparing a multi-course dinner — and in computing, it governs how a processor (the machine or person carrying out tasks) decides which of several waiting tasks to work on next.

A scheduling algorithm is the set of rules used to assign tasks to processors, and a priority list is the order in which tasks are lined up to be completed. Scheduling algorithms fall into two broad categories: pre-emptive priority scheduling, where a newly arrived task with higher priority than the one currently running immediately takes over the processor (pausing the current task); and non-pre-emptive priority scheduling, where a newly arrived task must wait in the queue, however high its priority, until the currently running task finishes.

Several time measures are used to evaluate how well a schedule performs. Burst time is how long a task needs on the processor, and completion time is when it finishes; from these:

Idle time is time during which the processor has nothing to work on, and response time is when a task first gets the processor (for non-pre-emptive scheduling, this is the same as its waiting time). Across a whole schedule, the average waiting time (AWT) — the mean of every task's waiting time — is the key measure of quality: the lower the AWT, the better the algorithm. An optimal schedule is one that achieves the shortest possible overall finishing time, and a Gantt chart (named after its inventor, Henry Gantt) is the bar chart conventionally used to display a schedule visually. …