首页 / 算法 / 操作系统-磁盘调度算法

操作系统-磁盘调度算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了操作系统-磁盘调度算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8025字，纯文字阅读大概需要12分钟。

内容图文

一、算法或原理的实现思想[1]

1、先来先服务算法（FCFS）First Come First Service

这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。

2、最短寻道时间优先算法（SSTF） Shortest Seek Time First

该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。

3、扫描算法（SCAN）电梯调度

扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

4、循环扫描算法（CSCAN）

循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。

二、程序（带注释）

(更方便阅读的形式已上传至博客)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAXLEN 100
int listLen;
int currentlyTrack;
int input[MAXLEN] = {0};

void fcfs();
void sstf();
void scan();
void cscan();

typedef struct Node
{
   bool flag;
   int data;
}NODE;

int main()
{
   int choice = 0;
   printf("------------- Welcome to the Banker Algorithm Simulator!-------------\n");
   printf("Please input the number of the access sequence:\n");
   scanf("%d", &listLen);
   if (listLen > MAXLEN)                      // The most access sequence is 100
  {
       printf("ERROR! No more than 100!");
       exit(0);
  }
   else
  {
       printf("Please input the access sequence:\n");  // input the access sequence
       for (int i=0; i < listLen; i++)
           scanf("%d", &input[i]);
  }

   printf("Please input current track:\n");          // input current track
   scanf("%d", &currentlyTrack);
   printf("Please choose a scheduling algorithm:\n");// choose algorithm
   printf("0. FCFS     1. SSTF     2. SCAN     3. CSCAN\n");
   scanf("%d", &choice);
   system("cls");
   printf("------------- Welcome to the Banker Algorithm Simulator!-------------\n");
   printf("The access sequence is :\n");           // output the sequence
   for (int i=0; i < listLen; i++)
       printf("%d ", input[i]);
   printf("\n");
   printf("Current track is : %d\n", currentlyTrack);// output current track
   switch(choice)
  {
       case 0: fcfs(); break;
       case 1: sstf(); break;
       case 2: scan(); break;
       case 3: cscan();break;
       default: printf("ERROR! Not a legal algorithm number!");exit(0);
  }
   return 0;
}

void fcfs()                     // First come first serve
{
   printf("Next track\t\tMoving distance\n");
   printf("%d\t\t\t%d\n", input[0], abs(input[0]-currentlyTrack));
   for (int i=1; i < listLen; i++)
       printf("%d\t\t\t%d\n", input[i], abs(input[i]-input[i-1]));
}

void sstf()                    // Shortest seek time priority
{
   int index = currentlyTrack;
   int newListLen = listLen + 1;
   NODE in[newListLen];
   int out[newListLen];
   int count = 0;
   for (int i=0; i < listLen; i++) // package a struct
  {
       in[i].data = input[i];
       in[i].flag = true;          // flag to describe if it is assign
  }
   in[listLen].data=currentlyTrack,in[listLen].flag=false; // add the current track to the sequence
   for (int i=0; i < newListLen-1; i++)    // sort the sequence
       for (int j=0; j < newListLen-1-i; j++)
           if (in[j].data > in[j+1].data)
          {
               NODE tmp = in[j];
               in[j] = in[j+1];
               in[j+1] = tmp;
          }
   for (int i=0; i < newListLen; i++)  // find out the current track's index
       if (!in[i].flag)
      {
           index = i;
           break;
      }
   while (true)
  {
       out[count++] = in[index].data;
       int i=index,j=index;
       while (!in[i].flag)
           i--;
       while (!in[j].flag)
           j++;
       if (i<0 && j>=newListLen)   // all track was assigned
           break;
       else if (i < 0)             // i is invalid
           index = j;
       else if (j > newListLen)    // j is invalid
           index = i;
       else
           index = in[i].data>in[j].data?i:j;  // find out the bigger one's index
       in[index].flag = false;     // sign out this track was assigned
  }
   printf("Next track\t\tMoving distance\n");
   for (int i=1; i < newListLen; i++)
       printf("%d\t\t\t%d\n", out[i], abs(out[i]-out[i-1]));
}

