第一篇：操作系統課程設計報告

操 作 系 統

課

程

設

計

實

驗

報

告

學院：計算機科學與技術學院

班級：計112

學號：1113022032

姓名:

一、實驗名稱：

用C++實現驅動調度算法、頁面替換算法、銀行家算法、處理器調度算法

二、實驗要求：

書寫實驗報告，包括的內容有：

（1）實驗題目

（2）程序中使用的數據結構及主要文字說明

（3）帶有注釋的源程序

（4）執行程序說明，表明各進程控制快的初始狀態，以及各算法的運行狀態

（5）通過實驗后的收獲與體會及對實驗的改進意見和見解

二、實驗目的：

通過自己編程來實現各類操作系統算法，進一步理解操作系統的概念及含義，提高對操作系統的認識，同時提高自己的動手實踐能力。加強我們對各類算法的理解。

三、實驗內容：

1、實現頁面替換算法

（1）FIFO 先進先出頁面替換算法

（2）LRU最近最少使用頁面替換算法

（3）LFU最少使用頻率頁面替換算法

2、銀行家算法

3、實現驅動調度算法

（1）先來先服務算法

（2）電梯算法

（3）掃描算法

4、實現處理器調度

（1）先進先出處理器調度

（2）時間片輪轉法

（3）優先級調度

四、實驗原理：

1、頁面替換算法

先進先出頁面置換算法：該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面加以淘汰。將已調入內存的頁面按先后次序鏈接成一個隊列，將最先調入的頁面與新頁面進行置換

最近最久未使用置換算法：該算法是利用“最近的過去”作為“最近的將來”，將最近最久未使用的頁面加以淘汰。將已調入內存的頁面按先后順序鏈接成一個隊列，為每一個頁面增加一個訪問字段，用來記錄一個頁面自上次被訪問以來所經歷的是時間t，當需淘汰一個頁面時，選擇現有頁面中其t值最大，即最近最久未使用的頁面加以淘汰

2、銀行家算法

先對用戶提出的請求進行合法性檢查，即檢查請求的是不大于需要的，是否不大于可利用的。若請求合法，則進行試分配。最后對試分配后的狀態調用安全性檢查算法進行安全性檢查。若安全，則分配，否則，不分配，恢復原來狀態，拒絕申請。

3、驅動調度算法

先進先出算法（FIFO）：總是嚴格按時間順序對磁盤請求予以處理。算法實現簡單、易于理解并且相對公平，不會發生進程餓死現象。但該算法可能會移動的柱面數較多并且會

經常更換移動方向，效率有待提高

電梯調度算法：總是將一個方向上的請求全部處理完后，才改變方向繼續處理其他請求。

掃描算法（scan algorithm）：總是從最外向最內（或最內向最外）進行掃描，然后在從最內向最外（或最外向最內）掃描。該算法與電梯調度算法的區別是電梯調度在沒有最外或最內的請求時不會移動到最外或最內柱面。

4、處理器調度算法

先進先出處理器調度：按照作業進入系統后備工作隊列的先后次序來挑選作業,先進入系統的作業將優先被挑選進入主存,創建用戶進程,分配所需資源,然后移入就緒隊列。

時間片輪轉法調度算法：調度次序每次把CPU分配給就緒隊列進程/線程使用規

定的時間間隔，就緒隊列中每個進程/線程輪流的運行一個時間片，當時間片耗盡時，就強迫當前運行進程/線程讓出處理器，轉而排列到就緒隊列尾部，等候下一輪調度。

優先級調度：根據確定的優先級來選取進程/線程，總是選擇就緒隊列中的優先

級最高者投入運行，即優先級越高，先被調用。

五、數據結構設計

對操作系統的各類算法設計數據結構如下：

頁面替換算法：void FIFO()；void LRU()；void LFU()；

銀行家算法：void Init()初始化算法

void Bank()銀行家算法

bool Safe()安全性算法

驅動調度算法：

struct MagneticHead//磁頭構成{

int site;

int count;

bool direct;

}；

struct Range//磁盤磁道范圍

{

int mStart;

int mEnd;

};

struct RequestList//請求序列

{

int site;

bool state;

};

struct Data//基本數據集合{

MagneticHead magneticHead;

RequestList *requestList;

int *executeList;

Range range;

int length;

};

處理器調度：

typedef struct pcb//時間片輪轉法

{

char pname[N];

int runtime;

int arrivetime;

char state;

struct pcb*next;

}PCB;

typedef struct PCB1//先進先出服務

{

char ID[3];//進程號

char name[10];//進程名

char state;//運行狀態

floatarrivetime;//到達時間

floatstarttime;//進程開始時間

floatfinishtime;//進程結束時間

floatservicetime;//服務時間

float turnaroundtime;//周轉時間

float weightedturnaroundtime;//帶權周轉時間

struct PCB1 *next;//指向下個進程

}pcb1;

struct pcb2 {優先級調度

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb2* link;

}*ready=NULL,*d;

typedef struct pcb2 PCB2;

六、課程設計總結

在本次課程設計中，就是講平時所做的實驗結合起來，實現操作系統的各類算法，了解操作系統的運行原理以及其基本概念，更好的將操作系統的原理很好的展現出來。同時，在本次實驗中遇到了很多問題，需要我們仔細的檢查和修改。其次，實驗中為了能更好的體現各類算法的運行情況，需要做一個清晰的界面，以能清楚地看出運行結果。

第二篇：操作系統課程設計報告

課程設計報告

題 目： 模擬請求頁式管理

課程名稱： 計算機操作系統 學 院： 信息工程學院

專 業： 計算機科學與技術

班 級： 14計本（1）學生姓名： * * * 學 號： 201403031** 指導教師： * * 成 績：

開課時間： 2016-2017 學年 一 學期

模擬請求頁式管理

第1章 需求分析

1.1設計要求

請求頁式管理是一種常用的虛擬存儲管理技術。本設計通過請求頁式存儲管理中頁面置換算法模擬設計，了解虛擬存儲技術的特點，掌握請求頁式管理的頁面置換算法。本實驗要求用Vc＋＋或其他高級語言編寫和調試。

編寫程序實現：

（1）先進先出頁面置換算法（FIFO）（2）最近最久未使用頁面置換算法（LRU）最佳置換頁面置換算法（OPT）設計一個虛擬存儲區和內存工作區，編程序演示以上三種算法的具體實現過程，并計算訪問命中率。

1.2解決方案

首先確定實現語言使用c#實現圖形化界面，后確定要實現哪些功能，比如算法選擇，頁面添加，模擬控制。然后確定輸出結構以便于程序的測試和驗證。將基本框架建立后再進行編程。編程前進行算法結構分析最后編程實現。

1.3算法實現原理

1、先進先出置換算法（FIFO）：

發生缺頁中斷時按照頁面進入內存順序總是淘汰最先進入內存的頁面。

2、最近最久未使用置換算法（LRU）：

發生缺頁中斷時總是淘汰存在內存中最長時間未被使用的頁面。

3、最佳置換算法（OPT）：

發生缺頁中斷時若一個或幾個頁面將來將不會被調用則按先進先出原則淘汰頁面，若將來都有調用則比較調用時刻選擇最遠時刻頁面淘汰。

4、缺頁率：缺頁次數占頁面調用次數的百分比。

第2章 概要設計

2.1數據設計

常變量：調用頁面最大數量（MaxN），內存最大頁面數（MaxM）待調用頁面數組：page_dd[MaxN]存放等待調用的頁面號

頁面數組專用指針 page_p，用于指向page_dd數組中正需調入內存的頁號 內存塊數組：Memery[MaxM]，存放內存當前存放的頁號 缺頁計數器：count，記錄缺頁次數

內存塊狀態數組：M1[MaxN],M2[MaxN],M3[MaxN]，記錄每次頁面調用結束后內存各塊的狀態

缺頁記錄數組s[MaxN]，用于記錄頁面調用時是否產生缺頁中斷，初始化為是

2.2函數設計

1、頁面添加函數：void btnAdd_Click(object sender, EventArgs e)用于實現通過點擊按鈕實現數據輸入。

2、內存初始化函數：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)參數有頁面數組、內存數組、狀態數組，采用先進先出算法對內存先進行裝滿 服務于先進先出頁面置換函數和最佳置換函數。

3、輸出函數：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于輸出模擬結果，參數有頁面數組，內存數組，狀態數組，缺頁記錄數組。再模擬之后調用。

