磁盘存储管理

磁盘存储管理第1页，课件共57页，创作于2023年2月9.1磁盘I/O磁盘I/O速度的高低，将直接影响文件系统的性能。提高磁盘I/O速度的主要途径：选择性能好的磁盘采用好的磁盘调度算法设置磁盘高速缓冲区第2页，课件共57页，创作于2023年2月直接（随机）存取设备：存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。一、数据的组织信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头,所有盘面中处于同一磁道号上的所有磁道组成一个柱面。磁道由若干个扇区组成，每个扇区的大小相当于一个盘块。物理地址形式：磁头号（盘面号）磁道号（柱面号）扇区号9.1.1磁盘性能简述第3页，课件共57页，创作于2023年2月磁道扇区第4页，课件共57页，创作于2023年2月柱面扇区磁臂磁头第5页，课件共57页，创作于2023年2月二、磁盘的类型固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低磁盘系统由磁盘本身和驱动控制设备组成，实际存取读写的动作过程是由磁盘驱动控制设备按照主机要求完成的。一次访盘请求：读/写，磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目）9.1.1磁盘性能简述第6页，课件共57页，创作于2023年2月磁盘访问时间包括以下三个部分：寻道时间TS：磁头移动定位到指定磁道。10-40msTS=m*n+s（m：常数，n:移动的磁道数，s:磁盘启动时间）旋转延迟时间TR：等待指定扇区旋转到磁头下。硬盘平均8.3ms,软盘平均50-100ms数据传输时间TT：数据在磁盘与内存之间的实际传输。TT=b/(r*N)(b:读写字节数r:磁盘转速N:一个磁道上的字节数）分析：提高I/O效率的关键是什么？9.1.1磁盘性能简述第7页，课件共57页，创作于2023年2月设计文件系统时应尽可能减少磁盘访问次数块高速缓存系统在内存中保存一些块，逻辑上它们属于磁盘，检查所有的读请求，看所需的块是否在高速缓存中。如果在，则可直接进行读操作。否则，首先要将块读到高速缓存，再拷贝到所需的地方，如果高速缓存已满，则需要进行淘汰合理分配磁盘空间分配块时，把有可能顺序存取的块放在一起，最好在同一柱面上，从而减少磁盘臂的移动次数好的磁盘调度算法9.1.1磁盘性能简述第8页，课件共57页，创作于2023年2月9.1.2早期的磁盘调度算法磁盘调度：

当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效公平：一个I/O请求在有限时间内满足高效：减少设备机械运动所带来的时间浪费，主要是使磁盘的平均寻道时间最短。第9页，课件共57页，创作于2023年2月一、先来先服务：按访问请求到达的先后次序服务。优点：简单，公平；缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。例：假设磁盘访问序列：98，183，37，122，14，124，65，67读写头起始位置：53安排磁头服务序列，计算磁头移动总距离（道数）9.1.2早期的磁盘调度算法第10页，课件共57页，创作于2023年2月53：98，183，37，122，14，124，65，67总=640先来先服务第11页，课件共57页，创作于2023年2月二、最短寻道时间优先：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务。9.1.2早期的磁盘调度算法第12页，课件共57页，创作于2023年2月53：98，183，37，122，14，124，65，67总=236最短寻道时间优先第13页，课件共57页，创作于2023年2月一、扫描算法（电梯算法）克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复9.1.3各种扫描算法第14页，课件共57页，创作于2023年2月第15页，课件共57页，创作于2023年2月53：98，183，37，122，14，124，65，67总=208本例所示的当前移动方向为向磁道号减少的方向电梯算法第16页，课件共57页，创作于2023年2月二、循环扫描算法循环扫描法也称单向扫描，规定磁头单向移动。例如：它对请求者的服务总是每次从０柱面号开始，然后移动至最大柱面。遇着访问进行服务。一次完后，磁头再返回０号柱面，又重复上述步骤。9.1.3各种扫描算法第17页，课件共57页，创作于2023年2月第18页，课件共57页，创作于2023年2月例：假设磁盘访问序列：98，183，37，122，14，124，65，67读写头起始位置：53,移动方向是向磁道号增加的方向循环扫描算法：访问序列：53，65，67，98，122，124，183，14，37总移动距离=3229.1.3各种扫描算法第19页，课件共57页，创作于2023年2月三、N步扫描和FSCAN算法

引入目的：避免磁臂粘连。

N步扫描：将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列，对每个队列的处理用SCAN方法。注意：N的选取。

FSCAN算法：两个队列，一是当前请求I/O的磁盘请求队列,二是在扫描期间新出现的所有磁盘请求组成的队列。这样，所有新到达的访问请求本次不予访问，留待下次再服务。9.1.3各种扫描算法第20页，课件共57页，创作于2023年2月FSCAN算法示意图第21页，课件共57页，创作于2023年2月例：假设磁盘访问序列：98，183，37，122，14，124，65，67新出现：45，7，30读写头起始位置：53当前移动方向为向磁道号增加的方向N步扫描（N=3)：分组序列：(98,183,37)，(122，14，124)，(65，67,45)，（7，30）访问序列：(98,183,37)，(14，122，124)，(67，65,45)，（30，7）总移动距离=?FSCAN算法：访问序列（65，67，98，122，124，183，37，14）（7，30，45）总移动距离=?9.1.3各种扫描算法526344第22页，课件共57页，创作于2023年2月9.2外存分配算法文件的物理结构：又称为文件的存储结构，是指文件在外存上的存储组织形式，于存储介质的特性有关。类型：顺序结构（顺序分配）链接结构（链接分配）索引结构（索引分配）第23页，课件共57页，创作于2023年2月9.2.1连续分配一个文件的信息存放在若干连续的物理块中

