每个块设备或者块设备的分区，都对应有自身的请求队列(request_queue),而每个请求队列都可以选择一个I/O调度器来协调所递交的request。I/O调度器的基本目的是将请求按照它们对应在块设备上的扇区号进行排列，以减少磁头的移动，提高效率。在前面讨论递交I/O请求的时候可以发现，每个request_queue都有一个request的队列，队列里的请求将按顺序被响应。实际上，除了这个队列，每个调度器自身都维护有不同数量的队列，用来对递交上来的request进行处理，而排在队列最前面的request将适时被移动到request_queue中等待响应。内核中实现的IO调度器主要有四种--Noop,Deadline,CFG以及最复杂的as.我们不妨从最简单的noop开始研究，顺便看一下调度器是如何与request_queue联系上的。

首先要了解描述elevator的数据结构。和elevator相关的数据结构有个，一个是elevator_type,一个是elevator_queue，前者对应一个调度器类型，后者对应一个调度器实例，也就说如果内核中只有上述四种类型的调度器，则只有四个elevator_type，但是多个块设备(分区)可拥有多个相应分配器的实例，也就是elevator_queue。两个数据结构中最关键的元素都是struct elevator_ops，该结构定义了一组操作函数，用来描述请求队列的相关算法，实现对请求的处理。

struct elevator_type
{
	struct list_head list;
	struct elevator_ops ops;
	struct elv_fs_entry *elevator_attrs;
	char elevator_name[ELV_NAME_MAX];
	struct module *elevator_owner;
};

struct elevator_queue
{
	struct elevator_ops *ops;
	void *elevator_data;
	struct kobject kobj;
	struct elevator_type *elevator_type;
	struct mutex sysfs_lock;
	struct hlist_head *hash;
};

函数elevator_init()用来为请求队列分配一个I/O调度器的实例

int elevator_init(struct request_queue *q, char *name)
{
	struct elevator_type *e = NULL;
	struct elevator_queue *eq;
	int ret = 0;
	void *data;

	
	/*初始化请求队列的相关元素*/
	INIT_LIST_HEAD(&q->queue_head);
	q->last_merge = NULL;
	q->end_sector = 0;
	q->boundary_rq = NULL;

	/*下面根据情况在elevator全局链表中来寻找适合的调度器分配给请求队列*/

	if (name) {//如果指定了name,则寻找与name匹配的调度器
		e = elevator_get(name);
		if (!e)
			return -EINVAL;
	}

	//如果没有指定io调度器，并且chosen_elevator存在，则寻找其指定的调度器
	if (!e && *chosen_elevator) {
		e = elevator_get(chosen_elevator);
		if (!e)
			printk(KERN_ERR "I/O scheduler %s not found\n",
							chosen_elevator);
	}
	
	//依然没获取到调度器的话则使用默认配置的调度器
	if (!e) {
		e = elevator_get(CONFIG_DEFAULT_IOSCHED);
		if (!e) {//获取失败则使用最简单的noop调度器
			printk(KERN_ERR
				"Default I/O scheduler not found. " \
				"Using noop.\n");
			e = elevator_get("noop");
		}
	}

	//分配并初始化elevator_queue
	eq = elevator_alloc(q, e);
	if (!eq)
		return -ENOMEM;

	//调用ops中的elevator_init_fn函数，针对调度器的队列进行初始化
	data = elevator_init_queue(q, eq);
	if (!data) {
		kobject_put(&eq->kobj);
		return -ENOMEM;
	}

	//建立数据结构的关系
	elevator_attach(q, eq, data);
	return ret;
}

所有的I/O调度器类型都会通过链表链接起来(通过struct elevator_type中的list元素)，elevator_get()函数便是通过给定的name，在链表中寻找与name匹配的调度器类型。当确定了I/O调度器的类型后，便要通过elevator_alloc()为等待队列分配一个调度器的实例--struct elevator_queue,并进行初始化；其后，由于每个调度器根据自身算法的不同，都会拥有不同的队列结构，在elevator_init_queue()中会调用特定于调度器的初始化函数针对这些队列进行初始化，并且返回特定于调度器的数据结构，最后再elevator_attach()中建立相关结构的关系。

static struct elevator_queue *elevator_alloc(struct request_queue *q,
				  struct elevator_type *e)
{
	struct elevator_queue *eq;
	int i;

	//为eq分配内存
	eq = kmalloc_node(sizeof(*eq), GFP_KERNEL | __GFP_ZERO, q->node);
	if (unlikely(!eq))
		goto err;

	//根据之前确定的elevator_type初始化eq
	eq->ops = &e->ops;
	eq->elevator_type = e;
	kobject_init(&eq->kobj, &elv_ktype);
	mutex_init(&eq->sysfs_lock);

	//分配elevator的哈希表内存
	eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
					GFP_KERNEL, q->node);
	if (!eq->hash)
		goto err;

	//初始化哈希表
	for (i = 0; i < ELV_HASH_ENTRIES; i++)
		INIT_HLIST_HEAD(&eq->hash[i]);

	return eq;
err:
	kfree(eq);
	elevator_put(e);
	return NULL;
}

static void *elevator_init_queue(str