Linux I/O Scheduler--Noop

       每个块设备或者块设备的分区，都对应有自身的请求队列(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(struct request_queue *q,
				 struct elevator_queue *eq)
{
	return eq->ops->elevator_init_fn(q);
}

 

static void elevator_attach(struct request_queue *q, struct elevator_queue *eq,
			   void *data)
{
	q->elevator = eq;
	eq->elevator_data = data;
}

下面就来看一下elevator_ops中定义了哪些操作

struct elevator_ops
{
	elevator_merge_fn *elevator_merge_fn;
	elevator_merged_fn *elevator_merged_fn;
	elevator_merge_req_fn *elevator_merge_req_fn;
	elevator_allow_merge_fn *elevator_allow_merge_fn;

	elevator_dispatch_fn *elevator_dispatch_fn;
	elevator_add_req_fn *elevator_add_req_fn;
	elevator_activate_req_fn *elevator_activate_req_fn;
	elevator_deactivate_req_fn *elevator_deactivate_req_fn;

	elevator_queue_empty_fn *elevator_queue_empty_fn;
	elevator_completed_req_fn *elevator_completed_req_fn;

	elevator_request_list_fn *elevator_former_req_fn;
	elevator_request_list_fn *elevator_latter_req_fn;

	elevator_set_req_fn *elevator_set_req_fn;
	elevator_put_req_fn *elevator_put_req_fn;

	elevator_may_queue_fn *elevator_may_queue_fn;

	elevator_init_fn *elevator_init_fn;
	elevator_exit_fn *elevator_exit_fn;
	void (*trim)(struct io_context *);
};

我们这里只关注几个主要的操作函数，其中前面加了*号的表示这些函数是每个调度器都必须实现的

elevator_merge_fn查询一个request，用于将bio并入

elevator_merge_req_fn将两个合并后的请求中多余的那个给删除

*elevator_dispatch_fn将调度器的队列最前面的元素取出，分派给request_queue中的请求队列以等候响应*

*elevator_add_req_fn将一个新的request添加进调度器的队列

elevator_queue_empty_fn检查调度器的队列是否为空

elevator_set_req_fn和elevator_put_req_fn分别在创建新请求和将请求所占的空间释放到内存时调用

*elevator_init_fn用于初始化调度器实例

一个请求在创建到销毁的过程遵循下面三种流程

 set_req_fn ->
 i.   add_req_fn -> (merged_fn ->)* -> dispatch_fn -> activate_req_fn -> (deactivate_req_fn -> activate_req_fn ->)* -> completed_req_fn

ii.  add_req_fn -> (merged_fn ->)* -> merge_req_fn
 iii. [none]
 -> put_req_fn

我们在分析调度器的实现时，不妨也以此为依据，选择i或者ii来作为分析的流程。

Noop调度器十分简单，其只拥有一个等待队列，每当来一个新的请求，仅仅是按先来先处理的思路将请求插入到等待队列的尾部。Noop调度器的定义如下：

static struct elevator_type elevator_noop = {
	.ops = {
		.elevator_merge_req_fn		= noop_merged_requests,
		.elevator_dispatch_fn		= noop_dispatch,
		.elevator_add_req_fn		= noop_add_request,
		.elevator_queue_empty_fn	= noop_queue_empty,
		.elevator_former_req_fn		= noop_former_request,
		.elevator_latter_req_fn		= noop_latter_request,
		.elevator_init_fn		= noop_init_queue,
		.elevator_exit_fn		= noop_exit_queue,
	},
	.elevator_name = "noop",
	.elevator_owner = THIS_MODULE,
};

Noop调度器使用的管理数据：

struct noop_data {
	struct list_head queue;
};

 

先来看noop_init_queue

static void *noop_init_queue(struct request_queue *q)
{
	struct noop_data *nd;

	//为noop调度器使用的数据结构分配内存
	nd = kmalloc_node(sizeof(*nd), GFP_KERNEL, q->node);
	if (!nd)
		return NULL;
	//初始化noop调度器使用的队列
	INIT_LIST_HEAD(&nd->queue);
	return nd;
}

noop_add_request用于将一个请求直接添加到等待队列的尾部

static void noop_add_request(struct request_queue *q, struct request *rq)
{	
	struct noop_data *nd = q->elevator->elevator_data;

	list_add_tail(&rq->queuelist, &nd->queue);
}

noop_merged_requests将合并后多余的那个请求给删除

static void noop_merged_requests(struct request_queue *q, struct request *rq,
				 struct request *next)
{
	list_del_init(&next->queuelist);
}

noop_dispatch将队首的请求分派到request_queue中

static int noop_dispatch(struct request_queue *q, int force)
{
	struct noop_data *nd = q->elevator->elevator_data;

	if (!list_empty(&nd->queue)) {//请求队列不为空
		struct request *rq;
		rq = list_entry(nd->queue.next, struct request, queuelist);//获取队首的请求
		list_del_init(&rq->queuelist);//从队列中删除
		elv_dispatch_sort(q, rq);//将rq插入request_queue
		return 1;
	}
	return 0;
}

 从上面的实现可以看出，Noop调度器只进行了合并，并没有对request进行重排，所以它适用于flash存储器，而不适用于磁盘这样的需要依靠磁头来定位的存储设备。