Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can C-SCAN (elevator) algorithm cause starvation?

I'm reading Silberschatz's OS book. In section 16.8.1 it says:

The fundamental problem with the elevator algorithm is that I/O operations cocentrated in a specific region of the disk can result in starvation of requests that need to occur in other regions of the disk.

The C-SCAN algorithm, processes all sectors in order, as illustrated on this web page.
I don't understand how this could cause some requests to wait indefinitely.

like image 909
musa Avatar asked Sep 03 '11 12:09

musa


People also ask

Which disk scheduling algorithm can cause starvation?

Priority Based Disk Scheduling Suppose the system keeps sending requests for high priority reads. Due to this, any low priority requests will never be satisfied as the Disk Scheduler will be busy servicing higher priority requests. This leads to starvation.

What is a disadvantage of the SSTF scheduling algorithm?

What is a disadvantage of the SSTF scheduling algorithm? Although the SSTF algorithm is a substantial improvement over the FCFS algorithm, it is not optimal. SSTF may cause starvation of some requests.

What is the advantage of C-SCAN algorithm for SCAN algorithm?

C-SCAN Algorithm is the successor and the improved version of the SCAN scheduling Algorithm. The Head move from one end to the other of the disk while serving all the requests in between. The waiting time for the cylinders which were just visited by the head is reduced in C-SCAN compared to the SCAN Algorithm.

What is the algorithm used in elevators?

Thor Love and Thunder - The Loop The elevator algorithm is a simple algorithm by which a single elevator can decide where to stop, is summarized as follows: Continue traveling in the same direction while there are remaining requests in that same direction.


2 Answers

If you look at Silberschatz's Operating System Concepts 7th edition you'll find that n exercise 7.5's answer he says starvation "the situation whereby a process must wait beyond a reasonable period of time—perhaps indefinitely—before receiving a requested resource." so SCAN and C-SCAN may spend an awful long time near one hot region of the disk before getting back to a starving area somewhere else. The starvation doesn't have to be a permanent denial of service.

like image 59
user926600 Avatar answered Nov 10 '22 00:11

user926600


It could be made to wait indefinitely if the same sector were requested over and over. The disk would be stuck servicing that one sector forever.

like image 45
Yay295 Avatar answered Nov 10 '22 00:11

Yay295