4、模擬控制函數：void btnmo_Click(object sender, EventArgs e）用于實現通過單擊模擬按鈕，根據用戶所選算法進行模擬并顯示結果。

5、先進先出算法模擬函數：

void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于實現先進先出算法模擬，參數有頁面數組，內存數組、內存狀態記錄數組，缺頁記錄數組。在模擬函數中調用。

6、最近最久未使用算法模擬函數：

void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于 3 實現最近最久未使用算法模擬，參數有頁面數組，內存數組，內存狀態記錄數組，缺頁記錄數組。在模擬函數中被調用。

7、最近最久未使用函數輔助函數：void LUR_I(int[] a,int e)用于對最近最久未使用算法中所用輔助數組（記錄頁面存在時長）進行調整，參數有輔助數組及需調整的數據下標。在最近最久未使用函數中調用。

8、最佳置換算法模擬函數：

void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s)用于模擬最佳置換算法。參數有頁面數組，內存數組，內存狀態記錄數組，缺頁記錄數組。在模擬函數中被調用。

9、最佳置換算法輔助函數：void OPT_F(int[] a, int e)用于對最佳置換算法中的輔助數組進行調整。參數有輔助數組，需調整數據下標。在最佳置換算法中被調用。

10、重置函數：void btncz_Click(object sender, EventArgs e)用于重新選擇算法進行新的模擬。

2.3主要算法設計

1、初始化函數算法：

第一步：將第一個頁面調入內存，調整最佳置換算法輔助數組，缺頁計數器加一，保存內存數組狀態。

第二步：調用下一個頁面并判斷內存中是否有本頁面有轉第三步，無轉第四步。第三步：更改缺頁數組對應下標值，記錄當前內存狀態，調整最佳置換算法輔助數組，頁面指針指向下一頁。

第四步：將頁面調入內存，調整最佳置換算法輔助函數，缺頁計數器加一，保存內存數組狀態。若內存尚不滿轉第一步。具體見圖1初始化算法流程圖。

開始頁面調入內存缺頁計數器加一記錄內存狀態調用下一頁否否內存是否有該頁面是記錄內存狀態修改缺頁數組內存已滿是結束

圖1 初始化算法流程圖

2、先進先出頁面置換算法：

第一步：檢查內存中是否已有需調用頁面，有則轉第二步，無則轉第三步。第二步：記錄當前內存狀態，修改缺頁數組對應下標值。

第三步：內存中無需要調用的頁面，進行出隊操作，然后進行入隊操作，記錄內存塊狀態，缺頁計數器加一。

第四步：若頁面數組未被調用結束轉第一步。具體見圖2先進先出算法流程圖。

開始頁面調入內存該頁在內存中是否已存在是否否先出隊操作后入隊操作記錄內存狀態修改缺頁數組值記錄內存狀態缺頁計數器加一頁面調用結束是結束

圖2 先進先出算法流程圖

3、最近最久未使用置換算法：

第一步：將頁面調入內存，記錄內存狀態，缺頁計數器加一，調整輔助數組，頁面指針加一。

第二步：檢查內存中是否已有所需頁面，有轉第三步，無轉第一步。

第三步：修改缺頁數組對應下標記錄，記錄內存狀態，調整輔助數組，頁面指針加一。第四步：內存是否已滿，無則轉第一步，是則轉第五步。

第五步：檢查內存中是否有所需頁面，有則記錄當前內存狀態，修改缺頁數組對應下標值。無則轉第六步。

第六步：檢查輔助數組找出最大值并記錄其下標，置換內存中對應下標的數據，調整輔助數組，缺頁計數器加一。

第七步：頁面是否調用結束未結束則轉第五步。具體見圖3最近最久未使用算法流程圖。

開始調入頁面至內存記錄內存狀態計數器加一否調整輔助數組調用下一頁內存中是否已有該頁否內存已滿是通過輔助數組確定淘汰頁面是修改缺頁數組記錄內存狀態調整輔助數組否頁面置換記錄內存狀態計數器加一調用結束是結束

圖3 最近最久未使用算法

4、最佳置換算法：

第一步：檢查內存中是否已有所需頁面，有則記錄內存狀態，修改缺頁數組對應下標數值。無則轉第二步。

第二步：判斷內存中各頁面的未來調用情況，記錄是否還有調用，若有則記錄調用時刻。

第三步：分析調用情況，內存中頁面都在將來不會被調用轉第四步，有一個被調用轉第五步，有兩個被調用轉第六步，全被調用轉第七步。

第四步:查找輔助數組找到內存中存在時間最長的頁面進行置換，修改內存狀態，缺頁計數器加一，修改輔助數組。

第五步：查找到不會被調用的頁面，并根據輔助數組選擇最早進入內存的頁面將其置換。修改內存狀態，缺頁計數器加一，修改輔助數組。

第六步：查找輔助數組找到將來不需要在調用的頁面將其置換，修改輔助數組，記錄內存狀態，缺頁計數器加一。

第七步：查找輔助數組，找尋最晚被調用的頁面，將其置換。記錄內存狀態，修改輔助數組，缺頁計數器加一。

第八步：頁面是否調用完成，否則轉第一步。具體見圖4最佳置換算法流程圖

開始調入頁面記錄內存狀態計數器加一更新輔助函數是頁面已存在否向后檢查內存當前頁面調用情況所有頁面都不會再度調用否是一個頁面會調用否否是兩個頁面會調用是否查找輔助數組得到最先進入頁面通過輔助數組得到不會再調用的頁面通過輔助數組獲取最晚調用的頁面通過輔助數組得到另外兩個頁面中最先進入的頁面置換頁面記錄內存狀態計數器加一更新輔助函數頁面調用結束是結束

圖4 最佳置換算法流程圖 2.4界面設計

采用c# 設計windows窗體應用程序，使用下拉列表框選擇算法，通過按鈕添加待調用的頁面。通過文本控件顯示模擬結果。顯示樣式：第一行：算法名稱；

第二行：調用頁面順序；

第三行至第五行顯示內存在每調用一次頁面后的狀態；

第六行：是否缺頁；

最后一行顯示缺頁率；

第3章 詳細設計與實現

3.1函數設計

1、添加按鈕功能實現代碼

主要功能：實現單擊一次添加一個調用頁面，并給出相應的提示，如正在輸入的是第幾次調度頁面，在輸入為空時能夠彈出對話框提示用戶，在輸入完成時為避免數組越界應在輸入完成時隱藏；輸入過程中始終保證時輸入焦點。private void btnAdd_Click(object sender, EventArgs e){ if(txtAdd.Text!= “")//輸入不為空才能繼續輸入 { page_dd[i_add] = Convert.ToInt32(txtAdd.Text);/*將輸入值賦值給頁面數組*/ txtShow.Text += txtAdd.Text + ” “;/*顯示供用戶查閱*/ i_add++;txtAdd.Clear();/*清空*/ if(i_add == MaxN)//輸入結束時 { txtAdd.ReadOnly = true;//不允許繼續輸入 btnAdd.Hide();//按鈕隱藏 return;} txtAdd.Focus();//設置為輸入焦點

label2.Text = ”第“ +(i_add + 1)+ ”次調度頁面：“;/*提示用戶正在輸入的是第幾次調度頁面*/ } /*輸入為空則彈出對話框提示用戶輸入為空*/ else { MessageBox.Show(”請輸入調用頁面！“, ”輸入為空“, MessageBoxButtons.OK, MessageBoxIcon.Warning);txtAdd.Focus();} }

2、初始化函數

主要功能：將內存一先進先出方式填滿，并記錄每個頁面進入時間，服務于先進先出頁面置換算法和最佳置換算法。

