磁盘，也就是机械硬盘。由多个盘面以及对应的磁头组成，盘面负责存储数据，磁头负责读写数据。

为了更好的管理存储空间，将盘面的细节抠出来。一个盘面被分成若干同心圆环的磁道，每个磁道被分为若干扇区。扇区就是磁盘读写的基本单位，每次读写都是操控一个扇区，一个扇区大小为512字节。扇区不能太大也不能太小，太大了造成存储碎片的浪费，太小了影响读写时间（因为磁头的移动很浪费时间

一次磁盘的读写分为三步：

  1. 寻道，移动磁头
  2. 旋转，旋转盘面
  3. 数据传输，电磁信号的转化

为了更好的定位，磁盘控制器通过三个参数来操控磁盘：

  1. 柱面(cyl)，从盘片的圆心出发，所有盘片上相等半径的磁道（圆环）在垂直方向上形成一个圆柱体，这就是一个柱面。从整体来看，所有柱面由里到外依次嵌套。移动磁头就是为了定位柱面
  2. 磁头(head)，有了柱面之后要读取柱面上的哪个盘面呢？这就由磁头来定位
  3. 扇区(sec)，盘面上的每个磁道上的每个扇区都有相应的编号，通过这个编号来旋转盘面就可定位到相应的扇区

除了上面三个参数，还需要给磁盘控制器发送另外一个参数缓存位置，告诉磁盘具体读写到内存的哪一块地方

因为是直接跟跟硬件打交道了，操作系统这一块的代码都是由汇编写的，比如说往特定端口传送一个数据。

1
2
3
4
5
6
7
8
9
/* linux0.11/include/io.h */
#define outb(value,port) \
__asm__ ("outb %%al,%%dx"::"a" (value),"d" (port))

#define outb_p(value,port) \
__asm__ ("outb %%al,%%dx\n" \
		"\tjmp 1f\n" \
		"1:\tjmp 1f\n" \
		"1:"::"a" (value),"d" (port))

向磁盘发送命令和数据需要连续的调用outb函数给连续的几个端口（具体是7个）传递数据

在linux0.11中大体上由下面两个函数构成了一个磁盘驱动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* linux0.11/kernel/blk_drv/hd.c */

void do_hd_request(void)
{
    ...hd_out(dev, nsect, sec, head, cyl, WIN_WRITE, &read_intr);
    port_write(HD_DATA,CURRENT->buffer,256);
}

void hd_out(unsigned int drive,unsigned int nsect,unsigned int sect,
		unsigned int head,unsigned int cyl,unsigned int cmd,
		void (*intr_addr)(void))
{
	...
	port=HD_DATA; /* 数据寄存器端口(0x1f0) */
	outb_p(hd_info[drive].wpcom>>2,++port);
	outb_p(nsect,++port);
	outb_p(sect,++port);
	outb_p(cyl,++port);
	outb_p(cyl>>8,++port);
	outb_p(0xA0|(drive<<4)|head,++port);
	outb(cmd,++port);
}

do_hd_request()函数负责接收传输请求，计算参数，传递参数调用hd_out。hd_out()函数负责接收参数，用outb向端口发送数据

磁盘控制器通过三个参数，三维编址的方式来定位扇区。Linux为了简化接口，将磁盘上的扇区进行统一编址，将三维编址转为了一维编址。

具体是怎么编址的呢。从0号盘面的0号磁道上的0号扇区开始编址为0，然后沿着磁道逐步递增，将当前磁道填满。转了一圈后，磁头又回到了原位，此时下一个编址的扇区不是当前盘面的下一磁道，因为这会导致磁头的移到造成时间上的浪费。这时可以将下一个编址扇区定位在下一个盘面上同一柱面上的磁道，这样子读取下一个扇区连磁头都不需要移动了。

所以整体的编址思路就是先将柱面填满，再填满定位扇区上面的磁道，再定位扇区

于是一个扇区的编址便有了具体的计算公式：C * (Heads * Sectors) + H * Sectors + S

其中Heads和Sectors对应一个磁盘的磁头数和一个磁道上的扇区数。这是一个磁盘的固定参数。

