Search code examples
operating-systemscheduling

What's the difference between device queue and waiting queue?

My understanding is that waiting queue is waiting for I/O request, so it seems like device queue is either the same as waiting queue or it's a subset of it? Is there some process in waiting queue but not in device queue?

Solution

  • What's the difference between device queue and waiting queue?

    Let's assume (for fun!) that you have a micro-kernel and a hard disk driver running as a process in user-space, where the specific device driver maintains some kind of data structure (one FIFO queue, a different queue for each IO priority level, a tree of some sort, ...) to keep track of pending operations for its device, and that this data structure is in the device driver process' virtual address space so that the device driver can access it quickly. I might (if it's just a FIFO queue and not something good) be tempted to call this a "device queue".

    Let's also assume that the scheduler (inside the micro-kernel) has:

    • some kind of data structure to keep track of "ready to run" tasks (tasks that are waiting for CPU time). I might (if it's just a FIFO queue and not something good) be tempted to call this a "waiting queue", but more likely I'd probably call it a "ready to run queue".

    • some kind of data structure to keep track of tasks that are waiting for time to pass (e.g. because they called sleep()). I might (if it's just a sorted list and not something good) be tempted to call this a "waiting queue" too, but more likely I'd probably call it a "sleeping list".

    Note that the kernel has no reason to have a data structure to keep track of tasks that are waiting for a message (from a device driver or from anywhere else); and only needs to do an if(task->state == WAITING_FOR_MESSAGE) { unblock(task); } for that case. In a similar way, if the kernel's page fault handler needs to make a task wait for a page's data to be fetched (e.g. from swap space) it can block the task (e.g. and set the task's state to WAITING_FOR_PAGE_DATA) and only needs to unblock the task when the data arrives, and doesn't need a data structure to keep track of these tasks either.