How does the Deadline IO Scheduler work?

[Sreyan Chakravarty]

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.

Hence I would be really grateful if someone would help me clearing my
doubts:

My questions are as follows:

1) Since the deadline scheduler copies each request into two queues ie. the
sorted by block number and the queue sorted by deadlines.

So effectively there are two copies of the same IO request.

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.

Otherwise the kernel must be keeping track of the requests that have
already executed.

So how does the kernel handle this?

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.

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?

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?

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.

So which one of the above will happen.

Would be very helpful if someone helped me understand these doubts.

Regards,
Sreyan Chakravarty
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20180124/0927511c/attachment.html>