In a single-processor system, only one process can run at a time; any others must wait until the CPU is free and can be rescheduled. A process is executed until completion of some I/O request. Till then CPU then just sits idle. All this time is wasted and no work is done during the waiting time. This problem is solved with multiprogramming where in several processes are kept in memory at one time. When one process has to wait, the operating system takes the CPU away from that process and gives the CPU to another process. This is called Scheduling.

CPU Scheduler

Whenever CPU is idle, the operating system must select one process from ready queue. The ready queue contains processes waiting for a chance to run on the CPU. This selection process is carried out by CPU scheduler. Let’s understand the concept of CPU scheduler.

Preemptive Scheduling

Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state. In any other case, scheduling is preemptive.

Scheduling Algorithms

There are various scheduling algorithms which defines how ready queue should be implemented. Let’s discuss some of them:

  • First-Come, First-Served Scheduling:  The simple scheduling algorithm is First-Come First-Serve (FCFS). In this algorithm, the process that requests the CPU first is allocated the CPU first. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/0 thus FCFS scheduling algorithm is non-preemptive. Disadvantage of this FCFS is that the average waiting time under the FCFS policy is often quite long.
  • Shortest Job First Scheduling: In Shortest Job First (SJF) algorithm, the process with the smallest estimated run time to completion is allocated the CPU first. This scheduling algorithm is non-preemptive. The SJF algorithm gives preference to shorter processes.
  • Priority Scheduling: In this algorithm, a priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. Priority scheduling can be either preemptive or non-preemptive. A major problem with priority scheduling algorithms is indefinite blocking, or starvation. A process that is ready to run but waiting for the CPU can be considered blocked.
  • Round-Robin Scheduling: In this algorithm, a small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum. It is designed specifically for time sharing system.
  • Multilevel Queue Scheduling
  • Multilevel Feedback-Queue Scheduling

Download as PDF

Read next:  Process Synchronization ››

« Back to Course page