操作系统复习笔记5

2024-07-04 13:50| 来源: 网络整理| 查看: 265

6．磁盘与文件系统磁盘的结构和基本概念磁道：磁盘上的同心圆盘面：磁盘的某一面扇区（盘块）：磁道划分为扇区，每个扇区固定大小柱面：所有盘面上相对位置相同的磁道组成柱面磁头磁头臂磁盘地址组成：柱面号·盘面号·扇区号

（其他基本概念详见教材）

磁盘的调度（★★★★★）存取时间的计算寻找时间 $T_s$ ：磁头移动到指定磁道的时间（下式中，m 是和磁盘驱动器速度相关的常数，移动跨越 n 条磁道，s 为磁臂启动时间）

\[ T_s=m\times n + s \]

延迟时间 $T_r$ ：磁头定位到某一磁道的扇区所需要的时间（下式中 r 为磁盘转速）

\[ T_r=\frac{1}{2r} \]

传输时间 $T_t$ ：磁盘读出或写入数据经历的时间（下式中 b 为每次读/写的字节数， N 为一个磁道上的字节数）

\[ T_{t}=\frac{b}{rN} \]

总平均存取时间为

\[ T_a=T_s+\frac{1}{2r}+\frac{b}{rN} \]

调度算法（★★★★★）算法名称调度标准优点缺点先来先服务（FCFS）先来先服务公平、简单平均寻道距离大最短寻找时间优先（SSTF）选择距离当前磁头位置最短的请求性能比FCFS好不能保证平均寻道时间最短，可能出现“饥饿” 扫描算法（SCAN，电梯调度）选择当前磁头运动方向上且距离当前磁头位置最短的请求寻道性能好，可避免“饥饿” 不利于远离磁头一端的请求循环扫描算法（C-SCAN）类似 SCAN 算法，但是当一个方向上处理完成后回返时，直接移动到起始端，不响应途中的任何请求。到达起始端后，才继续响应消除了对两端磁道请求的不公平性 -------- 磁盘的性能改善和容错

（见教材 8.4 8.5节）

外存分配方法与物理文件组织连续分配每个文件在磁盘上占有一组连续的块

连续分配链接分配每个文件散落在磁盘的各个碎片区域，每一块都存有指向下一块的指针

链接分配索引分配单独使用一块来存储文件各块存储位置，构成索引块

索引分配文件存储空间的管理空闲表法类似内存中的动态分配（回看内存管理）空闲链表法空闲盘块链空闲盘区链位示图法（★）用二进制的一位来表示某一盘块的使用情况： 1 表示已分配， 0 表示未分配（空闲）盘块的分配算法（行列号从 1 开始）找到合适的 “0” 的二进制位计算盘块号 b ：$b = (i-1)n+j$ （其中 i 代表行数，j 代表列数，n 代表每行位数）修改位示图矩阵：$map[i,j] = 1$ 盘块的回收算法块号 b 转换为行 i 列 j 号$i = (b-1)\ DIV\ n + 1,j=(b-1)\ MOD\ n + 1$ 修改位示图矩阵：$map[i,j] = 0$ 成组链接法

（详见教材）

