实时磁盘调度

2024-10-09

实时磁盘调度（通用3篇）

实时磁盘调度篇1

0 引言

随着数字多媒体技术的发展和普及,需要大量的多媒体服务器来支持实时多媒体流。一个实时多媒体流的编码比特率可以是固定的,也可以是可变的,如当今流行的视频点播、新闻点播等。为了避免内容传送的中断,即抖动,实时多媒体流磁盘请求必须在其截止时间前完成。一个多媒体服务器还将为如文字、图像等离散数据提供服务,这种离散数据没有实时性要求,称为非实时性磁盘请求。因此对于多媒体服务器来说,必须提出一个合理的实时磁盘调度策略,一方面要保证实时请求对于实时性的要求,另一方面也要为非实时磁盘请求提供合理的响应时间。

SCAN[1] 算法选择与当前磁头距离最短并且与磁头移动方向一致的任务作为下一个调度对象,已经被证明在减小磁盘寻道时间上是最优磁盘调度策略。但由于没有考虑实时磁盘请求,SCAN导致过多的截止时间被错过,不适合于实时多媒体服务器的磁盘调度算法。

EDF(Earliest Deadline First)[1]算法是一种基于任务截止时间的实时调度算法,在任务队列中具有最小截止时间的实时任务首先得到服务。这种算法能较好地满足任务的实时性,但它只考虑任务的截止时间因素而忽略了磁盘寻道时间,极大影响了系统的吞吐量。

许多实时磁盘调度算法如SCAN-EDF[1],SCAN-RT[2],DM-SCAN[3]都对SCAN算法进行改进,使其能够将实时性考虑在内。这些算法首先以EDF顺序来调度任务,对于截止时间相同的任务,如果不会引起错过其截止时间,则用SCAN算法来调度。最坏情况下,所有这些基于优先权的算法都将退化为EDF算法,并导致过多的磁盘寻道开销。由于这些算法都没有提供接纳控制来拒绝那些会错过其截止时刻的任务。结果导致不能保证处于服务中的流的质量。

由于多媒体服务器磁盘负载还包含了非实时任务请求,实时磁盘调度算法还必须让非时任务也具有合理的响应时间。一般的做法是每个磁盘周期都为非实时任务保留固定的权值。GSS(Group Sweeping Scheduling)[4]采用了分组策略的两级调度策略,对实时任务预留带宽。为了保证已经被接受的多媒体流的服务质量,QoS-Disk[5]引入了接纳控制机制来决定是否接受一个新到达的多媒体流。WRR-SCAN (Weighted-Round-Robin-SCAN)[6]算法对非实时任务采用固定预留带宽的方式。但是,当磁盘发生过载,或者实时任务和非实时任务请求比例突发变化时,磁盘性能将严重下降。

为此,提出了动态带宽分配扫描DBA-SCAN (Dynamic-Bandwidth-Assignment-SCAN ) 算法。该算法对非实时任务采用固定预留带宽的方式,并能够根据磁盘请求的负载变化动态调整磁盘带宽的分配比例,利用接纳控制拒绝一个不能在其截止时间前完成的请求,动态回收未用带宽来提高磁盘利用率。

1 DBA-SCAN磁盘调度框架

DBA-SCAN磁盘调度框架包括以下部分:质量协调部分,带宽预留计算部分,质量监测机制,接纳控制机制和动态带宽回收机制组成。一个磁盘作业由一个实时的连续多媒体任务或非周期任务发起。实时的连续多媒体任务是有时间限制,非周期任务没有时间限制,即非实时任务。实时磁盘调度策略不仅要考虑实时实时多媒体流请求,还要处理诸如图片、文字等离散的非实时磁盘请求。DBA-SCAN的总体运行框架如图1所示。

DBA-SCAN采用带宽预留机制,将可用的磁盘带宽预留给每个任务,预留的带宽是每个磁盘调度周期中,一个任务数据传送所需要的带宽,即一个磁盘调度周期中为其服务时的数据传输的最大时间。非实时任务则排成队列,由一个虚拟服务器服务,这个虚拟服务器也被预留了带宽。接纳控制决定是否接纳一个任务。质量协调器提供了自适应质量保证。核心调度器从每个队列中提取一轮作业,并将其排序成SCAN调度队列,同时完成动态回收未用带宽。实时任务分成保证性任务和可选性任务。保证性任务的请求必须要满足,可选性任务时在满足保证性任务后去满足的。

