【操作系统磁盘调度算法】OS实验C语言代码实现FCFS/SSTF/SCAN/CSCAN

2024-01-12 21:59
文章标签 算法 语言 代码 实现 实验 操作系统 调度 磁盘 os fcfs sstf scan cscan

本文主要是介绍【操作系统磁盘调度算法】OS实验C语言代码实现FCFS/SSTF/SCAN/CSCAN，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

  本文使用C语言实现了FCFS/SSTF/SCAN/CSCAN四种磁盘调度算法。提供手动输入磁道号和随机产生磁道号两种方式输入，输出为每一步访问的磁道号，每一步移动的距离以及平均移动距离。
  除了运行结果与教材一致外，还具有:1.可以修改最大随机磁道号(随机产生磁道序列号时)2.可以修改初始访问的磁道号(SSTF,SCAN,CSCAN算法中从哪个磁道号开始搜索)两大亮点。
  程序交互性较好，界面清晰，是本人在操作系统课验收的程序，如果文中有任何问题，欢迎在评论区指出，我会及时修改。希望这篇文章可以帮助到大家。

  本文会大致梳理整体思路以及实现亮点，对于太过于细节的问题不再赘述。
  关于程序完整的源代码，有需要的朋友可以添加本人qq2818120641一杯奶茶钱20r即可。(可以作为实验验收程序或者考研题目的验证手段hh)

文章目录

  • 一、程序运行结果展示
  • 二、本程序的亮点
    • 2.1可以修改最大随机磁道号
      • 2.1.1如何实现随机产生磁道号
      • 2.1.2使用常量定义随机磁道号的最大值
    • 2.2可以修改初始访问的磁道号
  • 三、四种磁盘调度算法的实现过程
    • 3.1 程序的整体结构
    • 3.2 FCFS 先来先服务算法
    • 3.3 SSTF 最短寻道时间优先算法
    • 3.4 SCAN 扫描算法
    • 3.5 CSCAN 循环扫描算法
  • 四、验证本程序运行的正确性
    • 4.1 FCFS验证
    • 4.2 STTF验证
    • 4.3 SCAN验证
    • 4.4 CSCAN验证
  • 五、完整程序下载链接
  • 六、补充
  • 七、杂谈

一、程序运行结果展示

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在此，先贴一下程序的头文件和主函数(不包括自定义的函数)【完整程序下载链接在最后的部分】，方便读者的理解，也方便下文的讲述的展开。