void init(int[] a, int[] b,int []m1,int[]m2,int[]m3){ /*內存未滿時循環*/ for(int i = 0;i < MaxM&&page_p

//調整輔助數組將剛進入內存的頁面的對應時間 OPT_F(O_Q ,i)； count++;//缺頁計數器加一 m1[page_p] = b[0];//保存內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];page_p++;//調用下一頁面

//檢查內存中是否原先就有需要的頁面； for(int j = 0;j <= i&&page_p

s[page_p] = 'F';//缺頁數組對應數據更改 m1[page_p] = b[0];//記錄內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);//調整最佳置換算法輔助函數 page_p++;//調用下一頁 j =-1;//重新開始尋找 } } } }

3、先進先出頁面置換函數

主要功能：根據先進先出算法要求在產生缺頁中斷時采用先進先出方式確定淘汰頁面，并在每次頁面調用時記錄下內存狀態，缺頁次數；采用循環隊列使得每次出隊的一定是最先進入內存的。

private void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s){ int Fpage_p = page_p;int front, rear;//定義隊列對手和對尾指針并初始化 front = 0;rear = MaxM1;int sa;for(;Fpage_p < MaxN;Fpage_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{ if(b[i] == a[Fpage_p]){ m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];s[Fpage_p] = 'F';sa = 1;break;} } if(sa == 0){ front =(front + 1)% MaxM;

rear =(rear + 1)% MaxM;b[rear] = a[Fpage_p];m1[Fpage_p] = b[0];m2[Fpage_p] = b[1];m3[Fpage_p] = b[2];count++;} else continue;} } /*最近最久未使用算法輔助數組調整函數*/ private void LUR_I(int[] a,int e){ int temp;temp = a[e];a[e] = 1;for(int i = 0;i < MaxM;i++){ if(a[i] < temp && i!=e)a[i]++;} } /*最佳置換算法輔助數組調整函數*/ private void OPT_F(int[] a, int e){ if(e!=-1){ a[e] = 0;for(int i = 0;i < MaxM;i++){ if(i!= e)a[i]++;} } else for(int i = 0;i < MaxM;i++){ a[i]++;} } /*最近最久未使用算法*/ private void LRU(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){

int[] L_Q = new int[MaxM]{3,3,3};int sa;for(int i = 0;i < MaxM && page_p < MaxN;i++){ b[i] = a[page_p];//調入內存 count++;m1[page_p] = b[0];//保存內存狀態 m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);page_p++;for(int j = 0;j <= i && page_p < MaxN;j++){ if(b[j] == a[page_p]){ s[page_p] = 'F';m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, j);page_p++;j =-1;} } } for(;page_p < MaxN;page_p++){ sa = 0;for(int i = 0;i < MaxM;i++)//用的頁面。{ if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];s[page_p] = 'F';LUR_I(L_Q, i);sa = 1;break;} } if(sa == 0){

檢查內存中是否已有要調40 for(int i = 0;i < MaxM;i++){ if(L_Q[i] == 3){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];LUR_I(L_Q, i);break;} } count++;} else continue;} } /*最佳置換算法*/ private void OPT(int[] a, int[] b, int[] m1, int[] m2, int[] m3, char[] s){ int sa;int O_p;int Ocount;int[] OPT_I=new int [MaxM ]{-1 ,-1 ,-1 };int[] OPT_J=new int [MaxM]{MaxN ,MaxN ,MaxN };for(;page_p < MaxN;page_p++){ for(int i = 0;i < MaxM;i++){ OPT_I[i] =-1;//刷新狀態數組 OPT_J[i] = MaxN;} sa = 0;for(int i = 0;i < MaxM;i++)//檢查內存中是否已有要調用的頁面。

{

if(b[i] == a[page_p]){ m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);

s[page_p] = 'F';sa = 1;break;} } if(sa == 0)//缺頁 { Ocount = 0;for(int i = 0;i < MaxM;i++){ O_p = page_p + 1;for(;O_p < MaxN;O_p++){ if(b[i] == a[O_p]){ Ocount++;OPT_I[i] = 1;OPT_J[i] = O_p;break;} } } switch(Ocount){ case 0://全部頁面以后都不會再度調用 int temp = 0;for(int i = 0;i < MaxM;i++){ if(O_Q[i] > O_Q[temp])temp = i;} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 1://有一個頁面將在以后調用 temp = 0;for(int i = 0;i < MaxM;i++){ if(OPT_I[i]!= 1 && O_Q[i] > O_Q[temp])temp = i;

} b[temp] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q ,temp);count++;break;case 2: for(int i = 0;i < MaxM;i++){ if(OPT_I[i] ==-1){ b[i] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, i);count++;} } break;case 3: int p = 0;for(int i = 0;i < MaxM;i++){ if(OPT_J[i] >OPT_J[p])p = i;} b[p] = a[page_p];m1[page_p] = b[0];m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q, p);count++;break;} } } } /*重置函數*/ private void btncz_Click(object sender, EventArgs e){ comboBox1.SelectedIndex = 0;

txtAdd.Text = ”“;page_p = 0;i_add = 0;count = 0;//txtShow.Text = ”";for(int i = 0;i < MaxM;i++)Memery[i] =-1;for(int i = 0;i < MaxN;i++)s[i] = 'T';} } }

第三篇：操作系統課程設計報告

操作系統課程設計報告

專 業：計算機科學與技術 學 號： 姓 名: 提交日期：

操作系統課程設計報告

【設計目的】

（1）本實驗的目的是通過一個簡單多用戶文件系統的設計，加深理解文件系統的內部功能和內部實現。

（2）結合數據結構、程序設計、計算機原理等課程的知識，設計一個二級文件系統，進一步理解操作系統。

（3）通過分對實際問題的分析、設計、編程實現，提高學生實際應用、編程的能力 【設計內容】

為Linux系統設計一個簡單的二級文件系統。要求做到以下幾點： 1.可以實現下列幾條命令：

login 用戶登錄

dir 列目錄

create 創建文件

delete 刪除文件

open 打開文件

close 關閉文件

read 讀文件

write 寫文件

cd 進出目錄

2．列目錄時要列出文件名，物理地址，保護碼和文件長度 3．源文件可以進行讀寫保護 【實驗環境】 Windows xp/7 C++/VC++

【相關知識綜述】

1、文件系統

文件系統是操作系統用于明確存儲設備（常見的是磁盤，也有基于NAND Flash的固態硬盤）或分區上的文件的方法和數據結構；即在存儲設備上組織文件的方法。操作系統中負責管理和存儲文件信息的軟件機構稱為文件管理系統，簡稱文件系統。文件系統由三部分組成：文件系統的接口，對對象操縱和管理的軟件集合，對象及屬性。從系統角度來看，文件系統是對文件存儲設備的空間進行組織和分配，負責文件存儲并對存入的文件進行保護和檢索的系統。具體地說，它負責為用戶建立文件，存入、讀出、修改、轉儲文件，控制文件的存取，當用戶不再使用時撤銷文件等。

2、位示圖

位示圖是利用二進制的一位來表示磁盤中的一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閑；為“1”時，表示已經分配。有的系統把“0”作為盤塊已分配的標記，把“1”作為空閑標志。(它們的本質上是相同的，都是用一位的兩種狀態標志空閑和已分配兩種情況。)磁盤上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。

操作系統課程設計報告

【設計思路】

本文件系統采用兩級目錄，其中第一級對應于用戶賬號，第二級對應于用戶帳號下的文件。另外，為了簡便文件系統未考慮文件共享，文件系統安全以及管道文件與設備文件等特殊內容。

首先應確定文件系統的數據結構：主目錄、子目錄及活動文件等。主目錄和子目錄都以文件的形式存放于磁盤，這樣便于查找和修改。

用戶創建的文件，可以編號存儲于磁盤上。如：file0,file1,file2?并以編號作為物理地址，在目錄中進行登記。

【程序主要流程圖】

否

驗證是否成

功？

是

目錄

右鍵進行選擇 操作

新建目錄新建文件打開文件

結束

開始登錄刪除屬性 2

操作系統課程設計報告

【源程序清單】

typedef struct

//文件結構體 /*the structure of OSFILE*/ { int fpaddr;

/*file physical address*/

int flength;

/*file length*/

int fmode;

/*file mode:0-Read Only;1-Write Only;2-Read and Write;3-Protect;*/

char fname[MAXNAME];

/*file name*/ } OSFILE;

typedef struct

//用戶文件目錄結構體 user file directory /*the structure of OSUFD*/ { char ufdname[MAXNAME];

/*ufd name*/ OSFILE ufdfile[MAXCHILD];

/*ufd own file*/ }OSUFD;

typedef struct

//登陸

/*the structure of OSUFD'LOGIN*/ { char ufdname[MAXNAME];

/*ufd name*/

char ufdpword[8];

/*ufd password*/ } OSUFD_LOGIN;

typedef struct

//文件打開模式 /*file open mode*/ { int ifopen;

/*ifopen:0-close,1-open*/

int openmode;

/*0-read only,1-write only,2-read and write,3-initial*/ }OSUFD_OPENMODE;

void DeleteF()/*Delete File*/ { int i,j,k=0;char str[255],str1[255];char fname[MAXNAME];k=ExistD(dirname);//獲取用戶的序號

printf(“Please input filename:”);gets(fname);//獲得需要打開的文件名fname

for(i=0;i

if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0)

{

操作系統課程設計報告

}

}

