第一篇：操作系統(tǒng)課程設(shè)計(jì)報(bào)告

操 作 系 統(tǒng)

課

程

設(shè)

計(jì)

實(shí)

驗(yàn)

報(bào)

告

學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

班級(jí)：計(jì)112

學(xué)號(hào)：1113022032

姓名:

一、實(shí)驗(yàn)名稱(chēng)：

用C++實(shí)現(xiàn)驅(qū)動(dòng)調(diào)度算法、頁(yè)面替換算法、銀行家算法、處理器調(diào)度算法

二、實(shí)驗(yàn)要求：

書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告，包括的內(nèi)容有：

（1）實(shí)驗(yàn)題目

（2）程序中使用的數(shù)據(jù)結(jié)構(gòu)及主要文字說(shuō)明

（3）帶有注釋的源程序

（4）執(zhí)行程序說(shuō)明，表明各進(jìn)程控制快的初始狀態(tài)，以及各算法的運(yùn)行狀態(tài)

（5）通過(guò)實(shí)驗(yàn)后的收獲與體會(huì)及對(duì)實(shí)驗(yàn)的改進(jìn)意見(jiàn)和見(jiàn)解

二、實(shí)驗(yàn)?zāi)康模?/p>

通過(guò)自己編程來(lái)實(shí)現(xiàn)各類(lèi)操作系統(tǒng)算法，進(jìn)一步理解操作系統(tǒng)的概念及含義，提高對(duì)操作系統(tǒng)的認(rèn)識(shí)，同時(shí)提高自己的動(dòng)手實(shí)踐能力。加強(qiáng)我們對(duì)各類(lèi)算法的理解。

三、實(shí)驗(yàn)內(nèi)容：

1、實(shí)現(xiàn)頁(yè)面替換算法

（1）FIFO 先進(jìn)先出頁(yè)面替換算法

（2）LRU最近最少使用頁(yè)面替換算法

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

2、銀行家算法

3、實(shí)現(xiàn)驅(qū)動(dòng)調(diào)度算法

（1）先來(lái)先服務(wù)算法

（2）電梯算法

（3）掃描算法

4、實(shí)現(xiàn)處理器調(diào)度

（1）先進(jìn)先出處理器調(diào)度

（2）時(shí)間片輪轉(zhuǎn)法

（3）優(yōu)先級(jí)調(diào)度

四、實(shí)驗(yàn)原理：

1、頁(yè)面替換算法

先進(jìn)先出頁(yè)面置換算法：該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面加以淘汰。將已調(diào)入內(nèi)存的頁(yè)面按先后次序鏈接成一個(gè)隊(duì)列，將最先調(diào)入的頁(yè)面與新頁(yè)面進(jìn)行置換

最近最久未使用置換算法：該算法是利用“最近的過(guò)去”作為“最近的將來(lái)”，將最近最久未使用的頁(yè)面加以淘汰。將已調(diào)入內(nèi)存的頁(yè)面按先后順序鏈接成一個(gè)隊(duì)列，為每一個(gè)頁(yè)面增加一個(gè)訪(fǎng)問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪(fǎng)問(wèn)以來(lái)所經(jīng)歷的是時(shí)間t，當(dāng)需淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大，即最近最久未使用的頁(yè)面加以淘汰

2、銀行家算法

先對(duì)用戶(hù)提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求的是不大于需要的，是否不大于可利用的。若請(qǐng)求合法，則進(jìn)行試分配。最后對(duì)試分配后的狀態(tài)調(diào)用安全性檢查算法進(jìn)行安全性檢查。若安全，則分配，否則，不分配，恢復(fù)原來(lái)狀態(tài)，拒絕申請(qǐng)。

3、驅(qū)動(dòng)調(diào)度算法

先進(jìn)先出算法（FIFO）：總是嚴(yán)格按時(shí)間順序?qū)Υ疟P(pán)請(qǐng)求予以處理。算法實(shí)現(xiàn)簡(jiǎn)單、易于理解并且相對(duì)公平，不會(huì)發(fā)生進(jìn)程餓死現(xiàn)象。但該算法可能會(huì)移動(dòng)的柱面數(shù)較多并且會(huì)

經(jīng)常更換移動(dòng)方向，效率有待提高

電梯調(diào)度算法：總是將一個(gè)方向上的請(qǐng)求全部處理完后，才改變方向繼續(xù)處理其他請(qǐng)求。

掃描算法（scan algorithm）：總是從最外向最內(nèi)（或最內(nèi)向最外）進(jìn)行掃描，然后在從最內(nèi)向最外（或最外向最內(nèi)）掃描。該算法與電梯調(diào)度算法的區(qū)別是電梯調(diào)度在沒(méi)有最外或最內(nèi)的請(qǐng)求時(shí)不會(huì)移動(dòng)到最外或最內(nèi)柱面。

4、處理器調(diào)度算法

先進(jìn)先出處理器調(diào)度：按照作業(yè)進(jìn)入系統(tǒng)后備工作隊(duì)列的先后次序來(lái)挑選作業(yè),先進(jìn)入系統(tǒng)的作業(yè)將優(yōu)先被挑選進(jìn)入主存,創(chuàng)建用戶(hù)進(jìn)程,分配所需資源,然后移入就緒隊(duì)列。

時(shí)間片輪轉(zhuǎn)法調(diào)度算法：調(diào)度次序每次把CPU分配給就緒隊(duì)列進(jìn)程/線(xiàn)程使用規(guī)

定的時(shí)間間隔，就緒隊(duì)列中每個(gè)進(jìn)程/線(xiàn)程輪流的運(yùn)行一個(gè)時(shí)間片，當(dāng)時(shí)間片耗盡時(shí)，就強(qiáng)迫當(dāng)前運(yùn)行進(jìn)程/線(xiàn)程讓出處理器，轉(zhuǎn)而排列到就緒隊(duì)列尾部，等候下一輪調(diào)度。

優(yōu)先級(jí)調(diào)度：根據(jù)確定的優(yōu)先級(jí)來(lái)選取進(jìn)程/線(xiàn)程，總是選擇就緒隊(duì)列中的優(yōu)先

級(jí)最高者投入運(yùn)行，即優(yōu)先級(jí)越高，先被調(diào)用。

五、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

對(duì)操作系統(tǒng)的各類(lèi)算法設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)如下：

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

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

void Bank()銀行家算法

bool Safe()安全性算法

驅(qū)動(dòng)調(diào)度算法：

struct MagneticHead//磁頭構(gòu)成{

int site;

int count;

bool direct;

}；

struct Range//磁盤(pán)磁道范圍

{

int mStart;

int mEnd;

};

struct RequestList//請(qǐng)求序列

{

int site;

bool state;

};

struct Data//基本數(shù)據(jù)集合{

MagneticHead magneticHead;

RequestList *requestList;

int *executeList;

Range range;

int length;

};

處理器調(diào)度：

typedef struct pcb//時(shí)間片輪轉(zhuǎn)法

{

char pname[N];

int runtime;

int arrivetime;

char state;

struct pcb*next;

}PCB;

typedef struct PCB1//先進(jìn)先出服務(wù)

{

char ID[3];//進(jìn)程號(hào)

char name[10];//進(jìn)程名

char state;//運(yùn)行狀態(tài)

floatarrivetime;//到達(dá)時(shí)間

floatstarttime;//進(jìn)程開(kāi)始時(shí)間

floatfinishtime;//進(jìn)程結(jié)束時(shí)間

floatservicetime;//服務(wù)時(shí)間

float turnaroundtime;//周轉(zhuǎn)時(shí)間

float weightedturnaroundtime;//帶權(quán)周轉(zhuǎn)時(shí)間

struct PCB1 *next;//指向下個(gè)進(jìn)程

}pcb1;

struct pcb2 {優(yōu)先級(jí)調(diào)度

char name[10];

char state;

int super;

int ntime;

int rtime;

struct pcb2* link;

}*ready=NULL,*d;

typedef struct pcb2 PCB2;

六、課程設(shè)計(jì)總結(jié)

在本次課程設(shè)計(jì)中，就是講平時(shí)所做的實(shí)驗(yàn)結(jié)合起來(lái)，實(shí)現(xiàn)操作系統(tǒng)的各類(lèi)算法，了解操作系統(tǒng)的運(yùn)行原理以及其基本概念，更好的將操作系統(tǒng)的原理很好的展現(xiàn)出來(lái)。同時(shí)，在本次實(shí)驗(yàn)中遇到了很多問(wèn)題，需要我們仔細(xì)的檢查和修改。其次，實(shí)驗(yàn)中為了能更好的體現(xiàn)各類(lèi)算法的運(yùn)行情況，需要做一個(gè)清晰的界面，以能清楚地看出運(yùn)行結(jié)果。

第二篇：操作系統(tǒng)課程設(shè)計(jì)報(bào)告

課程設(shè)計(jì)報(bào)告

題 目： 模擬請(qǐng)求頁(yè)式管理

課程名稱(chēng)： 計(jì)算機(jī)操作系統(tǒng) 學(xué) 院： 信息工程學(xué)院

專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)

班 級(jí)： 14計(jì)本（1）學(xué)生姓名： * * * 學(xué) 號(hào)： 201403031** 指導(dǎo)教師： * * 成 績(jī)：

開(kāi)課時(shí)間： 2016-2017 學(xué)年 一 學(xué)期

模擬請(qǐng)求頁(yè)式管理

第1章 需求分析

1.1設(shè)計(jì)要求

請(qǐng)求頁(yè)式管理是一種常用的虛擬存儲(chǔ)管理技術(shù)。本設(shè)計(jì)通過(guò)請(qǐng)求頁(yè)式存儲(chǔ)管理中頁(yè)面置換算法模擬設(shè)計(jì)，了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)，掌握請(qǐng)求頁(yè)式管理的頁(yè)面置換算法。本實(shí)驗(yàn)要求用Vc＋＋或其他高級(jí)語(yǔ)言編寫(xiě)和調(diào)試。

