CPU SCHEDULING ALGORITHMS

First-Come, First Come, First-Served (FCFS) Scheduling

This non-preemptive scheduling algorithm follows the first-in, first-out (FIFO) policy. As each process becomes ready, it joins the ready queue. When the current running process finishes execution, the oldest process in the ready queue is selected to run next.

Shortest-Job Job-First (SJF) Scheduling

Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time

Two schemes:

􀁺 nonpreemptive –once CPU given to the process it cannot be preempted until completes its CPU burst

􀁺 preemptive –if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as theShortest-Remaining-Time-First (SRTF)

SJF is optimal –gives minimum average waiting time for a given set of processes

Round Robin (RR)

􀂄 Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

􀂄 RR is designed specially for time-sharing systems.

􀂄 A small unit of time, called a time quantum or time slice, is defined.

􀂄 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.

􀂄 If there are nprocesses in the ready queue and the time quantum is q, then each process gets 1/nof the CPU time in chunks of at most qtime units at once. No process waits more than (n-1)q time units.

􀂄 Performance

􀁺 qlarge

⇒ FIFO

􀁺 q small

⇒ q must be large with respect to context switch, otherwise overhead is too high

Shortest Remaining Time (SRT)

This preemptive scheduling algorithm favors processes with the shortest remaining expected process time. As each process becomes ready, it joins the ready queue. This triggers an interrupt which preempts the current running process back into the ready queue. The process in the ready queue with the shortest remaining service time is selected to run next.