吳敬仙　繆行外

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

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

中圖分類號:G642 文獻標識碼:B

1引言

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

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

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

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

3伙伴算法( Buddy)分析

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

3.1Linux伙伴算法思想

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

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

3.2伙伴算法模擬

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

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

typedef struct _BlockData

{ int ID; //塊組號

int StartAddr; //塊首地址

int BlockSize; //塊大小

CString USDFlag; //塊屬性標志

// 已分配True或未分配False

} BLOCKDATA;

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

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

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

(3) 分配過程

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

(4) 窗口同步展示

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

4結(jié)論

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

參考文獻:

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

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

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