編寫(xiě)程序?qū)崿F(xiàn)：

（1）先進(jìn)先出頁(yè)面置換算法（FIFO）（2）最近最久未使用頁(yè)面置換算法（LRU）最佳置換頁(yè)面置換算法（OPT）設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，編程序演示以上三種算法的具體實(shí)現(xiàn)過(guò)程，并計(jì)算訪(fǎng)問(wèn)命中率。

1.2解決方案

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

1.3算法實(shí)現(xiàn)原理

1、先進(jìn)先出置換算法（FIFO）：

發(fā)生缺頁(yè)中斷時(shí)按照頁(yè)面進(jìn)入內(nèi)存順序總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面。

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

發(fā)生缺頁(yè)中斷時(shí)總是淘汰存在內(nèi)存中最長(zhǎng)時(shí)間未被使用的頁(yè)面。

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

發(fā)生缺頁(yè)中斷時(shí)若一個(gè)或幾個(gè)頁(yè)面將來(lái)將不會(huì)被調(diào)用則按先進(jìn)先出原則淘汰頁(yè)面，若將來(lái)都有調(diào)用則比較調(diào)用時(shí)刻選擇最遠(yuǎn)時(shí)刻頁(yè)面淘汰。

4、缺頁(yè)率：缺頁(yè)次數(shù)占頁(yè)面調(diào)用次數(shù)的百分比。

第2章 概要設(shè)計(jì)

2.1數(shù)據(jù)設(shè)計(jì)

常變量：調(diào)用頁(yè)面最大數(shù)量（MaxN），內(nèi)存最大頁(yè)面數(shù)（MaxM）待調(diào)用頁(yè)面數(shù)組：page_dd[MaxN]存放等待調(diào)用的頁(yè)面號(hào)

頁(yè)面數(shù)組專(zhuān)用指針 page_p，用于指向page_dd數(shù)組中正需調(diào)入內(nèi)存的頁(yè)號(hào) 內(nèi)存塊數(shù)組：Memery[MaxM]，存放內(nèi)存當(dāng)前存放的頁(yè)號(hào) 缺頁(yè)計(jì)數(shù)器：count，記錄缺頁(yè)次數(shù)

內(nèi)存塊狀態(tài)數(shù)組：M1[MaxN],M2[MaxN],M3[MaxN]，記錄每次頁(yè)面調(diào)用結(jié)束后內(nèi)存各塊的狀態(tài)

缺頁(yè)記錄數(shù)組s[MaxN]，用于記錄頁(yè)面調(diào)用時(shí)是否產(chǎn)生缺頁(yè)中斷，初始化為是

2.2函數(shù)設(shè)計(jì)

1、頁(yè)面添加函數(shù)：void btnAdd_Click(object sender, EventArgs e)用于實(shí)現(xiàn)通過(guò)點(diǎn)擊按鈕實(shí)現(xiàn)數(shù)據(jù)輸入。

2、內(nèi)存初始化函數(shù)：init(int[] a, int[] b,int []m1,int[]m2,int[]m3)參數(shù)有頁(yè)面數(shù)組、內(nèi)存數(shù)組、狀態(tài)數(shù)組，采用先進(jìn)先出算法對(duì)內(nèi)存先進(jìn)行裝滿(mǎn) 服務(wù)于先進(jìn)先出頁(yè)面置換函數(shù)和最佳置換函數(shù)。

3、輸出函數(shù)：void display(int[]a,int[]m1,int[]m2,int[]m3,char[]c)用于輸出模擬結(jié)果，參數(shù)有頁(yè)面數(shù)組，內(nèi)存數(shù)組，狀態(tài)數(shù)組，缺頁(yè)記錄數(shù)組。再模擬之后調(diào)用。

