第9章磁盘存储器管理

1、内容磁盘I/O外存分配方法空闲存储空间的管理磁盘容错技术文件系统性能的改善数据(shj)一致性控制第九章 磁盘(c pn)存储器管理共四十一页目的(md)及要求了解磁盘的性能和早期的磁盘调度算法，掌握各种扫描算法；领会和掌握常用的外存分配方法：连续分配、链接分配、索引分配；理解和掌握空闲存储空间的管理机制；了解各级磁盘容错技术；了解提高文件访问的快速性的各种手段；了解数据一致性控制的基本方法。第九章 磁盘(c pn)存储器管理共四十一页重点各种扫描算法(sun f)；常用的外存分配方法：连续分配、链接分配、索引分配；空闲存储空间的管理机制；难点成组链接法外存分配与回收；理解和掌握空闲存储空间的

2、管理机制；廉价磁盘冗余阵列磁盘容错技术；数据一致性并发控制。第九章 磁盘(c pn)存储器管理共四十一页主要任务分配空间组织(zzh)文件的存取方式提高磁盘储存空间的利用率提高I/O速度保证文件系统的可靠性第九章 磁盘(c pn)存储器管理共四十一页提高I/O速度的主要途径：选择性能好的磁盘采用适当的调度(diod)算法设置磁盘高速缓冲区9.1.1 磁盘性能简述9.1.2 磁盘调度算法9.1 磁盘(c pn)I/O共四十一页数据的组织盘片（Platter ）磁盘最基本的组成部分(z chn b fn)是由坚硬金属材料制成的涂以磁性介质的盘片，不同容量硬盘的盘片数不等。每个盘片有两面，都可记录信

3、息。磁道 (Tracks)盘片表面上以盘片中心为圆心，不同半径的同心圆称为磁道。扇区(Sectors) 盘片被分成许多扇形的区域，每个区域叫一个扇区，硬盘每个扇区可存储512字节信息。FAT32模式下，每个扇区的容量为4KB。每个扇区的大小相当与一个盘块。9.1.1 磁盘(c pn)性能简述共四十一页9.1.1 磁盘(c pn)性能简述磁头(Heads)每个盘片的每一面都会有一个读写头（read-write head），来读取相应盘面的内容。习惯用磁头号来区分。柱面 (Cylinders)不同(b tn)盘片相同半径的磁道所组成的圆柱称为柱面。磁道与柱面都是表示不同半径的圆，在许多场合，磁道和

4、柱面可以互换使用。共四十一页9.1.1 磁盘(c pn)性能简述柱面扇区磁臂磁头(ctu)共四十一页9.1.1 磁盘(c pn)性能简述扇区，磁道（或柱面）和磁头数构成了硬盘结构(jigu)的基本参数，这些 参数可以得到硬盘的容量，基计算公式为： 存储容量磁头数磁道（柱面）数每道扇区数每扇区字节数1.44M =28018512 共四十一页磁盘的类型固定头磁盘每条磁道上都有一个读/写磁头，所有(suyu)的磁头被装入一个磁臂通过这些磁头可以访问所有磁道，并进行并行读写主要用于大容量磁盘移动头磁盘每个盘面仅有一个磁头，被装入一个磁臂中为能访问盘面上的所有磁道，该磁头必须移动以进行寻道只能串行读/写

5、，致使I/O速度较慢结构简单，广泛应用中、小型磁盘，微机上的硬盘和软盘，都采用移动磁头结构9.1.1 磁盘(c pn)性能简述共四十一页磁盘访问时间寻道时间（seek time）Ts把磁头(ctu)从当前位置移到指定磁道所经历的时间。 Ts=m*n+ss-磁盘的启动时间,大约3ms；m-每移动一条磁道所经历的时间，对一般磁盘：m0.3ms，对高速磁盘：m0.1ms；n-移动的磁道数目；9.1.1 磁盘(c pn)性能简述共四十一页旋转延迟时间（rotational latency time）Tr指定(zhdng)扇区移动到磁头下所经历的时间 Tr=1/2r （平均情况下，需要旋转半圈）r磁盘以

