第一篇：《操作系統(tǒng)原理》算法總結(jié)
《操作系統(tǒng)原理》算法總結(jié)
一、進程(作業(yè))調(diào)度算法
? 先來先服務(wù)調(diào)度算法（FCFS）：每次調(diào)度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執(zhí)行。該進程一旦占有了處理器，它就一直運行下去，直到該進程完成或因發(fā)生事件而阻塞，才退出處理器。特點：利于長進程，而不利于短進程。
? 短進程（作業(yè)）優(yōu)先調(diào)度算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之占有處理器并執(zhí)行，直到該進程完成或因發(fā)生事件而阻塞，然后退出處理器，再重新調(diào)度。
? 時間片輪轉(zhuǎn)調(diào)度算法 ：系統(tǒng)將所有的就緒進程按進入就緒隊列的先后次序排列。每次調(diào)度時把CPU分配給隊首進程，讓其執(zhí)行一個時間片，當(dāng)時間片用完，由計時器發(fā)出時鐘中斷，調(diào)度程序則暫停該進程的執(zhí)行，使其退出處理器，并將它送到就緒隊列的末尾，等待下一輪調(diào)度執(zhí)行。
? 優(yōu)先數(shù)調(diào)度算法 ：它是從就緒隊列中選擇一個優(yōu)先權(quán)最高的進程，讓其獲得處理器并執(zhí)行。
? 響應(yīng)比高者優(yōu)先調(diào)度算法：它是從就緒隊列中選擇一個響應(yīng)比最高的進程，讓其獲得處理器執(zhí)行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先后次序，也不會使長進程長期得不到服務(wù)，因此是一個比較全面考慮的算法，但每次進行調(diào)度時，都需要對各個進程計算響應(yīng)比。所以系統(tǒng)開銷很大，比較復(fù)雜。
? 多級隊列調(diào)度算法 基本概念：
作業(yè)周轉(zhuǎn)時間（Ti）＝完成時間(Tei)－提交時間(Tsi)
作業(yè)平均周轉(zhuǎn)時間(T)＝周轉(zhuǎn)時間/作業(yè)個數(shù)
作業(yè)帶權(quán)周轉(zhuǎn)時間（Wi）＝周轉(zhuǎn)時間/運行時間
響應(yīng)比＝（等待時間＋運行時間）/運行時間
二、存儲器連續(xù)分配方式中分區(qū)分配算法
? 首次適應(yīng)分配算法（FF）：對空閑分區(qū)表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)長度要求的空閑區(qū)，分割這個空閑區(qū)，一部分分配給作業(yè)，另一部分仍為空閑區(qū)。
? 循環(huán)首次適應(yīng)算法：每次分配均從上次分配的位置之后開始查找。
? 最佳適應(yīng)分配算法(BF)：是按作業(yè)要求從所有的空閑分區(qū)中挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣可保證不去分割一個更大的區(qū)域，使裝入大作業(yè)時比較容易得到滿足。為實現(xiàn)這種算法，把空閑區(qū)按長度遞增次序登記在空閑區(qū)表中，分配時，順序查找。
三、頁面置換算法
? 最佳置換算法（OPT)：選擇以后永不使用或在最長時間內(nèi)不再被訪問的內(nèi)存頁面予以淘汰。
? 先進先出置換算法（FIFO）：選擇最先進入內(nèi)存的頁面予以淘汰。
? 最近最久未使用算法（LRU）：選擇在最近一段時間內(nèi)最久沒有使用過的頁，把它淘汰。
? 最少使用算法（LFU）：選擇到當(dāng)前時間為止被訪問次數(shù)最少的頁轉(zhuǎn)換。
四、磁盤調(diào)度
? 先來先服務(wù)（FCFS）：是按請求訪問者的先后次序啟動磁盤驅(qū)動器，而不考慮它們要訪問的物理位置
? 最短尋道時間優(yōu)先（SSTF）：讓離當(dāng)前磁道最近的請求訪問者啟動磁盤驅(qū)動器，即是讓查找時間最短的那個作業(yè)先執(zhí)行，而不考慮請求訪問者到來的先后次序，這樣就克服了先來先服務(wù)調(diào)度算法中磁臂移動過大的問題
? 掃描算法（SCAN）或電梯調(diào)度算法：總是從磁臂當(dāng)前位置開始，沿磁臂的移動方向去選擇離當(dāng)前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調(diào)度方法下磁臂的移動類似于電梯的調(diào)度，所以它也稱為電梯調(diào)度算法。
? 循環(huán)掃描算法（CSCAN）：循環(huán)掃描調(diào)度算法是在掃描算法的基礎(chǔ)上改進的。磁臂改為單項移動，由外向里。當(dāng)前位置開始沿磁臂的移動方向去選擇離當(dāng)前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業(yè)請求。
第二篇：操作系統(tǒng)實驗報告(clock算法)
實驗四 頁面置換算法
一、實驗?zāi)康?/p>
本實驗主要對操作系統(tǒng)中請求分頁式內(nèi)存管理及其應(yīng)用的一些關(guān)鍵算法進行模擬。學(xué)生通過設(shè)計與實現(xiàn)Clock算法，能夠加強對相應(yīng)理論的理解，并對了解操作系統(tǒng)內(nèi)部的基本處理原理與過程也有很多益處。
二、實驗要求
基本要求：描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實現(xiàn)。
1）初始化：輸入作業(yè)可占用的總頁框數(shù)，初始化置空。
2）輸入請求序列：輸入一個作業(yè)頁號訪問請求序列，依次占用相應(yīng)頁框，直至全部占用； 3）Clock算法：當(dāng)頁框全部占用后，對于后續(xù)新的頁號訪問請求，執(zhí)行Clock算法，淘汰1個頁面后裝入新的頁號。
4）顯示當(dāng)前分配淘汰序列：顯示淘汰的頁號序列。
描述Clock算法的基本原理、必要的數(shù)據(jù)結(jié)構(gòu)、算法執(zhí)行流程圖、編碼實現(xiàn)。
三、實驗內(nèi)容
1)基本原理
時鐘頁面置換算法是把所有的頁面都保存在一個類似鐘面的環(huán)形鏈表中，一個表針指向最老的頁面，如圖所示。
當(dāng)發(fā)生缺頁中斷時，算法首先檢查表針指向的頁面，如果它的R位是0就淘汰該頁面，并把新的頁面插入這個位置，然后把表針前移一個位置；如果R位是1就清除R位并把表針前移一個位置，重復(fù)這個過程直到找到了一個R位為0的頁面為止。2)算法流程設(shè)計
主函數(shù)流程: STEP1:輸入分配的頁框數(shù)，頁面訪問次數(shù)和要訪問的頁面號序列 STEP2:內(nèi)存頁面初始化。內(nèi)存中頁面的數(shù)據(jù)結(jié)構(gòu)為單循環(huán)鏈表，含有頁號值yehao和訪問位值a。開始時頁號均為-1，訪問位為0.STEP3：測試數(shù)據(jù)。具體算法是依要訪問的頁面號，調(diào)用find()函數(shù)查找是否已經(jīng)存在于內(nèi)存中。若存在，則修改其訪問位為1.若不存在，觸發(fā)缺頁中斷，調(diào)用tihuan()函數(shù)。最后，打印當(dāng)前內(nèi)存狀態(tài)。如此循環(huán)直至測試串都訪問完畢。3)主要函數(shù)實現(xiàn)
a)Makenode(double)函數(shù)：用于初始化一個節(jié)點。
b)Find（double）函數(shù)：依據(jù)輸入的頁號，查詢內(nèi)存中是否已存在此頁面。若存在返回值1，不存在返回值0.c)Tihuan（double）函數(shù)：在發(fā)生缺頁中斷時，時鐘指針查找訪問位為0的頁面進行替換，指針掃過的頁面訪問位置0，新加入的頁面訪問位置1。替換后指針下移。
d)Print_state()函數(shù)：打印當(dāng)前內(nèi)存中存在的頁面的狀態(tài)以及當(dāng)前時鐘指針所指向的頁面位置。
4)測試數(shù)據(jù)
輸入：
輸入分配的頁框數(shù) 3 輸入頁面訪問次數(shù) 15 輸入要訪問的頁面號序列 3 4 2 6 4 3 7 4 3 6 3 4 8 4 6 輸出（僅最后一項）：
5)結(jié)果分析
以下是clock算法對應(yīng)輸入頁面號序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6的分析表
四、實驗總結(jié)
1.加深對clock算法的理解。通過與其他算法的比較，我也了解了他們的異同之處。Clock算法其實是一種改進的第二次機會算法，它通過設(shè)置訪問位，找到最早最不常訪問的頁面，即標號為0的頁面。之所以叫clock算法，依我理解是將內(nèi)存中的排列順序附上時間的概念，clock指針掃過的頁面要將他們1置0就是基于這個思想，因為他們都是沒被訪問的，且在時鐘上的排列按照訪問時間順序。這樣就保證了每次替換的都是最早進來的且不最常訪問的頁面。
2.在時鐘內(nèi)存結(jié)構(gòu)的代碼實現(xiàn)上，我使用了自建的單循環(huán)鏈表，對其進行順序地遍歷即可實現(xiàn)時鐘指針的移動。另外通過全局變量node *r（時鐘）node *start（開始頁面項）node *r_prev（時鐘指針的前驅(qū)）的設(shè)置，方便了有關(guān)算法的實現(xiàn)。
3.此算法較為簡單，還有一種改進版的clock算法，增加了一個修改位，表示頁框是否被修改過。這樣的設(shè)計更加符合現(xiàn)在操作系統(tǒng)的調(diào)度原則。
參考文獻
[1]（美）Stanley B.Lippman 等 著 李師賢 等 譯.C++ Primer中文版（第4版）.人民郵電出版社, 2006-03-01 [2] 蔣愛軍，李師賢，梅曉勇 著.C++ Primer習(xí)題解答（第4版）.人民郵電出版社, 2007-02-01 [3] 塔嫩鮑姆（Tanenbaum.A.S），陳向群，馬洪兵 著.現(xiàn)代操作系統(tǒng)（原書第3版）.機械工業(yè)出版社, 2009-07-01 [4] 張堯?qū)W，史美林，張高.計算機操作系統(tǒng)教程.清華大學(xué)出版社, 2006-10-01 [5] 王曉東 著.數(shù)據(jù)結(jié)構(gòu)（STL框架）.清華大學(xué)出版社, 2009-09-01
第三篇：操作系統(tǒng)銀行家算法實驗報告
實驗四
死鎖
一、實驗?zāi)康?/p>
當(dāng)系統(tǒng)的總資源數(shù)m小于或等于所有進程對對資源的最大需求時，就可能產(chǎn)生 死鎖。死鎖會引起計算機系統(tǒng)的癱瘓。銀行家算法是在實現(xiàn)資源分配時避免死鎖的一個著名算法，該算法是在能確保系統(tǒng)處于安全狀態(tài)時才把資源分配給申請者。通過本實驗使學(xué)生能進一步理解死鎖的概念，并能選擇一個算法來避免死鎖。
二、實驗題目
系統(tǒng)中有m個同類資源被n個進程共享，每個進程對資源的最大需求數(shù)分別為S1, S2,…,Sn，且 Max(Si)<=m,(i=1,2,…n)。進程可以動態(tài)地申請資源和釋放資源。編寫一個程序，現(xiàn)銀行家算法，當(dāng)系統(tǒng)將資源分配給某一進程而不會死鎖時，就分配之。否則，推遲分配，并顯示適當(dāng)?shù)男畔ⅰ?/p>
三、數(shù)據(jù)結(jié)構(gòu)
主要數(shù)據(jù)結(jié)構(gòu):
Struct aa { void Print();//用于打印輸出表格的函數(shù) void Input();//用于輸入的函數(shù)
void tryfenpei(int i);//試分配函數(shù) void refenpei(int i);//恢復(fù)數(shù)據(jù)函數(shù) void checksafe(int s);//安全檢測函數(shù) }；
四、銀行家算法的流程圖 開始初始化資源類數(shù)c=3，進程數(shù)t=5初始化Available[c]，Max[t][c]，Allocation[t][c]，Need[t][c]，Request[c]輸入進程數(shù)iInt f=0f 五、源代碼 #include void Print();//用于打印輸出表格的函數(shù) void Input();//用于輸入的函數(shù) void tryfenpei(int i);//試分配函數(shù) void refenpei(int i);//恢復(fù)數(shù)據(jù)函數(shù) void checksafe(int s);//安全檢測函數(shù) //定義初始化數(shù)組 int Available[c], Max[t][c], Allocation[t][c], Need[t][c], Request[c]; int in;//用戶選擇的進程號 int main(int argc, char *argv[]){ int i;char ch='Y';cout<<“初始化數(shù)據(jù)如下：”< cout<<“試分配完成!”< cout<<“需要繼續(xù)實驗嗎?（y-繼續(xù) n終止）”;} else if(ch=='N'||ch=='n'){ cout<<“感謝您的使用，祝您愉快!”< void Print(){ int i,j;cout<<“ 進程個數(shù) ： ”< void Input(){ for(int j=0;j { for(int m=0;m void tryfenpei(int i){ for(int f=0;f //安全檢測函數(shù) void checksafe(int s){ int Work, flag, temp[t], i,j,l=0,k=0;bool Finish[t];for(i=0;i } if(l==5)//一共有三類資源A B C，一條進程下面的安全性檢測只檢測了A類。如果A類通過了，那么還要判斷B類，C類。否則不用 { for(i=0;i } i=s;//s傳遞進來賦給i，s是用戶輸入的進程號（有主函數(shù)里的in傳遞進來）while(i if(Finish[i]==false&&Need[i][j]<=Work){ Work=Work+Allocation[i][j];Finish[i]=true;temp[k]=i;//cout<<“temp=”< 六、執(zhí)行結(jié)果： 七、實驗總結(jié) 通過本次實驗了解到用銀行家算法來預(yù)防死鎖是可靠的，但也是非常保守的，因為它限制了進程對資源的存取，從而降低了進程的并發(fā)運行程度。死鎖檢測并不限制進程對資源的申請，只要有，就分配，但這也可能造成死鎖。但由于死鎖并不是經(jīng)常發(fā)生的，故大大提高了系統(tǒng)運行的效率。 總之，通過本實驗，使我進一步加深理解和掌握銀行家算法。 《計算機操作系統(tǒng)》 學(xué)號：班級：軟技姓名：張靖偉 課 程 設(shè) 計 報 告 4班 1367003270 目錄 實驗：進程調(diào)度算法——時間片輪轉(zhuǎn)算法 2 實驗：銀行家算法3 實驗：分區(qū)分配算法——4 實驗：頁面置換算法——5 實驗：磁盤調(diào)度算法—— BF和FF FIFO和LRU SCAN和SSTF 1實驗：進程調(diào)度算法——時間片輪轉(zhuǎn)算法 1.實驗設(shè)計說明 用時間片輪轉(zhuǎn)算法模擬單處理機調(diào)度。 （1）建立一個進程控制塊PCB來代表。PCB包括：進程名、到達時間、運行時間和進程后的狀態(tài)。 進程狀態(tài)分為就緒（R）和刪除（C）。 （2）為每個進程任意確定一個要求運行時間和到達時間。 （3）按照進程到達的先后順序排成一個隊列。再設(shè)一個指針指向隊首和隊尾。（4）執(zhí)行處理機調(diào)度時，開始選擇對首的第一個進程運行。（5）執(zhí)行： a)輸出當(dāng)前運行進程的名字； b)運行時間減去時間片的大小。 （6）進程執(zhí)行一次后，若該進程的剩余運行時間為零，則刪除隊首，并將該進程的狀態(tài)置為C；若不為空，則將向后找位置插入。繼續(xù)在運行隊首的進程。 （7）若進程隊列不空，則重復(fù)上述的（5）和（6）步驟直到所有進程都運行完為止。 2.實驗代碼 /*****************時間片輪轉(zhuǎn)調(diào)度算法*******************/ #include char pname[N];int runtime;/*進程名*/ /*服務(wù)時間*/ int arrivetime;/*到達時間*/ char state;/*進程狀態(tài)*/ struct pcb*next;/*連接指針*/ }PCB;typedef struct back_team/*后備隊列定義*/ { PCB*first,*tail;}BACK_TEAM;typedef struct pre_team/*就緒隊列定義*/ { PCB*first,*tail;}PRE_TEAM;PCB*creat()/*創(chuàng)建PCB*/ { char s[N];printf(“請輸入進程名：n”);scanf(“%s”,s);printf(“請輸入進程服務(wù)時間(/秒)：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)/*復(fù)制一個進程*/ { } PCB*getnext(PCB*p,BACK_TEAM*head)/*得到隊列中下一個進程*/ { } void del(BACK_TEAM*head,PRE_TEAM*S)/*釋放申請的空間*/ { PCB*p=head->first->next;while(p){ free(head->first);head->first=p;PCB*s=head->first;if(!p)return NULL;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;while(strcmp(s->pname,p->pname))s=s->next;return s->next; } } p=p->next;head->first=head->tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*創(chuàng)建后備隊列*/ { } bool recognize(PRE_TEAM*s1)/*判斷運行是否結(jié)束*/ { if(!s1||!s1->first)return false;PCB*p=creat();if(!head->first)else head->tail->next=p;head->first=p;head->tail=p;return head;if(s1->first==s1->tail) if(s1->first->state!='C')else return false;return true;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){ } printf(“%dt%st”,time,s->first);s->first->runtime--;time++;if(s->first->runtime<=0){ } PCB*p=s->first;s->first->state='C';printf(“%cn”,s->first->state);s->first=p->next;free(p);if(!s->first){ } goto next;s->tail=NULL;spe=false;return NULL;spe=false;return NULL;printf(“%cn”,s->first->state);next:PCB*head=s->first; } int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*創(chuàng)建就緒隊列*/ { int i=0;if(!head2->first) if(HEAD){ } if(c){ } head2->first=head2->tail=HEAD;return 1;head2->first=c;c->next=HEAD;head2->tail=HEAD;return 1;s->first=head->next;if(!s->first){ } head->next=NULL;return head;s->tail=NULL;spe=true;if(head2->first==head2->tail){ } else { } if(*test){ } if(c){ } head2->tail->next=c;head2->tail=c;if(head2->first->arrivetime!=time)for(i=0;i } if(c->arrivetime!=time){ } head2->tail->next=c;head2->tail=c;time++;return 1;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;do{ printf(“要創(chuàng)建進程嗎(y/n):”);if((ask=getchar())=='y'||ask=='Y'){ } else if(ask=='n'||ask=='N')else return 1;break;head1=creatbt(head1);num++;}while(1);PCB*p=copy(head1->first);PCB*HEAD=NULL;head2->first=head2->tail=copy(head1->first);printf(“時刻t進程名t狀態(tài)n”); } while(spe||recognize(head2)){ } del(head1,head2);return 1;CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1));3.實驗結(jié)果 和不馬上運行: 當(dāng)有兩個進程的時候 當(dāng)有多個進程的時候： 4.實驗結(jié)果分析 RR算法：每次調(diào)度時，把CPU分配給隊首進程，并且令其執(zhí)行一個時間片，時間片的大小從幾個ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便依據(jù)此信號來停止該進程的執(zhí)行；并且把它送往就緒隊列的隊尾；然后，再把處理劑分配給就緒隊列中的新隊首進程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程在一個給定時間內(nèi)均能獲得一時間片的處理機執(zhí)行時間。換言之，系統(tǒng)能在給定的時間內(nèi)相應(yīng)所有用戶的請求.2實驗：銀行家算法 1.實驗設(shè)計說明 1.該算法通過建立幾個簡單的二維數(shù)組Available,Max,Allocation,Need簡單的模擬銀行家算法和安全性算法，每個二維數(shù)組默認[][0]為A資源，[][1]為B資源，[][2]為C資源,默認有5個進程 2.程序首先要輸入各個進程的三種資源的情況，包括每個進程最大的需求量，已經(jīng)分配的資源量和現(xiàn)在還需要的資源量，以及系統(tǒng)現(xiàn)在剩余的資源量。3.程序會判斷輸入的信息是否在程序的規(guī)定范圍內(nèi)，正確才運行。 4．在執(zhí)行安全算法開始時，Work∶=Available;② Finish: 它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］∶=false;當(dāng)有足夠資源分配給進程時，再令Finish［i］∶=true 5.從進程集合中找到一個能滿足下述條件的進程： Finish［i］=false;并且 Need［i,j］≤Work［j］； 若找到，執(zhí)行6，否則，執(zhí)行7。 6.當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;然后繼續(xù)執(zhí)行5。 7.如果所有進程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 2.實驗代碼 #include return false;printf(“p%d可以運行n”,p);Work[0]+=Allocation[p][0];Work[1]+=Allocation[p][1];Work[2]+=Allocation[p][2];Finish[p]=1;while(num<=25){ if(!Finish[i]&&(Need[i][0]<=Work[0])&&(Need[i][1]<=Work[1])&&(Need[i][2]<=Work[2])) { printf(“p%d可以運行n”,i); Work[0]+=Allocation[i][0]; Work[1]+=Allocation[i][1]; Work[2]+=Allocation[i][2]; Finish[i]=1; } num++; i=(i+1)%5; if(i==p) i++;} for(m=0;m<5;m++) if(Finish[m]==0) break;if(m==5) return true;else { printf(“系統(tǒng)處于不安全狀態(tài)!n”); return false;} } void Banker(int p,int i,int j,int k){ int able[3]={Available[0],Available[1],Available[2]};int need[3]={Need[p][0],Need[p][1],Need[p][2]};int allocation[3]={Allocation[p][0],Allocation[p][1],Allocation[p][2]};if(i<=Need[p][0]&&j<=Need[p][1]&&k<=Need[p][2]) if(i<=Available[0]&&j<=Available[1]&&k<=Available[2]) { Available[0]-=i; Available[1]-=j; Available[2]-=k; Allocation[p][0]+=i; Allocation[p][1]+=j; Allocation[p][2]+=k; Need[p][0]-=i; Need[p][1]-=j; Need[p][2]-=k; if(!Safe(p)) { Available[0]=able[0],Available[1]=able[1],Available[2]=able[2]; Need[p][0]=need[0],Need[p][1]=need[1],Need[p][2]=need[2]; Allocation[p][0]=allocation[0],Allocation[p][1]=allocation[1],Allocation[p][2]=allocation[2]; printf(“系統(tǒng)可能發(fā)生死鎖!n”); } } else printf(“等待!系統(tǒng)資源不足!n”);else printf(“錯誤!申請的資源錯誤!n”);} int main(void){ int i,j,k=0,p;printf(“請輸入進程的三種資源的情況max{a,b,c} allocation{a,b,c} need{a,b,c}:n”);for(i=0;i<5;i++){ for(j=0;j<3;j++) scanf(“%d”,&Max[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Allocation[i][j]); for(j=0;j<3;j++) scanf(“%d”,&Need[i][j]);} printf(“請輸入Available{a,b,c}情況:”);for(i=0;i<3;i++) scanf(“%d”,&Available[i]);printf(“MaxtAllotNeedtAvain”);for(i=0;i<5;i++){ for(j=0;j<3;j++) printf(“%d ”,Max[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Allocation[i][j]); printf(“t”); for(j=0;j<3;j++) printf(“%d ”,Need[i][j]); printf(“t”); if(k!=4) printf(“n”); k++;} for(i=0;i<3;i++)printf(“%d ”,Available[i]);printf(“n請輸入要申請的進程和資源<0~4>:”);scanf(“%d %d %d %d”,&p,&i,&j,&k);if(p>=0&&p<=4)Banker(p,i,j,k);else printf(“沒有此進程!”);return 1;} 3.實驗結(jié)果 4.實驗結(jié)果分析 這個實驗只是簡單的演示了進程申請資源之后的進程運行的其中一個運行序列，因為這個算法課本上已經(jīng)有詳細的解說，所以這個程序并沒有把算法的過程展現(xiàn)出來，只展現(xiàn)了進程的運行序列結(jié)果，另外，如果申請錯誤的話程序會有不同的結(jié)果 有時會發(fā)生死鎖 實驗：分區(qū)分配算法——BF和FF 1.實驗設(shè)計說明 1.這個算法模擬的是對內(nèi)存空間的管理，這個程序用了一個簡單的二維數(shù)組模擬分區(qū)表。2.程序首先要輸入固定的五個分區(qū)的大小和始址，其次要輸入作業(yè)的大小和實現(xiàn)的算法，由于這個程序把FF和BF放到一個程序中，便于比較兩個算法。 首次適應(yīng)算法FF(First Fit)把分區(qū)大于等于請求作業(yè)請求的分區(qū)分給請求者，余下部分仍留在空閑區(qū)中，然后修改分區(qū)表。然后打印出分配后的分區(qū)表 最佳適應(yīng)算法BF（Best Fit） 首先把分區(qū)表按空間大小從小到大排序。然后把分區(qū)大于等于請求作業(yè)請求的分區(qū)分給請求者，余下部分仍留在空閑區(qū)中，然后修改分區(qū)表。然后打印出分配后的分區(qū)表 2.實驗代碼 #include int i,j;for(j=0;j<3;j++) for(i=0;i<5;i++) if(ta[i][1]>=job[j]){ } ta[i][1]-=job[j];ta[i][2]+=job[j];break;if(i==5)printf(“內(nèi)存不足!請等待!n”); } printf(“空閑區(qū)t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,ta[j][i]);printf(“n”);void BestFit(int job[3]){ int j1,temp1,temp2,temp3,i,j;for(j1=0;j1<3;j1++){ for(i=0;i<5;i++) for(j=0;j<4;j++) if(table[j][1]>table[j+1][1]){ temp1=table[j][0];temp2=table[j][1];temp3=table[j][2]; table[j][0]=table[j+1][0];table[j][1]=table[j+1][1];table[j][2]=table[j+1][2]; } table[j+1][0]=temp1;table[j+1][1]=temp2;table[j+1][2]=temp3; } if(i==5)printf(“內(nèi)存不足!請等待!n”);printf(“空閑區(qū)t大小t始址n”);for(j=0;j<5;j++){ } for(i=0;i<3;i++)printf(“%dt”,table[j][i]); } for(i=0;i<5;i++) if(table[i][1]>=job[j1]){ } table[i][1]-=job[j1];table[i][2]+=job[j1];break;printf(“n”);void main(){ int table1[5][3],job[3],j,i;printf(“請輸入5個空分區(qū)的大小和始址：”);for(i=0;i<5;i++){ } for(j=0;j<5;j++){ } printf(“請輸入3個要運行作業(yè)的大?。骸?;for(i=0;i<3;i++)scanf(“%d”,&job[i]);for(i=0;i<3;i++)printf(“%dt”,table[j][i]);table[i][0]=i+1;table1[i][0]=i+1;for(j=1;j<3;j++){ } scanf(“%d”,&table[i][j]);table1[i][j]=table[i][j];printf(“n”);printf(“請輸入要實現(xiàn)的算法1(FF)2(BF):”); } char c;scanf(“%d”,&i);getchar();if(i==1){ } else if(i==2){ } BestFit(job);printf(“還要實現(xiàn)FF嗎(y/n)”);if((c=getchar())=='y')FirstFit(job,table1);FirstFit(job,table1);printf(“還要實現(xiàn)BF嗎(y/n)”);if((c=getchar())=='y')BestFit(job);3.實驗結(jié)果 4.實驗結(jié)果分析 首先輸入分區(qū)表的分區(qū)情況，然后輸入運行作業(yè)的大小，選擇要實現(xiàn)的算法。第一個作業(yè)是96，所以找到第四個分區(qū)，第四個分區(qū)變?yōu)?22，316，接著到第二個作業(yè)20，然后把第一個分區(qū)分給第二個作業(yè)，則第一個分區(qū)信息變?yōu)?22，316，到第三個作業(yè)時，由于內(nèi)存表中沒有比第三個請求的分區(qū)還大的分區(qū)，所以會提示內(nèi)存不足； 然后到BF算法，因為是按空間大小排序的，所以第一個作業(yè)96被分配給了已經(jīng)排好序的內(nèi)存為96的第五個分區(qū)，第二個作業(yè)被分配給大小為36的分區(qū)，第三個作業(yè)被分配給內(nèi)存大小為218的分區(qū)，然后又對剩余空間再次排隊，用來給下一批作業(yè)分配。實驗：頁面置換算法——FIFO和LRU 1實驗設(shè)計說明 程序設(shè)置了兩個結(jié)構(gòu)體,freeBlock和jobQueue,其中freeBlock代表物理塊,初次創(chuàng)建物理塊時,物理塊的計時器time=0,還有代表作業(yè)的index=-1;物理塊有添加和刪除的功能，每一次添加或刪除都要初始化物理塊。并且可以重復(fù)添加和刪除，這樣可以很好的測試算法的性能。2.算法設(shè)計的思想是：進入物理塊時間越長的則物理塊的計時器數(shù)值越大，如果物理塊中有要訪問的頁面，則那個含頁面的物理塊的計數(shù)器變成1；并且物理塊要滿才會發(fā)生置換，于是設(shè)置了物理塊計數(shù)器Time； 2.實驗代碼 #include jobQueue*job=(jobQueue*)malloc(sizeof(jobQueue));job->index=num;job->next=NULL;if(!head){ jobQueue*j=head;while(j->next)j=j->next;j->next=job;head=job;else } } return head;freeBlock*creat(freeBlock*head){ } freeBlock*inse(freeBlock*head){ } freeBlock*dele(freeBlock*head){ freeBlock*test=head;while(test){ } freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=head;head=free;return head;test->index=-1;test->time=0;test=test->next;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*test=head;while(test){ } freeBlock*f=head;head=f->next;free(f);return head;test->index=-1;test->time=0;test=test->next;bool check(freeBlock*free,int j){ } void LRU(freeBlock*free,jobQueue*job){ int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ freeBlock*f=free;while(f){ } return false;if(f->index==j)return true;f=f->next; } size++;ftest=ftest->next;printf(“LRU置換頁面為：”);while(jtest){ ftest=free;while(ftest){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ if(ftest->index==jtest->index){ } ftest->time++;if(Time } } } } time=0;Time=0;break;if(ftest->time==Time){ } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;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){ } ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ } if(ftest->time==Time)time=0;Time=0;break;if(ftest->index==-1){ } ftest->time++;if(Time } } } { } ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void main(){ int num,ch,p;freeBlock*block=NULL;jobQueue*job=NULL;printf(“請輸入物理塊數(shù)目：”);scanf(“%d”,&p);for(int i=0;i } job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true){ printf(“增加物理塊（1）減少物理塊（2）,否則按任意鍵scanf(”%d“,&num);if(num==1){ } else if(num==2){ printf(”要減少幾塊：“);scanf(”%d“,&ch);if(ch>=p){ } for(i=0;i } } } FIFU(block,job);LRU(block,job);else ；break;3.實驗結(jié)果 4.實驗結(jié)果分析 程序開始要輸入物理塊數(shù)目和作業(yè)個數(shù),然后再輸入作業(yè).在測試后可以隨意添加或刪除物理塊來測試算法的性能。實驗：磁盤調(diào)度算法——SCAN和SSTF 1.實驗設(shè)計說明 算法定義了一個雙向鏈表，利用雙向鏈表可以很好的進行方向的轉(zhuǎn)換，且雙向鏈表的中有代表磁盤號的標識符index；兩個算法均采用訪問完一個磁盤序列時刪除該序列，其中scan算法實現(xiàn)時有點麻煩，首先要找到當(dāng)前磁盤號序列的Max最大值和最小值Min及指向他們的指針pmax，pmin，另外還要找到當(dāng)前磁頭的相鄰的兩個訪問序列信息psmax，psmin；還有一個重要的標志，那就是訪問的方向test；當(dāng)遇到最大值或最小值時，便會反置test的值，也就是訪問的方向 2.實驗代碼 #include printf(“請輸入磁道隊列以-1結(jié)束！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;else { } tail=p;scanf(“%d”,&ch);tail->right=p;p->left=tail;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))<=num){ } p=p->right;num=abs(p->index-index1);if(p!=p1)p2=p;p=p1->right;if(p2){ } else { printf(“%d ”,p1->index);index1=p2->index;printf(“%d ”,p2->index);p2->left->right=p2->right;if(p2->right)p2->right->left=p2->left;free(p2);p2=NULL; } } } index1=p1->index;if(!p){ } else { } p=p1;p1=p1->right;free(p);continue;free(p1);break;void SCAN(memory*head,int index){ int index1=index,num,test,max=0,min=199,Max,Min;printf(“請輸入磁頭查詢方向<0正向><1負向>!n”);scanf(“%d”,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL; while(p1){ } p1=head;while(p1){ if(!test){ if(!test){ } else { } p1=p1->right;pmin=p1;if(p1->index<=min)Min=min=p1->index;pmax=p1;if(p1->index>=max)Max=max=p1->index; } } pmin=p1;if(p1->index<=min)Min=min=p1->index; else { } p1=p1->right;pmax=p1;if(p1->index>=max)Max=max=p1->index;p1=head;while(true){ num=abs(p1->index-index1);p=p1;while(p){ if(!test){ if(p->index>=index1&&p->index<=max) } } if((abs(p->index-index1))<=num){ } psmin=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;else { } p=p->right;if(p->index<=index1&&p->index>=min) if(abs(p->index-index1)<=num){ } psmax=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;if(p2) { if(!test){ } else { index1=psmax->index;p=psmax;if(index1==Min){ } test=0;Max=Min=-1;p1=pmin;index1=psmin->index;p=psmin;if(index1==Max){ } test=1;Min=Max=-1;p1=pmax; } printf(“%d ”,index1);if(!test){ } else { if(psmax)if(psmin){ } else { } psmax->right->left=psmax->left;if(psmax->left) psmax->left->right=psmax->right;psmin->left->right=psmin->right;if(psmin->right) psmin->right->left=psmin->left;free(psmin);free(psmax); } } { } else { } psmin->right->left=psmin->left;if(psmin->left) psmin->left->right=psmin->right;psmax->left->right=psmax->right;if(psmax->right) psmax->right->left=psmax->left;free(psmax);free(psmin);else { if(!test){ if(p1->index==Max){ test=1; } } Min=Max=-1;else { } if(psmax){ } else { } printf(“%d ”,index1);index1=psmin->index;p=psmin;index1=psmax->index;p=psmax;if(p1->index==Min){ } test=0;Max=Min=-1; } } } if(p->left&&!p->right){ } else if(p->right&&!p->left){ } else if(!p->right&&!p->left){ } free(p);free(p);break;p1=p->right;p1->left=NULL;p1=p->left;p1->right=NULL;p2=psmax=psmin=NULL;void main(){ int p,t;memory*head=creat();printf(“請輸入磁頭當(dāng)前的位置(0-199)”);scanf(“%d”,&p);printf(“要進行的算法：<0:SCAN><1:SSTF>”);scanf(“%d”,&t);if(!t)SCAN(head,p);else SSTF(head,p);} 3.實驗結(jié)果 4.實驗結(jié)果分析 輸入要訪問的磁盤號，然后選擇要實現(xiàn)的算法就可以看到結(jié)果，當(dāng)選0（正向）的時候由于當(dāng)前的磁頭在143處，所以要訪問的磁盤號就必須大于143，當(dāng)最大的磁盤號訪問完時，就轉(zhuǎn)向小于143的磁盤開始由大向小訪問，選1的話則相反。最短尋道時間算法是從整個隊列中選擇距離磁頭最近的訪問，算法的實現(xiàn)運用了絕對值的概念 1.死鎖：各并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。 2.設(shè)備驅(qū)動程序：驅(qū)動物理設(shè)備和DMA控制器或I/O控制器等直接進行I/O操作的子程序的集合。負責(zé)設(shè)置相應(yīng)設(shè)備的有關(guān)寄存器的值，啟動設(shè)備進行I/O操作，指定操作的類型和數(shù)據(jù)流向等。 3.SPOOLING系統(tǒng)：外圍設(shè)備同時聯(lián)機操作。在SPOOLING系統(tǒng)中多臺外圍設(shè)備通過 通道或DMA器件和主機與外存連接起來。作業(yè)的輸入輸出過程由主機中的操作系統(tǒng)控制。 4.覆蓋技術(shù)：一個程序并不需要一開始就把他的全部指令和數(shù)據(jù)都裝入內(nèi)存后在執(zhí) 行。在單CPU系統(tǒng)中，每一時刻事實上只能執(zhí)行一條指令。因此可以把程序劃分為若干個功能上相對獨立的程序段，按照程序的邏輯結(jié)構(gòu)讓那些不會同時執(zhí)行的程序段共享同一塊內(nèi)存區(qū)。通常，這些程序段都被放在外存中，當(dāng)有關(guān)程序段的先頭程序段已經(jīng)執(zhí)行結(jié)束后，再把后續(xù)程序段調(diào)入內(nèi)存覆蓋前面的程序段。 5.交換技術(shù)：先將內(nèi)存某部分的程序或數(shù)據(jù)寫入外存交換區(qū)，再從外存交換區(qū)調(diào)入指 定 的程序或數(shù)據(jù)到內(nèi)存中來，并讓其執(zhí)行的一種內(nèi)存擴充技術(shù)。 6.進程：并發(fā)執(zhí)行的程序在執(zhí)行過程中分配和管理資源的基本單位。 7.通道：一個獨立于CPU的專管輸入輸出控制的處理機，他控制設(shè)備與內(nèi)存直接進 行數(shù)據(jù)交換。他有自己的通道指令，這些通道指令受CPU啟動，并在操作結(jié)束后向CPU發(fā)中斷信號。 8.線程：他是進程的一部分，有時被成為輕權(quán)進程或輕量級進程，也是CPU調(diào)度的基本單位。 9.臨界區(qū)：不允許多個并發(fā)進程交叉執(zhí)行的一段程序。 10.臨界資源：臨界區(qū)占用的資源 11.塊設(shè)備：將信息存儲在固定大小的塊中，每個塊都有自己的地址。 12.字設(shè)備：在I/O傳輸過程中以字符為單位進行傳輸?shù)脑O(shè)備。 13.作業(yè)：在一次應(yīng)用業(yè)務(wù)處理過程中，從輸入開始到輸出結(jié)束，用戶要求計算機所做的有關(guān)該次業(yè)務(wù)處理的全部工作稱為一個作業(yè)。 14.文件系統(tǒng)：操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)稱為文件系統(tǒng)。他負責(zé)為用戶 建立撤銷讀寫修改和復(fù)制文件，還負責(zé)完成對文件的按名存取和進行存取控制。 15.互斥：不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū) 16.同步：異步環(huán)境下的一組并發(fā)進程，因直接制約而互相發(fā)送消息而進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程。 17.抖動：由于內(nèi)存頁面置換算法選擇不當(dāng)，致使剛被調(diào)出內(nèi)存的頁又要馬上被調(diào)回內(nèi) 存，調(diào)回內(nèi)存不久又馬上被調(diào)出內(nèi)存，如此反復(fù)的局面。 18.虛擬存儲器：將進程中的目標代碼、數(shù)據(jù)等的虛擬地址組成的虛擬空間成為虛擬存 儲器。 19.中斷：是指計算機在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生任何非尋常的或非預(yù)期的急需處理事件，使得CPU暫時中斷當(dāng)前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，帶處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調(diào)度新的進程執(zhí)行的過程。 20.局部性原理：程序總是趨向于使用最近使用過的數(shù)據(jù)和指令，也就是程序執(zhí)行時所 訪問的存儲器地址不是隨機的，而是相對的簇集，這種簇集包含數(shù)據(jù)和指令兩部分。程序局部性包括時間局部性和空間局部性。程序的時間局部性：程序即將用到的信息可能就事目前正在使用的信息。程序的空間局部性：程序即將用到的信息可能與 21.22.23.24.25.26.27.28.29.30.31.目前正在使用的信息在空間上相鄰或臨近。進程控制塊（Process Control Block）：PCB是 系統(tǒng)為了管理進程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進程的外部特征，描述進程的運動變化過程。文件控制塊（FCB）：文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息。資源分配圖：用于分析死鎖的一種圖，由資源結(jié)點、進程結(jié)點、分配邊和請求邊組成。競態(tài)：多個并發(fā)進程共享數(shù)據(jù)的結(jié)果錯誤，其值不可確定，取決這些進程執(zhí)行的相對速度。i-節(jié)點：UNIX型文件系統(tǒng)中，一種用于存儲文件控制信息的數(shù)據(jù)結(jié)構(gòu)，每個文件對應(yīng)擁有一個這樣的數(shù)據(jù)塊，組織并存儲于外存特定的一些盤塊中。內(nèi)核：實現(xiàn)操作系統(tǒng)的最基本功能、常駐內(nèi)容并要求CPU在核心態(tài)方式下運行的代碼和相關(guān)數(shù)據(jù)結(jié)構(gòu)。信號量：操作系統(tǒng)內(nèi)容定義和管理的一種特殊數(shù)據(jù)結(jié)構(gòu)，提供了初始化、增值和減值等操作供進程調(diào)用，以實現(xiàn)進程互斥或同步。邏輯地址：程序設(shè)計員在程序中使用的地址。管程：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù) 管道：是連接讀寫進程的一個特殊文件，允許進程按先進先出方式傳送數(shù)據(jù)，也能使進程同步執(zhí)行操作。驅(qū)動調(diào)度：系統(tǒng)運行時，同時會有很多個訪問輔助儲存器的進程請求輸入輸 出操作，操作系統(tǒng)必須采取一種調(diào)度策略，使其能按最佳的次序執(zhí)行各訪問請求。第四篇：操作系統(tǒng)課程設(shè)計六種算法
第五篇：操作系統(tǒng)原理術(shù)語解析總結(jié)
點擊咨詢 