08級操作系統課程設計報告書

1、課程設計報告書2011 / 2012 學年 第 1 學期課程名稱：操作系統實踐課程設計 專業(yè)班級：學 號：姓 名： 指導教師： 課程設計指導教師評語 成 績：_ 指導教師簽字：_題目1 進程調度算法的模擬11 題目的主要研究內容及預期達到的目標（1）編程序模擬實現進程調度算法中的FCFS、SJF和高響應比優(yōu)先算法。（2）基本完成了模擬實現FCFS、SJF 和HRN調度算法。12 題目研究的工作基礎或實驗條件（1）硬件環(huán)境：windows系統（2）軟件環(huán)境：Visual C+ 13 設計思想 （1）FCFS:將系統中所有的就緒進程按照FCFS原則，排成一個隊列。每次調度時將CPU分派給隊首進程，

2、讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms。 在一個時間片結束時，發(fā)生時鐘中斷。 調度程序據此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程。 進程可以未使用完一個時間片，就出讓CPU（如阻塞）。(2)SJF：對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)先分派處理機。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。（3）HRN：HRN調度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，從中選出響應比最高的作業(yè)投入執(zhí)行。 響應比R定義如下： R =(W+T)/T = 1+W/T 其中T為該作業(yè)估計需要的執(zhí)行時間，W為作業(yè)在后備狀態(tài)隊列中的等待時間。14 流程圖15

3、 主要程序代碼#include<iostream.h>#include<stdio.h>#include<stdlib.h>#define N 100typedef struct JCBint ID; /*作業(yè)標識數*/int requesttime; /*作業(yè)運行所需時間*/int runtime; /*作業(yè)實際運行所需時間*/int priority; /*作業(yè)優(yōu)先數*/int quick; /*作業(yè)緊迫程度*/JCB;JCB jcbN;int jcbnum; /*后備作業(yè)數*/void init(); /*賦值函數*/void FCFS(); /*定義

4、FCFS函數*/void SJF();/*定義SJF函數*/void HRN();/*定義HRN函數*/void main() /*main函數*/int i=0;init();cout<<"="<<endl;cout<<"| 1:FCFS 2:SJF |"<<endl;cout<<"| 3:HRN |"<<endl;cout<<"="<<endl;while(i<=0|i>=5) /*while循環(huán)選擇算法

5、*/cout<<"Please select a number(1,2,3,4):"<<endl;cin>>i;switch(i) /*switch語句選擇執(zhí)行函數*/ case 1:FCFS();break;case 2:SJF();break;case 3:HRN();break;void init() /*對定義的變量進行賦值的函數*/int i=0;while(i<=0|i>=2000)cout<<"Input the JCB number:(1-2000)"<<endl;c

6、in>>i;jcbnum=i;for(i=0;i<jcbnum;i+) /*for循環(huán)賦值語句*/jcbi.ID=i+1;jcbi.priority=rand()%100+1;jcbi.quick=rand()%5+1;jcbi.requesttime=rand()%1000+1;void FCFS()/*FCFS函數*/int i;int w=0,t=0; int Waittime=0;/*給waitime賦值*/cout<<"This is frist come fist server:"<<endl;for(i=0;i<

7、jcbnum;i+)/*for循環(huán)語句*/cout<<"The NO."<<jcbi.ID<<"JCB enter Memory."<<endl;Waittime+=jcbi.requesttime;w=(Waittime-t)/(jcbi.requesttime);cout<<"帶權周轉時間為："<<w<<endl; t+;void SJF()/*SJF函數*/int i,j,dest ,Waittime,w,t=0;/*定義的變量*/cout<

8、;<"This is shortest job first:"<<endl;while(jcbnum>0)dest=0;for(i=0;i<jcbnum;i+)/*for循環(huán)語句*/if(jcbdest.requesttime>jcbi.requesttime)/*條件語句*/dest=i;cout<<"The NO."<<jcbdest.ID<<"JCB enter Mermory"<<endl; Waittime+=jcbdest.requestt