void scan() //Scan
{
   int choice = 0;
   int index = currentlyTrack;
   int newListLen = listLen + 1;
   NODE in[newListLen];
   int out[newListLen];
   int count = 0;
   printf("Please input the current access direction:\n0. increase\t\t1. decrease\n");
   scanf("%d", &choice);
   if (choice!=0 && choice!=1)
  {
       printf("ERROR! %d is not a valid direction! Input again!", choice);
       scan();
  }
   for (int i=0; i < listLen; i++)
  {
       in[i].data = input[i];
       in[i].flag = true;
  }
   in[listLen].data=currentlyTrack,in[listLen].flag=false;
   for (int i=0; i < newListLen-1; i++)
       for (int j=0; j < newListLen-1-i; j++)
           if (in[j].data > in[j+1].data)
          {
               NODE tmp = in[j];
               in[j] = in[j+1];
               in[j+1] = tmp;
          }
   for (int i=0; i < newListLen; i++)
       if (!in[i].flag)
      {
           index = i;
           break;
      }
   out[count++] = currentlyTrack;
   if (!choice)
  {
       for (int i=index+1; i < newListLen; i++)    // if increase direction, assign back of the current track
           out[count++] = in[i].data;
       for (int i=index-1; i >= 0; i--)            // then assign pre of it
           out[count++] = in[i].data;
  }
   else
  {
       for (int i=index-1; i >= 0; i--)
           out[count++] = in[i].data;
       for (int i=index+1; i < newListLen; i++)
           out[count++] = in[i].data;
  }
   printf("Next track\t\tMoving distance\n");
   for (int i=1; i < count; i++)
       printf("%d\t\t\t%d\n", out[i], abs(out[i]-out[i-1]));
}

void cscan()    //Cycle scan
{
   int choice = 0;
   int index = currentlyTrack;
   int newListLen = listLen + 1;
   NODE in[newListLen];
   int out[newListLen];
   int count = 0;
   printf("Please input the current access direction:\n0. increase\t\t1. decrease\n");
   scanf("%d", &choice);
   if (choice!=0 && choice!=1)
  {
       printf("ERROR! %d is not a valid direction! Input again!", choice);
       scan();
  }
   for (int i=0; i < listLen; i++)
  {
       in[i].data = input[i];
       in[i].flag = true;
  }
   in[listLen].data=currentlyTrack,in[listLen].flag=false;
   for (int i=0; i < newListLen-1; i++)
       for (int j=0; j < newListLen-1-i; j++)
           if (in[j].data > in[j+1].data)
          {
               NODE tmp = in[j];
               in[j] = in[j+1];
               in[j+1] = tmp;
          }
   for (int i=0; i < newListLen; i++)
       if (!in[i].flag)
      {
           index = i;
           break;
      }
   out[count++] = currentlyTrack;
   if (!choice)
  {
       for (int i=index+1; i < newListLen; i++)
           out[count++] = in[i].data;
       for (int i=0; i < index; i++)
           out[count++] = in[i].data;
  }
   else
  {
       for (int i=0; i < index; i++)
           out[count++] = in[i].data;
       for (int i=index+1; i < newListLen; i++)
           out[count++] = in[i].data;
  }
   printf("Next track\t\tMoving distance\n");
   for (int i=1; i < count; i++)
       printf("%d\t\t\t%d\n", out[i], abs(out[i]-out[i-1]));
}

三、程序的输入和输出

测试数据1：

55 58 39 18 90 160 150

100

0
操作系统-磁盘调度算法 - 文章图片

测试数据2：

55 58 39 18 90 160 150

100

1
操作系统-磁盘调度算法 - 文章图片

测试数据3：

55 58 39 18 90 160 150

100

0 操作系统-磁盘调度算法 - 文章图片

测试数据4：

55 58 39 18 90 160 150

100

1 操作系统-磁盘调度算法 - 文章图片

测试数据5：

55 58 39 18 90 160 150

100

0 操作系统-磁盘调度算法 - 文章图片
测试数据6：

55 58 39 18 90 160 150

100

1
操作系统-磁盘调度算法 - 文章图片

四、参考文献

