磁盘的管理(一)

前言

磁盘既是输入设备又是输出设备。输出设备（OutputDevice）是人与计算机交互的一种部件，用于数据的输出。输入设备：向计算机输入数据和信息的设备。

所以，使用磁盘大致上与显示器和键盘一样

在这里插入图片描述

提示：以下是本篇文章正文内容

一、磁盘的介绍

磁盘由一个个盘片组成的磁盘立体结构，一个盘片上下两面都是可读写的

磁盘利用了电流的磁效应，对一些电信号进行磁化，保存在磁盘中，用来表示一些信息。

在这里插入图片描述

硬盘又划分为磁头（Heads）、柱面(Cylinder)、扇区(Sector)

在这里插入图片描述

磁头(Heads)：每张盘面的正反两面各有一个磁头，一个磁头对应一张磁片的一个面。用第几磁头就可以表示数据在哪个磁面

柱面(Cylinder)：所有盘面中半径相同的同心磁道构成“柱面”，这一系列的磁道垂直叠在一起，就形成一个柱面的形状

扇区(Sector)：将磁道划分为若干个小的区段，就是扇区，每个扇区的容量为512字节，大小本质上是对磁盘数据的传输时间和磁盘的碎片浪费这2项参数的折中

在这里插入图片描述

==硬盘容量＝磁头数×柱面数×扇区数×512字节==

结构概况：

在这里插入图片描述

二、生磁盘的使用

1.IO过程简介

==磁盘I/O过程: 控制器–>寻道–>旋转–>传输==

在这里插入图片描述

1.磁头移动到相应的磁道上 2.磁道开始旋转，转到相应的扇区 3.此时再转的时候就是磁生电，磁信号就变成电信号，然后就读取数据 4.读到内存的缓冲区，将这个内存缓冲区修改一个字节 5.然后继续里面再转，此时是电生磁，把字节写到磁道上

==移动磁头，移动到对应的磁道上，然后转动磁道，移动到对应的扇区上，一边旋转一边进行磁生电，电生磁，和内存缓冲区进行数据的交互读和写==

2.直接使用磁盘

只要往控制器中写柱面、磁头、扇区、缓存位置

在这里插入图片描述

假如要往磁盘的某个扇区写一个字节，那么需要知道这个扇区对应的哪个柱面中的哪个磁头把这些参数传到磁盘控制器，磁盘控制器再根据这些参数进行驱动磁盘写数据

(1)磁盘读写的请求函数do_hd_request()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


void do_hd_request(void)
{
	..... 
	//前面一些语句就是要得到dev,nsect,sec,head,cyl，WIN_WRITE,&write_intr数据
	// 传递给磁盘控制器
	if (CURRENT->cmd == WRITE) {
		hd_out(dev,nsect,sec,head,cyl,WIN_WRITE,&write_intr);
		for(i=0 ; i<3000 && !(r=inb_p(HD_STATUS)&DRQ_STAT) ; i++)
			/* nothing */ ;
		if (!r) {
			bad_rw_intr();
			goto repeat;
		}
		port_write(HD_DATA,CURRENT->buffer,256);
	} else if (CURRENT->cmd == READ) {
		hd_out(dev,nsect,sec,head,cyl,WIN_READ,&read_intr);
	} else
		panic("unknown hd-command");
}

(2)磁盘驱动的核心代码hd_out()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


static 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))
{
	register int port asm("dx");

	if (drive>1 || head>15)
		panic("Trying to write bad sector");
	if (!controller_ready())
		panic("HD controller not ready");
	do_hd = intr_addr;
	outb_p(hd_info[drive].ctl,HD_CMD);
	port=HD_DATA; //数据寄存器端口(0x1f0)

	// outb_p接口就是往外设传送数据的
	// cpu中磁盘驱动的核心代码
	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);
}

以上方法需要的传递的参数太多，不够方便

3.盘块号读写磁盘(第一层抽象)

==将柱面、磁头、扇区包装成一个磁盘块==

在这里插入图片描述

磁盘驱动负责从block计算出cyl， head， sec(CHS)

假设扇区的编址如下，(block相邻的盘块可以快速读出)

1号扇区在0号扇区旋转方向的下一扇区，假设一个盘面有六个扇区，则0-5扇区在第一个盘面，6号扇区在0号扇区竖直方向的下的扇区

在这里插入图片描述

计算公式：block = c * (heads * sectors) + h * sectors + s

Sectors 是每个盘面的扇区数，Heads 是磁盘的磁头数量

扇区号 = 柱面号 × （一个柱面有多少扇区）+ 盘面号 ×（一个盘面有多少扇区）+ 扇区号