2 磁盘模型与任务模型

DBA-SCAN每次读或者写的最小单位为块,c表示块大小(单位:比特),V表示磁盘传输速率。磁头寻道时间为tseek(d) =a×d+tstart,其中,d表示磁头从一个磁道移动到另一个磁道所走过的磁道数,a是常数,表示磁头移动相邻两个磁道的时间,tstart为磁头启动时间。

实时磁盘调度策略的磁盘请求包括了周期性的实时请求和非周期到达的非实时请求。对于非实时请求来说,将其看成一个任务,由虚拟服务器来服务,每个磁盘调度周期都为其保留了一定的带宽。对于实时请求来说,每个磁盘调度周期都为每个实时请求预留固定的带宽。

实时请求 Ti可表示为 (Ai, Bi, Di),Ai表示到达时间,Bi表示请求磁盘块数,Di 表示截止时间。非实时请求Pi可表示为 (Ai, Bi)。

DBA-SCAN首先将磁盘带宽分成磁盘周期,磁盘周期划分如图2所示。

3 实时磁盘调度策略

一个磁盘周期的时间被分解为3个部分:磁盘寻道,磁盘旋转,磁盘数据传送。DBA-SCAN为每个任务分配一个权值来指示该任务在一个磁盘周期中所占有的最大传输时间。服务器在每个调度周期内轮流为每个任务服务。令L表示每个磁盘调度周期的时间,ts表示每个磁盘周期磁头寻道时间,tr 表示每个磁盘周期磁盘旋转时间,Wi表示实时任务Ti的权值,Wrt为所有实时任务权值之和,Wp表示非实时任务的权值,于是

对于非实时任务的权值Wp不是固定的,DBA-SCAN将利用负载监测机制来动态调整Wp的值。由于每个实时请求都带有固定的权值,通过调整权值,就能相应地控制QoS。

①权值的计算

对于实时任务Ti每个磁盘调度周期必须传输bi块数,Ti的权值是:

对于非实时任务每个磁盘调度周期保留磁盘块数ba,权值是:

没有非实时性任务时,DBA-SCAN将满足每个实时任务的截止时间。建立一个虚拟非实时服务器来为非实时任务服务。为其分配权值,为在每轮中保证其权值,为非实时任务提供小量数据传输率,以避免发生饥饿现象。非实时任务的权值越大,其作业的响应时间越短。

②接纳控制

DBA-SCAN提供了自适应质量保证,每个保证任务每一磁盘周期分配一个固定权值。剩余任务为可选任务。DBA-SCAN只有当其保证任务有足够带宽时才接纳可选任务。

当一个实时任务到达,利用公式 (1) 决定是否接纳该任务。对于tr 计算主要依赖文件系统如何组织数据块。当数据块在磁盘上随机存放时,一个磁盘周期所扫描的数据块可能不在同一个磁道上。每个磁盘周期传输的总数据块为:

其中,n为实时任务个数。最坏情况下所有数据块在不同磁道上,于是有:

其中,ta为磁盘旋转一圈与磁头启动之和。于是有:

为了完全利用带宽DBA-SCAN在磁盘周期前带宽分配,在磁盘周期后动态回收未用的带宽。前者通过每个调度周期尽可能调度更多的任务来降低磁盘开销,后者通过提前下一个磁盘周期的开始时间来动态回收未用带宽。

③负载监测机制

DBA-SCAN保证处于服务中的实时任务的质量。考虑最差情况下计算实时任务权值。然而,这些考虑也导致过多的磁盘调度时间保留,引起磁盘利用率的下降。

DBA-SCAN负载监测的方法是利用一个滑动窗口监测多媒体服务器磁盘负载的变化。自适应带宽分配调整的周期为滑动窗口大小ws。每隔ws时间进行一次带宽分配调整。监测的参数包括:实时请求的数目,非实时请求的数目,磁盘利用率。磁盘利用率定义为所有实时任务权值之和Wrt和非实时任务权值wp 与L的比值。多媒体服务器磁盘负载主要是实时多媒体请求,如果监测到实时请求和非实时请求变化较大,能够及时调整实时请求和非实时请求带宽分配。

