GATE CSE 2023 | Question: 17

Question

Which one or more of the following $\text{CPU}$ scheduling algorithms can potentially cause starvation?

• A. First-in First-Out
• B. Round Robin
• C. Priority Scheduling
• D. Shortest Job First

Comments

@VjayDeenanathChauhan Yes, it can suffer from starvation. In SRTF, the process with the shortest remaining exexution time is always chosen to run next. So if shorter processes keep arriving, longer processes may be indefinitely posponed, leading to starvation.

---

Ofc there is starvation. If shorter processes keep coming, then longer processes have to wait.

---

Those who confused why STARVATION is not possible in RR if it is possible in FCFS-

 RR WILL ALWAYS HAVE A FINITE TIME QUANTUM WHATEVER IT IS……..MAY BE 10 YEARS or  100YEARS…but after that fixed amout of  time other process will get CPU for sure.so starvation will never be there.

read this answer carefully provided by @Sachin Mittal 1 sir

Round Robin (RR) scheduling will never lead to starvation because every job is guaranteed CPU time after a fixed time quantum.

Since the time quantum is finite, each process eventually gets its turn to execute after a finite period, ensuring fairness among all tasks.

It is worth noting that the time quantum can be very large — for example, 10 minutes, 10 years, or even 100 years — but as long as it remains finite, every process will still receive CPU time and starvation will not occur.

Answer 1

Some History on this question:

What a controversy this was…

Telegram was full of people saying C, D is correct.

GO Classes was the first to say that even FCFS may have starvation — no one believed us, but we said it immediately after the paper was done.

See this video — we went live right after the paper ended: Watch Here 🎥

Also, see this follow-up session we conducted a day later: Watch Here 🎬

Both A, C, D and C, D were finally accepted as answers by IIT Kanpur. Anyway, GO Classes was the first to predict this answer accurately.

---

Please find the complete draft which we have submitted to challenge this question –

 View Draft Backup Link

The possible answers are either (A, C, D) or (C, D).

Both answers are supported by standard resources.

Shortest Job First and Priority Scheduling are prone to suffering from starvation.

Shortest Job First (SJF):
New shorter jobs may keep on coming.

Priority Scheduling:
Higher priority jobs may keep on coming.

Round Robin (RR) scheduling will never lead to starvation because every job is guaranteed CPU time after a fixed time quantum.

Since the time quantum is finite, each process eventually gets its turn to execute after a finite period, ensuring fairness among all tasks.

It is worth noting that the time quantum can be very large — for example, 10 minutes, 10 years, or even 100 years — but as long as it remains finite, every process will still receive CPU time and starvation will not occur.

Now let’s talk about FCFS.

Can First Come First Serve lead to Starvation?

Just imagine a first job submitted to CPU is –

while(1);

Yes, Infinite loop. Do you think other jobs will ever get a chance?

Berkeley Slide FCFS Starvation ✅

Page 32 https://inst.eecs.berkeley.edu/~cs162/su20/static/lectures/12.pdf

Berkeley Question FCFS Starvation ✅

Page 15
https://people.eecs.berkeley.edu/~kubitron/courses/cs162-F08/exams/fa07mt1-solutions.pdf

But there are other standard resources too which say NO Starvation 

IIT Bombay No Starvation ❌

Check Page 10 https://www.cse.iitb.ac.in/~rkj/cs347/additional/lectures/scheduling.pdf

UCSD No Starvation ❌

UCSD Lecture 8 also mentions that FCFS has no starvation.
Check Page 8 https://cseweb.ucsd.edu/classes/fa05/cse120/lectures/120-l8.pdf#page=8

---

📝 Edit:

GATE has accepted both (A, C, D) and (C, D) as answers.

Comments

GG Boys

---

dont you think the question should have also mentioned premptive or non premptive SJF

---

@Sachin Mittal 1 @Deepak Poonia

Sir please have a look at it. If this understanding is wrong then please explain what is wrong.

The pure definition of starvation really means that if a process is not getting a chance to execute then it is in starve mode or is starved. 

 

From Wikipedia:

From Tanenbaum: Page 463

It is clearly mentioned Starvation can be avoided by using a FCFS.

 

 

From OS: Three easy pieces: Problems With MLFQ

 

by interactive jobs they mean the one that needs to be preempted again and again because of the users activeness to get quick response. 

 

The question is directly asked from Abraham Silberschatz:

 

 

And I still believe that FCFS will not suffer from starvation. here's the reasoning.

 