6、秒计的旋转速度一个7200（转/每分钟）的硬盘，则旋转延迟时间为601000720024.17毫秒。一个5400（转/每分钟）的硬盘，旋转延迟时间为601000540025.56毫秒。一个300/600（转/每分钟）软盘，平均旋转延迟时间为6010003002100毫秒, 601000600250毫秒。9.1.1 磁盘(c pn)性能简述共四十一页传输时间Tt数据从磁盘(c pn)读出，或向磁盘(c pn)写数据所经历的时间，约为零点几个毫秒,可以忽略不计。Ttb/rNb读写的字节数 r磁盘以秒计的旋转速度N一条磁道上的字节数访问时间Ta=Ts+Tr+Tt=(m*n+s)+1/2r+b/rN9

7、.1.1 磁盘(c pn)性能简述共四十一页移动磁头磁道为哪个进程服务(fw)旋转磁盘扇区为哪个进程服务目标各进程对磁盘的平均访问时间（主要是平均寻道时间，即平均移动的磁道数目）最小9.1.2 磁盘(c pn)调度算法共四十一页先来先服务FCFS（First-Come,First-Served）最简单的磁盘调度算法，根据进程请求访问磁盘的先后次序进行调度。优点公平、简单，每个进程的请求都能依次得到处理(chl)，不会出现某个进程长时间得不到满足的情况。缺点未对寻道进行优化，平均寻道时间可能较长9.1.2 磁盘(c pn)调度算法共四十一页9.1.2 磁盘(c pn)调度算法从100磁道开始被访

8、问的下一个磁道号移动距离（磁道数）5545583391918219072160701501038112184146平均寻道长度：55.3共四十一页最短寻道时间优先SSTF（Shortest Seek Time First）选择要访问的磁道与当前磁头所在的磁道距离最近的进程优点每次的寻道时间最短缺点(qudin)不能保障平均寻道时间最短,出现进程“饥饿”现象9.1.2 磁盘调度(diod)算法共四十一页9.1.2 磁盘(c pn)调度算法从100磁道开始被访问的下一个磁道号移动距离（磁道数）901058325533916387218201501321601018424平均寻道长度：27.4共四十

9、一页扫描算法SCAN进程“饥饿”现象在SSTF中，若不断有新进程到来，且其访问的磁道与当前磁道的距离较近，这种进程被优先执行，而老进程一直得不到满足。SCAN算法不仅考虑访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，又称电梯调度算法。优点较好的寻道性能(xngnng)，又能防止进程“饥饿”现象，被广泛应用与大、中、小型机及网络中的磁盘调度缺点可能使进程的请求被严重推迟9.1.2 磁盘调度(diod)算法共四十一页9.1.2 磁盘调度(diod)算法从100磁道开始，向磁道号增加的方向移动被访问的下一个磁道号移动距离（磁道数）150501601018424909458325533

10、9163811820平均寻道长度：27.8共四十一页9.1.2 磁盘调度(diod)算法循环扫描算法CSCAN(Circular SCAN)规定磁头单向移动，即使(jsh)最小磁道号与最大磁道号紧邻，形成循环。从100磁道开始，向磁道号增加的方向移动被访问的下一个磁道号移动距离（磁道数）15050160101842418166382039155165839032平均寻道长度：27.5共四十一页9.1.2 磁盘(c pn)调度算法N步扫描算法N-Step-SCAN、改进前几种(j zhn)算法可能出现磁头静止在一个磁道上，导致其它进程无法及时进行磁盘I/O。把磁盘I/O请求队列分成长度为N的子队

11、列，每次使用SCAN算法处理这N个请求，使用FCFS处理子队列。当N很大时，该算法的性能接近于SCAN算法。当N=1时，该算法退化为FCFS算法。双队列扫描算法FSCAN对N步扫描算法的简化，即把磁盘I/O请求分成两个队列，当前请求磁盘I/O的进程放入一个队列，新生成的磁盘I/O请求放入另一队列中。交替使用SCAN算法处理一个队列。共四十一页9.2 外存分配(fnpi)方法即文件物理组织方式，其目标：有效利用外存空间(kngjin)提高文件的访问速度9.2.1 连续分配9.2.2 链接分配9.2.3 索引分配共四十一页9.2.1 连续(linx)分配连续分配（Continuous Alloca

12、tion）要求为每一个(y )文件分配一组相邻的盘块。优点顺序访问容易：连续的空间顺序访问速度快：一条或相邻的磁道上缺点要求有连续的存储空间：形成外碎片必须事先知道文件的长度：装入时要求filelengthstartcount20tr314mail619list428f26012345678910111213141516171819202122232425262728293031共四十一页9.2.2 链接(lin ji)分配filestartendjeep9250123456789101112131415161718192021222324252627282930311016251-1隐式链接