磁盘驱动的一个大作用就是翻译一个用户传递的扇区编址，将其转为三个定位参数

为了提高传输效率，Linux提出了**盘块(block)**的概念，其实也没什么，就是将连续的几个扇区定义为一个盘块，对上层的用户提供的接口也是以盘块为单位，这样对用户来说读写的基本单位就是一个盘块，但是对硬件来说读写的基本单位仍然是扇区。那么为什么提出这个概念呢？

磁盘访问时间 = 写入控制器时间 + 寻道时间 + 旋转时间 + 传输时间

其中，占据主要因素的是寻道时间和寻转时间

如果，此时计算机有很多的进程正在运行，每个进程都会涉及磁盘的访问。每个进程所要访问磁盘的地址可能会是非常离散的，又因为进程的调度缘故，使得磁盘每次读写时都会让磁头移来移去，这在目前阶段来说是无法避免的。但是如果让磁盘在每次移动后都多读写几个扇区，这样的话单位时间内传输的数据不久增加了吗。每次多读几个扇区就对应于读一个盘块。比如在没有盘块前，读写速率为100K/秒，有了盘块后，每次读写速率就变成了40M/秒。这就是盘块的原因。

但是盘块的大小不能太大，因为每次的读写单位是一个盘块，如果盘块太大就会造化过大的存储碎片，空间利用率就下降了。

因为Linux采用了盘块，所以上面的公式就变成了block = C * (Heads * Sectors) + H * Sectors + S，在作用于具体的扇区时只要将block * nsect就可以得到一维编址的扇区号，nsect是一个盘块有多少个扇区

那么linux0.11的盘块是多大呢，在make_request()中

1
2
3
4
5
6
7
8
9
/* linux0.11/kernel/blk_drv/hd.c */
static void make_request()
{
    ...
    struct request* req;
    req = request + NR_REQUEST;
    req->sector = bh->b_blocknr << 1; /* 这里可以看出盘块的大小是2个扇区 */
    add_reqeuest(major + blk_dev, req);
}

这个函数应该是操作系统提供给用户的接口，让用户能够发出访问磁盘的申请。磁盘驱动的作用就是从请求队列中取出进程发出的请求，解析请求，发出outb指令。

多个进程使用磁盘肯定要进行管理，这就需要请求队列。磁盘每次完成任务后就会发出中断，CPU每执行完一条指令就会检查中断，然后应该是去执行磁盘驱动程序，磁盘驱动程序就会处理请求队列中的请求。所以如何维护这个请求队列就是接下来要讲的调度算法。需要注意的是这里的队列说是队列，但在具体处理的时候并不遵循先进先出。

一开始想到的算法就是先来先服务算法(FCFS)，这个算法最简单最公平，但是缺点也很明显，因为毫无规律，磁头跟没头苍蝇一样移来移去，造成时间上的严重浪费

在FCFS算法的基础上，可以在一个节点跳到另一个节点的过程中将中间节点处理掉，于是有了短寻道优先算法(Shortest-seek-time First)。这个算法比起上一个算法大大减少了磁头移动的次数。但是仍然有个大缺点就是，从概率上来说，节点出现在中间的概率会非常大，而进程是源源不断得发出请求，这就造成驱动程序可能会一直服务中间节点，无法顾及两端节点，造成饥饿。

在短寻道优先算法(SSTF)的基础上继续改进，有了扫描调度算法(SCAN)。SSTF+中途不回折：每个请求都有处理机会。这个算法的思路就是，先不管离得近的高节点，先处理离的近的低节点，然后慢慢往0节点靠；到了0节点**（不管0节点有没有请求，都要到0节点才行，这是规定）后再处理离得最近的高节点，然后慢慢往最高节点靠，到了最高节点（不管最高节点有没有请求，都要到最高节点才行，这是规定）**后再往离得近点低节点靠。如此循环往复，就跟电梯一样。但是这个算法仍有缺点，如果在算法处理的过程中，中间突然有节点突然插进来，那么算法就会优先处理这个插进来的节点，中间的请求还是占便宜了。总结来说，这个算法就是没有回头路，在到达指定节点前不会回头。

