進(jìn)程調(diào)度算法 進(jìn)程調(diào)度算法磁盤(pán)調(diào)度算法銀行家算法操作系統(tǒng)課程設(shè)計(jì)大全

1、進(jìn)程調(diào)度算法 進(jìn)程調(diào)度算法磁盤(pán)調(diào)度算法銀行家算法操作系統(tǒng)課程設(shè)計(jì)大全 操作系統(tǒng)課程設(shè)計(jì)學(xué)院名稱(chēng)：專(zhuān)業(yè)班級(jí)：姓 名：學(xué) 號(hào)：說(shuō)明書(shū) 2010年7月16日評(píng)分標(biāo)準(zhǔn) 優(yōu)秀：有完整的符合標(biāo)準(zhǔn)的文檔，文檔有條理、文筆通順，格式正確，程序完全實(shí)現(xiàn)設(shè)計(jì)要求，獨(dú)立完成；良好：有完整的符合標(biāo)準(zhǔn)的文檔，文檔有條理、文筆通順，格式正確；程序完全實(shí)現(xiàn)設(shè)計(jì)要求，獨(dú)立完成，但存在少量錯(cuò)誤；中等：有完整的符合標(biāo)準(zhǔn)的文檔，有基本實(shí)現(xiàn)設(shè)計(jì)方案的軟件，設(shè)計(jì)方案正確； 及格：有完整的符合標(biāo)準(zhǔn)的文檔，有基本實(shí)現(xiàn)設(shè)計(jì)方案的軟件，設(shè)計(jì)方案基本正確；不及格：沒(méi)有完整的符合標(biāo)準(zhǔn)的文檔，軟件沒(méi)有基本實(shí)現(xiàn)設(shè)計(jì)方案，設(shè)計(jì)方案不正確。沒(méi)有獨(dú)立完成，

2、抄襲或雷同。 年 月 日目 錄 一進(jìn)程調(diào)度算法 二銀行家算法 三磁盤(pán)調(diào)度算法 4-23 頁(yè) 24-34 頁(yè) 35-46頁(yè)進(jìn)程調(diào)度算法1設(shè)計(jì)目的在多道程序設(shè)計(jì)中，經(jīng)常是若干個(gè)進(jìn)程同時(shí)處于就緒狀態(tài)，必須依照某種策略決定哪個(gè)進(jìn)程優(yōu)先占有處理機(jī)，因而必須解決進(jìn)程調(diào)度的問(wèn)題，進(jìn)程調(diào)度算法就是要解決進(jìn)程調(diào)度的問(wèn)題。 2. 任務(wù)及要求2.1 設(shè)計(jì)任務(wù)設(shè)計(jì)程序來(lái)模擬進(jìn)程的四種調(diào)度算法，模擬實(shí)現(xiàn)調(diào)度的基本功能。 2.2 設(shè)計(jì)要求產(chǎn)生的各種隨機(jī)數(shù)要加以限制，如alltime限制在40以?xún)?nèi)的整數(shù)。進(jìn)程的數(shù)量n不能取值過(guò)大。3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊PCB用結(jié)構(gòu)來(lái)描述

3、，包括以下字段：（1）進(jìn)程優(yōu)先數(shù)ID，其中0為閑逛進(jìn)程，用戶(hù)進(jìn)程的標(biāo)識(shí)數(shù)為1，2，3。 （2）進(jìn)程優(yōu)先級(jí)Priority，閑逛進(jìn)程（idle）的優(yōu)先級(jí)為0，用戶(hù)進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，優(yōu)先數(shù)越大，優(yōu)先級(jí)越高。（3）進(jìn)程占用的CPU時(shí)間CPUtime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4。 （4）進(jìn)程總共需要運(yùn)行時(shí)間Alltime，利用隨機(jī)函數(shù)產(chǎn)生。 （5）進(jìn)程狀態(tài)，0：就緒態(tài)；1：運(yùn)行態(tài)；2：阻塞態(tài)。 利用鏈表將數(shù)據(jù)連接起來(lái)，實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)。3.2 鏈表模塊 3.2.1 功能實(shí)現(xiàn)鏈表的存儲(chǔ)功能，以及實(shí)現(xiàn)存儲(chǔ)的查找功能。3.2.2 數(shù)據(jù)結(jié)構(gòu)構(gòu)造鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)，以及鏈表的初始化，鏈表的插入，鏈表

