一、设备分配

1. 设备分配中的数据结构

在进行设备分配时，通常都需要借助于一些表格的帮助。在表格中记录了相应设备或控制器的状态及对设备或控制器进行控制所需的信息。

在进行设备分配时所需的数据结构有：

• 设备控制表

• 控制器控制表

• 通道控制表

• 系统设备表

设备控制表(DCT)

系统为每一个设备都配置了一张设备控制表，用于记录本设备的情况，如图所示。

控制器控制表、通道控制表和系统设备表

• 控制器控制表(COCT)，如图(a)所示。

• 通道控制表(CHCT)，如图(b)所示。

• 系统设备表(SDT)：记录了系统中全部设备及其驱动程序地址。

2. 设备分配时应考虑的因素

设备的固有属性、分配算法、安全性、独立性。

设备的固有属性

• 共享+虚拟：注意调度的合理性。

• 独享：排他性分配，控制不好可能死锁。

分配算法

• FIFO

• 优先权

安全性

• 安全分配(同步)：当进程发出一个I/O后，即blocked，直到其I/O完成。

  • 打破了死锁条件“请求和保持”
  • 缺点：CPU、I/O串行工作，进程进展缓慢

• 不安全分配(异步)：需进行安全性检查，进程执行效率高。

二、SPOOLing技术

通过SPOOLing技术便可将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备。

1. 什么是SPOOLing

在主机的直接控制下，实现脱机输入、输出功能。此时的外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作称为：SPOOLing (Simultaneaus Periphernal Operating On一Line)，或称为假脱机操作。

2. SPOOLing系统的组成

• 输入井和输出井

  • 在磁盘上开辟的2个大存储空间，模拟输入和输出设备。

• 输入buf和输出buf(内存中)

  • 输入缓冲区用于暂存由输入设备送来的数据，以后再传送到输入井。输出缓冲区用于暂存从输出井送来的数据，以后再传送给输出设备。

• 输入SPi和输出SPo进程

  • 两个进程来模拟脱机I/O时的外围控制机。
  • 进程SPi模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，当CPU需要输入数据时，直接从输入井读入内存。
  • 进程SPo模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井，待输出设备空闲，再将输出井的数据经过输出缓冲区送到输出设备上。

3. 共享打印机

利用SPOOLing技术，可将之改造为一台可供多个用户共享的设备，从而提高设备的利用率，同时也方便了用户。

4. SPOOLing系统的特点

• 提高了I/O的速度缓和了CPU与低速I/O设备之间速度不匹配的矛盾

• 将独占设备改造为共享设备

• 实现了虚拟设备功能SPOOLing系统实现了将独占设备变换为若干台对应的逻辑设备的功能

三、磁盘高速缓存

1. 形式

• 逻辑上是磁盘、物理上是驻留在内存中的盘块。

• 固定大小和可变大小。

2. 数据交付方式

• 数据交付指将磁盘高速缓存中的数据传送给请求者进程。

• 步骤：先查缓存、后查磁盘并更新缓存。

• 方式：

  • 数据交付
  • 指针交付

3. 置换算法

• 较常用的置换算法仍然是最近最久未使用算法LRU、最近未使用算法NRU及最少使用算法LFU等。

• 除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

  • 访问频率

  • 可预见性

  • 数据的一致性

4. 周期性回写磁盘

例：ms-dos采用写穿透方式。

四、提高磁盘 I/O 速度的其它方法

• 提前读

• 延迟写

  • 访问频率高的磁盘块放在替换队列的尾部，减少回写次数。

• 优化物理块的分布

  • 目的是减小磁头移动距离。
  • 簇分配方式：一个簇为多个连续的块。

• 虚拟盘(RAM盘)

  • 和磁盘高速缓存区别：虚拟盘由用户控制；磁盘高速缓存由系统控制。

五、磁盘性能简述

1. 数据的组织和格式

• 磁盘设备可包括一或多个物理盘片，每个磁盘片分一个或两个存储面(surface)（见图(a)）

• 每条磁道又被逻辑上划分成若干个扇区(sectors)，图(b)显示了一个磁道分成8个扇区。

扇区结构3D参数的计算

在磁盘上，块号确定计算公式：

• 块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇号。

• 柱面号=块号/(磁道号×盘扇区)。

• 磁头号=块号MOD(磁道号×盘扇区)/盘扇区。

• 扇区号=块号MOD(磁道号×盘扇区)MOD盘扇区。

注：盘扇区指的是每个盘面分成的扇区数。

扇区结构3D参数的计算

某磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。

若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：

(1)位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少？

(2)现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0？

答案

(1)位示图第15个字的第7位对应的块号=15×16(字长)+7=247，而块号247对应的：

柱面号=247/(8×4)=7(从0编号，向下取整)

磁头号=(247 MOD 32)/4=5

扇区号=247 MOD 32 MOD 4=3

(2)块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇区=56×(8×4)+6×4+3=1819

字号=1819/16=113

位号=1819 MOD 16 =11

所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。

2. 磁盘的类型

• 固定头磁盘

  • 每个磁道上有一个磁头，快。

• 移动头磁盘

  • 每个盘面仅有一个磁头，慢 。

六、磁盘访问时间

寻道时间

Ts=m*n+S(m:常量,n:磁道数,S:磁盘启动时间)。

旋转延迟Tr

• 指定扇区旋转到磁头下所需时间。

• 设每秒r转，则Tr=1/2r(均值)。

传输时间

Tt=b/Rn(b:读写字节数, N:每道上的字节数)

访问时间

Ta=Ts+Tr+Tt。

由于特定磁盘，只有集中放数据，集中读写(b大)才能更好提高传输效率。

七、磁盘调度

目标

减少寻道时间

算法分类

• 先来先服务(FCFS, First Come First Served)

• 最短服务时间优先(SSTF, Shortest Seek Time First)

• 扫描(SCAN)算法

• 循环扫描(CSCAN)算法

• NStepSCAN 和 FSCAN 调度算法

1. 先来先服务

它根据进程请求访问磁盘的先后次序进行调度。

• 优点

  • 公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。

• 缺点

  • 平均寻道时间可能较长。

例如，若有磁盘共有200个柱面，其编号为0〜199，假定磁头刚完成56号柱面的访问，磁头正在98号柱面上，现有一个请求队列在等待访问柱面，访问的柱面号分别为190,97,90,45,150,32,162,108,112,80。按“先来先服务”调度算法，请给出移动的柱面的距离。

2. 最短服务时间优先调度算法(SSTF)

“最短服务时间优先”调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行，而不管访问者到来的先后次序。

用同一个例子来讨论。

3. 电梯调度算法(SCAN)

“电梯调度”算法总是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱面的访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。

移动臂的方向

• 移动臂是向外移的。

• 移动臂是向里移的。

用同一个例子来讨论。

4. “单向扫描”调度算法

该算法不考虑等待访问者的先后次序，总是从0号柱面开始向里扫描，按照各访问者所要访问的柱面位置的次序去选择访问者。移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面。

用同一个例子来讨论。

5 NStepSCAN 和 FSCAN 调度算法

N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他队列。

FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。在扫描期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。