4、模擬控制函數(shù)：void btnmo_Click(object sender, EventArgs e）用于實(shí)現(xiàn)通過(guò)單擊模擬按鈕，根據(jù)用戶(hù)所選算法進(jìn)行模擬并顯示結(jié)果。

5、先進(jìn)先出算法模擬函數(shù)：

void FIFO(int[] a, int[] b,int[]m1,int[]m2,int[]m3,char[] s)用于實(shí)現(xiàn)先進(jìn)先出算法模擬，參數(shù)有頁(yè)面數(shù)組，內(nèi)存數(shù)組、內(nèi)存狀態(tài)記錄數(shù)組，缺頁(yè)記錄數(shù)組。在模擬函數(shù)中調(diào)用。

6、最近最久未使用算法模擬函數(shù)：

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

7、最近最久未使用函數(shù)輔助函數(shù)：void LUR_I(int[] a,int e)用于對(duì)最近最久未使用算法中所用輔助數(shù)組（記錄頁(yè)面存在時(shí)長(zhǎng)）進(jìn)行調(diào)整，參數(shù)有輔助數(shù)組及需調(diào)整的數(shù)據(jù)下標(biāo)。在最近最久未使用函數(shù)中調(diào)用。

8、最佳置換算法模擬函數(shù)：

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

9、最佳置換算法輔助函數(shù)：void OPT_F(int[] a, int e)用于對(duì)最佳置換算法中的輔助數(shù)組進(jìn)行調(diào)整。參數(shù)有輔助數(shù)組，需調(diào)整數(shù)據(jù)下標(biāo)。在最佳置換算法中被調(diào)用。

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

2.3主要算法設(shè)計(jì)

1、初始化函數(shù)算法：

第一步：將第一個(gè)頁(yè)面調(diào)入內(nèi)存，調(diào)整最佳置換算法輔助數(shù)組，缺頁(yè)計(jì)數(shù)器加一，保存內(nèi)存數(shù)組狀態(tài)。

第二步：調(diào)用下一個(gè)頁(yè)面并判斷內(nèi)存中是否有本頁(yè)面有轉(zhuǎn)第三步，無(wú)轉(zhuǎn)第四步。第三步：更改缺頁(yè)數(shù)組對(duì)應(yīng)下標(biāo)值，記錄當(dāng)前內(nèi)存狀態(tài)，調(diào)整最佳置換算法輔助數(shù)組，頁(yè)面指針指向下一頁(yè)。

第四步：將頁(yè)面調(diào)入內(nèi)存，調(diào)整最佳置換算法輔助函數(shù)，缺頁(yè)計(jì)數(shù)器加一，保存內(nèi)存數(shù)組狀態(tài)。若內(nèi)存尚不滿(mǎn)轉(zhuǎn)第一步。具體見(jiàn)圖1初始化算法流程圖。

開(kāi)始頁(yè)面調(diào)入內(nèi)存缺頁(yè)計(jì)數(shù)器加一記錄內(nèi)存狀態(tài)調(diào)用下一頁(yè)否否內(nèi)存是否有該頁(yè)面是記錄內(nèi)存狀態(tài)修改缺頁(yè)數(shù)組內(nèi)存已滿(mǎn)是結(jié)束

圖1 初始化算法流程圖

2、先進(jìn)先出頁(yè)面置換算法：

第一步：檢查內(nèi)存中是否已有需調(diào)用頁(yè)面，有則轉(zhuǎn)第二步，無(wú)則轉(zhuǎn)第三步。第二步：記錄當(dāng)前內(nèi)存狀態(tài)，修改缺頁(yè)數(shù)組對(duì)應(yīng)下標(biāo)值。

第三步：內(nèi)存中無(wú)需要調(diào)用的頁(yè)面，進(jìn)行出隊(duì)操作，然后進(jìn)行入隊(duì)操作，記錄內(nèi)存塊狀態(tài)，缺頁(yè)計(jì)數(shù)器加一。

第四步：若頁(yè)面數(shù)組未被調(diào)用結(jié)束轉(zhuǎn)第一步。具體見(jiàn)圖2先進(jìn)先出算法流程圖。

開(kāi)始頁(yè)面調(diào)入內(nèi)存該頁(yè)在內(nèi)存中是否已存在是否否先出隊(duì)操作后入隊(duì)操作記錄內(nèi)存狀態(tài)修改缺頁(yè)數(shù)組值記錄內(nèi)存狀態(tài)缺頁(yè)計(jì)數(shù)器加一頁(yè)面調(diào)用結(jié)束是結(jié)束

圖2 先進(jìn)先出算法流程圖

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

第一步：將頁(yè)面調(diào)入內(nèi)存，記錄內(nèi)存狀態(tài)，缺頁(yè)計(jì)數(shù)器加一，調(diào)整輔助數(shù)組，頁(yè)面指針加一。

第二步：檢查內(nèi)存中是否已有所需頁(yè)面，有轉(zhuǎn)第三步，無(wú)轉(zhuǎn)第一步。

第三步：修改缺頁(yè)數(shù)組對(duì)應(yīng)下標(biāo)記錄，記錄內(nèi)存狀態(tài)，調(diào)整輔助數(shù)組，頁(yè)面指針加一。第四步：內(nèi)存是否已滿(mǎn)，無(wú)則轉(zhuǎn)第一步，是則轉(zhuǎn)第五步。

第五步：檢查內(nèi)存中是否有所需頁(yè)面，有則記錄當(dāng)前內(nèi)存狀態(tài)，修改缺頁(yè)數(shù)組對(duì)應(yīng)下標(biāo)值。無(wú)則轉(zhuǎn)第六步。

第六步：檢查輔助數(shù)組找出最大值并記錄其下標(biāo)，置換內(nèi)存中對(duì)應(yīng)下標(biāo)的數(shù)據(jù)，調(diào)整輔助數(shù)組，缺頁(yè)計(jì)數(shù)器加一。

第七步：頁(yè)面是否調(diào)用結(jié)束未結(jié)束則轉(zhuǎn)第五步。具體見(jiàn)圖3最近最久未使用算法流程圖。

開(kāi)始調(diào)入頁(yè)面至內(nèi)存記錄內(nèi)存狀態(tài)計(jì)數(shù)器加一否調(diào)整輔助數(shù)組調(diào)用下一頁(yè)內(nèi)存中是否已有該頁(yè)否內(nèi)存已滿(mǎn)是通過(guò)輔助數(shù)組確定淘汰頁(yè)面是修改缺頁(yè)數(shù)組記錄內(nèi)存狀態(tài)調(diào)整輔助數(shù)組否頁(yè)面置換記錄內(nèi)存狀態(tài)計(jì)數(shù)器加一調(diào)用結(jié)束是結(jié)束

圖3 最近最久未使用算法

4、最佳置換算法：

第一步：檢查內(nèi)存中是否已有所需頁(yè)面，有則記錄內(nèi)存狀態(tài)，修改缺頁(yè)數(shù)組對(duì)應(yīng)下標(biāo)數(shù)值。無(wú)則轉(zhuǎn)第二步。

第二步：判斷內(nèi)存中各頁(yè)面的未來(lái)調(diào)用情況，記錄是否還有調(diào)用，若有則記錄調(diào)用時(shí)刻。

第三步：分析調(diào)用情況，內(nèi)存中頁(yè)面都在將來(lái)不會(huì)被調(diào)用轉(zhuǎn)第四步，有一個(gè)被調(diào)用轉(zhuǎn)第五步，有兩個(gè)被調(diào)用轉(zhuǎn)第六步，全被調(diào)用轉(zhuǎn)第七步。

第四步:查找輔助數(shù)組找到內(nèi)存中存在時(shí)間最長(zhǎng)的頁(yè)面進(jìn)行置換，修改內(nèi)存狀態(tài)，缺頁(yè)計(jì)數(shù)器加一，修改輔助數(shù)組。

第五步：查找到不會(huì)被調(diào)用的頁(yè)面，并根據(jù)輔助數(shù)組選擇最早進(jìn)入內(nèi)存的頁(yè)面將其置換。修改內(nèi)存狀態(tài)，缺頁(yè)計(jì)數(shù)器加一，修改輔助數(shù)組。

第六步：查找輔助數(shù)組找到將來(lái)不需要在調(diào)用的頁(yè)面將其置換，修改輔助數(shù)組，記錄內(nèi)存狀態(tài)，缺頁(yè)計(jì)數(shù)器加一。

第七步：查找輔助數(shù)組，找尋最晚被調(diào)用的頁(yè)面，將其置換。記錄內(nèi)存狀態(tài)，修改輔助數(shù)組，缺頁(yè)計(jì)數(shù)器加一。

第八步：頁(yè)面是否調(diào)用完成，否則轉(zhuǎn)第一步。具體見(jiàn)圖4最佳置換算法流程圖

開(kāi)始調(diào)入頁(yè)面記錄內(nèi)存狀態(tài)計(jì)數(shù)器加一更新輔助函數(shù)是頁(yè)面已存在否向后檢查內(nèi)存當(dāng)前頁(yè)面調(diào)用情況所有頁(yè)面都不會(huì)再度調(diào)用否是一個(gè)頁(yè)面會(huì)調(diào)用否否是兩個(gè)頁(yè)面會(huì)調(diào)用是否查找輔助數(shù)組得到最先進(jìn)入頁(yè)面通過(guò)輔助數(shù)組得到不會(huì)再調(diào)用的頁(yè)面通過(guò)輔助數(shù)組獲取最晚調(diào)用的頁(yè)面通過(guò)輔助數(shù)組得到另外兩個(gè)頁(yè)面中最先進(jìn)入的頁(yè)面置換頁(yè)面記錄內(nèi)存狀態(tài)計(jì)數(shù)器加一更新輔助函數(shù)頁(yè)面調(diào)用結(jié)束是結(jié)束

圖4 最佳置換算法流程圖 2.4界面設(shè)計(jì)

采用c# 設(shè)計(jì)windows窗體應(yīng)用程序，使用下拉列表框選擇算法，通過(guò)按鈕添加待調(diào)用的頁(yè)面。通過(guò)文本控件顯示模擬結(jié)果。顯示樣式：第一行：算法名稱(chēng)；

第二行：調(diào)用頁(yè)面順序；

第三行至第五行顯示內(nèi)存在每調(diào)用一次頁(yè)面后的狀態(tài)；

第六行：是否缺頁(yè)；

最后一行顯示缺頁(yè)率；

第3章 詳細(xì)設(shè)計(jì)與實(shí)現(xiàn)

3.1函數(shù)設(shè)計(jì)

1、添加按鈕功能實(shí)現(xiàn)代碼

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

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

2、初始化函數(shù)

主要功能：將內(nèi)存一先進(jìn)先出方式填滿(mǎn)，并記錄每個(gè)頁(yè)面進(jìn)入時(shí)間，服務(wù)于先進(jìn)先出頁(yè)面置換算法和最佳置換算法。

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

//調(diào)整輔助數(shù)組將剛進(jìn)入內(nèi)存的頁(yè)面的對(duì)應(yīng)時(shí)間 OPT_F(O_Q ,i)； count++;//缺頁(yè)計(jì)數(shù)器加一 m1[page_p] = b[0];//保存內(nèi)存狀態(tài) m2[page_p] = b[1];m3[page_p] = b[2];page_p++;//調(diào)用下一頁(yè)面

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

s[page_p] = 'F';//缺頁(yè)數(shù)組對(duì)應(yīng)數(shù)據(jù)更改 m1[page_p] = b[0];//記錄內(nèi)存狀態(tài) m2[page_p] = b[1];m3[page_p] = b[2];OPT_F(O_Q,-1);//調(diào)整最佳置換算法輔助函數(shù) page_p++;//調(diào)用下一頁(yè) j =-1;//重新開(kāi)始尋找 } } } }

3、先進(jìn)先出頁(yè)面置換函數(shù)

主要功能：根據(jù)先進(jìn)先出算法要求在產(chǎn)生缺頁(yè)中斷時(shí)采用先進(jìn)先出方式確定淘汰頁(yè)面，并在每次頁(yè)面調(diào)用時(shí)記錄下內(nèi)存狀態(tài)，缺頁(yè)次數(shù)；采用循環(huán)隊(duì)列使得每次出隊(duì)的一定是最先進(jìn)入內(nèi)存的。

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

{ 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;} } /*最近最久未使用算法輔助數(shù)組調(diào)整函數(shù)*/ 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]++;} } /*最佳置換算法輔助數(shù)組調(diào)整函數(shù)*/ 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];//調(diào)入內(nèi)存 count++;m1[page_p] = b[0];//保存內(nèi)存狀態(tài) 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++)//用的頁(yè)面。{ 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){

檢查內(nèi)存中是否已有要調(diào)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;//刷新?tīng)顟B(tài)數(shù)組 OPT_J[i] = MaxN;} sa = 0;for(int i = 0;i < MaxM;i++)//檢查內(nèi)存中是否已有要調(diào)用的頁(yè)面。

{

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)//缺頁(yè) { 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://全部頁(yè)面以后都不會(huì)再度調(diào)用 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://有一個(gè)頁(yè)面將在以后調(diào)用 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;} } } } /*重置函數(shù)*/ 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';} } }

第三篇：操作系統(tǒng)課程設(shè)計(jì)報(bào)告

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 學(xué) 號(hào)： 姓 名: 提交日期：

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

【設(shè)計(jì)目的】

（1）本實(shí)驗(yàn)的目的是通過(guò)一個(gè)簡(jiǎn)單多用戶(hù)文件系統(tǒng)的設(shè)計(jì)，加深理解文件系統(tǒng)的內(nèi)部功能和內(nèi)部實(shí)現(xiàn)。

（2）結(jié)合數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)、計(jì)算機(jī)原理等課程的知識(shí)，設(shè)計(jì)一個(gè)二級(jí)文件系統(tǒng)，進(jìn)一步理解操作系統(tǒng)。

（3）通過(guò)分對(duì)實(shí)際問(wèn)題的分析、設(shè)計(jì)、編程實(shí)現(xiàn)，提高學(xué)生實(shí)際應(yīng)用、編程的能力 【設(shè)計(jì)內(nèi)容】

為L(zhǎng)inux系統(tǒng)設(shè)計(jì)一個(gè)簡(jiǎn)單的二級(jí)文件系統(tǒng)。要求做到以下幾點(diǎn)： 1.可以實(shí)現(xiàn)下列幾條命令：

login 用戶(hù)登錄

dir 列目錄

create 創(chuàng)建文件

delete 刪除文件

open 打開(kāi)文件

close 關(guān)閉文件

read 讀文件

write 寫(xiě)文件

cd 進(jìn)出目錄

2．列目錄時(shí)要列出文件名，物理地址，保護(hù)碼和文件長(zhǎng)度 3．源文件可以進(jìn)行讀寫(xiě)保護(hù) 【實(shí)驗(yàn)環(huán)境】 Windows xp/7 C++/VC++

【相關(guān)知識(shí)綜述】

1、文件系統(tǒng)

文件系統(tǒng)是操作系統(tǒng)用于明確存儲(chǔ)設(shè)備（常見(jiàn)的是磁盤(pán)，也有基于NAND Flash的固態(tài)硬盤(pán)）或分區(qū)上的文件的方法和數(shù)據(jù)結(jié)構(gòu)；即在存儲(chǔ)設(shè)備上組織文件的方法。操作系統(tǒng)中負(fù)責(zé)管理和存儲(chǔ)文件信息的軟件機(jī)構(gòu)稱(chēng)為文件管理系統(tǒng)，簡(jiǎn)稱(chēng)文件系統(tǒng)。文件系統(tǒng)由三部分組成：文件系統(tǒng)的接口，對(duì)對(duì)象操縱和管理的軟件集合，對(duì)象及屬性。從系統(tǒng)角度來(lái)看，文件系統(tǒng)是對(duì)文件存儲(chǔ)設(shè)備的空間進(jìn)行組織和分配，負(fù)責(zé)文件存儲(chǔ)并對(duì)存入的文件進(jìn)行保護(hù)和檢索的系統(tǒng)。具體地說(shuō)，它負(fù)責(zé)為用戶(hù)建立文件，存入、讀出、修改、轉(zhuǎn)儲(chǔ)文件，控制文件的存取，當(dāng)用戶(hù)不再使用時(shí)撤銷(xiāo)文件等。

