操作系統存儲管理方法與教學演示系統

吳敬仙　繆行外

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

關鍵詞:虛擬存儲;伙伴算法;日志;動態數據

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

1引言

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

2課程教學手段與方法的改進

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

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

3伙伴算法( Buddy)分析

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

3.1Linux伙伴算法思想

Linux虛擬存儲技術,通過多級頁表將虛擬地址轉換為物理地址。采用位圖和鏈表方式管理內存頁。

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

3.2伙伴算法模擬

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

(1)BLOCKDATA結構

typedef struct _BlockData

{ int ID; //塊組號

int StartAddr; //塊首地址

int BlockSize; //塊大小

CString USDFlag; //塊屬性標志

// 已分配True或未分配False

} BLOCKDATA;

描述當前某個塊組首地址、大小、空閑標志。所有塊組的BLOCKDATA結構被動態記錄在與此關聯的數據庫的動態數據集中。

(2) 系統界面

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

(3) 分配過程

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

(4) 窗口同步展示

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

4結論

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

參考文獻:

[1] 李善平,陳文智.邊干邊學——Linux內核指導[M].杭州:浙江大學出版社,2002.

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

[3] 陳莉君.Linux 操作系統內核分析[M].人民郵電出版社,1999.