第一篇：操作系统课程设计-磁盘调度算法
1.实验题目:
磁盘调度算法。
建立相应的数据结构；
在屏幕上显示磁盘请求的服务状况；
将一批磁盘请求的情况存磁盘文件，以后可以读出并重放； 计算磁头移动的总距离及平均移动距离； 支持算法：FIFO、SSTF、SCAN、CSCAN;
2.设计目的:
调度磁盘I/O请求服务，采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现，加深对算法的理解，同时通过用C++语言编写程序实现这些算法，并在windos平台上实现，更好的掌握操作系统的原理以及实现方法，提高综合运用专业课知识的能力。
3.任务及要求
3.1 设计任务
编程实现下述磁盘调度算法，并求出每种算法的平均寻道长度：
1、先来先服务算法（FCFS）
2、最短寻道时间算法（SSTF）
3、扫描算法（SCAN）
4、循环扫描算法（CSCAN）
3.2 设计要求
对用户指定的磁盘调度请求序列，基于以上四种算法，实现各自的调度顺序并输出，同时计算出各种算法下的平均寻道长度。
4.算法及数据结构
4.1算法的总体思想
queue[n] 为请求调度序列，diskrode为磁盘磁道数，headstarts为正在调度的磁道
①先来先服务算法（FCFS）按queue[n]数组的顺序进行磁盘调度，将前一个调度磁道与下一个调度磁道的差值累加起来，得到总的寻道长度，再除以n得到平均寻道长度。
②最短寻道时间优先算法（SSTF）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，通过循环语句找出离起始磁头最短的位置。
③扫描算法（SCAN）
将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，再在定位处反向遍历到另一端。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁
道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。
④循环扫描算法（CSCAN）将queue[n]进行由小到大的排序，首先定位当前调度磁headstarts在queue[n]的位置，然后在此位置按给定的方向遍历queue[n]，当道端点（queue[0]或queue[n-1]）时，反向到另一端点再以此方向进行遍历，直到queue[n]中所有都调度完。当调度磁道不在queue端点时，总的寻道长度为为前一个磁道与后一个磁道差值的累加，当到达端点且queue[n]未全调度时，总寻道长度加上端点值再加上磁盘磁道总长度，再加上下一个调度磁道的值，再按前面的算法进行，直到磁道全部都调度完毕，得到总的寻道长度，除以n得到平均寻道长度。
5、源代码：
#include 1、先来先服务算法（FCFS)**********”< cout<<“****** 2、最短寻道时间优先算法(SSTF)**********”< cout<<“****** 3、扫描算法(SCAN)**********”< cout<<“****** 4、循环扫描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //对当前正在执行的磁道号进行定位，返回磁道号小于当前磁道中最大的一个 int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是请求调度序列，n为其个数，diskroad为磁盘磁道数，headstarts为正在调度的磁道 { cout<<“************以下为FCFS调度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下为SSTF调度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN调度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN调度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示调度磁盘请求序列queue的长度，diskrode表示磁盘磁道的个数，headstarts表示目前正在调度的磁道； cout<<“请输入磁盘的总磁道数:”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序结束,谢谢使用！”< 沈阳理工大学课程设计专用纸 Noi 目 录 1 课程设计目的及要求……………………………………………………错误！未定义书签。2 相关知识…………………………………………………………………错误！未定义书签。3 题目分析…………………………………………………………………2 4 概要设计…………………………………………………………………2 4.1 先来先服务（FCFS）的设计思想……………………………….2 4.2 最短寻道时间优先调度（SSTF）的设计思想…………………..2 4.3 扫描算法（SCAN）的设计思想…………………………………2 4.4 循环扫描（CSCAN）的设计思想………………………………..2 5 代码及流程………………………………………………………………3 5.1 流程图……………………………………………………………...3 5.2 源代码……………………………………………………………...8 6 运行结果…………………………………………………………………16 7 设计心得…………………………………………………………………19 参考文献…………………………………………………………………………19 沈阳理工大学 沈阳理工大学课程设计专用纸 No1 1 课程设计目的及要求 设计目的：加深对操作系统原理的进一步认识，加强实践动手能力和程序开发能力的培养，提高分析问题解决问题的能力，培养合作精神，以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程，它不仅要求学生掌握操作系统的工作原理和理论知识，也要求学生的实际动手能力，以加深对所学习内容的理解，使学生熟练地掌握计算机的操作方法，使用各种软件工具，加强对课程内容的理解。这次课程设计，就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解。使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。 设计要求：编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度；要求设计主界面可以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN）相关知识 数据结构：数组 now:当前磁道号; array[]:放置磁道号的数组; void FCFS(int array[],int m)先来先服务算法(FCFS)void SSTF(int array[],int m)最短寻道时间优先算法(SSTF)void SCAN(int array[],int m)扫描算法(SCAN)void CSCAN(int array[],int m)循环扫描算法(CSCAN)磁盘调度：当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问（主要是寻道）时间最小。目前常用的磁盘调度算法有：1）闲来先服务2）最短寻道时间优先3）扫描算法4）循环扫描算法等 沈阳理工大学 沈阳理工大学课程设计专用纸 No2 3 题目分析 选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程 完成各分项功能。在算法的实现过程中，要求可决定变量应是动态可变的；同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟.各功能程序要求自行编写程序实现，不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法.最短寻道时间优先调度，循环（SCAN）调度算法。程序设计语言自选，最终以软件（含源代码以及执行程序）和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用。在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。概要设计 1.先来先服务（FCFS）的设计思想 即先来的请求先被响应。FCFS策略看起来似乎是相当“公平”的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。 2.最短寻道时间优先调度（SSTF）的设计思想 最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。 3.扫描算法（SCAN）的设计思想 扫描（SCAN）调度算法:该算法不仅考虑到欲访问 的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。 4.循环扫描（CSACN）的设计思想 循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。 沈阳理工大学 沈阳理工大学课程设计专用纸 No3 5 代码及流程 1.先来先服务（FCFS） 图 1—1 FCFS的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No4 2.最短寻道时间优先调度（SSTF） 图1—2 SSTF的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No5 3.扫描算法（SCAN） 图1—3 SCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No6 4.循环扫描（CSCAN） 图1—4 CSCAN的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No7 图1—5 主函数的流程图 沈阳理工大学 沈阳理工大学课程设计专用纸 No8 源代码： #include“stdio.h” #include“stdlib.h” //#include“iostream.h” #define maxsize 100 //定义最大数组域 //先来先服务调度算法 void FCFS(int array[],int m){ int sum=0,j,i;int avg;printf(“n FCFS调度结果: ”);for(i=0;i } avg=sum/(m-1);//计算平均寻道长度 printf(“n 移动的总道数： %d n”,sum);printf(“平均寻道长度： %d n”,avg);} //最短寻道时间优先调度算法 void SSTF(int array[],int m){ int temp;int k=1;int now,l,r;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No9 array[i]=array[j];array[j]=temp;} } } for(i=0;i for(i=m-1;i>=0;i--)//将数组磁道号从大到小输出 printf(“%d ”,array[i]);sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { for(i=0;i printf(“%d ”,array[l]);sum+=now-array[l];//计算移动距离 now=array[l];l=l-1;} else 沈阳理工大学 沈阳理工大学课程设计专用纸 No10 { printf(“%d ”,array[r]);sum+=array[r]-now;//计算移动距离 now=array[r];r=r+1;} } if(l=-1){ for(j=r;j printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } else { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//计算移动距离 } } avg=sum/m;printf(“n 移动的总道数： %d n”,sum);printf(“平均寻道长度： %d n”,avg);} //扫描算法 void SCAN(int array[],int m)//先要给出当前磁道号和移动臂的移动方向 { int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No11 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n SCAN调度结果: ”);for(i=m-1;i>=0;i--){ printf(“%d ”,array[i]);//将数组磁道号从大到小输出 } sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n SCAN调度结果: ”);for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No12 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=r;j //循环扫描算法 void CSCAN(int array[],int m){ int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈阳理工大学 沈阳理工大学课程设计专用纸 No13 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=now-array[0]+array[m-1];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“n CSCAN调度结果: ”);for(i=0;i printf(“%d ”,array[i]);//将磁道号从小到大输出 } sum=array[m-1]-now;//计算移动距离 } else { while(array[k] 沈阳理工大学 沈阳理工大学课程设计专用纸 No14 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=m-1;j>=r;j--){ printf(“%d ”,array[j]);} sum=2*(array[m-1]-array[0])-array[r]+now;//计算移动距离 }//磁道号减小方向 else { for(j=r;j // 操作界面 int main(){ int c;FILE *fp;//定义指针文件 int cidao[maxsize];//定义磁道号数组 int i=0,count;fp=fopen(“cidao.txt”,“r+”);//读取cidao.txt文件 if(fp==NULL)//判断文件是否存在 { printf(“n 请 先 设 置 磁 道!n”);exit(0);} while(!feof(fp))//如果磁道文件存在 沈阳理工大学 沈阳理工大学课程设计专用纸 No15 { fscanf(fp,“%d”,&cidao[i]);//调入磁道号 i++;} count=i-1;printf(“n-------------------n”);printf(“ 10-11OS课程设计--磁盘调度算法系统n”);printf(“ 计算机科学与技术二班n”);printf(“ 姓名：宋思扬n”);printf(“ 学号：0803050203n”);printf(“ 电话：************n”);printf(“ 2010年12月29日n”);printf(“n-------------------n”);printf(“n 磁道读取结果：n”);for(i=0;i 1、先来先服务算法（FCFS）n”);printf(“ 2、最短寻道时间优先算法（SSTF）n”);printf(“ 3、扫描算法（SCAN）n”);printf(“ 4、循环扫描算法（CSCAN）n”);printf(“ 5.退出n”);printf(“n”);printf(“请选择：”);scanf(“%d”,&c);if(c>5)break;switch(c)//算法选择 { case 1: FCFS(cidao,count);//先来先服务算法 printf(“n”);break;case 2: SSTF(cidao,count);//最短寻道时间优先算法 printf(“n”);break;case 3: 沈阳理工大学 沈阳理工大学课程设计专用纸 No16 SCAN(cidao,count);//扫描算法 printf(“n”);break;case 4: CSCAN(cidao,count);//循环扫描算法 printf(“n”);break;case 5: exit(0);} } return 0;} 6 运行结果 图2—1 运行界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No17 图2—2 运行FCFS的界面 图2—3 运行SSTF的界面 图2—4 运行SCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No18 图2—5 运行SCAN的界面 图2—6 运行CSCAN的界面 图2—7 运行CSCAN的界面 沈阳理工大学 沈阳理工大学课程设计专用纸 No19 运行结果： 四种磁盘调度运行结果正确，与预期的相符。设计心得 此次操作系统的课程设计，从理论到实践，在两个星期的日子里，可以说是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。 在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如：在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来又转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。 同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序编写不太会……通过这次课程设计之后，一定把以前所学过的知识重新温故。在此，也感谢在课程设计过程中帮我解惑的老师和同学。参考文献 [1] 《操作系统》 人民邮电出版社 宗大华 宗涛 陈吉人 编著 [2] 《C语言程序设计》 清华大学出版社 马秀丽 刘志妩 李筠 编著 [3] 《操作系统实验指导书》 沈阳理工大学 唐巍 菀勋 编著 沈阳理工大学 实验报告六磁盘调度算法 班级：软技2班学号：201467003084 姓名：刘道林 一． 实验内容： 熟悉磁盘的结构以及磁盘的驱动调度算法的模拟，编程实现简单常用的磁盘驱动调度算法先来先服务（FIFO）、电梯调度算法、最短寻找时间优先算法、扫描（双向扫描）算法、单向扫描（循环扫描）算法等。编程只需实现两个算法。 题目可 以选取教材或习题中的相关编程实例。 编程语言建议采用c/c++或Java。模拟程序鼓励采用随机数技术、动态空间分配技术，有条件 的最好能用图形界面展现甚至用动画模拟。 实验性质：验证型。 二． 实验目的和要求 1）掌握使用一门语言进行磁盘驱动调度算法的模拟； 2）编写程序将磁盘驱动调度算法的过程和结果能以 较简明直观的方式展现 出来。 三． 实验原理、方法和步骤 1.实验原理 磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。 常用的磁盘驱动调度算法有：最简单的磁盘驱动调度算法是先入先出（FIFO）法。这种算法的实质是，总是严格按时间顺序对磁盘请 求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移 动方向，效率有待提高。 最短寻找时间优先算法：总是优先处理最靠近的请求。该算法移动的柱面距离较小，但可能会经常改变 移动方向，并且可能会发生进程饥饿现象。 电梯调度：总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。 扫描（双向扫描）：总是从最外向最里进行扫描，然后在从最里向最外扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或 最里的请求时不会移动到最外或最里柱面，二扫描算法总是移到最外、最里柱面。两端的请求有优先服被务的迹象。 循环扫描（单 向扫描）：从最外向最里进行柱面请求处理，到最里柱面后，直接跳到最外柱面然后继续向里进行处理。该算法与扫描算法的区别是，回来过程不处理请求，基于这样的事实，因为里端刚被处理。 2.实验方法 1）使用流程图描述演示程序的设计思想； 2）选取c/c++、Java等计算机语言，编程调试，最终给出运行正确的程序。 四． 实验结果分析 能够将磁盘驱动调度算法在各种情况下都能得出正确的结论。对FIFO、最短寻找时间优先或电梯调度算法能够 在多次模拟数据下得出平均移动柱面数，并进行效率比较分析 五．源程序代码 #include char name[32]; /*定义进程名称*/ int team; /*定义柱面号*/ int ci; /*定义磁道面号*/ int rec; /*定义记录号*/ struct _proc *prior; struct _proc *next;} PROC; PROC *g_head=NULL,*g_curr=NULL,*local; int record=0; int yi=1;void init(){ PROC *p; 链表（初始I/O表）*/ g_head =(PROC*)malloc(sizeof(PROC)); g_head->next = NULL; g_head->prior = NULL; p =(PROC*)malloc(sizeof(PROC)); strcpy(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 =(PROC*)malloc(sizeof(PROC)); strcpy(p->name, “P2”); p->team=30; p->ci=5; p->rec=5; /*初始化 p->next = NULL; p->prior = g_curr; g_curr->next = p; g_curr=p; p =(PROC*)malloc(sizeof(PROC)); strcpy(p->name, “P3”); p->team=40; p->ci=2; p->rec=4; } void PrintInit() { p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=p;p =(PROC*)malloc(sizeof(PROC));strcpy(p->name, “P4”);p->team=85;p->ci=7;p->rec=3;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=p;p =(PROC*)malloc(sizeof(PROC));strcpy(p->name, “P5”);p->team=60;p->ci=8;p->rec=4;p->next = NULL;p->prior = g_curr;g_curr->next = p;g_curr=g_head->next;local =(PROC*)malloc(sizeof(PROC)); /*选中进程*/ strcpy(local->name, “P0”);local->team=0;local->ci=0;local->rec=0;local->next=NULL;local->prior=NULL; /*打印I/O表*/ PROC *t = g_head->next;printf(“------n”);printf(“ ---------I/O LIST---------n”);printf(“ process team ci rec n”);while(t!=NULL) { printf(“%4s %8d %8d %5dn”, t->name, t->team, t->ci, t->rec); t = t->next; } printf(“nnCurrent process is :n”); printf(“------------------------------nn”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, local->name, local->team, local->ci, local->rec); switch(yi) { case 1: { printf(“current direction is UPn”); break; } case 0: { printf(“current direction is downn”); break; } } } void acceptreq() /*接受请求函数*/ { PROC *p; p =(PROC*)malloc(sizeof(PROC)); printf(“please input the information of the new processnprocess-name:nprocess-teamnprocess-cinprocess-recn”); printf(“1.namen”); scanf(“%s”,p->name); printf(“2.team 0-199n”); scanf(“%d”,&p->team); /*输入请求进程信息*/ printf(“3.ci 0-19n”); scanf(“%d”,&p->ci); printf(“4.rec 0-7n”); scanf(“%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; printf(“NEW I/O LISTnn”); PrintInit(); /*将新的I/O请求表输出*/ } void qddd() /*驱动调度函数*/ { PROC *out; int min; int max=g_head->next->team; if(g_head->next==NULL); /*若已全部调度，则空操作*/ else { switch(yi) { case 1: { min=g_head->next->team; out=g_head->next; /*选出最小的team进程，模拟启动此进程*/ strcpy(local->name,out->name); local->team=out->team; local->ci=out->ci; local->rec=out->rec; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(g_curr->team > record) { min = g_curr->team; break; } } 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; strcpy(local->name,out->name); local->team=out->team;local->ci=out->ci;local->rec=out->rec; } } printf(“n-----------------------n”); printf(“the process choosed :n”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, out->name, out->team, out->ci,out->rec); (g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) (max if(max==record) yi=0; record=1000; break; break; }/*case 1*/ case /*case 1 的对称过程*/ { max=g_head->next->team; strcpy(local->name,out->name); local->team=out->team; record = local->team;printf(“%d”,record);for { if } { } 0: out=g_head->next; local->ci=out->ci; local->rec=out->rec; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(g_curr->team < record) { max = g_curr->team; break; } (g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(max<=g_curr->team&&g_curr->team { max=g_curr->team;out=g_curr; strcpy(local->name,out->name); local->team=out->team; local->ci=out->ci;local->rec=out->rec; } } printf(“n-----------------------n”); printf(“the process choosed :n”); printf(“ process team ci rec n”); printf(“%4s %8d %8d %5dn”, out->name, out->team, out->ci,out->rec); } for min=g_head->next->team; for(g_curr=g_head->next;g_curr!=NULL;g_curr=g_curr->next) { if(min>g_curr->team)min=g_curr->team; } record = local->team; if(min==record) { yi=1;record=0; break; } break; } default : return-1; }/*switch*/ 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); } }/*else*/ } void acceptnum() /*通过输入0~1选择‘驱动调度’或是‘接受请求’*/ { float num; char c; while(1) { printf(“---------------n”); printf(“please input a number between 0 and 1nnum<=0.5:accept requestnnum>0.5:qudong diaodunnnum==2:I/O LISTnnnum=?n”); scanf(“%f”,&num); getchar(); while((num<0||num>1)&&num!=2) /*过滤不合法数据 注意：本程序其他输入数据可能未过滤*/ { printf(“number ERROR!Input again please!nnum=?n ”); scanf(“%f”,&num); getchar(); } if(num>0.5&&num!=2) /*驱动调度*/ { if(g_head->next==NULL) { printf(“nn”); printf(“---------------------n”); printf(“I/O list is empty！!n”); /*请求表为空 无需调度*/ } else { printf(“qudong diaodun”); qddd(); /*调用函数进行调度*/ } } else if(num<=0.5) /*接受请求*/ { printf(“accept requestnn”); acceptreq(); } else if(num==2) /*通过输入2显示当前请求I/O表*/ { printf(“I/O LIST;”); printf(“-------------------n”); PrintInit(); printf(“n”); printf(“-----------------------n”); printf(“choose 'n' to quit else to continuen”); if(strcmp(c=getchar(),'n')==0||strcmp(c=getchar(),'N')==0) clrscr(); printf(“nnnnnn”); printf(“thank you for testing my program!n”); printf(“ ---by 01n”); sleep(2); printf(“nnBYEbye！”); sleep(2); return-1; else { clrscr(); } /*输入n离开本程序*/ { } } } } main() /*主程序*/ { init(); PrintInit(); acceptnum();} 《计算机操作系统》 学号：班级：软技姓名：张靖伟 课 程 设 计 报 告 4班 1367003270 目录 实验：进程调度算法——时间片轮转算法 2 实验：银行家算法3 实验：分区分配算法——4 实验：页面置换算法——5 实验：磁盘调度算法—— BF和FF FIFO和LRU SCAN和SSTF 1实验：进程调度算法——时间片轮转算法 1.实验设计说明 用时间片轮转算法模拟单处理机调度。 （1）建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。 进程状态分为就绪（R）和删除（C）。 （2）为每个进程任意确定一个要求运行时间和到达时间。 （3）按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。（4）执行处理机调度时，开始选择对首的第一个进程运行。（5）执行： a)输出当前运行进程的名字； b)运行时间减去时间片的大小。 （6）进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。 （7）若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。 2.实验代码 /*****************时间片轮转调度算法*******************/ #include char pname[N];int runtime;/*进程名*/ /*服务时间*/ int arrivetime;/*到达时间*/ char state;/*进程状态*/ struct pcb*next;/*连接指针*/ }PCB;typedef struct back_team/*后备队列定义*/ { PCB*first,*tail;}BACK_TEAM;typedef struct pre_team/*就绪队列定义*/ { PCB*first,*tail;}PRE_TEAM;PCB*creat()/*创建PCB*/ { char s[N];printf(“请输入进程名：n”);scanf(“%s”,s);printf(“请输入进程服务时间(/秒)：n”);int t;scanf(“%d”,&t);PCB*p=(PCB*)malloc(sizeof(PCB));strcpy(p->pname,s);p->runtime=t;printf(“请输入进程到达时间(/秒)：n”);scanf(“%d”,&t);p->arrivetime=t;p->state='R';p->next=NULL;getchar();return p;} PCB*copy(PCB*p)/*复制一个进程*/ { } PCB*getnext(PCB*p,BACK_TEAM*head)/*得到队列中下一个进程*/ { } void del(BACK_TEAM*head,PRE_TEAM*S)/*释放申请的空间*/ { PCB*p=head->first->next;while(p){ free(head->first);head->first=p;PCB*s=head->first;if(!p)return NULL;if(!p)return NULL;PCB*s=(PCB*)malloc(sizeof(PCB));strcpy(s->pname,p->pname);s->next=NULL;s->arrivetime=p->arrivetime;s->runtime=p->runtime;s->state=p->state;return s;while(strcmp(s->pname,p->pname))s=s->next;return s->next; } } p=p->next;head->first=head->tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*创建后备队列*/ { } bool recognize(PRE_TEAM*s1)/*判断运行是否结束*/ { if(!s1||!s1->first)return false;PCB*p=creat();if(!head->first)else head->tail->next=p;head->first=p;head->tail=p;return head;if(s1->first==s1->tail) if(s1->first->state!='C')else return false;return true;PCB*test=s1->first;while(test!=s1->tail&&(test->state!='C'))test=test->next;if(test==s1->tail) } return true;else return false;PCB*run(PRE_TEAM*s)/*在CPU中运行*/ { if(!s->first){ } printf(“%dt%st”,time,s->first);s->first->runtime--;time++;if(s->first->runtime<=0){ } PCB*p=s->first;s->first->state='C';printf(“%cn”,s->first->state);s->first=p->next;free(p);if(!s->first){ } goto next;s->tail=NULL;spe=false;return NULL;spe=false;return NULL;printf(“%cn”,s->first->state);next:PCB*head=s->first; } int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*创建就绪队列*/ { int i=0;if(!head2->first) if(HEAD){ } if(c){ } head2->first=head2->tail=HEAD;return 1;head2->first=c;c->next=HEAD;head2->tail=HEAD;return 1;s->first=head->next;if(!s->first){ } head->next=NULL;return head;s->tail=NULL;spe=true;if(head2->first==head2->tail){ } else { } if(*test){ } if(c){ } head2->tail->next=c;head2->tail=c;if(head2->first->arrivetime!=time)for(i=0;i } if(c->arrivetime!=time){ } head2->tail->next=c;head2->tail=c;time++;return 1;if(HEAD){ head2->tail->next=HEAD; } } head2->tail=HEAD;return 1;int main(void){ BACK_TEAM*head1=(BACK_TEAM*)malloc(sizeof(BACK_TEAM));head1->first=head1->tail=NULL;PRE_TEAM *head2=(PRE_TEAM*)malloc(sizeof(PRE_TEAM));head2->first=head2->tail=NULL;char ask;int num=0;bool test=true;do{ printf(“要创建进程吗(y/n):”);if((ask=getchar())=='y'||ask=='Y'){ } else if(ask=='n'||ask=='N')else return 1;break;head1=creatbt(head1);num++;}while(1);PCB*p=copy(head1->first);PCB*HEAD=NULL;head2->first=head2->tail=copy(head1->first);printf(“时刻t进程名t状态n”); } while(spe||recognize(head2)){ } del(head1,head2);return 1;CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1));3.实验结果 和不马上运行: 当有两个进程的时候 当有多个进程的时候： 4.实验结果分析 RR算法：每次调度时，把CPU分配给队首进程，并且令其执行一个时间片，时间片的大小从几个ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便依据此信号来停止该进程的执行；并且把它送往就绪队列的队尾；然后，再把处理剂分配给就绪队列中的新队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内相应所有用户的请求.2实验：银行家算法 1.实验设计说明 1.该算法通过建立几个简单的二维数组Available,Max,Allocation,Need简单的模拟银行家算法和安全性算法，每个二维数组默认[][0]为A资源，[][1]为B资源，[][2]为C资源,默认有5个进程 2.程序首先要输入各个进程的三种资源的情况，包括每个进程最大的需求量，已经分配的资源量和现在还需要的资源量，以及系统现在剩余的资源量。3.程序会判断输入的信息是否在程序的规定范围内，正确才运行。 4．在执行安全算法开始时，Work∶=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false;当有足够资源分配给进程时，再令Finish［i］∶=true 5.从进程集合中找到一个能满足下述条件的进程： Finish［i］=false;并且 Need［i,j］≤Work［j］； 若找到，执行6，否则，执行7。 6.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;然后继续执行5。 7.如果所有进程的Finish［i］=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 2.实验代码 #include return false;printf(“p%d可以运行n”,p);Work[0]+=Allocation[p][0];Work[1]+=Allocation[p][1];Work[2]+=Allocation[p][2];Finish[p]=1;while(num<=25){ if(!Finish[i]&&(Need[i][0]<=Work[0])&&(Need[i][1]<=Work[1])&&(Need[i][2]<=Work[2])) { printf(“p%d可以运行n”,i); Work[0]+=Allocation[i][0]; Work[1]+=Allocation[i][1]; Work[2]+=Allocation[i][2]; Finish[i]=1; } num++; i=(i+1)%5; if(i==p) i++;} for(m=0;m<5;m++) if(Finish[m]==0) break;if(m==5) return true;else { printf(“系统处于不安全状态!n”); return false;} } void Banker(int p,int i,int j,int k){ int able[3]={Available[0],Available[1],Available[2]};int need[3]={Need[p][0],Need[p][1],Need[p][2]};int allocation[3]={Allocation[p][0],Allocation[p][1],Allocation[p][2]};if(i<=Need[p][0]&&j<=Need[p][1]&&k<=Need[p][2]) if(i<=Available[0]&&j<=Available[1]&&k<=Available[2]) { Available[0]-=i; Available[1]-=j; Available[2]-=k; Allocation[p][0]+=i; Allocation[p][1]+=j; Allocation[p][2]+=k; Need[p][0]-=i; Need[p][1]-=j; Need[p][2]-=k; if(!Safe(p)) { Available[0]=able[0],Available[1]=able[1],Available[2]=able[2]; Need[p][0]=need[0],Need[p][1]=need[1],Need[p][2]=need[2]; Allocation[p][0]=allocation[0],Allocation[p][1]=allocation[1],Allocation[p][2]=allocation[2]; printf(“系统可能发生死锁!n”); } } else printf(“等待!系统资源不足!n”);else printf(“错误!申请的资源错误!n”);} int main(void){ int i,j,k=0,p;printf(“请输入进程的三种资源的情况max{a,b,c} allocation{a,b,c} need{a,b,c}:n”);for(i=0;i<5;i++){ for(j=0;j<3;j++) scanf(“%d”,&Max[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Allocation[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Need[i][j]);} printf(“请输入Available{a,b,c}情况:”);for(i=0;i<3;i++) scanf(“%d”,&Available[i]);printf(“MaxtAllotNeedtAvain”);for(i=0;i<5;i++){ for(j=0;j<3;j++) printf(“%d ”,Max[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Allocation[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Need[i][j]); printf(“t”); if(k!=4) printf(“n”); k++;} for(i=0;i<3;i++)printf(“%d ”,Available[i]);printf(“n请输入要申请的进程和资源<0~4>:”);scanf(“%d %d %d %d”,&p,&i,&j,&k);if(p>=0&&p<=4)Banker(p,i,j,k);else printf(“没有此进程!”);return 1;} 3.实验结果 4.实验结果分析 这个实验只是简单的演示了进程申请资源之后的进程运行的其中一个运行序列，因为这个算法课本上已经有详细的解说，所以这个程序并没有把算法的过程展现出来，只展现了进程的运行序列结果，另外，如果申请错误的话程序会有不同的结果 有时会发生死锁 实验：分区分配算法——BF和FF 1.实验设计说明 1.这个算法模拟的是对内存空间的管理，这个程序用了一个简单的二维数组模拟分区表。2.程序首先要输入固定的五个分区的大小和始址，其次要输入作业的大小和实现的算法，由于这个程序把FF和BF放到一个程序中，便于比较两个算法。 首次适应算法FF(First Fit)把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表 最佳适应算法BF（Best Fit） 首先把分区表按空间大小从小到大排序。然后把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表 2.实验代码 #include int i,j;for(j=0;j<3;j++) for(i=0;i<5;i++) if(ta[i][1]>=job[j]){ } ta[i][1]-=job[j];ta[i][2]+=job[j];break;if(i==5)printf(“内存不足!请等待!n”); } printf(“空闲区t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,ta[j][i]);printf(“n”);void BestFit(int job[3]){ int j1,temp1,temp2,temp3,i,j;for(j1=0;j1<3;j1++){ for(i=0;i<5;i++) for(j=0;j<4;j++) if(table[j][1]>table[j+1][1]){ temp1=table[j][0];temp2=table[j][1];temp3=table[j][2]; table[j][0]=table[j+1][0];table[j][1]=table[j+1][1];table[j][2]=table[j+1][2]; } table[j+1][0]=temp1;table[j+1][1]=temp2;table[j+1][2]=temp3; } if(i==5)printf(“内存不足!请等待!n”);printf(“空闲区t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,table[j][i]); } for(i=0;i<5;i++) if(table[i][1]>=job[j1]){ } table[i][1]-=job[j1];table[i][2]+=job[j1];break;printf(“n”);void main(){ int table1[5][3],job[3],j,i;printf(“请输入5个空分区的大小和始址：”);for(i=0;i<5;i++){ } for(j=0;j<5;j++){ } printf(“请输入3个要运行作业的大小：”);for(i=0;i<3;i++)scanf(“%d”,&job[i]);for(i=0;i<3;i++)printf(“%dt”,table[j][i]);table[i][0]=i+1;table1[i][0]=i+1;for(j=1;j<3;j++){ } scanf(“%d”,&table[i][j]);table1[i][j]=table[i][j];printf(“n”);printf(“请输入要实现的算法1(FF)2(BF):”); } char c;scanf(“%d”,&i);getchar();if(i==1){ } else if(i==2){ } BestFit(job);printf(“还要实现FF吗(y/n)”);if((c=getchar())=='y')FirstFit(job,table1);FirstFit(job,table1);printf(“还要实现BF吗(y/n)”);if((c=getchar())=='y')BestFit(job);3.实验结果 4.实验结果分析 首先输入分区表的分区情况，然后输入运行作业的大小，选择要实现的算法。第一个作业是96，所以找到第四个分区，第四个分区变为122，316，接着到第二个作业20，然后把第一个分区分给第二个作业，则第一个分区信息变为122，316，到第三个作业时，由于内存表中没有比第三个请求的分区还大的分区，所以会提示内存不足； 然后到BF算法，因为是按空间大小排序的，所以第一个作业96被分配给了已经排好序的内存为96的第五个分区，第二个作业被分配给大小为36的分区，第三个作业被分配给内存大小为218的分区，然后又对剩余空间再次排队，用来给下一批作业分配。实验：页面置换算法——FIFO和LRU 1实验设计说明 程序设置了两个结构体,freeBlock和jobQueue,其中freeBlock代表物理块,初次创建物理块时,物理块的计时器time=0,还有代表作业的index=-1;物理块有添加和删除的功能，每一次添加或删除都要初始化物理块。并且可以重复添加和删除，这样可以很好的测试算法的性能。2.算法设计的思想是：进入物理块时间越长的则物理块的计时器数值越大，如果物理块中有要访问的页面，则那个含页面的物理块的计数器变成1；并且物理块要满才会发生置换，于是设置了物理块计数器Time； 2.实验代码 #include jobQueue*job=(jobQueue*)malloc(sizeof(jobQueue));job->index=num;job->next=NULL;if(!head){ jobQueue*j=head;while(j->next)j=j->next;j->next=job;head=job;else } } return head;freeBlock*creat(freeBlock*head){ } freeBlock*inse(freeBlock*head){ } freeBlock*dele(freeBlock*head){ freeBlock*test=head;while(test){ } freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=head;head=free;return head;test->index=-1;test->time=0;test=test->next;freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=NULL;if(head)free->next=head;head=free;return head; } freeBlock*test=head;while(test){ } freeBlock*f=head;head=f->next;free(f);return head;test->index=-1;test->time=0;test=test->next;bool check(freeBlock*free,int j){ } void LRU(freeBlock*free,jobQueue*job){ int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ freeBlock*f=free;while(f){ } return false;if(f->index==j)return true;f=f->next; } size++;ftest=ftest->next;printf(“LRU置换页面为：”);while(jtest){ ftest=free;while(ftest){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ if(ftest->index==jtest->index){ } ftest->time++;if(Time } } } } time=0;Time=0;break;if(ftest->time==Time){ } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void FIFU(freeBlock*free,jobQueue*job){ int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ } size++;ftest=ftest->next; printf(“FIFU置换页面为：”);while(jtest){ ftest=free;while(ftest){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ } if(ftest->time==Time)time=0;Time=0;break;if(ftest->index==-1){ } ftest->time++;if(Time } } } { } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void main(){ int num,ch,p;freeBlock*block=NULL;jobQueue*job=NULL;printf(“请输入物理块数目：”);scanf(“%d”,&p);for(int i=0;i } job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true){ printf(“增加物理块（1）减少物理块（2）,否则按任意键scanf(”%d“,&num);if(num==1){ } else if(num==2){ printf(”要减少几块：“);scanf(”%d“,&ch);if(ch>=p){ } for(i=0;i } } } FIFU(block,job);LRU(block,job);else ；break;3.实验结果 4.实验结果分析 程序开始要输入物理块数目和作业个数,然后再输入作业.在测试后可以随意添加或删除物理块来测试算法的性能。实验：磁盘调度算法——SCAN和SSTF 1.实验设计说明 算法定义了一个双向链表，利用双向链表可以很好的进行方向的转换，且双向链表的中有代表磁盘号的标识符index；两个算法均采用访问完一个磁盘序列时删除该序列，其中scan算法实现时有点麻烦，首先要找到当前磁盘号序列的Max最大值和最小值Min及指向他们的指针pmax，pmin，另外还要找到当前磁头的相邻的两个访问序列信息psmax，psmin；还有一个重要的标志，那就是访问的方向test；当遇到最大值或最小值时，便会反置test的值，也就是访问的方向 2.实验代码 #include printf(“请输入磁道队列以-1结束！n”);int ch;memory*head=NULL,*tail,*p;scanf(“%d”,&ch);while(ch!=-1){ p=(memory*)malloc(sizeof(memory));p->index=ch;p->left=p->right=NULL; } } if(!head)head=p;else { } tail=p;scanf(“%d”,&ch);tail->right=p;p->left=tail;return head;void SSTF(memory*head,int index){ int index1=index,num;memory*p1=head,*p,*p2=NULL;while(true){ num=abs(p1->index-index1);p=p1;while(p){ } if((abs(p->index-index1))<=num){ } p=p->right;num=abs(p->index-index1);if(p!=p1)p2=p;p=p1->right;if(p2){ } else { printf(“%d ”,p1->index);index1=p2->index;printf(“%d ”,p2->index);p2->left->right=p2->right;if(p2->right)p2->right->left=p2->left;free(p2);p2=NULL; } } } index1=p1->index;if(!p){ } else { } p=p1;p1=p1->right;free(p);continue;free(p1);break;void SCAN(memory*head,int index){ int index1=index,num,test,max=0,min=199,Max,Min;printf(“请输入磁头查询方向<0正向><1负向>!n”);scanf(“%d”,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL; while(p1){ } p1=head;while(p1){ if(!test){ if(!test){ } else { } p1=p1->right;pmin=p1;if(p1->index<=min)Min=min=p1->index;pmax=p1;if(p1->index>=max)Max=max=p1->index; } } pmin=p1;if(p1->index<=min)Min=min=p1->index; else { } p1=p1->right;pmax=p1;if(p1->index>=max)Max=max=p1->index;p1=head;while(true){ num=abs(p1->index-index1);p=p1;while(p){ if(!test){ if(p->index>=index1&&p->index<=max) } } if((abs(p->index-index1))<=num){ } psmin=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;else { } p=p->right;if(p->index<=index1&&p->index>=min) if(abs(p->index-index1)<=num){ } psmax=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;if(p2) { if(!test){ } else { index1=psmax->index;p=psmax;if(index1==Min){ } test=0;Max=Min=-1;p1=pmin;index1=psmin->index;p=psmin;if(index1==Max){ } test=1;Min=Max=-1;p1=pmax; } printf(“%d ”,index1);if(!test){ } else { if(psmax)if(psmin){ } else { } psmax->right->left=psmax->left;if(psmax->left) psmax->left->right=psmax->right;psmin->left->right=psmin->right;if(psmin->right) psmin->right->left=psmin->left;free(psmin);free(psmax); } } { } else { } psmin->right->left=psmin->left;if(psmin->left) psmin->left->right=psmin->right;psmax->left->right=psmax->right;if(psmax->right) psmax->right->left=psmax->left;free(psmax);free(psmin);else { if(!test){ if(p1->index==Max){ test=1; } } Min=Max=-1;else { } if(psmax){ } else { } printf(“%d ”,index1);index1=psmin->index;p=psmin;index1=psmax->index;p=psmax;if(p1->index==Min){ } test=0;Max=Min=-1; } } } if(p->left&&!p->right){ } else if(p->right&&!p->left){ } else if(!p->right&&!p->left){ } free(p);free(p);break;p1=p->right;p1->left=NULL;p1=p->left;p1->right=NULL;p2=psmax=psmin=NULL;void main(){ int p,t;memory*head=creat();printf(“请输入磁头当前的位置(0-199)”);scanf(“%d”,&p);printf(“要进行的算法：<0:SCAN><1:SSTF>”);scanf(“%d”,&t);if(!t)SCAN(head,p);else SSTF(head,p);} 3.实验结果 4.实验结果分析 输入要访问的磁盘号，然后选择要实现的算法就可以看到结果，当选0（正向）的时候由于当前的磁头在143处，所以要访问的磁盘号就必须大于143，当最大的磁盘号访问完时，就转向小于143的磁盘开始由大向小访问，选1的话则相反。最短寻道时间算法是从整个队列中选择距离磁头最近的访问，算法的实现运用了绝对值的概念 《操作系统》课程设计报告 课题： 银行家算法 专业 计算机科学与技术 学生姓名 班级 计算机 学号 指导教师 信息工程学院 一、实验要求和实验目的实验目的：本课程设计是学生学习完《操作系统原理》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 实验要求：从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：两人一组，每组从所给题目中任选一个（如自拟题目，需经指导教师同意），每个学生必须独立完成课程设计，不能相互抄袭，同组者文档不能相同；设计完成后，将所完成的工作交由指导教师检查；要求写出一份详细的设计报告。 二、设计内容： 课题一、编制银行家算法通用程序，并检测所给状态的系统安全性。 1）银行家算法中的数据结构： 可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj 类资源K个。 最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。 1.分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资料当前已分配给没一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 上述三个矩阵存在如下关系： Need[i,j]= Max[i，j]- Allocation[i，j] 2）银行家算法 设Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Request[i，j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 三、设计思路 设计思路A、设计进程对各在资源最大申请表示及初值确定。B、设定系统提供资源初始状态。C、设定每次某个进程对各类资源的申请表示。D、编制程序，依据银行家算法，决定其申请是否得到满足。 四、详细设计 1、初始化：由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。 2、银行家算法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。 银行家算法的数据结构 假设有M个进程N类资源，则有如下数据结构: #define W #define R int M ; //总进程数 int N ; //资源种类 int ALL_RESOURCE[W]; //各种资源的数目总和 int MAX[W][R]; //M个进程对N类资源最大资源需求量 int AVAILABLE[R]; //系统可用资源数 int ALLOCATION[W][R]; //M个进程已经得到N类资源的资源量 int NEED[W][R]; //M个进程还需要N类资源的资源量 int Request[R]; //请求资源个数 3.“安全性检测“算法 1)先定义两个变量,用来表示推算过程的数据.F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.J[n]=False表示推算过程中各进程是否假设“已完成“ 系统试探分配资源，修改相关数据： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i]; 4、安全性检查算法 1)设置两个工作向量Work=AVAILABLE;FINISH 2)从进程集合中找到一个满足下述条件的进程，FINISH==false; NEED<=Work; 如找到，执行(3)；否则，执行(4) 3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 Work+=ALLOCATION; Finish=true; GOTO 4)如所有的进程Finish= true，则表示安全；否则系统不安全。 安全状态: 在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j 最大需求 尚需 P1 P2 P3 4 2 在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.银行家算法的数据结构.五、代码清单 #include #include #include #include #include #include const int MAX_P=20; const int MAXA=10; //定义A类资源的数量 const int MAXB=5; const int MAXC=7; typedef struct node{ int a; int b; int c; int remain_a; int remain_b; int remain_c; }bank; typedef struct node1{ char name[20]; int a; int b; int c; int need_a; int need_b; int need_c; }process; bank banker; process processes[MAX_P]; int quantity; //初始化函数 void initial() { int i; banker.a=MAXA; banker.b=MAXB; banker.c=MAXC; banker.remain_a=MAXA; banker.remain_b=MAXB; banker.remain_c=MAXC; for(i=0;i strcpy(processes[i].name,““); processes[i].a=0; processes[i].b=0; processes[i].c=0; processes[i].need_a=0; processes[i].need_b=0; processes[i].need_c=0; } } //新加作业 void add() { char name[20]; int flag=0; int t; int need_a,need_b,need_c; int i; cout< cout<<“新加作业“< cout<<“请输入新加作业名:“; cin>>name; for(i=0;i if(!strcmp(processes[i].name,name)){ flag=1; break; } } if(flag){ cout<<“错误,作业已存在“< } else{ cout<<“本作业所需A类资源:“; cin>>need_a; cout<<“本作业所需B类资源:“; cin>>need_b; cout<<“本作业所需C类资源:“; cin>>need_c; t=1; cout< if(need_a>banker.remain_a){ cout<<“错误,所需A类资源大于银行家所剩A类资源“< t=0; } if(need_b>banker.remain_b){ cout<<“错误,所需B类资源大于银行家所剩B类资源“< t=0; } if(need_c>banker.remain_c){ cout<<“错误,所需C类资源大于银行家所剩C类资源“< t=0; } if(t){ strcpy(processes[quantity].name,name); processes[quantity].need_a=need_a; processes[quantity].need_b=need_b; processes[quantity].need_c=need_c; quantity++; cout<<“新加作业成功“< } else{ cout<<“新加作业失败“< } } } //为作业申请资源 void bid() { char name[20]; int i,p; int a,b,c; int flag; cout< cout<<“要申请资源的作业名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ cout<<“该作业要申请A类资源数量:“; cin>>a; cout<<“该作业要申请B类资源数量:“; cin>>b; cout<<“该作业要申请C类资源数量:“; cin>>c; flag=1; if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){ cout<<“错误,所申请A类资源大于银行家所剩A类资源或该进程还需数量“< flag=0; } if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){ cout<<“错误,所申请B类资源大于银行家所剩B类资源或该进程还需数量“< flag=0; } if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){ cout<<“错误,所申请C类资源大于银行家所剩C类资源或该进程还需数量“< flag=0; } if(flag){ banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processes[p].a+=a; processes[p].b+=b; processes[p].c+=c; cout<<“为作业申请资源成功“< } else{ cout<<“为作业申请资源失败“< } } else{ cout<<“该作业不存在“< } } //撤消作业 void finished() { char name[20]; int i,p; cout< cout<<“要撤消作业名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ banker.remain_a+=processes[p].a; banker.remain_b+=processes[p].b; banker.remain_c+=processes[p].c; for(i=p;i processes[i]=processes[i+1]; } strcpy(processes[quantity-1].name,““); processes[quantity-1].a=0; processes[quantity-1].b=0; processes[quantity-1].c=0; processes[quantity-1].need_a=0; processes[quantity-1].need_b=0; processes[quantity-1].need_c=0; quantity--; cout<<“撤消作业成功“< } else{ cout<<“撤消作业失败“< } } //查看资源情况 void view() { int i; cout< cout<<“银行家所剩资源(剩余资源/总共资源)“< cout<<“A类:“< cout<<“ B类:“< cout<<“ C类:“< cout< if(quantity>0){ for(i=0;i cout<<“作业名:“< cout<<“A类:“< cout<<“ B类:“< cout<<“ C类:“< cout< } } else{ cout<<“当前没有作业“< } } //显示版权信息函数 void version() { cout< cout<<“ 银行家算法 “< cout< } void main() { int chioce; int flag=1; initial(); version(); while(flag){ cout<<“1.新加作业 2.为作业申请资源 3.撤消作业“< cout<<“4.查看资源情况 0.退出系统“< cout<<“请选择:“; cin>>chioce; switch(chioce){ case 1: add(); break; case 2: bid(); break; case 3: finished(); break; case 4: view(); break; case 0: flag=0; break; default: cout<<“选择错误“< } } } 六、使用说明 运行环境C-FREE4.0，新建任务。将编制好的代码输入此运行环境中。 按F5：出现如上图所示窗口。按照提示，新建一个作业：wujun。为作业分配资源，A：3；B：4；C：5。输入2，为作业分配资源。三种资源的数量分配分别为:A:3;B:5;C:4。输入4，查看资源情况。出现出错提示，所申请的B类资源超过银行家所剩B类资源或作业申请资源失败。输入0，退出系统。 重新加入一个作业：wujun1.并为作业分配资源分别为A:3;B:3;C:3，为该作业分配资源A:3;B:2;C:2.输入4查看资源情况。 显示输出，银行家算法所剩资源（剩余资源、总共资源）。 七、实验心得 八、参考文献 汤子瀛等.计算机操作系统.西安电子科技大学出版社.2001年5月 蒋静 徐志伟.操作系统原理•技术与编程『M』.北京:机械工业出版社,2004第二篇：操作系统课程设计,磁盘调度算法范文
第三篇：实验报告六 磁盘调度算法
第四篇：操作系统课程设计六种算法
第五篇：银行家算法《操作系统》课程设计报告
点击咨询 