下面是范文网小编整理的操作系统课程设计,磁盘调度算法范文3篇(磁盘调度算法的模拟实现课程设计),欢迎参阅。
操作系统课程设计,磁盘调度算法范文1
实验报告六磁盘调度算法
班级:软技2班学号:
姓名:刘道林
一.
实验内容:
熟悉磁盘的结构以及磁盘的驱动调度算法的模拟,编程实现简单常用的磁盘驱动调度算法先来先服务(FIFO)、电梯调度算法、最短寻找时间优先算法、扫描(双向扫描)算法、单向扫描(循环扫描)算法等。编程只需实现两个算法。
题目可
以选取教材或习题中的相关编程实例。
编程语言建议采用c/c++或Java。模拟程序鼓励采用随机数技术、动态空间分配技术,有条件 的最好能用图形界面展现甚至用动画模拟。
实验性质:验证型。
二.
实验目的和要求
1)掌握使用一门语言进行磁盘驱动调度算法的模拟;
2)编写程序将磁盘驱动调度算法的过程和结果能以 较简明直观的方式展现 出来。
三. 实验原理、方法和步骤
1.实验原理
磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率,从而影响计算机系统的整体效率。
常用的磁盘驱动调度算法有:最简单的磁盘驱动调度算法是先入先出(FIFO)法。这种算法的实质是,总是严格按时间顺序对磁盘请
求予以处理。算法实现简单、易于理解并且相对公平,不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移
动方向,效率有待提高。
最短寻找时间优先算法:总是优先处理最靠近的请求。该算法移动的柱面距离较小,但可能会经常改变
移动方向,并且可能会发生进程饥饿现象。
电梯调度:总是将一个方向上的请求全部处理完后,才改变方向继续处理其他请求。
扫描(双向扫描):总是从最外向最里进行扫描,然后在从最里向最外扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或
最里的请求时不会移动到最外或最里柱面,二扫描算法总是移到最外、最里柱面。两端的请求有优先服被务的迹象。
循环扫描(单 向扫描):从最外向最里进行柱面请求处理,到最里柱面后,直接跳到最外柱面然后继续向里进行处理。该算法与扫描算法的区别是,回来过程不处理请求,基于这样的事实,因为里端刚被处理。
2.实验方法
1)使用流程图描述演示程序的设计思想;
2)选取c/c++、Java等计算机语言,编程调试,最终给出运行正确的程序。
四.
实验结果分析
能够将磁盘驱动调度算法在各种情况下都能得出正确的结论。对FIFO、最短寻找时间优先或电梯调度算法能够
在多次模拟数据下得出平均移动柱面数,并进行效率比较分析
五.源程序代码 #include <> #include <> #include <> #include <> typedef struct _proc {
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(“”);
scanf(“%s”,p->name);
Printf(“ 0-199n”);
scanf(“%d”,&p->team);
/*输入请求进程信息*/
Printf(“ 0-19n”);
scanf(“%d”,&p->ci);
Printf(“ 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<=:accept requestnnum>: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>&&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<=) /*接受请求*/ { 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班 目录 实验:进程调度算法——时间片轮转算法 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 <> #include <> #include <> #define N 10 int time=0;bool spe=false;typedef struct pcb /*进程控制块定义*/ { 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 <> int Available[3],Max[5][3],Allocation[5][3],Need[5][3];bool Safe(int p){ int Work[3]={Available[0],Available[1],Available[2]};int Finish[5]={0,0,0,0,0};int i=0,m,num=0;if(Need[p][0]||Need[p][1]||Need[p][2]) 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 table[5][3];void FirstFit(int job[3],int ta[5][3]){ 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<> #include<> typedef struct freeBlock { int index,time;struct freeBlock*next;}freeBlock;typedef struct jobQueue { int index;struct jobQueue*next;}jobQueue;jobQueue*creat(jobQueue*head,int num){ 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 <> #include <> #include <> typedef struct memory { int index;struct memory*left,*right;}memory;memory*creat(){ 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.实验题目: 磁盘调度算法。 建立相应的数据结构; 在屏幕上显示磁盘请求的服务状况; 将一批磁盘请求的情况存磁盘文件,以后可以读出并重放; 计算磁头移动的总距离及平均移动距离; 支持算法:FIFO、SSTF、SCAN、CSCAN; 2.设计目的: 调度磁盘I/O请求服务,采用好的方式能提高访问时间和带宽。本实验通过编程对磁盘调度算法的实现,加深对算法的理解,同时通过用C++语言编写程序实现这些算法,并在windos平台上实现,更好的掌握操作系统的原理以及实现方法,提高综合运用专业课知识的能力。 3.任务及要求 设计任务 编程实现下述磁盘调度算法,并求出每种算法的平均寻道长度: 1、先来先服务算法(FCFS) 2、最短寻道时间算法(SSTF) 3、扫描算法(SCAN) 4、循环扫描算法(CSCAN) 设计要求 对用户指定的磁盘调度请求序列,基于以上四种算法,实现各自的调度顺序并输出,同时计算出各种算法下的平均寻道长度。 4.算法及数据结构 算法的总体思想 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<> #include<> #include<> void menu(){ cout<<“*********************菜单*********************”< 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<<“程序结束,谢谢使用!”< 操作系统课程设计,磁盘调度算法范文3篇(磁盘调度算法的模拟实现课程设计)相关文章: ★ 浅谈新课程改革背景下的高中物理教学[材料]3篇 新课程改革下的高中物理教学痛点 ★ 印刷设计与工艺课程教学大纲3篇(印刷设计与工艺课程教学大纲论文)操作系统课程设计,磁盘调度算法范文2
操作系统课程设计,磁盘调度算法范文3