逻辑文件组织无结构文件（流式文件）以字节为单位，如源代码文件等有结构文件（记录式文件）由一条条记录组成，每条记录中包含若干数据项。顺序文件按某种顺序排列形成的文件排列方式分为串结构和顺序结构串结构：通常按存入时间先后顺序排序顺序结构：用户指定关键字，按关键字排序索引文件建立索引表，为每个记录设置一个表项，从而加快检索记录的速度可按关键字建立索引，一个索引文件可能被多个索引表索引（如图书信息可按图书编号、图书名、作者等进行索引查找）索引顺序文件为每个文件建立索引表，将记录分组，只为每组的第一条记录建立索引表项可以有一级、二级、多级索引顺序文件查找效率比较（假设文件所含有的记录数为 N ，为检索到指定含有关键字的记录）顺序文件：平均需要查找 $\frac{N}{2}$ 索引顺序文件：平均需要查找 $\sqrt{N}$ 直接文件（散列文件）通过哈希函数，完成从关键字到物理地址的直接转换。文件的基本操作基本操作创建删除读写设置读/写位置 “打开”和“”关闭“”（★★★★）打开：系统将指名文件的属性（包括该文件在外存上的物理位置），从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引号）返回给用户，即建立了用户和指定文件之间的连接。关闭：断开上述连接 “打开”并非真正打开，而是读取文件相关属性；“关闭”并非真正关闭，而是断开连接。文件目录及其管理目录管理的要求实现“按名存取” 提高目录检索速度文件共享允许文件重名文件控制块（FCB）作用类似进程管理中的 PCB ，用来存放控制文件需要的各种信息，包括：基本信息：文件名、物理位置、逻辑结构、物理结构等存取控制信息：存取权限使用信息：创建时间、修改时间从而实现了“按名存取” FCB 的有序集合成为文件目录，一个 FCB 就是一个文件目录表项创建新文件时，也会创建一个对应的 FCB 索引结点为加快按文件名检索目录文件而引入。（无索引时，需依次检索 FCB，但是 FCB 中很多信息对于检索目录是多余的，因此把需要的信息抽出，形成索引【通常包括文件名、索引结点编号】，从而可以加快检索速度）根据索引结点所处位置不同，分为磁盘索引结点内存索引结点目录结构单级目录结构目录表类似一维数组，存储目录表项评价简单，实现了“按名存取” 查找速度慢不允许重名不便于共享只适用于单用户两级目录结构顶级目录表类似二维数组，第一维为用户名、第二维存储指向用户目录表的指针二级目录表存储对应用户的目录表项评价能满足目录管理的四个要求树形（多级）目录结构（★★★）对二级的推广，现代 OS 常用包括以下目录操作创建目录删除目录改变目录移动目录链接操作查找目录查询技术线性检索法（★★★）单级目录情况类似顺序查找算法流程树形目录情况读入第一个文件分量（文件分量即文件路径中被 “/” 分隔的字符串），在第一级目录表中，顺序查找，找到匹配，得到下一级目录表的块号读入下一个文件分量，在对应级目录表中，顺序查找，找到匹配，得到下一级目录表的块号以此类推，直至目录中所有文件分量都已处理完毕或者是未找到退出 Hash 方法利用 Hash 函数完成从文件名到索引值的映射，之后再用得到的索引值找到目录文件共享和保护文件共享基于有向无循环图

（详见教材）

利用索引结点（硬链接）（★★★）在用户目录表中，其表项只包括文件名和指向索引结点的指针，其他的相关信息放在索引结点中不同用户对共享文件创建、删除操作中的链接计数

索引分配利用符号链接（软链接）（★★★）共享时，会新建一个 LINK 文件，这个 LINK 文件中只含有被链接文件的路径

硬链接查找较快