==根据扇区号 sector 来算出 C、H、S==

S = sector%Sectors H = sector/Sectors%Heads C = sector/Sectors/Heads

通过编址建立从 C、H、S 扇区地址到扇区号的一个映射，这就是文件系统第一层抽象的中心任务。扇区号连续的多个扇区就是一个磁盘块

磁盘的访问时间

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

(其中主要是寻道时间, 旋转时间长，同时相邻的盘块应能快速读出)

通过磁盘号进行读写磁盘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


static void make_request()
{ 
	struct requset *req;
	req=request+NR_REQUEST;
	req->sector=bh->b_blocknr<<1;
	add_request(major+blk_dev,req); 
}

void do_hd_request(void)
{ 
	unsigned int block=CURRENT->sector;
	__asm__(“divl %4”:”=a”(block),”=d”(sec):”0”(block),
	“1”(0),”r”(hd_info[dev].sect));
	__asm__(“divl %4”:”=a”(cyl),”=d”(head):”0”(block),
	“1”(0),”r”(hd_info[dev].head));
	hd_out(dev,nsect,sec,head,cyl,WIN_WRITE,...);
	... 
}

有了磁盘块，用户发出的磁盘读写请求就是盘块号 blocknr 了，由于磁盘块是连续的多个扇区，可以容易地算出扇区号，即：sector = blocknr × blocksize（ blocksize 是描述磁盘块大小）

4.队列读写磁盘(第二层抽象)

操作系统中一般有多个进程，每个进程都会提出磁盘块访问请求，所以需要用队列来管理访问请求，这就是操作系统对磁盘管理的第二层抽象

在这里插入图片描述多个磁盘访问请求出现在请求队列，需要对磁盘进行调度

调度目标：平均延迟小调度算法：

(1)FCFS磁盘调度算法

最直观最公平的调度

在这里插入图片描述

(2)SSTF磁盘调度

在移动过程中把经过的请求处理(Shortest-seek-time First)

在这里插入图片描述

(3)SCAN磁盘调度

SSTF+中途不回折：每个请求都有处理机会

在这里插入图片描述

(4)C-SCAN磁盘调度(电梯算法)

SCAN+直接移到另一端：两端请求都能很快处理

在这里插入图片描述

这借鉴了生活中电梯的模型，电梯在运行的时候有上升和下降2种情况，当电梯上升时，本次上升的终点就是最高的请求楼层; 当电梯下降时，本次下降的终点就是最低的请求楼层

IN_ORDER()

1
2
3
4
5
6
7
8
9


// 核心思想是比较s1与s2中的sector大小
// 也就是比较s1与s2中的柱面号的大小
// 因为柱面的寻找是耗时最长的，所以要保证
// 寻找柱面也即寻道的时间不能太长，就要在
// 寻道上面做优化处理
#define IN_ORDER(s1,s2) 
((s1)->cmd<(s2)->cmd || ((s1)->cmd==(s2)->cmd && 
((s1)->dev < (s2)->dev || ((s1)->dev == (s2)->dev && 
(s1)->sector < (s2)->sector))))

知道了IN_ORDER()的作用，可以分析一下电梯算法

 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
27
28
29
30
31
32


// linux-0.11/kernel/blk_drv/ll_rw_blk.c
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
	struct request * tmp;

	req->next = NULL;
	cli();   // 开启临界区保护
	if (req->bh)
		req->bh->b_dirt = 0;
	if (!(tmp = dev->current_request)) {
		dev->current_request = req;
		sti();
		(dev->request_fn)();
		return;
	}
	//当符合这两种情况时就跳出循环
	// 并将req插入tmp和next之间
	//(1)当tmp的柱面号小于req的柱面号，且req小于next的柱面号(电梯上升)
	//(2)当tmp的柱面号小于next的柱面号，且req小于next的柱面号(电梯下降)
	// 不管这两种任何一种情况，
	// 下一步磁盘读写都会进入req这个对象上
	//否则就按照原有的,队列进行磁盘读写
	//这样就能更高效的使用磁盘
	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();
}

在这里插入图片描述

总结

小结：==生磁盘(raw disk)写过程==

在这里插入图片描述

磁盘的管理(二)

前言

如果让普通用户使用生磁盘(raw disk)，许多人连扇区都不知道是什么?要求他们根据盘块号来访问磁盘…这是不可能的。所以，需要在盘块上引入更高一层次的抽象概念—文件

一、磁盘文件

==磁盘使用的第三层抽象——文件，文件是一个连续的字符流==

用户可以在字符流上随意操作，操作系统会根据==映射表找到和字符流位置对应的磁盘块号==，操作系统完成了从磁盘块到字符流的映射。

