操作系统对磁盘的调度策略与分析

关键词：磁盘外部设备硬件程序

操作系统 (OS:Operating System) 是由一组程序组成, 能够有效地组织和管理计算机系统中的硬件和软件资源。磁盘是计算机中的重要硬件之一, 它是数据和程序存储的主要资源, 也是外部设备之一。而设备管理中重点是对使用频繁的设备, 而其它设备则是提供灵活的可扩充接口来解决, 磁盘是计算机中使用频率较高的外部设备, 对它的访问直接影响到整个系统的性能和效率, 如何有效管理、合理调度和使用磁盘对提高系统性能, 尤其是磁盘的访问速度和进程的运行速度显得尤为重要。本文介绍了磁盘调度的一些基本策略, 并对这些基本策略进行评述。

1 磁盘调度策略

在系统中有多个进程请求访问磁盘时, 应该先响应哪个请求, 这就称为磁盘调度策略。磁盘的基本存取单位是扇区, 访问磁盘实则上是对扇区进行读或写操作, 而扇区的访问需要三个参数[1]:柱面号、磁头号 (盘面号) 、扇区号来定位, 这就确定了访问盘区时要经过寻道、定扇区和读写三个操作, 即访问磁盘的时间=寻道时间+旋转延迟时间+传输时间。所谓寻道时间是指磁头从当前位置移动到指定磁道所经历的时间;旋转延迟时间:指定扇区移动到磁头下面所经历的时间;传输时间:将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间 (该时间基本上是固定的) 。而寻道是一种机械动作, 约占整个访问时间的75%[1], 因此, 磁盘调度策略以寻道优化为主要因素。磁盘调度由“寻道调度”和“旋转调度”两部分组成。

1.1 寻道调度算法

根据访问者指定的柱面位置来决定执行次序的调度, 称为“寻道调度”[2]。由于寻道时间花费较大, 所以寻道调度的目的是尽可能地减少操作中的寻道时间, 磁盘调度策略之重点也是考虑如何缩短寻道时间来提高磁盘的访问速度, 现介绍一些基本的寻道算法。

(1) 先来先服务算法FCFS (First Come First Serve) 。

先来先服务算法是按进程请求访问磁盘的先后次序进行调度。最简单的寻道算法是“先来先服务”调度算法, 这个算法实际上不考虑访问者要求访问的物理位置, 而只是考虑访问者提出访问请求的先后次序。

(2) 最短寻道时间优先算法SSTF (Shortest Seek Time First) 。

最短寻道时间优先算法是选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象, 即优先为距磁头当前所在位置最近柱面的请求服务。该算法总是从等待访问者中挑选寻道时间最短的那个请求先执行的, 而不管访问者到来的先后次序。这是为克服FCFS算法的缺点而提出的。

(3) 扫描算法 (Scan) 。

扫描算法是在磁头当前移动方向上, 选择与当前磁头所在磁道距离最近的请求作为下一次的服务, 如果沿臂的移动方向无请求访问时, 就改变臂的移动方向再选择。由于这种算法中磁头移动的规律颇似电梯的运行, 故又称电梯算法 (elevator algorithm) 。

该算法根据磁头引臂的移动方向可分为由外向内和由内向外两种。如果磁头位置不在两端, 则采取先由内向外、再由外向内的算法称为Scan (1) 算法, 如果是采取先由外向内再由内向外的算法称为Scan (2) 算法。

1.2 调度算法实例

现假设一个单磁头磁盘组共有200个柱面, 依次编号为:0～199, 当前磁头位置处于第65号柱面, 现有一访问柱面序列:107、183、48、130、18、127、65、66、77、193、140, 不同算法请求磁盘服务的次序和访问的柱面如表1。

1.3 调度算法分析

FCFS、SSTF、SCAN三种调度算法各有其可行性, 也都各有优缺点, 表2是上述请求访问柱面序列采用不同调度算法的移道总数与平均寻道长度统计。

将三种调度算法对同一请求访问序列进行调度所移动的磁道数和平均寻道长度用平滑线散点图绘制如图1。

根据不同算法的移臂寻道情况和移道总数与平均寻道长度进行分析, 得到不同调度算法的特点。

(1) FCFS调度算法的特点。

(1) 优点。

公平、实现简单。

(2) 缺点。

未对寻道进行优化。磁头引臂移动的速度是很慢的, 该算法让磁头引臂在内、外磁道之间频繁地移动, 造成较大的时间开销, 降低访问速度, 还加快机械的磨损。

这种调度算法通常可用于输入输出负载较轻的系统。

(2) SSTF调度算法的特点。

(1) 优点。

寻道性能比FCFS好。与先来先服务算法比较, 磁头引臂的机械运动明显减少, 访问时间大幅度降低, 因而缩短了为各访问者请求服务的平均时间, 也就提高了系统效率。

