osch8磁盘存储器的管理.ppt

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 MS-DOS的文件物理结构,15,8.1.3 FAT技术相关计算,磁盘块（扇区）大小，FAT表项大小，簇的大小磁盘容量 1.FAT12：FAT表项12位，簇大小为1，2，4，8个扇区等 2.FAT16： FAT表项16位，簇大小为4，8，,64个扇区 3.FAT32： FAT表项32位，簇大小为8个扇区,16,8.1.3 FAT文件,FAT表的计算 任给定一磁盘空间会计算FAT表的所占空间大小,17,FAT表的计算,1、盘块大小1K，硬盘大小500M，文件照映方式下，FAT占多大？ 2、文件A占用硬盘的第11,12,16,14四个盘块，文件A中各盘块链接情况如何？,18,8.1.5 索引文件,索引文件结构 文件结构的数据结构是文件的索引表，每个文件有一个索引表，表中每个表目包括：逻辑块号，物理块号。 索引表位置：文件目录中，文件的开头等。 索引表大小:固定大小，非固定大小。,19,(1) 单级索引文件方式,将多个索引表块按链接文件的方式串联起来。 例 每个索引表项占4个字节(可表示物理块号的范围从0232)，若物理块的大小为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*16=4096（个） 如果一个扇区被定义为一个存储块，用字长位16位的存储单元来构造位示图，共需要256个字。,39,位示图,盘块分配： 1、扫描位示图，找到一个或一组值为0的二进制位 2、转换为相应的盘块号 i行，j列对应的盘块号 b=n*(i-1)+j 3、修改位示图 mapi,j=1,40,位示图,盘块回收： 1、将盘块号转换为位示图中的行号和列号 i=(b-1) div n+1 j=(b-1) mod n+1 2、修改位示图,41,8.2.3 成组链接法,UNIX系统的空闲块的管理 在UNIX系统中每个子文件系统（一片软盘、一个硬盘的分区，一卷磁带）格式化后的结构如图，其中特别块是存放该子文件系统的管理信息，包括空闲块管理信息。,42,1. 空闲盘块的组织,43,2. 空闲盘块的分配与回收,44,补充：“按名存取”的实现,“按名存取”的思想 用户访问文件时，系统根据文件名查文件目录，找到它的FCB。经过合法性检查，从FCB里得到该文件所在的物理地址，然后进行所需要的存取操作。,45,文件MYFILE的FCB内容,46,2.“按名存取”的实现过程 要读文件MYFILE第3个记录，存放到数组A：A0，A1，A499中。程序里发读命令： READ（MYFILE，3，A） （1） 文件系统通过命令中提供的文件名MYFILE查文件目录，找到了文件MYFILE的FCB后，系统就把该命令改变成为： READ（FCB，3，A） （2） 命令验证合法后，系统就开始进行把对文件的读/写请求从逻辑结构映射到物理结构的工作。,47,把逻辑记录号3转换成相应的逻辑字节地址，即相对于该文件起点的字节数。 公式是： 逻辑字节地址=逻辑记录号*逻辑记录长度=3*500=1500 命令（2）转换成： READ（FCB，1500，A） （3）,48,把逻辑字节地址转换成相对块号和块内相对字节地址。 公式是： 相对块号=(逻辑字节地址/物理块尺寸)+相对起始块号=(1500/1000)+6=1+6=7 块内相对字节地址=逻辑字节地址%物理块尺寸=1500%1000=500 命令（3）转换成： READ（FCB，7，500，A） （4）,49,把相对块号转换成物理地址:道号和块号。 公式是： 道号=相对块号/每道块数=7/4=1 块号=相对块号%每道块数=7%4=3 命令（4）转换成： READ（FCB，1，3，500，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. 置换算法,将磁盘块的数据读入高速缓存时，高速缓存中已装满需要将数据先换出 LRU，NRU，LFU,54,3. 周期性地写回磁盘,系统发生故障时，存放在高速缓存中的数据丢失，造成高速缓存中的和磁盘中的数据不一致 UNIX系统中专门增设了一个修改(update)程序， 使之在后台运行，该程序周期性地调用一个系统调用SYNC，强制性地将所有在高速缓存中已修改的盘块数据写回磁盘。 MS-DOS中所采用的方法是：只要高速缓存中的某盘块数据被修改，便立即将它写回磁盘,55,8.3.2 提高磁盘I/O速度的其它方法,1. 提前读(Read-Ahead) 读磁盘 2. 延迟写 写磁盘 3. 优化物理块的分布 分配磁盘块 4. 虚拟盘,56,习题,UNIX系统专用块及空闲盘块情况如图所示。 (1) 每一组的第一个物理块的作用是什么？ (2) 当用户释放了78#，89，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.总结操作系统中时间和空间换