优点:

简单支持顺序存取和随机存取顺序存取速度快所需的磁盘寻道次数和寻道时间最少

缺点:A文件不能动态增长预留空间:浪费重新分配和移动

B不利于文件插入和删除

C外部碎片问题:存储压缩技术第24页，课件共57页，创作于2023年2月012345678910111213141516171819202122232425262728293031文件名始址块数count02tr143mail196list284f62文件目录countftrmaillist第25页，课件共57页，创作于2023年2月9.2.2链接分配一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。

优点：提高了磁盘空间利用率,不存在外部碎片问题;有利于文件插入和删除;有利于文件动态扩充。链接方式分为:隐式链接显式链接

第26页，课件共57页，创作于2023年2月一、隐式链接在文件目录的每个目录项中，都须含有链接文件第一个盘块和最后一个盘块的指针。缺点：存取速度慢，不适于随机存取可靠性问题，如指针出错更多的寻道次数和寻道时间链接指针占用一定的空间改进：将几个盘块组成一个簇，以簇为单位分配盘块，文件的每一个元素也以簇为单位。9.2.2链接分配第27页，课件共57页，创作于2023年2月文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-125第28页，课件共57页，创作于2023年2月二、显式链接整个磁盘设置一张链接表（FAT)，每个文件的FCB表的“物理地址”中存放链首指针。优点：减少访盘次数，提高检索速度。9.2.2链接分配第29页，课件共57页，创作于2023年2月文件卷中的每个簇均对应一个FAT表项，文件分配采用链式分配方法。MS-DOSFAT第30页，课件共57页，创作于2023年2月9.2.3索引分配一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中。一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块。优点：保持了链接结构的优点,又解决了其缺点，即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间缺点：较多的寻道次数和寻道时间索引表本身带来了系统开销如：内外存空间，存取时间第31页，课件共57页，创作于2023年2月012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep19

