block层IO调度器 (deadline调度算法) linux内核源码详解教程

本文是笔者在之前写过的一篇《iostat IO统计原理linux内核源码分析----基于单通道SATA盘》基础上，对IO传输过程涉及的IO请求的合并、加入IO算法队列、从IO算法队列派发IO请求、deadline调度算法涉及的linux内核源码，做更深层次的探讨，内核版本3.10.96。更详细的源码注释见https://github.com/dongzhiyan-stack/kernel-code-comment。

跟上篇一样，开头先来个IO传输的入口函数submit\_bio->generic\_make\_request->blk\_queue\_bio流程图。

本文正式开讲前，先说几点，rq和req都是同一个意思，都代表IO请求struct request结构。流程图中的虚线代表进入一个新的函数。

1 blk\_queue\_bio函数IO请求的合并

1.1 bio的合并

1 blk\_queue\_bio()函数中，首先尝试能否将bio合并到进程plug->list链表上的req，合并成功直接返回。

2 接着执行elv\_merge()函数尝试看能否将bio合并到IO算法队列里的req，如果可以合并则执行bio\_attempt\_front\_merge()/bio\_attempt\_back\_merge()将bio前项/后项到匹配的req。这个req合并bio后，req扇区起始/结束地址增大。接着需再尝试将req合并到其他req，就是req的二次合并，具体是执行attempt\_front\_merge()/attempt\_back\_merge()函数进行前项/后项二次req合并。如果二次合并失败，则执行elv\_merged\_request()：因为req发生了前项或者后项合并，req的扇区起始或者结束地址增大，需要把req从hash队列或者调度算法deadline红黑树队列中剔除，再按照req新的扇区起始或者结束地址插入队列

3 如果bio没找到能合并的req，就需要get\_request()分配新的req，然后调用\_\_elv\_add\_request()函数把新分配的req添加到IO算法队列。

1.1.1 elv\_merge函数讲解

先看下流程图

int elv\_merge(struct request\_queue *q, struct request **req, struct bio *bio)

{

struct elevator\_queue *e = q->elevator;

struct request *\_\_rq;

int ret;

//是否可以把bio合并到q->last\_merge，上次rq队列合并过的rq，elv\_rq\_merge\_ok是做一些权限检查啥的

if (q->last\_merge && elv\_rq\_merge\_ok(q->last\_merge, bio)) {

//检查bio和q->last\_merge代表的req磁盘范围是否挨着，挨着则可以合并bio到q->last\_merge，分为前项合并和后项合并

ret = blk\_try\_merge(q->last\_merge, bio);

if (ret != ELEVATOR\_NO\_MERGE) {

*req = q->last\_merge;

return ret;

}

}

\_\_rq = elv\_rqhash\_find(q, bio->bi\_sector);

if (\_\_rq && elv\_rq\_merge\_ok(\_\_rq, bio)) {

*req = \_\_rq;

return ELEVATOR\_BACK\_MERGE;//找到可以合并的req，这里返回ELEVATOR\_BACK\_MERGE，表示后项合并

}

//具体IO调度算法函数cfq\_merge或者deadline\_merge，找到可以合并的bio的req，这里是把bio前项合并到req

if (e->type->ops.elevator\_merge\_fn)

return e->type->ops.elevator\_merge\_fn(q, req, bio);//返回ELEVATOR\_FRONT\_MERGE，前项合并

return ELEVATOR\_NO\_MERGE;

}

1.1.2 bio\_attempt\_front\_merge、bio\_attempt\_back\_merge函数讲解

bio\_attempt\_front\_merge()/bio\_attempt\_back\_merge()函数的源码比较简单，就是bio前项/后项合并到req，简单看下二者的源码。

//req和bio二者磁盘范围挨着，req向前合并本次的bio，合并成功返回真

static bool bio\_attempt\_front\_merge(struct request\_queue *q,

struct request *req, struct bio *bio)