void OpenF()/*Open File*/ { int i,k=0;char fname[MAXNAME];//printf(“nnC:%s>”,strupr(dirname));k=ExistD(dirname);printf(“Please input filename:”);gets(fname);//獲得需要打開的文件名fname

for(i=0;i

if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0)

{

ifopen[k][i].ifopen=1;//打開文件

ifopen[k][i].openmode=ufd[k]->ufdfile[i].fmode;//將讀寫屬性賦值

//test// printf(“i=%d,k=%dn”,i,k);

///test// printf(“openmode=%dn”,ifopen[k][i].openmode);

printf(“Open file successfully!n”);

break;//打開文件則跳出循環 itoa(ufd[k]->ufdfile[i].fpaddr,str,10);//itoa函數，把數字轉換成字符串

strcpy(str1,“file”);strcat(str1,str);strcpy(str,“c:osfilefile”);strcat(str,str1);strcat(str,“.txt”);//str為文件的物理路徑

if(remove(str)==0)

//調用remove函數刪除 第k個用戶的第i個文件ufd[k]->ufdfile[i]

{

fpaddrno[ufd[k]->ufdfile[i].fpaddr] = 0;//位示圖置為0，表示沒被占用

for(j = i;j<=fcount[k]-1;j++)//文件順序往前移一位

ufd[k]->ufdfile[j] = ufd[k]->ufdfile[j+1];

fcount[k] = fcount[k]-1;//文件數-1

printf(“Delete file successfully!n”);

//除了刪除原文件，還要 刪除dir中的東西

} else

printf(“Delete file fail!n”);break;}

操作系統課程設計報告

}

} }

void CloseF()/*Close File*/ {

int i,k=0;char fname[MAXNAME];

k=ExistD(dirname);printf(“Please input filename:”);gets(fname);//獲得需要關閉的文件名fname

for(i=0;i

if(strcmp(strupr(ufd[k]->ufdfile[i].fname),strupr(fname))==0)

{

ifopen[k][i].ifopen=0;//關閉文件

ifopen[k][i].openmode=4;//fmode改為初始值4

printf(“Close file successfully!n”);

break;

}

} }

void WriteF()/*Write File*/ { int i,k,n=0;char fname[MAXNAME];char str[255],str1[255];int flag=1;

if(strcmp(strupr(ltrim(rtrim(dirname))),“")==0)

{

printf(”nError.Please convert to ufd dir before read.n“);

wgetchar=1;

return;} printf(”nCaution:Open file firstn“);printf(”Opened File(s)List:n“);k=ExistD(dirname);

操作系統課程設計報告

for(i=0;i

//文件屬性為只寫或者是讀寫才能write

{

printf(”%15s“,ufd[k]->ufdfile[i].fname);

n++;} if((n%4==0)&&(n!=0))printf(”n“);

} printf(”n%d files openned.n“,n);

if(n==0)wgetchar=1;if(n!=0){ printf(”nPlease input FileName:“);gets(fname);ltrim(rtrim(fname));i=ExistF(fname);if(i>=0){

if(ifopen[k][i].ifopen==1)

{

if((ifopen[k][i].openmode==1)||(ifopen[k][i].openmode==2))

{

itoa(ufd[k]->ufdfile[i].fpaddr,str,10);

strcpy(str1,”file“);

strcat(str1,str);

strcpy(str,”c:osfilefile“);

strcat(str,str1);

strcat(str,”.txt“);//物理路徑

int length=0;

char c;

printf(”Please input text('#' stands for end):n“);

fp_file=fopen(str,”ab+“);//在文件末尾加 add bit

while((c=getchar())!='#')//以#為結尾

{

fputc(c,fp_file);

if(c!='n')length++;

}

//fprintf(fp_file,”n“);

操作系統課程設計報告

fclose(fp_file);

ufd[k]->ufdfile[fcount[i]-1].flength += length;//原長度加輸入長度

printf(”n'%s' has been written successfully!n“,fname);

}

else

{

printf(”nError.'%s' has been opened with WRITE ONLY mode.It isn't read.n“,fname);

wgetchar=1;

}

}

else

{

printf(”nError.'%s' is in closing status.Please open it before readn“,fname);

wgetchar=1;

}

}

else

{

printf(”nError.'%s' does not exist.n",fname);

wgetchar=1;

} } }

操作系統課程設計報告

【測試結果】

1、創建用戶

2、創建文件，并且打開讀取文件

操作系統課程設計報告

3、寫文件

4、刪除文件

操作系統課程設計報告

【設計總結】

這兩周的課程設計時間非常短，從中學到了很多知識，也為我們的學習提供了良好的實踐平臺。首先，通過老師的細心指導和同學們的相互幫助，讓我對題目【二級文件系統】有了進一步了解。接下來，主要是研究老師所給的大部分代碼，參考他的基本思路，并且思考每一個結構體在代碼中的具體作用。這期間和一些同學交流了各自的思路，在交流中，大家漸漸的明確了這個程序的思路、框架結構等。我們所做的主要是補充了刪除文件，打開文件，關閉文件，寫文件這幾個部分。

代碼編寫完了之后，實現了題目所要求的基本功能，但是在測試的過程中，還發現了這個程序存在各種各樣的bug。不斷的測試修改后，得到完善。

這次課設最大的收獲在于：學會交流以及相互幫助。在大家的交流溝通之中，我們解決了一個又一個難題。

在這次課設中，我還意識到，要把這門課真真正正地學好，不單單只是為了能夠應付考試，平時還要多加學習，多加努力才對。

【參考文獻】

【1】C語言程序設計（第三版）譚浩強

【2】計算機操作系統教程(第三版).張堯學 史美林 張高

【3】計算機操作系統,西安電子科技大學出版社，方敏主編,2004.8

第四篇：操作系統課程設計

操作系統課程設計

注意事項：

0.請每位同學必須按時提交課程設計報告（包括電子版和紙質版），算入期末成績

1.在三個題目中選擇一個

2.如果選擇題目

（一）進程調度算法，要求實現其中2個以上（包括2個）進程調度算法 3.如果選擇題目

（二）銀行家算法，要求能夠判斷系統的安全狀態

4.如果選擇題目

（三）頁面調度算法，要求實現其中2個以上（包含2個）進程調度算法 5.報告應包含算法分析、實驗截圖、核心算法源代碼，請各位同學認真對待，獨立完成 6.提交要求：電子版（包括實驗程序）請發至ropeal@163.com，紙質版請班長收齊，由班長統一在課堂上提交（并提交未交人員名單），截止時間第16周周三(2014.1.31)7.格式要求：

7.1 A4紙10頁左右

7.2 封面請注明班級、姓名、學號、所選題目

7.3 電子版發送時，請打包成一個文件，將文件名設置為：學號+姓名+題目名稱（如20130000張三進程調度算法課程設計），郵件主題同文件名

一、進程調度算法

1.1 實驗目的： a、設計進程控制塊PCB表結構，模擬實現進程調度算法：FIFO，靜態優先級調度，時間片輪轉調度，多級反饋隊列調度。（實現其中之二）。* b、建立進程就緒隊列。對不同算法編制入鏈子程序。c、編寫一進程調度程序模擬程序。模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。* 由用戶輸入進程名和進程長度，然后按照短進程優先的進程處理順序給出進程的排序。

1.2 實驗原理 調度算法是指：根據系統的資源分配策略所規定的資源分配算法。1.2.1 先來先服務和短作業（進程）優先調度算法

1.先來先服務調度算法。先來先服務（FCFS）調度算法是一種最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。由此可知，本算法適合于CPU繁忙型作業，而不利于I/O繁忙型的作業（進程）。

2.短作業（進程）優先調度算法。短作業（進程）優先調度算法（SJ/PF）是指對短作業或短進程優先調度的算法，該算法既可用于作業調度，也可用于進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。1.2.2 高優先權優先調度算法

1.優先權調度算法的類型。為了照顧緊迫性作業，使之進入系統后便獲得優先處理，引入了最高優先權優先（FPF）調度算法。此算法常被用在批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度，還可以用于實時系統中。當其用于作業調度，將后備隊列中若干個優先權最高的作業裝入內存。當其用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時，又可以進一步把該算法分成以下兩種： 1)非搶占式優先權算法

2)搶占式優先權調度算法（高性能計算機操作系統）

2.優先權類型。對于最高優先權優先調度算法，其核心在于：它是使用靜態優先權還是動態優先權，以及如何確定進程的優先權。3．高響應比優先調度算法

為了彌補短作業優先算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間 1.2.3 基于時間片的輪轉調度算法

1.時間片輪轉法。時間片輪轉法一般用于進程調度，每次調度，把CPU分配隊首進程，并令其執行一個時間片。當執行的時間片用完時，由一個記時器發出一個時鐘中斷請求，該進程被停止，并被送往就緒隊列末尾；依次循環。2.多級反饋隊列調度算法 多級反饋隊列調度算法多級反饋隊列調度算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度算法。其實施過程如下：

1)設置多個就緒隊列，并為各個隊列賦予不同的優先級。在優先權越高的隊列中，為每個進程所規定的執行時間片就越小。

2)當一個新進程進入內存后，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度?? 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最后隊列）后，便按第n隊列時間片輪轉運行。3)僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；僅當第1到第（i-1）隊列空時，才會調度第i隊列中的進程運行，并執行相應的時間片輪轉。4)如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列，則此新隊列搶占正在運行的處理機，并把正在運行的進程放在第i隊列的隊尾。