题外篇，LOOK算法，没什么好说的，就是扫描调度算法去掉了必须到达0节点和最高节点才能掉头的规定。如果已经到达申请的最低节点或者最高节点就可以掉头了。

最终有了电梯算法(C-SCAN)，跟上面的思路差不多。慢慢先往0节点靠，但是到达最低节点后不是先处理离得最近的高节点，而是直接移动到最高节点，先处理最高节点，然后在往最低节点靠的过程中处理中间节点；在往高节点靠的过程也是这样，到达最高节点后直接移动到0节点，如此循环。这样先处理两端再解决中间的算法就是所谓的电梯算法。此外，因为磁头从最低点复位到最高点这样命令的执行是很快的，所以还是很好的。这个算法是基于扫描调度算法的不是LOOK算法，所以规定了必须走到0节点或者最高节点。

然后就是C-LOOK算法，没什么好说的，就是基于电梯算法去掉了必须到达0节点和最高节点才能掉头的规定。

这个算法的具体实现就放在add_request()函数中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* linux0.11/kernel/blk_drv/hd.c */
static void make_request()
{
    ...
    req->sector = bh->b_blocknr << 1; /* 这里可以看出盘块的大小是2个扇区 */
    add_reqeuest(major + blk_dev, req);
}

static void add_request(struct blk_dev_struct * dev, struct request * req)
{
	struct request * tmp = dev->current_request;
	req->next = NULL;
	cli();
	for ( ; tmp->next ; tmp=tmp->next)
		if ( (IN_ORDER(tmp,req) || !IN_ORDER(tmp,tmp->next) ) &&
		    IN_ORDER(req,tmp->next))
			break;
	req->next=tmp->next;
	tmp->next=req;
	sti();
}

/* linux0.11/kernel/blk_drv/blk.h */
#define IN_ORDER(s1,s2) \
(((s1)->dev < (s2)->dev || ((s1)->dev == (s2)->dev && \
(s1)->sector < (s2)->sector)))

add_request()函数将进程发出的请求放在一个全局变量——request队列中。因为这个变量是全局共享的，所以在操作的时候需要关中断（互斥），因为进程的执行依赖进程的时间片，进程时间片的减少由时间中断引起，关了中断后，时间中断不会执行，进程的时间片不会减少，进程的时间片不减少到0，也就不会触发进程的调度。或者说因为时间中断不会触发，中断中因为时间片减少为0触发调度算法的带啊吗也就不会执行。

这个IN_ORDER(s1, s2)比较出来的结果是s1 < s2，比较的是sector的大小，sector = C * (Heads * Sectors) + H * Sectors + S，其实真正比较的是C也就是柱面号的大小

(tmp < req || next <= tmp) && req < next

可以转变成下面两个条件

tmp < req && req < next

next <= tmp && req < next

最后的结果变成

tmp -> req -> next

在linux0.11中的电梯算法与老师描述的不太一样，就是方向不太一样。它是从中间先往高节点慢慢靠，再一下子去到最低节点

第一个条件是很正常，由低节点慢慢向高节点靠的过程中插入req

第二个条件就是，当tmp处于最高节点时，而next处于最低节点时，而且req还比next低，此时应该把最低节点替换为req，让磁头直接从tmp移到req，然后req的下一个目标是next。

最后一种情况应该是上面的条件都不成立，正常跳出for循环时，req应该是最高节点，这时并不让req直接插入队列代替原来的最高点，而是让req接上队列的末尾。

好的，接下来引入文件的概念

上面讲的是Linux对磁盘的两层抽象，第一层抽象：将三维编址变成一维编址，有了统一编址；第二层抽象：将多个扇区定义为盘块，之后对磁盘的使用就是通过盘块号。上面两层抽象叫做 Row Disk 生磁盘 。也就是还不够符合用户的直观想法。

从而有了第三层抽象——文件，从此叫做 Cookied Disk

