现代操作系统第四章文件系统PPT

1第四章文件系统文件目录文件系统的实现文件系统管理和优化文件系统实例2长期信息保存的要求能够保存大量数据在使用信息的进程终止后，信息仍然存在能够允许多个进程并发访问相关信息 满足上述三个要求，按单元将信息存储到磁盘和其他外部媒介的一般方法就是文件(files)。然后，进程可以读些它们。保存在文件中的信息必须是持久性的，也就是说，不受进程创建和终止的影响。文件只应该在其所有者显式地删除它时才消失。3三个抽象概念进程进程就是一个正在执行的程序进程地址空间地址空间：一个进程可用于寻址内存的一套地址集合。文件文件是进程创建的信息逻辑单元。4长期信息保存文件由操作系统管理。文件的存取、使用、保护以及实现都是操作系统的主要设计问题。整体上而言，处理文件的操作系统部份称为文件系统(filesystem):FAT/NTFS/CDFS/UFS/VMFS从用户的立场来看，文件系统最重要的方面是文件的出现方式，即文件的组成、文件的命名和保护、文件的操作等等。5文件文件命名文件结构文件类型文件存取文件属性文件操作6文件命名(FileNaming)文件是一种抽象机制。它们提供一种方法将信息存储在磁盘上，稍后再读出来。对用户来说，文件的实现必须隐藏信息的保存方式和位置以及磁盘的实际工作。(对用户半透明)文件的具体命名规则在各个系统中是不同的，不过全部操作系统都允许用1至8个字母组成的字符串作为合法文件名。7文件命名(FileNaming)典型的文件扩展名压缩文件file.zip一般文本文件file.txtTEX格式程序的输入file.texPostScript文件file.ps可移植文档格式文件file.pdf目标文件(编译程序的输出，尚未链接)file.objMPEG标准编码的电影file.mpgMPEGlayer3编码的音频压缩格式file.mp3JPEG标准编码的静态图片file.jpgWWW超文本链接标示语言文档file.html帮助文件file.hlp可交换的图像文件格式file.gifC语言源程序file.c备份文件file.bak含义扩展名8文件结构(FileStructure)文件结构有多种形式。通常的三种：字节序列记录序列树对于无结构的字节序列，操作系统不知道也不关心文件中是什么。它所看到的全部都是字节。任何意义都必须由用户级程序指定。UNIX和Windows都使用该方式。记录序列把文件看作定长的记录序列树：用于商业数据处理9三种类型的文件(a)字节序列(b)记录序列(c)树文件结构(FileStructure)10文件类型(FileTypes)一种分类：普通文件：包含用户信息的文件ASCII文件：可显示和打印二进制文件：有一定的内部结构，如可执行文件等。目录：系统文件，用于维护文件系统的结构。UNIX的一种分类字符特殊文件：与I/O相关的，用于建模诸如终端、打印机和网络等的串行I/O设备。块特殊文件：用于磁盘建模。11(a)可执行文件(b)存档文件文件类型(FileTypes)12魔数：很多类型的文件，其起始的几个字节的内容是固定的（或是有意填充，或是本就如此）。因此这几个字节的内容也被称为魔数(magicnumber)，因为根据这几个字节的内容就可以确定文件类型。Unix命令"file"