13、(lin ji) 在文件目录的每个目录项中含有指向链接文件第一和最后一个盘块的指针 只适用于顺序访问，对随机访问效率极低，可靠性差。改进：将几个盘块组成一个簇（Cluster）,在进行分配时以簇为单位进行，链接文件的元素也以簇为单位，这样可以成倍减少查找时间，也可减少指针占用的存储空间，但增大了内碎片。共四十一页9.2.2 链接(lin ji)分配显式链接把用于链接文件各物理块的指针，显式的存放(cnfng)在内存的一张链接表中，即文件分配表FAT（File Allocation Table）。不能支持高效的直接存取FAT占用较大的内存空间496EOF11105EOF0123456789101

14、1FCB AFCB BFAT共四十一页9.2.3 索引(suyn)分配单级索引分配为每个文件分配一个索引表，把分配给该文件的盘块号，记录在该索引表中。文件目录中，填上指向(zh xin)该索引表的指针。共四十一页9.2.3 索引(suyn)分配file序号jeep190123456789101112131415161718192021222324252627282930319161025-11.优点支持直接访问(fngwn)不产生外碎片2.缺点索引表在外存空间共四十一页9.2.3 索引(suyn)分配多级索引(suyn)分配105106254356357。0121051062543563579

15、85第二级索引磁盘空间9853607401125主索引360740。1125共四十一页9.2.3 索引(suyn)分配混合(hnh)分配方式将多种分配方式结合在一起。共四十一页9.3 空闲(kngxin)存储空间的管理9.3.1 空闲表法9.3.2 空闲链表法9.3.3 位示图法(t f)9.3.4 成组链接法共四十一页9.3.1 空闲(kngxin)表法为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个表目，包括序号、该区的起始空闲盘块号、空闲盘块数目等，按起始空闲盘块号排序。分配：是一种连续分配方式，顺序(shnx)查找空闲表，找到第一个合适的空闲区，修改空闲表。回收：将相应块按序填回

16、表中，并与前后合并成大块。特点：连续存放，易产生碎片。序号第1个空白块号空白块数物理块号1242,3,4,52939,10,11315515,16,17,18,194共四十一页9.3.2 空闲(kngxin)链表法空闲盘块链将磁盘上所有空闲存储空间，以盘块为单位链成一个链表。分配：从链首开始，依次摘下适当数目的空闲盘块进行分配。回收：依次链入链尾。特点：分配、回收简单，空闲盘块链可能很长。空闲盘区链将磁盘上所有空闲存储空间，以盘区（包括若干盘块）为单位链成一个链表。分配：查找(ch zho)合适大小的盘区进行分配回收：与前后盘区合并特点：分配、回收复杂，空闲盘区链较短。共四十一页9.3.3 位

17、示图法(t f)位示图系统为文件存储空间建立一张位示图，如下图。位示图反映了整个存储空间的分配情况，其中每一位对应一个(y )物理块，“1”表示对应块已被分配，“0”表示对应块为空白。1000110001111101001000111111111111100011111001000123456789101112131415012位 号字号共四十一页9.3.3 位示图法(t f)盘块的分配顺序扫描位示图，找到一个(y )或一组为“0”的二进制位将位号、字号转换为盘块号，进行分配：块号=位数*字号+位号修改位示图，置“1”。盘块的回收将盘块号转换为位号、字号：字号=块号 DIV 位数位号=块号 M

18、OD 位数修改位示图，置“0”。共四十一页9.3.4 成组链接(lin ji)法空闲盘块的组织空闲盘块栈存放当前可用的空闲盘块的盘块号，最多100个，以及空闲盘块数。栈是临界资源，为之设锁。文件区的所有空闲盘块，被划分(hu fn)为若干个组。设10000个盘块，100个为一组。201-7999号盘块存放文件。将每组的盘块数及盘块号，记入前一组的第一个盘块中。第一组的盘块数及盘块号记入空闲盘块栈最后一组的S.free(0)=0，作为结束标记共四十一页9.3.4 成组链接(lin ji)法.100300299.202201.100400399.302301.100500499.402401.9907999.79027901.299201.399301.78997801.79997901.3004007900S.free01.9899空闲盘块号栈.共四十一页9.3.4 成组链接(lin ji)法空闲(kngxin)盘块的分配空闲盘块号栈上锁否？栈指针是S.free(0)吗？从栈顶取出空闲盘