操作系统——文件系统.pptx

1第五章 文件管理2用户总是把长期要保存的或暂时要保存的大量信息，组织成文件的形式存放在辅助存储器中，成为计算机系统中的软件资源。用户希望的是能够“按名存取”。操作系统给我们提供了第五个功能-文件管理，主要有以下内容：5.1 文件管理基本理论5.2 Linux文件系统 5.3 Ext系列文件系统 5.4 虚拟文件系统 35.15.1 文件管理基本理论文件管理基本理论文件是具有名字的一组相关信息的有序集合，存放在外部存储器中。l组成：文件名+属性+文件体文件名：有限长度的字符串（注意DOS、Windows、Linux系统文件名）文件属性：包括文件类型、大小、物理位置、存取控制、建立或修改日期文件体：4文件分类不同的系统对文件的管理方式不同。按文件的性质和用途：系统文件，库文件、用户文件按文件中的数据形式：源文件，目标文件，可执行文件按存取权限：r,w,x按照文件的内容：普通文件，目录文件，特别文件（Linux系统中将设备也当作文件对待）5文件系统是操作系统的一个重要组成部分，实现文件管理的一组程序和所管理的全部文件（文件与目录的集合）以及管理文件所需要的一些数据结构的集合。文件系统通常以磁盘分区划分，每个分区对应一个独立的文件系统。文件系统管理的对象：文件+目录+磁盘存储空间对对象操纵和管理的软件集合：文件管理系统的核心部分。文件系统的功能（按名存取、存储空间管理、共享和保护等）大多是在这一层实现的。61 1 文件控制块文件控制块为了管理文件，文件系统为每个文件建立一个文件控制块(File Control Block，FCB)。nFCB记录了其的使用者和管理者所关心的所有信息（PCB？），包括文件名、大小、存储位置、修改和访问时间、权限等。n一个FCB就是一个文件目录项。n创建新文件时，建立FCB，随着文件的操作，FCB的内容动态更新，文件被删除时，其FCB删除。计算机系统中通常存有大量的文件，系统须采用某种有效的形式来组织和管理这些文件。由于文件与文件的FCB一一对应，因此，管理文件就是管理文件的FCB。2 2 目录目录n文件系统采用目录来组织文件。n目录是FCB的有序集合，通过目录将所有的FCB分层分类地组织在一起，方便了文件的检索操作。n目录本身需要长久保存的，也需以文件的形式存在，即目录文件，内容是一组FCB列表，每个表项（目录项）是一个文件的FCB。n由于目录本身也是文件，因此目录的FCB也可以作为另一个目录中的目录项，从而构成目录的层次关系。目录的主要功能之一 实现文件的“按名存取”n即用户只需提供文件名就可以对文件进行各种操作。在查找目录过程中，先将存放目录文件的第一个盘块中目录调入内存然后把用户所给定的文件名与目录项（每个文件的FCB）中的文件名逐一比较，若未找到指定文件，便将下一个盘块中的目录项调入内存。很显然，如果存放FCB的目录文件过大（占多个磁盘块），将会导致匹配文件名的过程要多次访问磁盘，导致问题产生的原因就是目录文件的每个目录项即FCB占空间，如何改善？！检索目录文件过程中只用到文件名，仅当找到一个目录项时才从该目录项中读出该文件的物理地址，而其它一些对该文件进行描述的信息在检索目录时不会用到，故这些信息不需调入内存。于是，可以将文件名和文件描述信息分开。引入索引结点！将文件目录中的每个目录项组成改为文件名和指向该文件所对应结点（索引结点，Index Node，I节点，其中存放文件描述信息单独形成)的指针所构成。引入I结点后，文件目录仅由文件名及指向该文件所对应的i结点的指针所构成。目录的主要功能之二 合理地组织文件。n单级目录：最简单的文件目录结构是在系统中建立一张目录线性表，每个文件占一表目，由文件名和文件的说明和管理信息组成（即其FCB或文件目录项）。单级目录能够单级目录能够实现实现“按名存取按名存取”，但存在，但存在查找速度慢；查找速度慢；不允许重名（主要问题）；不便于共享不允许重名（主要问题）；不便于共享等问题。等问题。n两级目录：系统设置一个主目录（MFD）后，再为每个用户设立一个用户目录（UFD）。MFD的每一项对应一个用户的目录文件，UFD每一项对应一个文件的FCB。n多级目录结构：将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构。系统中有一个根目录（或根目录文件），在这个目录中可登记一般文件，也可以登记目录文件，在每个目录文件中可以登记一般文件，也可以登记目录文件,现在，几乎所有的操作系统都采用树形目录结构3 3 文件的组织文件的组织文件的组织有两种：n文件的逻辑结构-用户对文件的组织方式，是指用户思维中文件的结构。n文件的物理结构-文件在存储介质上的组织形式，主要是指磁盘上文件的结构。文件的逻辑结构n记录式文件（有结构式文件）：文件是记录的集合，每个记录由彼此相关的域构成，记录可按顺序编号为记录1，记录2，又分定/不定长记录文件。n流式文件（无结构文件）：是相关的有序字符的集合，在其内部不再对信息进行组织划分，文件的长度为所含字符数。文件的物理结构一个文件存储介质，格式化后就分成许多大小相等的单位存储块（物理盘块），在现代计算机系统中，一般来说，每个物理块是一个磁盘的扇区，512字节。并给每个存储块有个编号，称为物理块号。文件的物理结构目前有三种基本结构，即连续文件结构、串联文件结构和索引文件结构。l连续文件结构：文件的数据存放在连续的物理存储块中。n优点：结构简单、实现容易n缺点：不利于文件动态扩充；创建文件时要求给出文件大小，用户不方便l串联文件结构：文件信息存于若干不一定连续的磁盘块中。每个物理块的最末一个字(或第一个字)作为链接字，指出后继块号。链首指针存在文件FCB中，文件的结尾块的指针为“”。n优点：文件动态扩充和修改容易（图中蓝线）;外存空间利用率高；n缺点：顺序存取效率高，随机存取效率太低，如果访问文件最后的内容，实际上是访问整个文件。（参考上图，理解这句话）n链接文件更适合于小型文件系统。为了克服串联文件的存取效率太低的问题，引入文件映照技术，即把串联文件中的链接字集中在一结构中。nDOS、WINDOWS系统采用（文件分配表）n文件分配表（File Allocation Table，FAT）磁盘格式化后建立，用于记录外存分配，FAT每个表项对应一个盘块（标记为0至N-1），其中用来存放分配给文件的下一个盘块号；放在内存中，整个系统一张FAT;分配给某文件的所有物理块都在该表中标出，文件的首块号记入FCB。显示链接。引入FAT的问题：FAT需占用较大的内存空间，只有将整个FAT表调入内存才能找到对应的盘块号。示例：若磁盘大小为1.2M，每个物理块大小为512B，则共有2.4K个FAT表项，则（回顾存储管理的单级页表的问题）l索引结构：不连续分配。每个文件建立一张索引表，每个表目指出文件内容与磁盘块号的对应关系 n索引结构是当代计算机操作系统中普遍采用的结构，如UNIX系统、LINUX系统。n优点：具备串联结构所有的优点，适合与随机存放n缺点：增加了索引的开销，存取文件时首先要取得索引表，这样就要增加一次访盘操作，降低了文件访问的速度索引表是在建立文件时由文件管理机构自动建立的，并存放在与文件相同的文件卷(如同一磁带或同一盘片)上。乍一看来，存取索引文件要访问2次外存（why?）。In fact!在访问索引文件之前，总是首先“打开”其对应的索引表文件，把其索引表文件的一部分读入主存，因此其后对文件的绝大多数访问只要1次访外。仅当更新索引表到另一部分时，才发生1次二度访外的情况。（回顾快表机制）（回顾页表地址映射）第1次访问索引表文件，第2次根据索引得到的物理块号再度访问外存。索引表是在建立文件时由文件管理机构自动建立的，并存放在与文件相同的文件卷(如同一磁带或同一盘片)上。乍一看来，存取索引文件要访问2次外存（why?）。In fact!在访问索引文件之前，总是首先“打开”其对应的索引表文件，把其索引表文件的一部分读入主存，因此其后对文件的绝大多数访问只要1次访外。仅当更新索引表到另一部分时，才发生1次二度访外的情况。（回顾快表机制）（回顾页表地址映射）第1次访问索引表文件，第2次根据索引得到的物理块号再度访问外存。Another Question!（回顾多级页表）引入多级索引和混合索引。混合索引应用 UNIX system 系统lUNIX system 混合索引动画演示l按文件的长度(占据数据块的个数)分为小文件、中文件、大文件、巨文件，分别对应直接、一次间接、二次间接、三次间接的编址方式。系统支持的最大文件=(10+256+2562+2563)512B4 4 文件存储空间的管理文件存储空间的管理无论程序还是数据都是以文件形式存放在外存上，外存上文件存放的空间叫作“文件存储空间”。l回顾内存空间的管理l对文件存储空间的管理工作包括：建立文件时为文件分配存储空间；删除文件时去配；以及修改文件时动态更新外存空间。l系统将外存空间分成若干大小相等的物理块，以块（or簇）为单位来交换信息。l文件存储空间的管理，实际上就是一个空闲块的组织和管理问题。三种常用的管理方法：空闲块表、空闲块链、位示图。空闲块表用空闲区表来管理文件存储空间，做法是系统设置一张表格，表中的每一个表目记录磁盘空间中的一个连续空闲盘区的信息。l表目的内容至少包括：空闲块区首块地址（物理块号）、空白块个数。l空闲块表适合于连续组织的文件，因为在分配文件时按文件尺寸申请一组连续的空闲块，撤消文件时归还这组连续的空闲块区。l与可变分区分配算法相似（回顾!），可采用最先适应、最坏适应、最佳适应算法。l由于空闲块区的个数是动态改变的，导致空闲块表目个数不能预先确定，因此可能会产生表目溢出(表较小时)或表目浪费(表较大时)。空闲块链把所有空闲块的块号用链表的形式连接在一起，适用于各种物理组织的文件。l注意，对空闲块链操作时应互斥。l需要分配空白块时从链首进行，所以在主存中要保存一个链首指针，它指向第一个空白块，当回收时，把回收块挂在空白块链尾上。位示图（bit map）位示图是外存空间的存储映射图，是系统在内存中划分出的若干字节的集合，用来指示磁盘存储情况。n采用位示图的具体做法是：为所要管理的磁盘设置一张位示图，位示图的大小，由磁盘的总块数决定。n位示图中的每一位（bit）对应外存空间的一个物理块。若该位为“1”，表示对应块被占用；“0”表示空闲。设整个文件空间有n块，那么可用n位构成位示图。例：设某磁盘组共有16个柱面，每个柱面有16个磁头寻道，每个磁道分16个扇区，整个磁盘空间的扇区数为：16*16*16=4096个 若一个扇区被定义为一个存储块，用字长16位的存储单元来构造位示图，共需要256个字。n分配：扫描位示图，找到足够的空闲块(对应位为“0”)分配，并将对应位改为“1”；n回收：将对应的位改为“0”即可。n位示图较小，系统启动时进入内存（全部或部分），因此可实现高速的分配。NOTE!：必须定时地把主存中的位示图复制到外存保存，以防万一文件系统发生故障，可以依据外存的位示图副本修复文件系统。UNIX系统系列磁盘空间管理方法 成组链接法UNIX系统采用空闲块成组链接法对磁盘空间的空闲块加以组织。l每100个空闲块划归1组，将各组中的盘块号存放在其前组中的第1个空闲块中，第1组的空闲盘块号放入系统专用的超级块(superblock)中。l第1组不足100块，文件存储空间不会恰好为100的整数倍，所以第1组小于100。l最后组99块，若把超级块看作是最后组的成员，则最后组也是100块。l其他各组均为100块。Important!l各组第1块和超级块：登记了下一组的盘块号。对应设置一个容量为100的堆栈，另设一个栈指针指向栈0单元，栈1单元，其内保存空闲块号。如果当前栈顶上升到栈99，那么意味着下1组有100个空闲块被链接在一起。l最后组第一块：null标志。空闲块的分配和回收通过栈指针的变化(栈0栈99)来体现。l分配超级块是否上锁，是则等待，否则上锁后转；从栈指针指向的栈顶取得空闲块号，若当前栈顶不是栈0单元，则转。否则该块是组中的第1块。而第1块不能直接分配，故转；栈指针退1，置超级块修改标记并解锁，分配该空闲块号给调用者，返回；把该块内容复制到超级块中，置超级块修改标记并解锁，把该块分配给调用者，返回。l回收超级块是否上锁，是则等待，否则上锁后转若栈未满(栈指针栈99)则转，否则转栈指针进1，空闲块号存入栈顶单元，置超级块修改标记并解锁后返回；把超级块内的栈复制到当前回收的空闲块中，再将该新空闲块号填入超级块中栈0单元，使栈指针指向栈底，置超级块修改标记并解锁后返回。注意，此时形成了1个新的空闲块组，该组的第1块正是刚回收的空闲块。成组链接法-动画演示成组链接法的优势l空闲块成组链接法不占用额外空间，只是临时借用每组的第1块登记下一组的空闲块号。l分配与回收工作几乎都在主存(超级块)中进行，仅当分完1组或收回满1组时才启动I/O通道工作。所以该方法在空间、时间开销方面相当节省。5.2 Linux文件系统 Linux继承了Unix文件系统的优秀设计，并结合了一些现代文件系统的先进技术，在开放性、可扩展性和性能方面都十分出色。Linux文件系统的几个主要特征。n支持多种文件系统：DOS、Windows等OS只支持一种或几种专用的文件系统，而Linux可以支持几乎所有流行的文件系统，使得Linux可以和许多其他OS共存，允许访问其他OS分区中的文件。n树型可挂载目录结构：Linux采用树型目录，并引入分区挂载的概念，系统分区上的文件系统称为根文件系统，其他所有分区的文件系统都要挂载(mount)到根文件系统的某个目录下。n文件、设备统一管理：Linux将设备抽象为文件。Linux使用标准的树型目录结构，无论操作系统管理几个磁盘分区，这样的目录树只有一个。EXT系列是Linux的标准文件系统，系统把它的磁盘分区做为系统的根文件系统，EXT以外的文件系统则安装(mount)在某个目录下，成为系统树型结构中的一个分枝。1 Linux文件系统的结构设计 Linux文件系统采用分层结构的设计，包括：n磁盘I/O系统层n磁盘高速缓存n磁盘文件系统层（也称实际文件系统）n虚拟文件系统n磁盘I/O系统层：是文件系统所依赖的底层模块，用于实现对存储在磁盘上的文件数据的I/O操作，由通用块层、I/O调度程序和设备驱动程序构成。n实际文件系统：Linux默认FS是Ext2-4，支持多种FS。Linux专用：Ext2-4、JFS、XFS、RFS和NFS；Unix：sysv、ufs、bfs；Minix：minix、XIA；Windows或DOS：FAT、NTFSn虚拟文件系统：为了屏蔽各个文件系统之间的差异，为用户提供访问文件的统一接口，Linux在具体的文件系统上增加了一个称为虚拟文件系统(Virtual File System，VFS)的抽象层，使得不同的文件系统按照同样的模式呈现在用户面前。n磁盘高速缓存：回顾前述知识。5.3 Ext系列文件系统 nExt2(Extended-2)：是专为Linux系统设计的,采用的是Unix文件系统的设计思想，运行稳定，存取效率也很高，可支持最大4TB(1T=1024G)的磁盘分区。2000年以前一直是几乎所有的Linux发行版的默认的文件系统。Ext2的弱点在于它是一个非日志文件系统，所以不能在系统发生断电或者其他系统故障时保证文件数据的完整性。nExt3：是一个基于Ext2开发的日志文件系统，具有健全的日志功能，可靠性很高。在非正常关机后，文件系统可在数十秒钟内自行修复。Ext3容量达到32TB，单个文件最大2TB。目前Ext3已被许多Linux发行版作为默认安装的文件系统。nExt4：最显著的改进是文件和文件系统的大小。Ext4容量达到1024PB(1P=1024T)，而文件大小则可达到16TB。1 Ext文件的结构Ext文件的逻辑结构是无结构的流式文件。基于字节流的概念，使得Linux系统可以把目录、设备等都当作文件来统一对待。Ext文件的物理结构采用易于扩展的多重索引方式，便于文件动态增长，同时也可以方便地实现顺序和随机访问。Ext文件系统引入索引节点（i节点）来描述文件，Ext文件的FCB分为i节点和目录项两部分描述。n目录文件的各目录项(directory entry）仅由文件名和i节点号（指向该文件的其它属性）构成。ni节点占用一个单独的存储块，包含文件说明信息（属性）和索引表（指向磁盘块）两部分，i节点毁坏则整个文件不可用。Ext3文件的物理结构采用了多重索引方式，i节点中的索引表描述如右图。n索引表011项直接指向磁盘块，称为直接块。n12项是一个指针，指向一个间接索引表，间接索引表中的指针指向数据块（称为间接块）。n同理13项（二次间接）、14项（三次间接）。示例：Ext2文件系统的默认块大小1KB，则12K以下的小文件，不需要使用间接索引。大的文件，需要用到间接索。设每个指针占4字节，则一个间接索引表含有256个指针，对应256个间接块。因此，大小在12K268K的文件需要一次间接，同理，更大的文件使用二次间接甚至三次间接指针，得到最大约16GB的文件。2 Ext目录文件同普通文件一样，每个目录文件对应一个目录项(在其父目录中)以及一个i节点，不同的是，其数据块中存放的不是文件内容而是目录项集合，包含了该目录下的所有文件的目录项（i节点号和文件名）。n头两个目录项是“.”和“.”。示例：目录A下含有子目录B和文件C、D、E。注意：文件D和E共享3 Ext文件定位以查找Linux系统中/home/zhuge/memo文件为例，实现按名查找。5.4 虚拟文件系统(VFS)虚拟文件系统是Linux内核中的一个软件层，用于给用户空间程序提供文件系统接口。它也提供了内核中的一个抽象功能 允许不同的文件系统共存。nVFS只存在于内存中，在系统启动之后才建立完成，并在系统关闭时撤销。VFS必须和实际文件系统一起才能构成一个完整的文件系统。nVFS屏蔽了各种实际文件系统的差异，为用户提供了一种标准的文件操作接口。1 VFS构成VFS用C语言编写，采用面向对象的程序设计思想，用统一的数据结构在内存中描述各种实际文件系统，包括：nVFS超级块(super block)：描述文件系统的基本信息，对应实际文件系统的超级块。nVFS目录项(dentry)：描述文件的路经分量。nVFS索引节点(inode)：描述文件的信息，对应文件的磁盘i节点。nVFS文件(file)：描述一个打开的文件，包括文件的当前使用信息。2 VFS与进程接口VFS为进程提供了访问文件系统的统一接口。接口由fs_struct和file_struct结构构成。nfs_struct用于建立进程与文件系统间的联系，主要包括文件系统的根目录和当前目录等信息。nfile_struct用于建立进程和所有该进程打开的文件之间的联系。3 VFS缓存机制缓存是在内存中开辟的存储区，用于存放那些可能会重复使用的数据，提高效率。n当VFS需要构造某个对象或存取磁盘数据时，先在缓存中查找。若有就直接使用，否则再启动I/O操作，传输数据，构造对象。nVFS采用如下缓存机制：dentry/inode缓存：用于缓存dentry和inode对象。页面缓存：用于缓存文件的内容。页面缓存：文件的inode对象将文件内容按位置映射到页面缓存中。读写文件时直接访问页面缓存，只在必要时才启动I/O操作，完成磁盘中与缓存间的数据传输。4 文件系统的操作用户进程使用VFS提供的一组系统调用来进行文件操作，VFS负责将这一组系统调用映射到实际文件系统的文件操作函数上。这是通过在VFS的超级块、目录项、i节点和文件结构中的操作集来实现的。n这些操作集统一地定义了对超级块、目录项、i节点和文件的所有操作的接口，它们通过函数指针连接到文件系统的某个操作函数上，完成具体的文件操作。打开文件OPEN：根据文件的路径名找到该文件的dentry、inode和file对象，在进程的file_struct结构中找到一个空闲的fd数组项，将file对象连到该表项中，返回该表项的下标，这个下标就是该打开文件的文件描述符。n若文件已经打开(被其他进程打开)，则其file结构已存在。此时只需找到该文件的file结构，将其连到本进程的file_struct中的fd上，并将file结构中的引用计数f_count加1，返回fd数组项的下标即可。关闭文件close：断开进程与该文件之间的连接，即释放该文件的file结构在file_struct表中占用的fd，将f_count减1，若为0释放file结构。读read/写write文件：文件在读/写前必须是已经打开的，系统通过fd的值在进程的file_struct中检索fd数组，得到文件的file结构和i节点，根据file结构中的f_mode和i节点中的i_mode检查文件的访问权限，然后通过file结构的f_op找到read()或write()操作函数，用这个函数完成数据的读/写。n读/写操作的起始位置是file结构中的当前文件位置标志f_pos（打开之初其值=0，读/写操作过程中动态更新）。用lseek()设置f_pos的值。END OF THIS CHAPTER