为完全利用带宽,DBA-SCAN加入了动态调度策略,包括了磁盘周期前带宽分配和磁盘周期后带宽回收。前者通过每个磁盘周期尽可能调度更多的任务来降低磁盘开销,后者通过提前下一个磁盘周期的开始时间来动态回收未用带宽。

④带宽分配比例调整

磁盘工作是存在欠载和过载两种情况,需要针对不同情况来考虑如何调整带宽分配。

第一种,欠载情况。

欠载情况发生在为非实时任务保留带宽时,实时任务带宽是过载的,而实际磁盘是欠载的,即有剩余的磁盘带宽,还有实时请求得不到服务,降低了磁盘利用率。因此,DBA-SCAN利用监测参数来调整实时任务和非实时任务带宽的比例。此时,减小为非实时任务保留的带宽,尽量优先满足实时请求,因为非实时任务是欠载的。

由于权值W是按质量保证大小所预留的,因此实际应用中,一个流整个回放过程中,处于峰值的回放时间很短,又因为多个流的峰值出现在同一时间段内的概率较小。因此,当Wa调整为较小的值时,还有很大的概率利用动态回收的带宽来为非实时任务服务。DBA-SCAN对于Wa动态调整对非实时任务平均响应时间的影响不大。

第二种,过载情况。

采用磁盘利用率可以很好地表示各类应用请求所需的带宽,但是在过负的情况下,由于磁盘是饱和的,它的利用率是100%,因此不能反映出各类应用请求所需的带宽。在短暂过载的情况下,通常到达率高的请求应该分配高比例带宽。但是在过载的情况下,已经没有足够的带宽来满足实际请求的需要。在这种情况下,带宽调整主要任务是在服务器过载时反映出实时请求和非实时请求对带宽要求的相对差异,估计每类应用请求所需要的带宽。

所有实时任务权值之和为:

非实时任务分配的权值为:

其中,W’rt和W’p分别为监测到得实时任务和非实时任务实际需求带宽。

4 实验结果

模拟仿真实验的目的是研究新提出的DBA-SCAN算法的性能,为了对比,选用WRR-SCAN算法。固定任务总数,通过调整实时任务的百分比表示实时请求到达的频繁程度。而服务时间和磁道号随机生成。参考文献[6]设置模拟实验参数如表1所示。

图3显示不同实时任务请求率向对实时任务错过截止时间率的影响。DBA-SCAN调度算法性能要优于WRR-SCAN,主要原因是该算法利用接纳控制和动态回收未用带宽来提高它们的运行质量。一个在其截止时间以后完成的磁盘请求不仅降低了流的质量也浪费了宝贵的磁盘带宽。当服务器超载时,接受还是拒绝一个磁盘请求对于处于服务中的实时流以及非实时请求的服务质量都有很大影响。DBA-SCAN拒绝一个不能在其截止时间前完成的请求。这种接纳控制在处理频繁到达的实时流时是高效的。

5 结束语

一个实时磁盘调度算法对于多媒体服务器的性能来说是非常关键的因素。本文中提出了一个新的实时磁盘调度策略DBA-SCAN。与传统的磁盘调度算法以尽力的方式服务不同,DBA-SCAN为所有处于服务中的流提供质量保证,并限定了非实时作业的响应时间。

DBA-SCAN将磁盘服务时间分成轮次,并对服务请求一SCAN顺序进行服务。DBA-SCAN通过将一个磁盘作业分成保证作业和可选作业来提供质量保证。非实时任务和实时任务在每轮调度时都被分配一个固定的权值。为了使带宽浪费最小化,DBA-SCAN引入了积极的带宽回收策略来在运行中动态回收未用带宽。回收的带宽将被用于为可选任务提供更好的质量以及减小非实时请求的响应时间。另外,通过自适应质量保证,WRR-SCAN能够灵活的对服务中的流进行质量与数量的权衡。

通过模拟程序来对比DBA-SCAN与WRR-SCAN调度算法,通过实验结果可以看出, DBA-SCAN的性能明显好于WRR-SCAN算法,而非实时请求的响应时间也能得到一定的控制。

