操作系统 存储管理

操作系统 存储管理

Posted by julyerr on February 25, 2018

紧接着上一篇操作系统内存管理总结,这篇文章就磁盘、文件系统等方面的内容进行总结。

磁盘管理

磁盘结构
相对于内存等电气设备而言,磁盘采用机械方式记录数据,速度慢上几个数量级。

磁盘调度算法
为了尽可能降低io操作,提出了多种磁盘调度算法

  • 先来先服务—FCFS 公平、简单,平均寻道距离大,仅应用在磁盘I/O较少的场合
  • 最短寻道时间优先—SSTF 优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。简单有效,可能出现“饥饿”现象。
  • 扫描算法(电梯法)—SCAN 磁盘先向一个方向移动,响应完对应的请求之后,才改变方向。具体过程如下图所示
  • 循环扫描(C-SCAN)算法 在扫描算法的基础上规定磁头单向移动来提供服务

文件管理

文件组织结构

逻辑结构
指用户观点出发所看到的文件组织形式

  • 字符流式文件 没有结构、一串有序字符的集合。当前操作系统中的普通文件都是流式文件。
  • 记录式文件 文件由多个记录构成,每个记录有一个键,可按键查找。如果所有记录长度相同,这种文件称为定长记录文件。通常用于经常对文件内容进行修改、追加、查找等场景中,如数据库文件。可采用多种方式组织这些记录:
    • 顺序文件 记录按照某种顺序排列所形成的文件,记录通常是定长的,能较快查找到文件中的记录。存取效率较高,但是增加和删除一个文件比较困难。
      • 串结构 各个记录之间的顺序与关键字无关,通常按照时间先后排序
      • 顺序结构 文件中所有记录按照关键字排列,可以按照关键词长度从大到小排列
    • 索引文件 记录为可变长度时,通常建立一张索引表,并为每个记录设置一个表项,加快对记录检索的速度
    • 索引顺序文件 为文件建立一张索引表,为每一组记录中的第一个记录设置一个表项
    • 直接文件 根据给定的记录键值,直接获得指定记录的物理地址。
    • hash文件 利用Hash函数可将记录键值转换为相应记录的地址。通常由Hash函数所求得的并非是相应记录的地址,而是指向一目录表相应表目的指针,该表目的内容指向相应记录所在的物理块。

物理结构

  • 顺序结构(连续文件) 特点 结构简单,存取速度较快;但是文件不能动态增长,不适用经常修改的文件中。
  • 链接结构(串联文件)
    • 隐式链接 在文件目录的每个目录项中,都须含有指向链接文件第一个盘块和最后一个盘块的指针
    • 显示链接 把用于链接文件各物理块的指针,显式的放在内存的一张链接表(FAT表)中,该表在整个磁盘仅设置一张。 特点 文件长度可以动态增长,但搜索效率较低,不适合随机存取的场景中。
  • 索引结构(索引文件) 特点 文件长度可以动态增长,也可以实现随机存取;但是索引表增加了空间开销,索引的多次访问时间开销较大。
  • 混合索引分配方式将多种索引分配方式相结合而形成的一种分配方式

文件存取方式

  • 顺序存取 按照文件的逻辑地址顺序存取
  • 随机存取 改变读写指针到欲读写处读写
  • 按键存取 给定关键字或者记录名进行存取

空闲块管理

文件存储空间通常是分成若干个大小相等的物理块,并以块为单位来交换信息的。因此,文件存储空间的管理实质上是一空闲块的组织、分配和回收等问题。常见有下面四种管理方式

  • 空闲块表 将所有空闲块记录在一个表中,适用于连续文件中
  • 空闲块链表 将所有空闲块链接起来,链较长,效率低
  • 成组链接法(空闲块链的扩展) 将所有空闲块分成若干组,每个组中采用堆栈结构进行管理,通常使用于Unix操作系统中。 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块中,由各组的第一个盘块可链成一条链(盘块链);最末一组第一个盘块中存放“0”,作为空闲盘块链的结束标志。每一组相当于一个栈,s_free[0]相当于栈底,s_free[99]相当于栈顶。
    分配
    首先检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格。若该盘块号已是栈底,即S.free[0],这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号,因此,须调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容,并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后,再分配一相应的缓冲区(作为该盘块的缓冲区)。最后,把栈中的空闲盘块数减1 并返回。
    回收
    将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1 操作。当栈中空闲盘块号数目已达100 时,表示栈已满,便将现有栈中的100个盘块号记入新回收的盘块中,再将其盘块号作为新栈底。
    以下为一个示例说明: 上图为操作之前,空闲盘块栈分配情况
    在为某个文件分配3个盘块后,系统要删除另一文件,并回收它所占的5个盘块,它们的盘块号依次为700、711、703、788、701,盘块链接情况如图所示
  • 位图法 使用二进制位反映磁盘分配使用情况,1表示已经分配,0则为分配,常用于微型机和小型机中

文件目录管理

文件组成

  • 文件体 文件本身内容
  • 文件说明(文件控制块FCB) 存放为管理文件所需的相关信息,包括文件名、第一个物理块的地址、存取控制和管理信息等。文件说明组成目录文件,文件系统利用目录文件完成按名存取和对文件信息的共享和保护。

文件目录

  • 单级目录 所有存入系统文件建立一张表
  • 二级目录 文件说明信息组织成目录文件,以用户为单位将各自的文件说明划分为不同的组。
  • 多级目录 目录也是文件,除最低一级物理块中装有文件信息外,其他每一级目录中存放的都是下一级目录或文件的说明信息。

目录查询技术

  • 线性检索法 用户提供的文件名是由多个文件分量名组成的路径名,查找/usr/ast/mbox过程如下
  • Hash方法 利用用户提供的文件名并将它转换为文件目录的索引值,再利用该索引值到目录中去查找

参考资料