Linux uses request structures to pass the I/O requests to the devices. All the block devices maintain a list of request structures. When a buffer is to be read or written, the kernel calls ll_rw_block() routine and passes it an array of pointers to buffer heads. ll_rw_block() routine in turn calls make_request() routine for each buffer. make_request() first tries to cluster the buffer with the existing buffers in any of the request structures present in the device queue. A request structure consists of a list of buffers which are adjacent on the disk. This clustering is performed only for the drivers compiled in the kernel and not for loadable modules. If clustering is possible, no new request structure is created, otherwise a new request is taken from the global pool of structures and initialized with the buffer and is passed to the add_request() routine. This routine applies the elevator algorithm using insertion sort based on the minor number of the device and the block number of buffer. If the device queue is empty, the kernel calls the strategy routine i.e. the request_fn() of the driver; otherwise, it is the responsibility of the driver to reinvoke it from the interrupt context (see Figure 4). Another requirement for request_fn() is that it cannot block as it needs to be called from the interrupt context.
To allow the accumulation of requests in the device queue, a plug is used. When the request comes in and the device queue is empty, the plug is put at the head of the device queue, and a task comprising of the unplug function is registered in the disk task queue. Thus the requests keep on accumulating for some time and then the task queue executes the unplug routine which removes the plug and calls the request_fn() to service the requests.
