[操作系统实验（进程调度+存储管理+磁盘调度++银行家算法+文件系统设计）]

操作系统实验(进程调度+存储管理+磁盘调度++银行家算法+文件系统设计) 实验三 进程调度 一、 实验目的 多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略来决定那个进程优先占有处理机。因而引起进程调度。本实验模拟在单处理机情况下的处理机调度问题，加深对进程调度的理解。

二、 实验要求 1． 设计进程调度算法，进程数不定 2． 包含几种调度算法，并加以实现 3． 输出进程的调度过程——进程的状态、链表等。

三、 参考例 1． 题目——优先权法、轮转法 简化假设 1） 进程为计算型的（无I/O） 2） 进程状态：ready、running、finish 3） 进程需要的CPU时间以时间片为单位确定 2． 算法描述 1） 优先权法——动态优先权 当前运行进程用完时间片后，其优先权减去一个常数。

2） 轮转法 开始 键盘输入进程数n，和调度方法的选择 优先权法？ 轮转法 产生n个进程，对每个进程产生一个PCB，并用随机数产生进程的优先权及进程所需的CPU时间 按优先权大小，把n个进程拉成一个就绪队列 初始化其他数据结构区 链首进程投入运行 时间片到，进程所需的CPU时间减1，优先权减3，输出个进程的运行情况 所需的CPU时间=0？ 撤销进程 就绪队列为空？ 结束 将进程插入就绪队列 N Y N Y Y B N 四、 实验流程图 产生n个进程，对每个进程用随机数产生进程的轮转时间片数及进程所需的时间片数，已占用CPU的时间片数置为0 按进程产生的先后次序拉成就绪队列链 链首进程投入运行 时间片到，进程所需时间片数减1，已占用CPU时间片数加1 输出各进程的运行情况 进程所需时间片数=0？ 撤销该进程 就绪队列为空吗？ 占用CPU的时间片数=轮转时间片数？ 占用CPU的时间片数置为0 把该进程插入就绪队列尾 B N Y N Y Y 结束 N 注意：
1． 产生的各种随机数的取值范围加以限制，如所需的CPU时间限制在1~20之间。

2． 进程数n不要太大通常取4~8个 3． 使用动态数据结构 4． 独立编程 5． 至少三种调度算法 6． 若有可能请在图形方式下，将PCB的调度用图形成动画显示。

