CPU Scheduling in Operating Systems

In this tutorial, we will know what the goals of CPU scheduling are and also what the scheduling criteria should be. In addition, we will understand the working of some of these scheduling algorithms .

What is CPU Scheduling :

CPU scheduling or processor scheduling is the technique of deciding which process run at given time. Following are different terminology with respect to a process

Arrival Time: The time at which the process arrives in the ready queue.

Completion Time: Time at which process completes its whole execution.

Burst Time: Time required by a process for its CPU execution.

Turn Around Time: (Completion Time – Arrival Time)

Waiting Time(W.T): (Turn Around Time – Burst Time)

Goals of CPU Scheduling :

Different schedulers have different goals, however the common goals are –

A. Maximizing throughput.

B. Maximizing the number of interactive processes.

C. Minimizing resource utilization.

D. Avoiding indefinite postponement.

E. Enforcing priorities.

F. Minimizing overhead.

G. Ensuring predictability.

Types of CPU Scheduling :

  • Preemptive processes : Can be removed any time from their current processor, so it helps to improve response times. It is important for interactive environments.
  • Non-preemptive processes : Run until completion of its execution, unimportant processes can block important ones for indefinite time.

Scheduling Criteria :

  • Processor-bound processes : they basically use all available processor time.
  • I/O-bound processes : Generates an I/O request immediately and gives up the processor.
  • Batch processes : They contains works that can be performed with no user interaction.
  • Interactive processes : They requires frequent user input.

Scheduling Algorithms :

Scheduling algorithms decide when and for how long each process runs.

FIFO/FCFS scheduling : This is the simplest scheme, because processes dispatched according to their arrival time. FIFO is non-preemptible.

Round-robin scheduling : This scheduling algorithm is similar to FIFO, but processes run only for a given amount of time (time slice or quantum). Round Robin is preemptible.

Shortest-Process-First (SPF) Scheduling : Scheduler selects process with smallest burst time to finish. It has lower average wait time than FIFO, consequently it reduces the number of waiting processes. SPF Scheduling is non-preemptive.

Highest-Response-Ratio-Next (HRRN) Scheduling : This is basically, the improvised version of SPF scheduling, non-preemptive. It considers how long process has been waiting. Above all, it prevents indefinite postponement.

Shortest-Remaining-Time (SRT) Scheduling : SRT is the preemptive version of SPF. Here shorter arriving processes preempt a running process, however it is not optimal always.

Multilevel Feedback Queues : Here the arriving processes enter the highest-level queue first and execute with higher priority compared to the processes in lower queues. Then the processes with long burst time, repeatedly descend into lower levels.