实现文件抽象的关键就在于能根据字符流位置找到对应的盘块号，即字符流和盘块号之间的映射关系，==文件: 建立字符流到盘块集合的映射关系==

1.顺序存储结构

文件使用顺序结构储存在磁盘上，==文件的FCB(文件控制块)存储该文件的起始块号(第一个)，和块数==，根据这个就能知道对应的字符在那个盘块

在这里插入图片描述

若盘块的大小为100，则文件中200-212对应在盘块8

但是，用顺序存储的结构适合文件的直接读写，不适合文件的动态增长，与数组一样，不方便插入元素

2.链式存储结构

链式存储结构：操作系统在 FCB 中需要存放的主要映射信息是==第一个磁盘块的盘块号==，利用这个信息可以找到文件的第一个磁盘块，再利用每个磁盘块中存放的下一个盘块号的指针，可以找到第二个磁盘块……

在这里插入图片描述若盘块的大小为100，则文件中200-212对应在盘块9

3.索引存储结构

索引存储结构：文件字符流被分割成多个逻辑块，在物理磁盘上寻找一些空闲物理盘块（无需连续）将这些逻辑块的内容存放进去，再找一个磁盘块作为索引块，其中按序存放各个逻辑块对应的物理磁盘块号(索引块来记录文件使用的盘块号) 在这里插入图片描述

索引结构指一个文件的信息存放在若干不连续的物理块中，系统为每个文件建立一个专用的数据结构——索引表，并将这些块的块号存放在索引表中。

优点是保留了链接结构的优点，同时解决了其缺点，即能顺序存取，又能随机存取，满足了文件动态增长，插入删除的需求，也能充分利用外存空间

缺点是索引表本身带来一定的系统开销

==多级索引：== 在这里插入图片描述

优点：

1.可以表示很大的文件 2.很小的文件高效访问 3.中等大小的文件访问速度也不慢

二、文件读取磁盘(第三层抽象)

通过文件对磁盘进行读写

1
2
3
4
5
6
7
8


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

既然对文件操作就要调用sys_write(),参数：fd文件描述符，buf内存缓冲区，count读写字符的个数在这里插入图片描述

根据文件信息 inode 对应的不是字符设备，而是常规文件，跳到 file_write() 去执行

file_write()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int file_write(struct m_inode *inode, struct file *filp, char *buf, int count)
{ 
	off_t pos;
	if(filp->f_flags&O_APPEND)//如果是追加，从文末开始
	pos=inode->i_size; else pos=filp->f_pos;
	.....
	while(i<count)
	{
		block=create_block(inode, pos/BLOCK_SIZE);//算出对应的块
		bh=bread(inode->i_dev, block);//发送请求，放入“电梯” 队列!
		int c=pos%BLOCK_SIZE; char *p=c+bh->b_data; //写入数据后，修改修改pos，
		bh->b_dirt=1; c=BLOCK_SIZE-c; pos+=c; // pos指向文件的读写位置(字符流末位置)
		... 
		//一块一块拷贝用户字符， 并且释放写出
		while(c-->0) *(p++)=get_fs_byte(buf++);
		brelse(bh); 
	}
	filp->f_pos=pos; 
}
//pos    先找到 文件的读写位置 （记录在 字段 f_pos 中）
//block  计算物理盘块号
//bread   向磁盘发出请求

工作过程：

1.根据file中的一个==读写指针fseek（文件的当前读写位置）及 count 找到文件读写对应的字符流位置==

2.根据字符流上的读写位置算出逻辑块号 ,==由inode 找到物理盘块号==

3.==用磁盘号，buf等形成request放入请求队列(“电梯”)==，就可以读写磁盘

==create_block()计算盘号，文件抽象的核心==

在这里插入图片描述这里采用的多级索引 block:(0-6):直接数据块（直接索引）， (7):一重间接， (8):二重间接

如果逻辑盘块号小于等于 6，说明 inode中的直接数据块就能映射出盘块号若这个逻辑盘块没有映射到物理盘块，就调用 new_block() 从磁盘上申请一个空闲物理盘块

block-=7 ， if(block<512) 说明逻辑盘块号对应的物理盘块号存放在一阶间接索引，接下来需要 bread(inode->i_dev,inode->i_zone[7]) 读入这个一阶索引块，接下来需要在这个索引块中寻找和逻辑块相对应的物理盘块号

m_inode结构体

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


struct m_inode{ //读入内存后的inode
	unsigned short i_mode; //文件的类型和属性
	...
	unsigned short i_zone[9]; //指向文件内容数据块
	struct task_struct *i_wait;
	unsigned short i_count;
	unsigned char i_lock;
	unsigned char i_dirt; 
	... 
}

