操作系统CH06.

第6章：文件系统吕鸣松（讲师）东北大学信息科学与工程学院[e-mail]《操作系统原理》2013年春季课程NortheasternUniversity主要内容•什么是文件与文件系统•文件的逻辑结构•外存分配方式•目录管理•文件存储空间的管理•文件的共享与保护•数据一致性检查《操作系统原理》——东北大学第6章文件系统2主要内容•什么是文件与文件系统•文件的逻辑结构•外存分配方式•目录管理•文件存储空间的管理•文件的共享与保护•数据一致性检查《操作系统原理》——东北大学第6章文件系统3文件、记录与数据项•数据项：是最低级的数据组织形式–基本数据项：用于描述一个对象的某种属性的字符集，又称数据元素或字段–组合数据项：由若干个基本数据项组成•记录–是一组相关数据项的集合，描述一个对象在某方面的属性•文件–由创建者所定义的、具有文件名的一组相关元素的有序集合《操作系统原理》——东北大学第6章文件系统4文件、记录与数据项•文件是具有名字的数据项的集合–文件名：文件的标志符号–文件体：文件本身的信息–文件说明：文件存储和管理信息，如：文件名、文件内部标识、文件的存储地址、访问权限、访问时间等–文件的属性：文件类型、文件长度、文件的物理位置、文件的建立时间《操作系统原理》——东北大学第6章文件系统5文件、记录与数据项•三者的关系《操作系统原理》——东北大学第6章文件系统6文件记录1记录2记录m…数据项1数据项2数据项n…文件类型•按用途分–系统文件、用户文件、库文件•按数据形式分–源文件、目标文件、可执行文件•按存取控制属性分–只执行文件、只读文件、读写文件•按组织形式和处理方式分–普通文件：ASCII码或二进制码组成的字符文件–目录文件：由文件目录组成–特殊文件：系统中各类I/O设备《操作系统原理》——东北大学第6章文件系统7文件系统模型《操作系统原理》——东北大学第6章文件系统8文件系统接口对对象操纵和管理的软件集合对象及其属性用户（程序）命令接口、程序接口对文件存储空间的管理对文件目录的管理逻辑、物理地址转换机制文件读写管理文件共享与保护文件、目录、磁盘存储空间文件系统模型•基本操作–创建文件、删除文件、读文件、写文件、截断文件、设置文件读写权限•文件打开与关闭•其它操作–对文件属性的操作–对目录的操作–系统调用等《操作系统原理》——东北大学第6章文件系统9文件系统层次结构《操作系统原理》——东北大学第6章文件系统10磁盘设备驱动程序磁带设备驱动程序基本文件系统基本I/O管理程序逻辑I/O堆顺序索引顺序索引哈希用户程序负责启动该设备上的I/O操作，处理I/O请求的完成处理与磁盘或磁带交换的数据块负责所有文件I/O的开始或结束使用户和应用程序能够访问到记录在应用程序和文件系统及保存数据的设备之间提供了一种标准接口数据块记录文件系统层次结构《操作系统原理》——东北大学第6章文件系统11文件结构用户和程序命令操作，文件名目录管理用户访问控制访问方法文件操作函数记录组块主存缓冲区中的物理快辅存(磁盘)中的物理快磁盘调度文件分配自由空间管理I/O文件管理关注的问题操作系统关注的问题主要内容•什么是文件与文件系统•文件的逻辑结构•外存分配方式•目录管理•文件存储空间的管理•文件的共享与保护•数据一致性检查《操作系统原理》——东北大学第6章文件系统12文件分类•按存放时限分类–临时文件、永久文件、档案文件•按设备类型分类–磁盘文件、磁带文件、卡片文件、打印文件•按文件的组织结构分类–逻辑结构：从用户观点出发观察到的文件组织–物理结构：文件的存储结构，即文件在外存的存储组织形式《操作系统原理》——东北大学第6章文件系统13文件分类《操作系统原理》——东北大学第6章文件系统14文件组织结构逻辑结构物理结构有结构文件无结构文件累积文件顺序文件索引顺序文件索引文件索引结构连续结构链接结构无结构文件•文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度•当前操作系统中常用的文件组织《操作系统原理》——东北大学第6章文件系统15累积文件（Pile）•文件体为无结构记录序列•通过分隔符来划分记录•各记录大小和组成可变•新记录总是添加到文件末尾，如日志log，或电子邮件的邮箱•检索必须从头开始•是一种简单的文件组织方式，当数据难以组织时使用《操作系统原理》——东北大学第6章文件系统16顺序文件•文件体由“大小相同、格式固定的排序记录序列”–由一个主文件和一个临时文件组成–记录按某个关键字域排序，存放在主文件中–新记录暂时保存在临时文件中，定期归并入主文件，并按正确顺序产生一个新文件–访问时需要顺序搜索——慢《操作系统原理》——东北大学第6章文件系统17索引顺序文件•在顺序文件基础上，另外建立索引和溢出文件–在索引文件中，可将关键字域中的取值划分若干个区间，每个区间对应一个索引项，后者指向该区间的开头记录–新记录暂存于溢出文件中，定期归入主文件，需调整索引《操作系统原理》——东北大学第6章文件系统18关键字逻辑地址ABZ索引文件姓名其它属性AnBingAnKangAnQingBaoRongBiJingBonLong主文件（顺序文件）索引文件•基本特征–主文件由记录组成，记录大小不必相同，不必排序，存放于主文件–另外建立索引，每个索引指向一个记录，索引项按照记录中的某个关键字域排序–对同一主文件，针对不同关键字域建立多个索引–索引文件的记录项通常较小，查找速度快，便于随机访问《操作系统原理》——东北大学第6章文件系统19哈希文件或直接文件•基本特征–由主文件和溢出文件组成–主文件由大小相同的记录组成–一个记录在文件中的位置，由哈希函数确定•addr=f(id)–访问速度快，通常一次只访问一条记录《操作系统原理》——东北大学第6章文件系统20文件的存取•“读”和“写”–读：存储介质内存–写：内存存储介质•顺序存取–按照文件信息的逻辑顺序依次存取，如，为存取记录Ri，必须先扫描过记录R1R2…Ri-1•随机存取（直接存取）–可以按照任意次序对文件进行读写操作，如可根据记录的编号来直接存取文件中任何一个记录•索引存取–对文件中的记录按某个数据项的值进行排列，从而可以根据键值来快速存取《操作系统原理》——东北大学第6章文件系统21主要内容•什么是文件与文件系统•文件的逻辑结构•外存分配方式•目录管理•文件存储空间的管理•文件的共享与保护•数据一致性检查《操作系统原理》——东北大学第6章文件系统22连续分配•原理–为每个文件分配一组相邻的磁盘块–只需记录第一个块的地址和总块数–优点：顺序访问，速度快–缺点：需要足够大的连续空间，文件长度事先已知《操作系统原理》——东北大学第6章文件系统23文件目录文件名起始块长度FileA23FileB95FileC188FileD302FileE263链接分配•隐式链接分配：在每个块中维护指向下一个块的指针《操作系统原理》——东北大学第6章文件系统24文件目录文件名起始块最后块………FileB128………适用于连续访问链接分配•显示链接分配–把用于链接物理块的指针显式的存放在内存的一张连接表中《操作系统原理》——东北大学第6章文件系统25文件目录文件名起始块最后块………FileB128………0123481428814328-1............物理块号FAT链接分配•例子–设磁盘块大小为1KB，硬盘大小为500MB，采用显式连接分配方式时，其FAT表需占多少存储空间？如果文件A占用硬盘的第11、12、16、14四个盘块，试画出文件A中各盘块间的链接情况及FAT的情况–总块数：500*1024，每个块需要19位二进制来表示《操作系统原理》——东北大学第6章文件系统26文件名起始块最末块………A1114………1112131415161216-114............FAT索引分配•单级索引分配–文件的第一个簇中记录了该文件的其他簇的位置《操作系统原理》——东北大学第6章文件系统27文件目录文件名索引块……FileB24……索引分配•多重索引分配–将一个大文件的所有索引表（二级索引）的地址放在另一个索引表（一级索引）中《操作系统原理》——东北大学第6章文件系统283607401125...105106254356357985360740......105106254255356主索引二级索引磁盘空间索引分配•混合索引分配：结合多种分配方式《操作系统原理》——东北大学第6章文件系统29索引数组i-addr[i]文件信息文件信息...文件信息...文件信息中型文件5KB-90KB...文件信息文件信息大型文件90KB-14.54MB...文件信息文件信息巨型文件14.54MB-1GB...文件信息一次间址二次间址三次间址索引分配•UNIX混合索引分配《操作系统原理》——东北大学第6章文件系统30文件最大支持：10+256+2562+2563个物理块每块存放256个物理块号地址主要内容•什么是文件与文件系统•文件的逻辑结构•外存分配方式•目录管理•文件存储空间的管理•文件的共享与保护•数据一致性检查《操作系统原理》——东北大学第6章文件系统31目录管理的要求•实现“按名存取”–用户只需向系统提供所需访问的文件名字，便能快速准确地找到指定文件在外存上的存储位置•提高对目录的检索速度–通过合理地组织目录结构予以实现•文件共享–允许多个用户共享一个文件•允许文件重名–允许不同用户对不同文件采用相同的名字，对相同文件采用不同的名字《操作系统原理》——东北大学第6章文件系统32文件控制块和索引节点•主要功能–用于描述和控制文件的数据结构，文件管理系统借助其中信息，对文件实施各种操作–文件与文件控制块一一对应，文件控制块的有序集合称为文件目录，一个文件控制块即为一个文件目录项•包含三类信息–基本信息：文件名、文件物理位置、文件逻辑结构、文件物理结构–存取控制信息：各类用户的存取权限–使用信息：文件的建立日期和时间、上次修改的日期和时间、当前使用信息（已打开文件的进程数、是否被其他进程锁住、文件在内存中是否已被修改但尚未拷贝到盘上、…）《操作系统原理》——东北大学第6章文件系统33文件控制块和索引节点•索引节点–目标是实现文件名与文件描述信息的分离–检索时，仅需文件名–文件描述信息单独形成一个索引节点——i节点《操作系统原理》——东北大学第6章文件系统34文件名索引节点编号文件名1文件名2………0131415UNIX的文件目录文件控制块和索引节点•磁盘索引节点–存放在磁盘上，每个文件有唯一的磁盘索引节点–包括：•文件主标识符：拥有该文件的个人或组标识•文件类型：正规文件、目录文件或特别文件•文件存取权限：各类用户对该文件的存取权限•文件物理地址：直接或间接给出文件所在盘块•文件长度、文件链接计数、文件存取时间《操作系统原理》——东北大学第6章文件系统35文件控制块和索引节点•内存索引节点–存放在内存中，文件打开时，将磁盘索引节点拷贝到内存的索引节点中–增加如下信息：•索引节点编号：标识内存索引节点•状态：指示i节点是否上锁或被修改•访问计数：有进程访问i节点时，计数加1•文件所属文件系统的逻辑设备号•链接指针：指向空闲链表和散列队列《操作系统原理》——东北大学第6章文件系统36目录结构•单级目录结构–整个文件系统中只建立一张目录表，每个文件占一个目录项–建立一个新文件时，先检索所有目录项，保证新文件名在目录中的唯一性，再从目录表中找出一个空白目录项，填入新文件信息–问题：查找速度慢，不允许重名，不便于实现文件共享《操作系统原理》——东北大学第6章文件系统37文件名物理地址文件说明状态位文件名1文件名2目录结构•两级目录结构–为每个用户建立一个单独的用户文件目录–这些文件目录由用户所有文件的文件控制块组成–系统中再建立一个主文件目录，其中每个用户目录文件占有一个目录项（目录名，指向子目录指针）–优点•提高了检索目录的速度•不同的用户目录中可以使用相同的文件名•不同用户可以用不同的文件名访