[1] 磁盘调度算法的设计思想

[2] SSTF算法实现
五、感想、体会或收获
进行sstf算法实现时遇到了Codeblocks无debug的问题。

初始思路为将已调度的磁道序号置为-1，但因为不能debug，并且未能解决，在阅读一个Java实现的代码后，发现他为磁盘号创建一个类，内部设flag作为是否调度的标志，于是想到用结构体为序列封装，增加flag表示是否完成调度，得以解决问题。

另外发现，以先排序再调度的方法实现算法，SSTF、SCAN和CSCAN算法实现函数的耦合度极高，但时间紧迫，因此未对耦合部分抽离为函数。且排序算法为了简单选用了冒泡排序，后期优化为快速排序。

内容总结

以上是互联网集市为您收集整理的操作系统-磁盘调度算法全部内容，希望文章能够帮你解决操作系统-磁盘调度算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/618682.html

来源：【匿名】

【上一篇】简单选择排序——c++【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【操作系统-磁盘调度算法】教程文章相关的互联网学习教程文章

操作系统磁道调度算法（C++实现）【代码】【图】

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）代码变量声明：1 vector<int> TrackOrder; //磁道初始序列在函数中简写为 t2 vector<int>...

操作系统之页面置换算法（最佳置换OPT，先进先出FIFO，最近最久未使用LRU）【代码】【图】

最近学习操作系统时，实验要求实现常见的三种页面置换算法，博主按照书上要求试着编写，实现了案例，并记录在博客随记中，以便后续自己复习并也给需要的同学分享参考一下!水平有限，若有错，请悄悄告诉博主！博主好立即改正。最佳置换算法（optimal replacement，OPT）是从内存中选择今后不再访问的页面或者在最长一段时间后才需要访问的页面进行淘汰。如下例子： 1 #include <iostream>2 #include <stdio.h>3 #include <stdlib.h...

短作业优先算法_操作系统_c语言实现【代码】【图】