9、ime;w=(Waittime-t)/(jcbdest.requesttime);cout<<"帶權周轉時間為："<<w<<endl;t+;for(j=dest;j<jcbnum-1;j+)/*用for語句進行賦值*/jcbj.ID=jcbj+1.ID;jcbj.requesttime=jcbj+1.requesttime;jcbnum-;void HRN()/*HRN函數*/int i,j,dest;/*定義的變量*/int waittime=0;/*給waitime賦值*/cout<<"This is Hi

10、ghest responseratio first"<<endl;while(jcbnum>0)dest=0;for(i=0;i<jcbnum;i+)/*for循環(huán)語句*/if(waittime/(jcbdest.requesttime)>(waittime/(jcbi.requesttime)/*條件語句*/dest=i;cout<<"The NO."<<jcbdest.ID<<"JCB enter Memory."<<endl;waittime+=jcbdest.

11、requesttime;/*給waittime賦新值*/for(j=dest;j<jcbnum-1;j+)/*用for語句進行賦值*/jcbj.ID=jcbj+1.ID;jcbj.requesttime=jcbj+1.requesttime;jcbnum-;16 運行結果及分析（1）FCFS算法運行結果（2）SJF算法運行結果：（3）HRN算法運行結果17 心得體會整個設計中最麻煩的就是程序模塊的劃分和各模塊之間接口設計，編程經常犯想當然的錯誤，出現了不少奇怪的錯誤。再調試中嘗試使用了分割法,對錯誤模塊進行定位,再進行排查.在算法實現上要有一定的思路體現設計的目的。同時上機調試也是十分重

12、要的，在調試的過程中能夠不斷的發(fā)現在編寫算法時應該注意的一些細節(jié)和算法語句的非法使用，在調試過程中通過對算法的不斷測試、更正、擴充功能、修飾細節(jié)，使算法程序不斷的得到完善。題目2 銀行家算法的實現11 題目的主要研究內容及預期達到的目標（1）編程序模擬實現銀行家算法。（2）基本完成了模擬實現銀行家算法。12 題目研究的工作基礎或實驗條件（1）硬件環(huán)境：windows系統（2）軟件環(huán)境：C語言 13 設計思想 （1）銀行家算法假設在進程并發(fā)執(zhí)行時進程i提出請求j類資源k個后，表示Requestij=k。系統按下述步驟進行安全檢查：1）如果RequestiNeedi則繼續(xù)以下檢查，否則顯示需求申請

13、超出最大需求值的錯誤。2）如果RequestiAvailable則繼續(xù)以下檢查，否則顯示系統無足夠資源，Pi阻塞等待。3）系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij;4）系統執(zhí)行安全性算法，檢查此次資源分配后，系統是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則， 將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。（2）安全性算法1）設置兩個向量

14、： 工作向量Work: 它表示系統可提供給進程繼續(xù)運行所需的各類資源數目，它含有m個元素，在執(zhí)行安全算法開始時，Work=Available; Finish: 它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false; 當有足夠資源分配給進程時， 再令Finishi=true。2）從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到， 執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。3）當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行： Workj=Worki+Allocationi,j

15、; Finishi=true; go to step 2; 4）如果所有進程的Finishi=true都滿足， 則表示系統處于安全狀態(tài)；否則，系統處于不安全狀態(tài)。結束 否是申請失敗。以上分配作廢，恢復原來的分配狀態(tài)：Availablej = Availablej + RequestijAllocationij= AllocationijRequestijNeedij = Needij+RequestijNYNYRequestij> Needij出錯返回：return(error)Requestij> Availablej出錯返回：(進程阻塞)return(error)Availab