{

const int ff = bio->bi\_rw & REQ\_FAILFAST\_MASK;

bio->bi\_next = req->bio;

req->bio = bio;

req->buffer = bio\_data(bio);//该bio对应的bh的内存page地址

//req->\_\_sector代表的磁盘空间起始地址=bio->bi\_sector.显然req代表的磁盘空间范围向前扩张

req->\_\_sector = bio->bi\_sector;

req->\_\_data\_len += bio->bi\_size; //req扇区范围向前增大

req->ioprio = ioprio\_best(req->ioprio, bio\_prio(bio));

drive\_stat\_acct(req, 0);

return true;

}

//req和bio二者磁盘范围挨着，req向后合并本次的bio，合并成功返回真

static bool bio\_attempt\_back\_merge(struct request\_queue *q, struct request *req,

struct bio *bio)

{

const int ff = bio->bi\_rw & REQ\_FAILFAST\_MASK;

req->biotail->bi\_next = bio;

req->biotail = bio;

//req->\_\_sector没变，但是req->\_\_data\_len累加本次的bio磁盘范围bio->bi\_size

req->\_\_data\_len += bio->bi\_size;

req->ioprio = ioprio\_best(req->ioprio, bio\_prio(bio));

//IO合并后，更改IO使用率等数据

drive\_stat\_acct(req, 0);

return true;

}

1.1.3 attempt\_front\_merge()、attempt\_back\_merge()、attempt\_merge()源码讲解

attempt\_front\_merge()/attempt\_back\_merge()函数都是调用attempt\_merge()函数，如下：

//之前req发生了前项合并,req的磁盘空间向前增大,从算法队列(比如deadline的红黑树队列)取出req的上一个req即prev,再次尝试把req合并到prev后边

int attempt\_front\_merge(struct request\_queue *q, struct request *rq)

{

//红黑树中取出req原来的前一个req,即prev

struct request *prev = elv\_former\_request(q, rq);

if (prev)//把req合并到prev，然后把req从算法队列剔除掉，做一些剔除req的收尾处理,并更新IO使用率数据

return attempt\_merge(q, prev, rq);

return 0;

}

//之前req发生了后项合并,req的磁盘空间向后增大,从算法队列(比如deadline的红黑树队列)取出req的下一个req即next,再次尝试把next合并到req后边

int attempt\_back\_merge(struct request\_queue *q, struct request *rq)

{

//只是从IO调度算法队列里取出req的下一个req给next，调用的函数elv\_rb\_latter\_request(deadline算法)或noop\_latter\_request(noop算法)

struct request *next = elv\_latter\_request(q, rq);

if (next)//把next合并到req，然后把next从算法队列剔除掉，做一些剔除next的收尾处理,并更新IO使用率数据

return attempt\_merge(q, rq, next);

//如果req没有next req，只能返回0

return 0;

}

下边现在重点看下attempt\_merge()的流程图和源码实现。

static int attempt\_merge(struct request\_queue *q, struct request *req,

struct request *next)//把next合并到req后边，req来自比如q->last\_merge或hash队列的req

{

//检查req扇区范围后边紧挨着next，没有紧挨着返回0

if (blk\_rq\_pos(req) + blk\_rq\_sectors(req) != blk\_rq\_pos(next))

return 0;

//在这里更新req->nr\_phys\_segments，扇区总数，因为要把next合并到req后边吧

if (!ll\_merge\_requests\_fn(q, req, next))

return 0;

if (time\_after(req->start\_time, next->start\_time))//如果next->start\_time更小则赋值于req->start\_time

req->start\_time = next->start\_time;

//一个req对应了多个bio，req->biotail应该是指向next上的第一个bio吧

req->biotail->bi\_next = next->bio;

//biotail貌似指向了next的最后一个bio

req->biotail = next->biotail;

//req吞并了next的磁盘空间范围

req->\_\_data\_len += blk\_rq\_bytes(next);

elv\_merge\_requests(q, req, next);

//next合并打了req，没用了，这个next从in flight队列剔除掉，顺便执行part\_round\_stats更新io\_ticks IO使用率计数

blk\_account\_io\_merge(next);

//req优先级，cfq调度算法的概念

req->ioprio = ioprio\_best(req->ioprio, next->ioprio);

if (blk\_rq\_cpu\_valid(next))

req->cpu = next->cpu;

return 1;

}

