操作系统课程设计六种算法.doc

计算机操作系统课程设计报告学号：1367003270班级：软技4班姓名：张靖伟目 录1 实验：进程调度算法时间片轮转算法2 实验：银行家算法3 实验：分区分配算法BF和FF4 实验：页面置换算法FIFO和LRU5 实验：磁盘调度算法SCAN和SSTF1实验：进程调度算法时间片轮转算法1.实验设计说明用时间片轮转算法模拟单处理机调度。（1） 建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。 进程状态分为就绪（R）和删除（C）。（2） 为每个进程任意确定一个要求运行时间和到达时间。（3） 按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。（4） 执行处理机调度时，开始选择对首的第一个进程运行。（5） 执行： a)输出当前运行进程的名字； b)运行时间减去时间片的大小。（6） 进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。（7） 若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。2.实验代码/*时间片轮转调度算法*/#include #include #include #define N 10int time=0;bool spe=false;typedef struct pcb/*进程控制块定义*/char pnameN;/*进程名*/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 sN;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)/*复制一个进程*/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;PCB*getnext(PCB*p,BACK_TEAM*head)/*得到队列中下一个进程*/PCB*s=head-first;if(!p)return NULL;while(strcmp(s-pname,p-pname)s=s-next;return s-next;void del(BACK_TEAM*head,PRE_TEAM*S)/*释放申请的空间*/PCB*p=head-first-next;while(p)free(head-first);head-first=p;p=p-next;head-first=head-tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*创建后备队列*/PCB*p=creat();if(!head-first)head-first=p;elsehead-tail-next=p;head-tail=p;return head;bool recognize(PRE_TEAM*s1)/*判断运行是否结束*/if(!s1|!s1-first)return false;if(s1-first=s1-tail)if(s1-first-state!=C)return true;elsereturn false;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)spe=false;return NULL;printf(%dt%st,time,s-first);s-first-runtime-;time+;if(s-first-runtimefirst;s-first-state=C;printf(%cn,s-first-state);s-first=p-next;free(p);if(!s-first)s-tail=NULL;spe=false;return NULL;goto next;printf(%cn,s-first-state);next:PCB*head=s-first;s-first=head-next;if(!s-first)s-tail=NULL;spe=true;head-next=NULL;return head;int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*创建就绪队列*/int i=0;if(!head2-first)if(HEAD)if(c)head2-first=c;c-next=HEAD;head2-tail=HEAD;return 1;head2-first=head2-tail=HEAD;return 1;if(head2-first=head2-tail)if(*test)if(head2-first-arrivetime!=time)for(i=0;ifirst-arrivetime;i+,time+);*test=false;return 1;if(c)head2-tail-next=c;head2-tail=c;elseif(c)if(c-arrivetime!=time)time+;return 1;head2-tail-next=c;head2-tail=c;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;doprintf(要创建进程吗(y/n):);if(ask=getchar()=y|ask=Y)head1=creatbt(head1);num+;else if(ask=n|ask=N)break;elsereturn 1;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)CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1);del(head1,head2);return 1;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: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true 5. 从进程集合中找到一个能满足下述条件的进程： Finishi=false;并且 Needi,jWorkj； 若找到， 执行6， 否则，执行7。 6.当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; 然后继续执行5。 7.如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。2.实验代码#include int Available3,Max53,Allocation53,Need53;bool Safe(int p)int Work3=Available0,Available1,Available2;int Finish5=0,0,0,0,0;int i=0,m,num=0;if(Needp0|Needp1|Needp2)return false;printf(p%d可以运行n,p);Work0+=Allocationp0;Work1+=Allocationp1;Work2+=Allocationp2;Finishp=1;while(num=25)if(!Finishi&(Needi0=Work0)&(Needi1=Work1)&(Needi2=Work2)printf(p%d可以运行n,i);Work0+=Allocationi0;Work1+=Allocationi1;Work2+=Allocationi2;Finishi=1;num+;i=(i+1)%5;if(i=p)i+;for(m=0;m5;m+)if(Finishm=0)break;if(m=5)return true;elseprintf(系统处于不安全状态!n);return false;void Banker(int p,int i,int j,int k)int able3=Available0,Available1,Available2;int need3=Needp0,Needp1,Needp2;int allocation3=Allocationp0,Allocationp1,Allocationp2;if(i=Needp0&j=Needp1&k=Needp2)if(i=Available0&j=Available1&k=Available2)Available0-=i;Available1-=j;Available2-=k;Allocationp0+=i;Allocationp1+=j;Allocationp2+=k;Needp0-=i;Needp1-=j;Needp2-=k;if(!Safe(p)Available0=able0,Available1=able1,Available2=able2;Needp0=need0,Needp1=need1,Needp2=need2;Allocationp0=allocation0,Allocationp1=allocation1,Allocationp2=allocation2;printf(系统可能发生死锁!n);elseprintf(等待!系统资源不足!n);elseprintf(错误!申请的资源错误!n);int main(void)int i,j,k=0,p;printf(请输入进程的三种资源的情况maxa,b,c allocationa,b,c needa,b,c:n);for(i=0;i5;i+)for(j=0;j3;j+)scanf(%d,&Maxij);for(j=0;j3;j+)scanf(%d,&Allocationij);for(j=0;j3;j+)scanf(%d,&Needij);printf(请输入Availablea,b,c情况:);for(i=0;i3;i+)scanf(%d,&Availablei);printf(MaxtAllotNeedtAvain);for(i=0;i5;i+)for(j=0;j3;j+)printf(%d ,Maxij);printf(t);for(j=0;j3;j+)printf(%d ,Allocationij);printf(t);for(j=0;j3;j+)printf(%d ,Needij);printf(t);if(k!=4)printf(n);k+;for(i=0;i3;i+)printf(%d ,Availablei);printf(n请输入要申请的进程和资源:);scanf(%d %d %d %d,&p,&i,&j,&k);if(p=0&p=4)Banker(p,i,j,k);elseprintf(没有此进程!);return 1; 3.实验结果4.实验结果分析这个实验只是简单的演示了进程申请资源之后的进程运行的其中一个运行序列，因为这个算法课本上已经有详细的解说，所以这个程序并没有把算法的过程展现出来，只展现了进程的运行序列结果，另外，如果申请错误的话程序会有不同的结果有时会发生死锁3 实验：分区分配算法BF和FF1.实验设计说明1.这个算法模拟的是对内存空间的管理，这个程序用了一个简单的二维数组模拟分区表。2.程序首先要输入固定的五个分区的大小和始址，其次要输入作业的大小和实现的算法，由于这个程序把FF和BF放到一个程序中，便于比较两个算法。首次适应算法FF(First Fit)把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表最佳适应算法BF（Best Fit）首先把分区表按空间大小从小到大排序。然后把分区大于等于请求作业请求的分区分给请求者，余下部分仍留在空闲区中，然后修改分区表。然后打印出分配后的分区表2.实验代码#include int table53;void FirstFit(int job3,int ta53)int i,j;for(j=0;j3;j+)for(i=0;i=jobj)tai1-=jobj;tai2+=jobj;break;if(i=5)printf(内存不足!请等待!n);printf(空闲区t大小t始址n);for(j=0;j5;j+)for(i=0;i3;i+)printf(%dt,taji);printf(n);void BestFit(int job3)int j1,temp1,temp2,temp3,i,j;for(j1=0;j13;j1+)for(i=0;i5;i+)for(j=0;jtablej+11)temp1=tablej0;temp2=tablej1;temp3=tablej2;tablej0=tablej+10;tablej1=tablej+11;tablej2=tablej+12;tablej+10=temp1;tablej+11=temp2;tablej+12=temp3;for(i=0;i=jobj1)tablei1-=jobj1;tablei2+=jobj1;break;if(i=5)printf(内存不足!请等待!n);printf(空闲区t大小t始址n);for(j=0;j5;j+)for(i=0;i3;i+)printf(%dt,tableji);printf(n);void main()int table153,job3,j,i;printf(请输入5个空分区的大小和始址：);for(i=0;i5;i+)tablei0=i+1;table1i0=i+1;for(j=1;j3;j+)scanf(%d,&tableij);table1ij=tableij;for(j=0;j5;j+)for(i=0;i3;i+)printf(%dt,tableji);printf(n);printf(请输入3个要运行作业的大小：);for(i=0;i3;i+)scanf(%d,&jobi);printf(请输入要实现的算法1(FF)2(BF):);char c;scanf(%d,&i);getchar();if(i=1)FirstFit(job,table1);printf(还要实现BF吗(y/n);if(c=getchar()=y)BestFit(job);elseif(i=2)BestFit(job);printf(还要实现FF吗(y/n);if(c=getchar()=y)FirstFit(job,table1);3.实验结果4.实验结果分析首先输入分区表的分区情况，然后输入运行作业的大小，选择要实现的算法。第一个作业是96，所以找到第四个分区，第四个分区变为122，316，接着到第二个作业20，然后把第一个分区分给第二个作业，则第一个分区信息变为122，316，到第三个作业时，由于内存表中没有比第三个请求的分区还大的分区，所以会提示内存不足；然后到BF算法，因为是按空间大小排序的，所以第一个作业96被分配给了已经排好序的内存为96的第五个分区，第二个作业被分配给大小为36的分区，第三个作业被分配给内存大小为218的分区，然后又对剩余空间再次排队，用来给下一批作业分配。4 实验：页面置换算法FIFO和LRU1实验设计说明程序设置了两个结构体,freeBlock和jobQueue,其中freeBlock代表物理块,初次创建物理块时,物理块的计时器time=0,还有代表作业的index=-1;物理块有添加和删除的功能，每一次添加或删除都要初始化物理块。并且可以重复添加和删除，这样可以很好的测试算法的性能。2.算法设计的思想是：进入物理块时间越长的则物理块的计时器数值越大，如果物理块中有要访问的页面，则那个含页面的物理块的计数器变成1；并且物理块要满才会发生置换，于是设置了物理块计数器Time；2.实验代码#include#includetypedef struct freeBlockint index,time;struct freeBlock*next;freeBlock;typedef struct jobQueueint 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)head=job;elsejobQueue*j=head;while(j-next)j=j-next;j-next=job;return head; freeBlock*creat(freeBlock*head)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*inse(freeBlock*head)freeBlock*test=head;while(test)test-index=-1;test-time=0;test=test-next;freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock);free-index=-1;free-time=0;free-next=head;head=free;return head;freeBlock*dele(freeBlock*head)freeBlock*test=head;while(test)test-index=-1;test-time=0;test=test-next;freeBlock*f=head;head=f-next;free(f);return head;bool check(freeBlock*free,int j)freeBlock*f=free;while(f)if(f-index=j)return true;f=f-next;return false;void LRU(freeBlock*free,jobQueue*job)int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest)size+;ftest=ftest-next;printf(LRU置换页面为：);while(jtest)ftest=free;while(ftest)if(ftest-index=jtest-index)ftest-time=0;if(ftest-index=-1)ftest-index=jtest-index;ftest-time+;time=0;break;ftest-time+;if(Timetime)Time=ftest-time;time+;ftest=ftest-next;ftest=free;while(time=size)&ftest)if(check(free,jtest-index)time=0;Time=0;break;if(ftest-time=Time)printf(%d ,ftest-index);ftest-index=jtest-index;ftest-time=1;time=0;Time=0;break;ftest=ftest-next;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)if(ftest-index=-1)ftest-index=jtest-index;ftest-time+;time=0;break;ftest-time+;if(Timetime)Time=ftest-time;time+;ftest=ftest-next;ftest=free;while(time=size)&ftest)if(check(free,jtest-index)time=0;Time=0;break;if(ftest-time=Time)printf(%d ,ftest-index);ftest-index=jtest-index;ftest-time=1;time=0;Time=0;break;ftest=ftest-next;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;ip;i+)block=creat(block);printf(请输入作业个数：);scanf(%d,&num);printf(请输入作业：);for(i=0;inum;i+)scanf(%d,&ch);job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true)printf(增加物理块（1）减少物理块（2）,否则按任意键);scanf(%d,&num);if(num=1)printf(要增加几块：);scanf(%d,&ch);for(i=0;i=p)printf(sorry!);break;for(i=0;ich;i+)block=dele(block);FIFU(block,job);LRU(block,job);else ；break;3.实验结果4.实验结果分析程序开始要输入物理块数目和作业个数,然后再输入作业.在测试后可以随意添加或删除物理块来测试算法的性能。5 实验：磁盘调度算法SCAN和SSTF1.实验设计说明算法定义了一个双向链表，利用双向链表可以很好的进行方向的转换，且双向链表的中有代表磁盘号的标识符index；两个算法均采用访问完一个磁盘序列时删除该序列，其中scan算法实现时有点麻烦，首先要找到当前磁盘号序列的Max最大值和最小值Min及指向他们的指针pmax，pmin，另外还要找到当前磁头的相邻的两个访问序列信息psmax，psmin；还有一个重要的标志，那就是访问的方向test；当遇到最大值或最小值时，便会反置test的值，也就是访问的方向2.实验代码#include #include #include typedef struct memoryint 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;elsetail-right=p;p-left=tail;tail=p;scanf(%d,&ch);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)index-index1);if(p!=p1)p2=p;p=p-right;p=p1-right;if(p2)index1=p2-index;printf(%d ,p2-index);p2-left-right=p2-right;if(p2-right)p2-right-left=p2-left;free(p2);p2=NULL;elseprintf(%d ,p1-index);index1=p1-index;if(!p)free(p1);break;elsep=p1;p1=p1-right;free(p);continue;void SCAN(memory*head,int index)int index1=index,num,test,max=0,min=199,Max,Min;printf(请输入磁头查询方向!n);scanf(%d,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL;while(p1)if(!test)pmax=p1;if(p1-index=max)Max=max=p1-index;elsepmin=p1;if(p1-indexindex;p1=p1-right;p1=head;while(p1)if(!test)pmin=p1;if(p1-indexindex;elsepmax=p1;if(p1-index=max)Max=max=p1-index;p1=p1-right;p1=head;while(true)num=abs(p1-index-index1);p=p1;while(p)if(!test)if(p-in