電腦科學與應用系
課程設計報告
作業系統原理
目錄1 題目簡述 2
2 需求分析 2
2.1設計思想 2
2.2要求 2
2.3任務 3
2.4執行環境 3
2.5開發工具 3
3 概要設計與詳細設計 3
3.1系統流程圖 3
3.2演算法流程圖 5
4 編碼與實現 10
4.1資料結構和演算法設計 10
4.2程式除錯與截圖 17
5 課程設計總結 20
參考文獻 21
附錄 22
動態分割槽分配演算法的模擬
1 題目簡述
動態分割槽分配是根據程序的實際需要,動態地為之分配記憶體空間。在實現可變分割槽分配時,將涉及到分割槽分配中所用到的資料結構、分配演算法和分割槽的分配與**操作。常用的資料結構有空閒分割槽表和空閒分割槽鏈兩種,分割槽分配演算法主要有首次適應演算法、最佳適應演算法、最壞適應演算法等。
本次試驗通過c語言進行程式設計除錯並執行,形象地表現出動態分割槽分配方式,直觀地展示了首次適應演算法、最佳適應演算法、最壞適應演算法對記憶體的釋放和**方式之間的區別。加深了我對三種演算法優缺點的理解,幫助我了解一些資料結構和分配演算法,進一步加深我對動態分割槽儲存器管理方式及其實現過程的理解。主要問題在於,如何解決三種演算法對記憶體的釋放和**空間的表示。
動態分割槽分配又稱為可變分割槽分配,這種分配方式並不是事先將主存劃分成一塊塊的分割槽,而是在作業進入主存時,根據作業的大小動態地建立分割槽,並使分割槽的大小正好適適應作業的需要。因此,分割槽中的大小是可變的,分割槽的數目也是可變的。
2 需求分析
2.1設計思想
(1)首次適應演算法(first_fit)
空閒分割槽鏈以位址遞增的次序連線。在分配記憶體時,從聯手開始順序查詢,直到找到乙個大小能滿足要求的空閒分割槽為止;然後再按照作業大小,從該分割槽劃出一塊記憶體空間給請求者,餘下的空閒分割槽仍然留在空閒鏈中。若從鏈首直至鏈尾都找不到乙個能滿足要求的分割槽,則此次記憶體分配失敗。
(2)最佳適應演算法(best_fit)
它從全部空閒區中找出能滿足作業要求的、且大小最小的空閒分割槽,這種方法能使碎片盡量小。為適應此演算法,空閒分割槽表(空閒區鏈)中的空閒分割槽要按從小到大進行排序,自表頭開始查詢到第乙個滿足要求的自由分割槽分配。該演算法保留大的空閒區,但造成許多小的空閒區。
(4)最壞適應演算法(worst_fit)
最壞適應分配演算法要掃瞄整個空閒分割槽或鍊錶,總是挑選乙個最大的空閒分割槽分割給作業使用。該演算法要求將所有的空閒分割槽按其容量從大到小的順序形成一空閒分割槽鏈,查詢時只要看第乙個分割槽能否滿足作業要求。優點是可使剩下的空閒分割槽不至於太小,產生碎片的機率最小,對中、小作業有利,同時該演算法查詢效率很高。
(4)記憶體**(free)
將釋放作業所在記憶體塊若改為空閒狀態,刪除其作業名,變為空。然後判斷該空閒塊是否與其他空閒塊相連,若釋放的記憶體空間與空閒塊相連時,則合併其為同乙個空閒鍊錶,同時修改開始位址及分割槽大小。
2.2要求
(1)用c++語言實現程式設計;
(2)利用結構體進行相關資訊處理;
(3)畫出查詢模組的流程圖;
(4)介面友好(良好的人機互交),程式要有注釋。
2.3任務
(1)掌握為實現多道程式併發執行,作業系統是如何通過作業排程選擇作業進入記憶體;
(2)系統如何為進入記憶體的作業分配記憶體空間,實現多道作業同時駐留記憶體,就緒程序佇列中的多個程序是如何以分式方式共享cpu,作業執行完成離開系統時,系統如何進行記憶體**,計算程序周轉時間;
(3)畫出所有模組的流程圖;
(4)編寫**;
(5)程式分析與除錯。
2.4執行環境
(1)windows2000/xp系統
(2)microsoft visual c++ 6.0編譯環境
2.5開發工具
c++語言
本程式採用c語言編寫,在windows下的visual c++環境下編譯,模擬可變分割槽儲存管理方式的記憶體分配與**。
3 概要設計與詳細設計
3.1系統流程圖
3.1.1系統流程圖
圖3.1.1 系統流程圖
3.2演算法流程圖
3.2.1記憶體分配流程圖
圖3.2.1 記憶體分配流程圖
3.2.2.首次適應演算法流程圖
圖3.2.2 首次適應演算法流程圖
3.2.3最佳適應演算法流程圖
圖3.2.3 最佳適應演算法流程圖
3.2.4 最壞適應演算法流程圖
圖3.2.4 最壞適應演算法流程圖
3.2.5 記憶體**流程圖
圖3.2.5 記憶體**流程圖
4 編碼與實現
4.1資料結構和演算法設計
相關資料結構定義:
空閒分割槽結構:typedef struct freearea()
線性鍊錶結構:typedef struct dulnode()
帶頭結點記憶體空間鍊錶結構:status initblock()
記憶體分配:status alloc()
顯示主存:void show()
測試類(主函式類):class testformemmanage
4.2程式除錯與截圖
1)首介面
2)首次適應演算法
測試資料:為作業申請空閒區800kb。作業1申請資源100kb,作業2申請資源120kb,作業3申請資源130kb,作業4申請資源140kb,釋放作業1和作業3,作業5申請資源160kb,這時,按照表從頭開始查詢,第乙個找到滿足條件的就停止查詢,並分配資源。
執行結果如下圖所示:
3)最佳適應演算法
測試資料:為作業申請空閒區800kb。作業1申請資源105kb,作業2申請資源115kb,作業3申請資源125kb,作業4申請資源135kb,釋放作業2和作業4,作業5申請資源145kb,這時,在每次的分配記憶體中,總是找到既滿足要求又是最小空閒分割槽,然後分配資源,這樣,就避免了「大材小用」的問題。
執行結果如下圖所示:
4)最壞適應演算法
測試資料:為作業申請空閒區800kb。作業1申請資源80kb,作業2申請資源100kb,作業3申請資源120kb,作業4申請資源140kb,釋放作業1和作業3,作業5申請資源160kb,這時,在掃瞄整個空閒分割槽鍊錶時,總是找到既滿足要求又是最大空閒分割槽,然後把它分割給作業。
執行結果如下圖所示:
5 課程設計總結
為期五周的課程設計,對於我個人來說是相當有難度的。在設計的過程中,有很多問題不是很清楚,所以做起來就就很困難,剛開始的時候都有點無從下手的感覺。很多時候在遇到問題時,基本知識都了解,但是就不知道怎麼才能把它們都整合到一塊,也就是說知識都是很零散的,沒有乙個完整的系統。
而且,又由於基礎知識不牢固,使得我在這次的課程設計中感到更加力不從心。
在設計的過程中,每走一步就會發現,思路想出來很容易,但涉及到實現的時候,總是有點手無足措。對於本次的課程設計,裡面還有很多需要改進的地方。乙個程式的順利出爐,少不了反覆地除錯和修改。
在除錯的過程中,總是會發生很多錯誤,但在解決這些錯誤的時候,開始很模糊的概念就會變得越來越清晰。其實很多錯誤都是很類似的,只要解決了乙個,其餘的就會迎刃而解了。
「千里之行,始於足下」,通過這次課程設計,我深深體會到這句千古名言的真正含義,我今天認真的進行課程設計,學會腳踏實地邁開這一步,就是為明天能穩健地在社會大潮中奔跑打下堅實的基礎。這次的課程設計,使我樹立了正確的設計思想,培養實事求是、嚴肅認真、高度負責的學習作風,加強操作能力的訓練和培養嚴謹求實的科學作風更尤為重要。在這次設計過程中,充分體現出自己單獨設計課程的能力以及綜合運用知識的能力,體會了學以致用、突出自己勞動成果的喜悅心情,從中發現自己平時學習的不足和薄弱環節,從而加以彌補。
通過本次實驗,我掌握了實現多道程式併發執行,作業系統是如何通過作業調, 選擇作業進入記憶體以及系統是如何為進入記憶體的作業分配記憶體空間,實現多道作業同時駐留記憶體,就緒程序佇列中的多個程序是如何以分式方式共享cpu,作業執行完成離開系統時,系統如何進行記憶體**。
最後,感謝我們的荊立夏老師,老師嚴謹細緻、一絲不苟的作風將會一直是我工作、學習中的榜樣;老師循循善誘的教導和不拘一格的教學思路給予我無盡的啟迪;這次課程設計的每個實驗細節和每個資料,都離不開老師您的細心指導。而您開朗的個性和寬容的態度,幫助我能夠很順利的完成了這次課程設計。祝願老師您在以後的工作和生活中繼續保持健康的身體和愉快的心情,再次感謝!
同時,也很感謝對我幫助過的同學們,謝謝你們對我的幫助和支援,讓我感受到同學的友誼和溫暖。
參考文獻
[1] 李玲玲. c語言程式設計[m]. 遼寧大學出版社,2010.1
[2] 譚浩強.程式設計基礎與c語言 .瀋陽:遼寧大學出版社,2010.1
[3] 嚴蔚敏、吳偉民等.資料結構(c語言版).北京:清華大學出版社,2008.
[4] 湯子瀛、梁紅兵等.《計算機作業系統第三版》.北京:西安電子科技大學出版社,2009.
附錄源**
#include
#include
#define free 0 //空閒狀態
#define busy 1 //已用狀態
#define ok 1 //完成
#define error 0 //出錯
#define max_length 800 //最大記憶體空間為800kb
typedef int status;
typedef struct freearea//定義乙個空閒區說明表結構
{ int id; //分割槽號
long size; //分割槽大小
long address; //分割槽位址
int state; //狀態
作業系統實驗報告
2014 2015 學年第 2 學期 系別計算機學院 專業電腦科學與技術 班級 2014級專公升本 姓名蔡圓圓 學號 1410211014 授課老師趙群禮 實驗一 熟悉linux基本命令及程式設計環境 實驗總結 編寫程式 gedit編輯器 編寫程式 c 存放 gcc linux c程式編譯工具 當前...
作業系統實驗報告
實驗名稱 哲學家就餐問題 班級 通訊1202班 學號 u201213584 姓名 趙越 指導老師 許毅平 一 實驗目的 1.熟練使用vc 6.0編譯環境,除錯並正確執行程式,更加熟練地利用c語言解決問題 2.了解哲學家就餐的基本原理,掌握死鎖的必要條件。3.理解源程式中產生和防止的演算法,及相關視窗...
作業系統實驗報告
實驗報告 一 實驗名稱 程序排程的設計與實現 二 實驗目的 1 綜合應用下列知識點設計並實現作業系統的程序排程 鄰接表,布林數 組,非阻塞輸入,圖形使用者介面 gui,程序控制塊,程序狀態轉換,多 級反饋佇列程序排程演算法。2 加深理解作業系統程序排程的過程。3 加深理解多級反饋佇列程序排程演算法。...