1.1.4 elv\_merged\_request()函数讲解

该函数流程图和源码如下：

void elv\_merged\_request(struct request\_queue *q, struct request *rq, int type)

{

struct elevator\_queue *e = q->elevator;

//如果刚req发生了前项合并，req扇区起始地址增大，把req从deadline的红黑树队列删除再按照新的扇区起始地址插入红黑树队列，具体调用deadline算法的deadline\_merged\_request函数

if (e->type->ops.elevator\_merged\_fn)

e->type->ops.elevator\_merged\_fn(q, rq, type);

if (type == ELEVATOR\_BACK\_MERGE)

//如果刚req发生了后项合并，req扇区结束地址增大，把req从hash队列删除再按照新的扇区结束地址插入hash队列

elv\_rqhash\_reposition(q, rq);

//q->last\_merge保存刚发生合并的req

q->last\_merge = rq;

}

1.1.5 \_\_elv\_add\_request()函数讲解

该函数主要负责将req添加IO算法队列里，流程图与源码如下：

deadline算法elevator\_add\_req\_fn接口函数是deadline\_add\_request()，目的是将req插入到红黑树队列和fifo队列\_\_elv\_add\_request源码如下：

//新分配的req插入IO算法队列，或者是把当前进程plug链表上req全部插入到IO调度算法队列

void \_\_elv\_add\_request(struct request\_queue *q, struct request *rq, int where)

{

rq->q = q;

switch (where) {

case ELEVATOR\_INSERT\_REQUEUE:

case ELEVATOR\_INSERT\_FRONT://前向合并

rq->cmd\_flags |= REQ\_SOFTBARRIER;

list\_add(&rq->queuelist, &q->queue\_head);//req直接插入q->queue\_head链表头而已，并没有进行req合并

break;

case ELEVATOR\_INSERT\_BACK://后向合并

rq->cmd\_flags |= REQ\_SOFTBARRIER;

//循环调用deadline算法的elevator\_dispatch\_fn接口一直选择派发的req到q->queue\_head链表

elv\_drain\_elevator(q);

list\_add\_tail(&rq->queuelist, &q->queue\_head);

//这里调用底层驱动数据传输函数，就会从rq->queue\_head链表取出req发送给磁盘驱动去传输

\_\_blk\_run\_queue(q);

break;

case ELEVATOR\_INSERT\_SORT\_MERGE://把进程独有的plug链表上的req插入IO调度算法队列里走这里

if (elv\_attempt\_insert\_merge(q, rq))

break;

case ELEVATOR\_INSERT\_SORT://新分配的req插入的IO调度算法队列

BUG\_ON(rq->cmd\_type != REQ\_TYPE\_FS);

rq->cmd\_flags |= REQ\_SORTED;

//队列插入新的一个req

q->nr\_sorted++;

if (rq\_mergeable(rq)) {

//新的req靠req->hash添加到IO调度算法的hash链表里

elv\_rqhash\_add(q, rq);

if (!q->last\_merge)

q->last\_merge = rq;

}

//把req插入到IO调度算法队列里，deadline是插入到红黑树队列和fifo队列

q->elevator->type->ops.elevator\_add\_req\_fn(q, rq);//deadline算法函数是deadline\_add\_request()

break;

case ELEVATOR\_INSERT\_FLUSH:

rq->cmd\_flags |= REQ\_SOFTBARRIER;

blk\_insert\_flush(rq);

break;

}

}

好的，前文主要讲解了：submit\_bio->generic\_make\_request->blk\_queue\_bio发起的IO请求，bio怎么合并到IO算法队列，或者新分配的req怎么插入到IO算法队列。IO算法队列需要特别说明一下，一共有这几个：IO算法默认的hash队列、deadline调度算法特有的红黑树rb队列和fifo队列。

