操作系統(tǒng)存儲(chǔ)管理方法與教學(xué)演示系統(tǒng)

吳敬仙　繆行外

摘要:“操作系統(tǒng)”課程具有理論性強(qiáng)、知識(shí)點(diǎn)多、概念多等特點(diǎn)。本文通過(guò)內(nèi)存分區(qū)算法與內(nèi)核機(jī)制演示系統(tǒng),展示內(nèi)存管理的最佳適應(yīng)法、最差適應(yīng)法、首次適應(yīng)法以及伙伴算法的動(dòng)態(tài)模擬實(shí)現(xiàn)。多媒體教學(xué)方法的應(yīng)用,幫助學(xué)生理解內(nèi)存管理的分配算法,提高了學(xué)生學(xué)習(xí)興趣,課堂教學(xué)質(zhì)量得到提高。

關(guān)鍵詞:虛擬存儲(chǔ);伙伴算法;日志;動(dòng)態(tài)數(shù)據(jù)

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

1引言

操作系統(tǒng)(Operating System,簡(jiǎn)稱OS)是用于控制、管理硬件和軟件資源以及方便用戶使用的程序集合,是用戶與計(jì)算機(jī)的接口。隨著操作系統(tǒng)在現(xiàn)代計(jì)算機(jī)系統(tǒng)中的作用越來(lái)越重要,“操作系統(tǒng)”課程已成為計(jì)算機(jī)類專業(yè)的必修課程。由于“操作系統(tǒng)”課程具有概念多、抽象、內(nèi)容廣、更新快的特點(diǎn),對(duì)老師授課和學(xué)生掌握難度都較大,如何將“操作系統(tǒng)”課程中抽象的原理與具體繁瑣的操作系統(tǒng)實(shí)現(xiàn)技術(shù)有機(jī)的結(jié)合起來(lái),以比較直觀的、易于理解、易于掌握的形式展現(xiàn)出來(lái),一直是操作系統(tǒng)教學(xué)過(guò)程中關(guān)心與探討的一大問(wèn)題。

2課程教學(xué)手段與方法的改進(jìn)

教學(xué)方法是指為達(dá)到教學(xué)目的,完成教學(xué)內(nèi)容,運(yùn)用教學(xué)手段而進(jìn)行的,有教學(xué)原則指導(dǎo)的一整套方式組成的、師生相互作用的活動(dòng)。

課程的時(shí)代化要求教學(xué)必須與時(shí)俱進(jìn),本課程教學(xué)實(shí)例分析與實(shí)驗(yàn)平臺(tái)均已采用目前流行的Linux 操作系統(tǒng)。在教學(xué)實(shí)踐中,不斷探索教學(xué)方法,包括為“操作系統(tǒng)”課程設(shè)計(jì)了“操作系統(tǒng)多媒體教學(xué)課件”與“操作系統(tǒng)多媒體教學(xué)輔助演示系統(tǒng)”。通過(guò)多媒體教學(xué)課件與教學(xué)輔助演示系統(tǒng)將一些較抽象的原理,諸如:內(nèi)存空閑分區(qū)的記載與分配回收的過(guò)程、虛地址到實(shí)地址的動(dòng)態(tài)轉(zhuǎn)換、存儲(chǔ)管理伙伴算法等,用課件動(dòng)畫(huà),生動(dòng)形象地揭示、演繹抽象原理的實(shí)現(xiàn)。本系統(tǒng)程序開(kāi)發(fā)平臺(tái)為Visual C++6.0,主要功能由圖1描述。

3伙伴算法( Buddy)分析

管理存儲(chǔ)器有許多不同的方式:單一連續(xù)區(qū)存儲(chǔ)管理、分區(qū)存儲(chǔ)管理、分頁(yè)存儲(chǔ)管理、分段存儲(chǔ)管理等。本設(shè)計(jì)針對(duì)分區(qū)存儲(chǔ)管理,通過(guò)分區(qū)表格記載內(nèi)存空閑區(qū),進(jìn)行分配與回收管理并作模擬演示。采用的算法有最佳適應(yīng)法、最差適應(yīng)法、首次適應(yīng)法和伙伴算法。

3.1Linux伙伴算法思想

Linux虛擬存儲(chǔ)技術(shù),通過(guò)多級(jí)頁(yè)表將虛擬地址轉(zhuǎn)換為物理地址。采用位圖和鏈表方式管理內(nèi)存頁(yè)。

伙伴策略:將主存劃分成塊,塊大小為2冪次頁(yè)(塊組):1頁(yè),2頁(yè),4頁(yè),8頁(yè),16頁(yè),32頁(yè)。塊內(nèi)頁(yè)連續(xù)存儲(chǔ)于MEM,當(dāng)分配一個(gè)空閑區(qū):S=2k時(shí),若空閑組鏈中2k鏈非空:分配出去。若2k鏈空:則找2 k+1鏈,不空:分成2個(gè)2 k。一個(gè)分配,一個(gè)進(jìn)2 k鏈。2 k+1 鏈空 :繼續(xù)找2 k+2 鏈。

