磁盘调度算法

简介: 磁盘调度算法

磁盘的结构:

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

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


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


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


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


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


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

所以磁盘的物理地址:

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


具体地:


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


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


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


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

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

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

磁盘的分类:

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

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

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

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

磁盘调度:

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

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


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

目录
相关文章
|
2天前
|
算法 人机交互 调度
进程调度算法_轮转调度算法_优先级调度算法_多级反馈队列调度算法
轮转调度算法(RR)是一种常用且简单的调度方法,通过给每个进程分配一小段CPU运行时间来轮流执行。进程切换发生在当前进程完成或时间片用尽时。优先级调度算法则根据进程的紧迫性赋予不同优先级,高优先级进程优先执行,并分为抢占式和非抢占式。多队列调度算法通过设置多个具有不同优先级的就绪队列,采用多级反馈队列优先调度机制,以满足不同类型用户的需求,从而优化整体调度性能。
25 15
|
2天前
|
算法 调度
作业调度算法_先来先服务算法_短作业优先算法_高响应比优先算法
本文介绍了作业调度算法,包括先来先服务(FCFS)、短进程优先(SJF)和高响应比优先(HRRN)算法。通过分析进程的到达时间和所需CPU服务时间,计算进程的开始时间、完成时间、平均周转时间和平均带权周转时间,以评估不同算法的性能。FCFS适合长作业,SJF适合短作业,而HRRN则综合了两者的优点。
22 12
|
4天前
|
算法 调度 UED
深入理解操作系统之进程调度算法
【9月更文挑战第9天】在操作系统的心脏跳动中,进程调度扮演着关键角色,就如同指挥家控制交响乐的节奏。本文将通过浅显易懂的语言和生动的比喻,带领读者走进进程调度的世界,探索不同调度算法背后的哲学与实践,以及它们如何影响系统的性能和用户体验。从最简单的先来先服务到复杂的多级队列和反馈循环,我们将一同见证操作系统如何在众多任务中做出选择,确保系统的高效与公平。
|
23天前
|
DataWorks 算法 调度
B端算法实践问题之配置脚本以支持blink批处理作业的调度如何解决
B端算法实践问题之配置脚本以支持blink批处理作业的调度如何解决
25 1
|
14天前
|
存储 算法 调度
深入理解操作系统:进程调度的算法与实现
【8月更文挑战第31天】在操作系统的核心,进程调度扮演着关键角色,它决定了哪个进程将获得CPU的使用权。本文不仅剖析了进程调度的重要性和基本概念,还通过实际代码示例,展示了如何实现一个简单的调度算法。我们将从理论到实践,一步步构建起对进程调度的理解,让读者能够把握操作系统中这一复杂而精妙的部分。
|
14天前
|
算法 调度 开发者
深入理解操作系统:进程管理与调度算法
在数字时代的心脏,操作系统扮演着至关重要的角色。它不仅是计算机硬件与软件之间的桥梁,更是确保多任务高效运行的守护者。本文将带你一探操作系统中进程管理的奥秘,并通过实际代码示例深入解析进程调度算法。无论你是编程新手还是资深开发者,了解这些基础概念都将有助于你更好地理解计算机工作原理,并提升你对系统性能调优的认识。准备好,让我们一起揭开操作系统的神秘面纱!【8月更文挑战第31天】
|
14天前
|
算法 调度
探索操作系统的心脏:进程调度算法揭秘
【8月更文挑战第31天】本文将带领读者深入理解操作系统中至关重要的一环——进程调度。通过浅显易懂的语言和逐步深入的内容安排,我们将从基础概念入手,探讨进程调度的目的和挑战,进而分析几种常见的调度算法。文中不仅提供了丰富的代码示例,还设计了互动问题,鼓励读者思考并应用所学知识。让我们一起揭开操作系统进程调度的神秘面纱,看看它是如何在幕后支撑着我们日常使用的电脑和移动设备的顺畅运行。
|
1月前
|
存储 算法 调度
基于和声搜索算法(Harmony Search,HS)的机器设备工作最优调度方案求解matlab仿真
通过和声搜索算法(HS)实现多机器并行工作调度,以最小化任务完成时间。在MATLAB2022a环境下,不仅输出了工作调度甘特图,还展示了算法适应度值的收敛曲线。HS算法模拟音乐家即兴创作过程,随机生成初始解(和声库),并通过选择、微调生成新解,不断迭代直至获得最优调度方案。参数包括和声库大小、记忆考虑率、音调微调率及带宽。编码策略将任务与设备分配映射为和声,目标是最小化完成时间,同时确保满足各种约束条件。
|
22天前
|
负载均衡 算法 Linux
在Linux中,LVS的负载调度算法是什么?
在Linux中,LVS的负载调度算法是什么?
|
2月前
|
算法 调度 UED
深入理解操作系统之进程调度算法
【7月更文挑战第31天】在操作系统的设计中,进程调度是核心功能之一,它直接关系到系统性能和用户体验。本文将探讨几种常见的进程调度算法,并通过代码示例加深理解。我们将从理论到实践,一探究竟。
25 0