进程调度-银行家算法-页面置换-操作系统课程设计大全

PAGEPAGE40操作系统课程设计说明书学院名称：专业班级：姓名：学号：2010年7月16日

评分标准优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确；及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，抄袭或雷同。成绩评定为：。指导教师：年月日

目录进程调度模拟1．设计目的0052.任务及要求0053.算法及数据结构3.1算法的总体思想（流程）0063.2算法具体实现0064.实验结果及分析4.1实验结果0164.2结果分析017银行家算法1．设计目的0182.任务及要求0183.算法及数据结构3.1算法的总体思想（流程）0183.2算法具体实现0184.实验结果及分析4.1实验结果0264.2结果分析027页面置换模拟1．设计目的0282.任务及要求0283.算法及数据结构3.1算法的总体思想（流程）0283.2算法具体实现0284.实验结果及分析4.1实验结果0394.2结果分析040课题一：进程调度模拟1．设计目的通过课程设计，加深对教材中进程调度模拟算法的理解,同时通过用C语言编程，并在Windows平台上实现,以更好地掌握操作系统的原理及实现方法，提高综合运用各专业课知识的能力。2.任务及要求2.1用语言来实现对n个进程采用不同调度算法的进程调度。2.2每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3…。（2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。（4）进程总共需要运行时间Alltime，利用随机函数产生。（5）进程状态，0：就绪态；1：运行态；2：阻塞态。（6）队列指针next，用来将多个进程控制块PCB链接为队列。2.3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加1。（2）进程每运行一个时间片，优先数减3。2.4在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。3.算法及数据结构3.1算法的总体思想（流程）主程序模块>初始化模块>函数模块3.2算法具体实现//编程比较四种调度算法“FCFS、SJF、PSA、RR”的调度方法和性能。#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<time.h>#defineready1#defineblock0#defineover2#defineT4typedefintstatus;//定义结构体，表示进程的PCB，用来标志一个进程typedefstructPpcb{intID;intPriority;intCPUtime;//进程占用的cpu的时间，进程每运行一次，累计值等于4intArrtime;//进程到达时间intStartime;//进程开始执行时间intFinitime;//进程结束时的时刻intAlltime;intCtime;intstate;structPpcb*next;}*pcb;pcbProcessCreate(intn){//创建n+1（包括idle）个进程实体，并建立链表,初始化 inti; srand((unsigned)time(NULL));pcbIdle,last,p; //为Idle进程赋初值 Idle=(pcb)malloc(sizeof(Ppcb)); Idle->ID=0; Idle->Priority=0; Idle->CPUtime=0; Idle->Arrtime=0; Idle->Startime=0; Idle->Finitime=0; Idle->Alltime=0; Idle->state=1; Idle->Ctime=0; Idle->next=NULL; last=Idle; for(i=1;i<=n;i++) {//为其他n个进程赋初值 p=(pcb)malloc(sizeof(Ppcb)); p->ID=i; p->Priority=rand()%(100-1)+1; p->CPUtime=0; p->Arrtime=rand()%(50-1)+1; p->Startime=0; p->Finitime=0; p->Alltime=rand()%(25-1)+1; p->state=0;p->Ctime=0; p->next=NULL; last->next=p; last=last->next; } returnIdle;}pcbOrder(pcb&head){//将n个进程按照到达时间由小到大排序Ppcb*cursor,*first,*prev,*max;first=NULL;if(head==NULL)returnNULL;for(cursor=max=head;cursor->next!=NULL;cursor=cursor->next){if(cursor->next->Arrtime<max->Arrtime){prev=cursor;max=cursor->next;}}first=max;if(max==head)head=head->next;elseprev->next=max->next;first->next=Order(head);returnfirst;}voidProcessPrint(Ppcb*Idle,intn){//输出进程的调度结果 inti;pcbp=Idle->next; printf("IDPriorityArrtimeAlltimeFinitimeCtime\n"); for(i=1;i<=n;i++,p=p->next) { printf("%-2d",p->ID); printf("%-2d",p->Priority); printf("%-2d",p->Arrtime); printf("%-2d",p->Alltime); printf("%-2d",p->Finitime); printf("%-2d",p->Ctime); printf("\n"); }}floatFCFSDispatch(Ppcb*Idle,intn){ pcbp=Idle;intj;floatactime=0; printf("先来先服务算法调度结果为：\n"); for(;p->next!=NULL;p=p->next) { if(p->next->Arrtime>p->Finitime) p->next->Finitime=p->next->Arrtime+p->next->Alltime; else p->next->Finitime=p->Finitime+p->next->Alltime; p->next->Ctime=p->next->Finitime-p->next->Arrtime; } ProcessPrint(Idle,n); for(j=1,p=Idle->next;j<=n;j++,p=p->next) { actime+=p->Ctime; } return(actime/n);}floatSJFDispatch(Ppcb*Idle,intn){ pcbp=Idle,q,r=NULL,s=NULL;intj;floatactime=0; printf("最短作业优先算法调度结果为：\n"); for(;p->next!=NULL;p=p->next) { if(p->next->Arrtime>p->Finitime) p->next->Finitime=p->next->Arrtime+p->next->Alltime; else { q=p->next; while(q->next&&q->next->Arrtime<=p->Finitime) { for(r=p;r!=q;r=r->next) { if(r->next->Alltime>q->next->Alltime) { s=q->next->next; q->next->next->next=r->next; r->next=q->next; q->next=s; break; } } q=q->next; } p->next->Finitime=p->Finitime+p->next->Alltime; p->next->Ctime=p->next->Finitime-p->next->Arrtime; } }ProcessPrint(Idle,n); for(j=1,p=Idle->next;j<=n;j++,p=p->next) { actime+=p->Ctime; } return(actime/n);}floatPriorityDispatch(pcbIdle,intn){ pcbp=Idle,q,r=NULL,s=NULL;intj;floatactime=0; printf("优先级算法调度结果为：\n"); for(;p->next!=NULL;p=p->next) { if(p->next->Arrtime>p->Finitime) p->next->Finitime=p->next->Arrtime+p->next->Alltime; else { q=p->next; while(q->next&&q->next->Arrtime<=p->Finitime) { for(r=p;r!=q;r=r->next) { if(r->next->Priority<q->next->Priority) { s=q->next->next; q->next->next->next=r->next; r->next=q->next; q->next=s; break; } } q=q->next; } p->next->Finitime=p->Finitime+p->next->Alltime; p->next->Ctime=p->next->Finitime-p->next->Arrtime; } } ProcessPrint(Idle,n); for(j=1,p=Idle->next;j<=n;j++,p=p->next) { actime+=p->Ctime; } return(actime/n);}floatRRDispatch(pcbIdle,intn){ pcbp=Idle;intnum=n;intj;floatactime=0; intcount=0; printf("时间片轮转算法调度结果为：\n"); while(num) { for(p=Idle;p->next!=NULL;p=p->next) { if(p->next->Arrtime>T&&p->next->state==0) { count=p->next->Arrtime; p->next->state=1; } elseif(p->next->state==2) p=p->next; else{} if(p->next->CPUtime+T>p->next->Finitime) { p->next->Finitime=count+p->next->Finitime- p->next->CPUtime; p->next->Ctime=p->next->Finitime-p->next->Arrtime; count=p->next->Finitime; p->next->state=2; num--; } else { p->next->CPUtime+=T; count=p->next->CPUtime; } } } ProcessPrint(Idle,n); for(j=1,p=Idle->next;j<=n;j++,p=p->next) { actime+=p->Ctime; } return(actime/n);}voidAlgorCompare(float*a){ printf("比较算法之间的优劣：\n"); printf("先来先服务算法的平均周转时间：%f\n",a[0]); printf("最短作业优先算法的平均周转时间：%f\n",a[1]); printf("优先级算法的平均周转时间：%f\n",a[2]); printf("时间片轮转算法的平均周转时间：%f\n",a[3]);}voidmain(){ intn;pcbIdle,p;floata[4]; for(inti=0;i<4;i++) a[i]=0; printf("待执行进程的个数为：\n"); scanf("%d",&n); printf("各个进程初始化情况如下：\n",n); Idle=ProcessCreate(n); ProcessPrint(Idle,n); Idle=Order(Idle); p=Idle; for(i=0;i<n;i++) p=p->next; p->next=NULL; printf("按到达时间排序：\n"); ProcessPrint(Idle,n); printf("用不同的算法进行进程调度的情况如下：\n"); a[0]=FCFSDispatch(Idle,n); a[1]=SJFDispatch(Idle,n); a[2]=PriorityDispatch(Idle,n); a[3]=RRDispatch(Idle,n);//时间片轮转法调度 AlgorCompare(a);//比较不通调度算法的优劣}4.实验结果及分析4.1实验结果4.2结果分析不同的算法平均周转时间不同，实际应用当中应该根据需求选择最合适的算法。课题二：银行家算法1．设计目的通过课程设计，加深对教材中银行家算法的理解,同时通过用C语言编程，并在Windows平台上实现,以更好地掌握操作系统的原理及实现方法，提高综合运用各专业课知识的能力。2.任务及要求编程序模拟银行家算法,要求能体现算法的全过程3.算法及数据结构3.1算法的总体思想（流程）主程序模块>初始化模块函数模块3.2算法具体实现#include<stdio.h>#include<stdlib.h>voidInit(intn,intm,int**&Max,int**&Allocation,int**&Need,int*&Available){//根据用户输入内容，将Max、Allocation、Need以及Available各矩阵初始化 inti,j; //Max矩阵 printf("请输入一个%d*%d的矩阵，代表每个进程所需要的每种资源的最大需求个数：\n",n,m); Max=(int**)malloc(n*sizeof(int*)); for(i=0;i<n;i++) { Max[i]=(int*)malloc(m*sizeof(int)); } for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%d",&Max[i][j]); } printf("输入的Max矩阵为：\n");for(i=0;i<n;i++) { for(j=0;j<m;j++) printf("%d",Max[i][j]); printf("\n"); } //Allocation矩阵 printf("请再输入一个%d*%d的矩阵,代表每个进程正在占用的各种资源的个数：\n",n,m); Allocation=(int**)malloc(n*sizeof(int*)); for(i=0;i<n;i++) { Allocation[i]=(int*)malloc(m*sizeof(int)); } for(i=0;i<n;i++) { for(j=0;j<m;j++) scanf("%d",&Allocation[i][j]); } printf("您输入的Allocation矩阵为：\n");for(i=0;i<n;i++) { for(j=0;j<m;j++) printf("%d",Allocation[i][j]); printf("\n"); } //Available矩阵 printf("请输入每类资源可利用的数目：\n"); Available=(int*)malloc(m*sizeof(int)); for(i=0;i<m;i++) scanf("%d",&Available[i]); printf("您输入的Available为：\n");for(i=0;i<m;i++) printf("%d",Available[i]); printf("\n"); //计算出Need矩阵代表每个进程还需要各种资源的个数 Need=(int**)malloc(n*sizeof(int*)); for(i=0;i<n;i++) { Need[i]=(int*)malloc(m*sizeof(int)); } printf("Need矩阵为：\n"); for(i=0;i<n;i++) { for(j=0;j<m;j++) { Need[i][j]=Max[i][j]-Allocation[i][j]; printf("%d",Need[i][j]); } printf("\n"); }}voidIsSafe(intn,intm,int**Need,int*Available,int**Allocation,int*SafeList,int*Work,bool*Finish){//判断目前是否处于安全状态 inti,j,mark,k=0; printf("处理中……\n"); Work=(int*)malloc(m*sizeof(int));for(i=0;i<m;i++) Work[i]=Available[i]; Finish=(bool*)malloc(n*sizeof(bool)); SafeList=(int*)malloc(n*sizeof(int)); for(i=0;i<n;i++) {//初始化为0 Finish[i]=false; } while(k<=n) { mark=1; for(i=0;i<n;i++) { mark=1; if(!Finish[i]) { for(j=0;j<m;j++) { if(Need[i][j]>Work[j]) { mark=-1; break; } } if(mark!=-1) { for(j=0;j<m;j++) { Work[j]=Work[j]+Allocation[i][j]; } Finish[i]=true; SafeList[k]=i; k++; mark=-1; break; } } } if(mark==1) { if(k==n) { printf("系统处于安全状态，且安全序列为：\n"); for(i=0;i<n;i++) printf("%d",SafeList[i]); printf("\n"); } else printf("系统处于不安全状态！\n"); break; } } }voidRequest(intn,intm,int**Need,int*Available,int**Allocation,int*SafeList,int*Work,bool*Finish){ inti,j; int*Request=NULL; printf("您想为哪个进程请求资源：\n"); scanf("%d",&i); Request=(int*)malloc(m*sizeof(int)); printf("对于每类资源，您希望分别请求几个:\n"); for(j=0;j<m;j++) scanf("%d",&Request[j]); for(j=0;j<m;j++) { if(Request[j]>Need[i][j]) { printf("所需要的资源数超过了所宣布的最大值，错误！\n"); break; } } if(j==m) { for(j=0;j<m;j++) { if(Request[j]>Available[j]) { printf("尚无足够的资源可供使用，错误！\n"); break; } } } if(j==m) { for(j=0;j<m;j++) { Available[j]-=Request[j]; Allocation[i][j]+=Request[j]; Need[i][j]-=Request[j]; } IsSafe(n,m,Need,Available,Allocation,SafeList,Work,Finish); }}voidmain(){ intn,m;//n:进程个数；m:资源种类数 int**Max=NULL;//矩阵表示：每个进程对每种资源的最大需求 int**Allocation=NULL;//矩阵表示：每个进程已经分配的每种资源个数 int**Need=NULL;//矩阵表示：每个进程尚需的各种资源的个数 int*Available=NULL;//每类资源可利用的数目 int*SafeList=NULL; int*Work=NULL; bool*Finish=NULL; printf("请输入进程个数n：\n"); scanf("%d",&n); printf("请输入资源种类数m：\n"); scanf("%d",&m);Init(n,m,Max,Allocation,Need,Available);IsSafe(n,m,Need,Available,Allocation,SafeList,Work,Finish);Request(n,m,Need,Available,Allocation,SafeList,Work,Finish);} scanf("%d",&m);Init(n,m,Max,Allocation,Need,Available);IsSafe(n,m,Need,Available,Allocation,SafeList,Work,Finish);Request(n,m,Need,Available,Allocation,SafeList,Work,Finish);}4.实验结果及分析4.1实验结果4.2结果分析首先对几个数组进行初始化，然后判断初始状态的安全性。输入进程的资源请求，尝试分配并判断安全性。课题三：页面置换算法1．设计目的通过课程设计，加深对教材中页面调度算法的理解,同时通过用C语言编程，并在Windows平台上实现,以更好地掌握操作系统的原理及实现方法，提高综合运用各专业课知识的能力。2.任务及要求设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程,并计算访问命中率：2.1先进先出的算法（FIFO）2.2最近最少使用算法（LRU）2.3最佳淘汰算法（OPT）2.4最不经常使用算法（LFU）3.算法及数据结构3.1算法的总体思想（流程）主程序模块初始化模块函数模块3.2算法具体实现#include<stdio.h>#include<stdlib.h>typedefstructBL{ intblock; structBL*next;}*BlockOrder;intNotin(intm,int*BlockList,intk,BlockOrdercur,BlockOrder&pre,int&flag){ intj=0;flag=0; if(BlockList[cur->block]==k) { pre=cur; flag=1; return0; } for(j=1;j<m;j++,cur=cur->next) { if(BlockList[cur->next->block]==k) { pre=cur; return0; } } return1;}voidPRAfifo(intm,intn,BlockOrderhead,BlockOrderlast,int*BlockList,int*PageList){ inti=0,j=0,count=0,flag=0; floatrr=0; BlockOrdercur=head,pre=NULL; printf("用FIFO算法进行页面置换：\n"); while(i<n) { printf("页面%d:",PageList[i]); if(Notin(m,BlockList,PageList[i],head,pre,flag)) { BlockList[head->block]=PageList[i]; last->next=head; last=last->next; head=head->next; } else { /* if(pre==head&&flag==1) { last->next=head; last=last->next; head=head->next; } else { last->next=pre->next; last=last->next; pre->next=pre->next->next; }*/ count++; } i++; for(j=0;j<m;j++) { if(BlockList[j]==-1) printf("-"); else printf("%d",BlockList[j]); } printf("\n"); } rr=(float)count/n; printf("用FIFO算法进行页面置换的命中率为：%2.1f",rr*100);puts("%");printf("\n");}voidPRAlru(intm,intn,BlockOrderhead,BlockOrderlast,int*BlockList,int*PageList){ inti=0,j=0,count=0,flag=0; floatrr=0; BlockOrdercur=head,pre=NULL; printf("用FIFO算法进行页面置换：\n"); while(i<n) { printf("页面%d:",PageList[i]); if(Notin(m,BlockList,PageList[i],head,pre,flag)) { BlockList[head->block]=PageList[i]; last->next=head; last=last->next; head=head->next; } else { if(pre==head&&flag==1) { last->next=head; last=last->next; head=head->next; } elseif(pre->next!=last) { last->next=pre->next; last=last->next; pre->next=pre->next->next; } else{} count++; } i++; for(j=0;j<m;j++) { if(BlockList[j]==-1) printf("-"); else printf("%d",BlockList[j]); } printf("\n"); } rr=(float)count/n; printf("用FIFO算法进行页面置换的命中率为：%2.1f",rr*100);puts("%");printf("\n");}voidPRAlfu(intm,intn,BlockOrderhead,BlockOrderlast,int*BlockList,int*PageList){ inti=0,j=0,count=0,flag=0; floatrr=0; BlockOrdercur=head,pre=NULL; printf("用lfu算法进行页面置换：\n"); while(i<n) { printf("页面%d:",PageList[i]); if(Notin(m,BlockList,PageList[i],head,pre,flag)) { BlockList[head->block]=PageList[i]; last->next=head; last=last->next; head=head->next; } else { if(pre==head&&flag==1) { last->next=head; last=last->next; head=head->next; } elseif(pre->next!=last) { last->next=pre->next; last=last->next; pre->next=pre->next->next; } else{} count++; } i++; for(j=0;j<m;j++) { if(BlockList[j]==-1) printf("-"); else printf("%d",BlockList[j]); } printf("\n"); } rr=(float)count/n; printf("用lfu算法进行页面置换的命中率为：%2.1f",rr*100);puts("%");printf("\n");}intIsIn(intm,int*BlockList,intk) { for(inti=0;i<m;i++) { if(BlockList[i]==k) return1; } return0; } voidnextj(intm,int*BlockList,intn,int*PageList,inti,int*&nextoccur) { intj,k; for(j=0;j<m;j++) { for(k=i+1;k<n;k++) { if(BlockList[j]==PageList[k]) { nextoccur[j]=k; break; } } if(BlockList[j]==-1) { nextoccur[j]=4*n-j; } elseif(k==n) nextoccur[j]=3*n-j; } } intChooseNextOut(int