When we say FCFS we say about non preemption and that in itself means that whatever the queue will be the last element will always get a chance to execute. No matter it is 1 second (if burst time is in milliseconds or 1 light year(just a joke). 

Now what starvation means is that the process nowhere get a chance to execute and that can happen because the scheduling algo is such that it always allow and preempts processes leaving that one process the scheduling like priority based and shortest job first. 

 

And FCFS doesn't have the capability to do that to kind of decide that (decide is a wrong term here). It simply will run a order maybe the worst. 

Starvation is only and only applicable if a process is denied to get execute. And FCFS has no power to do that.

 

Here you are applying a condition on a task/process. It's a task that keeps on running. But FCFS knows nothing about a process.

For an example: say this task while(1); and another task say T2 are in the queue.

They both arrive in the queue. Now FCFS sole purpose is to assign the Tasks in a FCFS basis, for it, it doesn't matter whether the task will ever end or not. It will give the chance to T2 as well. It's T1 property that is restricting T2 to execute but as a scheduler FCFS doesn't cause starvation to T2. Moreover T2 is getting starved because of T1 not because the scheduler is scheduling the process in that way. 

FCFS would cause starvation if it would do something like execute T1 put T1 out of the queue or hold it and then again execute T1 but it is not in the behavior of it. It simply can't do this.

Answer 2

Some History on this question:

What a controversy this was….

Telegram was full of people fighting which one should be correct out of A,C,D and C,D

Both A,C,D and C,D were accepted as answers finally by IITK
Anyway GO was first to predict this answer accurately, probably within 10 days after the exam

Comments

lol, glad to know

Answer 3

Answer should be both A,C,D and C,D.

I have attached some slides from universities and Books in favor that there is no starvation in FCFS.

IIT Bombay:

https://www.cse.iitb.ac.in/~rkj/cs347/additional/lectures/scheduling.pdf#page=10

University of Waterloo:

https://student.cs.uwaterloo.ca/~cs350/S10/notes/_Scheduling.pdf#page=9

The University of Texas at Austin:

https://www.cs.utexas.edu/users/dahlin/Classes/UGOS/lectures/lec3.pdf#page=7

University of California San Diego:

https://cseweb.ucsd.edu/classes/fa05/cse120/lectures/120-l8.pdf#page=8

University of Edinburgh,UK

https://www.inf.ed.ac.uk/teaching/courses/os/slides/09-sched.pdf#page=15

 

Operating System Concepts Tenth Edition (Galvin)

https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf#page=324

official Answer is given as,

 

It is mentioned in Question 5.7 that  “ the FCFS algorithm is the RR algorithm with an infinite time quantum”. So, if FCFS algorithm has starvation then RR algorithm can also potentially have starvation.

https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf#page=320

Operating Systems Internals And Design Principles Seventh Edition William Stallings

https://engineering.futureuniversity.com/BOOKS%20FOR%20I/William%20Stallings%20-%20Operating%20Systems%20(1).pdf#page=425

 

Comments

The students are lucky that IIT accepted A,C,D as the answer as well :) But I strongly agree with the statement “the FCFS algorithm is the RR algorithm with an infinite (very very large) time quantum (TQ more than BT of all the processes) ...So, if FCFS algorithm has starvation then RR algorithm can also potentially have starvation”

Just as how infinite loop/recursion is kind of an exception, similarly taking infinite or very very large quantum is also like an exception here.

This statement should have been enough to say that either A,B,C,D or C,D is correct.

---

Round Robin with an infinite quantum is do any one job at a time. That is not really round robin. Round Robin should preempt. If it is quantum is finite, then there can never be any starvation as a proccess always gets CPU after some finite time(however large it may be).

FIFO like all non preemtive algorithms can cause system-level halts in systems where multiple processes can have an infinite burst time.

However starvation is usually only talked about in terms of priority based scheduling algorithms. The problem is of definations, the thing that causes the most ambiguity in GATE. The answer could be ACD or CD but never ABCD as Round Robin is always fair.

---

One of the best answer, mentioning almost all the references for the problem

Answer 4

The answer is C, D.

Starvation is also called “Indefinite Blocking”. This definition and the word indefinite in particular are important here. With priority and SJF scheduling a process may be blocked for an indefinite(i.e, we cannot say how long it will take to run but it will get its chance at some point in time mostly because of aging techniques) time period when a stream of high-priority processes enters the system. In fact, starvation is associated with only priority-based algorithms.

In FCFS, either the process runs or blocks permanently(definitely). There is no indefinite blocking happening here. So, no starvation.

Comments

I think this argument is enough to change the key to C, D and make every resource out there on the internet consistent.

---

From Galvin 10^th Edition.

Answer 5

If infinite burst time is possible:

Ans: A,C,D

But since convoy effect exists, to acknowledge this problem, (and infinite burst not mentioned explicitly) also ans = C,D

Finally after answer challenge both A,C,D and C,D were awarded marks by IITK