当前位置：首页 > news >正文

口碑好的番禺网站建设中国世界排名前100大学

news 2025/11/14 15:44:07

口碑好的番禺网站建设,中国世界排名前100大学,广州番禺景点,企业网站建设规划文章目录前言储存系统地址转换内存扩展覆盖交换储存器分配——连续分配固定大小分区动态分区分配动态分区分配算法储存器分配——非连续分配页式管理基本思想地址变换硬件快表#xff08;TLB#xff09;多级页表段式管理段页式管理虚拟储存器——基于交换的内存扩充技术… 文章目录前言储存系统地址转换内存扩展覆盖交换储存器分配——连续分配固定大小分区动态分区分配动态分区分配算法储存器分配——非连续分配页式管理基本思想地址变换硬件快表TLB多级页表段式管理段页式管理虚拟储存器——基于交换的内存扩充技术基本概念请求分页页面置换算法页面分配策略、抖动、工作集内存映射文件文件管理概述目录结构文件目录的概念文件目录结构索引节点文件结构文件结构分类逻辑结构顺序文件索引文件索引顺序文件物理结构磁盘块连续分配顺序分配链接分配索引分配逻辑结构vs物理结构难点从头查找一个文件的过程文件储存空间管理空闲部分空闲表空闲链表位示图成组链表文件管理服务文件基本操作文件共享文件保护文件系统文件系统的布局虚拟文件系统文件系统挂载前言属实是极限冲刺了距离考研还有10天我还有俩本书没学完乐昨天一下午一晚上学完进程今天再接再厉直接学完储存和文件系统 IO部分参见我的计组笔记非常详细储存系统我不喜欢重复造轮子这一章我会比较简略尽量写高层次的思想具体内容我的另一篇笔记里面记录的很详细如果基础不是很好可以对照看。操作系统笔记——储存器管理、文件管理、设备管理地址转换关于物理地址逻辑地址从源程序到汇编语言程序的这些阶段都用逻辑地址逻辑地址默认0为地址起点不考虑和其他程序之间的相互作用因此后续几步直到把程序装入内存的整个过程肯定是要将逻辑地址变为物理地址的后续的步骤为编译链接为目标模块装入内存。如何变就形成了3种不同的方法绝对装入很low没OS才这么做在编译链接阶段形成物理地址静态重定位可重定位装入在装入的过程中将指令内容修改形成物理地址动态重定位动态运行时装入指令内容一直是逻辑地址使用重定位寄存器辅助地址偏移在程序真正运行访存的时候才形成物理地址才发现我们OS老师上课用的那张图是从王道这里来的我就说风格怎么不一样我们前面讨论的是如何形成物理地址其实形成如何把多个.o文件的逻辑地址统一起来也是一个需要注意的点这个技术就是链接静态链接链接阶段一次性组合动态链接装入时动态链接装入的时候一次性组合运行时动态链接调用的时候才针对性的装入对应的模块.dll动态链接库联系前面的物理地址生成很显然绝对装入方法只能搭配静态链接使用而动态链接只能和重定位方法结合使用视角抬高内存管理除了负责部分地址转换以外还有很多功能。内存保护的两种思路上下限寄存器直接记录程序物理地址的上下线重定位寄存器界地址寄存器界地址寄存器规定了逻辑地址的上限内存扩展覆盖覆盖就是让互斥的程序段公用一片内存有两种可能固定区互斥程序段只有一个那么这片区域就是独占一般来说只有一个固定区main函数覆盖区有多个程序公用每一个覆盖区都由当前覆盖段里占内存最大的模块决定。比如B先用内存C要用就把B的部分直接覆盖就行这也是这个名字的来源这个方法的缺点就是需要人为指定覆盖结构计算机不会分析不方便。交换交换就是把暂时不用的程序换出腾出空间给其他程序运行。结合第二章交换其实就对应着中级调度因此换出的程序首选被挂起的程序其次就是低优先级的总之尽可能减小换出的副作用。交换区要频繁读写因此单独划出。为了加快读写采用连续分配的方式管理磁盘IO更快储存器分配——连续分配所谓连续分配就是程序要放就是一整段全放进去不可以拆开。固定大小分区说白了单一连续分配就是只有一个应用分区因此没有外部碎片只有内部碎片下面的固定分区分配其实就是把这一个区拆分成多个固定的区只分配不改变大小。既然思想一致只是分区数量的差异那么碎片的逻辑也就一样了。多个分区还要进行管理需要一个固定分区表这个表能修改的只有分配标记如果最大的那个分区都满足不了当前程序就上覆盖技术。动态分区分配动态分区就是固定分区加强版除了可以修改标记以外还可以修改区域的大小。数据结构有两种分区表沿用固定分区的思路空闲分区链。这里注意一下其结构这是一个双向链表有首尾两侧链域中间部分可以存放分区的描述信息分配和回收的过程中要涉及到分区的拆分和回收合并拆分动态分配算法回收会涉及到表项/节点的修改或者删除要具体讨论动态分区的思路可以保证新分的区是满的所以没有内部碎片代价就是会产生外部碎片内存中有一些地方因为太小是怎么也用不到的解决方法也很直接就是把分区挪一下挤一挤即紧凑技术。很明显程序在这个过程中浮动了因此只能搭配动态运行时装入动态重定位技术使用。动态分区分配算法首次适应遍历空闲分区表/链第一个能用的就直接用同时进行修改优点快最佳适应最小适应一种粗暴的思路是遍历全部空闲分区链另一种更好一点的思路是维持空闲分区链的有序性在修改后重新排序因为分配只会导致减小所以我们只需要对着前半截进行一次插入排序即可优点保证大空间缺点产生小碎片慢最坏适应最大适应与2反其道而行之优点减少小碎片缺点破坏大空间慢邻近适应对1的修改从上一次停下的位置开始查找这样可以跳过前面因为分配而产生的小空间快速用到后面的大空间缺点是破坏大空间优点是比首次适应还快储存器分配——非连续分配页式管理基本思想页式管理其实是分区的进化版将分区粒度变得非常细同时用页表建立索引因此可以分散储存大大提高空间利用率。页表负责索引功能将逻辑页号转为物理页号这里区分一下名词逻辑页对应程序叫页页面物理页对应内存叫页框页帧物理块物理页面内存块因为逻辑页是连续递增的因此直接隐含在偏移地址里了不在页表项里而页表项的长度一定是要对齐的k字节如何转换呢逻辑到物理说白了就是用索引表的页号查找对应页框号然后拼接就可以注意页框号要乘系数才是页起始地址物理到逻辑 1的逆过程在二进制下其实很简单直接截取地址后半段就是页内偏移前半段就是页框号本质在于页框大小固定因此两部分都是定长地址变换硬件学过汇编的话这个过程非常熟悉。因为页表位置可以浮动我们干脆就用一个页表寄存器储存地址PTR 考虑到安全性检验还要再存页表长度这两个是分成两节存在一个寄存器里的需要注意既然是寄存器那其实也是程序上下文所以随着进程切换肯定也会有装入和保存的过程这个转换流程用字母描述 P页号W页内偏移需要注意的是越界验证因为PTR存的是页表长度所以是虚高1位的因此只要P等于M就算越界我们都是手算实际上计算机直接拼接就行前面说到页表项大小要对齐到k字节实际上不仅仅如此。 3B情况下会产生页框内碎片那么我如果要访问这个碎片地址上的页表项呢那只能1偏移这样做很麻烦而且容易出bug 所以干脆进行二次对齐对齐到能够被页框大小整除所以一般是用4字节做题的时候要考虑这两种对齐。快表TLB 参考cache原理TLB其实就是页表的cache材料也都是SRAM只不过TLB的等级还要在cache之上是最紧贴CPU的 TLB是一种cache更具体的说应该是全相联方式储存的模式。因此快表不能像页表那样把页号隐藏在地址里而是多加一个字段且每次要遍历快表。查找过程有两种先查TLB再查页表同时查询进而衍生出不同耗时·的计算结果 TLB和cache的区别 cache会缓存一整个内存块TLB只cache页表项从这个角度来看其实TLB就是比cache更细TLB是内存块的cache而cache是整个内存的cache 多级页表当一个页表存不下页表项就需要用二级。一般来说只有二级页表实际上可以多层区分一下名称二级页表外层页表或顶层页表页目录表每一行页目录项页表描述符一级页表每一行页表项页描述符转换过程无非就是前N次确定最终页号最后1次进行访存即N1次页表具体分几级要根据地址长度来定先抛去页内偏移之后看看能拆几节页号地址。段式管理首先要明确段式管理和页式管理是并列的都是非连续的分配。段式管理很像动态分区但领域不一样动态分区是给内存进行分区分区表是针对内存的每个分区对应一个进程段式管理是给进程空间进行分区段表是针对一个进程的每个分区对应程序的一个内存段段表和页式管理类似每个段表项都是等长的段号都是隐含的但是段不等长寻址过程也很类似都是两次越界检测越界也是同理这个段长是具体长度虚高所以只要满足WC就代表越界了从设计理念上来说段页还是不同的如下页式管理完全是为了系统服务的是物理性的纯粹按照地址切分的用户不可见段式管理更多的是为了用户服务是逻辑性的分模块的用户可见由设计理念来引申共享与保护因为段是逻辑的我们共享的时候也是按照模块共享的逻辑上非常直观比如我可以专门为可重入代码或者共享数据建立一个段这个段直接整体共享即可不可重入代码不可共享而页并不具备这种逻辑的整体性一页里面可能啥都有同理段也更有利于保护整个模块一起保护很方便页的内容很复杂错乱所以共享管理很麻烦定不定长也是一个区分点页式管理定长因此给定一个逻辑地址就可以直接通过除法运算锁定页号页式管理一维给地址直接上线性地址段式管理不定长给一个逻辑地址只能截取段号而不是除法运算因此段式管理是二维的给地址的时候要给两部分段命对应段号和段内地址段页式管理终于到了段页式管理了这才是版本真神。段页式管理是页段的综合底层用页高层用段。另一种理解就是把二级页表爆改成段表了段页式是两级的所以访存次数是213 要进行两次越界判断由此可得其实二级页表也得进行两次越界判断。注意这个TLB是把段号和页号一起作为一个tag的而不是弄两个TLB 虚拟储存器——基于交换的内存扩充技术基本概念虚拟内存的特征多次性针对装入过程来说对换性内外交换虚拟性针对空间视图来说看到的很大但是是虚拟的因为虚拟内存是把进程的内存空间拆分了所以必须使用非连续性内存分配技术。在此基础上增添两个功能请求调入置换后面以页举例更复杂的也是类似逻辑。请求分页请求分页逻辑可以参考cache来其实是一个思想但是具体还是不太一样cache仅仅是缓存管理能力很弱而虚拟内存的管理能力很强除了页框内容的缓存外还专门有页表来管理页框我们研究的其实是页表的管理。请求页表结构首先虚拟页表的管控对象是内存外存管控对象到底在内存还是外存因此要用状态位内存块号外存地址进行区分和寻址其次考虑置换过程置换哪一个因此要有访问字段辅助置换算法换出的时候是否要写回因此有修改位需要考虑是否被修改类似cache脏位如果目标页的有效位0说明在外存发生缺页中断。注意缺页中断并不是外中断而是广义的中断实际上是异常。之后研究一下请求分页管理中的细节其实和基本分页的区别无非就是两点额外的检查状态位额外的修改外存置换前是否写回外存页表置换后页表的标志位要刷新TLB快表的有效位恒等于1因此换出的时候要TLB删除否则出错换入的时候也可以根据局部性原理将这个页表项复制到TLB 不过不得不说这个过程真的挺复杂的后面做题继续细化吧你且知道相关联的三个部分就可以外存页表项以及对应的页框TLB 页面置换算法这几个方法在我另一篇笔记里已经有详细的描述了这里进行细化。注意页面置换次数≠缺页次数缺页是要更加广泛的注意题目问的是哪个。首先是OPT 具体做的时候就是从发生缺页的位置开始查看后面要调用的页在这里面找我们当前物理块里装的页排在最后一个的就是要置换出去的。然后是FIFO和LRU具体过程很简单 FIFO有两种理解方式效果相同做题的时候自己看着办新进来的页会把原来的页推下去末位淘汰直观另一种理解方式是用一个指针指向即将要替换的位置每次替换都让指针挪一位 LRU也是两种理解方式类似于FIFO的下推末位淘汰但是如果命中就把这个块提到最上面刷新存在感另一种理解方式是逆向遍历访问序列类似于OPT最后一个出现的就是要淘汰的只不过方向相反效果对比 FIFO有Belady异常而LRU就没有LRU效果是最接近OPT的但是开销太大需要硬件计时器参考cache替换要求的数量还不少。再说时钟置换算法CLOCK(NRU) 思想很简单排成循环队列命中刷新访问位1 注意命中不需要转时钟指针不变不命中按照时钟方式扫描进行替换 1置0访问位1相当于免死金牌0置换访问位0则受斩置换后要将指针后移防止这个新的页面在下一轮扫描的一开始就掉血极限情况是进行1轮1次扫描也就是两轮扫描这个方法兼顾了效率和效果。改进NRU还考虑到了写回的IO损耗尽可能避免IO替换修改位0的页面同时还要维持原本NRU的原则于是根据访问位修改位可以分成4个优先级 0,0既没用又没修改过直接换0,1没用但是被修改过换的成本大点但是造成的影响不大1,0用过不得不换只能找个换的成本小点的1,1成本最大不得已的办法具体如何去扫描呢分4轮先在没访问过的里面扫两轮第一轮扫0,0第二轮扫0,1同时置零访问位第二轮才会像NRU一样置零访问位因为这两轮整体并做对访问位的检查所以只置零一次之后在访问过的里面扫两轮注意这两轮本来是1,01,1的专长但是因为第一组操作已经把访问位置0所以走到这里的肯定在第一组操作之前全部都是1x的情况第三轮扫0,0第四轮扫0,1走到这一步一定会有一个页被置换出去这一组操作其实是针对修改位而来的改进NRU非常的完美两组操作继承自NRU对访问位的置0也和NRU完全一致而在在两组操作内部又加入了对修改位的考察虽然改进NRU最多进行4轮考察但是这点内存中的消耗和降低IO损耗带来的收益相比微不足道页面分配策略、抖动、工作集之后介绍三种分配置换的搭配固定分配局部置换其实就是我们前面做题的时候用的思路当前进程和外存进行交换可变分配全局置换只要缺页就增加物理块当前进程不直接和外存进行交换而是直接用空闲的或者从其他进程抢一个未锁定的页框过来之所以不直接是因为抢夺其他进程页框也会间接导致其他进程的交换实际上还是要交换这个方法反而还不如局部置换稳定可变分配局部置换在1的前提下如果系统察觉到1的缺页率比较高就分配空闲块当然3方法也存在抢夺物理块的情况但是频率比2低多了请求调页就是缺页中断精确度很高IO开销大预调页策略目标是减少IO开销就是一种预测因为其效果一般所以只是在程序刚启动才这么干这个时候调入不需要置换就算翻车也无所谓。再论从何处调页普通系统对换区大那就全在对换区操作就行因此要先复制到对换区再调入对换区小因此要尽可能精细化只把要修改的可能反复IO的数据写回到对换区 Unix系统介于普通系统的两个策略之间精细度居中第一次是从文件区调入之后换出的页面不管是否被修改过都放到对换区内存映射文件传统文件读写要进行内存文件的多级索引比较麻烦如果你不是一次性读入那么每读一个块都要多级索引一次。内存映射文件直接把文件索引一次性读到内存里分出一些页表项直接把文件地址记录进去出于效率考虑这里只是分配了页表项并没有将文件读入但是后续的读入已经很简单了不需要多级索引只需要IO就可以效率高多了。修改只需要在内存中这进一步减少了IO损耗最后进程关闭文件的时候才将文件一次性写回非常方便。总之内存映射既可以减少索引损耗又可以减少IO损耗文件映射还有另一个好处就是便于共享文件。注意区分页表项和物理页框实际上读入后的文件是放在物理页框里的我们说的共享只是让不同进程的页表项指向同一个页框。文件管理文件系统复杂之处在于非常庞杂需要一个良好的整体观明确区分各种概念接下来直接简要的把整个文件系统简单概括一下文件这一章整体都比较乱因为文件系统确实是比较庞大我在看我以前笔记的时候也同样有此感觉因此我在这篇笔记里要尽可能让宏观逻辑顺畅。因为文件系统庞大所以我会自上而下的写1,23从逻辑逐渐过渡到物理最后再拔高统筹45 先说目录结构这是和用户最直接关联的这一部分会着重讲解目录树的分支节点即目录文件这一节讲目录树叶节点上的普通文件先讲文件的逻辑结构再往下讲文件的物理结构这一节尤为重要决定了你访问文件的IO成本这一节加深对物理层面的理解文件之外的地方空闲块如何管理到此为止你已经可以从上到下找到一个文件的所有磁盘块了并且你也知道一个文件的空间从哪来到哪去了文件管理最基本的功能已经有了视角开始拔高补充一些文件的管理服务最后用文件系统统筹从最底层的磁盘分区到高层的VFS顺一遍概述区分标识符vs文件名前者是OS内部用后者给用户外存地址vs文件目录前者给OS内部用后者给用户文件内部和文件之间都需要组织。目录结构文件目录的概念文件目录离我们很近Windows文件夹就是一个文件目录的GUI 文件夹本身就是一个文件现实中你装文件的袋子肯定也是有实体的通过文件夹就可以找到文件夹里面的文件文件夹里面可能有文件夹也可能有文件这叫嵌套和你电脑里的逻辑是一样的。虽然他们都是文件但是性质不一样文件文件分为两部分数据本身文件体以及FCB一个文件对应一个FCB记录其元数据包括名称和物理地址等实现了按名访问。对文件修改的同时也要修改FCB文件夹也是文件所以文件夹本身也有数据FCB 文件夹文件目录文件夹记录了这个文件夹下面的所有文件包括下级目录和本层文件文件夹是一种特殊文件内含多个FCB而不是普通数据文件目录结构文件是要给人用的所以肯定会有一个名字也就是说文件和文件之间是要有区分的而内存里的东西就不需要这就是文件系统和内存的本质区别。既然有名字在一个文件夹下就不能重名因此文件目录结构是一个重要问题。最开始叫一级目录说白了就是整个系统只有一个文件夹MFDMaster File Directory很显然如果文件太多则需要遍历文件目录耗时很多之后升级二级目录多出来的一级代表用户UFDUser FD此时有一点区分度但是不太够多级目录就是我们现在见到的目录结构层层嵌套比如上图的路径要读3次目录才能找到文件之后你还得再读文件所以消耗是读目录读文件当然其灵活性的好处远远大于这点IO损耗索引节点回顾一下B树和B树这两者的区别在于B树节点本身就储存着数据而B树很精简索引节点只是索引叶节点只储存指针。当时还说了文件系统用B树一个重大原因就是其可以在一个磁盘块有限的空间里尽可能塞入多的索引项。越精简储存一个文件目录需要的磁盘块就越少从而减少在遍历索引表时的IO次数。因此直接把FCB中文件名字以外的元数据都剥离出去构成一个索引节点inode 文件结构这一章开始讲一个文件如何组织FCB和文件体两部分要统筹着看。文件结构分类流式文件和有结构文件的本质区别在于对齐。无结构文件流式文件基本单位很小比如txt每个字符是一个字节字节流压根就不需要考虑对齐直接切割到不同磁盘块里肯定是齐的结构文件记录式文件基本单位类似结构体你不能把结构体从中间切开吧所以要考虑对齐定长记录vs可变长记录可变长记录复杂但是利用率高定长记录直观简单逻辑结构类似于数据结构逻辑结构主要讨论逻辑不讨论具体实现这里说的地址通通指代逻辑地址与物理无关顺序文件顺序文件对应顺序表顺序表又可以分为链表和数组。链式储存只能顺序优点是可以分散储存顺序储存不定长只能顺序没有优点定长其实就相当于数组了优点是可以随机存取定长乱序串结构普通数组定长有序顺序结构可以上特殊算法了代价就是维护成本大总结一下但凡用了可变长记录就会破坏数组特性顺序文件就只能顺序查找了。FCB记录顺序表的首地址和长度注意题目会模糊逻辑结构和物理结构比如顺序文件储存其实暗含了物理结构默认的是顺序文件顺序分配索引文件前面说了在顺序文件的前提下一旦引入可变长记录就啥也不是了但是索引表可以完美解决这个问题。索引表本身是定长的因此可以随机访问索引表找到对应项目后再根据指针找到对应的数据记录虽然分两次查找速度会慢一点但是总比从头遍历数据记录好。数据库的索引原理就是这样索引的思想就在于给非随机存取的东西附加上随机存取的性质代价就是多走一层更占空间总结索引文件可以实现间接的随机存取FCB指向一个索引文件通过索引文件再找到文件所有的数据记录索引顺序文件索引文件有个缺点索引和数据记录一一对应也就是说其消耗是比例性的。如果数据记录本身太小了那么这个占比就很大类似于用链表节点存一个字符浪费率高达8/9 索引顺序文件双管齐下将数据记录分组内部为顺序结构每一组对应一个索引原来是一个数据很显然可以降低浪费率组之间分散分组后数据记录组的数量变少索引表项就少了如果索引表还是大那么还可拆分多级这个时候你就会发现已经有了B树的感觉了唯一细节的地方就在于这棵树的叶节点指向的是一组数据记录而不是一个数据记录。所以查数据也很简单先逐层查索引之后再到组内进行顺序查找把整体切分为组后顺序存储查找时间太长的缺点就被消除了而且组内存不定长记录也是没问题的。总之就是一个完美。物理结构物理结构和逻辑结构无关物理结构要解决的问题是给定一片连续的逻辑地址如何将其分配到物理空间并组织起来磁盘块如果磁盘块和内存块大小不一样呢扇区的大小一般为512B而我们之前学页式管理一页经常是4KB的这显然不对劲。我们姑且不讨论这些区别我们就默认磁盘块大小内存块大小在内外存交换的时候很方便直接以块为单位再联系一下cache和内存块的交换也是这个单位所以整个数据运行过程都非常流畅。类似于内存外存同样采用逻辑地址物理地址的思想。连续分配顺序分配顺序文件连续分配方式说白了就是串结构类似数组因此可以随机直接顺序访问注意磁盘和内存不一样磁盘特指HDD本身是无法进行随机读写的严格来说只能说叫直接读写即DAM介于纯粹顺序和纯粹随机之间磁盘本身的特性就决定了再快也快不到哪去。因此访问分散的磁盘块还是很耗时的这种顺序分配读起来是最快的。啥都好就是不够灵活扩展性很差而且会产生大量磁盘碎片终于知道以前windows上面说的磁盘碎片是啥了而且紧凑也很费时间这是致命缺点链接分配链式分配即链表。链表的优缺点隐式分配都有。最大的缺点就是只能顺序访问是纯粹的顺序访问读一个文件必须从头遍历这个过程中要反复IO每个块都要IO一次消耗非常大优点在于拓展是很简单的只需要改一下链域然后把FCB中的尾磁盘块指针改一下就行。这里有个问题为什么不像链表那样用NULL呢可能是磁盘里面没有NULL这个概念所以只能用块号限制相比而言下面的显式链接就是在内存中的链表因此是通过NULL机制-1来实现的收尾不需要尾块号显式链接的区别在于把磁盘中的连接结构提取到了内存中以FATFile Allocation Table的形式保存就是数组形式的链表一个磁盘只需要一个超大的FAT统一管理即可。虽然还是链表性能有显著提升本质区别在于隐式链接的遍历需要在内存和磁盘之间反复横跳而显式链接的链表遍历都可以在内存中操作而内存速度快的很就算按照链表的方式遍历速度也比反复IO快多了也就是说遍历的方式其实并没有太大变化只是n次内存操作比n次IO速度快多了此外还要做一些区分显式链表可以实现随机访问。在磁盘读写中一切随机访问都不是严格的随机访问这里的随机指的是可以跳过前面的磁盘块但是并不意味着可以跳过前面的显式链接因为你还是个链表嘛优缺点分析优点具有媲美顺序结构的性能随机访问优点具有媲美隐式链接的扩展性链表本质缺点内存驻留FAT消耗大外存空间也会有占用统称为储存空间索引分配显式链接比较优秀是以前系统常用的方案但是随着文件越来越多FAT逐渐变大负荷就太大了同时CPU性能之类的也提升了可以考虑通过若干次IO多次索引的方式来把压力分摊到IO上了索引分配的一个目标就是给FAT瘦身曾经的FAT是所有文件一张而现在是一个文件一张索引表然后逐级构成B树结构但是并不等同于数据结构学的那个B树类似于页表属实是万法归宗了我可以这么说凡是大规模的数据组织储存使用B树或者B都是很好的方案内存外存不约而同地使用了这种方法。在这里磁盘块可以被分成两类索引块存放索引表数据块单级索引非常简单就是先读索引然后通过索引把逻辑块号映射为物理块号再读物理块即可。如果一个索引块放不下一个文件的索引项就要扩展方案如下使用隐式链接方案链接索引块缺点同隐式链接如果索引块多了IO次数太多多层索引经典的B树思想但是并不等同数据结构那个B树其中涉及到逻辑地址到物理地址的转换需要根据情况进行除和模的计算尤其是多级情况下计算还是有一点复杂的具体来说除以一个子节点可以容纳的最大索引数 m k m^{k} mkm为下图的256k为剩余索引层数比如上图中两层索引k1因此除以256如果是三层索引那么计算第一层的索引下标就得除以 25 6 2 256^2 2562然后求模用这个模再除以 25 6 1 256^1 2561再求模总之就是除一下求个模循环往复直到最后一层混合索引多层索引比较死板无论多小的文件都需要固定的索引层数浪费现代操作系统中采用混合索引的方式根据文件的大小灵活扩充索引的级数以下图为例一个文件的顶级索引节点比较特殊是顶级索引表项目并不多。如果用到的块比较少那么就只用直接地址如果要多一些就要用一级间接索引从间接索引开始的索引节点这种索引节点就是填满的如果再放不下就启用二级间接。在Linux里面的顶级索引表是12111个索引项最高开三级索引注意因为FCB是改进版本所以根据指针读顶级索引表也算一次读内存所以不要被“二级索引”误导严格来看其实要高一级的IO次数计算的时候要注意。反过来如果题目告诉你顶级索引表已经读入了那么就不用修正了逻辑结构vs物理结构难点关键词区分 xx文件xx储存逻辑结构xx分配物理结构先区分一下逻辑地址和物理地址基础要牢固逻辑地址每个文件默认是从0开始的物理地址就是真实的磁盘块号从逻辑地址到物理地址的转换就是文件的物理结构来负责的与逻辑结构毫无关系。比如是用xx文件索引分配方式那么无论你是什么逻辑结构你都要通过索引表进行映射而如果是链式分配那么就需要给定物理首地址顺序遍历的方式去映射说白了这些分配方式都是逻辑到物理的映射方式进一步辨析文件/储存≠分配直观来看似乎就应该是连续文件配连续分配链式文件配链式分配但是其实不是这样的。无论你逻辑上文件是什么样的总之都是一片连续的逻辑地址思考一下C语言创建文件的过程你最终都是要write到这个文件里的无论你用什么逻辑组织最后你都要调用write函数逻辑上连续地写入文件这个write函数就决定了逻辑地址一定是连续的。因为逻辑空间必然连续所以OS会一视同仁自行决定分配方式比如下图逻辑结构是链式存储但是物理分配采用的是连续分配。总之逻辑结构和物理结构一点关系都没只不过是思想互相借鉴并不能对应不然为啥要分开讲呢从头查找一个文件的过程学到这里从头盘一下吧如何从文件系统里查一个文件的一项数据记录呢找到文件的目录逐级查找目录这个过程本身就是用FCB找目录文件再从中挑出FCB继续找目录文件的过程。目录通常都比较小所以没有复杂的物理结构获取目录每次IO一次即可找到目标文件的FCB遍历最下级文件目录注意目录里面的改进版FCB为索引结构只有名字和索引节点指针两项找到目标文件的索引节点解析节点从这里开始就要区分文件的物理结构了假设文件本身采用k级索引分配的逻辑结构储存文件在文件内查找数据记录从索引节点层层索引索引k次最后读取1次成功获得目标磁盘块完全跑下来IO成本查找目录的成本读文件的成本查找目录的成本就是目录级数斜杠个数读文件的成本要根据物理结构而定文件储存空间管理空闲部分前面说的目录结构文件结构都是对非空闲块进行管理还有空闲的部分在这一章集中讲解分区可以理解为一个特殊的文件夹目录区存放FCB以及索引节点以及各种分区元数据文件区放数据体 FCB索引以及文件体这些我们都在前面讲过了属于非空闲部分的管理接下来讲解一下如何管理空闲部分其实类似于内存管理思路都是类似的空闲表空闲表参考内存分区里面的空闲分区表同样的记录了起始地址长度分配和回收都是一模一样的具体到文件的物理结构来说这种空闲管理方式比较适合连续分配方式。空闲链表两种方式空闲盘区链类似于分区里面的空闲区链表重点都在“区”而空闲盘块链粒度更细区分空闲盘区链同内存中空闲区链表分配使用适应算法回收要检测被回收区两侧是否有空闲区相邻空闲盘块链这是一个全新的概念 OS视角下相当于把所有空闲的磁盘块变成了一个队列分配和回收分别是出队和入队的过程两种方式都适用于离散或者连续分配只是效率不同连续分配或者一次分多个空闲区块链快而如果是离散少量则空闲盘块链快位示图位示图很经典这里额外讲了字注意这里的字针对的是位示图的一行如果一行有kbit那么一个字对应k个磁盘块。还需要注意的是从0开始还是从1开始非典型情况可以参考矩阵压缩那一块思路一模一样。之所以要引入字是因为这样便于定位。分配的时候要将字号位号转化为盘块号同时将0置1回收的时候是逆向过程成组链表略0.1%的几率考我就当他0%主打一个效率文件管理服务文件基本操作 create创建文件两件事占用空闲磁盘块放文件体添加FCB到目录 delete是逆向过程 open两件事找到并检查权限打开此时FCB作为进程资源复制到进程的“打开文件表里” 还会把文件索引号文件描述符返回给用户程序其实就是一个key用于快速锁定内存中的这个FCB 考虑到文件的读写共享还需要在系统中维持一张系统打开文件表并且计数类似于硬链接的思想删除是逆过程删除的是进程本身的打开文件表项计数-1同样类似于硬链接如果计数为0则在系统打开文件表里删除对应项读文件从哪里读打开文件表中的读写指针读多少读到哪里内存中的位置写文件类似文件共享树结构的特点在于分支之间隔离。既然如此如何通过一个目录访问另一个目录呢分为软硬两种链接方法上图为硬链接文件和索引节点一一对应硬链接直接让当前目录里的FCB指向对应索引节点即可或者说在两个目录里存在一样的FCB。索引节点会维护一个计数器只有在全部硬链接都失效的时候count0才删除文件体和索引节点。还有一种软链接符号链接方式是Windows的方式即快捷方式.ink文件link本身就是一个文件当OS判断其为链接文件时会读取里面记录的目标文件的路径用这个路径找到对应文件目录下的文件而不是直接用FCB指向。软链接的本身只是快捷方式指向的文件删了就删了快捷方式本身不会受到影响只是没用了罢了。文件保护口令就是密码密码本身在文件之中FCB或者索引节点因此可以用技术手段去逆向分析破解。加密本质上也是把密码放在文件之中但是加密是把密码“分散”在整个文件之中了加密后的文件本身就是密码我们用密码去和加密后的文件比对解密就可以得到源文件。比较费事 ACL最基本的形式如上我们Linux里面用的chmod 777之类的指令变成二进制其实就是111 111 111 如果每个用户对每个文件都有这么一行实际上在列方向上是有冗余的在MySQL里面采用角色的思路来进行权限控制下面这个思路也是一样文件给每个角色分组整体分配权限然后某个用户访问的时候直接检查其归属于哪些分组即可。这样无论用户有多少一个文件ACL的长度也只有分组的个数。下图中组就是用户组一个文件可以针对每一个组配置对应的权限。文件系统文件系统的布局本节从最底层一个空磁盘开始逐步构建文件系统与内存接轨物理格式化低级格式化磁盘刚生产出来空白一片厂商会首先划分扇区进行编号固化在磁盘中这是最低级的格式化和用户的那个格式化不同有坏扇区物理上是无法挪动的可以将其信息固化编号的时候跳过顺延高级格式化后会形成MBR统筹所有分区若干磁盘分区下面列出分区内部结构如果安装有系统则会有一个引导块用于拉起系统超级块和空闲空间管理区功能类似互相补充i节点区存放inode即索引节点这片空间可以看做数组注意如果是混合索引分配那么i节点区不储存非顶层索引因为长度不对根目录规划好物理结构逻辑结构后文件系统基本构建完毕接下来是与内存的接轨接轨之前是文件的访问要先访问目录然后根据物理结构找到具体的磁盘块打开文件后进程以及系统会在内存中保持对文件的引用目录缓存和系统打开文件表归属于系统自然在内核空间进程打开文件表包含在PCB中而PCB又是在内核空间里打开流程如下需要注意下面三张表虚拟文件系统如果没有VFS不同文件系统的规范完全不同OS对于外接文件系统的兼容性就非常差。 VFS的宏观功能向上提供统一的文件标准接口比如POSIX接口向下规定协议对接入此VFS的文件系统一点硬性规定具体到细节上VFS通过若干思路实现接口的统一化统一不同文件系统的目录项统一用vnode保存只存在于内存中相对来说其他文件系统的目录项会同时存在于外存和内存中函数功能指针的意义在于区分不同v节点的文件系统类型毕竟上层OS下发的函数调用最终还是要落到具体的系统中的通过函数功能指针就可以找到这个文件对应的系统类型的函数接口进行专属于这个文件系统的操作文件系统挂载所谓的挂载就是把异种文件系统接入宿主机的VFS中日常中插U盘其实就是挂载要做三件事注册 VFS首先要知道这是个什么系统要记入挂载表里VFS还要知道这个系统如何操作即把其提供的函数接口保存下来接入把文件夹挂载到挂载点上一般来说Windows挂载点在磁盘根目录用过虚拟机的应该都有过挂载的经历比如说你是一个Linux的虚拟机但是你想要将主系统(Windows的文件夹共享到这个Linux中需要执行一个挂载命令才可以在hgfs文件夹里面看到共享文件夹这其实也是一个挂载的过程。

查看全文

http://www.zqtcl.cn/news/692023/