1 IO算法默认的hash队列：每一个新分配的req必然以“ req扇区结束地址”为key插入到hash队列。具体见elv\_rqhash\_add函数，里边执行hash\_add(e->hash, &rq->hash, rq\_hash\_key(rq))把req添加到hash队列。rq\_hash\_key(rq)就是hash key，即req扇区结束地址。

还有其他几处对hash队列的操作：1前文介绍过的elv\_merged\_request函数，里边执行elv\_rqhash\_reposition对req在hash队列重新排序。原因是req进行了后项合并，扇区结束地址变大了，那就要对这个req按照新的扇区结束地址在hash链表中重新排序；2 blk\_queue\_bio->\_\_elv\_add\_request->elv\_rqhash\_add流程是把req添加到hash队列(hash key是req扇区结束地址)。3 blk\_queue\_bio ->elv\_merge->elv\_rqhash\_find 遍历hash队列的req。

2 deadline调度算法的红黑树rb队列和fifo队列：deadline\_add\_request()函数负责将新的req添加到红黑树队列和fifo队列。把新的req插入红黑树队列的规则是req的“扇区起始地址”从小到大依次排列。新的req 插入fifo队列比较简单，直接插入fifo 队列dd->fifo\_list[data\_dir]链表尾部即可。fifo队列存在的意义是，每个req都有一个超时时间dd->fifo\_expire[data\_dir] ，新的req都是插入fifo队列的尾部。fifo队列尾部的req都是最晚插入fifo队列的，fifo队列头的req都是最早插入req的。fifo队列头的req最先被检查是否超时了，超时到了则选择该req派发。

deadline\_add\_request和deadline\_add\_rq\_rb源码如下：

static void deadline\_add\_request(struct request\_queue *q, struct request *rq)

{

struct deadline\_data *dd = q->elevator->elevator\_data;

const int data\_dir = rq\_data\_dir(rq);

//req添加到红黑树队列里

deadline\_add\_rq\_rb(dd, rq);

//设置req调度超时时间，超时时间到，则会把fifo队列头的req派发给驱动

rq\_set\_fifo\_time(rq, jiffies + dd->fifo\_expire[data\_dir]);

//req插入到fifo队列尾部

list\_add\_tail(&rq->queuelist, &dd->fifo\_list[data\_dir]);

}

//req添加到红黑树队列里

static void

deadline\_add\_rq\_rb(struct deadline\_data *dd, struct request *rq)

{

struct rb\_root *root = deadline\_rb\_root(dd, rq);

//把rq添加到红黑树里，就是按照每个req的起始扇区排序的

elv\_rb\_add(root, rq);

}

2 进程plug链表req的插入IO算法队列

内核很多地方派发req实际是执行blk\_flush\_plug\_list()函数把req插入IO算法队列，比如blk\_queue\_bio()->blk\_flush\_plug\_list()，blk\_flush\_plug()->blk\_flush\_plug\_list()。blk\_flush\_plug\_list函数源码和流程图如下：

//把进程plug链表上的req依次插入IO调度算法队列上

void blk\_flush\_plug\_list(struct blk\_plug *plug, bool from\_schedule)

{

struct request\_queue *q;

unsigned long flags;

struct request *rq;

LIST\_HEAD(list);

unsigned int depth;

list\_splice\_init(&plug->list, &list);

//对plug链表上的req排序，应该是按照每个req的起始扇区地址排序，起始扇区小的排在前

list\_sort(NULL, &list, plug\_rq\_cmp);

q = NULL;

depth = 0;

//依次取出进程plug链表上的req依次插入IO调度算法队列上

while (!list\_empty(&list)) {

//取出req

rq = list\_entry\_rq(list.next);

//从plug链表删除req

list\_del\_init(&rq->queuelist);

//在这里把req插入到IO调度算法队列里

\_\_elv\_add\_request(q, rq, ELEVATOR\_INSERT\_SORT\_MERGE);

//深度depth加1

depth++;

}

if (q)//里边执行\_\_blk\_run\_queue派发req给磁盘驱动

queue\_unplugged(q, depth, from\_schedule);

}

