长更向(ˇˍˇ)

deadline：（感觉Noop和deadline比cfq好讲，所以先讲了。。。。。。）
这是一个对各种要求，并综合考虑多方面特性进行调度的调度器，以满足对一个进程既能够顺序读写，但是又不会说出现其他进程久久不能得到块设备，所以，deadline中就引进了两种数据结构，一种是红黑树，另一种是链表（看了看红黑树的解释，感觉其实更像是二叉树的特别叫法，那还是按红黑树写比较好）红黑树负责对块设备的扇区进行顺序划分，名字叫做sort_list，另一类对进程发出的请求进行顺序排列，名字叫fifo_list
那么对于队列的请求，我们把它放在了batching中，用于统计进程需求的数量

那么读与写的优先级谁更大？读入。因为只有读入相关的代码才能够等待相应的操作，犹如你进入一家店，你需要等待服务生的下一步指示你才能进行。所以读的请求期限是写的1/10

还有一个理由说内核偏袒读方面的性能的原因，有两个东西，starved和write_starved,starved的数值由fifo_batching决定，而write_starved默认只有两个
转换成伪代码是这样的(请注意伪代码这三个字）：
if(starved>write_starved){
deviceTree.write();
}
deviceTree.read();

接下来看看scheduler的数据结构：
struct deadline_data {
struct rb_root sort_list[2];
struct list_head fifo_list[2];
struct request *next_rq[2];
unsigned int batching;
sector_t last_sector;
unsigned int starved;
int fifo_expire[2];
int fifo_batch;
int writes_starved;
int front_merges;
};
为了简洁，删除了注释，想要看注释的话等下面的链接

对deadline的定义：
static struct elevator_type iosched_deadline = {
.ops = {
.elevator_merge_fn = deadline_merge,
.elevator_merged_fn = deadline_merged_request,
.elevator_merge_req_fn = deadline_merged_requests,
.elevator_dispatch_fn = deadline_dispatch_requests,
.elevator_add_req_fn = deadline_add_request,
.elevator_queue_empty_fn = deadline_queue_empty,
.elevator_former_req_fn = elv_rb_former_request,
.elevator_latter_req_fn = elv_rb_latter_request,
.elevator_init_fn = deadline_init_queue,
.elevator_exit_fn = deadline_exit_queue,
},
.elevator_attrs = deadline_attrs,
.elevator_name = "deadline",
.elevator_owner = THIS_MODULE,
};

先初始化数据，进程需求放进队列，从第一个队列开始，从最后一个扇区找，需求相同，就检验参数，完全符合的话，放进merge（）；
static int
deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
{
struct deadline_data *dd = q->elevator->elevator_data;
struct request *__rq;
int ret;
if (dd->front_merges) {
sector_t sector = bio->bi_sector + bio_sectors(bio)
__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
if (__rq) {
BUG_ON(sector != blk_rq_pos(__rq));
if (elv_rq_merge_ok(__rq, bio)) {
ret = ELEVATOR_FRONT_MERGE;
goto out;
}
}
}
return ELEVATOR_NO_MERGE;
out:
*req = __rq;
return ret;
}

到这里就要重新插bio了，因为相应的红黑树的对应值改变了
static void deadline_merged_request(struct request_queue *q, struct request *req, int type)
{
struct deadline_data *dd = q->elevator->elevator_data;
if (type == ELEVATOR_FRONT_MERGE) {
elv_rb_del(deadline_rb_root(dd, req), req);
deadline_add_rq_rb(dd, req);
}
}

接下来就是判定，我需要接收下一个需求，还是开始进行读写，然后和通用层的合并做参数对接：
static void deadline_merged_requests(struct request_queue *q, struct request *req, struct request *next)
{
if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
if (time_before(rq_fifo_time(next), rq_fifo_time(req))) {
list_move(&req->queuelist, &next->queuelist);
rq_set_fifo_time(req, rq_fifo_time(next));
}
}
deadline_remove_request(q, next);
}

add_request()设置期望值
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);
deadline_add_rq_rb(dd, rq);
rq_set_fifo_time(rq, jiffies + dd->fifo_expire[data_dir]);
list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);
}

关键地方来了：检查starved值是否超过write_starved,move_request移走链表中的进程需求，由dispatch分配
static int deadline_dispatch_requests(struct request_queue *q, int force)
{
struct deadline_data *dd = q->elevator->elevator_data;
const int reads = !list_empty(&dd->fifo_list[READ]);
const int writes = !list_empty(&dd->fifo_list[WRITE]);
struct request *rq;
int data_dir;
if (dd->next_rq[WRITE])
rq = dd->next_rq[WRITE];
else
rq = dd->next_rq[READ];
if (rq && dd->batching < dd->fifo_batch)
if (reads) {
BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
if (writes && (dd->starved++ >= dd->writes_starved))
goto dispatch_writes;
data_dir = READ;
goto dispatch_find_request;
}
if (writes) {
dispatch_writes:
BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
dd->starved = 0;
data_dir = WRITE;
goto dispatch_find_request;
}
return 0;
dispatch_find_request:
if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
rq = rq_entry_fifo(dd->fifo_list[data_dir].next);
} else {
rq = dd->next_rq[data_dir];
}
dd->batching = 0;
dispatch_request:
dd->batching++;
deadline_move_request(dd, rq);
return 1;

move_request详细代码：
static void deadline_move_request(struct deadline_data *dd, struct request *rq)
{
const int data_dir = rq_data_dir(rq);
dd->next_rq[READ] = NULL;
dd->next_rq[WRITE] = NULL;
dd->next_rq[data_dir] = deadline_latter_request(rq);
dd->last_sector = rq_end_sector(rq);
deadline_move_to_dispatch(dd, rq);
}

移动到dispatch中执行的相关代码：
static inline void deadline_move_to_dispatch(struct deadline_data *dd, struct request *rq)
{
struct request_queue *q = rq->q;
deadline_remove_request(q, rq);
elv_dispatch_add_tail(q, rq);
}

不用数了这条回复是标准的15字。