考研408《操作系统》复习笔记，第四章《4.1 文件概念、文件逻辑结构、文件目录、文件物理结构》

应网友催稿主包最近也是很多事很疲惫所以笔记以最简洁形式来了可能不适合初学者抠细节但是复习框架是够的一、文件系统基础概念我直接思维导图放大来看【文件基础概念术语】定义了解一下【文件】就是一组有意义的数据/信息的【集合】一般【文件】是存储在【磁盘】的因为是要长期保存的数据文件的【属性也叫“访问类型”】只记重要的常用的文件名四级学习资料.pdf的这个四级学习资料就是给用户辨别的文件名注同一目录下不可有同名文件比如不能有2个test.txt标识符文件系统内部给操作系统识别各个文件的符号虽然同一目录下不允许同名文件但是我在桌面和在D盘还是可以创建两个同名的“test.txt”文件啊操作系统内部就会用一串用户看不懂的数字、符号组合来标识区分各个文件类型.mp3、.txt、.java、.pdf......这些文件类型位置特指用户看的懂的文件路径比如“D:/data”而非物理的磁盘实际地址大小就是这个文件的实际大小保护就是【安全】那限制用户的“写、改、读...”等权限经常做开发的应该会接触其中思维导图里的【文件结构】只是简单提一下其【逻辑结构】下面第二大点会重点讲【例题】二、文件目录简称“目录”1、【目录文件】概念当我们双击“照片”后操作系统会从一个“目录表文件”中找到【关键字 “照片”】对应的【目录项(也就是记录)】然后根据这个信息从外存中将“照片”目录的信息读入内存于是“照片”目录中的内容就可以显示出来了。而这个“目录表文件”就是【目录文件】它本身是存磁盘上的结构化文件记录当前路径下所有文件 / 子文件夹的元数据名字、权限、物理块号。永久存放于外存磁盘在运行时从外存调入到内存方便操作系统随时查找文件时用到它【文件控制块FCB】【目录项】那么一个【目录文件】里记录了很多条【目录项】这每一条【目录项】也叫【文件控制块FCB】再次强调FCB的多个名字【目录项】、【文件控制块】他记录的就是一个文件的各种属性其中最重要的是【文件名】、【文件物理存放地址】另外进程有【PCB】、文件有【FCB】别记混了2、【索引节点】对FCB的改进注意1、记一下【FAT32文件系统】不用索引节点2、凡是看到【从目录项分离】、【分离目录】这些字眼都是指【索引节点形式】【索引节点重点】因为在目录表查找文件时其实只用到了【文件名】所以FCB太多冗余属性信息了因此【索引节点】的改进结构如下【索引表】只记录【文件名】【该文件索引节点的位置指针】【索引节点】除了【文件名】之外的文件其他属性信息另外放在外存的索引节点叫【磁盘索引节点】放在内存后的索引节点叫【内存索引节点】放在内存后因为文件会被改动所以会额外添加一些内容比如几个进程在访问这个节点这个节点被改写了吗.....等了解即可3、【目录文件】和【文件目录】的区别这几个知识点可能很多人会混淆下图直观解释了【文件目录】和【目录文件】【目录项】和【记录】【记录】是一个【普通文件】的“一行数据信息”【目录项】是【目录文件】里的“一行数据”目录文件是特指“记录文件目录信息的文件”抱歉这里应该一个文件目录应该对应的是【文件】而不是【文件夹】的我截图时忽略这点急了。。。【例题】三、文件的【逻辑结构】直接思维导图记得放大看1、无结构文件又称【流式文件】就是一串【字符流】长度单位是【字节】没有结构所以也没甚好探讨的2、有结构文件又称【记录式文件】由多个【记录】构成每个记录里可以【定一个数据项】作为【关键字】1个【记录】由 多个【数据项】构成而【记录】的类型又分为【不定长 (可变长) 记录】和【定长记录】【定长记录】每个记录的【数据线个数一样】、【对应的数据项大小一样】重点【定长记录】可以【随机存储随机查找】就像访问数组第3个元素直接访问 a[2]只要知道了第1个记录的起始地址 2个记录的大小就找到 a[2]了【不定长 (可变长) 记录】每个记录的【数据线个数不一样】或者【对应数据项的大小不一样】重点【不定长 (可变长) 记录】不可以【随机存储随机查找】你都不知道每个记录的大小规律怎么计算第i个元素在哪有结构文件(记录式文件) 的【文件类型】1《顺序文件》顾名思义就是文件一个一个按顺序排列逻辑上就是数据结构的【逻辑结构之线性结构】回忆线性结构有线性表、串、数组、队列、栈物理上【线性表】物理上还对应了【物理结构顺序存储 、链式存储】所以顺序文件同样也包含了【顺序存储】【链式存储】但是考试不考【顺序文件链式存储】所以考试中默认【顺序文件】 逻辑上、物理上都是【顺序存储】【顺序文件】还分【可变长记录】、【定长记录】区别是【能否随机存取】【不定长可变长记录】不适合【随机存取】的因为各个记录大小不一样没法根据a[0]的地址算出第i个记录在哪【定长记录】是所有记录大小都统一因此可以根据大小计算出a[i]的地址可以【随机存取】【定长记录】还分【串结构】、【顺序结构】区别是【能否按关键字排序】串结构不能按关键字排序每次查找都要从头遍历顺序结构可以按关键字排序比如按姓名首字母大小、学号第一位大小2《索引文件》要记住的重点就是添加【索引表】每个【索引记录】是【变长记录】的长度、地址位置索引表的【每一个记录 (索引表项)】一一对应【每一个变长记录】【索引表】这个表必须是顺序、记录是定长的【索引表】指向的【变长记录】才是乱序的、记录是不定长的可以实现【快速查找 “不定长记录”】但却额外增加了【索引表空间】3《索引顺序文件》我直接思维导图解释要记住的重点就是解决【索引表】空间大问题把 “多个变长记录” 归为【一组】索引表【每一个记录 (索引表项)】指向的是【一组里的 “第1个记录” 的信息】【索引表】必须是顺序、记录是定长的但不需按关键字排序【变长记录组与组】之间是【乱序的】【一组里的记录】是【按顺序的】不仅减小了【索引表空间】、还提高了【查找效率】顺序文件、索引顺序文件的【查找次数】全网最透彻没有之一​​​​​​1个含有【​n个记录】的顺序文件【查找一个记录的平均次数】就是【(1n)/2】然而有的题目会隐含了 “粗略的”【平均查找次数公式】我们就不需要上面这个公式了例如这题题目规定了计算【平均查找次数的公式】【总记录数 / 2】而【n条记录的顺序文件】若用【一个索引文件】【最好的情况】就是分成【根号n个分组】【n个索引项的索引表】则【索引顺序文件】的【平均查找次数】计算【索引表平均查找次数】【1个分组平均查找次数】这还多一个【多级索引表】效率更高原理就是“不断套娃”【高级索引表】记录【低级索引表】的表项位置、【最低级索引表】才记录【各组变长记录】【例题】四、文件的【物理结构】前提提示不是知识点只是方便加深计组的知识点这一块概念有点像《计算机组成原理——第3章磁盘和固态硬盘》的内容像复习的可以去看看可看可不看非必要《磁盘和固态硬盘》https://blog.csdn.net/m0_73991249/article/details/1494237651、【文件块】和【磁盘块】理解四句话1、内存和外存磁盘以【块】传输【块】就是把多个存储单元分为一组块之间存储单元都一样2、用户操作的是【逻辑块号 块内地址】这里不理解需要补习计组内容块内地址其实就是一块里的存储单元的相对地址3、实际磁盘里用的是【物理块号 块内地址】4、用户的【逻辑块号 块内地址】对应 映射 磁盘的【物理块号 块内地址】2、三种分配方式映射方式【个人总结超快回忆法】连续分配、链式分配、索引分配每次回想起来都会忘所以我觉得应该直接用数据结构形状来记忆1连续分配就是【数组】要求【每个文件】物理磁盘上是【连续存放】重点文件【目录项】记录该文件【第一个磁盘块号】【所占用块数】映射关系【物理块号起始块号逻辑块号】比如图中给出【逻辑块号0】那么对应的【物理块号起始块4逻辑块04】优点【可以随机访问因为连续块方便计算块位置】【方便磁盘访问磁盘、磁头、磁带原理】缺点【为了保持文件整体有序增、删块要整体迁移不方便】【不灵活只要连续空间那就会产生很多外部碎片】容易遗漏这个知识点【连续分配】不允许【文件长度可变】​​​2链式分配这种文件又叫【链接文件】【物理上】是【离散分散存放的】① 隐式链接【链式分配】的【默认形式】重点题目没有指明是“显式链接”时【连接分配】通通默认等于【隐式链接】文件【目录项】记录文件的【起始块号】【结束块号】因为每个盘块都有指向下一个盘块的指针所以中间信息不用记缺点就是链表的特点不能随机存取只能顺序访问其中一个盘块有问题整个文件完蛋指针也占空间优点插入删除方便链表特点改链尾节点的指针指向即可② 显式链接重点就是在隐式链接基础上加了个【FATFile Allocation Table文件分配表】文件【目录】项只有【起始块号】然后每个盘块的下一块的指针由【FAT表】来记录注意【FAT表】之有一张一开机就读入【内存】所以显式链接【查找】文件时无需访问磁盘优点相对于“隐式”可以【随机存取】隐式要到磁盘外存一个一个遍历 [文件aaa] 的所有块故【顺序存取】[文件aaa] 有n个盘块就可能【磁盘I/On次】显式FAT表常驻内存【FAT表内】依旧像链表一样要【顺序存取】但是全程都在内存直到找到 [文件aaa] 所需的那一块的指针地址后才去外存取出全程只有取盘块这1次【磁盘I/O1次】因此比【隐式】快得多因为 [查找时] 不访问磁盘注意【随机存取】是相对于【访问磁盘】来说的在FAT表内查找文件时其逻辑还是像链表一样顺序查找3索引分配依旧文件在物理上【离散存放】只有【连续分配】才是【连续存放】组织方式就是系统为“每个文件”建立一个【索引表】索引表记录【逻辑块】和【物理块】之间的关系文件【目录项】记录文件的【索引块】磁盘块里存的是“索引表”——就叫【索引块】磁盘块里存的是“文件数据”——就叫【数据块】【索引块】里存【索引表】【索引表】的表项指向【数据块】因为【索引块】就是一个物理磁盘块大小固定如果【索引表】太大一个【索引块】会装不下那就分出3种分配方式① 单级索引分配【链接方案】一个【索引块】装不下就多几个然后采用【链式存储】连接各快因此可知只能【顺序访问】而且耗大量索引块空间② 多级索引分配像多级目录一样分一级、二级索引表一直套娃直到指向【数据块】重点固定【所有索引表大小】【磁盘块大小】那么要注意考点1、给出N级索引文件、磁盘块大小、一条索引表项大小问你 “大小最大多大”【索引表大小】【磁盘块大小】然后先计算一个索引表有最多可有几条【索引项m】然后【m × m × m ... m×块大小m乘N层索引这个“N”次】就是结果2、N层索引问你访问几次磁盘I/O那么答案就是【N1】N是放在磁盘需要调入内存的【索引表】、1是最后去磁盘取出【数据块】还有一个知识点记住【磁盘索引节点】和【内存索引节点】的区别就是有没有【访问计数值】③ 混合索引我真不知道怎么写这个笔记自己看吧然后等会在例题里找到做一下【例题】本小点提示然后注意【索引分配】是最牛逼的它支持【随机存取直接访问】因为它的索引表能快速指向对应的数据块哪怕多级索引层层一对一指向依旧很快也支持【任意拓展插入、删除】不管插入删除直接去索引表修改就行只用改索引表4、【逻辑结构】和【物理结构】区分大概思维导图框架混淆点1【顺序文件】的【顺序存储】和【链式存储】记住【顺序文件】作为逻辑结构概念它只是人类视角的一个数据结构那么实际物理上当然允许【顺序存储】或【链式存储】混淆点2【链式文件】的【链式分配】还是一样【链式文件】是用户逻辑结构概念【链式分配】是操作系统的物理结构概念混淆点3【索引文件】的【索引分配】还是一样【索引文件】是用户逻辑结构概念【索引分配】是操作系统的物理结构概念总结逻辑结构VS物理结构——服务对象【逻辑、物理结构】的本质就是看【这个结构是为了给谁服务为了让谁看得懂】【随机存取】问题内容这么多考试怎么记得起来谁可以随机存取谁不可以诀窍如下另外关于【隐式链接】、【显式链接】、【索引链接】这三很像的玩意我也做了总结所谓【随机存取】特指【针对外存磁盘访问可否直接一步到位】5、【逻辑 和 物理结构】例题重点重点【关于各个物理结构性能对比】记住这些特点【综合战力索引表是神六边形全能战神】然而从【随机直接访问】的角度来看【连续分配数组才是神】【最垃圾链式】从【插入、删除、拓展角度】【索引】、【链式】是神【连续、顺序分配】最垃圾【综合拓展记录成组分解技术】注意不要跟【成组连接分配】概念混淆【成组链接分配】下一章节学的【文件外存存储空间分配】的内容【记录成组分解技术】1个盘块只能存【完整的记录】若还有剩余的空闲区不够一个完整记录的大小直接不要了不可以用来存一个记录的一部分而下一个记录直接另起一个磁盘块记录【超级索引大难题看不懂题目就死看懂了巨简单】这种题第一件事找到【1个 文件快 / 磁盘块 / 数据块 / 索引块 多大】、【1个 指针 / 块号 / 地址 占多大】【1个索引块大小】/ 【1个 指针 / 块号 / 地址】【1个索引块有几个表项】第二件事判断具体某几块是【直接地址】【间接地址一级二级】【直接地址】的块有N个表项就【有N个数据块】【间接地址】的块N个表项对应N个下一级索引块最后一层索引块的N个表项才是对应N个数据块故N个表项有m级间接索引的话【数据块就有 N^(m-1)】【这一题是 “3层” “混合索引” 的真题】【王道的图】我个人看得不是很舒服【我重新画的图】非常清晰【升级版真题SB老头真是要死】学了前面的这里就简单了回忆【索引节点】知识点FCB的改进版