这个函数就是就是依次取出进程plug链表上的req依次执行\_\_elv\_add\_request()插入IO算法队列。\_\_elv\_add\_request()函数源码上一节已经详细解释过。还有一点需要注意，blk\_flush\_plug\_list()函数最后执行queue\_unplugged()才会把刚才插入IO算法队列的req派发给磁盘驱动，才能完成最终的磁盘数据传输。queue\_unplugged()里实际是执行\_\_blk\_run\_queue()->\_\_blk\_run\_queue\_uncond()->scsi\_request\_fn()把req派发给磁盘驱动。下文重点讲解。

3 \_\_blk\_run\_queue()派发req到磁盘驱动

3.1 req整体派发流程

先看下整体流程图

//从IO算法队列选择req派发给磁盘驱动

static void scsi\_request\_fn(struct request\_queue *q)

{

struct scsi\_device *sdev = q->queuedata;

struct Scsi\_Host *shost;

struct scsi\_cmnd *cmd;

struct request *req;

shost = sdev->host;

for (;;) {

int rtn;

//取出待派发的req，并分配SCSI命令结构体cmd并赋值

req = blk\_peek\_request(q);

if (!req || !scsi\_dev\_queue\_ready(q, sdev))

break;

//req 传输前的一些操作

blk\_start\_request(req);

cmd = req->special;

//发送SCSI命令，真正开始传输数据

rtn = scsi\_dispatch\_cmd(cmd);

}

}

重点是执行blk\_peek\_request()选择派发的req，分配SCSI命令cmd并赋值，源码如下：

struct request *blk\_peek\_request(struct request\_queue *q)