1．3 實驗要求

a、使用模塊化設計思想來設計； b、給出算法的流程圖或偽碼說明。c、學生可按照自身條件，隨意選擇采用的算法，（例如：采用冒泡法編寫程序，實現短進程優先調度的算法）

d、進程調度程序模擬程序只對PCB進行相應的調度模擬操作，不需要實際程序。

1.4 算法簡析 a、每個進程可有三個狀態，并假設初始狀態為就緒狀態。b、為了便于處理，程序中的某進程運行時間以時間片為單位計算。各進程的優先數或輪轉時間數以及進程需運行的時間片數的初始值均由用戶給定。c、在優先數算法中，優先數可以先取值為（50-該進程所需時間），進程每執行一次，優先數減3，CPU時間片數（CPUtime）加1，* 進程還需要的時間片數（needtime）減1。在時間片輪轉算法中，采用固定時間片

（即：每執行一次進程，該進程的執行時間片數為已執行了2個單位），這時，CPU時間片（CPUtime）數加2，* 進程還需要的時間片數（needtime）減2，并排列到就緒隊列的尾上。

d、對于遇到優先數一致的情況，采用FIFO策略解決。

二、銀行家算法

2.1 概述

2.1.1 設計目的1、了解多道程序系統中，多個進程并發執行的資源分配。

2、掌握死鎖的產生的原因、產生死鎖的必要條件和處理死鎖的基本方法。

3、掌握預防死鎖的方法，系統安全狀態的基本概念。

4、掌握銀行家算法，了解資源在進程并發執行中的資源分配策略。

5、理解死鎖避免在當前計算機系統不常使用的原因

2.2 關于死鎖

2.2.1 死鎖概念：

在多道程序系統中，雖可借助于多個進程的并發執行，來改善系統的資源利用率，提高系統的吞吐量，但可能發生一種危險━━死鎖。所謂死鎖(Deadlock),是指多個進程在運行中因爭奪資源而造成的一種僵局(Deadly_Embrace),當進程處于這種僵持狀態時，若無外力作用，它們都將無法再向前推進。一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現象稱為進程死鎖，這一組進程就稱為死鎖進程。

2.2.2 關于死鎖的一些結論：

參與死鎖的進程最少是兩個（兩個以上進程才會出現死鎖）

參與死鎖的進程至少有兩個已經占有資源

參與死鎖的所有進程都在等待資源

參與死鎖的進程是當前系統中所有進程的子集

注：如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰。

2.2.3 資源分類：

永久性資源： 可以被多個進程多次使用（可再用資源），分為：可搶占資源與不可搶占資源

臨時性資源：只可使用一次的資源；如信號量,中斷信號，同步信號等（可消耗性資源）

“申請--分配--使用--釋放”模式

2.2.4 產生死鎖的四個必要條件：

1、互斥使用（資源獨占）

一個資源每次只能給一個進程使用

2、不可強占（不可剝奪）

資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放

3、請求和保持（部分分配，占有申請）

一個進程在申請新的資源的同時保持對原有資源的占有（只有這樣才是動態申請，動態分配）

4、循環等待

存在一個進程等待隊列