摘要：多媒体服务器需要一个实时磁盘调度算法为具有软实时要求的连续多媒体流服务。传统的磁盘调度算法不适应实时多媒体流。提出一个新的实时磁盘调度DBA-SCAN(Dynamic-Band-width-Assignment-SCAN)算法。DBA-SCAN算法通过带宽预留和接纳控制机制为处于服务中多媒体流提供质量保证。对于非实时任务也预留了带宽以保证非实时任务具有合理的响应时间。DBA-SCAN采用一种积极策略在运行时动态回收未用的带宽。被回收的带宽被用于为可选任务或者更多的非实时任务服务。通过模拟实验对DBA-SCAN算法和WRR-SCAN算法进行对比,实验结果显示,DBA-SCAN为实时多媒体流提供了更好的质量。

关键词：实时磁盘调度,接纳控制,动态带宽分配,负载监测,SCAN

参考文献

[1]Walid G Lbrahim Kamel,Shahram Ghandeharizadeh.Disk schedu-ling in video editing systems[J].IEEE Transactions on Knowledgeand Data Engineering,2001,13(6):933-950.

[2]Kanhere S S,Sethu H,Parekh A B.Fair and efficient packetscheduling using elastic round robin[J].IEEE Transactions on Par-allel and Distributed Systems,2002,13(3):324-336.

[3]Reddy A L N,Wyllie J,Wijayaratne K B R.Disk scheduling in amultimedia I/O system[J].ACMTransactions on Multimedia Com-puting,Communications and Applications,2005,1(1):37-59.

[4]Ketil Lund,Vera Goebel.Adaptive disk scheduling in a multimediaDBMS[C].Proceedings of the eleventh ACM international confer-ence on Multimedia,2003:65-74.

[5] Myung-Sub Lee, Kwang-Jung Kim, Chang-Hyeon Park. Real-time disk scheduling algorithms based on the two-way SCAN technique[C]. Proceedings of the 2009 International Conference on Scalable Computing and Communications; Eighth International Conference on Embedded Computing, 2009:137-142.

[6]Cheng-Han Tsai,Tai-Yi Huang.An efficient real-time disk-schedu-ling framework with adaptive quality guarantee[J].IEEE Transac-tions on Computers,2008,57(5):634-647.

实时磁盘调度篇2

磁盘调度实践报告

姓名：董宇超班级：计算机一班学号：0906010124

 实践内容  实践目的及意义  功能设计及数据结构  调试运行及测设分析  存在的问题及改进设想  实践体会  总结  参考文献

正文：

1.实践内容：

 假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。 磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。为此设置“驱动调度”进程。

 由于磁盘与处理器是并行工作的，所以当磁盘在为一个进程服务时，占有处理器的其它进程可以提出使用磁盘（这里我们只要求访问磁道），即动态申请访问磁道，为此设置“接受请求”进程。

要求模拟电梯调度算法，对磁盘进行移臂操作，编程实现。

2.实践目的：

磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出工作，在现代计算机系统中往往同时会有若干个要求访问磁盘的输入输出要求。

系统可采用一种策略，尽可能按最佳次序执行访问磁盘的请求。由于磁盘访问时间主要受寻道时间T的影响，为此需要采用合适的寻道算法，以降低寻道时间。

本实验要求模拟设计一个磁盘调度程序，观察调度程序的动态运行过程。通过实验理解和掌握磁盘调度的职能。

3.功能设计：

由于程序简单，没有设计结构体，只定义了一下变量：

int m=0;//记录磁道数目

int n;//接受输入的磁道号

int disk[1000];//保存磁道序列

int currenttrack;//当前磁道号

int t;

int i=0,j=0,k=0;//循环参数

int option;//记录寻到方向

int sum=0;//统计寻道长度

源代码: #include void main(){ int m=0;//记录磁道数目

int n;//接受输入的磁道号

int disk[1000];//保存磁道序列

int currenttrack;//当前磁道号

int t;int i=0,j=0,k=0;//循环参数

int option;//记录寻到方向

int sum=0;//统计寻道长度

printf(“请输入当前的磁道号:”);scanf(“%d”,¤ttrack);

printf(“n--------------------1.向磁道号增加的方向访问--------------------”);printf(“n--------------------2.向磁道号减少的方向访问--------------------”);printf(“n请选择的当前磁头移动方向(1/2):”);scanf(“%d”,&option);

printf(“n请输入磁道请求序列(0~999并以<-1>结束):n”);scanf(“%d”,&n);while(n!=-1){

disk[i]=n;

m++;i++;

scanf(“%d”,&n);}

