磁盘调度算法

简介: 磁盘调度算法

磁盘的结构:

在学习磁盘调度算法之前,一定要了解磁盘的结构:

磁盘:磁盘的表面由一些磁性物质组成,可以用这些磁性物质来记录二进制数据


磁道:磁盘的盘面被划分为一个个磁道,这样的一圈就是一个磁道


扇区:一个磁道又被划分为一个个扇区,每个扇区就是一个“磁盘块”,每个扇区存放的数据量相同。因此最内侧磁道上的扇区面积最小,数据密度也最大


•每个盘面都对应一个磁头,一个盘片可能会有两个盘面(正面和背面)


•并且:所有的磁头都是连在同一个磁臂上的,因此所有磁头只能“共进退”


•所有盘面中相对位置相同的磁道组成了柱面

所以磁盘的物理地址:

可用 (柱面号,盘面号,扇区号) 来定位任意一个“磁盘块”。我们经常提到的文件数据存放在外存中的几号块,这个块号就可以转换成(柱面号,盘面号,扇区号)的地址形式。


具体地:


①根据“柱面号”移动磁臂,让磁头指向指定柱面;


②激活指定盘面对应的磁头;


③磁盘旋转的过程中,指定的扇区会从磁头下面划过,这样就完成了对指定扇区的读/写。


如何在磁盘中读/写数据:

磁盘由中间的马达带动旋转,磁头会由磁头臂带动,在红色箭头方向移动

磁头在磁道的最外层,如果要读取橙色磁道,那么磁头臂带动磁头,移动到橙色磁道,接着移动扇区,让目标扇区从磁头下面划过,就能完成对扇区的读/写操作。

磁盘的分类:

根据磁头是否能移动,可以将磁盘分为活动磁盘和固定头磁盘

磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道

磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头,每个磁道都有对应的磁头,所以读取某一个磁道的数据的时候,只需要激活与其对应的磁头就可以了。

根据盘片是否能更换,可以将磁盘分为可更换磁盘和固定盘磁盘

磁盘调度:

一次磁盘读/写操作需要的时间:
寻道时间:

确定需要读取的数据存放到哪个磁道上之后,需要将磁头移动到相应的磁道上,这里的移动时间也称为寻找时间(寻道时间) Ts: 在读/写数据前,将磁头移动到指定磁道所花的时间。


①启动磁头臂是需要时间的。假设耗时为 s;


②移动磁头也是需要时间的。假设磁头匀速移动,每跨越一个磁道耗时为 m,总共需要跨越n 条磁道。则:寻道时间 T= s + m*n


注:


现在的硬盘移动一个磁道大约需要0.2ms,磁臂启动时间约为2ms


延迟时间:

延迟时间是通过旋转磁盘,使磁头定位到目标扇区所需要的时间。设磁盘转速为r (单位:转/秒,或转/分),则平均所需的延迟时间 T =(1/2)*(1/r)= 1/2r


注:1/r 就是转一圈需要的时间。找到目标扇区平均需要转半圈,因此再乘以 1/2

注:硬盘的典型转速为5400 转/分,或 7200转/分

传输时间:

传输时间是 从磁盘读出或向磁盘写入数据所经历的时间,假设磁盘转速为r,此次读/写的字节数为h,每个磁道上的字节数为N。则:


传输时间= (1/r)* (b/N) = b/(rN)


注:每个磁道要可存 N 字节的数据,因此 b 字节的数据需要 b/N 个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间 1/r


总的平均存取时间:=Ts+1/2r+b/(rN)


延迟时间和传输时间都与磁盘转速相关,且为线性相关。而转速是硬件的固有属性,因此操作系统也无法优化延迟时间和传输时间。所以操作系统能影响的只有寻道时间,根据不同的磁盘调度算法影响寻道时间。


对于磁盘调度的题型可以看看:


1.假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为15us,由缓冲区送至用户区的时间是5us,在用户区内系统对每块数据的处理时间为1us,若用户需要将大小为10个磁盘块的Doc1文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间为 ( )us;采用双缓冲区需要花费的时间为 ()us。