{P1 , P2 , ? , Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，?，Pn等待P1占有的資源，形成一個進程等待環路

2.2.5 死鎖的解決方案 1 產生死鎖的例子

申請不同類型資源產生死鎖

P1： ?

申請打印機 申請掃描儀 使用

釋放打印機 釋放掃描儀 ? P2： ?

申請掃描儀 申請打印機 使用

釋放打印機 釋放掃描儀 ?

申請同類資源產生死鎖（如內存）

設有資源R，R有m個分配單位，由n個進程P1,P2,?,Pn（n > m）共享。假設每個進程對R的申請和釋放符合下列原則： * 一次只能申請一個單位 * 滿足總申請后才能使用 * 使用完后一次性釋放

m=2，n=3 資源分配不當導致死鎖產生

2死鎖預防: 定義:在系統設計時確定資源分配算法，保證不發生死鎖。具體的做法是破壞產生死鎖的四個必要條件之一

①破壞“不可剝奪”條件

在允許進程動態申請資源前提下規定，一個進程在申請新的資源不能立即得到滿足而變為等待狀態之前，必須釋放已占有的全部資源，若需要再重新申請 ②破壞“請求和保持”條件

要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當該進程所要資源均可滿足時才給予一次性分配 ③破壞“循環等待”條件 采用資源有序分配法：

把系統中所有資源編號，進程在申請資源時必須嚴格按資源編號的遞增次序進行，否則操作系統不予分配。

2.2.6 安全狀態與不安全狀態

安全狀態： 如果存在一個由系統中所有進程構成的安全序列P1，?Pn，則系統處于安全狀態。一個進程序列{P1，?，Pn}是安全的，如果對于每一個進程Pi(1≤i≤n），它以后尚需要的資源量不超過系統當前剩余資源量與所有進程Pj(j < i)當前占有資源量之和，系統處于安全狀態(安全狀態一定是沒有死鎖發生的)。

不安全狀態:不存在一個安全序列，不安全狀態一定導致死鎖。

2.3 數據結構設計

1.可利用資源向量矩陣AVAILABLE。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果AVAILABLE [j]= K，則表示系統中現有R類資源K個

2.最大需求矩陣MAX。這是一個n*m的矩陣，用以表示每一個進程對m類資源的最大需求。如果MAX [i,j]=K，則表示進程i需要R類資源的數目為K。

3.分配矩陣ALLOCATION。這也是一個n*m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果ALLOCATION [i,j]=K，則表示進程i當前已分得R類資源的數目為K。

4.需求矩陣NEED。這也是一個n*m的矩陣，用以表示每一個進程尚需的各類資源數。如果NEED [i,j]=K，則表示進程i還需要R類資源K個，才能完成其任務。上述矩陣存在下述關系：

NEED [i,j]= MAX[i,j]﹣ ALLOCATION[i,j]

2.4 算法的實現 2.4.1 初始化 由用戶輸入數據，分別對可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。2.4.2 銀行家算法

在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統始終都處于安全狀態，便可以避免發生死鎖。

銀行家算法的基本思想是分配資源之前,判斷系統是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。

設進程cusneed提出請求REQUEST [i]，則銀行家算法按如下規則進行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(2)；否則，出錯。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(3)；否則，出錯。(3)系統試探分配資源，修改相關數據： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統執行安全性檢查，如安全，則分配成立；否則試探險性分配作廢，系統恢復原狀，進程等待。

2.4.3 安全性檢查算法

(1)設置兩個工作向量Work=AVAILABLE;FINISH(2)從進程集合中找到一個滿足下述條件的進程，FINISH==false;NEED<=Work;如找到，執行(3)；否則，執行(4)(3)設進程獲得資源，可順利執行，直至完成，從而釋放資源。

Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的進程Finish= true，則表示安全；否則系統不安全。

三、頁面調度算法 3.1 實驗名稱

頁式虛擬存儲管理：頁面調度算法 3.2 實驗目的

頁式虛擬存儲器實現的一個難點是設計頁面調度（置換）算法，即將新頁面調入內存時，如果內存中所有的物理頁都已經分配出去，就要按某種策略來廢棄某個頁面，將其所占據的物理頁釋放出來，供新頁面使用。本實驗的目的是通過編程實現幾種常見的頁面調度（置換）算法，加深讀者對頁面思想的理解。3.3 實驗原理

頁面調度算法

目前有許多頁面調度算法，本實驗主要涉及先進先出調度算法、最近最少調度算法、最近最不常用調度算法。本實驗使用頁面調度算法時作如下假設，進程在創建時由操作系統為之分配一個固定數目物理頁，執行過程中物理頁的數目和位置不會改變。也即進程進行頁面調度時只能在分到的幾個物理頁中進行。

下面對各調度算法的思想作一介紹。

<1> 先進先出調度算法

先進先出調度算法根據頁面進入內存的時間先后選擇淘汰頁面，先進入內存的頁面先淘汰，后進入內存的后淘汰。本算法實現時需要將頁面按進入內存的時間先后組成一個隊列，每次調度隊首頁面予以淘汰。

<2>最近最少調度算法

先進先出調度算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。

<3>最近最不常用調度算法

由于程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬件或操作系統自動定時清零。

缺頁調度次數和缺頁中斷率、缺頁置換率計算

缺頁中斷次數是缺頁時發出缺頁中斷的次數。

缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%

缺頁調度次數是調入新頁時需要進行頁面調度的次數

缺頁置換率=缺頁調度次數/總的頁面引用次數*100% 3.4 實驗內容

（1）設計程序實現以上三種頁面調度算法，要求：

①.可以選擇頁面調度算法類型；

②.可以為進程設置分到物理頁的數目，設置進程的頁面引用情況，可以從鍵盤輸入頁面序列，也可從文件中讀??；

③.隨時計算當前的頁面調度次數的缺頁中斷率；

④.使用敲鍵盤或響應WM-TIMER的形式模仿時間的流逝；

⑤.以直觀的的形式將程序的執行情況顯示在計算機屏幕上；

⑥.存盤及讀盤功能，可以隨時將數據存入磁盤文件，供以后重復實驗時使用。

（2）假定進程分配到3個物理塊，對于下面的頁面引用序列：（test.txt）

7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1

請分別用先進和先出調度算法，最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。

再假定進程分配到4、5個物理塊，重復本實驗。

（3）假定進程分配到3個物理塊，對于下面的頁面引用序列：（test2.txt）

4-3-2-1-4-3-5-4-3-2-1-5-0-7-3-8-9-0-2-1-4-7-3-9

請分別用先進先出調度算法、最近最少用調度算法，最近最不常用調度算法計算缺頁中斷次數，缺頁中斷率和缺頁調度次數、缺頁置換率。

再假定進程分配到4、5個物理塊，重復本實驗。

（4）假定進程分配到3個物理塊，使用程序的動態頁面序列生成算法，生成一個頁面序列，將此序列存入磁盤文件。再從磁盤文件讀入該序列，用程序分別計算三種算法下的缺頁中斷次數、缺頁中斷率和缺頁調度次數、缺頁置換率。

第五篇：操作系統課程設計

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

（操作系統課程設計）

連續動態分區內存

管理模擬實現

學生姓名： 韓 慧 學生學號： 031140312 班 級： 031140--3 0311401、02、03、04班制

二〇一三年十二月 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

目錄

《操作系統》課程設計.......................................................1 引言......................................................................3 課程設計目的和內容......................................................3 需求分析.........................................................................3 概要設計...................................................................3 開發環境........................................................................4 系統分析設計.....................................................................4 有關了解內存管理的相關理論..................................................4 內存管理概念........................................................................4 內存管理的必要性..............................................................4 內存的物理組織.............................................................4 什么是虛擬內存.................................................................5 連續動態分區內存管理方式...................................................5 單一連續分配（單個分區)...................................................5

固定分區存儲管理...............................................................5 可變分區存儲管理（動態分區）..............................................5 可重定位分區存儲管理........................................................5 問題描述和分析....................................................................6 程序流程圖........................................................................6 數據結構體分析..................................................................8 主要程序代碼分析...............................................................9 分析并實現四種內存分配算法.................................................11 最先適應算.....................................................................11 下次適應分配算法..........................................................13 最優適應算法...............................................................16 最壞適應算法...............................................................18 回收內存算法................................................................20 調試與操作說明.................................................................22

初始界面.......................................................................22 模擬內存分配...............................................................23

已分配分區說明表面............................................................24 空閑區說明表界面.............................................................24 回收內存界面.....................................................................25 重新申請內存界面..........................................................26.總結與體會......................................................................28 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

參考文獻.........................................................................28

引言

操作系統是最重要的系統軟件，同時也是最活躍的學科之一。我們通過操作系統可以理解計算機系統的資源如何組織，操作系統如何有效地管理這些系統資源，用戶如何通過操作系統與計算機系統打交道。

存儲器是計算機系統的重要組成部分，近年來，存儲器容量雖然一直在不斷擴大，但仍不能滿足現代軟件發展的需要，因此，存儲器仍然是一種寶貴而又緊俏的資源。如何對它加以有效的管理，不僅直接影響到存儲器的利用率，而且還對系統性能有重大影響。而動態分區分配屬于連續分配的一種方式，它至今仍在內存分配方式中占有一席之地。

課程設計目的和內容：

理解內存管理的相關理論，掌握連續動態分區內存管理的理論；通過對實際問題的編程實現，獲得實際應用和編程能力。

編寫程序實現連續動態分區內存管理方式，該程序管理一塊虛擬內存，實現內存分配和回收功能。分析并實現四種內存分配算法，即最先適應算法，下次最先適應算法，最優適應算法，最壞適應算法。內存分配算法和回收算法的實現。

需求分析

動態分區分配是根據進程的實際需要，動態地為之分配內存空間。在實現動態分區分配時，將涉及到分區分配中所用的數據結構、分區分配算法和分區的分配和回收操作這樣三個問題。常用的數據結構有動態分區表和動態分區鏈。在對數據結構有一定掌握程度的情況下設計合理的數據結構來描述存儲空間，實現分區存儲管理的內存分配功能，應該選擇最合適的適應算法（首次適應算法，最佳適應算法，最后適應算法，最壞適應算法），在動態分區存儲管理方式中主要實現內存分配和內存回收算法，在這些存儲管理中間必然會有碎片的產生，當碎片產生時，進行碎片的拼接等相關的內容

概要設計

本程序采用機構化模塊化的設計方法，共分為四大模塊。⑴最先適應算法實現

從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在于減少查找時間。為適應這種算法，空閑分區表（空閑區鏈）中的空閑分區要按地址由低到高進行排序。該算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。⑵下次適應分配算法實現 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

該算法是最先適應算法的變種。在分配內存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到空閑區的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區為止，并從中劃出一塊與請求大小相等的內存空間分配給作業。該算法能使內存中的空閑區分布得較均勻。⑶最優適應算法實現

它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此算法，空閑分區表（空閑區鏈）中的空閑分區要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。⑷最壞算法實現

最壞適應分配算法要掃描整個空閑分區或鏈表，總是挑選一個最大的空閑分區分割給作業使用。該算法要求將所有的空閑分區按其容量從大到小的順序形成一空閑分區鏈，查找時只要看第一個分區能否滿足作業要求。

開發環境：

win7 下 VC++6.0 系統分析設計：

相關算法原理，算法流程圖，涉及的數據結構內容都相應包含在各章節中

有關了解內存管理的相關理論

內存管理概念：

內存管理，是指軟件運行時對計算機內存資源的分配和使用的技術。其最主要的目的是如何高效，快速的分配，并且在適當的時候釋放和回收內存資源。內存不是預先劃分好的，而是在系統運行的過程中建立分區.當作業裝入主存時，根據作業所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區給該作業；否則令該作業等待.分區長度不固定分區個數不固定。這種存儲管理的方法克服了固定分區嚴重浪費主存的問題，提高了主存資源的利用率。

內存管理的必要性：

內存管理對于編寫出高效率的 Windows 程序是非常重要的，這是因為Windows 是多任務系統，它的內存管理和單任務的 DOS 相比有很大的差異。DOS是單任務操作系統，應用程序分配到內存后，如果它不主動釋放，系統是不會對它作任何改變的；但 Windows 卻不然，它在同一時刻可能有多個應用程序共享內存，有時為了使某個任務更好地執行，Windows 系統可能會對其它任務分配的內存進行移動，甚至刪除。因此，我們在 Windows 應用程序中使用內存時，要遵循Windows 內存管理的一些約定，以盡量提高 Windows 內存的利用率。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

1.3 內存的物理組織：

物理地址：

把內存分成若干個大小相等的存儲單元，每個存儲單元占 8 位，稱作字節（byte）。每個單元給一個編號，這個編號稱為物理地址（內存地址、絕對地址、實地址）。

二、物理地址空間： 物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維空間。

什么是虛擬內存：

虛擬內存是內存管理技術的一個極其實用的創新。它是一段程序（由操作系統調度），持續監控著所有物理內存中的代碼段、數據段，并保證他們在運行中的效率以及可靠性，對于每個用戶層（user-level）的進程分配一段虛擬內存空間。當進程建立時，不需要在物理內存件之間搬移數據，數據儲存于磁盤內的虛擬內存空間，也不需要為該進程去配置主內存空間，只有當該進程被被調用的時候才會被加載到主內存。

連續動態分區內存管理方式的實現

在早期的操作系統中，主存分配廣泛采用連續分配方式。連續分配方式，是指為一個用戶程序分配一個連續的內存空間，該連續內存空間指的的是物理內存。下面介紹連續分配的四種方式。

單一連續分配（單個分區）

最簡單的存儲管理方式，用于多道程序設計技術之前。內存分為系統區和用戶區，系統區由操作系統使用。用戶區作為一個連續的分區分配給一個作業。分區存儲管理是滿足多道程序設計的最簡單的一種存儲管理方法，它允許多 4個用戶程序同時存在系統內存中，即共享內存空間。按分區劃分方式可分為固定分區和可變分區。

固定分區存儲管理

把內存的用戶區預先劃分成多個分區，每個分區大小可以相同，也可以不同。（分區的劃分由計算機的操作員或者由操作系統給出，并給出主存分配表）分區個數固定，分區的大小固定。一個分區中可裝入一個作業，作業執行過程中不會改變存放區域。早期的 IBM 的 OS/MFT（具有固定任務數的多道程序系統）采用了這種固定分區的方法。

可變分區存儲管理（動態分區）

內存不是預先劃分好的，而是在系統運行的過程中建立分區.當作業裝入主存時，根據作業所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個分區給該作業；否則令該作業等待。分區長度不固定分區個數不固定。這種存儲管理的方法克服了固定分區嚴重浪費主存的問題，提高了主存資源的利用率。ＩＢＭ操作系統ＯＳ／ＭＶＴ采用可變分區存儲管理。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

可重定位分區存儲管理

解決碎片問題的一種簡單方法是采用可重定位分區分配.。其中心思想是，把不同程序，且在內存中地址不連續的想法讓他們連續。

例：內存中現有 3 個空閑區，現有一作業到達，要求獲得 30k 內存空間，沒有分區滿足容量要求，若想把作業裝入，可將內存中所有作業進行移動，這樣把原來分散的空閑區匯集成一個大的空閑區。將內存中的作業進行移動使它們連接在一起把原來分散的多個小分區拼接成一個大的空閑區.這個過程稱為”緊湊”或”移動”。需解決的問題:每次”緊湊”后程序或數據裝入的物理地址變化采用動態重定位。

問題描述和分析

系統應利用某種分配算法，從空閑分區鏈表中找到所需大小的分區，如果空閑分區大小大于請求分區大小，則從該分區中按改請求的大小劃分出一塊內存空間大小劃分出一塊內存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區的首址返回給調用者。

當進程運行完畢師范內存時，系統根據回收區的首址，從空閑區中找到相應的插入點，此時可能出現以下四種情況之一：

⑴該空閑區的上下兩相鄰分區都是空閑區：將三個空閑區合并為一個空閑區。新空閑區的起始地址為上空閑區的起始地址，大小為三個空閑區之和?？臻e區合并后，取消可用表或自由鏈中下空閑區的表目項或鏈指針，修改上空閑區的對應項。

⑵該空閑區的上相鄰區是空閑區：將釋放區與上空閑區合并為一個空閑區，其起始地址為上空閑區的起始地址，大小為上空閑區與釋放區之和。合并后，修改上空閑區對應的可用表的表目項或自由鏈指針。

⑶該空閑區的下相鄰區是空閑區：將釋放區與下空閑區合并，并將釋放區的起始地址作為合并區的起始地址。合并區的長度為釋放區與下空閑區之和。同理，合并后修改可用表或自由鏈中相應的表目項或鏈指針。

⑷兩相鄰區都不是空閑區：釋放區作為一個新空閑可用區插入可用表或自由鏈。

程序流程圖

內存分配流程圖，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

從頭開始查表檢索完否？NY返回分區大小>所需大小N繼續檢索下一個表項Y分區大小-所需大小<=不可再分割大小N從該分區中劃出所需大小的新分區Y將該分區從鏈中移出將該分區分配給請求者修改有關數據結構返回

內存回收流程圖，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

開始判斷空閑區上下內存情況上為空下為空上下都為空上下都不為空將上面的空閑區合并，并回收將下面的空閑區合并，并回收將上下的空閑區合并，并回收直接將其回收結束 數據結構體分析

⑴進程屬性結構體 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空閑鏈表結構體 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配鏈表結構體 typedef struct busyspace { int from;readyque r;湖北民族學院信息工程學院11級計算機專業操作系統課程設計

busyspace * next;}busyspace,*busy

主要程序代碼分析

⑴主函數//代碼請添加適當的注釋。int main(){ Is=(idly)malloc(sizeof(idlyspace));Is->from=0;Is->size=256;Is->next=NULL;Is2=Is;Bs=(busy)malloc(sizeof(busyspace));Bs->next=NULL;int t,t1;printf(“n.......................歡迎來到動態分區存儲管理系統..................nn”);printf(“...........................請選擇要執行的算法:...........................n”);printf(“.........................1.最先適應算法

...............................n”);printf(“.........................2.下次適應算法............................n”);printf(“..........................3.最優適應算法

...............................n”);printf(“.........................4.最壞適應算法................................n”);printf(“........................................................................n”);printf(“請輸入您的選擇:”);scanf(“%d”,&t);int i;while(i!=5){

printf(“........................................................................n”);

printf(“.........................操作菜單如下：（請選擇）.......................n”);

printf(“..........................1.輸入進程分配空間...........................n”);

printf(“.........................2.進程撤銷回收空間...........................n”);

printf(“.........................3.輸出所有空閑分區

..........................n”);

printf(“..........................4.輸出所有已分配分區..........................n”);

printf(“..........................5.退

出..........................n”);

printf(“........................................................................n”);

scanf(“%d”,&i);

switch(i)

{

case 1:

switch(t)

{

case 1:

t1=FF();湖北民族學院信息工程學院11級計算機專業操作系統課程設計

break;

case 2:

t1=NF();

break;

case 3:

t1=BF();

break;

case 4:

t1=WF();

break;

default:

printf(“選擇算法錯誤n”);

return 1;

}

if(t1)

printf(“分配空間成功n”);

else

printf(“分配空間失敗n”);

break;

case 2:

t1=recover();

if(t1)

printf(“回收成功n”);

else

printf(“回收失敗n”);

break;

case 3:

Isprint();

break;

case 4:

Bsprint();

break;

} } return 0;}

