一、I/O调度器

1.1 数据结构

在将请求提交给块设备时，内核提供了各种调度策略，这些调度器用于重排和调度I/O请求以获得最优的性能。I/O调度器在内核中被称为elevator。内核使用了如下数据结构来实现和管理I/O调度器：

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

• elevator_type用于表示I/O调度器，内核中所有的I/O调度器都被保存在全局链表elv_list中，list用做链表元素。
• icq_cache：icq缓存，由I/O调度器核心创建、维护和使用
• ops：调度器的操作函数集
• icq_size：icq大小
• icq_align：icq对齐方式
• elevator_attrs：该I/O调度器在sys文件系统中的属性文件
• elevator_name：该调度器的名字
• icq_cache_name：icq缓存的名字

I/O调度器的操作函数集定义如下：

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_merge_fn：返回bio应该被添加（合并）到指定的请求的什么位置
• elevator_allow_merge_fn：判断新的bio是否可以和指定的请求合并，即添加到一个已存的请求中，它和elevator_merge_fn的功能可能在一个函数中提供，具体的要看调度器的实现。
• elevator_merged_fn：在将两个请求进行合并后调用，用于进行清理，以释放一些管理数据结构
• elevator_merge_req_fn：将两个请求合并为一个请求。当将一个bio合并到一个请求后，被合并到的那个请求可能就可以和它之前或者之后的请求进行合并（是之前还是之后，取决于新的bio添加到请求的方式）。因此在将一个新的bio合并到一个已存的请求之后，就要尝试进行请求的合并。
• elevator_bio_merged_fn：如果提供了，则它在新的bio被添加到一个已存的请求后被调用。bio和请求的合并由bio_attempt_front_merge或者bio_attempt_back_merge处理，而请求的合并由attempt_front_merge或者attempt_back_merge处理
• elevator_dispatch_fn：从调度器取得下一个应该被处理的请求
• elevator_add_req_fn：向调度器添加新的请求
• elevator_activate_req_fn：激活请求队列上的请一个求
• elevator_deactivate_req_fn：deactivate请求队列上的一个请求
• elevator_completed_req_fn：完成请求队列上一个请求的处理时对该请求调用该函数
• elevator_former_req_fn：获取请求队列上在指定的请求之前的请求
• elevator_latter_req_fn：获取请求队列上在指定的请求之后的请求
• elevator_set_req_fn：创建新的请求时调用，相当于构造函数的一部分。get_request->blk_alloc_request
• elevator_put_req_fn：释放请求时调用，相当于析构函数的一部分.blk_free_request->elv_put_request
• elevator_may_queue_fn：当从请求创建了一个新的请求时被调用，用于判断创建是否能够创建成功以及请求是否应该被排队。调度器可以实现一些限制来控制请求队列上的请求数目，这里就是实现限制检查的地方。
• elevator_init_fn：初始化调度器时调用，即调度器的构造函数
• elevator_exit_fn：删除调度器时调用，即调度器的析构函数

1.2 内核I/O调度器

在初始化请求队列时，内核会用elevator_init来初始化调度器及其关联的调度队列。随后该
内核实现了四种I/O调度器，分别为：

1.2.1 CFQ(Completely Fair Queuing, 完全公平排队)

该调度器是默认的调度器。该调度器围绕调度队列进行，内核使用一个轮转算法来处理各个队列，这确保了I/O带宽以公平的方式在各个队列之间进行分配。

1.2.2 Deadline I/O调度器

该调度器适用于两个目地：

•  试图最小化磁盘寻道时间：如果要保证这点就要分析请求，并按照最小寻道时间的要求重排请求。
•  尽可能保证请求在一定的时间内完成：如果要用于该目地，就要使用定时机制保证请求的到期时间

1.2.3 NOOP调度器

该调度器就是一个FIFO形式的调度器。请求被以先来先服务的形式入队。请求可以合并但是无法重排。

1.2.4 AS调度器(预测I/O调度程序)

它会对应用程序的读写进行预测以获得最优性能。它假设应用程序的读写请求不是孤立的，简单的说如果应用程序提交了一个读请求，则它认为下一个请求也是读，从而进行优化（当然这只是一个简单的说明，实际的预测要复杂的多）。

