操作系统课件第四版第八章.ppt

8.1 外存的组织方式 由于磁盘具有可直接访问的特性，故利用磁盘来存放文件时，具有很大的灵活性。 文件的物理结构主要是指磁盘上文件的结构。在为文件分配外存空间时，采用不同的分配方式将形成不同的文件物理结构。 目前常用的外存的组织方法有： 连续组织方式 ； 链接组织方式 ；索引组织方式 过去在一个系统中，仅采用其中的一种方法来为文件分配外存空间。在现代OS中，对文件可采取多种类型的组织形式。 二、链接组织方式 一个文件的信息存放在若干不连续的物理块中,各块之间通过指针链接，由此所形成的物理文件称为链接文件。 提高了磁盘空间利用率,不存在外部碎片问题，有利于文件插入和删除，有利于文件动态扩充。 1.隐式链接 在文件每个目录项中，都含有指向链接文件第一个盘块和最后一个盘块的指针。 问题：只适合于顺序访问,随机访问效率低，可靠性较差,只要其中的任何一个指针出现问题，都会导致整个链的断开。 五、索引组织方式 1.单级索引组织方式 一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中。 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块。 问题： 　　小文件采用此分配方式，其索引块的利用率极低。 3.增量式索引组织方式 也称为混合组织方式，UNIX文件系统采用的就是这种组织方式。每个文件的索引表为13个索引项，每项2个字节。 最前面10项直接登记存放文件信息的物理块号（直接寻址）。如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址。 UNIX中采用了三级索引结构后，文件最大可达16兆个物理块。 8.2 文件存储空间的管理 在为文件分配磁盘时，除了需要文件分配表，还需要设置一个磁盘分配表，用于记住可供分配的存储空间情况。存储空间的基本分配单位是磁盘块而非字节。 一、空闲表法和空闲链表法 1. 空闲表法（属于连续分配方式） 1）空闲表 将外存中的所有空闲块记录在一个表中，即空闲表，每个空闲区对应于一个空闲表项，共中包括表项序号、该空闲区的第一个盘块号、该区的空闲块数等信息。再将所有空闲区按其起始盘块号递增的次序排列。 2.链接数一致性检查 在UNIX类型的文件目录中，每个目录项中都含有一个索引结点号，用于指向该文件的索引结点。对于一个共享文件，其索引会在目录中出现多次。同时，在该共享文件的索引结点中有一个链接计数count，用来指出共享本文件的用户（进程）数。在正常情况下这两个数据应该一致。 配置一张计数器表，检查这种数据不一致性差错： （1）索引结点中的链接计数count值大于计数器表中相应索引结点号的计数值。(错误性质不严重） （2）索引结点中的链接计数count值小于计数器表中相应索引结点号的计数值。（有潜在的危险） 图8-11 空闲盘块的成组链接法 2.空闲盘块的分配与回收 须分别调用盘块分配过程和盘块回收过程来完成。 * 盘块分配过程： 1）将空闲盘块号栈调入内存； 2）栈指针Ptr初值为当前组的空闲盘块总块数（当前组由栈直接管理）； 3）用户提出空闲块请求n，按后进先出原则逐次取走指针所指的块号，Ptr Ptr-1； 4）当栈中只剩最后一个空闲块号时，启动设备管理程序，将该块中存放的下一组块号与总块数读入栈中后（将下组盘块交由栈管理），再将该块分配给申请者； 5）重置Ptr指针，继续分配。 * 盘块回收过程： 1）回收程序将文件释放的盘块号压入栈中，并做： Ptr Ptr+1； 2）块号记入Ptr所指的位置； 3）若 Ptr=100，表示该组回收结束； 4）若又有新的盘块回收，则启动设备管理程序，将现在栈中的100个盘块号和块数记入该块中（即将原来由栈管理的盘块改为由这个新盘块管理） ； 5）将此盘块的盘块号作为新栈底 (即新组的第一块)，重新置Ptr指针为1，另起一个新组。 8.3 提高磁盘I/O速度的途径 一、磁盘高速缓存 　 是一组在逻辑上属于磁盘，而物理上是驻留在内存中的盘块。 1.数据交付方式 （1）数据交付 （2）指针交付 后一种方式由于所传送的数据量少，因而节省了数据从磁盘存储空间到进程的内存工作区的时间。 2.置换算法 　　除了考虑到最近最久未使用这一原则外，还考虑了以下几点： （1）访问频率 （2）可预见性 （3）数据的一致性 3.周期性地写回磁盘 周期性地调用一个系统调用SYNC，该调用的主