5.3 Scheduling algorithms

CPU scheduling algorithm selects one process from the ready queue and assigns it the CPU. The following subsections describe several CPU scheduling.

First-Come, First-Served scheduling
The first-come, first-served (FCFS) scheduling algorithm is the simplest scheduling techniques.
The average waiting time can vary substantially if the process CPU-burst times vary greatly. The FCFS scheduling algorithm is nonpreemptive and is not suitable for time-sharing systems.

Shortest-Job-First Scheduling
The shortest-job-first (SJF) scheduling algorithm assigns CPU to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is applied. The SJF scheduling algorithm gives the minimum average waiting time for a given set of processes. The SJF algorithm can be preemptive or nonpreemptive. A preemptive SJF algorithm (it is called the shortest remaining time (SRT)) preempts the currently executing process. A nonpreemptive SJF algorithm allows the currently running process to finish its CPU burst.

Priority scheduling
In priority scheduling algorithm, each process has a priority. CPU is assigned to the process that has the highest priority. FCFS scheduling algorithm is applied when two processes has the same priority. The low priority number represents high priority.

5.3 Scheduling algorithms

Indefinite blocking (which is called starvation) is a major problem in priority scheduling algorithms. Low-priority processes can wait indefinitely. Aging is the solution for the starvation problem which gradually increasing the priority of processes that wait in the system for a long time.

Round-Robin scheduling
The round-robin (RR) scheduling algorithm is a preemptive algorithm designed especially for time-sharing systems. Each process can be assigned to CPU for a small unit of time, called a time quantum or time slice. To implement RR scheduling, the ready queue is used as a FIFO queue of processes. When a process arrives, it is placed in the end of the ready queue. The process in the head of the ready queue is assigned to CPU. If the process terminates within the time slice, it releases CPU. Otherwise, the process is forced to release CPU and is placed in the end of the ready queue. When the time quantum is very large, RR algorithm will work as if it is FCFS algorithm.

Multilevel queue scheduling
In multilevel queue scheduling, processes are classified into different groups according to their response-time requirements. In this scheduling technique, there are different ready queues. Each queue is assigned a different scheduling technique. Each queue has a higher priority over the lower queues.

5.3 Scheduling algorithms

Multilevel feedback-queue scheduling
In multilevel feedback-queue scheduling, there are multiple queues. Each queue has a quantum time higher than the above queues. When a process arrives, it enters the higher queue. If the process cannot terminate when it is assigned to CPU, it enters the lower queue. This scheduling forms aging which prevents starvation. Multilevel feedback-queue scheduling is considered the most general CPU-scheduling algorithm.