常见的磁盘调度算法-程序员宅基地

技术标签： 操作系统  磁盘调度算法  

目录

更新 2019-8-10：增加了 LOOK 调度算法和添加了一些小的知识点

早期的磁盘调度算法

先来先服务

顾名思义，先来先服务就是按照请求访问磁道的顺序来访问磁道。

我们来看一个实例
在这里插入图片描述
从 100 开始，按照请求的顺序，依次访问 55，58 … 等磁道。
移动距离是上一个磁道到下一个磁道的距离。

  1. 优点：公平，避免饥饿现象发生，不会产生磁臂黏着现象
  2. 缺点：寻道时间长

最短寻道时间优先（SSTF）

SSTF 的原理是访问的下一个磁道是距离现在这个磁道最近的那一个磁道。

假如此时磁盘请求队列如下，55，58，39，18，90，160，150，38，184，初始磁道是 100。

此时在整个队列中距离 100 最近的磁道是 90，于是磁头移动到 90 处。在队列剩余磁道中，距离 90 最近的是 58，于是磁头又移动到 58。以此类推。

注意，每次比较的两个数值一个是当前磁道数，另一个是队列中剩余的磁道数，拉通比较（实际上看一眼就知道了）后选择最近的。
在这里插入图片描述
可以看到 90 这个磁道是距离 100 这个磁道距离最近的磁道，所以先访问。
而 58 这个磁道是距离 90 这个磁道距离最近的，所以是接下来访问。

  1. 优点：比先来先算法性能更好
  2. 缺点：容易造成饥饿现象

为什么会造成饥饿现象

因为磁道的请求时动态的，随时都会有新的磁道请求加入，如果，一段时间内，所请求的磁道数都是在当前磁道数附近，那么早期请求但是距离当前磁道远的磁道将长时间得不到满足，造成饥饿现象。

基于扫描的磁盘调度算法

扫描算法（电梯调度算法，SCAN）

我们看到 SSTF 算法虽然性能好，但是容易造成饥饿现象，本质上就是磁头一直处在当前
磁道的小范围内。所以扫描算法就是用来解决这个问题的。

  1. 基本原理：就像它的名字一样，“电梯”算法先按照一个方向进行扫描，比如从内向外（如，从 0 号磁道向 100 好磁道移动就叫从内向外），再从外回到内（简单来说就是，从小到大，再从大到小）
  2. 注意点：在移动的过程中，不必到头才转向，如此时从外向内，当磁头移动到 5 号时，已经到达了本轮的最小磁道，就不会继续向 0 号移动了
  3. 示例：扫描算法的解决方式是，就是在 SSTF 的基础上增加了对磁头移动方向的规定。比如，此时磁盘请求队列中的请求顺序是 55，58，39，18，90，160，150，38，184。磁头初始位置在 100，且磁头沿着磁道号增大的方向移动。那么整个过程如下图所示
    在这里插入图片描述

循环扫描算法（Circular SCAN）

扫描算法也同样存在问题，那就是，如果我按照向外的方向，刚走过假设是 100 的磁道，此时新请求是 99 磁道，但是因为需要继续向外，所以不能访问 99 磁道，这就造成了一定的开销。

  1. 基本原理：循环扫描规定了磁头单向移动，在返回时是直接快速移动到起始端。比如现在假定该算法按照从内向外移动，当磁道扫描完本轮的最外（大）磁道 184 号时，磁头会直接移动到当前的最内磁道 18 号，如下图所示
    在这里插入图片描述

LOOK 调度算法

look 调度算法是对 SCAN 算法和 C-SCAN 算法的优化

在 SCAN 算法和 C-SCAN 算法中，磁头移动（如向外移动）时，必须要达到远端（最远的那个磁道）才回返。比如最远的磁道数是 200，而此时请求调度的磁道数是 180，但我们依然要移动到 200 才回返。

优化的点就在这里，LOOK 算法不需要达到磁盘的端点（如果这个端点没有处于请求队列中），只需要达到最远的那个请求的磁道就可以返回了。其实现的方法是每次移动前查看是否有更远的请求。