五．实验过程：
（1）输入：进程流文件（1.txt），其中存储的是一系列要执行的进程， 每个作业包括四个数据项：
进程名 进程状态(1就绪 2等待 3运行) 所需时间 优先数(0级最高) 进程0 1 50 2 进程1 2 10 4 进程2 1 15 0 进程3 3 28 5 进程4 2 19 1 进程5 3 8 7 输出: 进程执行流等待时间，平均等待时间 本程序包括:FIFO算法，优先数调度算法，时间片轮转调度算法 （2）程序代码 #include<stdio.h> #include<string.h> #include<iostream.h> const int block_time=10; //定义时间片的长度为10秒 const int MAXPCB=100; //定义最大进程数 //定义进程结构体 typedef struct node { char name[20]; int status; int time; int privilege; int finished; int wait_time; }pcb; pcb pcbs[MAXPCB]; int quantity; //初始化函数 void initial() { int i; for(i=0;i<MAXPCB;i++) { strcpy(pcbs[i].name,““); pcbs[i].status=0; pcbs[i].time=0; pcbs[i].privilege=0; pcbs[i].finished=0; pcbs[i].wait_time=0; } quantity=0; } //读数据函数 int readData() { FILE *fp; char fname[20]; int i; cout<<“请输入进程流文件名:“; cin>>fname; if((fp=fopen(fname,“r“))==NULL) { cout<<“错误,文件打不开,请检查文件名“<<endl; } else { while(!feof(fp)) { fscanf(fp,“%s %d %d %d“,pcbs[quantity].name,&pcbs[quantity].status, &pcbs[quantity].time,&pcbs[quantity].privilege); quantity++; } //输出所读入的数据 cout<<“输出所读入的数据“<<endl; cout<<“进程名 进程状态 所需时间 优先数“<<endl; for(i=0;i<quantity;i++) { cout<<“ “<<pcbs[i].name<<“ “<<pcbs[i].status<<“ “<<pcbs[i].time<<“ “<<pcbs[i].privilege<<endl; } return(1); } return(0); } //重置数据,以供另一个算法使用 void init() { int i; for(i=0;i<MAXPCB;i++) { pcbs[i].finished=0; pcbs[i].wait_time=0; } } //先进先出算法 void FIFO() { int i,j; int total; //输出FIFO算法执行流 cout<<endl<<“*****************************************************“<<endl; cout<<“FIFO算法执行流:“<<endl; cout<<“进程名 等待时间“<<endl; for(i=0;i<quantity;i++) { cout<<“ “<<pcbs[i].name<<“ “<<pcbs[i].wait_time<<endl; for(j=i+1;j<quantity;j++) { pcbs[j].wait_time+=pcbs[i].time; } } total=0; for(i=0;i<quantity;i++) { total+=pcbs[i].wait_time; } cout<<“总等待时间:“<<total<<“ 平均等待时间:“<<total/quantity<<endl; } //优先数调度算法 void privilege() { int i,j,p; int passed_time=0; int total; int queue[MAXPCB]; int current_privilege=1000; for(i=0;i<quantity;i++) { current_privilege=1000; for(j=0;j<quantity;j++) { if((pcbs[j].finished==0)&&(pcbs[j].privilege<current_privilege)) { p=j; current_privilege=pcbs[j].privilege; } } queue[i]=p; pcbs[p].finished=1; pcbs[p].wait_time+=passed_time; passed_time+=pcbs[p].time; } //输出优先数调度执行流 cout<<endl<<“***********************************************************“<<endl; cout<<“优先数调度执行流:“<<endl; cout<<“进程名 等待时间“<<endl; for(i=0;i<quantity;i++) { cout<<“ “<<pcbs[queue[i]].name<<“ “<<pcbs[queue[i]].wait_time<<endl; } total=0; for(i=0;i<quantity;i++) { total+=pcbs[i].wait_time; } cout<<“总等待时间:“<<total<<“ 平均等待时间:“<<total/quantity<<endl; } //时间片轮转调度算法 void timer() { int i,j,number,flag=1; int passed_time=0; int max_time=0; int round=0; int queue[1000]; int total=0; while(flag==1) { flag=0; number=0; for(i=0;i<quantity;i++) { if(pcbs[i].finished==0) { number++; j=i; } } if(number==1) { queue[total]=j; total++; pcbs[j].finished=1; } if(number>1) { for(i=0;i<quantity;i++) { if(pcbs[i].finished==0) { flag=1; queue[total]=i; total++; if(pcbs[i].time<=block_time*(round+1)) { pcbs[i].finished=1; } } } } round++; } if(queue[total-1]==queue[total-2]) { total--; } cout<<endl<<“*******************************************************“<<endl; cout<<“时间片轮转调度执行流:“<<endl; for(i=0;i<total;i++) { cout<<pcbs[queue[i]].name<<“ “; cout<<endl; } } //显示 void version() { cout<<“ 　　/********************* 进程调度 ********************/　“; cout<<endl<<endl; } //主函数 void main() { int flag; version(); initial(); flag=readData(); if(flag==1) { FIFO(); init(); privilege(); init(); timer(); } } （3）运行结果：
输入进程流文件名1.txt即可得出以下输出结果：
实验二 银行家算法 一、 实验目的 死锁会引起计算机工作僵死，因此操作系统中必须防止。本实验的目的在于让学生独立的使用高级语言编写和调试一个系统动态分配资源的简单模拟程序，了解死锁产生的条件和原因，并采用银行家算法有效地防止死锁的发生，以加深对课堂上所讲授的知识的理解。

二、 实验要求 设计有n个进程共享m个系统资源的系统，进程可动态的申请和释放资源，系统按各进程的申请动态的分配资源。

系统能显示各个进程申请和释放资源，以及系统动态分配资源的过程，便于用户观察和分析；

三、 数据结构 1． 可利用资源向量Available ，它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available（j）=k，标是系统中现有Rj类资源k个。

