Linux文件系统学习:电梯算法简介(13)

  • A+
所属分类:Linux系统

电梯简介

电梯调度算法主要适用于LINUX I/O磁盘请求调度。磁盘结构如下图所示,磁盘主要由盘面和磁头组成。

磁盘每次进读写请求时,需要给磁盘驱动器一个地址,磁盘驱动器根据给定地址计算出相应的扇区,然后将磁头移动到需要访问的扇区,开始进行读写。

读写磁盘时,转动磁头实际上很耗费时间,如果不采用调度策略,磁头直接根据请求进行直接访问,则必定会造成时间的浪费。比如以下这种访问方式,访问序列为 盘面1的10,70,20,30,50,如果顺序访问,则是10-》70,70-》20,20-》30,30-》50,这样磁头实际上转了2圈,势必造成一种浪费。

采用电梯调度策略,访问顺序变成这样10->20->30->50->70,磁头转动一圈就可以满足所有的访问请求,从而节约I/O访问时间,提高效率。

 

理论原理

电梯调度策略实际上提供了一种思路,在进行数据访问的同时,如果有新的请求到来,直接将其按照升序插入到等待队列中。

磁盘每次直接从等待队列中取出相应的逻辑地址,直接进行磁盘访问。当然这种调度策略也存在缺陷,如果在某一块地址区域磁盘访问特别频繁,可能会造成处在等待序列末尾的请求“饥饿”,也就是队尾的请求需要等待很长时间才能满足。

调度策略的本质是一种排序算法,对排序队列的一种操作,这种队列采用链表实现比较容易。

 

# 基础函数梳理

elevator_init
elv_merge
__elv_add_request
elv_next_request/blk_peek_request

 

# 数据结构

struct elevator_type
{
	/* managed by elevator core */
	struct kmem_cache *icq_cache;

	/* fields provided by elevator implementation */
	struct elevator_ops ops;
	size_t icq_size;	/* see iocontext.h */
	size_t icq_align;	/* ditto */
	struct elv_fs_entry *elevator_attrs;
	char elevator_name[ELV_NAME_MAX];
	struct module *elevator_owner;

	/* managed by elevator core */
	char icq_cache_name[ELV_NAME_MAX + 5];	/* elvname + "_io_cq" */
	struct list_head list;
};

 

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_bio_merged_fn *elevator_bio_merged_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_completed_req_fn *elevator_completed_req_fn;

	elevator_request_list_fn *elevator_former_req_fn;
	elevator_request_list_fn *elevator_latter_req_fn;

	elevator_init_icq_fn *elevator_init_icq_fn;	/* see iocontext.h */
	elevator_exit_icq_fn *elevator_exit_icq_fn;	/* ditto */

	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;
	elevator_registered_fn *elevator_registered_fn;
};

 

# 电梯初始化过程

blk_init_queue--》blk_init_queue_node--》blk_init_allocated_queue--》elevator_init

 

 

--- Linux文件系统学习系列笔记 ---

(原创笔记,转载请联系博主授权)

Linux文件系统学习:整体框架图(1)

Linux文件系统学习:初始化过程(2)

Linux文件系统学习:文件read流程分析(3)

Linux文件系统学习:文件read和BIO调度分析(4)

Linux文件系统学习:文件write过程分析(5)

Linux文件系统学习:io调度框架(6)

Linux文件系统学习:io的提交过程(7)

Linux文件系统学习:io的plug过程-启动篇(8)

Linux文件系统学习:io的plug过程-request请求(9)

Linux文件系统学习:io的plug过程-blk_init_queue(10)

Linux文件系统学习:io的plug过程-blk_flush_plug_list的情况(11)

Linux文件系统学习:io的plug过程-queuelist的问题(12)

Linux文件系统学习:电梯算法简介(13)

Linux文件系统学习:电梯算法noop(14)

Linux文件系统学习:电梯算法deadline(15)

 

<欢迎关注微信公众号,第一时间查看最新内容>

神农笔记微信公众号

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:2   其中:访客  1   博主  1

    • 归一真人 归一真人 2

      实操下来还是很多问题不知道如何解决,希望大神赐教!

        • 神农 神农 Admin

          @归一真人 微信号:shennongblog ,或者扫描右侧二维码关注微信公众号,有问题留言,神农君会抽空帮你解决!