第三章 ：分析并實現四種內存分配算法

最先適應算法

空閑區按地址從小到大的次序排列。

分配：當進程申請大小為 SIZE 的內存時，系統順序查找空閑區表（鏈），直到找到容量滿足要求（≥SIZE）的空閑區為止。從該空閑區中劃出大小為 SIZE的分區分配給進程，余下的部分仍作為一個空閑區，但要修改其首址和大小。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

優點：這種算法是盡可能地利用低地址部分的空閑區，而盡量地保證高地址 6部分的大空閑區，有利于大作業的裝入。

缺點:主存低地址和高地址分區利用不均衡。在低地址部分集中了許多非常小的空閑區碎片降低了主存的利用率。最先適應算法 int FF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

idly l=Is;int mt=256;busy b=Bs;idly min=NULL;while(l)

//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結點

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

//如果找到則為進程分配空間

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

下次適應分配算法

最先適應算法的變種。

總是從空閑區上次掃描結束處順序查找空閑區表（鏈），直到找到第一個滿足容量要求的空閑區為止，分割一部分給作業，剩余部分仍作為空閑區。下次適應分配算法 int NF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//尋找空閑表中大小滿足申請進程所需大小并且起址最小的空閑結點

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

//如果找到則為進程分配空間

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

}

//將申請空間進程插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改相應空閑節點的起址和大小

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

結點

t=1;

return t;}

l=Is;//l指向空閑表的頭

while(l!=Is2)

{

if(D.size<=l->size)

{

if(l->from

{ mt=l->from;min=l;t=1;

}

}

l=l->next;} if(mt!=256){

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

//ls2指向修改結點的下一個

//循環查找 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

while(b->next)

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

Is2=min->next;

t=1;

return t;} return t;}

最優適應算法

空閑區按容量遞增的次序排列。