2． 最大需求矩阵Max，这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max（i，j）=k，表示进程i需要Rj类资源的最大数目为k。

3． 分配矩阵Allocation，这是一个n×m的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation（i，j）=k，表示进程i当前已经分到Rj类资源的数目为k。Allocation i表示进程i的分配向量，有矩阵Allocation的第i行构成。

4． 需求矩阵Need，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need（i，j）=k，表示进程i还需要Rj类资源k个，才能完成其任务。Need i表示进程i的需求向量，由矩阵Need的第i行构成。

上述三个矩阵间存在关系：Need（i，j）=Max（i，j）-Allocation（i，j）；

四、 银行家算法 Request i 是进程Pi 的请求向量。Request i （j）=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：
1． 如果Request i ≤Need，则转向步骤2；
否则，认为出错，因为它所请求的资源数已超过它当前的最大需求量。

2． 如果Request i ≤Available，则转向步骤3；
否则，表示系统中尚无足够的资源满足Pi的申请，Pi必须等待。

3． 系统试探性地把资源分配给进程Pi，并修改下面数据结构中的数值：
Available = Available - Request i Allocation i= Allocation i+ Request i Need i= Need i - Request i 4． 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全才正式将资源分配给进程Pi，以完成本次分配；
否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

假定系统有5个进程（p0,p1,p2,p3,p4）和三类资源（A，B，C），各种资源的数量分别为10，5，7，在T0时刻的资源分配情况如下图：
Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 ( 2 3 0 ) P1 3 2 2 2 0 0 1 2 2 (3 0 2 ) (0 2 0 ) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 五、 安全性算法 1． 设置两个向量。

Work：它表示系统可提供给进程继续运行的各类资源数目，它包含m个元素，开始执行安全性算法时，Work = Available。

Finish：它表示系统是否有足够的资源分配给进程，使之运行完成，开始Finish（I）=false；
当有足够资源分配给进程Pi时，令Finish（i）=true；

2． 从进程集合中找到一个能满足下述条件的进程。

Finish（i）= = false；

Need i ≤work；

如找到则执行步骤3；
否则，执行步骤4；

3． 当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行 Work = work + Allocation i Finish（i）=true；
转向步骤2；

4． 若所有进程的Finish（i）都为true，则表示系统处于安全状态；
否则，系统处于不安全状态。

六、 系统流程图 开 始 输入资源数m, 及各类资源总数，初始化Available向量 输入进程数n，i=1 输入进程i的最大需求向量max。