根据inode区分文件的属性和类型

1
2
3
4
5
6
7
8
9


int sys_open(const char* filename, int flag)
{ 
	if(S_ISCHR(inode->i_mode)) //字符设备
	{ 
		if(MAJOR(inode->i_zone[0])==4)  //设备文件
		current->tty=MINOR(inode->i_zone[0]);
	}
	...
}

==如果是普通文件需要根据inode里面的映射表来建立磁盘号到字符流直接的映射==

==如果是特殊文件不需要inode去完成映射，inode存放主设备号(设备文件)==

MAJOR的宏定义

1
2


#define MAJOR(a)(((unsigned)(a))>>8)) //取高字节
#define MINOR(a)((a)&0xff) //取低字节

总结

==文件视图== 在这里插入图片描述

目录与文件系统

前言

文件，抽象一个磁盘块集合，这是第三层抽象，从文件到文件系统：文件系统，抽象整个磁盘（第四层抽象）

一、文件系统

在使用磁盘的时候，用户眼里的磁盘是一堆树结构的有组织的文件，文件系统就是实现文件到盘块的映射

在这里插入图片描述

目录树的优点：在这里插入图片描述

但是有了这样的映射，怎么才能使用 /my/data/a中a文件("/" 表示根目录)?

==通过文件路径名找到文件，也就是先通过文件路径找到文件a的FCB==

因为需要通过比较文件名才能找到文件，所以目录中需要存放子目录的文件名，又还需要在磁盘中操作该文件，因此还需要存子目录的FCB。

但实际上我们只需要比较一个文件名，却读入了大量的FCB，系统效率笔记低，因此可以在目录中存放子目录名+该目录对应的FCB地址。目录里存的就是<文件名：索引值>，实现这一索引结构，需要磁盘配合，==需要磁盘划分一块连续的区域来存放FCB块，这样就能建立索引值到FCB地址的映射==

因为根目录没有上一级目录来保存它的索引值，因此需要在磁盘中找一个固定的地址存放根目录

所以操作系统需要完成以下两个任务：

1.目录中存放子目录的文件名和子目录FCB的索引值 2.磁盘块要划分一段连续的区域专门存放FCB块，并定义一个初始地址作为根目录的索引

磁盘块如下：

(1)inode位图：哪些inode空闲，哪些被占用 (2)盘块位图：哪些盘块是空闲的，硬盘大小不同这个图的大小也不同 (3)引导块：磁盘启动和初始化 (4)超级块：记录两个位图有多大等信息

空闲位图(位向量)：0011110011101 表示：表示磁盘块2、 3、 4、 5、8、 9、 10、 12空闲

==完成全部映射下的磁盘使用过程== 在这里插入图片描述

二、文件系统代码实现

只要把文件系统如何映像到磁盘上对应扇区再加上前面学过的知识不就是文件系统的实现吗?

目录解析：

在open()函数里面找到对应文件并打开，而open()调用了sys_open()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


在linux/fs/open.c中
int sys_open(const char* filename, int flag)
{ 
	i=open_namei(filename,flag,&inode); //解析路径
	... 
}

int open_namei(...)
{ 
	dir=dir_namei(pathname,&namelen,&basename);
	....
}

static struct m_inode *dir_namei()
{ dir=get_dir(pathname); }

==经过一系列的调用真正完成目录解析的是get_dir==

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


static struct m_inode *get_dir(const char *pathname)
{ 
	if((c=get_fs_byte(pathname))==‘/’) //根目录
	{
		inode=current->root; pathname++;
	}
	else if(c) inode=current->pwd; //解析从此处开始
	while(1)
	{
		if(!c) return inode; //函数的正确出口
		bh=find_entry(&inode,thisname,namelen,&de);
		int inr=de->inode; 
		int idev=inode->i_dev;
		inode=iget(idev,inr); //根据目录项读取下一层inode
	}
}

(1)root：找到根目录； (2)find_entry：从目录中读取目录项； (3)inr：是目录项中的索引节点号； (4)iget：再读下一层目录

目录解析首先要找到一个解析的起点，如果路径名从 / 开始，就从根目录的inode 开始，否则要从当前目录的 inode 开始

==根目录inode的解析==

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


inode=current->root;

void init(void)
{ 
	setup((void *) &drive_info);
	...
}

sys_setup(void * BIOS)//在kernel/hd.c中
{ 
	hd_info[drive].head = *(2+BIOS);
	hd_info[drive].sect = *(14+BIOS);
	mount_root(); 
	... 
}

