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