2、位示圖

位示圖是利用二進(jìn)制的一位來(lái)表示磁盤(pán)中的一個(gè)盤(pán)塊的使用情況。當(dāng)其值為“0”時(shí)，表示對(duì)應(yīng)的盤(pán)塊空閑；為“1”時(shí)，表示已經(jīng)分配。有的系統(tǒng)把“0”作為盤(pán)塊已分配的標(biāo)記，把“1”作為空閑標(biāo)志。(它們的本質(zhì)上是相同的，都是用一位的兩種狀態(tài)標(biāo)志空閑和已分配兩種情況。)磁盤(pán)上的所有盤(pán)塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，這樣，由所有盤(pán)塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱(chēng)為位示圖。

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

【設(shè)計(jì)思路】

本文件系統(tǒng)采用兩級(jí)目錄，其中第一級(jí)對(duì)應(yīng)于用戶(hù)賬號(hào)，第二級(jí)對(duì)應(yīng)于用戶(hù)帳號(hào)下的文件。另外，為了簡(jiǎn)便文件系統(tǒng)未考慮文件共享，文件系統(tǒng)安全以及管道文件與設(shè)備文件等特殊內(nèi)容。

首先應(yīng)確定文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)：主目錄、子目錄及活動(dòng)文件等。主目錄和子目錄都以文件的形式存放于磁盤(pán)，這樣便于查找和修改。

用戶(hù)創(chuàng)建的文件，可以編號(hào)存儲(chǔ)于磁盤(pán)上。如：file0,file1,file2?并以編號(hào)作為物理地址，在目錄中進(jìn)行登記。

【程序主要流程圖】

否

驗(yàn)證是否成

功？

是

目錄

右鍵進(jìn)行選擇 操作

新建目錄新建文件打開(kāi)文件

結(jié)束

開(kāi)始登錄刪除屬性 2

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

【源程序清單】

typedef struct

//文件結(jié)構(gòu)體 /*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

//用戶(hù)文件目錄結(jié)構(gòu)體 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

//文件打開(kāi)模式 /*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);//獲取用戶(hù)的序號(hào)

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

for(i=0;i

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

{

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

}

}

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);//獲得需要打開(kāi)的文件名fname

for(i=0;i

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

{

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

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

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

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

printf(“Open file successfully!n”);

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

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

if(remove(str)==0)

//調(diào)用remove函數(shù)刪除 第k個(gè)用戶(hù)的第i個(gè)文件ufd[k]->ufdfile[i]

{

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

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

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

fcount[k] = fcount[k]-1;//文件數(shù)-1

printf(“Delete file successfully!n”);

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

} else

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

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

}

} }

void CloseF()/*Close File*/ {

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

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

for(i=0;i

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

{

ifopen[k][i].ifopen=0;//關(guān)閉文件

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(”O(jiān)pened File(s)List:n“);k=ExistD(dirname);

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

for(i=0;i

//文件屬性為只寫(xiě)或者是讀寫(xiě)才能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(”P(pán)lease input text('#' stands for end):n“);

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

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

{

fputc(c,fp_file);

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

}

//fprintf(fp_file,”n“);

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

fclose(fp_file);

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

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;

} } }

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

【測(cè)試結(jié)果】

1、創(chuàng)建用戶(hù)

2、創(chuàng)建文件，并且打開(kāi)讀取文件

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

3、寫(xiě)文件

4、刪除文件

操作系統(tǒng)課程設(shè)計(jì)報(bào)告

【設(shè)計(jì)總結(jié)】

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

代碼編寫(xiě)完了之后，實(shí)現(xiàn)了題目所要求的基本功能，但是在測(cè)試的過(guò)程中，還發(fā)現(xiàn)了這個(gè)程序存在各種各樣的bug。不斷的測(cè)試修改后，得到完善。

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

在這次課設(shè)中，我還意識(shí)到，要把這門(mén)課真真正正地學(xué)好，不單單只是為了能夠應(yīng)付考試，平時(shí)還要多加學(xué)習(xí)，多加努力才對(duì)。

【參考文獻(xiàn)】

【1】C語(yǔ)言程序設(shè)計(jì)（第三版）譚浩強(qiáng)

【2】計(jì)算機(jī)操作系統(tǒng)教程(第三版).張堯?qū)W 史美林 張高

【3】計(jì)算機(jī)操作系統(tǒng),西安電子科技大學(xué)出版社，方敏主編,2004.8

第四篇：操作系統(tǒng)課程設(shè)計(jì)

操作系統(tǒng)課程設(shè)計(jì)

注意事項(xiàng)：

0.請(qǐng)每位同學(xué)必須按時(shí)提交課程設(shè)計(jì)報(bào)告（包括電子版和紙質(zhì)版），算入期末成績(jī)

1.在三個(gè)題目中選擇一個(gè)

2.如果選擇題目

（一）進(jìn)程調(diào)度算法，要求實(shí)現(xiàn)其中2個(gè)以上（包括2個(gè)）進(jìn)程調(diào)度算法 3.如果選擇題目

（二）銀行家算法，要求能夠判斷系統(tǒng)的安全狀態(tài)

4.如果選擇題目

（三）頁(yè)面調(diào)度算法，要求實(shí)現(xiàn)其中2個(gè)以上（包含2個(gè)）進(jìn)程調(diào)度算法 5.報(bào)告應(yīng)包含算法分析、實(shí)驗(yàn)截圖、核心算法源代碼，請(qǐng)各位同學(xué)認(rèn)真對(duì)待，獨(dú)立完成 6.提交要求：電子版（包括實(shí)驗(yàn)程序）請(qǐng)發(fā)至ropeal@163.com，紙質(zhì)版請(qǐng)班長(zhǎng)收齊，由班長(zhǎng)統(tǒng)一在課堂上提交（并提交未交人員名單），截止時(shí)間第16周周三(2014.1.31)7.格式要求：

7.1 A4紙10頁(yè)左右

7.2 封面請(qǐng)注明班級(jí)、姓名、學(xué)號(hào)、所選題目

7.3 電子版發(fā)送時(shí)，請(qǐng)打包成一個(gè)文件，將文件名設(shè)置為：學(xué)號(hào)+姓名+題目名稱(chēng)（如20130000張三進(jìn)程調(diào)度算法課程設(shè)計(jì)），郵件主題同文件名

一、進(jìn)程調(diào)度算法

1.1 實(shí)驗(yàn)?zāi)康模? a、設(shè)計(jì)進(jìn)程控制塊PCB表結(jié)構(gòu)，模擬實(shí)現(xiàn)進(jìn)程調(diào)度算法：FIFO，靜態(tài)優(yōu)先級(jí)調(diào)度，時(shí)間片輪轉(zhuǎn)調(diào)度，多級(jí)反饋隊(duì)列調(diào)度。（實(shí)現(xiàn)其中之二）。* b、建立進(jìn)程就緒隊(duì)列。對(duì)不同算法編制入鏈子程序。c、編寫(xiě)一進(jìn)程調(diào)度程序模擬程序。模擬程序只對(duì)PCB進(jìn)行相應(yīng)的調(diào)度模擬操作，不需要實(shí)際程序。* 由用戶(hù)輸入進(jìn)程名和進(jìn)程長(zhǎng)度，然后按照短進(jìn)程優(yōu)先的進(jìn)程處理順序給出進(jìn)程的排序。

1.2 實(shí)驗(yàn)原理 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。1.2.1 先來(lái)先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

1.先來(lái)先服務(wù)調(diào)度算法。先來(lái)先服務(wù)（FCFS）調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。FCFS算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。由此可知，本算法適合于CPU繁忙型作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）。

2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法。短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（SJ/PF）是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。但其對(duì)長(zhǎng)作業(yè)不利；不能保證緊迫性作業(yè)（進(jìn)程）被及時(shí)處理；作業(yè)的長(zhǎng)短只是被估算出來(lái)的。1.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法

1.優(yōu)先權(quán)調(diào)度算法的類(lèi)型。為了照顧緊迫性作業(yè)，使之進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算法。此算法常被用在批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度，還可以用于實(shí)時(shí)系統(tǒng)中。當(dāng)其用于作業(yè)調(diào)度，將后備隊(duì)列中若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)其用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，此時(shí)，又可以進(jìn)一步把該算法分成以下兩種： 1)非搶占式優(yōu)先權(quán)算法

2)搶占式優(yōu)先權(quán)調(diào)度算法（高性能計(jì)算機(jī)操作系統(tǒng)）

2.優(yōu)先權(quán)類(lèi)型。對(duì)于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其核心在于：它是使用靜態(tài)優(yōu)先權(quán)還是動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。3．高響應(yīng)比優(yōu)先調(diào)度算法

為了彌補(bǔ)短作業(yè)優(yōu)先算法的不足，我們引入動(dòng)態(tài)優(yōu)先權(quán)，使作業(yè)的優(yōu)先等級(jí)隨著等待時(shí)間的增加而以速率a提高。該優(yōu)先權(quán)變化規(guī)律可描述為：優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間；即 =（響應(yīng)時(shí)間）/要求服務(wù)時(shí)間 1.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

1.時(shí)間片輪轉(zhuǎn)法。時(shí)間片輪轉(zhuǎn)法一般用于進(jìn)程調(diào)度，每次調(diào)度，把CPU分配隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)記時(shí)器發(fā)出一個(gè)時(shí)鐘中斷請(qǐng)求，該進(jìn)程被停止，并被送往就緒隊(duì)列末尾；依次循環(huán)。2.多級(jí)反饋隊(duì)列調(diào)度算法 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法，不必事先知道各種進(jìn)程所需要執(zhí)行的時(shí)間，它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。其實(shí)施過(guò)程如下：