3.2伙伴算法模擬

伙伴算法有效地分配和回收頁(yè)塊。頁(yè)分配使用2的冪次大小的塊。這意味著可以分配1頁(yè)大小,2頁(yè)大小,4頁(yè)大小的塊,依此類推。只要系統(tǒng)有滿足需要的足夠的空閑頁(yè),模擬分配代碼就會(huì)在 free_area中查找滿足需要大小的一個(gè)頁(yè)塊。free_area中的每一個(gè)單元都有描述自身大小的頁(yè)塊的占用和空閑情況的位圖。

(1)BLOCKDATA結(jié)構(gòu)

typedef struct _BlockData

{ int ID; //塊組號(hào)

int StartAddr; //塊首地址

int BlockSize; //塊大小

CString USDFlag; //塊屬性標(biāo)志

// 已分配True或未分配False

} BLOCKDATA;

描述當(dāng)前某個(gè)塊組首地址、大小、空閑標(biāo)志。所有塊組的BLOCKDATA結(jié)構(gòu)被動(dòng)態(tài)記錄在與此關(guān)聯(lián)的數(shù)據(jù)庫(kù)的動(dòng)態(tài)數(shù)據(jù)集中。

(2) 系統(tǒng)界面

本系統(tǒng)為空閑分區(qū)算法與內(nèi)核機(jī)制演示系統(tǒng),系統(tǒng)初始主界面見(jiàn)圖2所示 。主窗口中間16*16網(wǎng)格區(qū),每小格代表一個(gè)基本主存頁(yè)塊。用綠色小方格表示該頁(yè)為空閑,用紅色小方格表示該頁(yè)為忙。初始時(shí),設(shè)256個(gè)頁(yè)面均為空閑。當(dāng)前內(nèi)存使用率通過(guò)網(wǎng)格區(qū)右側(cè)方框圖顯示。主窗口右方,提供一組“初始化”、“分配”、“淘汰”、“演示”動(dòng)作按鈕。右下區(qū)記錄了對(duì)本系統(tǒng)進(jìn)行的所有操作,即操作日志。被記載在日志文件中。故當(dāng)再次啟動(dòng)本系統(tǒng)時(shí),可以再次見(jiàn)到退出系統(tǒng)時(shí)的狀態(tài)。

(3) 分配過(guò)程

當(dāng)分配一個(gè)長(zhǎng)度為prosize,即2k塊組時(shí),查動(dòng)態(tài)數(shù)據(jù)集中有否該長(zhǎng)度塊組處于空閑(False標(biāo)志),有則將該記錄標(biāo)志改為T(mén)rue,示作成功分配。否則,調(diào)用函數(shù),采用遞歸方法將塊組size =2k+1(若存在),分解為一對(duì)伙伴(2k 、2k),分別以二個(gè)塊組記錄進(jìn)動(dòng)態(tài)數(shù)據(jù)集。分配流程見(jiàn)圖3所示。

(4) 窗口同步展示

圖2、圖4 分別為程序初始界面窗口與數(shù)據(jù)集初態(tài)。點(diǎn)擊“分配”按鈕,可進(jìn)入分配界面,選擇內(nèi)存分配算法(伙伴算法)、輸入分配大小要求,執(zhí)行動(dòng)態(tài)分配過(guò)程。若首先分配4頁(yè),動(dòng)態(tài)數(shù)據(jù)集中將256個(gè)連續(xù)頁(yè)塊作遞歸分割,并將第一個(gè)4頁(yè)作分配(True),另一個(gè)4頁(yè)的伙伴空閑(False)。若隨后再分配16頁(yè),空閑區(qū)大小的頁(yè)塊和首地址的變化見(jiàn)圖5,內(nèi)存分布狀態(tài)見(jiàn)圖6所示。任何時(shí)候,都可選擇“淘汰”按鈕,將內(nèi)存空間作回收及合并,執(zhí)行淘汰處理。由于每次所作的內(nèi)存分配與回收操作,都被記錄在日志文件中,并通過(guò)主窗口顯示。動(dòng)態(tài)過(guò)程一目了然。

4結(jié)論

通過(guò)類似Buddy算法等的多媒體教學(xué)課件,較充分展示了教學(xué)內(nèi)容,并且從難以理解的基本概念開(kāi)始、運(yùn)用教學(xué)輔助演示系統(tǒng)的教學(xué)手段,以比較直觀、生動(dòng)、易于理解的形式展現(xiàn)出來(lái),有效的達(dá)到教學(xué)目的。

參考文獻(xiàn):

[1] 李善平,陳文智.邊干邊學(xué)——Linux內(nèi)核指導(dǎo)[M].杭州:浙江大學(xué)出版社,2002.

[2] 孟慶昌.Linux 教程[M].北京:電子工業(yè)出版社,2002.

[3] 陳莉君.Linux 操作系統(tǒng)內(nèi)核分析[M].人民郵電出版社,1999.