A.150        B.151        C.156        D.201  


A.150        B.151        C.156        D.201  


解答:


注:用户的处理过程,与用户的输入,传送过程是分开的,也就是说当数据在输入,传送的过程中,工作区可以处理前一个数据。两者互不影响,就像流水线一样,采用流水线的算法,这里有2段


①使用缓冲区:15+5


②处理:1us


单缓冲区:

(15+5+1)+20(输入+传送时间]=最长段)*(10-1)=201us

双缓冲区: 两个缓冲区是提供两种选择,不能同时向缓冲区1和缓冲区2输入数据。但是我们可以同一时刻对缓冲区1进行输入,对缓冲区2进行输出,形成两个并行的通路。这里分为了三段:

①使用缓冲区1:15us

②使用缓冲区2:15us

③处理:1us

(15+5+1)+15(最长段)*(10-1)=156us

答案:D,C

2.假设某磁盘的每个磁道划分成11个物理块,每块存放1个逻辑记录。逻辑记录R0,R1,...R9,R10存放在同一个磁道上,记录的存放顺序如下表所示:

如果磁盘的旋转周期为33ms,磁头当前处在R0的开始处。若系统使用单缓冲区顺序处理这些记录,每个记录处理时间为3ms,则处理这11个记录的最长时间为(),若对信息存储进行优化分布后,处理11个记录的最少时间为()。


A.33ms        B.336ms        C.366ms        D.376ms


A.33ms        B.66ms        C.86ms        D.93ms

对于R0:读3ms+处理3ms,当处理完R0之后,磁头已经到达了R1位置,要想继续处理R1,磁头必须旋转一圈,到R1的开头,也就是10个物理块(30us)


R1:30us(延迟旋转时间)+3us(读)+3us(处理)=36us


R2:30us+3us+3us


我们可以发现除了R0之外,其他的处理时间均是36us,则这11个记录的最长时间为


36*10+6=366ms


若对信息存储进行优化分布:这里处理完之后,刚好转了2圈,1圈的时间=33ms,所以总时间为


33*2=66ms

磁盘调度算法:

假定当前磁头位于100号磁道,进程对磁道的请求序列依次为55,58,39,18,90,160,150,38,180。当采用先来先服务和最短寻道时间优先算法时,总的移动的磁道数分别是多少? (请给出寻道次序和每步移动磁道数)


先来先服务顺序为:

100 -> 55 -> 58 -> 39 -> 18 -> 90 -> 160 -> 150 -> 38 -> 180

将相邻磁道的距离加和起来就是最后的总移动磁道数

可以看到先来先服务算法(FCFS)的磁盘调度非常简单,但是其忽略了寻道时间,可能导致较长的平均寻道时间,同时也可能产生饥饿问题(就是一个或多个进程,请求由于无法得到所需的资源或服务,而长时间等待无法被处理)


最短寻道顺序为:

谁离当前所在磁道最近,就移动到哪一个磁道中,所以顺序为


100->90->58->55->39->38->18->150->160->180


最短寻道算法(SSTF)是优先选择离磁头位置最近的磁道进行访问,可以减少平均寻道时间,然而,如果请求分布不均匀,并且出现了一组连续的请求,这些请求的磁道位置非常接近,那么其他远离这个区域的请求可能会等待较长时间,产生类似于饥饿的效果。


电梯寻道顺序:

总的顺序为:18->38->39->55->58->90->100->150->160->180


从小到大:100->150->160->180->90->58->55->39->38->18

从大到小:100->90->58->55->39->38->18->150->160->180

电梯寻道算法(SCAN)的处理过程可以概括为:


磁头从某一端开始向另一端移动,途中遇到的请求被依次处理,直到到达最远的请求所在的位置,然后改变方向继续处理另一侧的请求。


这种算法使得磁盘请求的等待时间相比于最短寻道算法均衡,能够有效避免饥饿现象,并且能够快速响应新的请求。