1)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。在優(yōu)先權(quán)越高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就越小。

2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等候調(diào)度。如果他能在一個(gè)時(shí)間片中完成，便可撤離；如果未完成，就轉(zhuǎn)入第二隊(duì)列的末尾，在同樣等待調(diào)度?? 如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)（進(jìn)程）從第一隊(duì)列依次將到第n隊(duì)列（最后隊(duì)列）后，便按第n隊(duì)列時(shí)間片輪轉(zhuǎn)運(yùn)行。3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?到第（i-1）隊(duì)列空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行，并執(zhí)行相應(yīng)的時(shí)間片輪轉(zhuǎn)。4)如果處理機(jī)正在處理第i隊(duì)列中某進(jìn)程，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則此新隊(duì)列搶占正在運(yùn)行的處理機(jī)，并把正在運(yùn)行的進(jìn)程放在第i隊(duì)列的隊(duì)尾。

1．3 實(shí)驗(yàn)要求

a、使用模塊化設(shè)計(jì)思想來(lái)設(shè)計(jì)； b、給出算法的流程圖或偽碼說(shuō)明。c、學(xué)生可按照自身?xiàng)l件，隨意選擇采用的算法，（例如：采用冒泡法編寫(xiě)程序，實(shí)現(xiàn)短進(jìn)程優(yōu)先調(diào)度的算法）

d、進(jìn)程調(diào)度程序模擬程序只對(duì)PCB進(jìn)行相應(yīng)的調(diào)度模擬操作，不需要實(shí)際程序。

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

（即：每執(zhí)行一次進(jìn)程，該進(jìn)程的執(zhí)行時(shí)間片數(shù)為已執(zhí)行了2個(gè)單位），這時(shí)，CPU時(shí)間片（CPUtime）數(shù)加2，* 進(jìn)程還需要的時(shí)間片數(shù)（needtime）減2，并排列到就緒隊(duì)列的尾上。

d、對(duì)于遇到優(yōu)先數(shù)一致的情況，采用FIFO策略解決。

二、銀行家算法

2.1 概述

2.1.1 設(shè)計(jì)目的1、了解多道程序系統(tǒng)中，多個(gè)進(jìn)程并發(fā)執(zhí)行的資源分配。

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

3、掌握預(yù)防死鎖的方法，系統(tǒng)安全狀態(tài)的基本概念。

4、掌握銀行家算法，了解資源在進(jìn)程并發(fā)執(zhí)行中的資源分配策略。

5、理解死鎖避免在當(dāng)前計(jì)算機(jī)系統(tǒng)不常使用的原因

2.2 關(guān)于死鎖

2.2.1 死鎖概念：

在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來(lái)改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)━━死鎖。所謂死鎖(Deadlock),是指多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局(Deadly_Embrace),當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)。一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱(chēng)為進(jìn)程死鎖，這一組進(jìn)程就稱(chēng)為死鎖進(jìn)程。

2.2.2 關(guān)于死鎖的一些結(jié)論：

參與死鎖的進(jìn)程最少是兩個(gè)（兩個(gè)以上進(jìn)程才會(huì)出現(xiàn)死鎖）

參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源

參與死鎖的所有進(jìn)程都在等待資源

參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集

注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。

2.2.3 資源分類(lèi)：

永久性資源： 可以被多個(gè)進(jìn)程多次使用（可再用資源），分為：可搶占資源與不可搶占資源

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

“申請(qǐng)--分配--使用--釋放”模式

2.2.4 產(chǎn)生死鎖的四個(gè)必要條件：

1、互斥使用（資源獨(dú)占）

一個(gè)資源每次只能給一個(gè)進(jìn)程使用

2、不可強(qiáng)占（不可剝奪）

資源申請(qǐng)者不能強(qiáng)行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放

3、請(qǐng)求和保持（部分分配，占有申請(qǐng)）

一個(gè)進(jìn)程在申請(qǐng)新的資源的同時(shí)保持對(duì)原有資源的占有（只有這樣才是動(dòng)態(tài)申請(qǐng)，動(dòng)態(tài)分配）

4、循環(huán)等待

存在一個(gè)進(jìn)程等待隊(duì)列

{P1 , P2 , ? , Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，?，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路

2.2.5 死鎖的解決方案 1 產(chǎn)生死鎖的例子

申請(qǐng)不同類(lèi)型資源產(chǎn)生死鎖

P1： ?

申請(qǐng)打印機(jī) 申請(qǐng)掃描儀 使用

釋放打印機(jī) 釋放掃描儀 ? P2： ?

申請(qǐng)掃描儀 申請(qǐng)打印機(jī) 使用

釋放打印機(jī) 釋放掃描儀 ?

申請(qǐng)同類(lèi)資源產(chǎn)生死鎖（如內(nèi)存）

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

m=2，n=3 資源分配不當(dāng)導(dǎo)致死鎖產(chǎn)生

2死鎖預(yù)防: 定義:在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一

①破壞“不可剝奪”條件

在允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源前提下規(guī)定，一個(gè)進(jìn)程在申請(qǐng)新的資源不能立即得到滿(mǎn)足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請(qǐng) ②破壞“請(qǐng)求和保持”條件

要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請(qǐng)它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿(mǎn)足時(shí)才給予一次性分配 ③破壞“循環(huán)等待”條件 采用資源有序分配法：

把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請(qǐng)資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配。

2.2.6 安全狀態(tài)與不安全狀態(tài)

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

不安全狀態(tài):不存在一個(gè)安全序列，不安全狀態(tài)一定導(dǎo)致死鎖。

2.3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

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

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

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

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

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

2.4 算法的實(shí)現(xiàn) 2.4.1 初始化 由用戶(hù)輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。2.4.2 銀行家算法

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

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

設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。

(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。

2.4.3 安全性檢查算法

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

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

三、頁(yè)面調(diào)度算法 3.1 實(shí)驗(yàn)名稱(chēng)

頁(yè)式虛擬存儲(chǔ)管理：頁(yè)面調(diào)度算法 3.2 實(shí)驗(yàn)?zāi)康?/p>

頁(yè)式虛擬存儲(chǔ)器實(shí)現(xiàn)的一個(gè)難點(diǎn)是設(shè)計(jì)頁(yè)面調(diào)度（置換）算法，即將新頁(yè)面調(diào)入內(nèi)存時(shí)，如果內(nèi)存中所有的物理頁(yè)都已經(jīng)分配出去，就要按某種策略來(lái)廢棄某個(gè)頁(yè)面，將其所占據(jù)的物理頁(yè)釋放出來(lái)，供新頁(yè)面使用。本實(shí)驗(yàn)的目的是通過(guò)編程實(shí)現(xiàn)幾種常見(jiàn)的頁(yè)面調(diào)度（置換）算法，加深讀者對(duì)頁(yè)面思想的理解。3.3 實(shí)驗(yàn)原理

頁(yè)面調(diào)度算法

目前有許多頁(yè)面調(diào)度算法，本實(shí)驗(yàn)主要涉及先進(jìn)先出調(diào)度算法、最近最少調(diào)度算法、最近最不常用調(diào)度算法。本實(shí)驗(yàn)使用頁(yè)面調(diào)度算法時(shí)作如下假設(shè)，進(jìn)程在創(chuàng)建時(shí)由操作系統(tǒng)為之分配一個(gè)固定數(shù)目物理頁(yè)，執(zhí)行過(guò)程中物理頁(yè)的數(shù)目和位置不會(huì)改變。也即進(jìn)程進(jìn)行頁(yè)面調(diào)度時(shí)只能在分到的幾個(gè)物理頁(yè)中進(jìn)行。

下面對(duì)各調(diào)度算法的思想作一介紹。

<1> 先進(jìn)先出調(diào)度算法

先進(jìn)先出調(diào)度算法根據(jù)頁(yè)面進(jìn)入內(nèi)存的時(shí)間先后選擇淘汰頁(yè)面，先進(jìn)入內(nèi)存的頁(yè)面先淘汰，后進(jìn)入內(nèi)存的后淘汰。本算法實(shí)現(xiàn)時(shí)需要將頁(yè)面按進(jìn)入內(nèi)存的時(shí)間先后組成一個(gè)隊(duì)列，每次調(diào)度隊(duì)首頁(yè)面予以淘汰。

<2>最近最少調(diào)度算法

先進(jìn)先出調(diào)度算法沒(méi)有考慮頁(yè)面的使用情況，大多數(shù)情況下性能不佳。根據(jù)程序執(zhí)行的局部性特點(diǎn)，程序一旦訪(fǎng)問(wèn)了某些代碼和數(shù)據(jù)，則在一段時(shí)間內(nèi)會(huì)經(jīng)常訪(fǎng)問(wèn)他們，因此最近最少用調(diào)度在選擇淘汰頁(yè)面時(shí)會(huì)考慮頁(yè)面最近的使用，總是選擇在最近一段時(shí)間以來(lái)最少使用的頁(yè)面予以淘汰。算法實(shí)現(xiàn)時(shí)需要為每個(gè)頁(yè)面設(shè)置數(shù)據(jù)結(jié)構(gòu)記錄頁(yè)面自上次訪(fǎng)問(wèn)以來(lái)所經(jīng)歷的時(shí)間。

<3>最近最不常用調(diào)度算法

由于程序設(shè)計(jì)中經(jīng)常使用循環(huán)結(jié)構(gòu)，根據(jù)程序執(zhí)行的局部性特點(diǎn)，可以設(shè)想在一段時(shí)間內(nèi)經(jīng)常被訪(fǎng)問(wèn)的代碼和數(shù)據(jù)在將來(lái)也會(huì)經(jīng)常被訪(fǎng)問(wèn)，顯然這樣的頁(yè)面不應(yīng)該被淘汰。最近最不常用調(diào)度算法總是根據(jù)一段時(shí)間內(nèi)頁(yè)面的訪(fǎng)問(wèn)次數(shù)來(lái)選擇淘汰頁(yè)面，每次淘汰訪(fǎng)問(wèn)次數(shù)最少的頁(yè)面。算法實(shí)現(xiàn)時(shí)需要為每個(gè)頁(yè)面設(shè)置計(jì)數(shù)器，記錄訪(fǎng)問(wèn)次數(shù)。計(jì)數(shù)器由硬件或操作系統(tǒng)自動(dòng)定時(shí)清零。

缺頁(yè)調(diào)度次數(shù)和缺頁(yè)中斷率、缺頁(yè)置換率計(jì)算

缺頁(yè)中斷次數(shù)是缺頁(yè)時(shí)發(fā)出缺頁(yè)中斷的次數(shù)。

缺頁(yè)中斷率=缺頁(yè)中斷次數(shù)/總的頁(yè)面引用次數(shù)*100%

缺頁(yè)調(diào)度次數(shù)是調(diào)入新頁(yè)時(shí)需要進(jìn)行頁(yè)面調(diào)度的次數(shù)

缺頁(yè)置換率=缺頁(yè)調(diào)度次數(shù)/總的頁(yè)面引用次數(shù)*100% 3.4 實(shí)驗(yàn)內(nèi)容

（1）設(shè)計(jì)程序?qū)崿F(xiàn)以上三種頁(yè)面調(diào)度算法，要求：