91611025-1-1-119第32页，课件共57页，创作于2023年2月当索引表较大时，有如下几种组织方式：链接模式:一个盘块一个索引表,多个索引表链接起来多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中混合模式:UNIX文件系统采用的是多级索引结构(综合模式)。每个文件的索引表为13个索引项，每项4个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）9.2.3索引分配第33页，课件共57页，创作于2023年2月混合分配(假定每个盘块大小为4KB）:1.直接地址:当文件不大于40KB时，可直接从索引结点中读出全部盘块号。2.一次间接地址iaddr(10):允许文件长达4MB3.多次间接地址：Iaddr(11):两次,4GBIaddr(12):三次,4TB9.2.3索引分配第34页，课件共57页，创作于2023年2月第35页，课件共57页，创作于2023年2月第36页，课件共57页，创作于2023年2月9.3空闲存储空间的管理9.3.1空闲表法9.3.2空闲链表法9.3.3位示图法9.3.4成组链接法第37页，课件共57页，创作于2023年2月9.3.1空闲表法

将所有空闲块记录在一个表中，即空闲盘块表（示意图）特点:数据结构:空闲盘块表(序号,第一空闲盘块号,空闲盘块数)连续分配,分配和回收与内存管理的动态分区分配方法类似分配速度快,可减少访盘频率,用于小文件的分配和对换空间的管理第38页，课件共57页，创作于2023年2月序号第一空闲盘块号空闲盘块数12429331554----返回空闲盘块表第39页，课件共57页，创作于2023年2月9.3.2空闲链表法把所有空闲盘块链成一个空闲链,根据构成链的基本元素不同,可有两种链表形式:空闲盘块链:基本元素为盘块。优点：分配回收过程简单缺点：空闲盘块链可能很长空闲盘区链：基本元素为盘区（可包含若干个盘块）特点：分配回收与动态分区类似说明：可用显式链接方式提高检索速度第40页，课件共57页，创作于2023年2月9.3.3位示图法1.位示图用一串二进制位反映磁盘空间中分配使用情况,每个物理块对应一位,分配物理块为1，否则为0。磁盘上的所有盘块都有一个二进制位与之对应，由所有盘块所对应的位组成的集合，称为位示图。Varmap:array[1…m,1…n]ofbit优点：占用空间少，描述能力强，适合各种物理结构第41页，课件共57页，创作于2023年2月2.盘块的分配（1）顺序扫描位示图，查找为0的一个或一组二进制位（2）返回对应盘块号。假设位于位示图的第i行，第j列，对应的盘块为b=n(i-1)+j(n为每行的位数）（3）修改位示图map[i,j]=13.盘块的回收（1）将回收盘块号b转换成行号i和列号ji=(b-1)DIVn+1;j=(b-1)MODn+1（2）修改位示图：map[i,j]=09.3.3位示图法第42页，课件共57页，创作于2023年2月已知块号，则磁盘地址：

柱面号＝[块号/（磁头数×扇区数）]

磁头号＝[（块号mod（磁头数×扇区数））/扇区数]

扇区号＝（块号mod（磁头数×扇区数））mod扇区数已知磁盘地址：块号＝柱面号×（磁头数×扇区数）＋磁头号×扇区数＋扇区号9.3.3位示图法第43页，课件共57页，创作于2023年2月9.3.4成组链接法磁盘文件卷结构:超级块：描述文件系统的状态，包括磁盘空闲块栈，空闲i结点栈i节点（inodelist）：存放文件说明信息，每项64字节目录文件：每个目录项16字节。文件名区分大小写。文件分配：直接索引，一级、二级、三级间接索引第44页，课件共57页，创作于2023年2月空闲块成组链接，建立空闲块专用栈，空闲块分配时按组进行，一组的空闲块分配完了，再使用下一组；回收时次序相反，入栈一组空闲块后，够成一组。这种方法兼备了空闲空间表法和空闲块链接法的优点，UNIX系统使用这种空闲块管理策略。9.3.4成组链接法第45页，课件共57页，创作于2023年2月s-nfree空闲块数;s_free[100]空闲块块号;s_flock锁位9.3.4成组链接法第46页，课件共57页，创作于2023年2月下面演示分配过程的例子当前空闲块栈中还有两块未分配9.3.4成组链接法第47页，课件共57页，创作于2023年2月……s_nfree=2300299012s_free…99100400399…301…299#300#100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#第48页，课件共57页，创作于2023年2月……s_nfree=130001s_free…99100400399…301…分配299#300#100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#第49页，课件共57页，创作于2023年2月……s_nfree=03000s_free…99100400399…301…100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#300#分配第50页，课件共57页，创作于2023年2月……s_nfree=100400399…30101…99100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#s_free300#分配第51页，课件共57页，创作于2023年2月下面演示回收过程的例子当前空闲块栈中有99个空闲块9.3.4成组链接法第52页，课件共57页，创作于2023年2月……s_nfree=99460299

…350012…9899100700899…601…299#460#1005067099…4010…700#...990799…910…506#899