分配：當進程申請存儲空間，系統順序查找空閑區表（鏈），直到找到第一個滿足容量要求的空閑區為止。采用最優適應算法選中的空閑區是滿足容量要求的最小空閑區。優點：選中的空閑區是滿足容量要求的最小空閑區，而不致于毀掉較大的空閑區。

缺點：空閑區的大小一般與申請分區大小不相等，因此將其一分為二，留下來的空閑區一般情況下是很小的，以致無法使用。隨著時間的推移，系統中的小空閑區會越來越多，從而造成存儲空間的浪費。最優適應算法 int BF(){ int t=0;湖北民族學院信息工程學院11級計算機專業操作系統課程設計

readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);scanf““%””,&D.size);

idly l=Is;idly min=NULL;int mt=256;busy b=Bs;while(l)//在空閑鏈中尋找第一個大于所輸入的進程大小的空閑塊

{

if(D.size<=l->size)

{

if(l->size

{

mt=l->size;min=l;t=1;

}

}

l=l->next;} if(mt!=256)

{

busy j;

j=(busy)malloc(sizeof(busyspace));空間

j->from=min->from;

//申請分配用于存放進程的內存

//找到第一個滿足要求的空閑塊

//將第一個滿足要求的空閑塊（min）的首地址賦給j

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];16 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

}

j->r.size=D.size;

while(b->next)

//按從小到大的順序查找新進程在已分配區中的位置

{ if(b->next->fromfrom)

b=b->next;else

break;

}

j->next=b->next;

b->next=j;

min->from=min->from+D.size;

min->size=min->size-D.size;

} return t;}

最壞適應算法

為了克服最佳適應算法把空閑區切割得太小的缺點，人們提出了一種最壞適應算法，即每次分配時，總是將最大的空閑區切去一部分分配給請求者，剩余的部分仍是一個較大的空閑區。避免了空閑區越分越小的問題。要求空閑區按容量遞減的順序排列。

分配：進程申請存儲區時，檢查空閑區表（鏈）的第一個空閑區的大小是否滿足要求，若不滿足則令進程等待；若滿足則從該空閑區中分配一部分存儲區給用戶，剩下的部分仍作為空閑區。最壞適應算法 int WF(){ int t=0;readyque D;printf““請輸入進程名:””);scanf““%””,D.name);

printf““輸入進程申請空間大小:””);

//將所輸入的進程插入進程鏈

//改變該空閑塊的起始地址 //改變該空閑塊的剩余大小 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

scanf““%””,&D.size);

//輸入進程申請的空間大小

idly l=Is;//l指向空閑鏈表ls頭

idly min=NULL;int mt=0;busy b=Bs;

//b指向已分配鏈表Bs頭

//找到空閑分區中大小滿足進程的請求且尺寸最大的結點

while(l){

if(D.size<=l->size)//判斷進程所申請的大小是否小于空閑區的各結點大小

{

if(l->size>mt)

{ mt=l->size;min=l;//min指向空閑區中尺寸最大的結點

t=1;

}

}

l=l->next;} if(mt!=0)點

{

busy j;

j=(busy)malloc(sizeof(busyspace));

j->from=min->from;

for(int i=0;i<10;i++)

{

j->r.name[i]=D.name[i];

}

j->r.size=D.size;

//判斷是否找到了空閑區的滿足結

//l指向空閑鏈表下一個結點

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

while(b->next)置

//尋找插入到已分配鏈表中的位

{ if(b->next->fromfrom)

b=b->next;else

break;

}

//把此進程結點j插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改空閑鏈表的相應結點的參數

min->from=min->from+D.size;

min->size=min->size-D.size;} return t;}

可變分區的回收

當某個進程釋放某存儲區時，系統首先檢查釋放區是否與系統中的空閑區相鄰若相鄰則把釋放區合并到相鄰的空閑區去，否則把釋放區作為一個空閑區插入到空閑表的適當位置。

釋放區與空閑區相鄰的四種情況。

（1）釋放區與前空閑區相鄰：把釋放區與前空閑區合并到一個空閑區。其首址仍為前空閑區首址，大小為釋放區大小與空閑區大小之和。

（2）釋放區與后空閑區相鄰：則把釋放區合并到后空閑區，其首地址為釋放區首地址，大小為二者之和。

（3）釋放區與前后兩空閑區相鄰：這三個區合為一個空閑區，首地址為前空閑區首址，大小為這三個空閑區之和，并取消后空閑區表目。

（4）釋放區不與任何空閑區相鄰：將釋放區作為一個空閑區，將其大小和首址插入到空閑區表的適當位置。

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

回收內存算法

int recover(){ readyque D;printf““請輸入想要回收的進程名””);

scanf““%””,D.name);

busy b=Bs;idly l=Is;while(b->next)鏈表中

{

bool yo=1;

for(int i=0;i<10;i++)

{

if(b->next->r.name[i]==D.name[i])yo=yo*1;

else yo=0;

}

//如果在已分配鏈表中則釋放該結點所占空間

if(yo)

{

int t=b->next->from;

int ts=b->next->r.size;

//查找輸入的進程名是否在已分配湖北民族學院信息工程學院11級計算機專業操作系統課程設計

while(l)

{ if(l->from>t+ts)不鄰接

{ idly tl;tl=(idly)malloc(sizeof(idlyspace));tl->from=t;tl->size=ts;tl->next=l;Is=tl;break;} if(l->from==t+ts)

l->from=t;

l->size=l->size+ts;

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;}

if(l->from+l->size

idly tl;

tl=(idly)malloc(sizeof(idlyspace));

tl->from=t;

tl->size=ts;

tl->next=l->next;

l->next=tl;

break;}

else if(l->from+l->size==t)

//所回收進程與空閑結點上鄰接 {

//所回收進程與空閑結點上下都不鄰接

//所回收進程與空閑結點下鄰接 {

//所回收進程與空閑結點上下都 21 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

l->size=l->size+ts;

if(l->from+l->size==l->next->from)接

{

l->size=l->size+l->next->size;

idly tm=l->next;

l->next=l->next->next;

freI);

}

br

l=l->next;

}

//從已分配鏈表中釋放所回收進程

busy tb=b->next;

b->next=b->next->next;

free(tb);

return 1;

}

b=b->next;} printf(“沒找到這”進程n”);return 0;}

//所回收進程與空閑結點上下都鄰調試與操作說明

初始界面

程序初始界面，有四個塊選擇，選擇要執行的算法，調試以最壞算法為例，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

選擇最壞適應算法，如圖

模擬內存分配

給進程a分配內存20，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

已分配分區說明表界面

同理，給進程b分配內存30，給進程c分配內存40，給進程d分配50，給進程e分配60，如圖

空閑分區說明表界面 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

查看空閑分區，如圖

回收內存界面

回收進程b和d所占內存，如圖

已分配分區說明表和空閑分區說明表 如圖 湖北民族學院信息工程學院11級計算機專業操作系統課程設計

重新申請內存界面

再為新進程i分配內存30，如圖

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

根據最壞適應算法結合圖所示可知，該算法將會從空閑分區表中選擇一塊最大的內存空間分配給進程i，從圖也可看出該模擬算法實現了最壞適應算法

湖北民族學院信息工程學院11級計算機專業操作系統課程設計

總結與體會

本次做的課題是動態分區分配算法實現，此次課程設計成功實現了內存分配和內存回收，內存分配中包含了四種算法，分別是首次適應算法，循環首次適應算法，最佳適應算法和最壞適應算法。經編碼調試，表明該程序模塊是有效可行的。

通過這門課程的學習讓我充分了解了內存管理的機制實現，從而更深一步的的對計算機

有了很多了解，這對于以后我們的研究和學習計算機系統起到了很重要的作用。

對于本次論文制作，自己的編程能力有所提高，對操作系統內存分配，存儲空間的回收都有全新的認識。

在這次操作系統課程設計中，我使用了c++編寫系統軟件，對os中可變分區存儲管理有了深刻的理解，但是過程中遇到了很多困難，一邊做一邊學，對c++有了比較多的理解。

實驗中遇到很多問題，浪費了很多時間，總而言之是自己學習還不夠好，不扎實，希望在以后學習中加以改善，學到更多知識。

參考文獻

【1】 湯子瀛，哲鳳屏，湯小丹.計算機操作系統.西安：西安電子科技大學出版社，2001.。湖北民族學院信息工程學院11級計算機專業操作系統課程設計

【2】 任愛華.操作系統實用教程.北京：清華大學出版社，2001。