<div dir="auto">I am trying my best to understand how the deadline scheduler actually works for certain scenarios. But there is actually a lack of proper documentation for IO Schedulers in particular.<div dir="auto"><br></div><div dir="auto">Hence I would be really grateful if someone would help me clearing my doubts:</div><div dir="auto"><br></div><div dir="auto">My questions are as follows:</div><div dir="auto"><br></div><div dir="auto">1) Since the deadline scheduler copies each request into two queues ie. the sorted by block number and the queue sorted by deadlines. </div><div dir="auto"><br></div><div dir="auto">So effectively there are two copies of the same IO request.</div><div dir="auto"><br></div><div dir="auto">So what happens if a request is serviced from the deadline queue. How is that request's corresponding version removed from the sorted queue? A queue is not a random access data structure, thus to remove the request from the sorted queue the kernel must traverse the head and delink the request if the queue is implemented via a linked list.</div><div dir="auto"><br></div><div dir="auto">Otherwise the kernel must be keeping track of the requests that have already executed.</div><div dir="auto"><br></div><div dir="auto">So how does the kernel handle this?</div><div dir="auto"><br></div><div dir="auto">2) Imagine the device is busy serving a request for block 50 the next request is for block 56, then a request for block 30 comes in. </div><div dir="auto"><br></div><div dir="auto">What does the scheduler do? Does it keep go on to dispatch the request for block 56? Or does it pick block 30 since the scheduler performs sorting?</div><div dir="auto"><br></div><div dir="auto">If it picks block 56 that makes sense since it is desirable for the disk head to move in one direction rather than going back to 30. But then how is the sorting done?</div><div dir="auto"><br></div><div dir="auto">If it picks 30 then the sorting is taken care of but then the disk is doubling back and there is little benefit to the sorting step.</div><div dir="auto"><br></div><div dir="auto">So which one of the above will happen.</div><div dir="auto"><br></div><div dir="auto">Would be very helpful if someone helped me understand these doubts.</div><div dir="auto"><br></div><div dir="auto">Regards,</div><div dir="auto">Sreyan Chakravarty</div></div>