PTA题目注:在PTA上面提交时务必把scanf_s改成scanf,(编译器用的是vs2019). 主函数 int main() {int n; //进程数量scanf_s("%d", &n);struct pcb p[100];input(p,n);sort(p,n);sjf(p, n);output(p,n);return 0; }核心算法 void sjf(struct pcb* p, int n) {int finishedcount = 0; //记录已经完成的进程数 int unfinishedposition = 0; // 记录未完成的进程的位置 double nowtime = 0; //现在时间for...

超硬核！学霸把操作系统经典算法给敲完了！要知行合一

上期的笔记，浏览快1万了，既然关注的人很多，那就发出来承诺过的算法全模拟，希望帮到你们。上期的操作系统学霸笔记，考试复习面试全靠它一、模拟进程调度功能 data.h #ifndef _Data_h_ #define _Data_h_#include <stdio.h> #include <stdlib.h> #include <string.h>#define ElemType PCB #define Status int #define OK 1 #define ERROR 0 #define TimeSlice 1 #define Infinity 10 //INT_MAX#define NAME_MAXSIZE 20 typedef...

操作系统之调度算法

操作系统管理了系统的有限资源，当有多个进程(或多个进程发出的请求)要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程(请求)来占用资源。这就是调度。目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。这时就可以根据不同的调度的方法来进行处理进程。 FCFS(First-Come，First-Served) 先来先服务调度算法：在进程调度中，FCFS就是从就绪队列的队首选择最先到达就绪队列的进度，为该进程分配CPU...

操作系统课程设计之银行家算法【代码】【图】

操作系统课程设计之银行家算法背景银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超...

操作系统中的『银行家算法（避免死锁）』

银行家算法中的数据结构需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程 i 还需要 Rj 类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j] 银行家算法的步骤（判断是否为安全状态）设Request i是进程Pi的请求向量，如果Requesti [j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：计算Need矩...

操作系统，最先适应分配算法代码【代码】

以下代码如有疑问，请联系博主，最佳适应算法与最差适应算法只需添加简单的排序即可完成（本代码中未添加） #include <windows.h> #include <conio.h> #include <stdlib.h> #include <stdio.h> #include <io.h> #include <string.h>#define MAX_THREAD 3typedef struct freearea { //表示空闲区域的数据结构struct freearea *next; //指向下一个结点的指针int start_address; ...

操作系统-银行家算法(Java实现)【代码】【图】

一、银行家算法思想银行家算法是最著名的死锁避免算法，其思想是：将操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行继续申请资源是，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过...

最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现【代码】

?经过读题，我觉得这两个题目要表达的意思应该是完全相同的，当然也可能是我的理解出现了偏差。所以就把LRU 和 LFT 当作是一个。 ?当然，因为这个缘故，我把最近最久未使用的LRU当作了最久未使用写到底，到最后发现还是更像最不常用置换算法LFT一些。 ? 下面就是代码了，用C语言链表实现，希望能给同学们提供一种思路。 Main函数中有测试样例，思路什么的就不写了，代码中都已经注释出来了，如果有疑问的话请评论区留言。LFT.h #in...

操作系统之调度算法【图】

调度算法的评价指标 cpu利用率cpu利用率=cpu有效工作时间 / (cpu有效工作时间+cpu空闲时间)系统吞吐量：单位时间内完成作业的数量系统吞吐量=总共完成作业数 / 总共耗费时间周转时间：从作业被提交到作业完成为止的时间间隔周转时间 = 作业完成时间 - 作业提交时间带权周转时间带权周转时间 = 周转时间 / 作业实际运行时间平均周转时间平均周转时间 = 各作业周转时间之和 / 作业数平均带权周转时间平均带权周转时间 = 各作业带权周...

操作系统(5) 死锁的概念死锁产生的必要条件死锁的处理策略预防死锁避免死锁死锁的检测和解除银行家算法【图】

死锁文章目录死锁一、死锁的概念1. 死锁、饥饿、死循环的区别2. 死锁产生的必要条件3. 死锁的处理策略二、死锁的处理策略 --- 预防死锁三、死锁的处理策略 --- 避免死锁1. 安全序列的介绍2. 银行家算法四、死锁的处理策略 --- 死锁的检测与解除1. 死锁的检测2. 死锁的解除3. 知识回顾一、死锁的概念 1. 死锁、饥饿、死循环的区别 (1) 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进 (2) 饥饿：长期得不到...

【操作系统】页面置换算法（最佳置换算法）（C语言实现）【代码】【图】

【操作系统】页面置换算法（最佳置换算法）（C语言实现） #####（编码水平较菜，写博客也只是为了个人知识的总结和督促自己学习，如果有错误，希望可以指出） 1.页面置换算法：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置...

【操作系统】编程模拟FIFO，LRU，NUR，OPT页面置换算法【代码】

#include<stdio.h> #include<stdlib.h> #include<time.h> #define random(x) (rand()%x)#define LOG 1 //1-show log 2-no show #define TYPE 10 //page types #define NUM 20 //page nums #define SIZE 5 //cache sizestruct page{int id;//page idint time=0;//different meaning in different algorithm }; struct page pageList[NUM],cache[SIZE];//page needs,page cachevoid init(){//rando...

操作系统页面置换算法（最佳置换算法，FIFO，LRU，Clock）【图】

页面置换算法为什么要页面置换最佳置换算法先进先出页面置换算法LRU置换算法Clock置换算法为什么要页面置换缺页中断：在地址映射过程中，若在页表中发现所要访问的页面不在内存，则产生中断，当发生中断时，系统必须在内存选择一个页面移出内存，以便为调入新的页面让出空间。缺页率的计算：假设一个进程的逻辑空间为n页，系统为其分配的物理块数为m，如果在进程运行的过程当中，访问页面成功（即所访问的页面在内存中）的次数...

首页 / 算法 / 操作系统-磁盘调度算法

操作系统-磁盘调度算法

内容导读

内容图文

一、算法或原理的实现思想[1]

二、程序（带注释）

三、程序的输入和输出

四、参考文献

内容总结

内容备注

内容手机端

【操作系统-磁盘调度算法】教程文章相关的互联网学习教程文章

操作系统 - 相关标签

调度算法 - 相关标签

算法 - 最新教程

算法 - 最热教程