当前位置：文档之家 › 操作系统磁盘调度SCAN算法

操作系统磁盘调度SCAN算法

  • 格式：docx
  • 大小：20.05 KB
  • 文档页数：9

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>typedefstruct_proc{char name[100]; /*定义进程名称*/int team; /*定义柱面号*/int ci; /*定义磁道面号*/int rec; /*定义记录号*/struct_proc *prior;struct_proc *next;}PRO;PRO *g_head = NULL, *g_curr = NULL, *local;int record = 0; //初始柱面号int yi = 1; //初始方向int rec0 = 0; //初始记录号void init(){PRO *p; /*初始化链表（初始I/O表）*/ g_head = (PRO*)malloc(sizeof(PRO));g_head->next = NULL;g_head->prior = NULL;p = (PRO*)malloc(sizeof(PRO));strcpy_s(p->name, "P1");p->team = 100;p->ci = 10;p->rec = 1;p->next = NULL;p->prior = g_head;g_head->next = p;g_curr = g_head->next;p = (PRO*)malloc(sizeof(PRO));strcpy_s(p->name, "P2");p->team = 50;p->ci = 10;p->rec = 5;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P3");p->team = 40;p->ci = 10;p->rec = 4;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P4");p->team = 60;p->ci = 20;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P5");p->team = 50;p->ci = 20;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P6");p->team = 60;p->ci = 20;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P7");p->team = 50;p->ci = 2;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P8");p->team = 50;p->ci = 5;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P9");p->team = 50;p->ci = 100;p->rec = 6;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = p;p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P10");p->team = 60;p->ci = 10;p->rec = 10;p->next = NULL;p->prior = g_curr;g_curr->next = p;local = (PRO*)malloc(sizeof(PRO)); /*选中进程*/strcpy_s(local->name, "P0");local->team = 50;local->ci = 50;local->rec = 50;local->next = NULL;local->prior = NULL;}void PrintInit() /*打印I/O表*/{PRO *t = g_head->next;printf("-------------------------------------\n");printf(" 请求I/O表\n");printf(" 进程名柱面号磁道号记录号\n");while (t != NULL){printf("%4s %8d %8d %5d\n", t->name, t->team, t->ci, t->rec);t = t->next;}}void acceptreq() /*接受请求函数*/{PRO *p;p = (PRO*)malloc(sizeof(PRO));printf("please input the information of the new process\n");printf("进程名:");scanf_s("%s", p->name,20);printf("柱面号(0-199):");scanf_s("%d", &p->team); /*输入请求进程信息*/ printf("磁道号(0-20):");scanf_s("%d", &p->ci);printf("记录号(0-7):");scanf_s("%d", &p->rec);getchar();g_curr = g_head; /*将此节点链入I/O请求表*/ while (g_curr->next != NULL)g_curr = g_curr->next;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr = g_head->next;PrintInit(); /*将新的I/O请求表输出*/}void SCAN() /*驱动调度函数*/{PRO *out = 0;int deng = 0;int deng1 = 0;int min = g_head->next->team;//大于里最小的int max = g_head->next->team;//小于里最大的for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (g_curr->team == record)//找到是否有同一个柱面号的进程，deng=1{min = g_curr->rec;out = g_curr;deng = 1;break;}}switch (deng){case 1://找出同一个柱面号里最小的记录号for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (g_curr->team == record&&abs(g_curr->rec - rec0) <= abs(min - rec0)){min = g_curr->rec;out = g_curr;}}break;case 0:switch (yi)//不属于同一个柱面号里。