在用户眼里，文件就是一串字符流，比如一个源文件test.c。但是在磁盘的角度来看，文件就是一个个盘块。所以，操作系统的工作就是将用户对字符流的修改映射到对盘块的修改。从这点来看，操作系统真的是衔接软件和硬件的桥梁，磁盘只负责存储数据，但是将数据存储在什么地方，以什么样的方式存储，这就不是它要操心的了，这是操作系统的工作。

那么操作系统该如何维护这种映射，以及如何存储数据呢？

最直接的想法是将文件按顺序在磁盘中一块一块连续存储。这样只需要在test.c的FCB（文件控制块）中存储该文件的文件名，起始块和块数就行了。这样的话，只需要计算出要修改的字符在字符流中的位置然后取余一定的数值就可以计算出相应的逻辑盘块号，然后加上起始块就行。

比如说，我要修改test.c文件的200-212行，而每100行就占据一个盘块。这样可以计算出200行的逻辑盘块号为 200 % 100 = 2，再加上该文件的物理起始块号比如 6，就可以得出 200 行所在的物理盘块号为 6+2 = 8，最后把我们计算出的盘块放到上面讲的申请队列就可以了。

这样的连续存储的方式很方便，缺点也很明显，不利于文件的缩减和扩增，因为这会挤到旁边的文件。

既然数组的方式不行，于是有了链表的方式。

就跟传统链表，在每个盘块号的结尾放上指向下一个盘快号的指针就行。FCB只需要记录起始块号就可以按着链表慢慢找下去了。优点很明显，利于盘块的插入和删除。但是缺点就是每次查找的时间复杂度为 O(n)

最终想出来的就是索引结构，结合了数组和链表。inode的i就是索引index 的意思，而node指代的就是FCB。

具体是什么意思呢。管理一个文件，首先有一个总的管理盘块，这个管理盘块叫做索引块，其实就是一个索引表，它就像一个数组一样，记录下每个逻辑盘块号所指向的物理盘块号。然后FCB只需要存储文件的索引块就可以通过索引块中的指向找到想要的逻辑盘块对应的物理盘块。

其实对磁盘的存储管理可以借鉴像内存管理的多级页表那样，在磁盘中建立多级索引。

对于小文件，可以直接从索引块中找到对应的物理块。

对于中文件，可以使用一级索引表。

对于大文件，可以使用二级索引。

以文件的的形式使用磁盘又是如何实现的

首先先来看一下

1
2
3
4
5
6
7
8
9
10
11
/* linux0.11/fs/read_wirte.c */

int sys_write(int fd, const char* buf, int count)
{
    struct file* file;
    struct m_inode* inode;
    file = current->filp[fd];
    inode = file->inode;
    if (S_ISREG(inode->i_mode))
        return file_write(inode, file, buf, count);
}

用户通过系统调用函数write进入这个函数，然后开启磁盘的读写。

从这里看出，用户只需要提供文件描述符、缓冲区内存地址、要读写的字节数

然后sys_write()会根据文件描述符，从filp中获取到文件指针file，再通过文件指针获取到inode，也就是FCB。最后一并传给file_write()函数

有了要读写的缓冲区，和要读写的大小，但是具体是文件的哪个位置呢。这个信息存储在file中的读写指针。

1
2
3
4
5
6
7
8
typedef long off_t;
struct file {
	unsigned short f_mode;
	unsigned short f_flags;
	unsigned short f_count;
	struct m_inode * f_inode;
	off_t f_pos; /* 读写指针 */
};

我们可以把一个文件看作一个有头没有尾的字节数组，对文件的修改就是对这个字节数组修改，而这个f_pos读写指针就是这个数组的索引，指向哪就从哪里开始修改。刚开始file被创建时，f_pos会被初始化为0。

inode结构中的i_zone[]就是逻辑块号到物理块好的映射。其中

i_zone[0-6]是直接表示逻辑块号到物理块号的映射

i_zone[7]是一级索引表

i_zone[8]是二级索引表

由此可以看出，对于Linux0.11存储的文件所占据的磁盘最大为 7 + 512 + 512*512 = 262663个盘块，也就是262663KB = 256MB