#include <stdio.h>
#include <stdlib.h>
#define MAX_DISK 200
#define BEGIN_DISK 100
int main()
{while (1){int disk_num = 0;printf("请输入磁道号序列长度：\n");scanf("%d", &disk_num);int list[disk_num];init(list, disk_num);int result_list[disk_num];init(result_list, disk_num);int choice=0;printf("请选择: 1.自行输入页面数据 2.随机产生页面数据\n");scanf("%d", &choice);if(choice==1){printf("请输入磁道号序列：\n");for (int i = 0; i < disk_num; i++)scanf("%d", &list[i]);	}else if(choice==2){	int flag[MAX_DISK+1];init(flag,MAX_DISK+1);for (int i = 0; i < disk_num; i++){int a = rand() % (MAX_DISK) + 1;//产生disk_num个1到200的随机数 if (flag[a]==-1){list[i]=a; flag[a]=1;}else{i=i-1;}				}printf("磁道号序列为:\n");for(int i=0;i<disk_num;i++){printf("%d ",list[i]);if((i+1)%10==0)printf("\n");}printf("\n");  }else{printf("----------输入非法数字，请输入1或者2----------\n\n");continue;} FCFS(list, disk_num, result_list);init(result_list, disk_num);SSTF(list, disk_num, result_list);init(result_list, disk_num);SCAN(list, disk_num, result_list);init(result_list, disk_num);CSCAN(list, disk_num, result_list);init(result_list, disk_num);printf("\n\n--------------------\n\n");}
}

其中：
void init(int list[], int num)
void show_result(int list[], int num)
void quicksort(int num[],int count,int left,int right)
void FCFS(int list[], int disk_num,int result_list[])
void SSTF(int list[], int disk_num,int result_list[])
void SCAN(int list[], int disk_num,int result_list[])
void CSCAN(int list[], int disk_num,int result_list[])
均为自定义函数

二、本程序的亮点

2.1可以修改最大随机磁道号

  由于老师的要求，需要采用随机输入磁道号序列的方式运行程序，目的是为了避免每次手动输入数据的繁琐性。因此就会产生一个问题：随机的磁道号范围应该是多少：是[1,100],[1,200]还是[1,500]？所以，需要在程序中方便地修改最大的磁道号。
在这里插入图片描述

  例如书本中的例子，此时输入的磁道号序列为55,58,39,18,90,160,150,38,184。此时最小磁道号为18，最大磁道号为184,初始访问的磁道号为100。
  倘若我们选择手动输入磁道号的方式，那么基本不需要关注磁道号范围的问题，输入的数字只需要在定义的int变量的[-2147483648,2147483647]范围内即可。但是如果采用随机生成序列的方式，就需要一个常量来控制产生的最大磁道号。
  ps:其实最小磁道号也可以使用一个常量来保存，实现方法与最大磁道号相似，但一般都是从1开始，因此，不考虑再设置一个最小磁道号常量。

2.1.1如何实现随机产生磁道号

  首先我们要明确，磁盘调度算法的磁道号序列是确定的，因此，输入的磁道号中不能有重复的数字，所以我们产生的随机磁道号序列需要保证这一点，主要靠以下代码实现（产生的结果存放在list[]数组中）。

int flag[MAX_DISK+1];init(flag,MAX_DISK+1);for (int i = 0; i < disk_num; i++){int a = rand() % (MAX_DISK) + 1;//产生disk_num个1到200的随机数 if (flag[a]==-1){list[i]=a; flag[a]=1;}else{i=i-1;}				}

  主要的思路就是另开一个大小跟最大磁道号一样大的数组flag[]，用来存放每次产生的数字之前是否产生过，如果产生过，就需要让i减1，重新产生随机数，直至产生够了disk_num个数字。

2.1.2使用常量定义随机磁道号的最大值

  相信大家通过上面的代码已经发现了，程序是使用定义宏常量的方式控制产生的最大随机数为200的，定义MAX_DISK常量的代码如下：

#define MAX_DISK 200

  同时，想要随机数的范围，只需要修改下面这句话即可

int a = rand() % (MAX_DISK) + 1;//产生disk_num个1到200的随机数

  例如现想要修改随机数范围为[50,450],则将代码修改为：

#define MAX_DISK 400
int a = rand() % (MAX_DISK) + 50;//产生disk_num个50到450的随机数

2.2可以修改初始访问的磁道号

  四种磁盘调度算法均可以通过共享BEGIN_DISK常量，以实现对初始访问磁道号的快速修改。以SSTF算法为例：

#define BEGIN_DISK 100
void SSTF(int list[], int disk_num,int result_list[])
{	printf("----------SSTF----------\n");int temp_list[disk_num];init(temp_list, disk_num);for(int i=0;i<disk_num;i++){temp_list[i]=list[i]; 	}int last=BEGIN_DISK; //第一次寻找从BEGIN_DISK号磁道开始int flag[disk_num];//定义数组，标志磁道是否被访问过了 init(flag,disk_num); //初始化数组，置为-1，表示未被访问过 for (int n=0;n<disk_num;n++){	int distance=999;//寻找距离int mindistance=999;int mint=0; for(int t=0;t<disk_num;t++){	if(flag[t]==-1){distance=abs(last-list[t]);if(distance<mindistance){mindistance=distance;mint=t;}}	} result_list[n]=list[mint];last=list[mint];flag[mint]=1;//标志磁道号已经被访问过 }show_result(result_list,disk_num);printf("----------SSTF结束----------\n");
}

  其中BEGIN_DISK常量作为初始的last变量的值。假如想要修改初始磁道为150，只需要修改以下代码即可:

#define BEGIN_DISK 150

三、四种磁盘调度算法的实现过程

3.1 程序的整体结构

  按照mian()函数的代码，先对程序的整体结构进行描述。再次将main()函数贴一下：

#include <stdio.h>
#include <stdlib.h>
#define MAX_DISK 200
#define BEGIN_DISK 100
int main()
{while (1){int disk_num = 0;printf("请输入磁道号序列长度：\n");scanf("%d", &disk_num);int list[disk_num];init(list, disk_num);int result_list[disk_num];init(result_list, disk_num);int choice=0;printf("请选择: 1.自行输入页面数据 2.随机产生页面数据\n");scanf("%d", &choice);if(choice==1){printf("请输入磁道号序列：\n");for (int i = 0; i < disk_num; i++)scanf("%d", &list[i]);	}else if(choice==2){	int flag[MAX_DISK+1];init(flag,MAX_DISK+1);for (int i = 0; i < disk_num; i++){int a = rand() % (MAX_DISK) + 1;//产生disk_num个1到200的随机数 if (flag[a]==-1){list[i]=a; flag[a]=1;}else{i=i-1;}				}printf("磁道号序列为:\n");for(int i=0;i<disk_num;i++){printf("%d ",list[i]);if((i+1)%10==0)printf("\n");}printf("\n");  }else{printf("----------输入非法数字，请输入1或者2----------\n\n");continue;} FCFS(list, disk_num, result_list);init(result_list, disk_num);SSTF(list, disk_num, result_list);init(result_list, disk_num);SCAN(list, disk_num, result_list);init(result_list, disk_num);CSCAN(list, disk_num, result_list);init(result_list, disk_num);printf("\n\n--------------------\n\n");}
}

通过while(1){ }语句进行使程序循环运行，方便重新运行。
Step1.让用户输入磁道号序列的长度。
Step2.让用户选择1.自行输入磁道号序列或者2.随机产生磁道号序列。并将磁道号序列存放到list[]数组后，输出展示一遍list[]数组。
Step3.进行四种磁盘调度算法并输出运行结果(在四种调度算法内部调用show_result()函数)。
注意：需要在每次调用磁盘调度算法后使用自定义函数void init(int list[], int num)初始化result_list数组，防止上一个算法的运行结果影响下一个算法
void init(int list[], int num)函数如下：

void init(int list[], int num)
{for (int i = 0; i < num; i++)list[i] = -1;
}

void show_result(int list[], int num)函数如下：

void show_result(int list[], int num)
{	int last=BEGIN_DISK;double move=0;printf("       (从100磁道开始)\n");printf("下一个磁道号    移动距离(磁道数)\n");for(int i=0;i<num;i++){printf("%10d%10d\n",list[i],abs(last-list[i]));move+=abs(last-list[i]);last=list[i];}move=move/num;printf("平均寻道长度：%.1lf\n",move);  
}

3.2 FCFS 先来先服务算法

void FCFS(int list[], int disk_num,int result_list[])
{printf("----------FCFS----------\n");for(int i=0;i<disk_num;i++)result_list[i]=list[i]; show_result(result_list,disk_num);printf("----------FCFS结束----------\n");
}

  这个最简单，只需要把输入的数组直接赋值给result_list[]数组，之后调用show_result()函数按格数输出即可。

3.3 SSTF 最短寻道时间优先算法

void SSTF(int list[], int disk_num,int result_list[])
{	printf("----------SSTF----------\n");int temp_list[disk_num];init(temp_list, disk_num);for(int i=0;i<disk_num;i++){temp_list[i]=list[i]; 	}int last=BEGIN_DISK; //第一次寻找从BEGIN_DISK号磁道开始int flag[disk_num];//定义数组，标志磁道是否被访问过了 init(flag,disk_num); //初始化数组，置为-1，表示未被访问过 for (int n=0;n<disk_num;n++){	int distance=999;//寻找距离int mindistance=999;int mint=0; for(int t=0;t<disk_num;t++){	if(flag[t]==-1){distance=abs(last-list[t]);if(distance<mindistance){mindistance=distance;mint=t;}}	} result_list[n]=list[mint];last=list[mint];flag[mint]=1;//标志磁道号已经被访问过 }show_result(result_list,disk_num);printf("----------SSTF结束----------\n");
}

  SSTF算法实现思路也比较清晰，在每次选择磁道号后计算距离最近的磁道号即可。

3.4 SCAN 扫描算法

void SCAN(int list[], int disk_num,int result_list[])
{printf("----------SCAN----------\n");int temp_list[disk_num];init(temp_list, disk_num);for(int i=0;i<disk_num;i++){temp_list[i]=list[i]; 	}quicksort(temp_list,disk_num,0,disk_num-1);int index=disk_num-1;int last=BEGIN_DISK;//寻找距离100最近的磁道号 for(int i=0;i<disk_num;i++){if(temp_list[i]>last){index=i;break;}}int fangxiang=1;//方向变量，1为磁道号增加方向，0为减小方向。第一次使从BEGIN_DISK号开始向增加方向扫描。 int flag[disk_num];//定义数组，标志磁道是否被访问过了 init(flag,disk_num); //初始化数组，置为-1，表示未被访问过 int n=disk_num;int result_index=0;while(n)//如果还存在没有访问过的磁道号 {	if(fangxiang){while(index<=disk_num-1&&flag[index]==-1){result_list[result_index]=temp_list[index];flag[index]=1;//标记已被访问过的磁道号 index++; result_index++;n--;//磁道号总体数目减1 }if(index==disk_num){fangxiang=0;//方向置为0 index--;//防止下一次访问越界 }}else{while(index>=0&&flag[index]==-1){result_list[result_index]=temp_list[index];flag[index]=1;//标记已被访问过的磁道号 index--;result_index++;n--;}index--;}	}   show_result(result_list,disk_num);printf("----------SCAN结束----------\n");
}

  SCAN算法我的实现思路是：首先将传入的list[]数组使用快速排序后保存至temp_list[]数组，之后通过方向变量fangxiang的值(1或0)控制磁头的移动方向，实现对磁道号序列的扫描。
  需要注意的是，需要另外开一个flag[]数组标志磁道号是否被访问过，如果下标为index的磁道号被访问过，需要另flag[index]的值为-1。
  快速排序void quicksort(int num[],int count,int left,int right)函数如下：

void quicksort(int num[],int count,int left,int right)
{if (left >= right){return ;}int key = num[left];int lp = left;           //左指针int rp = right;          //右指针while (lp < rp) {if (num[rp] < key) {int temp = num[rp];for (int i = rp - 1; i >= lp; i--) {num[i + 1] = num[i];}num[lp] = temp;lp ++;rp ++;}rp --;}quicksort(num,count,left,lp - 1);quicksort(num,count,rp + 1,right);
}

3.5 CSCAN 循环扫描算法

void CSCAN(int list[], int disk_num,int result_list[])
{printf("----------CSCAN----------\n");int temp_list[disk_num];init(temp_list, disk_num);for(int i=0;i<disk_num;i++){temp_list[i]=list[i]; 	}quicksort(temp_list,disk_num,0,disk_num-1);int index=disk_num-1;int last=BEGIN_DISK;//寻找距离100最近的磁道号 for(int i=0;i<disk_num;i++){if(temp_list[i]>last){index=i;break;}}int flag[disk_num];//定义数组，标志磁道是否被访问过了 init(flag,disk_num); //初始化数组，置为-1，表示未被访问过 int n=disk_num; int result_index=0;//存放结果数组里的下标 while(n)//如果还存在没有访问过的磁道号 {	while(index<=disk_num-1&&flag[index]==-1){result_list[result_index]=temp_list[index];flag[index]=1;//标记已被访问过的磁道号 index++;result_index++;n--;//磁道号总体数目减1 }index=0;}   show_result(result_list,disk_num);printf("----------CSCAN结束----------\n");
}

  CSCAN实现思路基本与SCAN类似，区别在于磁头的移动方向控制部分，当index>disk_num-1时，需要将index重新置为0。

四、验证本程序运行的正确性

注意：这一部分需要采用手动输入指定的磁道号序列来验证，而不能随机产生磁道号序列。

4.1 FCFS验证

教材FCFS运行结果
程序FCFS运行结果

4.2 STTF验证

教材SSTF运行结果
程序SSTF运行结果

4.3 SCAN验证

教材SCAN运行结果
程序SCAN运行结果

4.4 CSCAN验证


教材CSCAN运行结果

程序CSCAN运行结果

五、完整程序下载链接

添加本人qq2818120641购买

六、补充

  SCAN 和 C-SCAN 在磁盘的整个宽度内移动磁臂。实际上，这两种算法通常都不是按这种方式实施的。更常见的是，磁臂只需移到一个方向的最远请求为止。
  遵循这种模式的 SCAN 算法和 C-SCAN 算法分别称为 LOOK 和 C-LOOK 调度，因为它们在向特定方向移动时查看是否会有请求。

七、杂谈

  学习路上记录一下此时此刻的思路，作为来过此地的标记，以方便日后回忆。
程序如果有任何问题或者可以改进的地方欢迎在下方评论区留言。感谢看到这里的各位，谢谢你们的时间。

这篇关于【操作系统磁盘调度算法】OS实验C语言代码实现FCFS/SSTF/SCAN/CSCAN的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/599295。

相关文章

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

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

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

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

生产环境，由于硬盘空间不足，往往需要增加一块硬盘。刚加载的硬盘没有数据时，可以执行磁盘数据均衡命令。（Hadoop3.x新特性） plan后面带的节点的名字必须是已经存在的，并且是需要均衡的节点。 如果节点不存在，会报如下错误： 如果节点只有一个硬盘的话，不会创建均衡计划： （1）生成均衡计划 hdfs diskbalancer -plan hadoop102 （2）执行均衡计划 hd
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（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 （扩展欧几里得算法的简单应用）

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视频监控汇聚抖动检测算法优势

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

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

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

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2