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

hope they accept our opinion😞

---

FCFS is non preemptive, so it can lead to starvation if one of the processes runs forever.

 

FCFS may cause starvation in some cases

---

wouldn’t this be a case of livelock as starvation means indefinite wait but bound to get cpu at some time whereas if a process runs forever it’s not possible to get CPU at all

Answer 1

Please find the complete draft here – 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: Higher priority jobs may keep on coming.

 

Round Robin will never lead to starvation because every job will get a time after a FIXED time quantum.
Since the time quantum is finite, eventually every job will get a chance to run after a finite amount of time. It is worth noting that the time quantum can be set to a large value, such as 10 minutes, 10 years, or even 100 years, but as long as it is finite, every job will receive a chance to execute.

 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?

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

 

Also, check below source- 
https://people.eecs.berkeley.edu/~kubitron/courses/cs162-F08/exams/fa07mt1-solutions.pdf

But there are other standard resources too which say NO Starvation

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

 

Let’s wait for GATE official answer key.

In our opinion, you can challenge either of the cases once the key comes.

Comments

Operating Systems: Internals and Design Principals- William Stallings 7th Edition (PDF also available on google)

Mentions in FCFS starvation not possible. 

---

@Sachin Mittal 1 sir, @GO Classes

Here are some standard resources that I have found, supporting that FCFS doesn’t suffer from starvation. These might be helpful in drafting a challenge. 

=> Carnegie Mellon University lecture notes:

https://www.andrew.cmu.edu/course/15-440-sp10/applications/ln/lecture7.html 

it says

This algorithm is very easy to implement, and it is also very fair and consequently starvation-free.

=> Washington University Lecture Notes : https://courses.cs.washington.edu/courses/cse451/15wi/lectures/pdf/10-sched.pdf

for FCFS

jobs treated equally, no starvation.

=>Lecture notes by IIT Kanpur : https://ict.iitk.ac.in/wp-content/uploads/CS330-Operating-Systems-lec03.pdf

=> Balancing SRPT and FCFS via Starvation Mitigation – Research paper : http://128.84.21.203/pdf/2112.14403

this paper identifies processes that starve and takes help of FCFS to mitigate starvation. Which clearly says that FCFS (without any special assumptions) doesn’t suffer from starvation.

---

we won they accepted both A,C,D and C,D

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

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.

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.