i≤n max≤资源总数 提示错误重新输入 i加1 任选一个进程作为当前进程 输入该进程的资源请求量Request 调用银行家算法，及安全性算法，完成分配，或并给出提示 该进程的Need向量为0 该进程已运行结束 Need矩阵为0 所有进程运行都结束 结 束 N Y Y N N Y 初始化need 矩阵 N Y 七．银行家算法程序代码 #include<stdio.h> #include<conio.h> #include<iostream> using namespace std; typedef struct Max1 // 资源的最大需求量 { int m_a; int m_b; int m_c; }Max; typedef struct Allocation1 //已分配的资源数 { int a_a; int a_b; int a_c; }Allocation; typedef struct Need1 //还需要的资源数 { int n_a; int n_b; int n_c; }Need; struct Available1 //可利用的资源量 { int av_a; int av_b; int av_c; } q; struct pr //定义一个结构 { char name; Max max; Allocation allocation; Need need; int finishflag; }p[5]; char na[5]; //******************************************** void init() //读入文件“1.txt“ { cout<<“各进程还需要的资源数NEED：“<<endl; FILE *fp; fp=fopen(“1.txt“,“r+“); // 打开文件“1.txt“ for(int i=0;i<5;i++) { fscanf(fp,“%c,%d,%d,%d,%d,%d,%d＼n“,&p[i].name,&p[i].max.m_a,&p[i].max.m_b, &p[i].max.m_c,&p[i].allocation.a_a,&p[i].allocation.a_b,&p[i].allocation.a_c); p[i].need.n_a=p[i].max.m_a-p[i].allocation.a_a; p[i].need.n_b=p[i].max.m_b-p[i].allocation.a_b; p[i].need.n_c=p[i].max.m_c-p[i].allocation.a_c; cout<<p[i].name<<“: “<<p[i].need.n_a<<“ “<<p[i].need.n_b<<“ “<<p[i].need.n_c<<endl; } fclose(fp); //关闭文件 } //*********************************************** int fenpei()//分配资源 { cout<<“Available:“; cout<<q.av_a<<“ “<<q.av_b<<“ “<<q.av_c<<endl; int finishcnt=0,k=0,count=0; for(int j=0;j<5;j++) p[j].finishflag=0; while(finishcnt<5) { for(int i=0;i<5;i++) { if(p[i].finishflag==0&&q.av_a>=p[i].need.n_a&&q.av_b>=p[i].need.n_b&&q.av_c>=p[i].need.n_c) { q.av_a+=p[i].allocation.a_a; q.av_b+=p[i].allocation.a_b; q.av_c+=p[i].allocation.a_c; p[i].finishflag=1; finishcnt++; na[k++]=p[i].name; break; } } count++;//禁止循环过多 if(count>5)return 0; } return 1; } //**************************************************** int shq() //申请资源 { int m=0,i=0,j=0,k=0; //m为进程号; i,j,k为申请的三类资源数 cout<<“请输入进程号和请求资源的数目!“<<endl; cout<<“如：进程号 资源A B C“<<endl; cout<<“ 0 2 0 2“<<endl; cin>>m>>i>>j>>k; if(i<=p[m].need.n_a&&j<=p[m].need.n_b &&k<=p[m].need.n_c) { if(i<=q.av_a&&j<=q.av_b&&k<=q.av_c) { p[m].allocation.a_a+=i; p[m].allocation.a_b+=j; p[m].allocation.a_c+=k; p[m].need.n_a=p[m].max.m_a-p[m].allocation.a_a; p[m].need.n_b=p[m].max.m_b-p[m].allocation.a_b; p[m].need.n_c=p[m].max.m_c-p[m].allocation.a_c; cout<<“各进程还需要的资源数NEED:“<<＇＼n＇; for(int w=0;w<5;w++) cout<<p[w].name<<“: “<<p[w].need.n_a<<“ “<<p[w].need.n_b <<“ “<<p[w].need.n_c<<endl; return 1; } else cout<<“Request>Available让进程“<<m<<“等待......“<<endl; } else cout<<“Request>Need,让进程“<<m<<“等待......“<<endl; return 0; } //******************************************** void main() { int flag; char c; cout<<“ /******** 银 行 家 算 法********/ “<<endl; cout<<“确认已经在＼“1.txt＼“文档中正确输入各进程的有关信息后按回车键“<<endl; getch(); init(); q.av_a=10; //各种资源的数量 q.av_b=5; q.av_c=7; while(flag) { for(int i=0;i<5;i++) { q.av_a-= p[i].allocation.a_a; q.av_b-= p[i].allocation.a_b; q.av_c-= p[i].allocation.a_c; } if(fenpei()) { cout<<“这样配置资源是安全的!“<<endl; cout<<“其安全序列是：
“; for(int k=0;k<5;k++) cout<<“-->“<<na[k]; cout<<endl; cout<<“有进程发出Request请求向量吗?(Enter y or Y)“<<endl; cout<<endl; c=getch(); if(c==＇y＇||c==＇Y＇) { if(shq())continue; else break; } else flag=0; } else {flag=0; cout<<“不安全!!!“<<endl;} } } 八．运行结果 实验三 存储管理 一． 实验目的 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。

二． 实验内容 （1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。

页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。

在本实验中，假定页面大小为1k，用户虚存容量为32k，用户内存容量为4页到32页。

（2） produce_addstream通过随机数产生一个指令序列，共320条指令。

A、 指令的地址按下述原则生成：
1） 50%的指令是顺序执行的 2） 25%的指令是均匀分布在前地址部分 3） 25%的指令是均匀分布在后地址部分 B、 具体的实施方法是：
1） 在[0，319]的指令地址之间随机选取一起点m；

2） 顺序执行一条指令，即执行地址为m+1的指令；