就是利用这个原理工作的。BSS：是“BlockStartedbySymbol”的缩写，意为“以符号开始的块”。BSS是Unix链接器产生的未初始化数据段。其他的段分别是包含程序代码的“text”段和包含已初始化数据的“data”段。BSS段的变量只有名称和大小却没有值。比如，在C语言之类的程序编译完成之后，已初始化的全局变量保存在.data段中，未初始化的或初始化为0全局变量保存在.bss段中。文件类型(FileTypes)13文件存取(FileAccess)早期操作系统只有一种文件存取方式：顺序存取(sequentialaccess)。进程在这些系统中可从开始处顺序读文件全部字节或记录，但不能跳过某一些内容也不能非顺序读取。当磁盘被用来存储文件后，可以非顺序地读取磁盘存储文件中的字节或记录，或按照关键字而不是位置来存取记录。这种能够以任何次序读取其中字节或记录的文件称作随机存取文件(randomaccessfile)。14顺序存取从起点读取所有字节/记录不能跳过,可以倒带或者倒退对于磁带媒介比较方便随机存取以任意次序读取字节/记录是数据库系统的根本所在可以下列方式读取文件:移动文件标记(seek)，然后读取读取，然后移动文件标记文件存取(FileAccess)15可能的文件属性该文件可能增长的最大字节数最大尺寸文件的字节数当前大小最后改变该文件的日期时间最后修改时间最后访问该文件的日期时间最后访问时间文件创建的日期时间创建时间关键字域的字节数关键字长度关键字在每个记录中的偏移关键字位置一个记录的字节数记录长度0表示未上锁；非0表示已锁定锁定标志0表示正常；1表示进程退出时删除文件临时标志0表示只能顺序存取；1表示随机存取随机存取标志0表示ASCII文件；1表示二进制文件ASCII/二进制标志0表示已经备份；1表示需要备份存档标志0表示一般文件；1表示系统文件系统标志0表示正常；1表示不显示在列表中隐藏标志0表示读/写；1表示只读只读标志当前所有者所有者创建该文件的人的ID创建者访问文件需要密码密码哪些人可以哪些方式访问文件保护含义属性文件属性(FileAttributes)16创建(Create)删除(Delete)打开(Open)关闭(Close)读(Read)写(Write)添加(Append)定位(Seek)获取属性(Getattributes)设置属性(SetAttributes)重命名(Rename)文件操作(FileOperations)17/*文件赋值程序。错误监测和报告已经尽可能地省略了。*/#include<sys/types.h> /*包含必要的头文件*/#include<fcntl.h>#include<stdlib.h>#include<unistd.h>intmain(intargc,char*argv[]); /*ANSI原型*/#defineBUF_SIZE4096 /*使用的缓冲区大小为4096字节*/#defineOUTPUT_MODE0700 /*输出文件的保护位*/intmain(intargc,char*argv[]){ intin_fd,out_fd,rd_count,wt_count;charbuffer[BUF_SIZE];if(argc!=3)exit(1); /*如果argc不是3，则语法错误*/使用文件系统调用的示例复制文件的简单程序(1/2)18/*打开输入文件，并创建输出文件*/in_fd=open(argv[1],O_RDONLY); /*打开源文件*/if(in_fd<0)exit(2); /*如果不能打开，则退出*/out_fd=creat(argv[2],OUTPUT_MODE); /*创建目标文件*/if(out_fd<0)exit(3); /*如果不能创建，则退出*//*复制循环*/while(TRUE){ rd_count=read(in_fd,buffer,BUF_SIZE); /*读入一个数据块*/ if(rd_count<=0)break; /*如果文件结束或者错误，退出循环*/ wt_count=write(out_fd,buffer,rd_count); /*写数据*/ if(wt_count<=0)exit(4); /*wt_count<=0为错误*/}/*关闭文件*/close(in_fd);close(out_fd);if(rd_count==0) /*最后的读没有错误*/ exit(0);else exit(5); /*最后的读有错误*/}使用文件系统调用的示例复制文件的简单程序(2/2)19目录(Directory)为了记录文件信息，文件系统通常有目录(directories)或者文件夹(folders)。在许多系统中，目录本身就是文件。目录包括其组织(organization)、属性(properties)以及作用于其上的操作(operations)。20目录(Directory)一级目录系统两级目录系统层次目录系统路径名目录操作21一级目录系统目录系统的最简单形式是使用一个目录包含所有的文件。有时候，称之为根目录(rootdirectory)，不过，由于只有一个目录，名字无关紧要。在早期的个人计算机上，这种系统非常普遍，部分原因是只有一个用户。非常有趣的是，世界上最大的超级计算机CDC6600，对于所有文件也只有一个目录，尽管它同时有多个用户使用。这个决断无疑是想保持软件设计的简单。22单层目录系统单层目录系统包含的4个文件，分别属于3个不同的人A、B和C。一级目录系统23两级目录系统为了避免不同用户为其自己拥有的文件取相同的文件名所导致的冲突，下一步就是给每个用户一个私有目录。这样，一个用户选择的名字不会干扰另一个用户的选择，而且在两个或多个目录中的相同名字不会发生问题。例如，这种设计可以用于多用户计算机或者通过局域网共享公用文件服务器的个人计算机的简单网络上。24两级目录系统图中字母表示目录和文件的所有者25层次目录系统双层目录系统消除了不同用户之间的文件名冲突，但仍然难以使有很多文件的用户感到满意。用户常常需要把文件按某种逻辑方式组织起来。最终我们需要的是一般的层次(即目录树)。采用层次结构，每个用户可以拥有多个所需的目录，自然地组织他们的文件。26层次目录系统目录树27路径名(PathNames)用目录树组织文件系统时，要某种方法指明文件名。常用的方法有两种：绝对路径名(absolutepathname)：绝对路径名是从根目录开始到文件的路径，且是唯一的。相对路径名(relativepathname)：它常和工作目录，也称作当前目录一起采用。是从当前目录到文件的路径。28UNIX目录树路径名(PathNames)29路径名(PathNames)绝对路径示例：(1)文件mailbox:/usr/ast/mailbox(2)文件dictionary：/usr/lib/dictionary相对路径示例：(1)当前目录:/ 相对路径：usr/ast/mailbox(1)当前目录:/usr 相对路径：ast/mailbox(1)当前目录:/usr/ast 相对路径：mailbox(1)当前目录:/usr/lib 相对路径：../ast/mailbox