(2) 缺点。

缺乏公平性。先请求的不一定能得到服务。

未考虑磁头臂的移动方向。该算法总是选择离当前读写磁头最近的那个柱面, 这种选择可能导致移动臂来回改变移动方向。由于移动臂改变方向是机械动作, 速度相对较慢, 不能保证平均寻道时间最短。这就使得最小响应时间的目标和公平性之间存在冲突。

可能出现“磁道歧视”现象。假设某一时刻短磁道请求不断, 则离当前磁头较远的长磁道请求将可能长时间得不到服务 (“饥饿”) 。

(3) 扫描算法的特点。

(1) 优点

公平合理、寻道性能好、效率高、避免了“饥饿”现象[2]。

(2) 缺点。

不利于磁头反方向一端的访问请求。若在某一时间段内在磁头移动方向上不断出现访问请求, 则磁头移动反方向的请求将长时间得不到服务。

“电梯调度”算法在实现时, 不仅要记住读写磁头的当前位置, 还必须记住移动臂的当前前进方向。

1.4 寻道调度算法的改进

上述三种调度算法中, 扫描算法的实现性和实用性较强, 在该算法基础上进一步改进, 从而派生出两种优秀的算法:N步扫描 (N-Scan) 算法和循环扫描算法 (CSCAN) 。

(1) N步扫描 (N-Scan) 算法[1]。

N步扫描 (N-Scan) 算法, 磁头引臂同Scan算法一样往复运动, 所不同的是它只为一次特定的扫描开始前已经等待的访问请求服务, 在本次扫描期间内新到达的访问请求被集中在一起, 并按优化次序排列后在回程扫描期间内得到服务。

该算法在吞吐量和平均周转时间方面都具有良好的性能。

(2) 循环扫描算法 (CSCAN) 。

循环扫描算法 (CSCAN) 规定磁头单向移动 (又称单向扫描) , 自里向外 (自外向里) 移动时当磁头移到最外 (里) 磁道时, 立即又返回到最里 (外) 边的磁道, 这实际上等于将最低柱面和最高柱面看作是相邻柱面。如此循环进行扫描。该算法消除了对两端磁道请求的不公平。

除了“先来先服务”调度算法外, 其余调度算法都是根据欲访问的柱面位置来继续调度的。在调度过程中可能有新的请求访问者加入。在这些新的请求访问者加入时, 如果读写已经超过了它们所要访问的柱面位置, 则只能在以后的调度中被选择执行。

由于磁盘的所有盘片读写磁头都被固定在惟一的移动臂上同时移动, 所以常又把寻道算法称为移臂调度算法, 这是因为寻道就是通过移动臂的移动把磁头移到指定的柱面上。

1.5 旋转调度

寻道调度完成了将磁头从当前位置移动到指定磁道的操作, 而对于在同一个柱面中多个访问者的读写请求, 还需要有调度算法, 用来确定为这些访问等待者服务的次序, 若从减少输入输出操作总时间为目标出发, 显然应该优先选择延迟时间最短的请求去执行。根据延迟时间来决定执行次序的调度称为“旋转调度”。

进行旋转调度时应分析下列情况。

(1) 若干进程请求访问同一盘面上的不同扇区。

(2) 若干进程请求访问不同盘面上的不同编号的扇区。

(3) 若干进程请求访问不同盘面上的编号相同的扇区。

对于前两种情况, 旋转调度总是为首先到达读写磁头位置下的扇区进行读写操作。对于第三种情况, 由于这些扇区编号相同, 又在同一个柱面上, 所以它们同时到达读写磁头的位置下。这时旋转调度可任意选择一个读写磁头进行读写操作。

2 结语

磁盘调度策略之重点就是选择好寻道调度算法, 在基本的调度算法中, 各有利弊, 使用时需加以权衡、选择。如FCFS具有公平性, 实现简单的特点, 对于输入输出负载较轻的系统可选择, SSTF的寻道性能好, 对特殊的访问请求有较好的访问特性, 扫描算法公平合理, 寻道性能好, 效率高, 能避免“饥饿”现象, 通过改进后的N步扫描 (N-Scan) 算法和循环扫描算法 (CSCAN) 具有良好的性能。在设计操作系统的磁盘调度算法时应该根据多方因素特别是系统性能的要求来进行寻道算法的设计和选择。

摘要：磁盘是存储数据和程序的重要资源, 能够被多个用户或进程交替使用, 能够合理、快速地对存储在磁盘上的数据和程序进行访问, 不但能提高系统吞吐量, 更能提高系统的整体性能。本文介绍操作系统中几种常见的磁盘调度算法, 并对其进行评价。

关键词：FCFS,SSTF,Scan