操作系统文件管理

第八章文件管理文件和文件系统文件逻辑结构外存分配方式目录管理文件存储空间的管理文件共享与文件保护数据一致性检查程序和数据以文件的形式存储在外存中。文件系统，作为操作系统中的一个重要组成部分，负责文件的组织、存储和访问。本章的主要内容是文件的组织结构，文件系统空间管理以及文件的共享与保护。§8.1文件和文件系统文件系统的引入：所有的计算机应用程序都要：存储信息和检索信息三个基本要求：能够存储大量的信息长期保存信息可以共享信息解决方法：把信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。而文件是通过文件系统来管理的，包括：文件的结构，命名，存取，使用，保护和实现方法。文件系统：是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。两种观点用户观点：最基本的功能是实现了按名存取。另外，文件系统还应提供：一个文件由什么组成，如何命名，如何保护文件，可以进行何种操作等等。操作系统观点：文件目录怎样实现，怎样管理存储空间，文件存储位置，磁盘实际运作方式(与设备管理的接口)等等。基于文件系统的概念，数据的组成可有三级：数据项记录文件一、文件、记录和数据项1、数据项1）基本数据项：描述一个对象属性的字符集。是最小逻辑数据单位。称为原子数据、数据元素、字段。基本数据项有型（数据项的名字、类型等）值（某实体的具体数据）2）组合数据项：由若干个基本数据项组成。2、记录：一组相关数据项的集合。描述一个对象某方面的属性。用关键字来唯一标识一条记录。3、文件：具有文件名的一组相关信息的集合。描述一个对象集。有结构文件：由若干相关记录组成。无结构文件：字符流文件。4、文件的属性：1）文件类型2）文件长度3）文件物理位置4）文件的存取控制5）文件的建立时间二、文件类型许多OS中用文件的扩展名表征文件类型。1.按用途分系统文件用户文件库文件（由标准子程序及常用的例程等构成的文件，允许调用，不允许修改）2.按文件中的数据形式分：1）源文件：由源程序和数据构成的文件2）目标文件：编译后的二进制代码文件3）可执行文件：目标文件链接后形成的文件3按存取控制属性分：只执行文件、只读文件、读写文件4按文件的逻辑结构分（从用户角度出发所观察到，是用户可以直接处理的数据及形式）：有结构文件（记录式文件）、无结构文件5按文件的物理结构分（文件存储结构，文件在外存上的存储组织形式）：顺序文件、链接文件、索引文件三、文件系统模型对象及其属性说明：对象包括文件、目录、磁盘存储空间对对象进行操纵和管理的软件集合（核心）文件系统的功能有：存储空间的管理；文件目录的管理；地址映射；文件的读写管理；文件的共享与保护文件系统的接口：命令接口、程序接口图6-2文件系统模型四、文件操作1.对记录的操作：检索所有记录；检索单个记录；插入、修改、删除一个记录。2.对文件的操作基本操作：文件的创建（分配外存、建立目录项）、删除、读、写、截断、设置文件的读写位置。文件的打开和关闭设置和修改文件的属性建立、修改和删除目录文件的打开和关闭当前OS对文件的操作过程可分为两步：检索文件目录找到指定文件的属性及其在外存上的位置；对文件实施相应的操作。为避免多次重复检索目录，当用户第一次请求对某一文件进行操作时，先利用Open系统调用将该文件打开。“打开”的含义：系统将文件的属性（目录信息）从外存复制到内存打开文件表中，并返回该表目的编号给用户，建立了用户与文件间的联系。以后若再访问此文件，则利用编号直接在内存中检索，从而节省大量的检索开销，提高了文件的操作速度。“关闭”的含义：当用户不再需要对该文件的操作时，OS将会把该文件从打开文件表中的表目上删除掉，从而切断用户与文件间的联系。§8.2文件逻辑结构文件的逻辑结构（文件组织）：从用户观点出发观察到的文件全貌，用户用这种逻辑结构形式来实现存储、检索和加工文件中的数据。它可以独立于在外存上的物理存储。文件的物理结构（文件的存储结构）：系统设计人员看待文件时要考虑文件具体在存储设备中如何放置、如何组织、如何实现存取等细节，这与存储介质的存储性能有关。（分为顺序、链接及索引结构）注：文件的逻辑结构和物理结构都将影响文件的检索速度。文件逻辑结构的设计要求：访问性能：便于检索、便于修改存储性能：向物理存储转换方便，最小的文件存储空间。一、文件逻辑结构类型有结构文件：由至少一个记录组成的文件。无结构文件：即流式文件。1、有结构文件：由至少一个记录组成的文件。按照记录长度划分：定长记录：所有记录的长度是相同的。变长记录：各记录的长度不相同。指数据项数目不同或数据项本身长度不定。按照记录组织方式划分：顺序文件：一系列记录按一定顺序排列成的文件。常是定长记录。索引文件：为每条记录设置一表项，以记录该记录的信息。常是变长记录。索引顺序文件：以记录分组，每组内为顺序的；每一组设置一个表项，形成索引表。2.无结构文件即流式文件构成文件的基本单位是字符。不划分记录，顺序访问，每次读写访问可以指定任意数据长度。是当前操作系统中常用的文件组织。如源程序、库函数等。二、顺序文件1.逻辑记录的排序串结构：根据记录生成的先后顺序排列。顺序结构：记录按关键字排列。2.对顺序文件的读或写操作若顺序文件中的记录是定长的，则有当前记录的逻辑地址，就可得出下一记录的逻辑地址。设读指针为Rptr，则Rptr:=Rptr+L（L为记录长度）；写指针为Wptr，则Wptr:=Wptr+L而在变长记录文件中，L要换成Li，为刚读（写）完记录的长度。R0R1R2R3…Ri…LLLLLL2L3L4LL(i＋1)LRptr(a)定长记录文件L0R0L1R1…Ri…Wptr(b)变长记录文件Li00L0L0＋1L1L0＋L1＋2Li∑(Lk＋1)i－1k＝0∑(Lk＋1)ik＝0图6-3定长和变长记录文件每个记录前面用1个单元存放记录长度3顺序文件的优缺点优点：批量存取时效率高，可存储在磁带上；对定长记录，还可方便实现直接存取。缺点：对变长记录，直接存取低效，对某一记录操作时，查找费时多；增加或删除记录时，实现困难。三、索引文件引入:为解决变长记录文件的直接存取低效问题。对于顺序结构文件，若是定长记录，则第i个的位置可看作Ai=i×L；而若是变长记录，则需iLiAii1i解决方法：为变长记录建立一张索引表，每个记录在索引表中占一项，如图。索引项按照记录中的某个关键字域排序，索引表本身是一个定长记录的顺序文件，易于直接存取某一项。检索过程：根据提供的关键字值，查找索引表（可用顺序或折半等方法）。找到该记录对应的表项，根据指向记录的指针值访问记录。优点：记录大小不必相同，不必排序，索引文件的记录项通常较小，查找速度快，便于随机访问(randomaccess)；易于进行文件的增删。缺点：索引表的存在，占用了存储空间。索引号0长度m指针ptrm01m1…imi…索引表R0R1…Ri…逻辑文件图6-4索引文件的组织四、索引顺序文件将所有记录分为若干组，建立一张索引表，表项中记录每组中第一条记录的信息，如该记录的关键字值、指向该记录的指针。每一组和整个大文件都应是按关键字顺序排列的。键AnQiBaoRongChenLin逻辑地址姓名AnQiAnKang其它属性BaoRong…逻辑文件检索过程：根据提供的关键字值，先查找索引表（可用顺序或折半等方法）。找到该记录所在记录组的第一个记录的表项，读相关表项，找到该记录在文件中的位置。再顺序查找文件，以得到要找的记录。索引顺序文件即把原顺序文件分组、分级，可减少查找次数。若记录个数很多时，也可建立多级索引，把索引表文件再建立索引表。索引文件与索引顺序文件的区别在于索引文件中主文件不排序。6.直接文件和哈希文件直接文件：根据记录键值，直接获得指定记录的物理地址。问题：如何实现键值到物理地址的转换？一种实现方式：哈希文件记录位置由哈希函数确定。检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。要求记录大小相同。访问速度快。§8.3外存分配方式为文件分配外存的时候要考虑：有效地利用外存空间提高对文件的访问速率常用的外存分配方法有：连续分配链接分配索引分配一个系统通常采用一种分配方式.一、连续分配为每一个文件分配一组相邻接的盘块。通常位于一个磁道上。操作时，磁头较少移动。将逻辑文件中的记录顺序地存储到邻接的各物理盘块中，形成的物理文件称为“顺序文件”。顺序文件保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。在FCB中记录该文件第一个记录所在的盘块号和文件长度（盘块数）。count311457282420161283291317212529610141822263011151923270maillistftr目录Filecounttrmaillistfstart01419286length23642图6-7磁盘空间的连续分配长时间使用后，出现外存的外部碎片。可以通过紧凑将外存空闲空间合并成连续的区域。优点：1）支持顺序访问和直接访问。2）顺序访问速度快，所需的磁盘寻道次数和寻道时间最少。缺点：1）要求连续的存储空间，有碎片产生。2）须事先知道文件的长度，预留空间:浪费。二、链接分配一种离散的分配方式。指将文件装到多个离散的盘块中，通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表。这样形成的物理文件称为“链接文件”。类型：隐式链接显式链接1.隐式链接：每个盘块中都有指向下一个盘块的指针。文件目录的目录项中含有指向链接文件第一个盘块和最后一个盘块的指针。如图：优点：提高了磁盘空间利用率,不存在外部碎片问题；有利于文件插入和删除；有利于文件动态扩充。缺点：存取速度慢，不适于随机存取；可靠性较差，如指针出错；更多的寻道次数和寻道时间；链接指针占用一定的空间。22181410623127231915117304812162024281591317212529302611016-125目录Filestartendjeep925图6－8磁盘空间的链接式分配2.显式链接将链接文件各物理块的指针，显式地存放在内存的一张链接表中，该表也称为FAT（文件分配表）。整个磁盘有一张链接表。表项序号为物理盘块号，表项中存放链接指针，即同一文件的下一盘块号。每个文件的链首盘块号记入FCB中。它常驻内存，以提高检索速度，减少了访问磁盘的次数。（如DOS）缺点：不能高效地直接存取；FAT需占较大的内存空间(数兆以上)。FCB２FAT物理块号０４５１012345图6-9显式链接结构MS-DOS的文件物理结构如图：每个文件的第一个盘块号放在自己的FCB中。整个系统有一张文件分配表FAT。在FAT的每一个表项中存放下一个盘块号。对于1.2MB的软盘，盘块的大小为１KB，每个FAT表项占12位，在每个FAT中共含有1.2K个表项，共需1.8KB。而对200MB的硬盘，共含200K个盘块，如果FAT的每个表项需2.5个字节，需占用500KB。４９FCBAFCBBFAT65EOFEOF101101234567891011三、索引分配1.单级索引分配：一个文件的信息存放在若干不连续物理块中，为每个文件建立一个专用数据结构－索引块（表），用来记录分配给该文件的所有盘块号。在文件的FCB中填入指向该索引块的指针。如图：文件由数据文件和索引表组成，称为索引文件。对文件进行操作时，通过FCB得到索引块的块号，读索引块中的内容即可找到该文件在硬盘中的位置。优点：即能顺序存取,又能直接存取；所占盘块不连续，是一种离散分配方式，不产生外部碎片；。缺点：索引表本身带来了系统开销，当文件较小时，是一种外存空间的浪费。1230567491011813141512171819162