void mount_root(void)//在fs/super.c中
{
	mi=iget(ROOT_DEV,ROOT_INO));
	current->root = mi;
	...
}

所有进程的 root 都是从 1 号进程继承来的，在 1 号进程 init() 函数中要执行 mount_root()函数，用来将根目录的 inode读入到内存中，并且关联到 1 号进程的 PCB 中

有了起点目录文件的 inode，接下来读出目录文件内容，然后用文件路径上的文件名和和目录中的目录项逐个比对，不断向下解析，直到路径名被全部处理完成, 最终找到目标文件的inode

==读取inode （iget()函数）==

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


struct m_inode * iget(int dev, int nr)
{ 
	struct m_inode * inode = get_empty_inode();
	inode->i_dev=dev; inode->i_num=nr;
	read_inode(inode); return inode;
}

static void read_inode(struct m_inode *inode)
{ 
	struct super_block *sb=get_super(inode->i_dev);;
	lock_inode(inode);
	block=2+sb->s_imap_blocks+sb->s_zmap_blocks+
	(inode->i_num-1)/INODES_PER_BLOCK;
	bh=bread(inode->i_dev,block);
	inode=bh->data[(inode->i_num-1)%INODES_PER_BLOCK];
	unlock_inode(inode); 
}

以上都是根据磁盘的划分来实现的在这里插入图片描述

从上图可以看到inode 数组的起始位置在引导块,超级块以及两个位图数组之后

inode 数组在磁盘上的起始位置 = 引导块大小 + 超级块大小 + s_imap_blocks大小 + s_zmap_blocks大小

==开始解析目录 find_entry()==

函数 find_entry 根据目录文件的 inode 读取目录项数组，然后逐个目录项进行匹配，即 while(i<entries) if(match(namelen,name,de))

 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


在fs/namei.c中
static struct buffer_head *find_entry(struct m_inode
**dir, char *name, ..., struct dir_entry ** res_dir)
{ 
	int entries=(*dir)->i_size/(sizeof(struct dir_entry));
	int block=(*dir)->i_zone[0];
	*bh=bread((*dir)->i_dev, block);
	struct dir_entry *de =bh->b_data;
	while(i<entries) //entries是目录项数
	{ 	//#define BLOCK_SIZE  1024   两个扇区
		if((char*)de> = BLOCK_SIZE+bh->b_data)
		{
			brelse(bh);
			block=bmap(*dir,i/DIR_ENTRIES_PER_BLOCK);
			bh=bread((*dir)->i_dev,block);
			de=(struct dir_entry*)bh->b_data;
		} 
		//读入下一块上的目录项继续match
		if(match(namelen,name,de))
		{
			*res_dir=de;return bh;
		}
			de++; i++; 
	}
}

de: directory entry(目录项)

1
2
3
4
5
6
7


#define NAME_LEN 14

struct dir_entry
{
	unsigned short inode; //i节点号
	char name[NAME_LEN]; //文件名 
}

iget 用来读取索引节点，根据 inode 编号（iget 的参数）和 inode 数组的初始位置计算出该 inode 所在的磁盘块号，再用 bread 发送请求，放入“电梯” 队列，就可以完成磁盘的读写。

磁盘的管理(一)#

前言#

一、磁盘的介绍#

二、生磁盘的使用#

1.IO过程简介#

2.直接使用磁盘#

3.盘块号读写磁盘(第一层抽象)#

4.队列读写磁盘(第二层抽象)#

(1)FCFS磁盘调度算法#

(2)SSTF磁盘调度#

(3)SCAN磁盘调度#

(4)C-SCAN磁盘调度(电梯算法)#

总结#

磁盘的管理(二)#

前言#

一、磁盘文件#

1.顺序存储结构#

2.链式存储结构#

3.索引存储结构#

二、文件读取磁盘(第三层抽象)#

总结#

目录与文件系统#

前言#

一、文件系统#

二、文件系统代码实现#

磁盘的管理(一)

前言

一、磁盘的介绍

二、生磁盘的使用

1.IO过程简介

2.直接使用磁盘

3.盘块号读写磁盘(第一层抽象)

4.队列读写磁盘(第二层抽象)

(1)FCFS磁盘调度算法

(2)SSTF磁盘调度

(3)SCAN磁盘调度

(4)C-SCAN磁盘调度(电梯算法)

总结

磁盘的管理(二)

前言

一、磁盘文件

1.顺序存储结构

2.链式存储结构

3.索引存储结构

二、文件读取磁盘(第三层抽象)

总结

目录与文件系统

前言

一、文件系统

二、文件系统代码实现