16、lej = Availablej RequestijAllocationij= Allocationij + RequestijNeedij = Needij Requestij假定分配：輸入初始參數（資源分配及請求情況）開始 假定分配之后，系統安全嗎？申請成功。輸出各種數據的變化銀行家算法流程圖14 流程圖15 主要程序代碼#include <iostream>using namespace std;#define MAXPROCESS 50 /*最大進程數*/#define MAXRESOURCE 100 /*最大資源數*/int AVAILABLEMAXRESOURCE; /

17、*可用資源數組*/int MAXMAXPROCESSMAXRESOURCE; /*最大需求矩陣*/int ALLOCATIONMAXPROCESSMAXRESOURCE; /*分配矩陣*/int NEEDMAXPROCESSMAXRESOURCE; /*需求矩陣*/int REQUESTMAXPROCESSMAXRESOURCE; /*進程需要資源數*/bool FINISHMAXPROCESS; /*系統是否有足夠的資源分配*/int pMAXPROCESS; /*記錄序列*/int m,n; /*m個進程,n個資源*/void Init();bool Safe();void Dijkstr

18、a();int main() Init(); Safe(); Dijkstra();void Init() /*初始化算法*/ int i,j; cout<<"請輸入進程的數目:" cin>>m; cout<<"請輸入資源的種類:" cin>>n; cout<<"請輸入每個進程最多所需的各資源數,按照"<<m<<"x"<<n<<"矩陣輸入"<<endl; for(i=0;i&l

19、t;m;i+) for(j=0;j<n;j+) cin>>MAXij; cout<<"請輸入每個進程已分配的各資源數,也按照"<<m<<"x"<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>ALLOCATIONij; NEEDij=MAXij-ALLOCATIONij; if(NEEDij<0) cout<<"您輸入的第"

20、<<i+1<<"個進程所擁有的第"<<j+1<<"個資源數錯誤,請重新輸入:"<<endl; j-; continue; cout<<"請輸入各個資源現有的數目:"<<endl; for(i=0;i<n;i+) cin>>AVAILABLEi; void Dijkstra() /*銀行家算法*/ int i,cusneed; char again; while(1) cout<<"請輸入要申請資源的進程號(注:第

21、1個進程號為0,依次類推)"<<endl; cin>>cusneed; cout<<"請輸入進程所請求的各資源的數量"<<endl; for(i=0;i<n;i+) cin>>REQUESTcusneedi; for(i=0;i<n;i+) if(REQUESTcusneedi>NEEDcusneedi) cout<<"您輸入的請求數超過進程的需求量!請重新輸入!"<<endl; continue; if(REQUESTcusneedi>