但是,如果有连续的请求集中在磁头移动方向的最远端,可能会导致部分请求的等待时间增长。


循环电梯算法顺序:

总的顺序为:18->38->39->55->58->90->100->150->160->180

从小到大:

从大到小:

循环电梯算法(C-SCAN)的处理过程可以概括为:


C-SCAN算法将磁道分为两个方向上的两个区域:从最小磁道到最大磁道为一个方向,而从最大磁道到最小磁道为另一个方向。当磁头向一个方向移动并处理请求时,它会一直处理直到达到最远的请求所在的位置。然后,磁头会立即返回到最近的请求处(即最小磁道或最大磁道,具体取决于实现),重新开始处理新的请求。


该算法对于连续请求较为集中的情况有较好的性能,但是会导致中间位置的磁道请求长时间被忽略,这可能会对一些请求的响应时间产生较大影响。

目录
相关文章
|
17天前
|
算法 调度
深入理解操作系统之进程调度算法的设计与实现
【5月更文挑战第27天】 在多任务处理的现代操作系统中,进程调度算法是核心组件之一,负责决定哪个进程将获得CPU资源。本文不仅探讨了几种经典的进程调度算法,包括先来先服务(FCFS)、短作业优先(SJF)和轮转调度(RR),还分析了各自的优势、劣势及适用场景。此外,文章将深入讨论如何根据系统需求设计自定义调度算法,并提供了基于伪代码的实现示例。最后,通过模拟实验比较了这些算法的性能,以指导读者在实际操作系统设计时的选择与优化。
|
2天前
|
算法 调度 决策智能
基于自适应遗传算法的车间调度matlab仿真,可以任意调整工件数和机器数,输出甘特图
这是一个使用MATLAB2022a实现的自适应遗传算法解决车间调度问题的程序,能调整工件数和机器数,输出甘特图和适应度收敛曲线。程序通过编码初始化、适应度函数、遗传操作(选择、交叉、变异)及自适应机制进行优化,目标如最小化完工时间。算法在迭代过程中动态调整参数,以提升搜索效率和全局优化。
|
8天前
|
消息中间件 算法 Java
抖音面试:说说延迟任务的调度算法?
Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。 ## 1.延迟任务实现 在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码: ```java public class DelayTaskExample { public static void main(String[] args) { System.ou
20 5
抖音面试:说说延迟任务的调度算法?
|
20天前
|
算法 调度 UED
【操作系统】调度算法的评价指标和三种调度算法
【操作系统】调度算法的评价指标和三种调度算法
29 2
|
29天前
|
算法 调度 UED
作业调度算法(含详细计算过程)和进程调度算法浅析
作业调度算法(含详细计算过程)和进程调度算法浅析
135 1
作业调度算法(含详细计算过程)和进程调度算法浅析
|
29天前
|
算法 调度
考虑需求响应的微网优化调度模型【粒子群算法】【matlab】
考虑需求响应的微网优化调度模型【粒子群算法】【matlab】
|
29天前
|
算法 调度
【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究
【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究
|
29天前
|
算法 Serverless 调度
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
基于分布式ADMM算法的考虑碳排放交易的电力系统优化调度研究(matlab代码)
|
29天前
|
算法 调度
基于CCG算法的IEEE33配电网两阶段鲁棒优化调度matlab
基于CCG算法的IEEE33配电网两阶段鲁棒优化调度matlab
|
1天前
|
算法 安全
基于龙格库塔算法的SIR病毒扩散预测matlab仿真
该程序使用龙格库塔算法实现SIR模型预测病毒扩散,输出易感、感染和康复人群曲线。在MATLAB2022a中运行显示预测结果。核心代码设置时间区间、参数,并定义微分方程组,通过Runge-Kutta方法求解。SIR模型描述三类人群动态变化,常微分方程组刻画相互转化。模型用于预测疫情趋势,支持公共卫生决策,但也存在局限性,如忽略空间结构和人口异质性。