3） 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地址为m’；

4） 顺序执行一条指令，地址为m’+1的指令 5） 在后地址[m’+2，319]中随机选取一条指令并执行；

6） 重复上述步骤1）~5），直到执行320次指令 C、 将指令序列变换称为页地址流 在用户虚存中，按每k存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条~第9条指令为第0页（对应虚存地址为[0，9]）；

第10条~第19条指令为第1页（对应虚存地址为[10，19]）；

。。。。。。

第310条~第319条指令为第31页（对应虚存地址为[310，319]）；

按以上方式，用户指令可组成32页。

（3） 计算并输出下属算法在不同内存容量下的命中率。

1） 先进先出的算法（FIFO）；

2） 最近最少使用算法（LRU）；

3） 最佳淘汰算法（OPT）；

4） 最少访问页面算法（LFR）；

其中3）和4）为选择内容 开 始 生成地址流 输入算法号S 1≤S≤4 形成地址页号 用户内存空间msize=2 Msize≤32 OPT() FIFO() LRU() LFU() Msize加1 S=? 是否用其他算法继续 结 束 N Y 1 2 3 4 Y N 提示出错，重新输入 三． 系统框图 四．页面置换算法程序代码：
#include<stdio.h> #include<string.h> #include<iostream.h> const int MAXSIZE=1000;//定义最大页面数 const int MAXQUEUE=3;//定义页框数 typedef struct node { int loaded; int hit; }page; page pages[MAXQUEUE]; //定义页框表 int queue[MAXSIZE]; int quantity; //初始化结构函数 void initial() { int i; for(i=0;i<MAXQUEUE;i++) { pages[i].loaded=-1; pages[i].hit=0; } for(i=0;i<MAXSIZE;i++) { queue[i]=-1; } quantity=0; } //初始化页框函数 void init() { int i; for(i=0;i<MAXQUEUE;i++) { pages[i].loaded=-1; pages[i].hit=0; } } //读入页面流 void readData() { FILE *fp; char fname[20]; int i; cout<<“请输入页面流文件名:“; cin>>fname; if((fp=fopen(fname,“r“))==NULL) { cout<<“错误,文件打不开,请检查文件名“; } else { while(!feof(fp)) { fscanf(fp,“%d “,&queue[quantity]); quantity++; } } cout<<“读入的页面流:“; for(i=0;i<quantity;i++) { cout<<queue[i]<<“ “; } } //FIFO调度算法 void FIFO() { int i,j,p,flag; int absence=0; p=0; cout<<endl<<“----------------------------“<<endl; cout<<“先进先出调度算法(FIFO)页面调出流:“; for(i=0;i<quantity;i++) { flag=0; for(j=0;j<MAXQUEUE;j++) { if(pages[j].loaded==queue[i]) { flag=1; } } if(flag==0) { if(absence>=MAXQUEUE) { cout<<pages[p].loaded<<“ “; } pages[p].loaded=queue[i]; p=(p+1)%MAXQUEUE; absence++; } } absence-=MAXQUEUE; cout<<endl<<“总缺页数:“<<absence<<endl; } //最近最少使用调度算法（LRU） void LRU() { int absence=0; int i,j; int flag; for(i=0;i<MAXQUEUE;i++) { pages[i].loaded=queue[i]; } cout<<endl<<“---------------------“<<endl; cout<<“最近最少使用调度算法(LRU)页面流:“; for(i=MAXQUEUE;i<quantity;i++) { flag=-1; for(j=0;j<MAXQUEUE;j++) { if(queue[i]==pages[j].loaded) { flag=j; } } //CAUTION pages[0]是队列头 if(flag==-1) { //缺页处理 cout<<pages[0].loaded<<“ “; for(j=0;j<MAXQUEUE-1;j++) { pages[j]=pages[j+1]; } pages[MAXQUEUE-1].loaded=queue[i]; absence++; } else { //页面已载入 pages[quantity]=pages[flag]; for(j=flag;j<MAXQUEUE-1;j++) { pages[j]=pages[j+1]; } pages[MAXQUEUE-1]=pages[quantity]; } } cout<<endl<<“总缺页数:“<<absence<<endl; } //显示 void version() { cout<<“ /*******************虚拟存储管理器的页面调度****************/“<<endl; cout<<endl; } void main() { version(); initial(); readData(); FIFO(); init(); LRU(); init(); init(); } 四． 运行结果 运行程序前先新建一个页面流文件文件（格式为*.txt），在文件中存储的是一系列页面号（页面号用整数表示，用空格作为分隔符），用来模拟待换入的页面。例如：
14 5 18 56 20 25 6 3 8 17 实验四 磁盘调度 一、 实验目的：
磁盘是高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出工作，在现代计算机系统中往往同时会有若干个要求访问磁盘的输入输出要求。系统可采用一种策略，尽可能按最佳次序执行访问磁盘的请求。由于磁盘访问时间主要受寻道时间T的影响，为此需要采用合适的寻道算法，以降低寻道时间。本实验要求学生模拟设计一个磁盘调度程序，观察调度程序的动态运行过程。通过实验让学生理解和掌握磁盘调度的职能。