①.可以選擇頁(yè)面調(diào)度算法類(lèi)型；

②.可以為進(jìn)程設(shè)置分到物理頁(yè)的數(shù)目，設(shè)置進(jìn)程的頁(yè)面引用情況，可以從鍵盤(pán)輸入頁(yè)面序列，也可從文件中讀取；

③.隨時(shí)計(jì)算當(dāng)前的頁(yè)面調(diào)度次數(shù)的缺頁(yè)中斷率；

④.使用敲鍵盤(pán)或響應(yīng)WM-TIMER的形式模仿時(shí)間的流逝；

⑤.以直觀(guān)的的形式將程序的執(zhí)行情況顯示在計(jì)算機(jī)屏幕上；

⑥.存盤(pán)及讀盤(pán)功能，可以隨時(shí)將數(shù)據(jù)存入磁盤(pán)文件，供以后重復(fù)實(shí)驗(yàn)時(shí)使用。

（2）假定進(jìn)程分配到3個(gè)物理塊，對(duì)于下面的頁(yè)面引用序列：（test.txt）

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

請(qǐng)分別用先進(jìn)和先出調(diào)度算法，最近最少用調(diào)度算法，最近最不常用調(diào)度算法計(jì)算缺頁(yè)中斷次數(shù)，缺頁(yè)中斷率和缺頁(yè)調(diào)度次數(shù)、缺頁(yè)置換率。

再假定進(jìn)程分配到4、5個(gè)物理塊，重復(fù)本實(shí)驗(yàn)。

（3）假定進(jìn)程分配到3個(gè)物理塊，對(duì)于下面的頁(yè)面引用序列：（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

請(qǐng)分別用先進(jìn)先出調(diào)度算法、最近最少用調(diào)度算法，最近最不常用調(diào)度算法計(jì)算缺頁(yè)中斷次數(shù)，缺頁(yè)中斷率和缺頁(yè)調(diào)度次數(shù)、缺頁(yè)置換率。

再假定進(jìn)程分配到4、5個(gè)物理塊，重復(fù)本實(shí)驗(yàn)。

（4）假定進(jìn)程分配到3個(gè)物理塊，使用程序的動(dòng)態(tài)頁(yè)面序列生成算法，生成一個(gè)頁(yè)面序列，將此序列存入磁盤(pán)文件。再?gòu)拇疟P(pán)文件讀入該序列，用程序分別計(jì)算三種算法下的缺頁(yè)中斷次數(shù)、缺頁(yè)中斷率和缺頁(yè)調(diào)度次數(shù)、缺頁(yè)置換率。

第五篇：操作系統(tǒng)課程設(shè)計(jì)

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

（操作系統(tǒng)課程設(shè)計(jì)）

連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存

管理模擬實(shí)現(xiàn)

學(xué)生姓名： 韓 慧 學(xué)生學(xué)號(hào)： 031140312 班 級(jí)： 031140--3 0311401、02、03、04班制

二〇一三年十二月 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

目錄

《操作系統(tǒng)》課程設(shè)計(jì).......................................................1 引言......................................................................3 課程設(shè)計(jì)目的和內(nèi)容......................................................3 需求分析.........................................................................3 概要設(shè)計(jì)...................................................................3 開(kāi)發(fā)環(huán)境........................................................................4 系統(tǒng)分析設(shè)計(jì).....................................................................4 有關(guān)了解內(nèi)存管理的相關(guān)理論..................................................4 內(nèi)存管理概念........................................................................4 內(nèi)存管理的必要性..............................................................4 內(nèi)存的物理組織.............................................................4 什么是虛擬內(nèi)存.................................................................5 連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式...................................................5 單一連續(xù)分配（單個(gè)分區(qū))...................................................5

固定分區(qū)存儲(chǔ)管理...............................................................5 可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）..............................................5 可重定位分區(qū)存儲(chǔ)管理........................................................5 問(wèn)題描述和分析....................................................................6 程序流程圖........................................................................6 數(shù)據(jù)結(jié)構(gòu)體分析..................................................................8 主要程序代碼分析...............................................................9 分析并實(shí)現(xiàn)四種內(nèi)存分配算法.................................................11 最先適應(yīng)算.....................................................................11 下次適應(yīng)分配算法..........................................................13 最優(yōu)適應(yīng)算法...............................................................16 最壞適應(yīng)算法...............................................................18 回收內(nèi)存算法................................................................20 調(diào)試與操作說(shuō)明.................................................................22

初始界面.......................................................................22 模擬內(nèi)存分配...............................................................23

已分配分區(qū)說(shuō)明表面............................................................24 空閑區(qū)說(shuō)明表界面.............................................................24 回收內(nèi)存界面.....................................................................25 重新申請(qǐng)內(nèi)存界面..........................................................26.總結(jié)與體會(huì)......................................................................28 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

參考文獻(xiàn).........................................................................28

引言

操作系統(tǒng)是最重要的系統(tǒng)軟件，同時(shí)也是最活躍的學(xué)科之一。我們通過(guò)操作系統(tǒng)可以理解計(jì)算機(jī)系統(tǒng)的資源如何組織，操作系統(tǒng)如何有效地管理這些系統(tǒng)資源，用戶(hù)如何通過(guò)操作系統(tǒng)與計(jì)算機(jī)系統(tǒng)打交道。

存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，近年來(lái)，存儲(chǔ)器容量雖然一直在不斷擴(kuò)大，但仍不能滿(mǎn)足現(xiàn)代軟件發(fā)展的需要，因此，存儲(chǔ)器仍然是一種寶貴而又緊俏的資源。如何對(duì)它加以有效的管理，不僅直接影響到存儲(chǔ)器的利用率，而且還對(duì)系統(tǒng)性能有重大影響。而動(dòng)態(tài)分區(qū)分配屬于連續(xù)分配的一種方式，它至今仍在內(nèi)存分配方式中占有一席之地。

課程設(shè)計(jì)目的和內(nèi)容：

理解內(nèi)存管理的相關(guān)理論，掌握連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理的理論；通過(guò)對(duì)實(shí)際問(wèn)題的編程實(shí)現(xiàn)，獲得實(shí)際應(yīng)用和編程能力。

編寫(xiě)程序?qū)崿F(xiàn)連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式，該程序管理一塊虛擬內(nèi)存，實(shí)現(xiàn)內(nèi)存分配和回收功能。分析并實(shí)現(xiàn)四種內(nèi)存分配算法，即最先適應(yīng)算法，下次最先適應(yīng)算法，最優(yōu)適應(yīng)算法，最壞適應(yīng)算法。內(nèi)存分配算法和回收算法的實(shí)現(xiàn)。

需求分析

動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配時(shí)，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配和回收操作這樣三個(gè)問(wèn)題。常用的數(shù)據(jù)結(jié)構(gòu)有動(dòng)態(tài)分區(qū)表和動(dòng)態(tài)分區(qū)鏈。在對(duì)數(shù)據(jù)結(jié)構(gòu)有一定掌握程度的情況下設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)來(lái)描述存儲(chǔ)空間，實(shí)現(xiàn)分區(qū)存儲(chǔ)管理的內(nèi)存分配功能，應(yīng)該選擇最合適的適應(yīng)算法（首次適應(yīng)算法，最佳適應(yīng)算法，最后適應(yīng)算法，最壞適應(yīng)算法），在動(dòng)態(tài)分區(qū)存儲(chǔ)管理方式中主要實(shí)現(xiàn)內(nèi)存分配和內(nèi)存回收算法，在這些存儲(chǔ)管理中間必然會(huì)有碎片的產(chǎn)生，當(dāng)碎片產(chǎn)生時(shí)，進(jìn)行碎片的拼接等相關(guān)的內(nèi)容

概要設(shè)計(jì)

本程序采用機(jī)構(gòu)化模塊化的設(shè)計(jì)方法，共分為四大模塊。⑴最先適應(yīng)算法實(shí)現(xiàn)

從空閑分區(qū)表的第一個(gè)表目起查找該表，把最先能夠滿(mǎn)足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。該算法優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。⑵下次適應(yīng)分配算法實(shí)現(xiàn) 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

該算法是最先適應(yīng)算法的變種。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_(kāi)始查找，而是從上次找到空閑區(qū)的下一個(gè)空閑開(kāi)始查找，直到找到第一個(gè)能滿(mǎn)足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得較均勻。⑶最優(yōu)適應(yīng)算法實(shí)現(xiàn)

