Question

Of the scheduling algorithms, FCFS, SJF (non preemptive), SRTF (preemptive version of SJF), RR, and the class of Priorty algorithms, which ones cannot cause starvation? Briefly explain your answers.

Answer 1

Round robin does not cause starvation. A process in the ready list will have to wait for the only N turns of length at most q each before being allocated the CPU where N is the number of processes in the ready queue ahead of the process and q is the quantum of CPU allocated to a process when it is scheduled.

SJF and SRTF can cause starvation of some process, P, if just before the running process finishes its CPU burst, a new process always arrives with a CPU burst smaller P's burst.

Priority scheduling algorithms can also cause starvation of some process, P, if just before the running process finishes its CPU burst, a new process always arrives with a priority smaller than P's priority. However, if priorities are adjusted during execution so that any process which has not received any recent CPU usage eventually has the highest priority (this is called aging), then starvation obviously cannot occur.

FCFS does not quite guarantee that starvation cannot occur. A process that has an infinite CPU burst (e.g., that executes code with an infinite loop) will starve all remaining processes. On the other hand, if no process has an infinite CPU burst, then starvation will not occur. For, in this case, a process in the ready list will then have to wait for the only N turns, each of finite length, before being allocated the CPU where N is the number of arrivals in the ready list before this process.