30路径名(PathNames)每个目录中有两个特殊的目录项：.(一个点)：当前目录。..(两个点)：父目录。31目录操作创建(Create)删除(Delete)打开目录(Opendir)关闭目录(Closedir)读目录(Readdir)重命名(Rename)链接(Link)解除链接(Unlink)32文件系统的实现以上从用户角度考察文件和目录以下从实现者角度来考察文件系统。用户关心的是文件是怎样命名的、可以进行哪些操作、目录树是什么样的以及类似的界面问题。而实现者感兴趣的是文件和目录是怎样存储的、磁盘空间是怎样管理的以及怎样使系统有效而可靠地工作等等。33文件系统的实现文件系统布局文件的实现目录的实现共享文件日志结构文件系统日志文件系统虚拟文件系统34文件系统布局MBR：磁盘的0号扇区叫做MBR(MasterBootRecord，主引导记录)，用于启动计算机。分区表：位于MBR的尾部。多数磁盘可以划分为一个或多个分区，该表给出了每个分区的起点和终点地址。表中有一个分区被标记为活动的。计算机启动：BIOS读入并执行MBR。MBR程序首先确定活动分区，读入其第一块，即引导块(bootblock)，并执行它。引导块中的程序载入包含在该分区中的操作系统。35文件系统布局不同的文件系统磁盘布局不相同36实现文件文件的物理存储方法：连续分配(ContiguousAllocation)链表分配(LinkedListAllocation)使用内存表的链表分配(LinkedListAllocationUsingaTableinMemory)i-节点(i-nodes)37连续分配最简单的分配方案是把每个文件作为连续数据块存储在磁盘上。所以，在块大小为1K的磁盘上，50K的文件要分配50个连续的块。该分配方案有两大优势首先，简单、容易实现，记录每个文件用到的磁盘块简化为只需记住一个数字即可，也就是第一块的磁盘地址。其次，性能较好，在一次操作中，就可以从磁盘上读出整个文件。缺点：不能预知文件的长度，会造成磁盘碎片。适用于CD-ROM，文件长度已知且在使用中不会改变。38(a)分配给7个文件的连续磁盘空间(b)文件D、F被删除后的磁盘状态连续分配39链表分配存储文件的第二种方法是为每个文件构造磁盘块的链表。每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。优点：这类方法可以利用每个磁盘块。不会因为磁盘碎片而浪费存储空间。缺点：顺序读取文件非常方便，但是随机存取却相当缓慢。40链表分配将文件保存为磁盘块的链表41使用内存表的链表分配链表分配使用主存中的一个文件分配表42i-节点记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一张称为i-节点的小表，其中列出了文件属性和文件中各块在磁盘上的地址。43i-节点 UNIX文件系统，采用1KB的磁盘块大小和4B的磁盘地址。若I-节点包括10个直接块，一次、二次、三次间接块各一个，则此文件系统允许文件最大长度是？解：1KB的磁盘块，存放4B的地址号，每块可放1K/4=256个块号最大文件长度：(10*1K+1*256*1K+1*2562*1K+1*2563*1K)B44目录的实现打开文件时，操作系统利用用户给出的路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录系统的主要功能是把ASCII文件名映射成查找文件数据所需的信息。目录项的设计文件名磁盘地址文件属性45固定长度的目录项(a)包含固定大小项的简单目录，目录项中有磁盘地址和属性。(b)目录中的每一项只是对i-节点的引用。46长度不固定的目录项在目录中处理长文件名的两种方法(a)行方式(b)堆方式47共享文件(SharedFiles)当几个用户同在一个项目里工作时，他们常常需要共享文件。其结果是，如果一个共享文件同时出现在属于不同用户的不同目录下，工作起来就很方便。如下图，B目录与该共享文件的连接称为一个连接(Link)。文件系统本身是一个有向无环图(directedacyclicgraph)而不是一棵树。48共享文件(SharedFiles)包含一个共享文件的文件系统49实现共享文件的两种方法：硬链接：在UNIX系统中，只有I节点与文件本身关联，目录中有一个目录项指向该I节点，I节点中记录了有多少链接。如下图。符号链接：目录B中有一个目录项，指向一个类型为LINK的新文件，此文件中只包含了链接文件的路径名。共享文件(SharedFiles)50(a)链接前的状态(b)创建链接后(c)原所有者删除该文件后共享文件(SharedFiles)51日志结构文件系统随着CPU越来越快，内存越来越大磁盘Cache也越来越大来自Cache的读请求数增加大部分磁盘访问将是写操作LFS策略将整个磁盘构造成一个日志把所有写操作先缓冲在内存中定期将其写入磁盘日志的尾部打开文件时，定位i-节点，然后查找数据块52文件系统管理和优化磁盘空间管理文件系统备份文件系统的一致性文件系统性能磁盘碎片整理53磁盘空间管理文件通常存放在磁盘上，所以磁盘空间的管理是系统设计者要考虑的一个主要问题。存储n个字节的文件可以有两种策略：分配n个字节的连续磁盘空间，或者把文件分成很多个连续的块。在存储器管理中，单纯段式和分页也要进行同样的权衡。54块尺寸(BlockSize)一旦决定把文件按固定大小的块来存储，就会有一个问题：块的大小应该是多少?按照磁盘组织方式，扇区、磁道和柱面明显都可以作为分配单位。在页式系统中，页面大小也是主要选项之一。块很大，比如以柱面为分配单位，这时每个文件，甚至是1个字节的文件，都要占用整个一个柱面。磁盘空间利用率低块很小，则每读一块都有寻道和旋转时间。数据传输速率低55块尺寸(BlockSize)实线(左边刻度)给出一个磁盘的数据速率虚线(右边刻度)给出磁盘空间效率所有文件都是2KB。56块大小与磁盘数据率关系 设磁盘每道有128KB，旋转时间是8.33毫秒，平均寻道时间是10毫秒，若块大小是K字节，则数据传输率是多少?解：读取一块所需时间为：T=10+8.33/2+K/217*8.33(ms)数据率为：K/T(B/ms)K=512，数据率是：512*8/(10+4.165+512/217*8.33)=2.89*105bit/sK=1K，数据率是： 1024*8/(10+4.165+1024/217*8.33)=5.76*105bit/sK=2K，数据率是： 2046*8/(10+4.165+2046/217*8.33)=1.145*106bit/s57空闲块的记录一旦选定了块大小，下一个问题就是如何记录空闲块。广泛采用的是两种方法：第一种方法采用磁盘块的链表。每个块中包含尽有可能多的空闲磁盘块号。另一种空闲磁盘空间管理的方法是采用位映像。n个块的磁盘需要n位位映像。在位映像中，空闲块用1表示，分配块用0表示(或者反之)。58空闲块的记录(a)用链表保存空闲列表(b)位映像59空闲块的记录 设磁盘块大小为1KB，16bits磁盘地址，若磁盘容量为20MB，则共有20M/1K=20480个块，存放所有块号所需空间：用链表记录空闲块