它從全部空閑區(qū)中找出能滿(mǎn)足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為適應(yīng)此算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按從小到大進(jìn)行排序，自表頭開(kāi)始查找到第一個(gè)滿(mǎn)足要求的自由分區(qū)分配。⑷最壞算法實(shí)現(xiàn)

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

開(kāi)發(fā)環(huán)境：

win7 下 VC++6.0 系統(tǒng)分析設(shè)計(jì)：

相關(guān)算法原理，算法流程圖，涉及的數(shù)據(jù)結(jié)構(gòu)內(nèi)容都相應(yīng)包含在各章節(jié)中

有關(guān)了解內(nèi)存管理的相關(guān)理論

內(nèi)存管理概念：

內(nèi)存管理，是指軟件運(yùn)行時(shí)對(duì)計(jì)算機(jī)內(nèi)存資源的分配和使用的技術(shù)。其最主要的目的是如何高效，快速的分配，并且在適當(dāng)?shù)臅r(shí)候釋放和回收內(nèi)存資源。內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待.分區(qū)長(zhǎng)度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問(wèn)題，提高了主存資源的利用率。

內(nèi)存管理的必要性：

內(nèi)存管理對(duì)于編寫(xiě)出高效率的 Windows 程序是非常重要的，這是因?yàn)閃indows 是多任務(wù)系統(tǒng)，它的內(nèi)存管理和單任務(wù)的 DOS 相比有很大的差異。DOS是單任務(wù)操作系統(tǒng)，應(yīng)用程序分配到內(nèi)存后，如果它不主動(dòng)釋放，系統(tǒng)是不會(huì)對(duì)它作任何改變的；但 Windows 卻不然，它在同一時(shí)刻可能有多個(gè)應(yīng)用程序共享內(nèi)存，有時(shí)為了使某個(gè)任務(wù)更好地執(zhí)行，Windows 系統(tǒng)可能會(huì)對(duì)其它任務(wù)分配的內(nèi)存進(jìn)行移動(dòng)，甚至刪除。因此，我們?cè)?Windows 應(yīng)用程序中使用內(nèi)存時(shí)，要遵循Windows 內(nèi)存管理的一些約定，以盡量提高 Windows 內(nèi)存的利用率。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

1.3 內(nèi)存的物理組織：

物理地址：

把內(nèi)存分成若干個(gè)大小相等的存儲(chǔ)單元，每個(gè)存儲(chǔ)單元占 8 位，稱(chēng)作字節(jié)（byte）。每個(gè)單元給一個(gè)編號(hào)，這個(gè)編號(hào)稱(chēng)為物理地址（內(nèi)存地址、絕對(duì)地址、實(shí)地址）。

二、物理地址空間： 物理地址的集合稱(chēng)為物理地址空間（主存地址空間），它是一個(gè)一維空間。

什么是虛擬內(nèi)存：

虛擬內(nèi)存是內(nèi)存管理技術(shù)的一個(gè)極其實(shí)用的創(chuàng)新。它是一段程序（由操作系統(tǒng)調(diào)度），持續(xù)監(jiān)控著所有物理內(nèi)存中的代碼段、數(shù)據(jù)段，并保證他們?cè)谶\(yùn)行中的效率以及可靠性，對(duì)于每個(gè)用戶(hù)層（user-level）的進(jìn)程分配一段虛擬內(nèi)存空間。當(dāng)進(jìn)程建立時(shí)，不需要在物理內(nèi)存件之間搬移數(shù)據(jù)，數(shù)據(jù)儲(chǔ)存于磁盤(pán)內(nèi)的虛擬內(nèi)存空間，也不需要為該進(jìn)程去配置主內(nèi)存空間，只有當(dāng)該進(jìn)程被被調(diào)用的時(shí)候才會(huì)被加載到主內(nèi)存。

連續(xù)動(dòng)態(tài)分區(qū)內(nèi)存管理方式的實(shí)現(xiàn)

在早期的操作系統(tǒng)中，主存分配廣泛采用連續(xù)分配方式。連續(xù)分配方式，是指為一個(gè)用戶(hù)程序分配一個(gè)連續(xù)的內(nèi)存空間，該連續(xù)內(nèi)存空間指的的是物理內(nèi)存。下面介紹連續(xù)分配的四種方式。

單一連續(xù)分配（單個(gè)分區(qū)）

最簡(jiǎn)單的存儲(chǔ)管理方式，用于多道程序設(shè)計(jì)技術(shù)之前。內(nèi)存分為系統(tǒng)區(qū)和用戶(hù)區(qū)，系統(tǒng)區(qū)由操作系統(tǒng)使用。用戶(hù)區(qū)作為一個(gè)連續(xù)的分區(qū)分配給一個(gè)作業(yè)。分區(qū)存儲(chǔ)管理是滿(mǎn)足多道程序設(shè)計(jì)的最簡(jiǎn)單的一種存儲(chǔ)管理方法，它允許多 4個(gè)用戶(hù)程序同時(shí)存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。按分區(qū)劃分方式可分為固定分區(qū)和可變分區(qū)。

固定分區(qū)存儲(chǔ)管理

把內(nèi)存的用戶(hù)區(qū)預(yù)先劃分成多個(gè)分區(qū)，每個(gè)分區(qū)大小可以相同，也可以不同。（分區(qū)的劃分由計(jì)算機(jī)的操作員或者由操作系統(tǒng)給出，并給出主存分配表）分區(qū)個(gè)數(shù)固定，分區(qū)的大小固定。一個(gè)分區(qū)中可裝入一個(gè)作業(yè)，作業(yè)執(zhí)行過(guò)程中不會(huì)改變存放區(qū)域。早期的 IBM 的 OS/MFT（具有固定任務(wù)數(shù)的多道程序系統(tǒng)）采用了這種固定分區(qū)的方法。

可變分區(qū)存儲(chǔ)管理（動(dòng)態(tài)分區(qū)）

內(nèi)存不是預(yù)先劃分好的，而是在系統(tǒng)運(yùn)行的過(guò)程中建立分區(qū).當(dāng)作業(yè)裝入主存時(shí)，根據(jù)作業(yè)所需要的主存容量查看是否有足夠的主存空間，若有則按需要分割一個(gè)分區(qū)給該作業(yè)；否則令該作業(yè)等待。分區(qū)長(zhǎng)度不固定分區(qū)個(gè)數(shù)不固定。這種存儲(chǔ)管理的方法克服了固定分區(qū)嚴(yán)重浪費(fèi)主存的問(wèn)題，提高了主存資源的利用率。ＩＢＭ操作系統(tǒng)ＯＳ／ＭＶＴ采用可變分區(qū)存儲(chǔ)管理。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

可重定位分區(qū)存儲(chǔ)管理

解決碎片問(wèn)題的一種簡(jiǎn)單方法是采用可重定位分區(qū)分配.。其中心思想是，把不同程序，且在內(nèi)存中地址不連續(xù)的想法讓他們連續(xù)。

例：內(nèi)存中現(xiàn)有 3 個(gè)空閑區(qū)，現(xiàn)有一作業(yè)到達(dá)，要求獲得 30k 內(nèi)存空間，沒(méi)有分區(qū)滿(mǎn)足容量要求，若想把作業(yè)裝入，可將內(nèi)存中所有作業(yè)進(jìn)行移動(dòng)，這樣把原來(lái)分散的空閑區(qū)匯集成一個(gè)大的空閑區(qū)。將內(nèi)存中的作業(yè)進(jìn)行移動(dòng)使它們連接在一起把原來(lái)分散的多個(gè)小分區(qū)拼接成一個(gè)大的空閑區(qū).這個(gè)過(guò)程稱(chēng)為”緊湊”或”移動(dòng)”。需解決的問(wèn)題:每次”緊湊”后程序或數(shù)據(jù)裝入的物理地址變化采用動(dòng)態(tài)重定位。

問(wèn)題描述和分析

系統(tǒng)應(yīng)利用某種分配算法，從空閑分區(qū)鏈表中找到所需大小的分區(qū)，如果空閑分區(qū)大小大于請(qǐng)求分區(qū)大小，則從該分區(qū)中按改請(qǐng)求的大小劃分出一塊內(nèi)存空間大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑鏈表中。然后，將分配區(qū)的首址返回給調(diào)用者。

當(dāng)進(jìn)程運(yùn)行完畢師范內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)以下四種情況之一：

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

⑵該空閑區(qū)的上相鄰區(qū)是空閑區(qū)：將釋放區(qū)與上空閑區(qū)合并為一個(gè)空閑區(qū)，其起始地址為上空閑區(qū)的起始地址，大小為上空閑區(qū)與釋放區(qū)之和。合并后，修改上空閑區(qū)對(duì)應(yīng)的可用表的表目項(xiàng)或自由鏈指針。

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

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

程序流程圖

內(nèi)存分配流程圖，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

從頭開(kāi)始查表檢索完否？NY返回分區(qū)大小>所需大小N繼續(xù)檢索下一個(gè)表項(xiàng)Y分區(qū)大小-所需大小<=不可再分割大小N從該分區(qū)中劃出所需大小的新分區(qū)Y將該分區(qū)從鏈中移出將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回

內(nèi)存回收流程圖，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

開(kāi)始判斷空閑區(qū)上下內(nèi)存情況上為空下為空上下都為空上下都不為空將上面的空閑區(qū)合并，并回收將下面的空閑區(qū)合并，并回收將上下的空閑區(qū)合并，并回收直接將其回收結(jié)束 數(shù)據(jù)結(jié)構(gòu)體分析

⑴進(jìn)程屬性結(jié)構(gòu)體 typedef struct readyque { char name[10];int size;}readyque,*readyqueue;⑵空閑鏈表結(jié)構(gòu)體 typedef struct idlyspace { int from;int size;idlyspace * next;}idlyspace,*idly;⑶已分配鏈表結(jié)構(gòu)體 typedef struct busyspace { int from;readyque r;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

busyspace * next;}busyspace,*busy

主要程序代碼分析