/* 冒泡排序使磁道请求序列从小到大排序 */ for(j=0;j

for(i=0;i

{

if(disk[i]>disk[i+1])

{

t=disk[i];

disk[i]=disk[i+1];

disk[i+1]=t;

}

} }

/* 找到当前磁道号在磁道请求序列中的排序位置 */

k=0;for(i=0;i

k++;else

break;} printf(“n--------------电梯算法调度后的磁盘调度序列-------------n”);/* 第一种: 当前磁道号先向外再向里读 */ if(option==1){ for(i=k;i

printf(“%5d”,disk[i]);} for(i=k-1;i>=0;i--){

printf(“%5d”,disk[i]);} sum=2*(disk[m-1]-disk[k])+disk[k]-disk[0];printf(“n寻道长度为：%5d”,sum);} /* 第二种: 当前磁道号先向里再向外读 */ if(option==2){

for(i=k-1;i>=0;i--){

printf(“%d ”,disk[i]);

sum+=disk[i];}

for(i=k;i

printf(“%5d”,disk[i]);

sum+=disk[i];} sum=disk[m-1]-disk[k]+2*(disk[k]-disk[0]);printf(“n寻道长度为：%5d”,sum);

} printf(“n”);}

4.调试运行：

运行开始后出现如下界面，举例输入5：

然后出现：

1.先选择1（按按磁道号增加的方向寻道）：

接着输入磁道序列，若要结束输入，输入-1即可：

然后出现如下寻道结果：

2.再选择2（按按磁道号减少的方向寻道）：

接着输入磁道序列，若要结束输入，输入-1即可：

然后出现如下寻道结果：

5.存在的问题：

由于初次做操作系统模拟实验，所以程序设计中存在很多问题，例如：由于电梯算法是从当前的磁道号开始沿着预定的方向寻道，当本方向上的请求全部满足时，再反向寻道，但是程序模拟过程中，进程不能随着寻道的同时添加新的进程，使得电梯调度算法不能更好的体现。只能预先输入一串请求，然后只对这一段请求寻道。

改进之处：添加更高级的算法，使得请求能在寻道的同时加进来。

还有一些简单的已解决的问题，不一一列举了。

6.实践心得体会：

通过这次实践学会了不少内容，更深的理解了磁道调度的几种算法，而且学会了系统的编写程序。在编程过程中，需要查阅各种资料，并且学习前人的编写方法，找出优劣，然后形成自己的思想，最终完成程序的编写。

通过模拟磁盘调度的电梯调度算法，并比较与其他调度算法的不同，懂得了各种算法在不同情况下的作用。选择一个好的调度算法可以节约很多时间。

在模拟过程中出现过好多问题，有的解决了，有的还未解决，不管如何都是一种收获。

在最初的时候，由于程序编写隐藏的错误，编译没有发现，却执行不下去，然后改正错误，修复漏洞，最终满足实验要求。

7.总结：

为期一周的操作系统实践课结束了，编写了电梯调度算法的磁盘调度模拟程序。电梯调度寻道方式就像电梯运行一样，就是沿一个方向寻道，直到满足这一方向的所有请求，便反向寻道。在程序中添加了寻道长度的显示，以便将电梯调度的效率与其他磁盘调度算法比较。

8.参考文献：

1.操作系统教程（第4版）„„„„孙钟秀主编高等教育出版社；

实时磁盘调度篇3

硬盘作为一种磁表面存储器, 是在非磁性的合金材料表面涂上一层很薄的磁性材料, 通过磁层的磁化来存储信息。硬盘主要由磁盘和磁头及控制电路组成, 信息存储在磁盘上, 磁头负责读出或写入。硬盘一开机, 其磁盘就开始高速旋转。磁关可以采用轻质薄膜部件, 盘片在高转下产生的气生的气流浮力迫使磁头离开盘面悬浮在盘片上方, 浮力与磁头座架弹簧的反向弹力使得磁头保持平衡。这样的非接触式磁头可以有效地减小磨损和由摩擦产生的热量及阻力。同时, 磁盘是典型的直接存取设备, 允许文件系统直接存取磁盘上的任意物理块。磁盘机是由若干张盘片构成, 每张盘片上都涂有磁层, 用于记录信息, 各盘片的圆心固定在一个旋转轴上, 每个盘面 (除磁盘组最上面和最下面的伺服面外) 对应一个磁头, 磁头固定在移动臂上, 移动臂沿半径方向移动可将磁头从当前位置移动到指定磁道, 旋转轴的转动带动磁盘旋转可将扇区移动到磁头下, 这样便可在指定扇区读或写数据。

