六 文件管理PPT课件

.,1,第六章文件管理,6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制,.,2,教学目的与要求,理解文件和文件系统的概念掌握文件的逻辑结构和物理组织掌握文件存储空间的管理、目录管理掌握文件的共享和保护,教学重点：逻辑结构和物理组织、文件存储空间的管理、目录管理、文件的共享和保护教学难点：逻辑结构和物理组织，成组链接法,.,3,6.1文件和文件系统,6.1.1文件、记录、数据项(说明包含关系)数据项基本数据项：可命名的最小逻辑单位/字段组合数据项：由若干基本数据项组成基本数据项的类型和数据记录一组相关数据项的集合关键字：能唯一地标识出记录的基本/组合数据项文件具有文件名的一组相关信息的集合。,.,4,文件属性,文件类型文件长度文件物理位置文件建立时间,图6-1文件、记录和数据项之间的层次关系,.,5,6.1.2文件类型和文件系统模型,类型一、按用途分类：系统文件，用户文件，库文件。（用户对以上三者的访问权限不同）二、按文件中的数据形式分类源，目标，可执行。三、存取控制E，R，R/W,.,6,6.1.2文件类型和文件系统模型,类型四、逻辑结构（1）有结构（记录式）（2）无结构（流式）五、物理安排（1）顺序文件；数据（连续放）（2）链接文件；（3）索引文件；六、文件与目录文件,.,7,文件系统模型,概念：文件和对文件进行操纵和管理的软件集合。三个层：文件(对象及属性)文件操作文件访问接口一、管理的对象及属性（1）文件（2）目录：例：目录项用于方便用户（提供文件逻辑名来访问文件）和提高文件存取速度。（3）物理存贮空间的管理，好坏将影响访问速度。,图6-2文件系统模型,.,8,.,9,用户接口接受用户发来的文件系统调用，进行必要的语法检查，根据用户对文件的存取要求，转换成统一格式的内部系统调用，并进入符号文件系统。符号文件系统根据文件名或文件路径名，建立或搜索文件目录，获得文件内部唯一标识来代替这个文件，供后面存取操作使用。基本文件系统根据文件内部标识负责把文件说明信息调入到内存的活动文件表中，这样查找同一表目就不用反复读盘了。如文件已经打开，则根据本次存取要求修改活动文件表内容，并把控制传到下一层。存取控制验证根据活动文件表相应目录项识别调用者的身份，验证存取权限，判定本次文件操作的合法性，实现文件的存取、共享、保护和保密。如不允许本次访问便发出一个错误条件，本次文件操作请求失败。,.,10,逻辑文件系统根据文件说明中的文件结构和存取方法等逻辑结构信息，把指定的逻辑记录地址转换成相应相对的块地址。对于流式文件，只要把用户指定的逻辑地址按块长计算出相对块号；对记录式文件，先把记录号转换成逻辑地址，再把其转换成相对块号。物理文件系统根据活动文件表相应目录项中的物理结构信息，将相对块号及块内相对地址转换为文件存储器的物理块号和块内地址。设备和分配策略模块负责文件存储空间的分配，若为写操作，则动态地为调用者申请物理块；实现缓冲区信息管理。根据物理块号生成I/O控制系统的地址格式。I/O控制系统具体执行I/O操作，实现文件信息的存取。这一层属于设备管理功能。,.,11,文件系统模型,二、对对象操纵和管理的软件集合：（1）逻辑文件系统：受命write(recordof文件，buf)write(逻辑号，buf)（2）基本I/O管理：write(逻辑号，buf)（3）基本文件系统：向driver发令，(buf具体物理盘块号)（4）I/O控制层：driver三、文件系统接口命令接口：例如copy命令程序接口：,.,12,6.1.3文件操作,一、对记录操作类似数据库二、对文件操作：创fopen/删/读fread/写fwrite/截断（清空）/拔指针fseek三、打开关闭操作打开：将文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号fd（索引)返回给用户四、其它更名、更改属性,.,13,6.2文件逻辑结构,概念：用户所能观察和访问到的文件的数据结构组织，独立于物理特性，容易检索和修改。无论是逻辑还是物理结构，都会影响到文件的检索速度,.,14,6.2.1逻辑结构类型,一、有结构文件：记录式文件a类：（1）定长记录（2）变长记录b类：（1）顺序文件：通常是定长记录，（为何，因变长采用此方式查询速度慢）（2）索引文件：（3）索引顺序文件：顺序组织多个组，每组记录中的第一个记录设置一索引项。二、无结构文件：流式文件以字节为单位，利用读/写指针进行访问。,.,15,6.2.2顺序文件,一、逻辑记录的排序（1）按记录录入的时间排:串结构。（2）按关键字排序：顺序结构。后一种情况更有利于提高查询速度。如可用折半查找法等。二、对顺序文件的读/写操作（图6.3)定长记录顺序文件：例：顺序读易于定位，甚至可随机读取。变长记录：不易定位，只能顺序读取。,.,16,图6-3定长和变长记录文件,.,17,6.2.2顺序文件,三、优/劣：批处理时效率是所有逻辑文件中最高的。可存在于磁带上。交互应用时“效率低”（如要查找单个记录），尤其是对变长记录的顺序文件。增加、删除记录涉及到排序问题，开销大。事务文件(log），用于存放将更新到主文件的记录。,.,18,6.2.3索引文件,由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用折半查找，速度更快。特点：提高了速度，增加了存储开销放索引文件。增、删记录时，对索引表作相应的修改。,.,19,图6-4索引文件的组织,.,20,6.2.4索引顺序文件,将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项。速度：例1：10000个记录，顺序文件：5000次查找查到。索引顺序文件，设100个记录一组，索引表的找法设为顺序法的情况下，则平价查找次数为50+50=100。例2：1000000个纪录：一级索引：（100个纪录一组）：平价查找5050次二级索引：平价查找50+50+50=150次,.,21,图6-5索引顺序文件,.,22,6.2.5直接文件和哈希文件,直接文件键值转换：由记录键值到记录物理地址的转换哈希文件A=H(k）是一种索引链接文件,图6-6Hash文件的逻辑结构,.,23,6.3外存分配方法（文件物理组织）,6.3.1连续分配（磁带，磁盘都可采用）（顺序文件）每个文件分配一组相邻盘块。优点：因磁头移动距离小，顺序访问容易且速度快.缺点：要求连续空间，一段时间后需整理磁盘以消除外部碎片。必须事先知道长度，文件不易动态增长和删除。文件对应目录项（属性）中包含：始址、总块数、最后一块字节数。,.,24,图6-7磁盘空间的连续分配,.,25,6.3.2链接分配（串连文件/链接文件）,文件离散地分配于各盘块中，消除了外部碎片，以提高外存利用率，文件长度可变，易于增删，只能顺序存取。对应目录项：链表的首指针1、隐式链接文件目录表中有start块号，每块中有指向下一块号的指针。缺点：只适合于顺序访问，对随机访问效率低，可靠性差。簇：包含多个块的单位，当以它为单位分配并链接，可减少访问时间，但增大了内部碎片,.,26,链式分配,图6-8磁盘空间的链接式分配,.,27,6.3.2链接分配（串连文件/链接文件）,2、显式链接：把用于链接的指针显式存放在内存的一张表中，查找在内存中进行。文件分配表（FAT）：表项中存放着下一盘块的块号文件目录表（FDT）/文件控制块（FCB）FAT-块链,图6-9显式链接结构,.,28,图6-10MS-DOS的文件物理结构,.,29,DOS磁盘盘区划分表,.,30,DOS磁盘访问操作流程,文件名,磁盘目录表FDT,文件分配表FAT,磁盘扇区定位,扇区物理操作,.,31,DOS对于1.2MB软盘，盘块大小为1KB，采用显示链接分配方式时，其FAT需占多少存储空间？注：FAT的每个表项存放一个盘块号，故FAT的表项数目由磁盘的物理块数决定。FAT的表项的长度通常取半个字节的整数倍解：FAT中共需表项数=1.2M/1K=1.2k每个FAT表项占12位，即1.5个字节所以FAT故共占1.8k存储空间.,例3,.,32,6.3.3索引分配（索引文件）,1、单级索引分配链接分配问题：不能高效直接存取；FAT需占较大的内存。概念：为每个文件分配一个索引块特点：支持直接访问；不会产生外部碎片问题：（1）文件较大时有利。文件较小时浪费外存空间（还需为小文件建索引块）（2）当文件较大时，索引块太多，查找速度减慢解决：当索引太大时，则需建立多级索引,.,33,图6-11索引分配方式,.,34,6.3.3索引分配（索引文件）,2、多级索引分配两级:为索引块再建立一级索引设一个盘块大小为1k，每个盘块号占4byte，则一个索引块可存放256个盘块号。所以两级索引存放的文件的盘块号总数为：256256=64k,故文件的最大长度为64M三、四级:适用于文件更大时,.,35,图6-12两级索引分配,.,36,例4,请分别解释在连续分配方式、隐式链接分配方式、显示链接分配方式和索引分配方式中如何将文件的字节偏移量3500转换为物理块号和块内偏移量（设盘块大小为1KB，盘块号需占4个字节）。解：3500/1024得商为3，余数为428，则逻辑块号为3，块内偏移量为428。（1）在连续分配中，可从相应文件的FCB中得到起始物理盘块号，例如a0，则所求的物理盘块号为a0+3，块内偏移量为428（2）在隐式链接分配中，由于每块需留4个字节存放下一个盘块号，因此逻辑块号为3500/1020的商3，块内偏移为440。从FCB中可得该文件的首个（即第0个）盘块的块号，如b0；然后可从b0块得到第1个盘块号，如b1；再从b1得到第2个盘块号，如b2；从b2得到第3个盘块号，如b3；如此可得所求物理盘块号b3，块内偏移量为440。,.,37,解：,（3）在显式链接分配中，从FCB中可得该文件的首个（即第0个）盘块的块号，如c0；然后从FAT的第c0项中得到分配给文件的第1个盘块的块号，如c1；再从FAT的第c1项中得到分配给文件的第2个盘块的块号，如c2；从FAT的第c2项中得到分配给文件的第3个盘块的块号，如c3；如此可得所求物理盘块号c3，块内偏移量为428。（4）在索引分配中，可从文件的FCB中得该文件的索引块的地址；再从索引块的第3项（距离索引块首字节12字节的位置）可获得字节偏移量3500对应的物理块号，而块内偏移为428。,.,38,6.3.3索引分配（索引文件）,3、混合分配方式（UNIX系统）,直接地址、一级、二级和多级索引合用索引节点：13个地址项,图6-13混合索引方式,.,39,3、混合分配方式（UNIX系统）,设每个块大小为4k，一索引项（盘块号）占4字节，则1)直接地址iadd(0)-iadd(9)：小文件（有无同名加入目录表（2）删除文件回收块清除占用目录项优点：简单，能实现按名存取缺点：速度慢/不允许重名/不便于共享(不能用不同名字访问同一文件)。,图6-16单级目录,.,50,目录项例,.,51,6.4.2目录结构,2、两级目录结构主文件目录MFD+用户文件目录UFD特点:(1)提高了速度:如：n个用户，每用户最多m个文件，则最坏速度为n+m而非n*m（2）可重名（3）可共享（但不方便）,.,52,图6-17两级目录结构,.,53,6.4.2目录结构,3、树型目录结构（多级目录）（图6.18）特点：能有效地提高对目录的检索速度允许文件重名便于实现文件共享（1）目录结构：一目录文件中的目录项可为：目录文件（节点）、数据文件（树叶）（2）路径名：（3）当前目录/工作目录。例：在UNIX系统中，如果当前路径为/usr/wang，相对路径为./last,那么文件的绝对路径为什么？4、增/删除（可/不可删除非空目录）,.,54,图6-18多级目录结构,.,55,6.5目录查询技术,文件访问过程：文件名目录项（FCB）或索引结点盘块号启动磁盘驱动程序1、线性检索法例：/usr/ast/mbox（图6-19）（1）根中得usr的索引结点号6;（2）6中得usr目录文件为132#；（3）132#中得/usr/ast的索引结点是26.（4）26中的/usr/ast目录文件中406#（5）406#中得/usr/ast/mbox的索引结点是60.（6）60中得/usr/ast/mbox的物理地址,.,56,图6-19查找/usr/ast/mbox的步骤,.,57,2.Hash方法,一种处理此“冲突”的有效规则是：(1)在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。(2)如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。(3)如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。,.,58,6.5文件存储空间管理,1.空闲表法：分配：首次/循环首次/最佳/最坏回收：判断是否合并。由于连续分配比较快，因此对对换空间及小文件的管理适用。,图6-20空闲盘块表,.,59,2.空闲链表法1)空闲盘块链缺点：可能该链很长。2)空闲盘区链：一个盘区含多个盘块，类似于内存分区分配与回收(合并)。,6.5文件存储空间管理,.,60,6.5文件存储空间管理,6.5.2位示图法（可采用连续或离散分配）1.位示图（图6-21）2.盘块的分配：（1）顺序扫描，找一个或一组=0的块。（2）根据找到的行/列得以盘块号。b=n(i-1)+j（3）修改位图，令mapi,j=1。3.回收（1）由磁块号得(i,j)i=(b-1)divn+1j=(b-1)modn+1（2）修改位图：令mapi,j=0。特点：因不占空间，可放入内存，易于访问。,.,61,图6-21位示图,.,62,例5,有一个计算机系统利用下图所示的位示图（行号、列号都从0开始编号）来管理空闲盘块。如果盘块从1开始编号，每个盘块的大小为1KB。（1）现要从文件分配两盘块，试具体说明分配过程。（2）若要释放磁盘的第300块，应如何处理？,.,63,解,（1）分配过程线形检索得：i1=2，j1=2；i2=3，j2=6。计算空闲盘块号：b1=i116+j1+1=216+2+1=35b2=i216+j2+1=316+6+1=55修改位示图：令map2，2=map3，6=1，并将对应块35，55分配出去。,.,64,解,（2）释放过程计算出第300块所对应的二进制行号i和ji=（300-1）/16=18j=（300-1）%16=11修改位示图：令map18，11=0。,.,65,6.5文件存储空间管理,6.5.3成组链接法（UNIX）1、空闲盘块的组织。空闲盘块号栈：（图6-22）2、空闲盘块的分配与回收分配：到s.free(0)时，由于该块内容为下一组的盘号，将内容加入空闲盘块号栈中，再分配。回收：到s.free(100)时，将空闲盘块栈中内容放入新到的回收块中，将该回收块作为栈底。,.,66,图6-22空闲盘块的成组链接法,.,67,例:某个系统采用成组链接法来管理磁盘空闲空间，目前磁盘的状态如下图示：该磁盘中目前还有多少个空闲盘块，请简述磁盘块的分配过程在为某个文件分配3个盘块后，系统要删除另一个文件，并回收它所占的5个盘块，它们的盘块号依次为700，711，703，788，701，请画出回收后的盘块链接情况。,.,68,解：（3）删除文件，回收五个盘块后：,.,69,图6-23包含有共享文件的文件系统,6.6文件共享与保护,.,70,（1）建立链接时，将共享文件的物理地址链拷贝。(图6-23)缺点：文件增、改时，其它用户不知，造成新增内容不能共享。（2）共享索引结点：当count1时，这时文件主也不能删文件。否则，指针悬空。(图6-24)(图6-25),6.6.1基于索引结点的共享方式,.,71,图6-24基于