⑴主函數(shù)//代碼請(qǐng)?zhí)砑舆m當(dāng)?shù)淖⑨尅nt 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.......................歡迎來(lái)到動(dòng)態(tài)分區(qū)存儲(chǔ)管理系統(tǒng)..................nn”);printf(“...........................請(qǐng)選擇要執(zhí)行的算法:...........................n”);printf(“.........................1.最先適應(yīng)算法

...............................n”);printf(“.........................2.下次適應(yīng)算法............................n”);printf(“..........................3.最優(yōu)適應(yīng)算法

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

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

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

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

printf(“.........................2.進(jìn)程撤銷(xiāo)回收空間...........................n”);

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

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

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

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

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

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

scanf(“%d”,&i);

switch(i)

{

case 1:

switch(t)

{

case 1:

t1=FF();湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

break;

case 2:

t1=NF();

break;

case 3:

t1=BF();

break;

case 4:

t1=WF();

break;

default:

printf(“選擇算法錯(cuò)誤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;}

第三章 ：分析并實(shí)現(xiàn)四種內(nèi)存分配算法

最先適應(yīng)算法

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

分配：當(dāng)進(jìn)程申請(qǐng)大小為 SIZE 的內(nèi)存時(shí)，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到容量滿(mǎn)足要求（≥SIZE）的空閑區(qū)為止。從該空閑區(qū)中劃出大小為 SIZE的分區(qū)分配給進(jìn)程，余下的部分仍作為一個(gè)空閑區(qū)，但要修改其首址和大小。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

優(yōu)點(diǎn)：這種算法是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址 6部分的大空閑區(qū)，有利于大作業(yè)的裝入。

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

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

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

//尋找空閑表中大小滿(mǎn)足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn)

{

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ìn)程分配空間

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

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;}

下次適應(yīng)分配算法

最先適應(yīng)算法的變種。

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

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

int mt=256;idly l=Is2;idly min=NULL;busy b=Bs;while(l)//尋找空閑表中大小滿(mǎn)足申請(qǐng)進(jìn)程所需大小并且起址最小的空閑結(jié)點(diǎn)

{

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;

//如果找到則為進(jìn)程分配空間

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

}

//將申請(qǐng)空間進(jìn)程插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改相應(yīng)空閑節(jié)點(diǎn)的起址和大小

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

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

Is2=min->next;

結(jié)點(diǎn)

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指向修改結(jié)點(diǎn)的下一個(gè)

//循環(huán)查找 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

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;}

最優(yōu)適應(yīng)算法

空閑區(qū)按容量遞增的次序排列。

分配：當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間，系統(tǒng)順序查找空閑區(qū)表（鏈），直到找到第一個(gè)滿(mǎn)足容量要求的空閑區(qū)為止。采用最優(yōu)適應(yīng)算法選中的空閑區(qū)是滿(mǎn)足容量要求的最小空閑區(qū)。優(yōu)點(diǎn)：選中的空閑區(qū)是滿(mǎn)足容量要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。

缺點(diǎn)：空閑區(qū)的大小一般與申請(qǐng)分區(qū)大小不相等，因此將其一分為二，留下來(lái)的空閑區(qū)一般情況下是很小的，以致無(wú)法使用。隨著時(shí)間的推移，系統(tǒng)中的小空閑區(qū)會(huì)越來(lái)越多，從而造成存儲(chǔ)空間的浪費(fèi)。最優(yōu)適應(yīng)算法 int BF(){ int t=0;湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

readyque D;printf““請(qǐng)輸入進(jìn)程名:””);scanf““%””,D.name);

printf““輸入進(jìn)程申請(qǐng)空間大小:””);scanf““%””,&D.size);

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

{

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;

//申請(qǐng)分配用于存放進(jìn)程的內(nèi)存

//找到第一個(gè)滿(mǎn)足要求的空閑塊

//將第一個(gè)滿(mǎn)足要求的空閑塊（min）的首地址賦給j

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

{

j->r.name[i]=D.name[i];16 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

}

j->r.size=D.size;

while(b->next)

//按從小到大的順序查找新進(jìn)程在已分配區(qū)中的位置

{ 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;}

最壞適應(yīng)算法

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

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

printf““輸入進(jìn)程申請(qǐng)空間大小:””);

//將所輸入的進(jìn)程插入進(jìn)程鏈

//改變?cè)摽臻e塊的起始地址 //改變?cè)摽臻e塊的剩余大小 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

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

//輸入進(jìn)程申請(qǐng)的空間大小

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

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

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

//找到空閑分區(qū)中大小滿(mǎn)足進(jìn)程的請(qǐng)求且尺寸最大的結(jié)點(diǎn)

while(l){

if(D.size<=l->size)//判斷進(jìn)程所申請(qǐng)的大小是否小于空閑區(qū)的各結(jié)點(diǎn)大小

{

if(l->size>mt)

{ mt=l->size;min=l;//min指向空閑區(qū)中尺寸最大的結(jié)點(diǎn)

t=1;

}

}

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

{

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;

//判斷是否找到了空閑區(qū)的滿(mǎn)足結(jié)

//l指向空閑鏈表下一個(gè)結(jié)點(diǎn)

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

while(b->next)置

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

{ if(b->next->fromfrom)

b=b->next;else

break;

}

//把此進(jìn)程結(jié)點(diǎn)j插入到已分配鏈表中

j->next=b->next;

b->next=j;

//修改空閑鏈表的相應(yīng)結(jié)點(diǎn)的參數(shù)

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

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

可變分區(qū)的回收

當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)去，否則把釋放區(qū)作為一個(gè)空閑區(qū)插入到空閑表的適當(dāng)位置。

釋放區(qū)與空閑區(qū)相鄰的四種情況。

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

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

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

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

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

回收內(nèi)存算法

int recover(){ readyque D;printf““請(qǐng)輸入想要回收的進(jìn)程名””);

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;

}

//如果在已分配鏈表中則釋放該結(jié)點(diǎn)所占空間

if(yo)

{

int t=b->next->from;

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

//查找輸入的進(jìn)程名是否在已分配湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

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)

//所回收進(jìn)程與空閑結(jié)點(diǎn)上鄰接 {

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都不鄰接

//所回收進(jìn)程與空閑結(jié)點(diǎn)下鄰接 {

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都 21 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

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;

}

//從已分配鏈表中釋放所回收進(jìn)程

busy tb=b->next;

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

free(tb);

return 1;

}

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

//所回收進(jìn)程與空閑結(jié)點(diǎn)上下都鄰調(diào)試與操作說(shuō)明

初始界面

程序初始界面，有四個(gè)塊選擇，選擇要執(zhí)行的算法，調(diào)試以最壞算法為例，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

選擇最壞適應(yīng)算法，如圖

模擬內(nèi)存分配

給進(jìn)程a分配內(nèi)存20，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

已分配分區(qū)說(shuō)明表界面

同理，給進(jìn)程b分配內(nèi)存30，給進(jìn)程c分配內(nèi)存40，給進(jìn)程d分配50，給進(jìn)程e分配60，如圖

空閑分區(qū)說(shuō)明表界面 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

查看空閑分區(qū)，如圖

回收內(nèi)存界面

回收進(jìn)程b和d所占內(nèi)存，如圖

已分配分區(qū)說(shuō)明表和空閑分區(qū)說(shuō)明表 如圖 湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

重新申請(qǐng)內(nèi)存界面

再為新進(jìn)程i分配內(nèi)存30，如圖

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

根據(jù)最壞適應(yīng)算法結(jié)合圖所示可知，該算法將會(huì)從空閑分區(qū)表中選擇一塊最大的內(nèi)存空間分配給進(jìn)程i，從圖也可看出該模擬算法實(shí)現(xiàn)了最壞適應(yīng)算法

湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

總結(jié)與體會(huì)

本次做的課題是動(dòng)態(tài)分區(qū)分配算法實(shí)現(xiàn)，此次課程設(shè)計(jì)成功實(shí)現(xiàn)了內(nèi)存分配和內(nèi)存回收，內(nèi)存分配中包含了四種算法，分別是首次適應(yīng)算法，循環(huán)首次適應(yīng)算法，最佳適應(yīng)算法和最壞適應(yīng)算法。經(jīng)編碼調(diào)試，表明該程序模塊是有效可行的。

通過(guò)這門(mén)課程的學(xué)習(xí)讓我充分了解了內(nèi)存管理的機(jī)制實(shí)現(xiàn)，從而更深一步的的對(duì)計(jì)算機(jī)

有了很多了解，這對(duì)于以后我們的研究和學(xué)習(xí)計(jì)算機(jī)系統(tǒng)起到了很重要的作用。

對(duì)于本次論文制作，自己的編程能力有所提高，對(duì)操作系統(tǒng)內(nèi)存分配，存儲(chǔ)空間的回收都有全新的認(rèn)識(shí)。

在這次操作系統(tǒng)課程設(shè)計(jì)中，我使用了c++編寫(xiě)系統(tǒng)軟件，對(duì)os中可變分區(qū)存儲(chǔ)管理有了深刻的理解，但是過(guò)程中遇到了很多困難，一邊做一邊學(xué)，對(duì)c++有了比較多的理解。

實(shí)驗(yàn)中遇到很多問(wèn)題，浪費(fèi)了很多時(shí)間，總而言之是自己學(xué)習(xí)還不夠好，不扎實(shí)，希望在以后學(xué)習(xí)中加以改善，學(xué)到更多知識(shí)。

參考文獻(xiàn)

【1】 湯子瀛，哲鳳屏，湯小丹.計(jì)算機(jī)操作系統(tǒng).西安：西安電子科技大學(xué)出版社，2001.。湖北民族學(xué)院信息工程學(xué)院11級(jí)計(jì)算機(jī)專(zhuān)業(yè)操作系統(tǒng)課程設(shè)計(jì)

【2】 任愛(ài)華.操作系統(tǒng)實(shí)用教程.北京：清華大學(xué)出版社，2001。