磁盘调度算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN)

2024-04-24 15:32

本文主要是介绍磁盘调度算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

常见的磁盘调度算法有以下几种:

1.FIFO:先来先服务算法;

2.SSTF: 最短寻道时间算法;

3.SCAN:电梯调度算法;(这样命名很形象)

4.CSCAN: 循环扫描算法

5.FSCAN:分步电梯调度算法(分两个队列)


下面详细说一下各个算法的主要思想:

首先是FIFO算法,也就是先来先服务算法。这种算法的思想比较容易理解。假设当前磁道在某一位置,依次处理服务队列里的每一个磁道,这样做的优点是处理起来比较简单,但缺点是磁头移动的距离和平均移动距离会很大。

其次,是SSTF,最短寻道时间算法。这种算法的本质是利用贪心算法来实现,假设当前磁道在某一位置,接下来处理的是距离当前磁道最近的磁道号,处理完成之后再处理离这个磁道号最近的磁道号,直到所有的磁道号都服务完了程序结束。这样做的优点是性能会优于FIFO算法,但是会产生距离当前磁道较远的磁道号长期得不到服务,也就是“饥饿”现象,因为要求访问的服务的序列号是动态产生的,即各个应用程序可能不断地提出访问不同的磁道号的请求。

接下来,是SCAN算法,也就是很形象的电梯调度算法。先按照一个方向(比如从外向内扫描),扫描的过程中依次访问要求服务的序列。当扫描到最里层的一个服务序列时反向扫描,这里要注意,假设最里层为0号磁道,最里面的一个要求服务的序列是5号,访问完5号之后,就反向了,不需要再往里扫。结合电梯过程更好理解,在电梯往下接人的时候,明知道最下面一层是没有人的,它是不会再往下走的。

然后是,CSCAN算法,循环扫描算法,来看一下上一种算法,有什么问题。仔细一看,我们会发现,在扫描到最里面的要求服务的序列时,接着会反向,在接下来的很大一部分时间里,应该是没有要求服务的磁道号的,因为之前已经访问过了。什么意思,就是说从初始磁道号到最里层的一个磁道号之间的所有序列都已经访问过了,所以SCAN会增加等待的时间。为了解决这样的情况,CSCAN算法的思想是,访问完最里面一个要求服务的序列之后,从最外层的序号开始往里走。也就是始终保持一个方向。就像梳头发,从上往下梳,到了最下面之后,再一次的从上往下梳,这个顺序是不会变的。没有人会从下往上梳头发吧。。

最后,是FSCAN算法,也就是分步电梯调度算法。算法思想是,在扫描的过程中所有新产生的序列放在另外的一个队列中,当访问完当前队列之后,再访问新产生的一个队列。这种算法可以有效防止磁壁粘着现象。


下面结合一个例子来看一下,服务的顺序和计算磁头移动的总距离。

假设当前磁头在67号,要求访问的磁道号顺序为98,25,63,97,56,51,55,55,6  (电脑随机产生的,设定最外层磁道号为100号)

FIFO算法的服务序列是:98,25,63,97,56,51,55,55,6

磁头移动的总距离distance = (98-67)+(98-25)+(63-25)+(97-63)+(97-56)+(56-51)+(55-51)+(55-55)+(55-6)

SSTF算法的服务序列是: 63,56,55,55,51,25,6,97,98

磁头移动的总距离distance = (67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)

SCAN算法的服务序列是:63,56,55,55,51,25,6,97,98

磁头移动的总距离distance = (67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)

我发现这里例子举的不好,SSTF和SCAN算法的服务序列竟是一样的,尴尬!

CSCAN算法的服务序列是:63,56,55,55,51,25,6,98,97

磁头移动的总距离distance = (67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(100-98)+(98-97)

上式中,当扫描到磁道6时,直接从6号磁道移动到98号磁道,所以需要计算从6号移动到98号的距离,所以作更正:

distance = (67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+|6-98|+(98-97),感谢woshiqinyikun,qq_35819971提出意见


原文地址https://blog.csdn.net/jaster_wisdom/article/details/52345674

这篇关于磁盘调度算法剖析(FIFO、SSTF、SCAN、CSCAN、FSCAN)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/932123

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int