• CPU scheduling is the basis of multi-programming operating system.
  • By switching the CPU among the processes the operating system can make the use of computer effectively.
  • The objective of multi programming is to maximize CPU utilization so processor would have a process running all the time.
  • In a single tasking system, only one process may run at a time, and other processes must wait until CPU is free.
  • Several processes are kept in memory at one time, when one process has to wait, operating system takes the CPU away from the process and gives the CPU to another process. This pattern continues.
  • Scheduling is a fundamental operating system function. All computer resources are scheduled before use.
  • Since the CPU is one of the primary computer resources, its scheduling is central to operating system design.

CPU I/O Burst Design

  • The success of CPU scheduling depends on the property, CPU input/output burst cycle of processor. Process execution consists of a cycle of CPU execution and input/output waits.
  • Processes switches between these two states. Process execution begins with CPU execution followed by an input/output burst and another CPU burst and another input/output burst and so on.
  • All processes terminate with CPU burst cycle. Last CPU burst will end with a system request to terminate execution rather than with another input/output burst.
  • The duration of the CPU burst have been extensively measured. The CPU burst cycle varies by process and computer. They tend to have frequency curve similar to the following diagram.
CPU/IO Busrt Cycle

Burst Time (miliseconds)

  • The curve is generally characterized as exponential or in hyper exponential form. It may have short CPU burst and long CPU burst. An input/output bound program for process, typically have many short CPU burst. A CPU bound program or process might have few very long CPU burst.

CPU Scheduler

  • The operating system has to select one of the processes in the ready queue to be executed whenever CPU becomes idle. The selection process is performed  by the short term scheduler.
  • The schedulers select among the processes in memory that are ready to execute and allocates the CPU to one of them. A ready queue may be implemented as a FIFO queue, priority queue, tree or simply unordered link list. All the processes in the ready queue are lined up waiting for chance to run on the CPU. The records in the queues are generally PCB of the processes.