進程調(diào)度-銀行家算法-頁面置換-操作系統(tǒng)課程設(shè)計大全

PAGEPAGE40操作系統(tǒng)課程設(shè)計說明書學(xué)院名稱：專業(yè)班級：姓名：學(xué)號：2010年7月16日

評分標準優(yōu)秀：有完整的符合標準的文檔，文檔有條理、文筆通順，格式正確，程序完全實現(xiàn)設(shè)計要求，獨立完成；良好：有完整的符合標準的文檔，文檔有條理、文筆通順，格式正確；程序完全實現(xiàn)設(shè)計要求，獨立完成，但存在少量錯誤；中等：有完整的符合標準的文檔，有基本實現(xiàn)設(shè)計方案的軟件，設(shè)計方案正確；及格：有完整的符合標準的文檔，有基本實現(xiàn)設(shè)計方案的軟件，設(shè)計方案基本正確；不及格：沒有完整的符合標準的文檔，軟件沒有基本實現(xiàn)設(shè)計方案，設(shè)計方案不正確。沒有獨立完成，抄襲或雷同。成績評定為：。指導(dǎo)教師：年月日

目錄進程調(diào)度模擬1．設(shè)計目的0052.任務(wù)及要求0053.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）0063.2算法具體實現(xiàn)0064.實驗結(jié)果及分析4.1實驗結(jié)果0164.2結(jié)果分析017銀行家算法1．設(shè)計目的0182.任務(wù)及要求0183.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）0183.2算法具體實現(xiàn)0184.實驗結(jié)果及分析4.1實驗結(jié)果0264.2結(jié)果分析027頁面置換模擬1．設(shè)計目的0282.任務(wù)及要求0283.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）0283.2算法具體實現(xiàn)0284.實驗結(jié)果及分析4.1實驗結(jié)果0394.2結(jié)果分析040課題一：進程調(diào)度模擬1．設(shè)計目的通過課程設(shè)計，加深對教材中進程調(diào)度模擬算法的理解,同時通過用C語言編程，并在Windows平臺上實現(xiàn),以更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，提高綜合運用各專業(yè)課知識的能力。2.任務(wù)及要求2.1用語言來實現(xiàn)對n個進程采用不同調(diào)度算法的進程調(diào)度。2.2每個用來標識進程的進程控制塊PCB用結(jié)構(gòu)來描述，包括以下字段：（1）進程優(yōu)先數(shù)ID，其中0為閑逛進程，用戶進程的標識數(shù)為1，2，3…。（2）進程優(yōu)先級Priority，閑逛進程（idle）的優(yōu)先級為0，用戶進程的優(yōu)先級大于0，且隨機產(chǎn)生，優(yōu)先數(shù)越大，優(yōu)先級越高。（3）進程占用的CPU時間CPUtime，進程每運行一次，累計值等于4。（4）進程總共需要運行時間Alltime，利用隨機函數(shù)產(chǎn)生。（5）進程狀態(tài)，0：就緒態(tài)；1：運行態(tài)；2：阻塞態(tài)。（6）隊列指針next，用來將多個進程控制塊PCB鏈接為隊列。2.3優(yōu)先數(shù)改變的原則（1）進程在就緒隊列中每呆一個時間片，優(yōu)先數(shù)增加1。（2）進程每運行一個時間片，優(yōu)先數(shù)減3。2.4在調(diào)度前，系統(tǒng)中擁有的進程數(shù)PCB_number由鍵盤輸入，經(jīng)初始化后，所有的進程控制塊PCB鏈接成就緒隊列。3.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）主程序模塊>初始化模塊>函數(shù)模塊3.2算法具體實現(xiàn)//編程比較四種調(diào)度算法“FCFS、SJF、PSA、RR”的調(diào)度方法和性能。#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<time.h>#defineready1#defineblock0#defineover2#defineT4typedefintstatus;//定義結(jié)構(gòu)體，表示進程的PCB，用來標志一個進程typedefstructPpcb{intID;intPriority;intCPUtime;//進程占用的cpu的時間，進程每運行一次，累計值等于4intArrtime;//進程到達時間intStartime;//進程開始執(zhí)行時間intFinitime;//進程結(jié)束時的時刻intAlltime;intCtime;intstate;structPpcb*next;}*pcb;pcbProcessCreate(intn){//創(chuàng)建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){//輸出進程的調(diào)度結(jié)果 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("先來先服務(wù)算法調(diào)度結(jié)果為：\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("最短作業(yè)優(yōu)先算法調(diào)度結(jié)果為：\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("優(yōu)先級算法調(diào)度結(jié)果為：\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("時間片輪轉(zhuǎn)算法調(diào)度結(jié)果為：\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("比較算法之間的優(yōu)劣：\n"); printf("先來先服務(wù)算法的平均周轉(zhuǎn)時間：%f\n",a[0]); printf("最短作業(yè)優(yōu)先算法的平均周轉(zhuǎn)時間：%f\n",a[1]); printf("優(yōu)先級算法的平均周轉(zhuǎn)時間：%f\n",a[2]); printf("時間片輪轉(zhuǎn)算法的平均周轉(zhuǎn)時間：%f\n",a[3]);}voidmain(){ intn;pcbIdle,p;floata[4]; for(inti=0;i<4;i++) a[i]=0; printf("待執(zhí)行進程的個數(shù)為：\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("用不同的算法進行進程調(diào)度的情況如下：\n"); a[0]=FCFSDispatch(Idle,n); a[1]=SJFDispatch(Idle,n); a[2]=PriorityDispatch(Idle,n); a[3]=RRDispatch(Idle,n);//時間片輪轉(zhuǎn)法調(diào)度 AlgorCompare(a);//比較不通調(diào)度算法的優(yōu)劣}4.實驗結(jié)果及分析4.1實驗結(jié)果4.2結(jié)果分析不同的算法平均周轉(zhuǎn)時間不同，實際應(yīng)用當(dāng)中應(yīng)該根據(jù)需求選擇最合適的算法。課題二：銀行家算法1．設(shè)計目的通過課程設(shè)計，加深對教材中銀行家算法的理解,同時通過用C語言編程，并在Windows平臺上實現(xiàn),以更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，提高綜合運用各專業(yè)課知識的能力。2.任務(wù)及要求編程序模擬銀行家算法,要求能體現(xiàn)算法的全過程3.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）主程序模塊>初始化模塊函數(shù)模塊3.2算法具體實現(xiàn)#include<stdio.h>#include<stdlib.h>voidInit(intn,intm,int**&Max,int**&Allocation,int**&Need,int*&Available){//根據(jù)用戶輸入內(nèi)容，將Max、Allocation、Need以及Available各矩陣初始化 inti,j; //Max矩陣 printf("請輸入一個%d*%d的矩陣，代表每個進程所需要的每種資源的最大需求個數(shù)：\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的矩陣,代表每個進程正在占用的各種資源的個數(shù)：\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("請輸入每類資源可利用的數(shù)目：\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矩陣代表每個進程還需要各種資源的個數(shù) 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){//判斷目前是否處于安全狀態(tài) 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("系統(tǒng)處于安全狀態(tài)，且安全序列為：\n"); for(i=0;i<n;i++) printf("%d",SafeList[i]); printf("\n"); } else printf("系統(tǒng)處于不安全狀態(tài)！\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("所需要的資源數(shù)超過了所宣布的最大值，錯誤！\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:進程個數(shù)；m:資源種類數(shù) int**Max=NULL;//矩陣表示：每個進程對每種資源的最大需求 int**Allocation=NULL;//矩陣表示：每個進程已經(jīng)分配的每種資源個數(shù) int**Need=NULL;//矩陣表示：每個進程尚需的各種資源的個數(shù) int*Available=NULL;//每類資源可利用的數(shù)目 int*SafeList=NULL; int*Work=NULL; bool*Finish=NULL; printf("請輸入進程個數(shù)n：\n"); scanf("%d",&n); printf("請輸入資源種類數(shù)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.實驗結(jié)果及分析4.1實驗結(jié)果4.2結(jié)果分析首先對幾個數(shù)組進行初始化，然后判斷初始狀態(tài)的安全性。輸入進程的資源請求，嘗試分配并判斷安全性。課題三：頁面置換算法1．設(shè)計目的通過課程設(shè)計，加深對教材中頁面調(diào)度算法的理解,同時通過用C語言編程，并在Windows平臺上實現(xiàn),以更好地掌握操作系統(tǒng)的原理及實現(xiàn)方法，提高綜合運用各專業(yè)課知識的能力。2.任務(wù)及要求設(shè)計一個虛擬存儲區(qū)和內(nèi)存工作區(qū)，編程序演示下述算法的具體實現(xiàn)過程,并計算訪問命中率：2.1先進先出的算法（FIFO）2.2最近最少使用算法（LRU）2.3最佳淘汰算法（OPT）2.4最不經(jīng)常使用算法（LFU）3.算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）主程序模塊初始化模塊函數(shù)模塊3.2算法具體實現(xiàn)#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