操作系统 第八章磁盘存储器的管理

8.1 磁盘 I/O

8.1.1 提高 I/O 速度的主要途径

  • 选择性能好的磁盘
  • 采用适当的调度算法
  • 设置磁盘高速缓冲区 #### 8.1.2 磁盘性能描述

  • 数据的组织
    • 盘片(Platter):每个盘片有两面,都可记录信息。
    • 磁道(Tracks):盘片表面上以盘片中心为圆心,不同半径的同心圆称为磁道。
    • 扇区(Sectors) :盘片被分成许多扇形的区域,每个区域叫一个扇区,硬盘每个扇区可存储 512 字节信息。FAT32 模式下,每个扇区的容量为 4KB。每个扇区的大小相当与一个盘块。
    • 磁头(Heads):每个盘片的每一面都会有一个读写头,来读取相应盘面的内容。习惯用磁头号来区分。
    • 柱面 (Cylinders):不同盘片相同半径的磁道所组成的圆柱称为柱面。磁道与柱面都是表示不同半径的圆,在许多场合,磁道和柱面可以互换使用。
    • 存储容量 = 磁头数 × 磁道(柱面)数 × 每道扇区数 × 每扇区字节数
  • 磁盘的类型

    • 固定头磁盘

      每条磁道上都有一个读/写磁头,所有的磁头被装入一个磁臂,通过这些磁头可以访问所有磁道,并进行并行读写,主要用于大容量磁盘。

    • 移动头磁盘

      每个盘面仅有一个磁头,被装入一个磁臂中,磁头必须移动以进行寻道,只能串行读/写,致使 I/O 速度较慢,结构简单,广泛应用中、小型磁盘。

  • 磁盘访问时间

    • 寻道时间 Ts

      把磁头从当前位置移到指定磁道所经历的时间,一般为 2-30 毫秒,平均约为 10 毫秒。Ts = m * n + s。

      s ——磁盘的启动时间,大约 3ms;

      m ——每移动一条磁道所经历的时间,对一般磁盘:m=0.3ms,对高速磁盘:m <= 0.1ms;

      n ——移动的磁道数目;

    • 旋转延迟时间 Tr

      指定扇区移动到磁头下所经历的时间,平均为 50-100ms,

      Tr = 1/2 r(平均情况下,需要旋转半圈)

      r ——磁盘以秒计的旋转速度

      一个 7200(转/每分钟)的硬盘,则旋转延迟时间为 60×1000÷7200÷2=4.17 毫秒。

    • 传输时间 Tt

      数据从磁盘读出,或向磁盘写数据所经历的时间,约为零点几个毫秒,可以忽略不计。

      Tt= b / r N b ——读写的字节数

      r ——磁盘以秒计的旋转速度

      N ——一条磁道上的字节数

    访问时间 Ta = Ts + Tr + Tt = (m*n+s) + 1/2 r + b/rN

  • 磁盘调度算法

    移动磁头--磁道为哪个进程服务

    旋转磁盘--扇区为哪个进程服务

    目标--各进程对磁盘的平均访问时间(主要是平均寻道时间,即平均移动的磁道数目)最小

    先来先服务 FCFS:最简单的磁盘调度算法,根据进程请求访问磁盘的先后次序进行调度。

    最短寻道时间优先 SSTF:选择要访问的磁道与当前磁头所在的磁道距离最近的进程。

    “饥饿”现象:在 SSTF 中,若不断有新进程到来,且其访问的磁道与当前磁道的距离较近,这种进程被优先执行,而老进程一直得不到满足。

    扫描算法 SCAN: 不仅考虑访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向,又称电梯调度算法。

    循环扫描算法 CSCAN:规定磁头单向移动,即使最小磁道号与最大磁道号紧邻,形成循环。

    N 步扫描算法 N-Step-SCAN:把磁盘 I/O 请求队列分成长度为 N 的子队列,每次使用 SCAN 算法处理这 N 个请求,使用 FCFS 处理子队列。当 N 很大时,该算法的性能接近于 SCAN 算法。当 N=1 时,该算法退化为 FCFS 算法。

    双队列扫描算法 FSCAN:对 N 步扫描算法的简化,即把磁盘 I/O 请求分成两个队列,当前请求磁盘 I/O 的进程放入一个队列,新生成的磁盘 I/O 请求放入另一队列中。交替使用 SCAN 算法处理一个队列。

8.2 外存分配方法

目标:有效利用外存空间,提高文件的访问速度。

8.2.1 连续分配

为每一个文件分配一组相邻的盘块。

8.2.2 链接分配

隐式链接:在文件目录的每个目录项中含有指向链接文件第一和最后一个盘块的指针,只适用于顺序访问。

显式链接:把用于链接文件各物理块的指针,显式的存放在内存的一张链接表中,即文件分配表FAT(File Allocation Table)。

8.2.3 索引分配

单级索引分配:为每个文件分配一个索引表,把分配给该文件的盘块号,记录在该索引表中。文件目录中,填上指向该索引表的指针。

多级索引分配、混合分配方式。

8.3 空闲存储空间的管理

8.3.1 空闲表法

为外存上的所有空闲区建立一张空闲表,每个空闲区对应一个表目,包括序号、该区的起始空闲盘块号、空闲盘块数目等,按起始空闲盘块号排序。

分配:是一种连续分配方式,顺序查找空闲表,找到第一个合适的空闲区,修改空闲表。

回收:将相应块按序填回表中,并与前后合并成大块。

特点:连续存放,易产生碎片。

8.3.2 空闲链表法

  • 空闲盘块链
    • 磁盘上所有空闲存储空间,以盘块为单位链成一个链表。
    • 分配:从链首开始,依次摘下适当数目的空闲盘块进行分配。
    • 回收:依次链入链尾。
    • 特点:分配、回收简单,空闲盘块链可能很长。
  • 空闲盘区链
    • 将磁盘上所有空闲存储空间,以盘区(包括若干盘块)为单位链成一个链表。
    • 分配:查找合适大小的盘区进行分配
    • 回收:与前后盘区合并
    • 特点:分配、回收复杂,空闲盘区链较短。

8.3.3 位示图法

系统为文件存储空间建立一张位示图。位示图反映了整个存储空间的分配情况,其中每一位对应一个物理块,“1”表示对应块已被分配,“0”表示对应块为空白。

  • 盘块的分配:顺序扫描位示图,找到一个或一组为“0”的二进制位,将位号、字号转换为盘块号,进行分配:块号 = 位数 * 字号 + 位号,修改位示图,置“1”。
  • 盘块的回收:将盘块号转换为位号、字号,字号=块号 DIV 位数,位号=块号 MOD 位数,修改位示图,置“0”。

8.3.4 成组链接法

空闲盘块栈:存放当前可用的空闲盘块的盘块号,最多100个,以及空闲盘块数。栈是临界资源,为之设锁。

文件区的所有空闲盘块,被划分为若干个组。设10000个盘块,100个为一组。201-7999号盘块存放文件。

将每组的盘块数及盘块号,记入前一组的第一个盘块中。第一组的盘块数及盘块号记入空闲盘块栈,最后一组的 S.free(0)=0,作为结束标记

  • 空闲盘块的分配:
  • 空闲盘块的回收:

  • 优点:空白块号登记不占用额外空间,只借用每组的第一个空白块。当前可分配的物理块号存放在空闲盘块栈,因此绝大部分的分配和回收工作是在主存中进行,可以节省时间。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×