磁盘存储器

一 . 外存的组织方式(文件保存的物理方式)

文件的物理结构直接与外存的组织方式:

顺序结构	链接结构	索引结构
连续分配	链接分配	索引分配

1.连续组织方式

每一个文件分配到相邻的盘块(一个连续的磁道上 相邻盘块)

特点: 最简单的物理结构将逻辑上链接的文件信息依次存入内存块中

**优点:**①访问容易,随机存储②顺序访问速度快在一条磁道上

缺点:①为一个文件分配连续存储空间有外部碎片,降低利用率,紧凑开销大
②没有办法事先估计好文件大小 ③对动态增长的文件,难以事先分配

2.链接组织方式

​为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。

隐式链接	显式连接
下一个盘块地址在盘块内部	将各个盘块地址放在一个盘块中

隐式链接

缺点:①存取速度慢不支持随机存取②可靠性差当指针在中间出错则文件损坏
③需要多次寻道浪费时间④指针占用大量空间

解决方法:①提高检搜速度和减少指针空间②多块成为一簇的单位,增加内碎片

显式链接

FCB中指向该FAT文件分配表 当系统调用文件时自动将FAT调入内存依次读取表结构中的盘块。

缺点:占用较大内存

优点:避免指针断裂造成文件损失

顺序存储	链式存储
支持随机存储,有外碎片	没有外碎片,不能直接存取
	FAT技术随机存取,浪费存储空间

3.索引组织方式

​一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个索引块，把分配给该文件的所有盘块号都记录在该索引块中。建立一个文件时,只需要目录项上填充索引块指针

​打开文件时只需要知道该文件的盘块号,不必将整个FAT调入内存,将索引块放入FCB中实现随机存取。

**优点:**①直接访问,随机存储②不会有外碎片③满足文件动态增长的需求

**缺点:**①需要多次寻道②索引表本身的内部开销③有了索引表内碎片

4.多级索引组织方式

文件需要占用多个索引表,消耗大量盘块,则可以建立多级索引表:

5.混合式索引组织方式

某些大文件可以运用不同的多级的方式 直接寻址,间接寻址查找

二 . 文件空闲空间管理

​任何一种文件组织方式,都需要为文件分配磁盘块,那些磁盘块可以分配和回收?
这节引入磁盘分配表:分为分配回收的机制。
空闲空间的管理方法:

位图法	空闲块表	空闲块链表
用0/1表示每个物理块的分配状况	将空闲的块记录在一个表中	把空闲块连成一个链

1. 位视图法

'0’表示空闲,'1’表示已分配,存放在磁盘上,较小的放置在内存上。

1)盘块的分配

​ 分配三个步骤:

​ 1.顺序扫描位视图,从中找到一个或一组位’0’的二进制位;

​ 2.计算找到的一个或一组二进制位转化为相应的盘块号:
​ 计算公式: b = n(i-1)+j (第i行,第j列) n为每一行的位数

​ 3.修改位视图 领map[i,j] =1

2)盘块的回收

​回收二个步骤:

​1.将回收盘块的盘块号转化为为使徒的行号和列号;
​转化公式 :i = (b - 1) DIV n + 1; j = (b - 1) MOD n + 1;
2.将 map[i,j] = 0;

3) 位图法的特点
​优点: ①很容易到一个或一组相邻接的空闲盘块;②位图很小，占用空间少，因而可以保存在内存，节省启动磁盘次数。常用于小型机/微型机

2. 空闲表法

​空闲表法时连续分配方式,为每个文件分配一块连续的存储空间,系统为外存所有的空闲区建立一张空闲表。
表项为表示序号,空闲区的第一个盘块号,该区的空闲盘块数。

1)盘块分配
​空闲盘区的分配与内存的动态分区分配分配类似，同样是采用 首次适应算法 和 最佳适应算法 等。在系统为某新创建空闲块时,检搜空闲表中的表项,知道找到一个大小满足要求的空闲区,将该盘区分配给用户进程,同时修改空闲表。
2)盘块回收
​系统在对用户所释放的存储空间进行回收时，也采用类似内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者予以合并。
3)空闲链表使用的场景
​在存储器分配中,较少采用连续内存分配方式,但在外存上考录到读取速率读取次数问题,这种分配方式有较好的分配速度,可减少访问磁盘IO的频率,故在微型机使用广泛
1.磁盘中的对换空间,采用连续分配方式
2.文件小于1-4块时候,采用连续分配方式;较大时候采用离散分配;
​3.对多媒体文件,要求文件的流畅性,要减少寻道时间,采用连续分配方式