比如我们看到的下面两幅图片，分别是对 SCAN 和 C-SCAN 进行优化后的 LOOK 算法，它们都没有到达端点在回返。

（下面两幅图片的来源）
在这里插入图片描述

在这里插入图片描述

参考

  1. 《计算机操作系统》
  2. 磁盘调度算法剖析
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_34902437/article/details/83592055

智能推荐

JavaScript学习笔记_curry函数未定义-程序员宅基地

文章浏览阅读343次。五种原始的变量类型1.Undefined--未定义类型 例：var v;2.String -- ' '或" "3.Boolean4.Number5.Null--空类型 例： var v=null;Number中：NaN -- not a number非数本身是一个数字，但是它和任何数字都不相等，代表非数，它和自己都不相等判断是不是NaN不能用=_curry函数未定义

兑换码编码方案实践_优惠券编码规则-程序员宅基地

文章浏览阅读1.2w次，点赞2次，收藏17次。兑换码编码设计当前各个业务系统，只要涉及到产品销售，就离不开大大小小的运营活动需求，其中最普遍的就是兑换码需求，无论是线下活动或者是线上活动，都能起到良好的宣传效果。兑换码：由一系列字符组成，每一个兑换码对应系统中的一组信息，可以是优惠信息（优惠券），也可以是相关奖品信息。在实际的运营活动中，要求兑换码是唯一的，每一个兑换码对应一个优惠信息，而且需求量往往比较大（实际上的需求只有预期_优惠券编码规则

c语言周林答案,C语言程序设计实训教程教学课件作者周林ch04结构化程序设计课件.ppt...-程序员宅基地

文章浏览阅读45次。C语言程序设计实训教程教学课件作者周林ch04结构化程序设计课件.ppt* * 4.1 选择结构程序设计 4.2 循环结构程序设计 4.3 辅助控制语句 第四章 结构化程序设计 4.1 选择结构程序设计 在现实生活中，需要进行判断和选择的情况是很多的: 如果你在家，我去拜访你 如果考试不及格，要补考 如果遇到红灯，要停车等待 第四章 结构化程序设计 在现实生活中，需要进行判断和选择的情况..._在现实生活中遇到过条件判断的问

幻数使用说明_ioctl-number.txt幻数说明-程序员宅基地

文章浏览阅读999次。幻数使用说明 在驱动程序中实现的ioctl函数体内，实际上是有一个switch{case}结构，每一个case对应一个命令码，做出一些相应的操作。怎么实现这些操作，这是每一个程序员自己的事情。 因为设备都是特定的，这里也没法说。关键在于怎样组织命令码，因为在ioctl中命令码是唯一联系用户程序命令和驱动程序支持的途径 。 命令码的组织是有一些讲究的，因为我们一定要做到命令和设备是一一对应的，利_ioctl-number.txt幻数说明

ORB-SLAM3 + VScode:检测到 #include 错误。请更新 includePath。已为此翻译单元禁用波浪曲线_orb-slam3 include <system.h> 报错-程序员宅基地

文章浏览阅读399次。键盘按下“Shift+Ctrl+p” 输入: C++Configurations，选择JSON界面做如下改动：1.首先把 “/usr/include”,放在最前2.查看C++路径，终端输入gcc -v -E -x c++ - /usr/include/c++/5 /usr/include/x86_64-linux-gnu/c++/5 /usr/include/c++/5/backward /usr/lib/gcc/x86_64-linux-gnu/5/include /usr/local/_orb-slam3 include 报错

「Sqlserver」数据分析师有理由爱Sqlserver之十-Sqlserver自动化篇-程序员宅基地

文章浏览阅读129次。本系列的最后一篇，因未有精力写更多的入门教程，上篇已经抛出书单，有兴趣的朋友可阅读好书来成长，此系列主讲有理由爱Sqlserver的论证性文章，希望读者们看完后，可自行做出判断，Sqlserver是否真的合适自己，目的已达成。渴望自动化及使用场景笔者所最能接触到的群体为Excel、PowerBI用户群体，在Excel中，我们知道可以使用VBA、VSTO来给Excel带来自动化操作..._sqlsever 数据分析

