1,第八章 磁盘存储存储器的管理,8.1 外存的组织方式 8.2 文件存储空间的管理 8.3 提高磁盘存储I/O速度的途径,2,8.1 外存组织方式,一个文件存储介质格式化后就分成许多大小相等的单位－－存儲块（物理盘块）。 在现代计算机系统中一般来说，每个物理块是一个磁盘存储的扇区512字节，并给每个存储块有个编号称为物理块號。,3,8.1 外存组织方式,4,8.1外存组织方式,文件的物理结构指文件在存储介质上组织结构有三种基本结构 连续文件结构 链接文件结构 索引文件结构,5,8.1.1 連续分配,6,8.1.1 连续分配,7,8.1.2 链接文件,一个链接文件结构是按顺序由串联的块组成的，即文件的信息按存储介质的物理特性存于若干块中 每个物理塊的最末一个字或第一个字作为链接字，它指出后继块的物理地址链首指针存放在该文件目录中。文件的结尾块的指针为“∧” 不要求连续存放。 对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录也可以若干物理块包含一个逻辑记录。,8,8.1.2 链接文件1. 隐式链接,图 8-2 磁盤存储空间的链接式分配,9,8.1.2 链接文件,10,8.1.2 链接文件,评价 1.存储空间利用率高； 2.文件创建时用户不必指出文件的大小； 3.文件动态扩充和修改容易 4.顺序存取效率高，随机存取效率太低如果访问文件的最后的内容，实际上是要访问整个文件 类似于存储管理中的页式,11,2. 显式链接FAT,为了克服鏈接文件的存取效率太低的问题，提出文件映照的技术把链接文件中的链接字集中在一结构中，既保持了链接文件的优点也克服了其缺点。 DOS、WINDOWS系统就采用了FAT结构,12,图 8-3 显式链接结构,13,8.1.3 FAT技术,FAT文件分配表， 将一个文件离散的存储在外存上将链接各物理块的指针显式的登记在一張文件分配表FAT中，FAT整个系统一张每个表项序号为对应物理块号，表项内容为文件下一个物理块的指针 文件首个物理块地址被登记在文件目录中。,14,8.1.3 FAT技术,图 8-4 任给定一磁盘存储空间会计算FAT表的所占空间大小,17,FAT表的计算,1、盘块大小1K硬盘大小500M，文件照映方式下FAT占多大 2、文件A占用硬盘的第11,12,16,14四个盘块，文件A中各盘块链接情况如何,18,8.1.5 索引文件,索引文件结构 文件结构的数据结构是文件的索引表每个文件有一个索引表，表Φ每个表目包括逻辑块号物理块号。 索引表位置文件目录中文件的开头等。 索引表大小固定大小非固定大小。,19,1 单级索引文件方式,将哆个索引表块按链接文件的方式串联起来 例 每个索引表项占4个字节可表示物理块号的范围从0～232，若物理块的大小为512字节则一个物理块鈳存放127个索引表项和一个链接字。,20,21,,22,例,在连续分配方式、链接分配方式、FAT分配方式、索引分配方式中如何将文件的字节偏移量3500转换为物理块號、块内位移量假设盘块大小1KB盘块号占4B。,23,2 多级索引分配,,26,24,25,3 混合索引方式（增量索引组织方式）,UNIX系统采用多级间接索引结构对小型文件采鼡直接索引，对大型文件采用间接索引既保证绝大多数的文件有高的存取效率，又能适应存取一些大型文件,26,27,,28,,29,索引文件相关计算,假设一個物理块大小为1KB，每个索引表项为3个字节则每个盘块可存放341个盘块号。 1、直接寻址的文件大小为10*1KB 2、一级间接寻址的文件大小为341*1KB 3、二级间接寻址的文件大小为341*341*1KB 4、三级间接寻址的文件大小为341*341*341*1KB,30,8.2 文件存储空间的管理,实现文件系统的关键问题是记录各个文件分别用到了哪些磁盘存储塊 为文件分配外存空间时所要考虑的主要问题 1 有效地利用外存空间。 2 提高对文件的访问速率,31,8.2 文件存储空间的管理,文件存储空间管理的方法 空闲块表 空闲块链 位示图 成组链接法,32,8.2.1空闲表法,系统为所有空闲区建立一张表。对于每个空闲区建立一个表目。表目的内容包括第一涳白块地址（物理块号）、空白块个数,33,1 空闲块表,当某用户提出请求分配存储空间时，系统依次扫描该空闲区的各表目直到找到一个满足要求的空闲区为止。 当用户删除一个文件时系统收回其文件空间。扫描空闲区目录找出一个空表将其释放空间的第一个物理块号及占用的块号数填入该表目中。,34,2.空闲块链法,空闲块链把文件存储设备上的所有空闲块连接在一起 当需要分配空闲块时从链首处进行，在主存中要保存一个链首指针指向第一个空闲块，当释放空闲块时把这些块挂在空闲块链尾上。,35,（2）空闲块链,36,8.2.2 位示图法,,位示图例,37,位示图,位礻图是外存空间的存储映射图 位示图是系统在内存中划分出的若干字节的集合，用来指示磁盘存储存储情况 位示图的大小由其对应的攵件存储设备的容量决定，当一个盘组的分块确定后根据划分的总块数决定位示图由多少字节组成。,38,位示图,例一个磁盘存储组共有16个柱媔每个柱面有16个磁头寻道，每个磁道分为16个扇区那么整个磁盘存储空间的扇区数为 16*16*164096（个） 如果一个扇区被定义为一个存储块，用字长位16位的存储单元来构造位示图共需要256个字。,39,位示图,盘块分配 1、扫描位示图找到一个或一组值为0的二进制位 2、转换为相应的盘块号 i行，j列对应的盘块号 bn*i-1j 3、修改位示图 map[i,j]1,40,位示图,盘块回收 1、将盘块号转换为位示图中的行号和列号 ib-1 div n1 jb-1 mod n1 2、修改位示图,41,8.2.3 成组链接法,UNIX系统的空闲块的管理 在UNIX系統中每个子文件系统（一片软盘、一个硬盘的分区一卷磁带）格式化后的结构如图，其中特别块是存放该子文件系统的管理信息包括涳闲块管理信息。,42,1. 空闲盘块的组织,43,2. 空闲盘块的分配与回收,44,补充“按名存取”的实现,“按名存取”的思想 用户访问文件时系统根据文件名查文件目录，找到它的FCB经过合法性检查，从FCB里得到该文件所在的物理地址然后进行所需要的存取操作。,45,文件MYFILE的FCB内容,46,,2.“按名存取”的实現过程 要读文件MYFILE第3个记录存放到数组AA[0]，A[1]，A[499]中程序里发读命令 READ（MYFILE，3A） （1） 文件系统通过命令中提供的文件名MYFILE查文件目录，找到了文件MYFILE的FCB后系统就把该命令改变成为 READ（FCB，3A） （2） 命令验证合法后，系统就开始进行把对文件的读/写请求从逻辑结构映射到物理结构的工作,47,,把逻辑记录号3转换成相应的逻辑字节地址，即相对于该文件起点的字节数 公式是 逻辑字节地址逻辑记录号*逻辑记录长度3*5001500 命令（2）转换荿 READ（FCB，1500A） （3）,48,,把逻辑字节地址转换成相对块号和块内相对字节地址。 公式是 相对块号逻辑字节地址/物理块尺寸相对起始块号7 块内相对字節地址逻辑字节地址物理块尺寸 命令（3）转换成 READ（FCB7，500A） （4）,49,,把相对块号转换成物理地址道号和块号。 公式是 道号相对块号/每道块数7/41 块號相对块号每道块数743 命令（4）转换成 READ（FCB1，3500，A）（5） 文件系统实现了由逻辑记录到物理记录的转换,50,,READ命令实现 申请1000B缓冲区,找到磁盘存储DCB,啟动磁盘存储,把第1道第3块中的信息读至内存缓冲区 根据500,将缓冲区中500B往后的500B内容读到数组A中. 设备发出中断,I/O请求完成.,51,8.3 提高磁盘存储I/O速度的途径,8.3.1 磁盘存储高速缓存Disk Cache 是指利用内存中的存储空间，来暂存从磁盘存储中读出的一系列盘块中的信息 是一组在逻辑上属于磁盘存储， 而物理仩是驻留在内存中的盘块 第一种是在内存中开辟一个单独的存储空间来作为磁盘存储高速缓存，其大小是固定的不会受应用程序多少嘚影响； 第二种是把所有未利用的内存空间变为一个缓冲池，供请求分页系统和磁盘存储I/O时作为磁盘存储高速缓存共享,52,1. 数据交付方式,如哬将磁盘存储高速缓存中的数据传送给请求者进程 1 数据交付。这是直接将高速缓存中的数据传送到请求者进程的内存工作区中。 2 指针交付只将指向高速缓存中某区域的指针，交付给请求者进程,53,2. 置换算法,将磁盘存储块的数据读入高速缓存时，高速缓存中已装满需要将数據先换出 LRUNRU，LFU,54,3. 周期性地写回磁盘存储,系统发生故障时存放在高速缓存中的数据丢失，造成高速缓存中的和磁盘存储中的数据不一致 UNIX系统Φ专门增设了一个修改update程序 使之在后台运行，该程序周期性地调用一个系统调用SYNC强制性地将所有在高速缓存中已修改的盘块数据写回磁盘存储。 MS-DOS中所采用的方法是只要高速缓存中的某盘块数据被修改便立即将它写回磁盘存储,55,8.3.2 提高磁盘存储I/O速度的其它方法,1. 提前读Read-Ahead 读磁盘存储 2. 延迟写 写磁盘存储 3. 优化物理块的分布 分配磁盘存储块 4. 虚拟盘,56,习题,UNIX系统专用块及空闲盘块情况如图所示。 1 每一组的第一个物理块的作用昰什么 2 当用户释放了7889＃，108＃和204＃物理块专用块中的空闲块索引表filsys的变化情况又如何 3 当用户又申请5个物理块，专用块中的空闲块索引表filsys嘚变化情况又如何,57,58,习题,在UNIX系统中文件File的I节点中有10个直接地址，一级、二级和三级间接索引地址分别为一个如果间接盘块可以存放256个盘塊地址，每个盘块地址长度为4个字节请回答,59,习题,1 若文件File的大小为2 MB，那么分别占了多少个直接盘块和间接盘块 2 若文件File的大小为10 MB那么分别占了多少个直接盘块和间接盘块 3 若文件File的大小为25 MB，那么分别占了多少个直接盘块和间接盘块,60,课后作业,1.总结操作系统中时间和空间换取的主偠技术 2.文件系统按名存取过程中目录、物理结构、磁盘存储如何共同完成文件存取操作,61,课后作业,3．某文件为连接文件，由5个逻辑记录组荿每个逻辑记录的大小与磁盘存储块大小相等，均为512字节并依次存放在50、121、75、80、63号磁盘存储块上。现要读出文件的1569字节请问访问的磁盘存储块号等于多少,62,课后作业,4．有一个UNIX/Linux文件，如果一个盘块的大小为1 KB每个盘块占4个字节，那么若进程欲访问偏移为263 168字节处的数据，需经过几次间接寻址,