3. 空闲链表法

将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素不同，可把链表分成空闲盘块链和空闲盘区链。

空闲盘块链

将空闲的盘块链接在一块 回收时候挂接在末尾
优点:分配回收简单
缺点:盘块链较长,为一个文件要分配多次,分配回收效率低

空闲盘区链

将若干个盘块(相邻的,紧挨的)链接成一个链表 盘区内要知明盘区内部信息盘块大小
分配:采用首次适应算算找到存储空间
回收: 需要考虑前后端是否有空闲盘区 考虑是否需要合并
优点:回收分配效率高;空闲盘区链短
缺点:回收分配复杂

4. 成组链接法

空闲表法,空闲链表法均不适用于大型文件系统,都过于冗长 在UNIX系统采用时成组链接法 上述方法的结合
■文件区的所有空闲盘块被分成若干组（如100个空闲盘分成一组），设第201-7999号盘块用于存放文件；
■每一组的第一个盘块中记录有下一组的盘块总数和盘块号；最后一组只有99个可用盘块；
■第一组盘块总数和所有盘块号记入空闲盘块号栈中。

分配:分配的时候从栈顶开始分配,最后若分配到栈底,则将栈底指向的新的空闲盘区的栈顶继续使用,依次类推

回收:将空闲出来的盘块回收到栈内,若栈内已满,则便将栈中的盘块收录入新的盘块中,将盘块号指针作为新的栈底

三 . 磁盘存储器的性能调度

1.磁盘数据的组织.

磁盘设备包含多个物理片,每个此片分上下2个存储面,每个面含有若干磁道,每个词到存储数目相同的0/1二进制位,逻辑上分为若干扇区,一个扇区代表一个物理块

2.磁盘访问时间

R转动一周时间,B每次传输字节数 为一条磁道上的数据数(bit)
(1)寻道时间: t = 磁盘转动速度 * 第几磁道 + s启动磁壁时间
(2)旋转延迟时间: t = 1/2R
(3)数据传输时间: t = B/RN
而找寻一次盘块到读入识别数据 t = 寻道时间+旋转延迟时间+数据传输时间

3.磁盘调度算法

​ (1) 先来先服务(FCFS) --早期
​ 算法思想：根据进程请求访问磁盘的先后次序进行调度。

(2) 最短寻道时间优先(SSTF)

​ 算法思想：该算法选择这样的进程，其要求访间的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种算法不能保证平均寻道时间最短。

优缺点：减少了磁道平均查找时间，但没考虑磁头移动的方向也没有考虑进程在队列中等待时间，有可能引起饥饿

进程’饥饿’现象:
只要不断有新进程到达，且新进程所要访问的磁道与磁头当前所在磁道的距离较近，则新进程一定优先满足，而某些老进程则会发生"饥饿”现象。

(3)引入SCAN算法:电梯调度算法

​不仅要考虑磁头与磁道的距离,更要保持当前移动方向一致且距离最近的访问对象。

从盘面的圆心->圆边->圆心

(4) 循环扫描(CSCAN)算法

从盘面的圆心----缓慢沿途相应请求----->圆边------立即------>圆心
特点:从将磁盘的头尾相接单方向循环

(5) NstepSCAN和FCSAN调度算法

​ “磁壁黏着”: 有一个或几个进程对某一磁道有较高的访问频率 则 磁头可能一直处于某个磁道,造成垄断现象

NstepSCAN

算法思想：将磁盘请求队列分成若干个长度为的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法。对一个队列处理完后，在处理其他队列。当正在处理某子队列时，如果又出现新的I/0请求，便将新的请求放入其他队列。

多队列依次调度–> 将几个进程请求排列为一队,依次给每个磁道最近的进程返回消息

FSCAN

​算法思想:将请求访问队列分为两个子队列,一个是请求队列进程形成的队列,有SCAN算法处理,另一种则通过扫描期间新过来的请求放入一个队列中不考率队列的长短,所有的新要求放在下一次扫描中解决。