文件保护有口令保护、加密保护、访问控制等方法访问控制类型读写执行添加删除列表清单根据用户身份进行控制，为文件和目录添加一个访问控制表，规定每个用户名及其所允许访问的类型解题技巧及重要结论软链接、硬链接中的引用计数问题建立软链接（符号链接）：引用计数直接复制硬链接：引用计数加一删除软链接：删除操作，对软链接不可见（注意软链接只保存了文件的路径）。当之后依据软链接访问文件，发现不存在时，此时可以删除符号链接硬链接：删除文件，引用计数减一；若引用计数不为零，则不能删除所共享的文件例题（2009·408统考） F1 引用计数为 1 ，建立符号链接（软链接）F2 ，再建立硬链接 F3 ，删除 F1 ，则此时 F2 、F3 引用计数为解答：建立 F2 ，由于是软链接，引用计数直接复制，为 1 ；再建立 F3 ，F1 和 F3 的引用计数都加一，为 2；删除 F1，不影响 F2 但影响 F3 ，故 F2 仍为 1 ，F3 要减掉一为 1 混合索引中的计算相关概念文件索引结点：存储索引地址。索引地址类型又分为直接地址：此地址直接指向磁盘数据块。所以$磁盘数据块的块数 = 文件索引结点中含有直接地址项的项数$ 一级间接地址索引：顶级索引节点（在这里便是文件索引结点）存放索引，通过这个索引找第二张表，才能找到指向磁盘数据块的地址因此$磁盘数据块的块数 = 磁盘索引块地址项的项数=\frac{磁盘索引块大小}{地址项大小}$ 二级间接地址索引：顶级索引节点存放一级索引，通过这个索引找第二张表；找到二级索引，通过这个索引查第三张表才能找到指向磁盘数据块的地址故$磁盘数据块的块数 = 磁盘索引块地址项的项数^2=(\frac{磁盘索引块大小}{地址项大小})^2$ n 级间接地址索引，以此类推有$磁盘数据块的块数 = 磁盘索引块地址项的项数^n=(\frac{磁盘索引块大小}{地址项大小})^n$ 典型例题（2010·408）文件索引结点 7 个地址项，其中 4 个直接地址、2个一级间接地址索引、 1 个 2 级间接地址索引，每个地址项大小为 4 B，磁盘索引块和磁盘数据块大小均为 256 B，则可表示的单个文件最大长度是分析： 4 个直接地址：4 × 256 B 2 个一级间接：2 × (256/4) × 256 B 1 个二级间接：1 × (256/4) × (256/4) × 256 B 总计：上述三项之和文件系统二级索引分配，磁盘块大小 1KB，每个盘块号占 4B，单个文件最大长度为分析：依题意知，共有 1KB / 4B = 256 个索引项由于是二级索引，故最大文件长度为 256 × 256 × 1KB = 64 MB 总结（公式补充） $索引项个数 =\frac{磁盘块大小}{盘块号大小}$ $文件长度= 索引项个数^{索引级数}\times 磁盘块大小$ 文件系统中， FCB 占 64 B，一个盘块大小为 1 KB，一级目录，设文件目录中有 3200 个目录项，则查找一个文件平均需要访问几次磁盘分析依题意知，共有 3200 × 64 B / 1 KB = 200 个盘块一级目录，平均访问磁盘为 200 / 2 = 100 次总结：（公式补充） $目录项盘块数 = \frac{目录项项数\times FCB大小}$ 一级目录：$平均访问磁盘次数=\frac{目录项盘块数}{2}$（类似文件的顺序查找）（2015·408）文件索引结点中，10 个直接、1个一级、1个二级，磁盘块大小 1 KB，索引指针大小 4 B 。若文件索引结点已经读入内存，则把该文件偏移量（按字节编址）为 1234 和 307400 处所在的磁盘块读入内存，需访问的盘块数分别是分析 10 个直接地址：10 × 1 KB = 10 KB 1 个一级间接：1 × ( 1 KB / 4 B ) × 1 KB = 256 KB 1 个二级间接：1 × ( 1 KB / 4 B ) × ( 1 KB / 4 B ) × 1 KB = 64 KB 1234 B < 10 KB，地址可以直接得到，只需再访问 1 次磁盘，获取该地址的数据即可 10 KB + 256 KB < 1234 B < 64 MB，可知该文件内容在二级索引指针所指向的某个磁盘块中。访问 2 次磁盘，获得地址；再依此地址访问 1 次磁盘，获得数据。共需要 3 次总结磁盘访问次数 = 索引级数（为了找到地址。P.S.直接地址当作 0 级）+ 1（为了找到数据：依地址，取数据）设有一记录文件，采用链接分配方式，逻辑记录的固定长度为 100 B，在磁盘上存储时采用记录成组分解技术，盘块长度为 512 B。若该文件的目录项已经读入内存，则对 22 个逻辑记录完成修改后，共启动磁盘多少次分析第 22 条记录的地址为 22 × 100 B = 2200 B 2200 B / 512 B = 4 还有剩余，故在第 5 个盘快上。链接分配，要找到第五个盘块的地址，需要从第一个开始，依次寻找，需要 5 次此盘启动，才能拿到第 22 个逻辑记录的物理地址。之后依据这个物理地址，访存修改，还需要启动 1 次磁盘。所以共需 6 次位示图相关（2015·408）文件系统中用位示图，位图位于 32 ~ 127 号块中，每个盘块占 1024 B，盘块和块内字节均从 0 号开始编号。假设要释放盘块号为 409612 ，则位图中要修改的位所在的盘块号和块内字节序号分别是分析： $盘块号=起始块号+\lfloor\frac{盘块号}{盘块大小\times 8}\rfloor$ $块内字节号 =盘块号 mod (盘块大小)/8$ 数据带入公式，即可参考资料计算机操作系统.汤小丹等 2020年操作系统考研复习指导.王道论坛

【本文地址】

公司简介

联系我们