I have a few queries about how the Linux Deadline IO scheduler operates in certain cases:

My knowledge of the deadline scheduler:
The deadline IO scheduler maintains the standard queue from which it normally services IO requests, which is sorted in ascending order via the logical block number and two other queues which are sorted via submission time.

My questions:

1. Imagine if the scheduler finds that a read request in the read queue has expired, so it stops servicing from the standard queue and starts servicing the expired request from the read queue. What happens to the copy an expired request from the standard queue?
   
   If you think about it the deadline IO scheduler maintains two copies of each IO request, one in the standard queue sorted via block number and another in the read/write queue sorted via submission time.
   
   So if the request is serviced from the read/write queue what happens to the copy of the request in the standard queue? Or vice versa.
   
   A queue is not a random access data structure so the kernel cannot just go the IO request and remove it, it must be keeping track of "has this request already been executed"?
   
   How does the kernel do this?
   
   
2. Imagine if the disk head is at block 57, the next request is for block 60, but just then a request for block 55 comes in.
   
   What will the scheduler do at a time like this? Will it put the request for block 55 next line since it has a lower block number than 60 to be served or will it wait for block 60 to get completed, since it is desirable for the disk head to move in a smooth linear fashion?
   
   Going by the sorting techniques of the deadline IO scheduler my intuition tells me that the request for block 55 will be serviced next, thus effectively bringing the disk head back.
   
   But isn't it generally desirable for the disk head to move in a smooth linear fashion always.

Why do you think there are two copies? Why not just read the documentation?

http://elixir.free-electrons.com/lin...ne-iosched.txt

I think that there are two copies because of the following quote from the Wikipedia article.

To test my understanding tell me if the following outline of the deadline io scheduler is correct or not:

A request enters the scheduler, it enters either one of the two queues based on the type of request, either read or write.

The fifo_batch tunable is responsible for deciding the max number of requests served in a particular batch, so let's say it serves 5 requests from the read batch and then sees that there is an expired request in the write batch so it proceeds to service those.

Is my above understanding correct?

Also, you have not answered my second doubt, what happens if a request for a lower block number comes in when the scheduler is busy dispatching a request for a higher block number? In that case, the above described example would not really hold.

Also, have a look at this picture which describes the Deadline Scheduler, it shows two copies explicitly.

I think you are wrong about there being only one copy, how would I go about checking the source code for the deadline scheduler?

In fact, you can have a look at the source code here. It shows two structs containing the same data, as mentioned in the comments.

Honestly, between diagrams like that and the very-thorough documentation already discussed, and(!) the source-code, what more is there to "discuss?"

Well, neither the documentation nor the diagrams or the source code answers the doubts that I asked in my original question. Since you say that the diagram is correct then there are two queues then the kernel has two identical copies of the same IO request - this has not been answered. What happens if a request for a lower block number comes in while servicing a request for a higher block number, is it sorted in or is it delayed?

None of my original questions have been answered.

That's whats left to "discuss"

The lists each contain a pointer to the single request. There is one copy of each request.

Exactly ... and the algorithm is perfectly aware that it's sitting on two lists.

The "two lists" conveniently represent the set of competing concerns that apply to I/O requests. They might be time-sensitive, in which case they must be satisfied "on time," but at the same time we want to execute the actual operations as physically-efficiently as possible, bundling I/O requests together as much as possible. Two queues, each constructed according to a different heuristic, very-conveniently represent these so that no "search" is necessary. When a request is selected from one queue it is of course also removed from the other. Once it is forwarded to the action-item queue for the physical driver, the physical strategy is now fixed and it is not touched or reconsidered again.

It is actually a very simple matter to put a block into two queues at the same time.

Thanks for replying.

How is it removed ?

Let me give an example and you can point out the problems in my understanding :

Lets say the next request to be picked is from the Write Deadline Queue, since the write for 90 is expired. So it picks that IO request, now as you say it has to remove that from the sorted queue. Am I correct so far ?

So if the queues are implemented using Linked Lists, then the code has to start from either the head or tail of the queue and find the element that matches the block number and delete it from the linked list. Am I correct so far ?

I am not sure but the code I linked to shows the queues being implemented using arrays that too of length 2. That kind of seems odd since you would hope real systems queue in a large number of requests and the length would be greater than 2.

Do you see the problem ? Since I can't exactly "run" the deadline scheduler code by itself, I am unable to understand the behavior for it myself.

I haven't looked at the code – and, I'm not going to – but any struct can be a member of two queues or lists at the same time, as long as it has two sets of pointers: one for each. And, if the data structure is a doubly-linked list, in which the block points both to its successor and its predecessor, no search is required to find it. It's elementary data-structure manipulation. You simply remove the block from both of the queues of which it is now a part, one after the other.

In such implementations it is also quite common to have a "dummy block" which serves as the anchor but which can be manipulated using code that doesn't have to provide a special-case for "the anchor" vs. "a block within the queue." An "empty" list might have "one element on it – the anchor."

The two queues therefore provide a very-elegant and also very-efficient "two ways of looking at the same thing." If you will, "two possible ways to prioritize and to sequence these requests."

Sorry for the late reply.

Just tell me something:

How does the scheduler know that if it gets a request if it has already served it or not. For example, a request that is served from the deadline queue may appear later from the sorted queue, how does the kernel understand that it has already done that request?