磁盘调度算法

简介: 磁盘调度算法

磁盘的结构:

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

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


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


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


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


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


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

所以磁盘的物理地址:

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


具体地:


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


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


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


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

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

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

磁盘的分类:

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

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

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

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

磁盘调度:

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

确定需要读取的数据存放到哪个磁道上之后,需要将磁头移动到相应的磁道上,这里的移动时间也称为寻找时间(寻道时间) 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算法将磁道分为两个方向上的两个区域:从最小磁道到最大磁道为一个方向,而从最大磁道到最小磁道为另一个方向。当磁头向一个方向移动并处理请求时,它会一直处理直到达到最远的请求所在的位置。然后,磁头会立即返回到最近的请求处(即最小磁道或最大磁道,具体取决于实现),重新开始处理新的请求。


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

目录
相关文章
|
9天前
|
DataWorks 算法 调度
B端算法实践问题之配置脚本以支持blink批处理作业的调度如何解决
B端算法实践问题之配置脚本以支持blink批处理作业的调度如何解决
20 1
|
27天前
|
存储 算法 调度
基于和声搜索算法(Harmony Search,HS)的机器设备工作最优调度方案求解matlab仿真
通过和声搜索算法(HS)实现多机器并行工作调度,以最小化任务完成时间。在MATLAB2022a环境下,不仅输出了工作调度甘特图,还展示了算法适应度值的收敛曲线。HS算法模拟音乐家即兴创作过程,随机生成初始解(和声库),并通过选择、微调生成新解,不断迭代直至获得最优调度方案。参数包括和声库大小、记忆考虑率、音调微调率及带宽。编码策略将任务与设备分配映射为和声,目标是最小化完成时间,同时确保满足各种约束条件。
|
8天前
|
负载均衡 算法 Linux
在Linux中,LVS的负载调度算法是什么?
在Linux中,LVS的负载调度算法是什么?
|
2月前
|
缓存 负载均衡 算法
(四)网络编程之请求分发篇:负载均衡静态调度算法、平滑轮询加权、一致性哈希、最小活跃数算法实践!
先如今所有的技术栈中,只要一谈关于高可用、高并发处理相关的实现,必然会牵扯到集群这个话题,也就是部署多台服务器共同对外提供服务,从而做到提升系统吞吐量,优化系统的整体性能以及稳定性等目的。
|
2月前
|
算法 大数据 调度
探索操作系统的心脏:进程调度算法
【7月更文挑战第31天】在数字世界的复杂编织中,操作系统扮演着枢纽的角色,而进程调度则是其跳动的心脏。本文将深入探讨几种常见的进程调度算法,通过代码示例揭示它们对系统性能的影响,并讨论如何根据应用场景选择恰当的调度策略。
21 1
|
2月前
|
机器学习/深度学习 缓存 并行计算
操作系统调度算法的演变与优化
【7月更文挑战第23天】本文深入探讨了操作系统中调度算法的发展历程,从简单的先来先服务到复杂的多级反馈队列调度算法。通过分析不同算法的特点和性能表现,文章揭示了调度算法在提升系统响应速度、公平性以及资源利用率方面的重要性。同时,文章也讨论了现代操作系统如何通过优化调度算法来适应多核处理器架构,以及未来可能的研究方向。
|
2月前
|
算法 网络性能优化 调度
基于De-Jitter Buffer算法的无线网络业务调度matlab仿真,对比RR调度算法
1. **功能描述**: 提出了一个去抖动缓冲区感知调度器,结合用户终端的缓冲状态减少服务中断。该算法通过动态调整数据包发送速率以优化网络延迟和吞吐量。 2. **测试结果**: 使用MATLAB 2022a进行了仿真测试,结果显示De-Jitter Buffer算法在网络拥塞时比RR调度算法更能有效利用资源,减少延迟,并能根据网络状态动态调整发送速率。 3. **核心程序**: MATLAB代码实现了调度逻辑,包括排序、流量更新、超时和中断处理等功能。 仿真结果和算法原理验证了De-Jitter Buffer算法在无线网络调度中的优势。
|
2月前
|
机器学习/深度学习 算法 物联网
深入剖析操作系统调度算法
【7月更文挑战第13天】本文旨在探讨和比较不同的操作系统调度算法,并分析其对系统性能的影响。文章首先概述了调度算法的基本概念及其重要性,随后详细阐述了常见的调度算法类型,包括先来先服务、短作业优先、优先级调度、时间片轮转以及多级反馈队列等。通过对比不同算法的优缺点,文章进一步探讨了现代操作系统中调度算法的应用与挑战,以及如何根据实际需求选择合适的调度策略。最后,文章展望了操作系统调度算法的未来发展方向,特别是在云计算和物联网时代下的适应性与创新。
30 1
|
2月前
|
算法 调度 UED
深入理解操作系统之进程调度算法
【7月更文挑战第31天】在操作系统的设计中,进程调度是核心功能之一,它直接关系到系统性能和用户体验。本文将探讨几种常见的进程调度算法,并通过代码示例加深理解。我们将从理论到实践,一探究竟。
17 0
|
2月前
|
机器学习/深度学习 算法 数据挖掘
操作系统调度算法的演进与性能分析
随着计算机科学的发展,操作系统作为硬件与软件之间的桥梁,其调度算法对系统性能有着举足轻重的影响。本文将探讨操作系统中调度算法的演变,从早期的简单调度策略到现代复杂的多级反馈队列和实时调度机制,并结合最新研究和实验数据,深入分析不同调度算法对系统吞吐量、响应时间及资源利用率的影响。通过对调度算法性能的定量评估,本文旨在为系统设计者提供优化决策的理论依据,同时为未来调度算法的研究指明方向。
27 0

热门文章

最新文章

下一篇
云函数