分向里和向外方向{case 1://向外（大）方向for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (g_curr->team > record)//找到第一个大于它的柱面号的进程{min = g_curr->team;deng1 = 1;//存在大于的柱面号break;}}switch (deng1){case 1://存在for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (min >= g_curr->team&&g_curr->team>record)//找到大于它的柱面号的最小的柱面号{min = g_curr->team;out = g_curr;}}break;case 0://不存在yi = 0;//反方向,即向外（小）方向for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (max <= g_curr->team)//找柱面号比它小的第一个进程{min = g_curr->team;out = g_curr;}}break;}break;case 0:for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (g_curr->team < record)//找到第一个小于它的柱面号deng1=1{max = g_curr->team;deng1 = 1;break;}}switch (deng1){case 1:for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (max <= g_curr->team&&g_curr->team<record)//找到小于它的柱面号的最大的柱面号{max = g_curr->team;out = g_curr;}}break;case 0:yi = 1;//向反方向，即向内（大）方向for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next){if (min >= g_curr->team){min = g_curr->team;out = g_curr;}}break;}break;}break;}strcpy_s(local->name, out->name);local->team = out->team;local->ci = out->ci;local->rec = out->rec;printf("被选中进程:\n");printf(" 进程名柱面号磁道号记录号\n");printf("%4s %8d %8d %5d\n", out->name, out->team, out->ci, out->rec);switch (yi){case 1:printf("current direction is UP\n");printf("-------------------------------------\n");break;case 0:printf("current direction is DOWN\n");printf("-------------------------------------\n");break;}record = local->team;rec0 = local->rec;if (out->next == NULL) /*将选中的进程从I/O请求表中删除*/{out->prior->next = NULL;free(out);}else{out->prior->next = out->next;out->next->prior = out->prior;free(out);}}void acceptnum() /*通过输入0~1选择‘驱动调度’或是‘接受请求’*/{float num;char c = 'y';do{printf("please input a number between 0 and 1\n");printf("num<=0.5:接受请求 num>0.5:驱动调度\n");printf("num:");scanf_s("%f", &num);getchar();while((num<0 || num>1)) /*过滤不合法数据注意：本程序其他输入数据可能未过滤*/{printf("ERROR!!!! Input again please!\nnum:\n");scanf_s("%f", &num);getchar();}if (num>0.5) /*驱动调度*/{if (g_head->next == NULL)printf("请求I/O表 is empty!!!\n"); /*请求表为空无需调度*/else{printf("-------------------------------\n");printf("驱动调度\n");PrintInit();SCAN(); /*调用函数进行调度*/ }}else/*接受请求*/{printf("-------------------------------\n");printf("接受请求\n");PrintInit();acceptreq();}printf("是否继续(y/n):"); /*输入n离开本程序*/c = getchar();} while (c == 'y' || c == 'Y');}int main() /*主程序*/{init();PrintInit();acceptnum();return 0;}。

合集下载

磁盘scan算法

磁盘scan算法

磁盘scan算法磁盘扫描算法（Disk scan algorithm）是磁盘调度算法的一种，常用于磁盘调度器中，用于决定磁盘磁头移动的顺序。

磁盘扫描算法可以提高磁盘的访问效率，减少磁盘的寻道时间，提高磁盘I/O的吞吐量。

磁盘扫描算法的基本思想是将盘面划分为多个磁道，磁头从磁道的起始位置开始扫描，逐渐向磁道的末尾移动，然后返回起始位置，循环往复。

磁盘上的请求按磁道的顺序进行处理，以减少磁盘磁头的移动次数，提高访问效率。

磁盘扫描算法的实现可以通过以下步骤进行：1.获取当前磁头的位置和待处理的磁道请求队列。

2.将磁道请求队列按磁道号从小到大进行排序。

3.根据磁头当前位置，找到磁道请求队列中第一个磁道号大于等于当前位置的请求的索引，将这个索引作为起始索引。

4.从起始索引开始，按磁道号的递增顺序依次处理磁盘请求，直到处理完所有的请求。

5.处理完所有请求后，磁头返回起始位置，继续按磁道号的递增顺序处理剩下的请求。

6.重复步骤4和步骤5，直到处理完所有请求。

磁盘扫描算法的优点是可以提高磁盘访问的效率，降低磁盘寻道时间，特别适用于磁盘负载较高的情况。

它的缺点是对于位于起始位置两侧的请求会有较长的等待时间，可能造成较高的响应延迟。

磁盘扫描算法的应用范围广泛，例如在文件系统中用于文件存储和访问，数据库系统中用于数据的存取，以及操作系统中用于调度磁盘I/O操作等。

总之，磁盘扫描算法通过按磁道号的顺序处理磁盘请求，可以提高磁盘的访问效率，减少磁盘的寻道时间，是常用的磁盘调度算法之一、通过合理选取起始位置和磁道号的排序方式，可以进一步优化算法的性能。

磁盘扫描算法是研究磁盘调度和磁盘I/O优化的重要内容之一。

操作系统磁盘调度算法实验报告及代码

操作系统磁盘调度算法实验报告及代码

操作系统磁盘调度算法实验报告及代码一、实验目的通过实验掌握磁盘调度算法的实现过程，了解各种不同磁盘调度算法的特点和优缺点，并比较它们的性能差异。

二、实验原理磁盘调度是操作系统中的重要内容，其主要目的是提高磁盘的利用率和系统的响应速度。

常见的磁盘调度算法有：FCFS（先来先服务）、SSTF （最短寻道时间）、SCAN（扫描）、C-SCAN（循环扫描）等。

三、实验过程1.编写代码实现磁盘调度算法首先，我们需要定义一个磁盘请求队列，其中存放所有的IO请求。

然后，根据所选的磁盘调度算法，实现对磁盘请求队列的处理和IO请求的调度。

最后，展示运行结果。

以FCFS算法为例，伪代码如下所示：```diskQueue = new DiskQueue(; // 创建磁盘请求队列while (!diskQueue.isEmpty()request = diskQueue.dequeue(; // 取出队列头的IO请求//处理IO请求displayResult(; // 展示运行结果```2.运行实验并记录数据为了验证各种磁盘调度算法的性能差异，我们可以模拟不同的场景，例如，随机生成一批磁盘IO请求，并使用不同的磁盘调度算法进行处理。

记录每种算法的平均响应时间、平均等待时间等指标。

3.撰写实验报告根据实验数据和结果，撰写实验报告。

实验报告通常包括以下内容：引言、实验目的、实验原理、实验步骤、实验结果、实验分析、结论等。

四、实验结果与分析使用不同的磁盘调度算法对磁盘IO请求进行处理，得到不同的实验结果。

通过对比这些结果，我们可以看出不同算法对磁盘IO性能的影响。

例如，FCFS算法对于请求队列中的请求没有排序，可能会导致一些请求等待时间过长。

而SSTF算法通过选择离当前磁道最近的请求进行处理，能够减少平均寻道时间，提高磁盘性能。

五、实验总结通过本次实验，我们学习了操作系统中磁盘调度算法的原理和实现过程。

不同的磁盘调度算法具有不同的优缺点，我们需要根据实际情况选择合适的算法。

磁盘调度算法的模拟实现

磁盘调度算法的模拟实现

磁盘调度算法的模拟实现磁盘调度算法是指操作系统中负责管理物理磁盘的一种算法，其主要目的是优化磁盘访问，提高磁盘效率。

常见的磁盘调度算法有FCFS（先来先服务）、SSTF（最短寻道时间优先）、SCAN（扫描）、C-SCAN（循环扫描）等。

下面我将分别介绍这几种算法的模拟实现。

1.FCFS（先来先服务）算法模拟实现：首先，我们需要定义一个队列，用于存储用户请求的磁道号。

然后，将用户请求的磁道号加入队列中，按照先来先服务的原则进行服务，即按照队列中的请求顺序依次访问磁盘。

计算总体访问时间等信息，并输出结果。

2.SSTF（最短寻道时间优先）算法模拟实现：首先，我们需要定义一个队列，用于存储用户请求的磁道号。

然后，从当前磁头位置开始，找到与当前位置距离最近的请求磁道号，计算距离最小的请求所在的队列位置，并将该请求从队列中取出访问磁盘。

重复上述过程，直至队列为空。

计算总体访问时间等信息，并输出结果。

3.SCAN（扫描）算法模拟实现：首先，我们需要定义一个队列，用于存储用户请求的磁道号。

然后，将用户请求的磁道号加入队列中，并将队列按磁道号从小到大排序。

假设当前磁头位置为start，将磁头移动到队列中第一个比start大的磁道号，然后按照顺时针方向继续移动，直至访问队列中最大的磁道号。

然后，改变移动方向，回到队列中最小的磁道号为止。

计算总体访问时间等信息，并输出结果。

4.C-SCAN（循环扫描）算法模拟实现：首先，我们需要定义一个队列，用于存储用户请求的磁道号。

然后，将用户请求的磁道号加入队列中，并将队列按磁道号从小到大排序。

假设当前磁头位置为start，将磁头移动到队列中第一个比start大的磁道号，然后按照顺时针方向继续移动，直至访问队列中最大的磁道号，并将磁头移动到队列中最小的磁道号。

计算总体访问时间等信息，并输出结果。

以上是对于不同磁盘调度算法的简要模拟实现。

在实际应用中，还需要考虑更多的细节，如怎样处理新到的请求、队列的管理等。

操作系统实验磁盘调度扫描算法循环扫描算法

操作系统实验磁盘调度扫描算法循环扫描算法

学号P1514032 专业计算机科学与技术姓名实验日期2017.12.7教师签字成绩实验报告【实验名称】磁盘调度（二）【实验目的】磁盘调度中寻道时间直接影响到数据访问的快慢，处理好磁盘寻道时间是关键。

分别采用扫描策略、循环扫描策略处理。

【实验原理】1. 扫描算法（SCAN算法）SCAN算法，也就是很形象的电梯调度算法。

先按照一个方向(比如从外向内扫描)，扫描的过程中依次调度经过的磁道。

当扫描到最里层的一个磁道时反向扫描直至所有磁道都被调度。

2.循环扫描算法（CSCAN算法）CSCAN算法，循环扫描算法，它的思想是，访问完最里面一个要求服务的序列之后，从最外层的序号开始往里走。

也就是始终保持一个方向，故称为循环扫描算法。

【数据结构和符号说明】（1）数据结构和符号说明编译语言：C++数据结构：结构体数组符号定义：typedefstruct Track//磁道结构体{int id;//磁道序列int state=0;//是否访问过，未被访问置状态为0} Track;Track track[N];//最大磁道数为100Track track1[N];//复制的磁道数组用于输出int step[N];//移动距离int num,i,current_track,num1; //当前磁道即部分中间变量函数说明：void init()//初始化程序void input()//输入函数void sort1()//从小到大排序int abs(inta,int b)//相减的绝对值intfind_first_bignum()//寻找第一个最大值intfind_first_smallnum()//寻找第一个最小值void SCAN(intup_or_down)//扫描算法void CSCAN(intup_or_down)//循环扫描算法void output(Track a[])//输出函数void output_average_track()//输出平均寻道时间int show()//显示用户界面//返回值为输入的选择项流程图：SCAN算法：CSCAN算法（与SCAN算法基本类似）：代码：#include<stdio.h>#define N 100typedefstruct Track{int id;//磁道序列int state=0;//是否访问过，未被访问置状态为0 } Track;Track track[N];//最大磁道数为100Track track1[N];int step[N];//移动距离int num,i,current_track,num1;void init()//初始化程序{num=0;for (i=0; i<num; i++){track[i].state=-1;//id置为1track1[i].state=-1;step[i]=-1;//移动距离为-1}}void input()//输入函数{printf("输入当前磁道\n");scanf("%d",&current_track);num1=current_track;printf("输入要访问的磁道数目\n");scanf("%d",&num);printf("输入要访问磁道序列\n");for(i=0; i<num; i++)scanf("%d",&track[i].id);}void FCFS()//先来先服务{for(i=0; i<num; i++){if((current_track-track[i].id)<0)//求移动距离step[i]=track[i].id-current_track;elsestep[i]=current_track-track[i].id;//取绝对值 track[i].state=1;//状态置为1current_track=track[i].id;//更新当前磁道}}int abs(inta,int b)//相减的绝对值{return a-b>0?a-b:b-a;}intSerch_min_pos()//寻找到当前磁道最短的需求磁道{int min=45536;//最小距离标志intpos;for(inti=0; i<num; i++)if(track[i].state==1)continue;else if(min>abs(track[i].id,current_track))//寻找最小距离{min=abs(track[i].id,current_track);pos=i;}track[pos].state=1;return pos;//返回在数组中的位置}void SSTF()//最短寻道优先{for(i=0; i<num; i++)//计数器{track1[i]=track[Serch_min_pos()];//更新到要输出的数组中step[i]=abs(track1[i].id,current_track);//移动距离current_track= track1[i].id;//标志}}void output(Track a[])//输出函数{printf("\n\n <从%d号磁道开始>\n",num1);printf("==================================================\n");//排班printf("被访问的下一个磁道\t\t移动距离（磁道数）\n");for(i=0; i<num; i++)printf("\t%4d\t\t||\t%4d\n",a[i].id,step[i]);printf("==================================================\n");}void output_average_track()//输出平均寻道时间{double sum=0;//和for(i=0; i<num; i++)sum+=step[i];printf(" 平均寻道长度%3.2f\n\n\n",sum/num);//输出}int show()//显示用户界面{int choose;//选择printf("\n******************早期的磁盘调度算法******************\n"); printf("\t\t1、先来先服务(FCFS)\n");printf("\t\t2、最短寻道时间优先（SSTF)\n");printf("\t\t3、退出（EXIT）\n");scanf("%d",&choose);return choose;}int main(){do{init();switch(show())//返回值是选择{case 1://FCFSinput();FCFS();output(track);output_average_track();break;case 2://最短寻道input();SSTF();output(track1);output_average_track();break;case 3://退出return 0;default:break;}}while(1);return 0;}截图：主界面开始，输入选择先来先服务还是最短寻道优先，输入当前磁道，输入要访问的磁道，输入要访问的磁道序列。