Linux IO SchedulerNoop.docx
- 文档编号:12853132
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:12
- 大小:18.89KB
Linux IO SchedulerNoop.docx
《Linux IO SchedulerNoop.docx》由会员分享,可在线阅读,更多相关《Linux IO SchedulerNoop.docx(12页珍藏版)》请在冰点文库上搜索。
LinuxIOSchedulerNoop
LinuxI/OScheduler--Noop
分类:
Linux驱动程序2012-12-1021:
24 2437人阅读 评论
(2) 收藏 举报
每个块设备或者块设备的分区,都对应有自身的请求队列(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。
两个数据结构中最关键的元素都是structelevator_ops,该结构定义了一组操作函数,用来描述请求队列的相关算法,实现对请求的处理。
[cpp] viewplaincopy
1.struct elevator_type
2.{
3. struct list_head list;
4. struct elevator_ops ops;
5. struct elv_fs_entry *elevator_attrs;
6. char elevator_name[ELV_NAME_MAX];
7. struct module *elevator_owner;
8.};
[cpp] viewplaincopy
1.struct elevator_queue
2.{
3. struct elevator_ops *ops;
4. void *elevator_data;
5. struct kobject kobj;
6. struct elevator_type *elevator_type;
7. struct mutex sysfs_lock;
8. struct hlist_head *hash;
9.};
函数elevator_init()用来为请求队列分配一个I/O调度器的实例
[cpp] viewplaincopy
1.int elevator_init(struct request_queue *q, char *name)
2.{
3. struct elevator_type *e = NULL;
4. struct elevator_queue *eq;
5. int ret = 0;
6. void *data;
7.
8.
9. /*初始化请求队列的相关元素*/
10. INIT_LIST_HEAD(&q->queue_head);
11. q->last_merge = NULL;
12. q->end_sector = 0;
13. q->boundary_rq = NULL;
14.
15. /*下面根据情况在elevator全局链表中来寻找适合的调度器分配给请求队列*/
16.
17. if (name) {//如果指定了name,则寻找与name匹配的调度器
18. e = elevator_get(name);
19. if (!
e)
20. return -EINVAL;
21. }
22.
23. //如果没有指定io调度器,并且chosen_elevator存在,则寻找其指定的调度器
24. if (!
e && *chosen_elevator) {
25. e = elevator_get(chosen_elevator);
26. if (!
e)
27. printk(KERN_ERR "I/O scheduler %s not found\n",
28. chosen_elevator);
29. }
30.
31. //依然没获取到调度器的话则使用默认配置的调度器
32. if (!
e) {
33. e = elevator_get(CONFIG_DEFAULT_IOSCHED);
34. if (!
e) {//获取失败则使用最简单的noop调度器
35. printk(KERN_ERR
36. "Default I/O scheduler not found. " \
37. "Using noop.\n");
38. e = elevator_get("noop");
39. }
40. }
41.
42. //分配并初始化elevator_queue
43. eq = elevator_alloc(q, e);
44. if (!
eq)
45. return -ENOMEM;
46.
47. //调用ops中的elevator_init_fn函数,针对调度器的队列进行初始化
48. data = elevator_init_queue(q, eq);
49. if (!
data) {
50. kobject_put(&eq->kobj);
51. return -ENOMEM;
52. }
53.
54. //建立数据结构的关系
55. elevator_attach(q, eq, data);
56. return ret;
57.}
所有的I/O调度器类型都会通过链表链接起来(通过structelevator_type中的list元素),elevator_get()函数便是通过给定的name,在链表中寻找与name匹配的调度器类型。
当确定了I/O调度器的类型后,便要通过elevator_alloc()为等待队列分配一个调度器的实例--structelevator_queue,并进行初始化;其后,由于每个调度器根据自身算法的不同,都会拥有不同的队列结构,在elevator_init_queue()中会调用特定于调度器的初始化函数针对这些队列进行初始化,并且返回特定于调度器的数据结构,最后再elevator_attach()中建立相关结构的关系。
[cpp] viewplaincopy
1.static struct elevator_queue *elevator_alloc(struct request_queue *q,
2. struct elevator_type *e)
3.{
4. struct elevator_queue *eq;
5. int i;
6.
7. //为eq分配内存
8. eq = kmalloc_node(sizeof(*eq), GFP_KERNEL | __GFP_ZERO, q->node);
9. if (unlikely(!
eq))
10. goto err;
11.
12. //根据之前确定的elevator_type初始化eq
13. eq->ops = &e->ops;
14. eq->elevator_type = e;
15. kobject_init(&eq->kobj, &elv_ktype);
16. mutex_init(&eq->sysfs_lock);
17.
18. //分配elevator的哈希表内存
19. eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
20. GFP_KERNEL, q->node);
21. if (!
eq->hash)
22. goto err;
23.
24. //初始化哈希表
25. for (i = 0; i < ELV_HASH_ENTRIES; i++)
26. INIT_HLIST_HEAD(&eq->hash[i]);
27.
28. return eq;
29.err:
30. kfree(eq);
31. elevator_put(e);
32. return NULL;
33.}
[cpp] viewplaincopy
1. 12px;">static void *elevator_init_queue(struct request_queue *q, 2. struct elevator_queue *eq) 3.{ 4. return eq->ops->elevator_init_fn(q); 5.}
[cpp] viewplaincopy
1. 12px;">static void elevator_attach(struct request_queue *q, struct elevator_queue *eq, 2. void *data) 3.{ 4. q->elevator = eq; 5. eq->elevator_data = data; 6.}
下面就来看一下elevator_ops中定义了哪些操作
[cpp] viewplaincopy
1. 12px;">struct elevator_ops 2.{ 3. elevator_merge_fn *elevator_merge_fn; 4. elevator_merged_fn *elevator_merged_fn; 5. elevator_merge_req_fn *elevator_merge_req_fn; 6. elevator_allow_merge_fn *elevator_allow_merge_fn; 7. 8. elevator_dispatch_fn *elevator_dispatch_fn; 9. elevator_add_req_fn *elevator_add_req_fn; 10. elevator_activate_req_fn *elevator_activate_req_fn; 11. elevator_deactivate_req_fn *elevator_deactivate_req_fn; 12. 13. elevator_queue_empty_fn *elevator_queue_empty_fn; 14. elevator_completed_req_fn *elevator_completed_req_fn; 15. 16. elevator_request_list_fn *elevator_former_req_fn; 17. elevator_request_list_fn *elevator_latter_req_fn; 18. 19. elevator_set_req_fn *elevator_set_req_fn; 20. elevator_put_req_fn *elevator_put_req_fn; 21. 22. elevator_may_queue_fn *elevator_may_queue_fn; 23. 24. elevator_init_fn *elevator_init_fn; 25. elevator_exit_fn *elevator_exit_fn; 26. void (*trim)(struct io_context *); 27.}; 28.
我们这里只关注几个主要的操作函数,其中前面加了*号的表示这些函数是每个调度器都必须实现的
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调度器的定义如下:
[cpp] viewplaincopy
1. 12px;">static struct elevator_type elevator_noop = { 2. .ops = { 3. .elevator_merge_req_fn = noop_merged_requests, 4. .elevator_dispatch_fn = noop_dispatch, 5. .elevator_add_req_fn = noop_add_request, 6. .elevator_queue_empty_fn = noop_queue_empty, 7. .elevator_former_req_fn = noop_former_request, 8. .elevator_latter_req_fn = noop_latter_request, 9. .elevator_init_fn = noop_init_queue, 10. .elevator_exit_fn = noop_exit_queue, 11. }, 12. .elevator_name = "noop", 13. .elevator_owner = THIS_MODULE, 14.};
Noop调度器使用的管理数据:
[cpp] viewplaincopy
1. 12px;">struct noop_data { 2. struct list_head queue; 3.}; 4.
先来看noop_init_queue
[cpp] viewplaincopy
1. 12px;">static void *noop_init_queue(struct request_queue *q) 2.{ 3. struct noop_data *nd; 4. 5. //为noop调度器使用的数据结构分配内存 6. nd = kmalloc_node(sizeof(*nd), GFP_KERNEL, q->node); 7. if (! nd) 8. return NULL; 9. //初始化noop调度器使用的队列 10. INIT_LIST_HEAD(&nd->queue); 11. return nd; 12.}
noop_add_request用于将一个请求直接添加到等待队列的尾部
[cpp] viewplaincopy
1. 12px;">static void noop_add_request(struct request_queue *q, struct request *rq) 2.{ 3. struct noop_data *nd = q->elevator->elevator_data; 4. 5. list_add_tail(&rq->queuelist, &nd->queue); 6.}
noop_merged_requests将合并后多余的那个请求给删除
[cpp] viewplaincopy
1. 12px;">static void noop_merged_requests(struct request_queue *q, struct request *rq, 2. struct request *next) 3.{ 4. list_del_init(&next->queuelist); 5.}
noop_dispatch将队首的请求分派到request_queue中
[cpp] viewplaincopy
1. 12px;">static int noop_dispatch(struct request_queue *q, int force) 2.{ 3. struct noop_data *nd = q->elevator->elevator_data; 4. 5. if (! list_empty(&nd->queue)) {//请求队列不为空 6. struct request *rq; 7. rq = list_entry(nd->queue.next, struct request, queuelist);//获取队首的请求 8. list_del_init(&rq->queuelist);//从队列中删除 9. elv_dispatch_sort(q, rq);//将rq插入request_queue 10. return 1; 11. } 12. return 0; 13.} 14.
从上面的实现可以看出,Noop调度器只进行了合并,并没有对request进行重排,所以它适用于flash存储器,而不适用于磁盘这样的需要依靠磁头来定位的存储设备。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Linux IO SchedulerNoop