精华内容
下载资源
问答
  • 一个采用三级索引文件系统
    千次阅读 多人点赞
    2020-10-19 23:47:24

    操作系统中,最常见的文件分配方式有连续分配、链式分配和索引分配,连续分配无法改变文件的大小且易产生外部碎片,链式分配解决了以上的问题但是无法实现文件的随机访问、查找效率低。为此,便提出了一种更为高级的文件分配方式——索引分配。


    一、直接索引

    直接索引不使用FAT文件分配表,而是在文件控制块(FCB)中设置一个区域,成为索引块或索引表,每个文件都有一个FCB(Linux系统中使用inode索引节点),因此每个文件都有其对应的索引表。目录条目包括索引表的地址,索引表中不存储任何文件信息,而是存储一个个索引表项,每个索引表项都有一个指向分配给该文件某个磁盘块的指针,要读取文件的第i块数据,通过索引表的第i个表项中的指针来定位所需的块在磁盘中的位置。下面是索引表的示意图:

    在这里插入图片描述

    从上图可以读出,文件1.txt在磁盘中的块分别为4、7、9、0、5.

    当创建一个文件时,索引表中的指针均初始化为-1,表示不指向任何磁盘块。首次写入文件的第i块时,系统从磁盘的空闲块中取得一个快,将其地址写到索引块中的第i个条目,以此类推。文件结束时,索引表最后一个条目设置为-1,表示存储的磁盘块到此结束。
    内存的分页管理中,每个程序都有一个页表要维护索引表,在文件的索引分配中也一样,每个文件都有自己的索引表。索引表存储在磁盘上,因此为了节约空间,应尽可能让索引表小,然而索引表越小,索引表项也就越少,即能够指向磁盘块的指针数就越少,这样一来,就系统就无法支持大的文件。也就是说,文件的大小受到索引表大小的限制。为了解决这个问题,又提出了新的索引分配解决方案。


    二、链接索引

    在链接索引中,采取了同文件的链式分配相同的思想,由于索引表也是存储在磁盘上的,并且通常占用一个磁盘块的大小,因此可以将多个索引表用指针连接起来,以此来支持大文件的存取。


    三、混合索引

    混合索引指将多种分配方式与索引分配相结合的分配方式。如既采用连续分配的方式,又采用索引分配的方式,即一个文件前面的数据块采用连续分配,后面的数据块采用索引分配。下面给出2012年数据结构考试真题,并结合真题进行进一步说明这种分配方式。

    【2012统考真题】
    设某文件系统空间最大为4TB(1TB = 1024GB = 1024×1024MB,以此类推)。以磁盘块为基本分配单位,且磁盘块大小为1KB。FCB中有一个512B大小的索引表区域。

    (1) 若采用直接索引分配方式,索引表中存放若干个含有指向磁盘块的指针的索引表项,那每个索引表项最少占用多少字节?可支持的单个文件最大为多少字节?

    (2) 若采用连续分配+直接索引分配的混合索引的分配方式,其中,索引表项的格式为:前8B的空间表示<起始磁盘块块号,磁盘块数>,用于文件前半部分的顺序存储,其中起始磁盘块块号占6B,磁盘块数占2B;后504B的空间采用(1)中的直接索引结构,即索引表区域大小为504B,并规定索引表项的大小为6B。在这种分配方式下,可支持的单个文件最大为多少字节?为使单个文件支持的长度达到最大,请指出表示起始磁盘块块号磁盘块数的空间分别所需要的字节数。

    【解】
    (1) 为了能够充分利用磁盘,索引表必须能够表达整个磁盘空间。系统空间4TB合4×240B,每个磁盘块为1KB,那么整个磁盘就有4TB / 1KB = 4×240B / 210B = 232 个磁盘块。因此索引表必须能够表示整个232个磁盘块,故所有的索引表项加起来最少能够表达32位的二进制数(与内存寻址能力的思想一致,32位操作系统的寻址能力是 232B = 4GB ),32位就是32bits,换算成字节数就是4字节(32 / 8 = 4),即每个索引表项最少需要4字节的空间来存储。那么,索引表本身大小是512B,索引表项的大小是4B,显然,每个索引表最多能够存储512B / 4B = 128个索引表项。每个索引表项含有一个指针,指向一个磁盘块,那么128个索引表项就有128个指针,可以表示128个磁盘块,每个磁盘块的大小为1KB,故可支持的单个文件最大为128KB

    (2)
    针对该小问的第①问,分成两部来算,先计算采用连续分配方式的最大总磁盘块大小,再计算采用直接索引分配方式的最大总磁盘块大小,两者求和即可。采用连续分配方式时,能够连续存取的磁盘块总大小取决于磁盘块数,题目中告诉我们磁盘块数这个字段占2B,也就是16bits,因此,其所能寻址空间为216个磁盘块,即 216KB大小的空间;在后面的直接索引分配方式中,索引表占504B,索引表项大小为6B,故能够存储504B / 6B = 84个索引表项,同(1)问,能够表示84KB大小的空间,两者求和知,在这种混合索引分配的情况下,可支持的单个文件最大为 (216+84)KB.
    针对第②问,根据上面的分析,可以知道文件的大小仅与连续分配有关,而直接索引分配能够表示的磁盘块数就是固定的84块。而在连续分配下,文件大小又仅仅与磁盘块数这个字段的大小有关,下面进行详细分析。我们设表示起始磁盘块块号磁盘块数的字段所需要的字节数分别为x字节和y字节,则首先我们得到等式关系:
    x+y=8(题目要求)
    再一个,由于起始磁盘块块号可以是任意块号,因此,该字段也必须能够表示全部的磁盘空间,这一部分在第(1)问中详细阐述了,也就是最小值为32位,合4字节,即得到不等关系:
    x >= 4
    那么文件大小可以表示为:
    F = (28y + 84)KB
    即在 x+y=8 和 x >= 4 的情况下求 F 的最大值,显然,x=y=4时,F的最大值为(232 + 84)KB = 4TB + 84KB,这已经超过文件系统空间的最大值了,多的必然舍弃,因此这时文件最大只能是4TB

    【答案】
    (1) 4字节;128KB
    (2)
        ① (216+84)KB,合67,194,880字节
        ② 4字节、4字节,最大为4TB


    四、多层索引(间接索引)

    多层索引分配方案与之前讲过的内存分页管理中的多级页表方案类似,只不过这里的直接块(或直接索引)指向一个物理块,一级索引指向若干个直接块,二级索引指向若干个一级索引,以此类推;而在多级分页方案中,一级页表扩展到若干个二级页表,每个二级页表扩展到若干个三级页表,以此类推……最终的每个n级页表才指向若干个内存块,两者正好反过来,下面给出多层索引的示意图:

    在这里插入图片描述


    如图所示,索引节点有三个直接块、一个一级索引和一个二级索引。每个直接块指向一个磁盘块,一级索引指向若干直接块,二级索引指向若干个一级索引,以此类推。

    【例】
    在某操作系统中,文件系统采取多层索引分配方式。在索引节点中,有10个直接块(每个直接块直接指向一个数据块)、1个一级间接块、1个二级间接块和1个三级间接块。假设每个索引块(直接块和所有间接块)和数据块的大小均为4KB,每个索引表项大小为4B。
    (1) 仅仅用直接块最多能够表示多大的文件?
    (2) 该索引节点能够访问到的地址空间为多大?
    (3) 读取文件的第10000B和10MB的内容,分别需要访问磁盘多少次?

    【解】
    (1) 由题目知,该索引结点共有10个直接块,每个直接块只有一个指向数据块的指针,因此所有的直接块加起来能够表示10个数据块的空间,也就最多能够表示10 × 4KB = 40KB的文件。

    (2) 由(1)知,所有的直接块能够表达40KB的空间;一级间接块的大小为4KB,每个索引表项的大小为4B,故1个一级间接块有4KB / 4B = 1024个索引表项,而每个索引表项指向一个直接块,就相当于一个数据块,故1个一级间接块能够表示1024 × 4KB = 4096KB,合4MB的空间;1个二级间接块指向1024个一级间接块,1个一级间接块指向1024个直接块,故1个二级间接块能够表示1024 × 1024 × 4KB,合4GB的空间;同理,1个三级间接块指向1024个二级间接块,1个二级间接块指向1024个一级间接块,1个一级间接块指向1024个直接块,故1个三级间接块能够表示1024 × 1024 × 1024 × 4KB,合4TB。以上结果相加,得到该索引节点能够访问到的地址空间为40KB + 4MB + 4GB + 4TB ≈ 4TB

    (3) 10000B / 4KB ≈ 2.44,2 < 2.44 < 3,故10000B的内容存放于第三个直接块中,直接块直接指向一个数据块,直接从直接块获取数据块的物理地址,根据这个物理地址去磁盘中访问该数据即可,因此访问磁盘2次。由(2)知,全部的直接块可以表示的空间大小为40KB = 0.04MB,全部的一级间接块(其实就有一个)能够表示4MB的内容,全部的二级间接块(其实也就有一个)能够表示4GB的内容。所有的直接块和一级间接块加起来能够表示4.04MB的内容,所有的直接块、一级间接块和二级间接块加起来能够表示4.00404GB的内容,显然4.04MB < 10MB < 4.00404GB,也就是说10MB的位置正好落在二级间接块中,故先读取二级间接块的索引表(访问第一次)找到对应的一级间接块的物理地址,再读取一级间接块的索引表(访问第二次)找到对应的直接块,再读取直接块存放的物理地址(访问第三次),即数据块的地址,再去该地址读取该数据块的内容(访问第四次)。因此,读取10MB的内容时,需要访问磁盘4次

    【答案】
    (1) 40KB
    (2) ≈4TB
    (3) 2次、4次

    更多相关内容
  • 操作系统-UNIX三级索引技术

    千次阅读 多人点赞 2019-11-03 10:35:29
    UNIX三级索引技术 目标:学透软考的一道题目 基础知识 在文件系统中,文件的存储设备通常划分为若干大小相等的物理块,每块长为512或1024字节。文件的物理结构是指文件在存储设备上的存储方法,常用的文件物理...

    UNIX三级索引技术

    目标:学透软考的一道题目

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q7uRjKRl-1572748510148)(C:\Users\JunSIr\AppData\Roaming\Typora\typora-user-images\image-20191103061243398.png)]

    基础知识

    1. 在文件系统中,文件的存储设备通常划分为若干个大小相等的物理块,每块长为512或1024字节。文件的物理结构是指文件在存储设备上的存储方法,常用的文件物理结构有:连续文件串联文件索引文件三种。
    2. 存储空间会被划分成n个物理块,在索引文件中,一个文件会被放入不同的物理块,这时需要索引表指出一个文件分别被拆分存在哪个块,所以索引表里存的是文件碎片的地址

    索引文件

    是一种对文件存储不连续分配的方法,为每个文件建立一张索引表索引表不一定存在文件存放位置,为了减少访问磁盘的次数,一般先读入索引表),索引表中的每一表项指出文件信息所在的逻辑块号和与之对应的物理块号

    对一些大的文件,当索引表的大小超过一个物理块时,会发生索引表的分配问题 ,一般采用多级(间接索引)技术

    多级(间接索引)技术

    这时在由索引表指出的物理块中存放的不是文件存储位置而是存放文件信息的物理块地址(即索引表里存索引表…)

    Unix系统三级索引

    为了使一张索引表(一个数组)能完整存下一个文件

    在Unix系统中,文件的物理结构采用索引方式。定义有一个索引节点字符数组(一张索引表),该字符数组最多可以放下13个地址项(理解成13个盘块或13个物理块),并且规定

    地址项0-9采用直接寻址方法,

    地址项10采用一级间接寻址,

    地址项11采用二级间接寻址,

    地址项12采用三级间接寻址。

    题目分析

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vtxqw8zz-1572748510149)(C:\Users\JunSIr\AppData\Roaming\Typora\typora-user-images\image-20191103100449145.png)]

    根据UNIX的文件存储规定,目测答案为B

    换算过程: 11264字节/1024字节(1KB)=11KB ,由于地址项0-9可直接寻址10个物理盘块,又因为每个盘块的大小为1KB,所以访问文件前10KB采用直接寻址,地址项10采用一次间接寻址,即地址项10里存放的是一级索引表的地址

    因为每个盘块号占4个字节,所以,一级索引表可存放1024(1KB)/4 = 256个物理块地址,所以当访问文件10–>10+256=266KB之间采用一次间接寻址

    同理,二级索引表可存放的则为256256个物理块,三级索引表则为256256乘256

    结构示意图

    在这里插入图片描述

    展开全文
  • 操作系统--文件管理之索引

    千次阅读 多人点赞 2021-01-01 17:49:54
    一级索引 索引存储的结构 ...如此题10^3为1000,所以应建立三级索引。 则有如下示意图 一级一个,二级10个,三级100个,每个索引占1块,所以共计111个。 增量索引 A1个1级索引,A2个2级索引,A

    一级索引

    索引存储的结构

    在这里插入图片描述
    不会出题。。。。

    多级索引

    在这里插入图片描述
    多级索引求占用物理块数
    设有一个包含1000个记录的索引文件,每个记录正好占用一个物理块。一个物理块可以存放10个索引表目。建立索引时,一个物理块应有一个索引表目,试问索引应占几个物理块?

    • 首先求出建立了几级的索引
    • 物理块的n次方恰好大于等于总记录,则N为索引级别。如此题10^3为1000,所以应建立三级索引。
    • 则有如下示意图
      在这里插入图片描述
    • 一级一个,二级10个,三级100个,每个索引占1块,所以共计111个。

    增量索引

    UNIX 3级增量索引
    A1个1级索引,A2个2级索引,A3个3级索引…,磁盘每块大小为XB,每块地址为YB求管理最大文件

    1. 每个磁盘块能装多少个索引项X/Y项
    2. 求有多少个块 ∑ 1 n A i × ( X Y ) i − 1 \sum_{1}^{n} Ai\times \left ( \frac{X}{Y}\right )^{i-1} 1nAi×(YX)i1
    3. 再乘以每块的大小 X B ∗ ∑ 1 n A i × ( X Y ) i − 1 XB*\sum_{1}^{n} Ai\times \left ( \frac{X}{Y}\right )^{i-1} XB1nAi×(YX)i1

    一个文件系统,磁盘每块大小为2KB,每块地址用4B表示。采用UNIX System V文件系统管理的最大的文件是多少?

    • 2KB/4B=512条
    • 直 接 索 引 有 10 个 , 一 级 索 引 有 1 个 所 以 1 ∗ 512 块 , 二 级 索 引 有 一 个 所 以 1 ∗ 512 ∗ 512 块 , 3 级 索 引 一 个 所 以 1 ∗ 512 ∗ 512 ∗ 512 。 直接索引有10个,一级索引有1个所以1*512块,\\二级索引有一个所以1*512*512块,\\3级索引一个所以1*512*512*512。 1011512151251231512512512
    • 所以最大文件为:
      2 K B ∗ ( 10 + 512 + 512 ∗ 512 + 512 ∗ 512 ∗ 512 ) = 20 K B + 1 M B + 0.5 G B + 0.25 T B 2KB*(10+512+512*512+512*512*512)\\=20KB+1MB+0.5GB+0.25TB 2KB(10+512+512512+512512512)=20KB+1MB+0.5GB+0.25TB

    多级索引和增量索引给出两个例题,但实际做题中,都会相互考到,请理解计算过程和原理。

    展开全文
  • 每个索引节点(I节点)有十三个地址项,10个直接地址项,1个一级索引地址,1个二级索引地址,1个三级索引地址,给你一个文件大小通过计算能得知该文件占了那些块。(此为C++编写,仅供参考)
  • 文件系统()---文件系统基础知识

    千次阅读 2022-03-28 22:52:56
    前面主要是学习linux进程管理的调度,其细节越来越多,结合目前移动设备,其调度算法越来越复杂,涉及到芯片涉及,电源管理,多核负载等,这块内容暂时告段落,本章正式进入到文件系统的学习。 现在的磁盘是具有大...

    前面主要是学习linux进程管理的调度,其细节越来越多,结合目前移动设备,其调度算法越来越复杂,涉及到芯片涉及,电源管理,多核负载等,这块内容暂时告一段落,本章正式进入到文件系统的学习。
    到目前为止,我们看到了两项关键操作系统的发展:

    • 进程,是虚拟化CPU
    • 地址空间,是虚拟化的内存
      在这两种抽象的共同作用下,程序运行时就好像它在自己的私有的独立世界中一样,好像它有自己的处理器(或多处理器),好像它有自己的内存空间,这种假象使得对系统的编程变得越来越容易,在这一部分中,我们还需要加一个持久存储。

    现在的磁盘是具有大容量、低成本以及持久化的特点,即使发生断电、磁盘上的数据也不会丢失。但是对于一般用户而言,磁盘的使用是一个非常痛苦的,因为他们不清楚如何驱动一个磁盘,以及计算数据在磁盘上存放的位置。对于操作系统是一个魔术师,它提供用户各种抽象。前面章节我们学习了进程的抽象是CPU,虚拟内存的抽象是内存,对于磁盘来说,操作系统提供给用户就是在磁盘外面包裹一层容易使用的抽象,用户直接与这层抽象打交道,而无需了解磁盘的技术细节。在操作系统中,这层为磁盘提供的抽象就是文件系统

    本章主要是学习文件系统的基本原理,主要涉及以下的内容:

    • 文件系统的存储方式
    • 文件系统的分配方式

    1. 文件系统的分类

    1.1 文件结构

    文件的构造有以下几种方式

    在这里插入图片描述

    • 流式文件: 构成文件的基本单位是字符,文件是由逻辑意义、无结构的一串字符的字节序列,对于操作系统不关心序列的内容是什么,操作系统能看到的都是字节(Byte),其文件的内容只能在用户程序中进行解释。

      把文件看成字节序列提供了最大的灵活性,用户程序可以向文件中写任何内容,并且可以通过任何方便的形式命令,操作系统不提供任何帮助,也不会构成障碍。所有的unix版本和windows都使用这种文件模型

    • 记录式文件: 文件是具有固定长度的记录的序列,每个记录都有其内部结构,可以按照记录进行读、写、查找等等操作。

    • 树式文件: 这种组织结构中,文件由一颗记录树构成,记录树的长度不一定相同,每个记录树都在记录中的固定位置上包含一个key字段,这颗树按照key进行排序,从而可以对特定的key进行快速查找。如图,用户可以读出制定Hen记录,而不用关系记录在文件中的确切位置,用户也可以在文件中添加新记录,但是用户不能决定添加在何处位置,该位置由操作系统决定。

    1.2 文件的存储

    对于文件是存储介质上的存放方式,对于物理结构,主要解决两个问题:

    • 假设一个文件被划分成N块,这N块在磁盘上是怎么存放的?
    • 其地址(块号)是如何记录的?

    1.2.1 连续结构

    对于不同的文件系统采用不同的方式,首先我们从文件存储的结构来看看连续存储的结构,把每个文件作为一连串连续的数据块存储在磁盘上。因此,在具有1KB块的数据上,将为50KB分配50个连续的磁盘块

    在这里插入图片描述

    从磁盘开始处(块0)处开始写入占用4块长度的File A,然后是一个占用6块长度的File C,紧跟着在A的末尾开始写,每个文件都会在新的文件块中写,对于这种方式有什么缺点呢?是不是跟我们的内存管理很像,例如D/E被删去了,此文件所占用的块也随之释放,就会在磁盘中留下一些空闲块,这个是不是跟内存管理很像,就会形成很多的磁盘碎片(外碎片)。

    对于这种连续存储结构的优缺点:

    • 优点
      • 连续文件存储实现比较简单,支持顺序存取和随机存取,只需要记住两个数字就可以了,一个是第一块的文件地址和文件块的数量,给定第一个块的编号,就可以通过简单的算法找到任何其他块的编号
      • 读取性能比较强,可以通过一次操作从文件中读取整个文件,只需要一次寻找第一个块,对于磁盘的访问,后面就不需要寻道时间和旋转延迟,所需要磁盘寻道次数和寻道时间最少

    所以,连续存储结构分配方式具有实现简单,高性能的特点

    • 缺点

      • 文件不能动态增加,预留空间的方式带来浪费,重新分配,就需要重新移动
      • 不利于文件插入删去
      • 也会跟内存管理的方式一样,带来外部碎片问题,刚开始的时候,碎片问题不是一个大问题,因为每个新文件都会在之前文件的结尾处进行写入。但是,当磁盘最终被填满后,要么压缩磁盘,要么重新使用空闲块的空间。压缩磁盘的开销太大,因此不可行;空闲块需要维护一个空闲列表,但是页会存在一个问题,为空闲块匹配合适大小的文件,需要知道该文件的最终大小。

    在这里插入图片描述

    想象以下这种的设计结构,例如用户想启动一个word进程,创建文档,应用程序首先会询问最终创建的文档有多大,否则应用程序就不会继续运行。如果空闲块的大小要比文件的大小小,程序就会终止。因为没有连续的空间来存储该文件,但是实际上磁盘上有很多零散的碎片。

    在许多年前,连续分配由于其简单和高性能被实际使用在磁盘文件系统中,对于生活中,CD-ROM就广泛的使用了连续分配的方式,这种制度光碟只能写入一次,信息将永久的保存,使用时通过光碟的移动读出信息。后来由于用户不希望创建文件时,就指定文件的大小,于是就慢慢放弃放弃了这种想法。

    1.2.2 链接结构

    一个文件的信息存放在若干不连续的物理块中,各个块之间通过指针来链接,前一个物理块指向下一个物理块

    在这里插入图片描述

    下面此磁盘块的链接方式存储文件,每个块的第一个字作为指向下一个块的指针,块的其他部分存储数据,如下是磁盘的整个链表分配方案

    在这里插入图片描述

    与连续分配方案不同,这一方法可以充分利用每个磁盘块,除了最后一个磁盘块外,不会因为磁盘碎片浪费存储空间。同样,在目录项中,只能存储第一个文件块,那么其他文件块也能够被找到。

    链表的方式存放是离散的,不用连续的,于是就可以消除磁盘碎片,可大大提高磁盘空间的利用率,同时文件的长度可以动态扩展

    对于这种连续链接结构的优缺点:

    • 优点:

      • 提高了磁盘空间的利用率,不存在外部碎片问题
      • 有利于文件插入和删去
      • 有利于文件动态扩充
    • 缺点:

      • 存取速度慢,不适用于随机存取,尽管顺序读取非常方便,但是随机访问却很困难,这也是数组和链表的一大区别
      • 可靠性问题,如指针出错
      • 更多的寻道次数和寻道时间
      • 链接指针占用一定的空间,许多程序都是以长度为2的整数次幂来读写磁盘,由于每个块的前几个字节被指针所使用的,所以要读出一个完成的块大小信息,就需要当前块的信息和下一块的信息拼凑而成,因此就引发了查找和拼接的开销

      1.2.3 使用内存表进行链表分配

      由于连续分配和链表分配都有其缺点,所以提出了使用内存表来解决该问题,取出每个磁盘块的指针,把它们放在内存中的一个表中,就可以解决上述链表中的两个不足之处,
      在这里插入图片描述

      这个图中有两个文件,其内容为

      • 文件A依次使用磁盘块的地址为4、7、2、10、12,文件A从地址4开始,顺着链表就能找到文件A的全部磁盘块
      • 文件B依次使用磁盘块的地址为6、3、11、14,文件B从第6块开始,顺着链表就能找到文件B的全部磁盘块

      在这里插入图片描述

      同时会发现,这两个链表都以不属于有效磁盘编号的特殊标记(-1)结束,内存中这种表格称为文件分配表。但是使用这种方式,就是必须要把整个链表放到内存中,对于1TB的磁盘和1KB的大小块,那么这张表就需要有10亿项,每一项对应于这10亿个磁盘块中的一块,每项至少3个字节,为了提高查找速度,有时需要4个字节,那么这张表就需要3GB或2.4GB的内存。对于FAT的管理方式采用这种方式,但是不能较好的扩展在大型磁盘中,由于其比较实用,并仍被各个windows版本所支持。

      1.2.4 索引结构

      索引分配允许文件离散地分配在各个磁盘块中,系统会为每一个文件建立一个索引表,索引表中记录了文件中每个逻辑块对应的物理块。索引表存放的磁盘块叫做索引块,文件数据存放的磁盘块叫做数据块

      索引的实现是为每个文件创建一个「索引数据块」,里面存放的是指向文件数据块的指针列表,说白了就像书的目录一样,要找哪个章节的内容,看目录查就可以。

    在这里插入图片描述

    我们首先通过文件名,找到索引表对应的块号为24,发现24的索引表的对应的㘞块号是1->8->3->14->28。

    在这里插入图片描述

    首先用户给出需要访问的逻辑块号i,操作系统需要找出所需要访问的文件的目录项,在FCB中可以找到索引块对应的物理块号,通过该物理块号,可以找到索引表,将索引表读入内存,就能在索引表找到逻辑块i对应的物理块。所以,支持顺序访问和随机访问,文件拓展实现容易(只需要给文件分配一个空闲块,并增加一个索引项即可),但是索引表需要占用一定空间。

    优点:

    保持了链接结构的优点,又解决了其缺点

    • 既能满足顺序存取,又能随机存取
    • 满足了文件动态增长,插入,删去的要求
    • 能充分利用磁盘空间

    缺点:

    • 较多的寻道次数和寻道时间
    • 索引表本身带来了系统开销,如内存、磁盘空间、存取时间

    那我们现在需要考虑另外一个问题,假设磁盘块的大小为512byte,一个索引项为4byte,那么一个磁盘块只能记录128个索引项,但是如果一个文件大小超过了128个磁盘块,那么索引项使用一个磁盘块就无法存放了,此时该如何解决呢?

    我们比较容易想到的就是,既然一个磁盘块存放不下,那么就使用两块,对的,这种想法是没错的,但是我们要考虑的是在使用多个磁盘块的时候,如果将这多个磁盘块关联起来,同时还能不降低查询效率?这里就产生如下的方案:

    • 链接索引方式: 一个盘块存储一个索引表,多个索引表链接在一起
    • 多级索引方式: 将文件的索引表地址放在另一个索引表中
    • 综合模式: 直接索引方式与间接索引方式结合

    链接索引方式

    它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针,于是当一个索引数据块的索引信息用完了,就可以通过指针的方式,找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题,万一某个指针损坏了,后面的数据也就会无法读取了。

    img

    多级索引方式

    还有另外一种组合方式是索引 + 索引的方式,这种组合称为「多级索引块」,实现方式是通过一个索引块来存放多个索引数据块,一层套一层索引,像极了俄罗斯套娃是吧。

    img

    在这里插入图片描述

    linux采用三级索引结构

    • 每个文件的索引表有15个索引项,每项2个字节
    • 前12项直接存放文件的物理块号(直接寻址)
    • 如果文件大于12块,则利用第13项指向一个物理块,在该物理块中存放文件物理块的块号(一级索引),假设扇区大小为512字节,物理块等于扇区块大小,一级索引表可以存放256个物理块
    • 对于更大的文件,还可以利用第14和第15项,作为二级和三级索引表

    在这里插入图片描述

    所以,这种方式能很灵活地支持小文件和大文件的存放: - 对于小文件使用直接查找的方式可减少索引数据块的开销; -对于大文件则以多级索引的方式来支持,所以大文件在访问数据块时需要大量查询;

    这个方案就用在了 Linux Ext 2/3 文件系统里,虽然解决大文件的存储,但是对于大文件的访问,需要大量的查询,效率比较低。

    文件方式的存储做个总结

    方式访问磁盘次数优点缺点
    顺序存储需访问磁盘1次顺序存取速度快,当文件定长时可以根据文件起始地址及记录长度进行随机访问要求连续的存储空间,会产生外部碎片,不利于文件的动态扩展
    链表存储需要访问磁盘n次无外部碎片,提高了外存空间利用率,动态增加较方便只能按照文件的指针链顺序访问,查找效率低,指针信息存放消耗内存或磁盘空间
    索引存储m级需要访问m+1次可以随机访问,易于文件的增删索引表增加存储空间的开销,索引表查找策略对文件系统效率影响较大

    2 参考文档

    操作系统——文件系统概述、文件逻辑地址、目录、物理地址

    一口气搞懂「文件系统」,就靠这 25 张图了

    现代操作系统

    展开全文
  • 一个采用三级索引结构的UNIX 文件系统中,假设物理块大小为1KB,用64位表示一个物理块号。主索引表含有13 个块地址指针,其中前10 个直接指向盘块号,第11 个指向一级索引表,第12 个指向二级索引表,第13 个指向...
  • 文件索引习题

    千次阅读 2019-01-08 17:46:52
    1、设文件索引结点中有8地址项,每地址项大小为4字节,其中5地址项为直接地址索引,2地址项是一级间接地址索引,1地址项是二间接地址索引,磁盘索引块和磁盘数据块大小均为1KB。则可表示的单个文件最大...
  • 数据结构之索引文件

    千次阅读 2022-04-21 15:46:54
    这类包括文件数据区和索引表两大部分的文件称做索引文件。 图1所示为两索引表的例子。索引表中的每项称做索引项。不论主文件是否按关键字有序,索引表中的索引项总是按关键字(或逻辑记录号)顺序排列。若数据区中...
  • 文件系统采用索引节点管理,其磁盘索引块和磁盘数据块大小均为 1KB 字节且每文件索引节点有 8 地址项 iaddr[0]~iaddr[7],每地址项大小为 4 字节,其中 iaddr[0]~iaddr[4]采用直接地址索引,iaddr[5]和 ...
  • 假设文件系统采用索引节点管理,且索引节点有8地址项 iaddr[0] ~ iaddr[7] ,每地址项大小为4B。 iaddr[0] ~ iaddr[4] 采用直接地址索引, iaddr[5] 和 iaddr[6] 采用一级间接地址索引, iaddr[7] 采用...
  • 操作系统 第七章 文件管理

    千次阅读 2020-07-01 11:06:32
    从用户的观点看,操作系统中引入文件系统的目的是(D)。 A. 实现虚拟存储 B....C....D....文件系统中,文件访问控制信息存储的合理位置是(A)。...A....B....C....D....下列关于索引文件的叙述中, (A)... 索引文件的索引表中每记录的索引项可..
  • 【操作系统文件管理

    千次阅读 2021-01-17 12:37:27
    文件 F1 的当前引用数值为 1 ,先建立文件 F1 的符号链接(软链接)文件 F2 ,再建立文件 F1 的硬链接文件 F3,然后删除文件 F1,此时文件 F2 和文件 F3 的引用计数值分别是(1,1)。
  • Linux文件系统课后作业

    千次阅读 多人点赞 2021-03-23 21:47:01
    2、若盘块大小为4KB,块地址用4字节表示,文件系统采用索引组织方式,索引项0至索引项9为直接索引,索引项10为级间接索引,索引项11为二级间接索引,索引项12为三级间接索引。若文件索引节点已在内存中,请计算读出文件...
  • 操作系统——文件系统

    千次阅读 2022-03-06 23:57:18
    文章目录文件系统的功能规划文件系统的基本组成一切皆文件目录项和目录是一个东西吗?那文件数据是如何存储在磁盘的呢?虚拟文件系统文件的物理结构文件块文件分配方式连续分配非连续空间存放方式链式分配隐式链接...
  • 自定义文件系统下的磁盘访问次数计算

    千次阅读 多人点赞 2016-10-20 15:07:19
    一个文件系统如图所示:图中的方框表示目录,圆圈表示普通文件。根目录常驻内存,目录文件组织成链接文件,不设FCB,普通文件组织成索引文件。目录表指示下一文件名及其磁盘地址(各占2B,共4B)。若下级文件是目录...
  • 【操作系统】多级索引、混合索引例题

    万次阅读 多人点赞 2020-08-22 16:21:28
    多级索引: 文件系统采用多重结构搜索文件内容。设块长为512B,每个块号占3B,如果不考虑逻辑块号在物理块中所占的...一个三级索引可存放文件的大小为:170×170×170×512=251×107B 混合索引: eg1/某系统中磁盘的每
  • 2.文件系统采用文件目录可以( ) 编号 选项 A 缩短访问存储器的时间 B 实现文件共享 C 节省内存空间 D 解决不同用户间的文件命名冲突 3.文件的存储管理实际上是对( )的管理 编号 选项 ...
  • 操作系统文件系统练习题

    万次阅读 多人点赞 2015-12-28 17:19:37
    1.Linux系统有几种类型文件?...相同点是,它们都是文件,都有一个文件名和i节点号。 不同点是,普通文件的内容为数据,目录文件的内容为目录项或文件名与i节点对应表,而设备文件不占用磁盘空间,通
  • 1、磁盘提供大量的外存空间来维持文件系统,磁盘的两特点,使其成为存储多文件的方便媒介: ①可以原地重写;可以从磁盘上读块,修改该块,并将它写回到原来的位置 ②可以直接访问磁盘上的任意块信息。...
  • 文件系统试题

    千次阅读 2019-01-22 16:23:59
    文件控制块(FCB)包含一个512B的索引表。如果索引表只采用直接索引结构,存放文件占用的磁盘块号。在该文件系统中,单个文件最大长度为多少块? 答案 128 某文件系统空间的最大容量为16TB(1T=2的40次方),以存储块为...
  • 文件系统的文件目录项中有6个表目的数组用作描述文件的物理结构,该数组的前4个表目用作直接索引,第5个表目为一间接索引,最后一个表目用作二间接索引,磁盘块的大小为512字节,块号占2字节。请回答下列问题...
  • 【操作系统】文件系统大作业

    千次阅读 2022-04-14 12:56:29
    一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、链接、i-node(10个直接地址,一个一级间接、一个二级间接和一个三级间接)分配方案时,每块大小为4KB,每块地址用4B表示,问: (1)各文件系统管理的...
  • 北航操作系统课程-第十次作业-文件系统

    千次阅读 多人点赞 2020-06-04 12:26:34
    北京航空航天大学计算机学院-2020春操作系统课程,理论课第十次作业,内容为文件系统。 题目作者为北航计算机学院操作系统课程组,答案为博主原创。水平有限,无法保证作答正确性,如有错误敬请批评指正。部分作答...
  • 操作系统考点之文件系统要点总结及目录分解法

    千次阅读 多人点赞 2020-12-21 15:50:50
    如题: 一个文件系统中,其FCB占64B,一个盘块大小是1KB,采用目录。假定文件目录中有3200个目录项,则查找一个文件平均需要访问磁盘( )次。 分析:没有说目录分解,那么FCB的有序集合,就是目录。也就是题中...
  • 操作系统文件的分类

    千次阅读 2020-12-13 21:26:37
    对于常见的文件分类进行了简单的介绍,另外对于文件的逻辑结构以及物理结构进行了详细的介绍!
  • 摘要 星际文件系统是一种点对点的分布式文件系统, 旨在连接所有有相同的文件系统的计算机设备。在某些方面, IPFS类似于web, 但...这形成了一个广义的Merkle DAG 数据结构,可以用这个数据结构构建版本文件系统,...
  • 操作系统-文件的结构以及文件管理

    千次阅读 2020-07-29 22:21:48
    文件的管理,文件的结构有哪几种,文件类型,文件属性,文件常用的几种操作你都了解多少?
  • 操作系统:文件系统的实现

    千次阅读 2020-12-31 14:39:13
    目录文件系统结构二、文件系统实现1.概述2.虚拟文件系统三、目录实现1.线性列表2.哈希表四、磁盘空间的分配方法1.连续分配2.链接分配3.索引分配五、磁盘空闲空间的管理1.位向量2.链表3.组4.计数六、文件系统的...
  • 口气搞懂「文件系统」,就靠这 25 张图了

    万次阅读 多人点赞 2020-08-13 21:48:43
    前言 不多 BB,直接上「硬菜」。 正文 文件系统的基本组成 文件系统是操作系统中负责管理持久数据的子系统,说简单点,就是负责把用户的文件存到磁盘硬件中,因为即使计算机断电了,磁盘...Linux 文件系统会为每..

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,270
精华内容 58,108
关键字:

一个采用三级索引文件系统