07第七章-文件系统1

第七章文件系统OS实现系统资源管理:硬件资源、软件资源;软件资源:程序、数据;文件管理:软件资源以文件形式存于外存空间,软件资源管理通常称为文件管理;文件管理由文件系统来完成;文件系统在设备管理之上。1.文件的概念文件:具有符号名而且在逻辑上具有完整意义的信息项的有序序列。7.1文件与文件系统7.1.1文件编号:01……k……n-1信息项信息项……信息项……信息项文件名:符号名,文件创建时确定,访问时用;信息项:构成文件的基本单位;等长或不等长;有顺序关系;读/写指针:信息项的读/写位置;读/写指针2.文件分类系统文件,用户文件;临时文件,永久文件;只读文件,只写文件,读/写文件;磁盘文件,磁带文件,磁鼓文件;目录文件,普通文件;程序文件,数据文件;程序文件源文件,目标文件,可执行文件,头文件,库文件。7.1.1文件UNIX文件分类普通文件:内容可以是程序、数据、图象等,保存在磁盘块中;目录文件:文件描述信息(文件名,文件号)序列,保存在磁盘块中;特殊文件:将各种设备作为文件处理。界面统一,使用文件与使用设备命令相同,申请设备open,释放close,读read,写write;利用文件保护功能可以保护设备。7.1.1文件7.1.2文件系统文件系统:文件与管理信息资源的程序集合称为文件系统。为用户提供按名存取文件的手段;文件的组织形式;外存空间的管理;处于设备管理上层。7.2文件的访问方式7.2.1顺序访问:磁带从文件起始位置开始顺序访问;从文件中间某处开始顺序访问。7.2.2随机访问:磁盘、光盘按信息项编号随机访问;按关键字(key)随机访问。7.3文件的组织文件的组织:又称文件结构;逻辑组织:外部组织形式,用户看到的文件组织形式。物理组织:内部组织形式,物理存储设备上的组织形式。OS完成逻辑组织形式到物理组织形式的转换。7.3.1文件的逻辑组织1.流式文件非结构形式的字节序列(UNIX,Windows,etc);构成文件的基本单位是字节。用户可以对非结构的流式文件按自定义的结构来处理。编号:01……k……n-1字节字节……字节……字节读/写指针7.3.1文件的逻辑组织(Cont.)2.记录式文件:记录的序列等长记录(优点:处理方便,速度快;缺点:空间浪费);不等长记录(优点:省空间;缺点:处理不便,速度慢);流式文件是记录式文件的特例。编号:01……k……n-1记录记录……记录……记录读/写指针7.3.2文件的物理组织物理组织:逻辑组织到磁盘块的映射。文件:记录(字节)序列⇒磁盘:块(block)序列考虑因素:①记录格式:等长或不等长,流式不必考虑;②空间开销:除保存文件内容之外的存储开销;③访问速度:顺序/随机访问速度;④长度变化:动态增长/减少。组织形式:顺序结构、链接结构、索引结构、散列结构、倒排结构。7.3.2文件的物理组织(Cont.)⒈顺序结构又称连续结构。一个文件占有若干连续的磁盘块。FCB……首块号28块数4…………块28块29块30块31……磁盘空间优点:速度快,节省空间;缺点:长度变化困难。⒉链接结构：又称串联结构,一文件可存于不连续块中,块间以指针相连。7.3.2文件的物理组织(Cont.)优点:长度变化容易。缺点:随机访问速度慢。FCB……首块号28块数4…………块28……块30……块45块46……磁盘空间7.3.2文件的物理组织(Cont.)⒊索引结构一文件可存于不连续块中,块号记在索引块中。优点:随机访问速度快;长度变化容易。缺点:额外需要索引块,存储开销大;FCB……索引块号28块数4…………块43……块87……块97块98……磁盘空间0431872973984……索引块287.3.2文件的物理组织(Cont.)⒋散列结构适用于定长记录和按键随机查找的访问方式;通常用于构造文件目录,一个记录内容就是一个目录项。计算地址:hash(key)=addr(在磁盘或文件中的存放位置)7.3.2文件的物理组织(Cont.)问题:给定key1≠key2,有hash(key1)=addr1,hash(key2)=addr2,若addr1=addr2,则发生conflict。Conflictresolution:顺序探查法:如发生冲突,则在冲突位置开始顺序探查第一个空闲的存储位置。记录中增加两个域:冲突计数;记录位置的空闲标志。7.3.2文件的物理组织(Cont.)⑴保存记录:保存记录的键值为key.地址空闲标志冲突计数……………addr:12键值key记录内容……1键值key1记录内容Hash(key)=addr文件空间保存记录key计算hash(key)⇒addr,adaddr对应的记录位置冲突记数加1位置ad空闲?ad指向下一个记录位置ad记录位置标记为占用记录key内容⇒ad记录位置保存记录key结束FT7.3.2文件的物理组织(Cont.)⑵查找记录:查找键值为key的记录。查找记录keyhash(key)⇒ad,addr取ad对应记录的冲突记数countad记录键值=keycount--count=0找到结束未找到结束ad记录空闲hash(ad.key)=addrcount=0ad指向下一个记录位置FFFFFTTTTT7.3.2文件的物理组织(Cont.)⑶删除记录:删除键值为key的记录。删除记录key调用“查找记录key”找到key?记录key不存在返回addr=hash(key)ad.空闲标志=0addr.冲突计数减1删除记录key返回FT特点:按关键字检索速度快。用途:常用于目录检索。注意:Hash空间可循环使用,满时保存失败。7.3.2文件的物理组织(Cont.)5.倒排结构键:记录中的域称为键;主键:记录中能唯一区分文件中所有记录的键称为主键;其它键称为次键。倒排结构:以键值和记录地址构成的索引结构称为倒排结构。主索引:键值为主键的索引称为主索引;次索引:键值为次键的索引称为次索引。7.3.2文件的物理组织(Cont.)表7-1各种文件物理结构的主要特性特性物理结构长度变化内存开销外存开销顺序访问速度按号随机访问速度按键随机访问速度定长变长定长变长定长变长顺序结构难小小快快快慢慢慢链接结构易小小快快慢慢慢慢索引结构易大大快快快慢慢慢散列结构易小小────快─倒排结构易大大────快快UNIX文件物理结构P389~390)……i_addr[0]……i_addr[9]i_addr[10]i_addr[11]i_addr[12]……i_node…………………………文件最大长度=10+256+2562+2563(块)多级索引+链接结构信息块索引块7.3.2文件的物理组织(Cont.)例：在UNIX系统中，设磁盘物理块大小为1KB，每个索引块可以保存256个索引项。假设某UNIX文件大小为1028KB。⑴请画出该UNIX文件的物理结构；⑵计算访问以下逻辑块号（逻辑块号从0开始）时，需要多少次I/O传输：①265；②266；③1025。解：⑴零级索引和一级索引能保存的块数＝10＋256＝266块；剩下的1028－266＝762块，可用二级索引。762＝256×2+250，即占用二级索引的3个索引项。该文件的UNIX物理结构如图所示。⑵根据文件的物理结构，访问逻辑块号①265需要2次I/O；②266需要3次I/O；③1025需要3次I/O7.3.2文件的物理组织(Cont.)……i_addr[0]……i_addr[9]i_addr[10]i_addr[11]i_addr[12]……i_nodenull。。。逻辑块0逻辑块9逻辑块10逻辑块265。。。逻辑块266逻辑块521逻辑块522逻辑块777逻辑块778逻辑块1027。。。。。。null250块256块256块256块给定的UNIX文件的物理结构7.3.2文件的物理组织(Cont.)7.4文件目录7.4.1文件控制块与目录项1.文件控制块(FCB)文件存在的标志,其中保存系统管理文件需要的全部信息;每个文件一个FCB,保存在外存;建立文件时创建,删除文件时撤销。2.目录项目录文件中的一项,内容为FCB;通常目录项名为文件名。7.4.2文件目录与目录文件1.文件目录用于检索文件的目录;目录项构成的有序序列;给定一个文件名,通过查找文件目录找到相应的目录项(FCB)。2.目录文件内容为目录项的文件,长度固定的记录式文件;实现文件目录的管理。文件控制块FCB文件名文件号用户名文件地址文件长度记录大小文件类型文件属性共享说明文件逻辑结构文件物理结构建立日期保存日期最后修改日期和时间最后访问日期和时间口令其它目录项1(FCB1)目录项2(FCB2)……目录项n(FCBn)目录文件目录,文件图示:文件目录7.4.2文件目录与目录文件(Cont.)7.4.3单级目录与多级目录1.单级目录(Single-LevelDirectory)整个系统只有一个目录,所有文件均登记在该目录中。FCB1FCB2……FCBi……FCBnfile1file2fileifilen…………目录文件普通文件单级目录结构缺点:⑴Namingproblem;⑵Groupingproblem⑶Protectionproblem.单级目录例:7.4.3单级目录与多级目录(Cont.)2.二级目录(Two-LevelDirectory)系统目录(公共目录),用户目录(私用目录);为每个用户单独设置目录。FCB1……FCBj……用户目录普通文件USER1……USERi……USERkFCB1……FCBmFCB1……FCBn……………………系统目录二级目录结构7.4.3单级目录与多级目录(Cont.)二级目录例:特点:⑴Pathname;⑵Canhavethesamefilenamefordifferentuser;⑶Efficientsearching;⑷Nogroupingcapability.7.4.3单级目录与多级目录(Cont.)3.多级目录(Multi-LevelDirectory)目录为树形结构;叶结点是一般文件或目录文件;非叶结节点是目录文件;根结点称作根目录文件。优点:便于文件分类;查找速度快(由于每个文件目录下文件少);可以实现文件连接(Link)。7.4.3单级目录与多级目录(Cont.)多级目录例:rootUnixbinusrlibdevetcVIusersWangLiSd1d2f1flibclibCClpConsolebinYaccPasswordf27.4.3单级目录与多级目录(Cont.)将FCB分为次部和主部两部分。次部:(文件名,文件号)长度固定(UNIX16bytes);保存在目录文件中。主部:(其它,连接记数)记录长度固定(UNIX32bytes);保存在外存固定区域,打开时读入内存;给定文件号,可计算主部位置。改进的好处可以提高查找速度(顺序查找)可以实现文件连接(link)7.4.4文件目录的改进改进的文件目录图示:文件号FCB主部1FCB1主部2FCB2主部……nFCBn主部目录项1(FCB1次部)目录项2(FCB2次部)……目录项n(FCBn次部)文件目录目录文件7.4.4文件目录的改进(Cont.)顺序查找n个记录，找到一个记录的平均查找记录的次数=(1+2+……n)/n=(n+1)/2设未分次部和主部的FCB构成的文件目录占n个磁盘块，则顺序查找文件目录，找到一个文件目录的平均访问磁盘块的次数=(n+1)/2设次部构成的文件目录占m个磁盘块，则顺序查找文件目录，找到一个文件的平均访盘次数＝(m+1)/2+17.4.4文件目录的改进(Cont.)7.4.5根目录与当前目录1.根目录树状结构(多级目录)文件系统中,根结点对应的目录称为根目录;根目录保存在外存空间固定位置。2.当前目录目前正在使用的工作目录称为当前目录。查找路径由根目录开始查找;由当前目录开始查找。查找算