1.3 修改调度器

如果要修改系统默认的调度器，可以通过设置启动参数elevator=调度器名字来修改。如果只是要临时修改某个设备的调度器，可以通过sys文件系统下该设备目录中的queue目录中的scheduler文件来实现，把自己希望使用的调度器的名字写入该文件即可。比如：

root@rover-OptiPlex-780:/sys/block/sda/queue# cat scheduler 
noop [deadline] cfq 
root@rover-OptiPlex-780:/sys/block/sda/queue# echo cfq >  /sys/block/sda/queue/scheduler
root@rover-OptiPlex-780:/sys/block/sda/queue# cat /sys/block/sda/queue/scheduler
noop deadline [cfq] 

二、请求队列管理

请求队列的管理对于块层是很重要的，其中涉及到很多管理请求队列的API。做一下简单的总结。

2.1 创建和删除队列

struct request_queue *blk_init_queue(request_fn_proc *rfn, spinlock_t *lock)
void blk_cleanup_queue(struct request_queue *q)

这两个API分别用来创建和删除请求队列

2.2 请求队列中请求管理API

当驱动处理请求时自然的就需要和请求队列交互以获得请求。相关API包括：

struct request *blk_fetch_request(struct request_queue *q);

用于获取请求

void blk_complete_request(struct request *);

用于在处理完一个请求时调用。

void blk_abort_request(struct request *);

取消一个请求

void blk_requeue_request(struct request_queue *, struct request *);

重新将一个请求添加到请求队列中

2.3 请求队列的请求队列管理API

void blk_start_queue(struct request_queue *q);
void blk_stop_queue(struct request_queue *q);
void blk_run_queue(struct request_queue *);

这三个API分别用于启动请求队列，停止请求队列，执行一个请求队列。
void blk_queue_segment_boundary(struct request_queue *q, unsigned long mask)；
如果一个设备无法处理跨越某个边界的段，就用该函数设置其边界，mask是个边界掩码，比如0xffffffff表示无法跨越4M边界。

块层提供了丰富的队列相关的API，具体的可以参考文件(include/linux/blkdev.h)。

三、文件系统与块设备的关系

在linux中一切皆文件，linux将所有设备也都当做一个文件来处理。这里简单梳理下二者的关系

3.1 文件系统的简单概述

Linux文件系统使用索引节点来记录文件信息，索引节点是一个数据结构，它包含了一个文件的文件名，位置，大小，建立或修改时间，访问权限，所属关系等文件控制信息，一个文件系统维护了一个索引节点的数组，每个文件或目录都与索引结点数组中的唯一一个元素对应，系统为每个索引结点分配了一个号码，也就是该结点在数组中的索引号，称为索引结点号。
Linux文件系统将文件索引结点号和文件名同时保存在目录中，所以目录只是将文件的名称和它的索引结点号结合在一起的一张表。

3.2 磁盘块的组织

在linux中磁盘块由四个部分组成，分别为引导块 、专用块 、 i节点表块 和数据存储块。
Linux系统中的每个文件都被赋予一个唯一的数值，这个数值称做索引节点。索引节点存储在一个称作索引节点表＜ inode table＞中，该表在磁盘格式化时被分配。每个实际的磁盘或分区都有其自己的索引节点表。一个索引节点包含文件的所有信息，包括磁盘上数据的地址和文件类型。文件类型包括如普通文件、目录和特殊文件这样的信息。
linux硬盘组织方式为:引导区、超级块（superblock)，索引结点（inode)，数据块（datablock)，目录块（diredtory block)。其中超级块中包含了关于该硬盘或分区上的文件系统的整体信息，如文件系统的大小等；超级块后面的数据结构是索引结点，它包含了针对某一个具体文件的几乎全部信息，如文件的存取权限、所有者、大小、建立时间以及对应的目录块和数据块等；数据块是真正存储文件内容的位置。但是索引结点中不包括文件的名字，文件名是放在目录块里的。目录块里包含有文件的名字以及此文件的索引结点编号。