二、 实验题目：
模拟电梯调度算法，对磁盘进行移臂操作 三、 提示及要求：
1、 假设磁盘只有一个盘面，并且磁盘是可移动头磁盘。

2、 磁盘是可供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其它想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。为此设置“驱动调度”进程。

3、 由于磁盘与处理器是并行工作的，所以当磁盘在为一个进程服务时，占有处理器的其它进程可以提出使用磁盘（这里我们只要求访问磁道），即动态申请访问磁道，为此设置“接受请求”进程。

4、 为了模拟以上两个进程的执行，可以考虑使用随机数来确定二者的允许顺序，程序结构图参考附图：
5、 “接受请求”进程建立一张“进程请求I/O”表，指出等待访问磁盘的进程要求访问的磁道，表的格式如下：
进程名 要求访问的磁道号 6、 “磁盘调度”的功能是查“请求I/O”表，当有等待访问的进程时，按电梯调度算法（SCAN算法）从中选择一个等待访问的进程，按其指定的要求访问磁道。SCAN算法参考课本第九章。算法模拟框图略。

7、 图1中的“初始化”工作包括：初始化“请求I/O”表，设置置当前移臂方向；
当前磁道号。并且假设程序运行前“请求I/O”表中已有若干进程（4～8个）申请访问相应磁道。

四、 实验报告：
1、 实验题目。

2、 程序中用到的数据结构及其说明。

3、 打印源程序并附注释。

4、 实验结果内容如下：打印“请求I/O”表，当前磁道号，移臂方向，被选中的进程名和其要求访问的磁道，看是否体现了电梯调度（SCAN）算法。

5、 体会与问题。

