【操作系统磁盘调度算法】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。

相关文章

Vue中动态权限到按钮的完整实现方案详解

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表（routes）1.2 修改角色与路由权限表（role_routes）二、后端接口设计
阅读更多...
C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)

《C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)》本文主要介绍了C#集成DeepSeek模型实现AI私有化的方法,包括搭建基础环境,如安装Ollama和下载DeepS... 目录前言搭建基础环境1、安装 Ollama2、下载 DeepSeek R1 模型客户端 ChatBo
阅读更多...
Qt实现发送HTTP请求的示例详解

Qt实现发送HTTP请求的示例详解

《Qt实现发送HTTP请求的示例详解》这篇文章主要为大家详细介绍了如何通过Qt实现发送HTTP请求,文中的示例代码讲解详细,具有一定的借鉴价值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、添加network模块2、包含改头文件3、创建网络访问管理器4、创建接口5、创建网络请求对象6、创建一个回复对
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
grom设置全局日志实现执行并打印sql语句

grom设置全局日志实现执行并打印sql语句

《grom设置全局日志实现执行并打印sql语句》本文主要介绍了grom设置全局日志实现执行并打印sql语句,包括设置日志级别、实现自定义Logger接口以及如何使用GORM的默认logger,通过这些... 目录gorm中的自定义日志gorm中日志的其他操作日志级别Debug自定义 Loggergorm中的
阅读更多...
Spring Boot整合消息队列RabbitMQ的实现示例

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring
阅读更多...
Gin框架中的GET和POST表单处理的实现

Gin框架中的GET和POST表单处理的实现

《Gin框架中的GET和POST表单处理的实现》Gin框架提供了简单而强大的机制来处理GET和POST表单提交的数据,通过c.Query、c.PostForm、c.Bind和c.Request.For... 目录一、GET表单处理二、POST表单处理1. 使用c.PostForm获取表单字段：2. 绑定到结
阅读更多...
springMVC返回Http响应的实现

springMVC返回Http响应的实现

《springMVC返回Http响应的实现》本文主要介绍了在SpringBoot中使用@Controller、@ResponseBody和@RestController注解进行HTTP响应返回的方法,... 目录一、返回页面二、@Controller和@ResponseBody与RestController
阅读更多...
nginx中重定向的实现

nginx中重定向的实现

《nginx中重定向的实现》本文主要介绍了Nginx中location匹配和rewrite重定向的规则与应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下... 目录一、location1、 location匹配2、 location匹配的分类2.1 精确匹配2
阅读更多...
Nginx之upstream被动式重试机制的实现

Nginx之upstream被动式重试机制的实现

《Nginx之upstream被动式重试机制的实现》本文主要介绍了Nginx之upstream被动式重试机制的实现,可以通过proxy_next_upstream来自定义配置,具有一定的参考价值,感兴... 目录默认错误选择定义错误指令配置proxy_next_upstreamproxy_next_upst
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2