随便推点

智慧校园智慧教育大数据平台（教育大脑）项目建设方案PPT_高校智慧大脑-程序员宅基地

文章浏览阅读294次，点赞6次，收藏4次。教育智脑）建立学校的全连接中台，对学校运营过程中的数据进行处理和标准化管理，挖掘数据的价值。能：一、原先孤立的系统聚合到一个统一的平台，实现单点登录，统一身份认证，方便管理；三、数据共享，盘活了教育大数据资源，通过对外提供数。的方式构建教育的通用服务能力平台，支撑教育核心服务能力的沉淀和共享。物联网将学校的各要素（人、机、料、法、环、测）全面互联，数据实时。智慧校园解决方案，赋能教学、管理和服务升级，智慧教育体系，该数据平台具有以下几大功。教育大数据平台底座：教育智脑。教育大数据平台，以中国联通。_高校智慧大脑

编程5大算法总结--概念加实例_算法概念实例-程序员宅基地

文章浏览阅读9.5k次，点赞2次，收藏27次。分治法，动态规划法，贪心算法这三者之间有类似之处，比如都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。贪心是则可看成是链式结构回溯和分支界限为穷举式的搜索，其思想的差异是深度优先和广度优先一：分治算法一、基本概念在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两_算法概念实例

随笔—醒悟篇之考研调剂_考研调剂抑郁-程序员宅基地

文章浏览阅读5.6k次。考研篇emmmmm，这是我随笔篇章的第二更，原本计划是在中秋放假期间写好的，但是放假的时候被安排写一下单例模式，做了俩机试题目，还刷了下PAT的东西，emmmmm，最主要的还是因为我浪的很开心，没空出时间来写写东西。　　距离我考研结束已经快两年了，距离今年的考研还有90天左右。　　趁着这个机会回忆一下青春，这一篇会写的比较有趣，好玩，纯粹是为了记录一下当年考研中发生的有趣的事。　　首先介绍..._考研调剂抑郁

SpringMVC_class org.springframework.web.filter.characterenco-程序员宅基地

文章浏览阅读438次。SpringMVC文章目录SpringMVC1、SpringMVC简介1.1 什么是MVC1.2 什么是SpringMVC1.3 SpringMVC的特点2、HelloWorld2.1 开发环境2.2 创建maven工程a>添加web模块b>打包方式：warc>引入依赖2.3 配置web.xml2.4 创建请求控制器2.5 创建SpringMVC的配置文件2.6 测试Helloworld2.7 总结3、@RequestMapping注解3.1 @RequestMapping注解的功能3._class org.springframework.web.filter.characterencodingfilter is not a jakart

gdb: Don‘t know how to run. Try “help target“._don't know how to run. try "help target".-程序员宅基地

文章浏览阅读4.9k次。gdb 远程调试的一个问题:Don't know how to run. Try "help target".它在抱怨不知道怎么跑，目标是什么. 你需要为它指定target remote 或target extended-remote例如:target extended-remote 192.168.1.136:1234指明target 是某IP的某端口完整示例如下:targ..._don't know how to run. try "help target".

c语言程序设计教程 郭浩志,C语言程序设计教程答案杨路明郭浩志-程序员宅基地

文章浏览阅读85次。习题 11、算法描述主要是用两种基本方法：第一是自然语言描述，第二是使用专用工具进行算法描述2、c 语言程序的结构如下：1、c 语言程序由函数组成，每个程序必须具有一个 main 函数作为程序的主控函数。2、“/*“与“*/“之间的内容构成 c 语言程序的注释部分。3、用预处理命令#include 可以包含有关文件的信息。4、大小写字母在 c 语言中是有区别的。5、除 main 函数和标准库函数以..._c语言语法0x1e

推荐文章

热门文章

相关标签