4、的長(zhǎng)3.2.3 算法 typedef structElemType *elem; int length; int listsize; SqList;Status InitList(SqList &l) l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!l.elem) exit(OVERFLOW); stsize) ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase) e

5、xit(OVERFLOW); L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType *q=&L.elemi-1, *p=&L.elemL.length-1; while(p>=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK; Status GetElem(SqList L,int i,ElemType &e) if(iL.length)return ERROR; elsereturn OK;void Outputlist(SqList &L) i

6、f(0=L.length)printf(elsefor(int i=0;iprintf(3.3 主函數(shù)模塊 3.3.1功能實(shí)現(xiàn)進(jìn)程調(diào)度的四種算法，以及人機(jī)交互的菜單。 3.3.2 數(shù)據(jù)結(jié)構(gòu)主要包括五個(gè)部分，分別是四種算法，和進(jìn)程的輸入和菜單部分，功能分別實(shí)現(xiàn)。 3.3.3算法void main() int number; PCB pcb100 ;srand(time(0); int max; int ppp100; int time=0; int time1; int m; int a100; a0=0;printf(*n printf(* printf(if(m!=1&&m!

7、=2&&m!=3&&m!=4) printf(if(m!=1&&m!=2&&m!=3&&m!=4) printf(scanf( printf(scanf( printf(scanf( printf(printf(for(int r=0;r for(int i=0;i pcbi.Priority=rand()%50; while(1)if(pcbi.Priority else break; pcbi.Alltime=rand()%40; while(1)if(pcbi.Alltimepcbi.Alltime=rand

8、()%40;elsebreak; if(m=1) printf( int coun=0; /計(jì)數(shù)變量 int wait100; /等待時(shí)間數(shù)組 wait0=0; int Allwait=0; for(int i1=0;i1為%dn coun+=pcbi1.Alltime; if(i1!=0) waiti1=pcbi1-1.Alltime+waiti1-1; for(int i2=0;i2 printf( if(m=2)int min=pcb0.Alltime;int wait1100;wait10=0;int in=0;int coun1=0;printf(度!*ncoutfor(i=0;ic

9、outprintf( for(i=0;imin=50;for(j=0;j作業(yè)優(yōu)先調(diào) if(pcbj.Alltimeif(m=3) printf( printf( for(int f=1;fint count=0,count1=0;for(int i=0;ipppi=pcbi.Priority;if(pcbi.Alltime!=0)count1+;count1-;time=time+count1*4;max=Max(ppp,number);if(pcbmax.Alltime=0)pppmax=-1;pcbmax.Priority=-1;max=Max(ppp,number);pcbmax.Pri

10、ority-=4;pcbmax.Alltime-=4;pcbmax.CPUtime+=4;if(pcbmax.Alltimepcbmax.Alltime=0; for(int w=0;w printf( 間n for(int k=0; kprintf(pcbk.Priority, pcbk.Alltime,pcbk.CPUtime); for(int l=0;l for(int k=0; kprintf(printf( printf( for(int f=1;f int count=0; for(i=0;i0) pcbi.Alltime-=4; continue; pcbi.CPUtime+=

11、4; if(pcbi.Alltime pcbi.Alltime=0; / printf( printf( for(int k=0; k / for(int l=0;l printf(4. 實(shí)驗(yàn)結(jié)果及分析4.1 實(shí)驗(yàn)結(jié)果先到先服務(wù)算法的實(shí)驗(yàn)結(jié)果如下： 最短作業(yè)優(yōu)先調(diào)度的實(shí)驗(yàn)結(jié)果如下： 優(yōu)先權(quán)調(diào)度算法的實(shí)驗(yàn)結(jié)果如下： 輪轉(zhuǎn)法調(diào)度的實(shí)驗(yàn)結(jié)果如下： 4.2 結(jié)果分析本次試驗(yàn)基本實(shí)現(xiàn)了進(jìn)程調(diào)度的四種算法，每一種算法都能模擬出算法的具體過(guò)程。相應(yīng)的結(jié)果也完全符合預(yù)想的結(jié)果。同時(shí)，對(duì)于算法的實(shí)踐編寫(xiě)進(jìn)一步增加了編程的技巧，以及編程的熟練程度。 銀行家算法 1設(shè)計(jì)目的銀行家算法是避免死鎖的一種十分重要的方法，

12、通過(guò)編寫(xiě)一個(gè)模擬的動(dòng)態(tài)的銀行家算法的程序，能夠進(jìn)一步加深對(duì)死鎖的理解，以及產(chǎn)生死鎖的必要條件。并掌握通過(guò)銀行家算法來(lái)避免死鎖。 2. 任務(wù)及要求2.1 設(shè)計(jì)任務(wù)根據(jù)銀行家算法的基本思想來(lái)設(shè)計(jì)程序，模擬銀行家算法的過(guò)程。用程序來(lái)實(shí)現(xiàn)銀行家算法的具體動(dòng)態(tài)過(guò)程。2.2 設(shè)計(jì)要求根據(jù)銀行家算法的基本思想，編寫(xiě)和調(diào)試一個(gè)能實(shí)現(xiàn)動(dòng)態(tài)的分配資源的模擬程序。并能夠有效的防止死鎖的發(fā)生。 3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程）銀行家算法的基本思想是，系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)受到進(jìn)程的請(qǐng)求后會(huì)試探性的把資源分配給他，現(xiàn)在系統(tǒng)將剩下的資源和進(jìn)程集合中其他進(jìn)程還需要的資源作對(duì)比，找出剩

13、余資源能滿足的進(jìn)程，從而保證進(jìn)程運(yùn)行完并釋放資源繼續(xù)滿足剩下進(jìn)程對(duì)資源的需要。最后檢查集合為空集時(shí)表明本次申請(qǐng)可行，系統(tǒng)繼續(xù)處于安全狀態(tài)，可以實(shí)施本次分配。否則不能實(shí)施本次分配。3.2 顯示資源矩陣 showdata() 模塊3.2.1 功能主要是顯示資源的矩陣，包括輸入的已分配的的資源矩陣，以及輸出的資源矩陣。3.2.2 數(shù)據(jù)結(jié)構(gòu)最大需求矩陣max以及已分配矩陣allocation，分別定義為m*n階的矩陣，利用二維數(shù)組來(lái)存儲(chǔ)。3.2.3 算法 void showdata() /顯示資源矩陣int i,j;coutfor(i=0;icoutcoutfor (j=0;jcoutcoutcout

14、coutcoutfor(j=0;jfor(i=0;icoutcoutcoutfor(i=0;icoutfor(j=0;jcoutcoutfor(j=0;jcoutcoutfor(j=0;jcoutcout 3.3 申請(qǐng)資源判定模塊3.3.1功能利用銀行家實(shí)現(xiàn)對(duì)申請(qǐng)的資源進(jìn)行判定。3.3.2 數(shù)據(jù)結(jié)構(gòu)對(duì)已經(jīng)存儲(chǔ)的矩陣進(jìn)行比較。3.3.3算法 void share()/利用銀行家算法對(duì)申請(qǐng)資源對(duì)進(jìn)行判定 char ch;int i=0,j=0;ch=y;coutcin>>i;/輸入須申請(qǐng)的資源號(hào)coutfor(j=0;j coutcin>>Requestj;/輸入需要申請(qǐng)的

15、資源for (j=0;j if(Requestj>Needij)/判斷申請(qǐng)是否大于需求，若大于則出錯(cuò)coutch=n;break;elseif(Requestj>Avaliablej)/判斷申請(qǐng)是否大于當(dāng)前資源，若大于則coutcoutch=n;break; if(ch=y)changdata(i);/根據(jù)進(jìn)程需求量變換資源showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 3.4 主函數(shù)模塊3.4.1功能實(shí)現(xiàn)銀行家算法對(duì)資源的增加、刪除、修改。 3.4.2 數(shù)據(jù)結(jié)構(gòu) 對(duì)已經(jīng)完成的模塊進(jìn)行功能集成。3.4.3算法 int main

16、() int i,j,number,choice,m,n,flag;char ming;cout cout *coutcoutcin>>n;coutN=n;for(i=0;icoutcin>>ming;namei=ming;coutcin>>number;Avaliablei=number;coutcoutcin>>m;M=m;coutfor(j=0;jcin>>Maxij;doflag=0;coutfor(i=0;ifor(j=0;j cin>>Allocationij;if(Allocationij>Maxij)

17、flag=1;Needij=Maxij-Allocationij;if(flag)cout showdata(); /顯示各種資源safe(); /用銀行家算法判定系統(tǒng)是否安全while(choice) cout coutcoutcoutcoutcoutcout coutcoutcin>>choice;switch(choice) case 1: addresources();break; case 2: delresources();break;case 3: changeresources();break;case 4: share();break;case 5: addpro

18、cess();break;case 0: choice=0;break;default: cout return 1;4. 實(shí)驗(yàn)結(jié)果及分析4.1 實(shí)驗(yàn)結(jié)果 4.2 結(jié)果分析銀行家算法就是在系統(tǒng)分配資源時(shí)，找到一個(gè)安全序列，使得進(jìn)程間不會(huì)發(fā)生死鎖。若發(fā)生死鎖則讓進(jìn)程等待。4.3實(shí)驗(yàn)總結(jié)通過(guò)本次試驗(yàn)，加深了我對(duì)銀行家算法的理解，掌握了如何利用銀行家算法來(lái)避免死鎖。通過(guò)對(duì)代碼的編寫(xiě)也加深了我對(duì)數(shù)據(jù)結(jié)構(gòu)的進(jìn)一步理解。 磁盤(pán)調(diào)度算法1設(shè)計(jì)目的加深對(duì)操作系統(tǒng)的磁盤(pán)調(diào)度的進(jìn)一步理解以及進(jìn)一步的認(rèn)識(shí)。加強(qiáng)實(shí)踐能力和動(dòng)手動(dòng)腦能力，同時(shí)加深對(duì)磁盤(pán)調(diào)度概念的理解，同時(shí)也再一次提高了自己編程的能力。2. 任務(wù)及要求2

19、.1 設(shè)計(jì)任務(wù)分析設(shè)計(jì)模擬磁盤(pán)管理系統(tǒng)的方法，加深對(duì)磁盤(pán)調(diào)度算法的了解以及個(gè)算法的特點(diǎn)。2.2 設(shè)計(jì)要求分別設(shè)計(jì)出先來(lái)先服務(wù)算法，最短尋道時(shí)間優(yōu)先算法，掃描算法。并分別求出它們的平均尋道時(shí)間。3. 算法及數(shù)據(jù)結(jié)構(gòu)3.1算法的總體思想（流程） 1.先來(lái)先服務(wù)的算法，即先來(lái)的請(qǐng)求先被響應(yīng)。FCFS算法看起來(lái)是比較合理的算法，但是當(dāng)請(qǐng)求頻率過(guò)高的時(shí)候FCFS算法的響應(yīng)時(shí)間就會(huì)大大的延長(zhǎng)，這也是最基本的算法，直接實(shí)現(xiàn)的是由輸入的順序來(lái)順序的執(zhí)行。2.最短尋道時(shí)間優(yōu)先算法，要求訪問(wèn)的磁道，與當(dāng)前磁頭所在的磁道的距離最近，從而以使每次的尋道時(shí)間最短。3.掃描磁盤(pán)調(diào)度，該算法不考慮與訪問(wèn)磁道與當(dāng)前磁道的距離

20、，更優(yōu)先考慮的磁頭當(dāng)前的移動(dòng)方向，例如，當(dāng)磁頭正在有向外移動(dòng)時(shí)，SCAN算法所考慮的下一個(gè)訪問(wèn)對(duì)象，應(yīng)是其與訪問(wèn)的磁道，即在當(dāng)前磁道之外，又是最近的。這樣磁頭逐漸的從外向里移動(dòng)，直至再無(wú)更里面的磁道要訪問(wèn)，從而避免了出饑餓的情況。 3.2先來(lái)先服務(wù)模塊3.2.1 功能實(shí)現(xiàn)磁盤(pán)調(diào)度的先來(lái)先服務(wù)調(diào)度。 3.2.2 數(shù)據(jù)結(jié)構(gòu)用鏈表來(lái)存儲(chǔ)輸入的數(shù)據(jù)，即各待訪問(wèn)的磁道。然后遍歷這個(gè)鏈表，依次對(duì)這個(gè)鏈表進(jìn)行訪問(wèn)，從而實(shí)現(xiàn)先來(lái)先服務(wù)調(diào)度。3.2.3 算法 void fcfs(Node *head,int c,int f) /先來(lái)先服務(wù)算法void print(Node *);Node *l; /,*m,*n

21、;float num=0;l=head->next;for(int i=0;i num+=abs(l->data-f);f=l->data;l=l->next;num=num/c;coutprint(head);cout 3.3最短尋道時(shí)間優(yōu)先模塊 3.3.1功能實(shí)現(xiàn)磁盤(pán)調(diào)度的最短尋道時(shí)間調(diào)度。 3.3.2 數(shù)據(jù)結(jié)構(gòu)以鏈表來(lái)存儲(chǔ)數(shù)據(jù)，通過(guò)循環(huán)訪問(wèn)鏈表來(lái)尋找距本次磁道的最短距離，依次這樣訪問(wèn)。3.3.3算法、 void sstf(Node *head,int c,int f)/最短尋道時(shí)間優(yōu)先算法void print(Node *);Node *p,*q,*r,*s,*l

22、,*m;l=(Node *)malloc(sizeof(Node);l->next=NULL;m=l;q=head;p=head->next;s=head;r=head->next;for(int i=0;iint min=abs(f-r->data);for(int j=0;jp=p->next;q=q->next;if(abs(f-p->data)min=abs(f-p->data);r=p;s=q;num+=abs(f-r->data);f=r->data;s->next=r->next;r->next=NUL

23、L;m->next=r;m=r;q=head;p=head->next;s=head;r=head->next;coutprint(l);cout 3.4 掃描算法模塊 3.4.1功能實(shí)現(xiàn)磁盤(pán)調(diào)度的掃描算法。 3.4.2 數(shù)據(jù)結(jié)構(gòu)以鏈表來(lái)存儲(chǔ)數(shù)據(jù)，以開(kāi)始磁道為限來(lái)分磁道，分為大于的和小于的，然后分別訪問(wèn)兩部分，按照開(kāi)始的方向進(jìn)行訪問(wèn)。3.4.3算法 void scan(Node *head,int c,int f) /掃描算法 void print(Node *);int min,max,i=0,j=0;float num=0;Node *p,*q,*r,*s,*m,*n,*

24、x,*y;r=(Node *)malloc(sizeof(Node);/存放比開(kāi)始磁道小的磁道r->next=NULL;s=r;m=(Node *)malloc(sizeof(Node); /存放比開(kāi)始磁道大的磁道m(xù)->next=NULL;n=m;x=(Node *)malloc(sizeof(Node);x->next=NULL;y=x;q=head;p=head->next;while(p->next!=NULL)if(p->data-f>0)q->next=p->next;p->next=NULL;n->next=p;n=

25、p;p=q->next;i+;elseq->next=p->next;p->next=NULL;s->next=p;s=p;p=q->next;j+; if(p->data>=f)n->next=p;n=p;i+;elses->next=p;s=p;j+;q=r; /對(duì)比開(kāi)始磁道小的磁道排序p=r->next;while(q->next->next!=NULL)q=q->next;p=q->next;max=q->data;while(p->next!=NULL)if(p->data>max)max=p->data;p-&