22、AVAILABLEi) cout<<"您輸入的請求數超過系統有的資源數!請重新輸入!"<<endl; continue; for(i=0;i<n;i+) AVAILABLEi-=REQUESTcusneedi; ALLOCATIONcusneedi+=REQUESTcusneedi; NEEDcusneedi-=REQUESTcusneedi; if(Safe() cout<<"同意分配請求!"<<endl; else cout<<"您的請求被拒絕!"<<e

23、ndl; for(i=0;i<n;i+) AVAILABLEi+=REQUESTcusneedi; ALLOCATIONcusneedi-=REQUESTcusneedi; NEEDcusneedi+=REQUESTcusneedi; for(i=0;i<m;i+) FINISHi=false; cout<<"您還想再次請求分配嗎?是請按y/Y,否請按其它鍵"<<endl; cin>>again; if(again='y'|again='Y') continue; break; bool Saf

24、e() /*安全性算法*/ int i,j,k,l=0; int WorkMAXRESOURCE; /*工作數組*/ for(i=0;i<n;i+) Worki=AVAILABLEi; for(i=0;i<m;i+) FINISHi=false; for(i=0;i<m;i+) if(FINISHi=true) continue; else for(j=0;j<n;j+) if(NEEDij>Workj) break; if(j=n) FINISHi=true; for(k=0;k<n;k+) Workk+=ALLOCATIONik; pl+=i; i=-1

25、; else continue; if(l=m) cout<<"系統是安全的"<<endl; cout<<"安全序列:"<<endl; for(i=0;i<l;i+) cout<<pi; if(i!=l-1) cout<<"->" cout<<""<<endl; return true; cout<<"系統是不安全的"<<endl; return false; 16

26、 運行結果及分析17 心得體會整個設計中最麻煩的就是程序模塊的劃分和各模塊之間接口設計，編程經常犯想當然的錯誤，出現了不少奇怪的錯誤。再調試中嘗試使用了分割法,對錯誤模塊進行定位,再進行排查.在算法實現上要有一定的思路體現設計的目的。同時上機調試也是十分重要的，在調試的過程中能夠不斷的發(fā)現在編寫算法時應該注意的一些細節(jié)和算法語句的非法使用，在調試過程中通過對算法的不斷測試、更正、擴充功能、修飾細節(jié)，使算法程序不斷的得到完善。題目3 磁盤調度算法的模擬11 題目的主要研究內容及預期達到的目標（1）編程序模擬實現磁盤調度算法中的FCFS、SSTF、SCAN和CSCAN算法。（2）基本完成了模擬實現

27、FCFS、SSTF、SCAN和CSCAN調度算法。12 題目研究的工作基礎或實驗條件（1）硬件環(huán)境：windows系統（2）軟件環(huán)境： C語言13 設計思想 （1） 先來先服務(First-Come，First-Served，FCFS):這是一種簡單的磁盤調度算法。它根據進程請求訪問磁盤的先后次序進行調度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平均尋道時間可能較長。(2) 最短尋道時間優(yōu)先(ShortestSeekTimeFirst，SSTF):該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所

28、在的磁道距離最近，以使每次的尋道時間最短，但這種調度算法卻不能保證平均尋道時間最短。(3) 掃描(SCAN)算法:SCAN算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，SCAN算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁道，在當前磁道之內，從而避免了饑餓現象的出現。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調度算法。(4) 循環(huán)掃描(CSCAN)算法:處理該

29、進程的請求，致使該進程的請求被嚴重地推遲。為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構成循環(huán)，進行掃描。14 流程圖（1）FCFS算法流程圖：（2）SSTF算法流程圖：（3）SCAN算法:（4）CSCAN算法：15 主要程序代碼#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<math.h>#include<time.h>typedef stru

30、ct int n;int visited;L;void fifo(int s,int a,int n);void zuijin(int s,int a,int n);void scan(int s,int a,int n,int z);void cscan(int s,int a,int n,int z);int a;int NG=0;float Nsum=0;void main() int string50; int i; int j=0; int n; int f; int N; printf("輸入當前磁道號(0-200):"); scanf("%d&quo

31、t;,&a); printf("輸入要訪問的磁道數量(0-50)："); scanf("%d",&n); for(j;j<n;j+) printf("輸入尋道序列串："); scanf("%d",&stringj); printf("-n"); printf("| 0.退出 |n"); printf("| 1.先來先服務 |n"); printf("| 2.最短尋道時間優(yōu)先 |n"); printf(&qu

32、ot;| 3.電梯調度算法 |n"); printf("| 4.循環(huán)掃描算法 |n"); printf("| 5.返回菜單 |n"); printf("-n"); printf("選擇："); while(i!=0) scanf("%d",&i); switch(i) case 0:i=0; break; case 1:fifo(string,a,n); break; case 2:zuijin(string,a,n); break; case 3:printf("輸

33、入磁頭移動方向(0 向內 1向外)："); scanf("%d",&f); scan(string,a,n,f); break; case 4:printf("輸入磁頭移動方向(0 向內 1向外)："); scanf("%d",&f); cscan(string,a,n,f); break; case 5:printf("-n"); printf("| 0.退出 |n"); printf("| 1.先來先服務 |n"); printf("|

34、 2.最短尋道時間優(yōu)先 |n"); printf("| 3.電梯調度算法 |n"); printf("| 4.循環(huán)掃描算法 |n"); printf("| 5.返回菜單 |n"); printf("-n"); printf("選擇："); break; void fifo(int s,int a,int n)int i=0,m;float sum=0;printf("先來先服務算法：n");printf("-n");printf("磁道

35、號|移動距離n");while(i<n)if(a>si)m=a-si;else m=si-a;a=si;printf("%6d|%6dn",si,m);sum=sum+float(m);i+;printf("n-n");printf("平均尋道數：%.1fn",sum/n);void zuijin(int s,int a,int n) int m; L l50;float sum=0; printf("最短尋道時間優(yōu)先算法：n");printf("-n");printf(&

36、quot;磁道號|移動距離n");for(int i=0;i<n;i+) li.n=si; li.visited=0;for(int j=0;j<n;j+)int s=1000;for(int k=0;k<n;k+)if(lk.visited=0) m=abs(lk.n-a); if(m<s)s=m; for(int p=0;p<n;p+)if(lp.visited=0)if(s=abs(lp.n-a)lp.visited=1;a=lp.n;printf("n%6d|%6d",lp.n,s);sum=sum+float(s);prin

37、tf("n-n"); printf("平均尋道數：%.1fn",sum/n);void scan(int s,int a,int n,int z) int m;int count1=0,count2=0;int x=0;L l50;L k50;float sum=0; printf("電梯調度算法：n");printf("-n");printf("磁道號|移動距離n"); for(int i=0;i<n;i+)if(si>a)lcount1.n=si; lcount1.visited

38、=0;count1+;for(int j=0;j<n;j+)if(sj<a)kcount2.n=sj; kcount2.visited=0;count2+; while(x<n) if(z=1)for(int i=0;i<count1;i+) int s=1000; for(int j=0;j<count1;j+) if(lj.visited=0) m=abs(lj.n-a); if(m<s)s=m; for(int p=0;p<count1;p+) if(lp.visited=0)if(s=abs(lp.n-a)lp.visited=1;a=lp.n

39、;printf("n%6d|%6d",lp.n,s);sum=sum+float(s);x+; z=0; if(z=0)for(int i=0;i<count2;i+) int s=1000; for(int j=0;j<count2;j+) if(kj.visited=0) m=abs(kj.n-a); if(m<s)s=m; for(int p=0;p<count2;p+) if(kp.visited=0)if(s=abs(kp.n-a)kp.visited=1;a=kp.n;printf("n%6d|%6d",kp.n,s)

40、;sum=sum+float(s);x+; z=1; Nsum=sum;NG=a; printf("n-n"); printf("平均尋道數：%.1fn",sum/n);void cscan(int s,int a,int n,int z)int m;L l50;int t;int y=0;float sum=0.0; printf("循環(huán)掃描算法：n");printf("-n");printf("磁道號|移動距離n"); for(int i=0;i<n;i+) li.n=si; li.v

41、isited=0;for(int k=0;k<n-1;k+) t=lk+1.n; for(int p=0;p<k+1;p+) if(lp.n>t)break; if(p>k)continue; for(int j=k;j>p-1;j-)lj+1.n=lj.n; lp.n=t;while(y<n)int j;if(z=1) for(j=0;j<n;j+)if(lj.n>a)break; for(int k=j;k<n;k+) m=lk.n-a; lk.visited=1; a=lk.n; y+; printf("n%6d|%6d&q

42、uot;,lk.n,m); sum=sum+float(m); for(int h=0;h<j;h+) m=abs(lh.n-a); lh.visited=1; a=lh.n; y+; printf("n%6d|%6d",lh.n,m); sum=sum+float(m); if(z=0) for(j=0;j<n;j+)if(lj.n<a)break; for(int h=0;h<j;h+) m=abs(lh.n-a); lh.visited=1; a=lh.n; y+; printf("n%6d|%6d",lh.n,m); su

43、m=sum+float(m); for(int k=j;k<n;k+) m=abs(lk.n-a); lk.visited=1; a=lk.n; y+; printf("n%6d|%6d",lk.n,m); sum=sum+float(m); printf("n-n");printf("平均尋道數：%.1fn",sum/n);16 運行結果及分析(1)先來先服務算法運行結果：（2）最短尋道時間優(yōu)先算法運行結果：（3）SCAN算法運行結果：（4）CSCAN算法運行結果：17 心得體會整個設計中最麻煩的就是程序模塊的劃分和各模塊之間

44、接口設計，編程經常犯想當然的錯誤，出現了不少奇怪的錯誤。再調試中嘗試使用了分割法,對錯誤模塊進行定位,再進行排查.在算法實現上要有一定的思路體現設計的目的。同時上機調試也是十分重要的，在調試的過程中能夠不斷的發(fā)現在編寫算法時應該注意的一些細節(jié)和算法語句的非法使用，在調試過程中通過對算法的不斷測試、更正、擴充功能、修飾細節(jié)，使算法程序不斷的得到完善。題目4 讀者/寫者問題11 題目的主要研究內容及預期達到的目標（1）利用多進程或多線程模擬實現讀者/寫者問題。（2）基本完成了利用多進程或多線程模擬實現讀者/寫者問題。12 題目研究的工作基礎或實驗條件（1）硬件環(huán)境：windows系統（2）軟件環(huán)境

45、： C語言13 設計思想（1）讀者優(yōu)先 如果沒有寫者正在操作，則讀者不需要等待，用一個整型變量g_NumOfReading記錄讀者數目，用于確定是否釋放讀者線程，g_NumOfReading的初值為0.當線程開始調入時.每個讀者準備讀. 等待互斥信號,保證對g_NumOfReading的訪問,修改互斥.即g_NumOfReading+.而當讀者線程進行讀操作時,則讀者數目減少(g_NumOfReading-).當g_NumOfReading=0 時，說明所有的讀者都已經讀完.（2）寫者優(yōu)先寫者優(yōu)先與讀者不同之處在于一旦一個寫者到來，它應該盡快對文件進行寫操作，如果有一個寫者在等待，則新到來的讀

46、者不允許進行讀操作。為此應當填加一個整形變量g_NumOfWriteRequest，用于記錄正在等待的寫者的數目，g_NumOfWriteRequest的初值為0.當線程開始調入時.只允許一個寫者準備讀. 等待互斥信號,保證對g_NumOfWriteRequest 的訪問,修改互斥.即g_NumOfWriteRequest+.而當寫者線程進行讀操作時,則相應寫者數目減少(g_NumOfWriteRequest-).當g_NumOfWriteRequest=0 時，說明所有的讀者都已經讀完，離開臨界區(qū)喚醒讀者,釋放互斥信號.14 流程圖（1）讀者優(yōu)先流程圖：（2）寫者優(yōu)先流程圖：15 主要程序代

47、碼#include "windows.h" #include <conio.h> #include <stdlib.h> #include <fstream.h> #include <io.h> #include <string.h> #include <stdio.h> #define READER 'R' /讀者 #define WRITER 'W' /寫者 #define INTE_PER_SEC 1000 /每秒時鐘中斷的數目 #define MAX_THREAD_NUM 64 /最大線程數 #define MAX_FILE_NUM 32 /最大文件數目數 #define MAX_STR_LEN 32 /字符串的長度 int readcount=0; /讀者數目 int writecount=0; /寫者數目 CRITICAL_SECTION RP_Write; /臨界資源 CRITICAL_SECTION cs_Write; CRITICAL_SECTION cs_Read; struct ThreadInfo int serial; /線程序號 char entity; /線程類別(判斷是讀者還是寫