2 磁盘调度算法分析

现有的磁盘调度算法大致上可以分为两大类:传统调度算法和实时调度算法。传统磁盘调度算法的目标是提高磁盘的有效I/O速率, 而忽略单个请求的响应时间。实时调度算法的首要目标是保证每个I/O请求对服务时限的要求, 并在此前提下尽量提高磁盘I/O带宽的利用效率。下面将对现有的磁盘调度算法进行详细的分析。

2.1 传统磁盘调度算法

FCFS是最简单的磁盘调度算法, 它与请求队列的长度、请求到达的频率和相邻请求之间的位置毫无关系。在载荷较轻松的环境下, FCFS的性能尚可接受, 但在载荷较重的情况下, FCFS的性能就会严重下降, 甚至恶化。人们之所以研究FCFS算法, 是因为:a.任何调度算法在请求队列长度为1, 请求速率极低或相邻请求的间隔为无穷大时退化为FCFS算法;b.FCFS算法是衡量其它调度算法性能的基准。FCFS算法可描述为:Loop{Schedule the oldest request from

SSTF算法选择下一个服务对象的原则是最短寻道时间。由于计算准确的寻道时间并不容易, 加之寻道时间随寻道距离的增加而单调递增, 因此SSTF有时也被称之为最短寻道距离优先 (SSDF) 算法。这样请求队列中距当前磁头所在磁道最近的请求就是下一个服务对象。在重载荷的情况下, SSTF的平均响应时间较短, 但响应时间的方差较大。

2.1.3 SCAN算法

SCAN算法平等地看待请求队列中的每一个请求, 它让磁头在最内圈和最外圈磁道之间连续往返移动, 并在移动过程中响应处在寻道方向上的请求。SCAN算法的平均响应时间比SSTF算法长, 但响应时间方差比SSTF要小。SCAN算法的一种变化为CSCAN, 与SCAN算法的区别在于单向服务请求, 即磁头从最内移动到最外圈的过程中与SCAN算法一样服务请求队列中的请求, 但当磁头到达最外圈后, 执行一次全过程寻道操作、将磁头迅速移动到最内圈, 然后开始新一轮的服务。

2.1.4 LOOK算法

LOOK算法是SCAN算法的一种改进。对LOOK算法而言, 磁头同样在最内圈和最外圈磁道之间往返移动。但LOOK算法发现所移动的方向上不再有请求时立即改变移动方向, 而SCAN算法则需移动到最外圈或最内圈时才改变移动方向。同SCAN算法一样, LOOK算法的一种变化称为CLOOK, 它将LOOK算法中的双向服务移动改成单向服务移动。

SATF算法与SSTF算法的思想类似, 唯一的区别是SATF算法将SSTF算法中的寻道时间改成了访问时间。这是因为磁盘技术发展到今天, 寻道时间已经有了很大的改进, 但旋转等待时间却无多大改善。SATF考虑到了旋转等待时间的影响。

2.2 实时调度算法

与FCFS调度算法类似, EDF算法是多媒体实时调度算法中最简单的调度算法。它响应请求队列中时限最早的请求, 是其它算法性能衡量的基准和特例。

SCAN-EDF是SCAN算法和EDF算法相结合的产物。它以EDF的方式选择请求队列中谁是下一个服务对象, 而对于具有相同时限的请求, 则按SCAN算法服务每一个请求。

FD-SCAN算法首先从请求队列中找出时限最早、从当前位置开始移动又可满足其时限要求的请求, 作为下一次SCAN的方向。并在磁头向该请求移动的过程中响应处在寻道路径上的请求。这种算法忽略了用SCAN算法响应其它请求的开销, 因而并不能确保服务对象时限最终得到满足。

LMD算法是第一个明确对服务超时限数作为优化对象的实时调度算法。该算法可描述为:

Insert the new request at position I of queue calculate the

number

of missed deadlines when servicing all the request in order in

put the new request at the position which produce least

除了上述所描述的一些实时调度算法外, 还有P-SCAN (Priority

Only) 等等。