{

while ((rq = \_\_elv\_next\_request(q)) != NULL) {

ret = q->prep\_rq\_fn(q, rq);//scsi\_prep\_fn

if (ret == BLKPREP\_OK) {

break;

}

}

blk\_peek\_request()函数整体总结如下：

1 从q->queue\_head队列头取出待进行IO数据传输的req.如果q->queue\_head没有req，则执行deadline\_dispatch\_requests从fifo队列选择派发的req

2 分配一个struct scsi\_cmnd *cmd，使用req对cmd进行部分初始化cmd->request=req，req->special = cmd，还有cmd->transfersize传输字节数、cmd->sc\_data\_direction DMA传输方向

3 先遍历req上的每一个bio，再得到每个bio的bio\_vec，把bio对应的文件数据在内存中的首地址bvec->bv\_pag+bvec->bv\_offset写入scatterlist。scatterlist是磁盘数据DMA传输有关的数据结构，scatterlist保存到bidi\_sdb->table.sgl，bidi\_sdb是req的struct scsi\_data\_buffer成员。

blk\_peek\_request()函数里执行\_\_elv\_next\_request()，目的是：从q->queue\_head链表取出待传输的req，如果q->queue\_head链表没有req，则执行deadline\_dispatch\_requests()从fifo队列选择派发的req到q->queue\_head。

static inline struct request *\_\_elv\_next\_request(struct request\_queue *q)

{

while (1) {

//从q->queue\_head取出待传输的req，如果q->queue\_head没有req，则执行deadline\_dispatch\_requests从fifo队列选择派发的req

if (!list\_empty(&q->queue\_head)) {

rq = list\_entry\_rq(q->queue\_head.next);

return rq;

}

if (unlikely(blk\_queue\_bypass(q)) ||

!q->elevator->type->ops.elevator\_dispatch\_fn(q, 0))//deadline\_dispatch\_requests()选择派发的req

return NULL;

}

deadline\_dispatch\_requests()函数是deadline IO调度算法的核心，重点讲解。

3.2 deadline\_dispatch\_requests()IO调度算法派发req

deadline\_dispatch\_requests()函数流程，源码和流程图如下：

static int deadline\_dispatch\_requests(struct request\_queue *q, int force)

{

struct deadline\_data *dd = q->elevator->elevator\_data;

//如果fifo队列有read req,list\_empty返回0，reads为1

const int reads = !list\_empty(&dd->fifo\_list[READ]);

//如果fifo队列有write req,list\_empty返回0，writes为1

const int writes = !list\_empty(&dd->fifo\_list[WRITE]);

struct request *rq;

int data\_dir;

//每次从红黑树选取一个req发给驱动传输，这个req的下一个req保存在next\_rq[]，现在又向驱动发送req传输，优先先从next\_rq取出req

if (dd->next\_rq[WRITE])

rq = dd->next\_rq[WRITE];

else

rq = dd->next\_rq[READ];

if (rq && dd->batching < dd->fifo\_batch)

goto dispatch\_request;

if (reads) {

BUG\_ON(RB\_EMPTY\_ROOT(&dd->sort\_list[READ]));

if (writes && (dd->starved++ >= dd->writes\_starved))

goto dispatch\_writes;

//否则下面选择read req

data\_dir = READ;

goto dispatch\_find\_request;

}

if (writes) {

dispatch\_writes:

BUG\_ON(RB\_EMPTY\_ROOT(&dd->sort\_list[WRITE]));

//dd->starved清0

dd->starved = 0;

//下面选择write req，就一个赋值操作

data\_dir = WRITE;

goto dispatch\_find\_request;

}

return 0;

dispatch\_find\_request:

//deadline\_check\_fifo:如果deadline fifo队列有超时的req要传输返回1，或者next\_rq没有暂存req，if都成立。则从fifo队列头取出req

if (deadline\_check\_fifo(dd, data\_dir) || !dd->next\_rq[data\_dir]) {

//取出fifo队列头的req，最早入fifo队列的req，最早入队的req当然更容易超时

rq = rq\_entry\_fifo(dd->fifo\_list[data\_dir].next);

} else {

//否则直接取出next\_rq暂存的req

rq = dd->next\_rq[data\_dir];

}

//batching清0

dd->batching = 0;

dispatch\_request://到这里，req直接来自next\_rq或者fifo队列，这个req就要被发给驱动传输了

//batching加1

dd->batching++;

deadline\_move\_request(dd, rq);

return 1;

}

deadline\_dispatch\_requests()函数简单来说是：选择合适待派发给驱动传输的req，然后把req添加到q->queue\_head链表，然后设置新的next\_rq，并把req从fifo队列和红黑树队列剔除。将来向磁盘驱动程序派发的req就是从queue\_head链表取出的。req来源有:上次派发设置的next\_rq；read req派发过多而选择的write req；fifo 队列上超时要传输的req，统筹兼顾，有固定策略。

1 首先呢，从dd->next\_rq[WRITE/ READ]获取上次派发req后设置的next req，if (rq && dd->batching < dd->fifo\_batch)这个判断是为了防止一直派发dd->next\_rq[WRITE/ READ]，每派发一个next req，dd->batching就会加1，如果dd->batching < dd->fifo\_batch成立，就goto dispatch\_request直接使用dd->next\_rq[WRITE/ READ]指定的next req。

2 如果if (rq && dd->batching < dd->fifo\_batch) 不成立，说明派发的dd->next\_rq[WRITE/ READ]指定的next req太多了，该派发fifo队列的req了，这个req更紧急。此时就会进入if (reads) 或者if (writes) 分支，最后执行goto dispatch\_find\_request从dd->fifo\_list[data\_dir] fifo队列选择派发的req，具体流程是：先执行if (deadline\_check\_fifo(dd, data\_dir) || !dd->next\_rq[data\_dir])，deadline\_check\_fifo(dd, data\_dir)函数是判断fifo队列有没有超时的req，有则执行rq = rq\_entry\_fifo(dd->fifo\_list[data\_dir].next) 取出fifo队列头的req(这是最早加入fifo队列的req，最早入队的req当然更容易超时)。

3 回到第二步，还有一点没讲，就是if (reads)分支里的if (writes && (dd->starved++ >= dd->writes\_starved)) ，每派发一个read req(即data\_dir = READ)则dd->starved++加1，等到dd->starved++ >= dd->writes\_starved则goto dispatch\_writes执行data\_dir = WRITE，这样就会派发write req。dd->starved的作用是派发dd->writes\_starved个read req后，就该派发write req了，防止write req饿着。

deadline\_dispatch\_requests()最后执行的deadline\_move\_request()函数，作用是把req添加到req->queue\_head链表，设置新的next\_rq，并把req从fifo队列和红黑树队列剔除，将来磁盘驱动程序就是从req->queue\_head链表取出req派发的。源码如下：

//把req添加到req->queue\_head链表，设置新的next\_rq，并把req从fifo队列和红黑树队列剔除，将来磁盘驱动程序就是从req->queue\_head链表取出req传输的

static void

deadline\_move\_request(struct deadline\_data *dd, struct request *rq)

{

//req是read还是write

const int data\_dir = rq\_data\_dir(rq);

dd->next\_rq[READ] = NULL;

dd->next\_rq[WRITE] = NULL;

//从红黑树队列中取出req的下一个req作为next\_rq，下次deadline\_dispatch\_requests()选择派发给的req时就可能是它了

dd->next\_rq[data\_dir] = deadline\_latter\_request(rq);

//req的磁盘空间end地址

dd->last\_sector = rq\_end\_sector(rq);

//把req添加到req->queue\_head链表，并把req从fifo队列和红黑树队列剔除，将来磁盘驱动程序就是从queue\_head链表取出req派发的

deadline\_move\_to\_dispatch(dd, rq);

}

deadline\_move\_to\_dispatch()函数源码如下：

//把req添加到req->queue\_head链表，并把req从fifo队列和红黑树队列剔除，将来磁盘驱动程序就是从queue\_head链表取出req派发的

static inline void

deadline\_move\_to\_dispatch(struct deadline\_data *dd, struct request *rq)

{

struct request\_queue *q = rq->q;

//从fifo队列和红黑树队列剔除req

deadline\_remove\_request(q, rq);

//把req添加到req->queue\_head链表，将来磁盘驱动程序就是从queue\_head链表取出req派发的

elv\_dispatch\_add\_tail(q, rq);

}

deadline\_remove\_request()源码如下：

//deadline算法从fifo队列和红黑树剔除req。剔除前如果req原本是dd->next\_rq[]保存req，还要找到req在红黑树的下一个req赋值给dd->next\_rq[]

static void deadline\_remove\_request(struct request\_queue *q, struct request *rq)

{

struct deadline\_data *dd = q->elevator->elevator\_data;

//从fifo队列剔除rq

rq\_fifo\_clear(rq);

//如果req原本是dd->next\_rq[]保存req，则要找到req在红黑树的下一个req赋值给dd->next\_rq[]，然后把req从红黑树中剔除

deadline\_del\_rq\_rb(dd, rq);

}

deadline\_del\_rq\_rb()函数源码如下：

//如果req原本是dd->next\_rq[]保存req，则要找到req在红黑树的下一个req赋值给dd->next\_rq[]，然后把req从红黑树中剔除

static inline void

deadline\_del\_rq\_rb(struct deadline\_data *dd, struct request *rq)

{

const int data\_dir = rq\_data\_dir(rq);

if (dd->next\_rq[data\_dir] == rq)

dd->next\_rq[data\_dir] = deadline\_latter\_request(rq);

//deadline\_rb\_root(dd, rq)是取出调度算法的读或者写红黑树队列头rb\_root，然后把req从这个红黑树队列剔除掉

elv\_rb\_del(deadline\_rb\_root(dd, rq), rq);

}

//把req添加到rq->queue\_head链表，将来磁盘驱动程序就是从queue\_head链表取出req派发的

void elv\_dispatch\_add\_tail(struct request\_queue *q, struct request *rq)

{

if (q->last\_merge == rq)

q->last\_merge = NULL;

//req从hash队列剔除

elv\_rqhash\_del(q, rq);

q->nr\_sorted--;

//结束扇区

q->end\_sector = rq\_end\_sector(rq);

q->boundary\_rq = rq;

//把req添加到rq->queue\_head链表，将来磁盘驱动程序就是从queue\_head链表取出req派发的

list\_add\_tail(&rq->queuelist, &q->queue\_head);

}