一个磁盘块可以存放1KB/16-1=511个块号 全部磁盘块共需20480/511=40个块的空闲链表来存放位映像 20480个块需要20480bit的位图，则位图占用20480/1KB=20个块60空闲块的记录(a)指向空闲磁盘块的指针块在内存中，几乎全满；还有3个指针块在磁盘上。(b)释放一个3个块的文件后的结果。(c)另一种处理3个空闲块的策略。灰色的项表示空闲磁盘块的指针。61磁盘配额(DiskQuotas)为了防止人们贪心占有太多的磁盘空间，多用户操作系统，像UNIX，常常提供一种强行的磁盘配额机制。其思想是系统管理员分给每个用户拥有文件和块的最大数量，操作系统确保每个用户不超过分给他们的配额。当用户打开文件时，系统找到文件属性和磁盘地址，并把它们送人内存中的打开文件表。其中一个属性告诉文件所有者是谁。任何该文件大小的增长都记到所有者的配额上。62磁盘配额(DiskQuotas)在配额表中记录每个用户的配额63文件系统可靠性备份(Backups)文件系统一致性(FileSystemConsistency)64备份(Backups)即使有再好的处理坏块的策略，经常地备份文件也是很重要的。毕竟，在一些关键的数据块损坏之后，自动切换到备用块，无异于亡羊补牢。备份软盘上的文件系统很简单，只需把整个磁盘复制到一张空软盘上。物理转储(physicaldump)：转储所有的磁盘块逻辑转储(logicaldump)：只转储自某个时间以来被修改的文件和目录65备份(Backups)被转储的文件系统。方框表示目录，圆圈表示文件。灰色的项表示上次转储后被修改过。每个目录和文件都使用其i-节点号标记。66备份(Backups)算法：Step1:所有的目录和已修改的文件相应的I节点号在位图中被标记，如下图aStep2:其下没有包含被修改的子目录和文件的目录其I节点标记被删除，如下图bStep3:扫描位图，转储所有被标记的目录Step4:扫描位图，转储所有被标记的文件67逻辑转储使用的位映像备份(Backups)68文件系统一致性影响文件系统可靠性的另一个问题是文件系统的一致性。很多文件系统读取磁盘块，进行修改后，再写回磁盘。如果在修改过的磁盘块全部写回之前，系统崩溃，则文件系统有可能会处于不一致状态。如果未被写回的块是i-节点块、目录块或者包含空闲表的磁盘块时，这个问题尤为严重。系统启动时运行一个实用程序检查一致性，包括块一致性检查和文件一致性检查69块一致性检查方法 检查程序构造两张表，每个表为每个块设立一个计数器（初始化为0）。第一张表中计数器跟踪块在文件中的出现次数；第二张表中计数器跟踪块在空闲链表中出现次数。 检查程序读取全部的I节点，建立相应文件所使用的全部块的块号表。每读到一个块号，第1张表中该块对应计数器增1；检查程序检查链表（或位图），查找全部未使用的块，每找到一个，第二张表中该块对应计数器增1。70块一致性检查文件系统一致：每个块要么在第一个计数器中为1，要么在第二个计数器中为1文件系统不一致：两个计数器值都为0——丢失块第一个计数器值超过1——分配空闲块，将文件中内容写入空闲块第二个计数器值超过1——重建空闲表两个计数器中值都等于1——把块从空闲表中删除71块一致性检查文件系统状态(a)一致的(b)缺少的块(c)在空闲列表中复制块(d)复制数据块72文件一致性检查方法：