五、 附图：
开始 初始化 磁盘调度 随机数＞1/2 继续？ 接受请求 输入在[0，1]区间内的随机数 结束 六．磁盘调度的程序代码：
#include<iostream> #include<cmath> using namespace std; typedef struct node { int data; struct node *next; }Node; void main() { void fcfs(Node *,int,int);//声明先来先服务函数FCFS void sstf(Node *,int,int);//声明最短寻道时间优先函数SSTF void scan(Node *,int,int);//声明扫描函数SCAN void print(Node *); //输出链表函数 Node *head,*p,*q; //建立一个链表 int it,c=0,f,s; //c为链表长度,f是开始的磁道号,s是选择哪个算法 head=(Node *)malloc(sizeof(Node)); head->next=NULL; q=head; cout<<“ /**************磁盘调度算法***************/“<<endl; cout<<endl; cout<<“新建一个单链表,以0作为结束标志:“; cin>>it; while(it!=0) { p=(Node *)malloc(sizeof(Node)); p->next=NULL; p->data=it; q->next=p; q=p; cin>>it; c++; } cout<<“从几号磁道开始:“; cin>>f; //f为磁道号 print(head); cout<<“链表长度为:“<<c<<endl; cout<<“1、先来先服务算法FCFS“<<endl; cout<<“2、最短寻道时间优先算法SSTF“<<endl; cout<<“3、电梯调度算法(扫描算法SCAN)“<<endl; cout<<“0、退出“<<endl; cout<<“请选择:“; cin>>s; while(s!=0) { switch(s) { case 1:cout<<“你选择了:先来先服务算法FCFS“<<endl; fcfs( head,c,f); break; case 2:cout<<“你选择了:最短寻道时间优先算法SSTF“<<endl; sstf( head,c,f); break; case 3:cout<<“你选择了:电梯调度算法(扫描算法SCAN)“<<endl; scan( head,c,f); break; } cout<<“退出请选0,继续请选1,2,3:“; cin>>s; } } /***********************************************************/ void fcfs(Node *head,int c,int f)//先来先服务算法 { void print(Node *); Node *l;//*m,*n; float num=0; //num为平均寻道长度 l=head->next; for(int i=0;i<c;i++) { num+=abs(l->data-f); f=l->data; l=l->next; } num=num/c; cout<<“先来先服务的寻道顺序是:“<<endl; print(head); cout<<“平均寻道长度:“<<num<<endl; } /*****************************************************************/ void sstf(Node *head,int c,int f)//最短寻道时间优先算法 { void print(Node *); Node *p,*q,*r,*s,*l,*m; l=(Node *)malloc(sizeof(Node)); l->next=NULL; m=l; q=head; p=head->next; s=head; r=head->next; float num=0; for(int i=0;i<c;i++) { int min=abs(f-r->data); for(int j=0;j<c-i-1;j++) { p=p->next; q=q->next; if(abs(f-p->data)<min) { min=abs(f-p->data); r=p; s=q; } } num+=abs(f-r->data); f=r->data; s->next=r->next; r->next=NULL; m->next=r; m=r; q=head; p=head->next; s=head; r=head->next; } num=num/c; cout<<“最短寻道时间优先顺序是:“<<endl; print(l); cout<<“平均寻道长度:“<<num<<endl; } /***************************************************************/ void scan(Node *head,int c,int f)//扫描算法（电梯调度算法） { void print(Node *); int min,max,i=0,j=0; float num=0; Node *p,*q,*r,*s,*m,*n,*x,*y; r=(Node *)malloc(sizeof(Node));//存放比开始磁道小的磁道 r->next=NULL; s=r; m=(Node *)malloc(sizeof(Node));//存放比开始磁道大的磁道 m->next=NULL; n=m; x=(Node *)malloc(sizeof(Node)); x->next=NULL; y=x; q=head; p=head->next; while(p->next!=NULL) { if(p->data-f>0) { q->next=p->next; p->next=NULL; n->next=p; n=p; p=q->next; i++; } else { q->next=p->next; p->next=NULL; s->next=p; s=p; p=q->next; j++; } } if(p->data>=f) { n->next=p; n=p; i++; } else { s->next=p; s=p; j++; } q=r; //对比开始磁道小的磁道排序 p=r->next; while(q->next->next!=NULL) { q=q->next; p=q->next; max=q->data; while(p->next!=NULL) { if(p->data>max) { max=p->data; p->data=q->data; q->data=max; max=q->data; } p=p->next; } if(p->data>max) { max=p->data; p->data=q->data; q->data=max; max=q->data; } } //print(r); q=m; p=m->next; while(q->next->next!=NULL) { q=q->next; p=q->next; min=q->data; while(p->next!=NULL) { if(p->data<min) { min=p->data; p->data=q->data; q->data=min; min=q->data; } p=p->next; } if(p->data<min) { min=p->data; p->data=q->data; q->data=min; min=q->data; } } //print(m); x=m; p->next=r->next; y=x->next; while(y->next!=NULL) { num+=abs(f-y->data); f=y->data; y=y->next; } num+=abs(f-y->data); num=num/c; cout<<“扫描算法的顺序是:“<<endl; print(x); cout<<“平均寻道长度为:“<<num<<endl; } /*****************************************************/ void print(Node *head) //输出链表 { Node *p; p=head->next; cout<<“单链表显示:“; if(p==NULL) { cout<<“单链表为空:“; } else if(p->next==NULL) { cout<<p->data; } else { while(p->next!=NULL) { cout<<p->data<<“->“; p=p->next; } cout<<p->data<<endl; } } 七．运行结果：

相关热词搜索：