The need for scheduling processes can be traced back to the first time-sharing systems, where multiple users would generally be waiting for service from a central system. On such a system, CPU time was a scarce resource, and scheduling algorithms were necessary to provide a responsive system to the multiple users.

Almost all modern operating systems are capable of multi-tasking. If you've ever checked your e-mail while typing a word document, or listened to music (via your PC) while surfing the world-wide web, you've undoubtedly experienced the multi-tasking features of your operating system.

While it may appear that the computer was performing all these tasks all at once, the reality is that each CPU core is only capable of processing one task at any given time. The operating system has to handle the multitude of processes that are competing for CPU time. It is the operating system's job to schedule and prioritise tasks, switching the CPU among processes, in order to make the computer more productive. Thus the development of good scheduling algorithms is imperative in the efficient use of resources to optimize the performance of a system.

The essential idea behind operating system scheduling is simple: Maximise CPU utilisation. The CPU will run a process until the process has to wait (for whatever reason), after which the CPU would become idle. To fully utilise the CPU, the operating system would give the CPU to another process that is ready to run (runnable). This pattern continues, allowing the CPU to be efficiently shared between processes.

Processes can be in three states, switching between which is CPU intensive. These states are as follows:

• Running - process is running on CPU.
• Ready - ready to run, but not actually running on the CPU.
• Waiting - waiting for some event like IO to happen.

Scheduling decisions, that decide which process to run next, can occur in the following circumstances:

1. When a current process switches from running to waiting. This can occur in cases when an I/O request is issued, or because the process is waiting for a child to terminate.
2. When a process switches from running to ready – for example, upon completion of the interrupt handler, like the timer interrupt in interactive systems. If the scheduler switches processes in this case, it has preempted the running process. Another common interrupt handler is the I/O completed handler.
3. When a process switches from waiting to ready state (on completion of I/O for example).
4. When a process terminates.

Process scheduling needs to be efficient not only in the selection of the next process to run, but also in the number of switches made per unit time. Each switch is resource intensive and involves multiple steps, consuming already-scarce CPU time. As such, overzealous switching is counterproductive.

show more »

CPU and I/O Burst Cycle
Processes typically go through two stages: A cycle of CPU execution, called a CPU burst, followed by a wait on I/O to complete, also called I/O burst (or I/O wait). Processes alternate between these two states.



Process execution always begins with a CPU burst. Normally, after awhile, the process would want to input or output data through a read or write. During this time, process execution suspends until this I/O burst is complete.The cycle continues until eventually, the CPU burst ends when the process completes. In an I/O bound program, it has been observed that the program would typically have many short CPU bursts. A CPU-bound program, on the other hand, might have a few long CPU bursts. This observation helps a developer to select an appropriate CPU-scheduling algorithm.


CPU Scheduler
Whenever a process completes (or suspends) and the CPU becomes idle, the operating system must select another process that is in the read queue for execution. This selection process is performed by the CPU scheduler (or short-term scheduler). It would be good to note that the ready queue is not necessarily a first-in, first-out (FIFO) queue. Such queues can be implemented in many ways, such as a FIFO queue, priority queue, a tree, a circular list, etc.


Preemptive Scheduling
In preemptive scheduling, the scheduler actively suspends currently running processes and gives the CPU to another process. This ensures fairness in some ways, but introduces a problem of synchronization of data among processes.