使用一张计数器链表，以I节点号索引，每个文件一个计数器。检查程序从根目录开始，沿目录树搜索，遇到一个文件，则相应计数器加1（符号链接不计）。搜索完毕，表中每个计数器表示此文件被多少目录所包含，并把此值与实际I节点中的链接数比较（文件创建时，链接数等于1）不一致实际链接数>计数器实际链接数<计数器73文件系统性能缓存提前读块(BlockReadAhead)策略减少磁盘臂移动(ReducingDiskArmMotion)74文件系统性能对磁盘的存取比对内存的存取要慢。读一个内存字可能花10纳秒。从硬盘读可能以10MB/sec进行，每32位的字要慢40倍，不过，还必须加上5-10毫秒的寻道时间，并且等待扇区旋转到磁头下。如果只需要一个字，内存存取要比磁盘存取快上100万倍。由于存取时间的这种区别，许多文件系统设计了各种优化方法来改进性能。75缓存用于减少磁盘访问的最通常的技术就是块缓存(blockcache)或者缓冲区缓存(buffercache)。Cache的发音为“Cash”，源自于法语的cacher，意即隐藏。在这里的上下文中，Cache是块的一个集合，逻辑上属于磁盘，不过由于性能的原因保存在内存中。76缓存高速缓存的管理：对于读操作，检查要读的块是否在高速缓存中，如果在，直接进行读操作不需访问磁盘；如果不在则首先将该块从磁盘读入缓存，再拷贝给用户。77缓存缓存中的块置换：如果缓存已满，要调入新块，则必须把某一块调出缓存。分页系统中的页面置换算法也适用于缓存。缓存的组织：为提高查找速度，建立一个哈希表，根据（设备号+磁盘地址）为哈希值索引，具有相同哈希值的块链接在一起。如下图78缓存(Caching)缓冲区cache的数据结构79提前读块(BlockReadAhead)第二种改进文件系统性能的技术就是试图在其需要前将块读入Cache中，以提高命中率。特别的，许多文件是顺序读取的。当请求文件系统在文件中产生块k时，它完成该请求，不过，当它完成时，它顺便检查Cache看块k+1是否在那里。如果不在，它设定读取块k+1，这样当需要它时，它已经在Cache中了。至少它将在途中了。80减少磁盘臂移动另一种增强文件系统性能的方法是通过把可能被顺序访问的块相互临近地放置，尽可能放在相同的柱面上，这样就可以减少磁盘臂的移动。当写入输出文件时，文件系统必须每次定位一块。如果空闲块记录在位映像中，而且整个位映像在主存中，那么就很容易选择一个与前一块尽可能接近的空闲块。如果使用空闲链表，其部份是在磁盘上，要定位接近的块就比较困难了。81文件系统实例CD-ROM文件系统ISO9660文件系统RockRidge扩展Joliet扩展MS-DOS文件系统UNIXV7文件系统82ISO9660文件系统最经常被采用的CD-ROM文件系统的标准是1988年发布的国际标准ISO9660。事实上，目前市场上的每个CD-ROM都兼容该标准，某些可能具有下面将提到的扩展。该标准的目标之一就是所有CD-ROM可以在每台计算机上读出来，与其使用的字节次序以及操作系统无关。因此，在该文件系统上加入了某些限制，使得可以在最弱的操作系统上(例如MS-DOS)使用。83ISO9660文件系统ISO9660文件系统的目录项84RockRidge扩展其扩展分为如下几个域：PX–POSIX属性PN–主设备和次设备号SL–符号链接NM–替代名CL–孩子位置PL–双亲位置RE–重定位TF–时间标签85Joliet扩展Joliet提供的主要扩充是：长文件名Unicode字符集深达8层的目录嵌套具有扩展名的目录。86MS-DOS文件系统第一印象认为，MS-DOS就是一个更大、更好的CP/M。它只能在Intel平台上运行，不支持多道程序，而且只能以PC的实模式运行(起初是其唯一的模式)。其外壳有更多特性以及更多的系统调用，但是，其基本的操作系统仍旧是载入程序、操作键盘和屏幕以及管理文件系统。87MS-DOS文件系统MS-DOS目录项88MS-DOS文件系统不同块尺寸的最大分区大小空格表示禁止的组合。2TB2048MB32KB2TB1024MB16