《操作系統(tǒng)》實(shí)驗(yàn)指導(dǎo)書34103

1、操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書（第二版）華南農(nóng)業(yè)大學(xué)信息學(xué)院及軟件學(xué)院孫微微主編，張麗霞參編目 錄第一部分 操作系統(tǒng)實(shí)驗(yàn)要求1一、操作系統(tǒng)實(shí)驗(yàn)教學(xué)概述11、實(shí)驗(yàn)教學(xué)的基本情況12、實(shí)驗(yàn)教學(xué)的指導(dǎo)思想和教學(xué)目的13、實(shí)驗(yàn)項(xiàng)目表1二、操作系統(tǒng)實(shí)驗(yàn)教學(xué)規(guī)范21、實(shí)驗(yàn)課的意義22、實(shí)驗(yàn)步驟23、實(shí)驗(yàn)報告規(guī)范34、實(shí)驗(yàn)考核5第二部分 實(shí)驗(yàn)內(nèi)容6實(shí)驗(yàn)一 進(jìn)程同步互斥不死鎖的哲學(xué)家問題6實(shí)驗(yàn)二 進(jìn)程同步互斥讀者寫者問題7實(shí)驗(yàn)三 頁式虛擬存儲管理中地址轉(zhuǎn)換和缺頁中斷9實(shí)驗(yàn)四 單處理器系統(tǒng)的時間片輪轉(zhuǎn)進(jìn)程調(diào)度11實(shí)驗(yàn)五 單處理器系統(tǒng)的優(yōu)先數(shù)進(jìn)程調(diào)度14實(shí)驗(yàn)六 內(nèi)存分配和回收三種適應(yīng)法15實(shí)驗(yàn)七 內(nèi)存分配和回收伙伴系統(tǒng)17實(shí)

2、驗(yàn)八 死鎖避免銀行家算法18實(shí)驗(yàn)九 死鎖檢測資源分配圖化簡法19實(shí)驗(yàn)十 目錄及文件的長度和個數(shù)統(tǒng)計(jì)2020第一部分 操作系統(tǒng)實(shí)驗(yàn)要求一、操作系統(tǒng)實(shí)驗(yàn)教學(xué)概述1、實(shí)驗(yàn)教學(xué)的基本情況 課程總學(xué)時數(shù)：64學(xué)時； 課程總學(xué)分：3.5學(xué)分實(shí)驗(yàn)總學(xué)時：8適用專業(yè)：信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程專業(yè)，軟件學(xué)院軟件工程專業(yè)考核方式及方法：實(shí)際操作程序運(yùn)行實(shí)驗(yàn)報告。實(shí)驗(yàn)成績、考勤及書面作業(yè)成績組成平時成績。平時成績占課程總成績30，考試成績占課程總成績70。2、實(shí)驗(yàn)教學(xué)的指導(dǎo)思想和教學(xué)目的1）指導(dǎo)思想：通過由淺入深、循序漸進(jìn)、精講多練，培養(yǎng)學(xué)生對計(jì)算機(jī)操作系統(tǒng)的熟練使用，使學(xué)生全面了解操作系統(tǒng)的特

3、點(diǎn)，熟練掌握操作系統(tǒng)的基本設(shè)計(jì)方法和系統(tǒng)工作原理。2）教學(xué)目的：使學(xué)生通過實(shí)驗(yàn)來驗(yàn)證課堂教學(xué)的理論，并學(xué)會設(shè)計(jì)一些簡單的綜合應(yīng)用程序或小型的模擬操作系統(tǒng)。3、實(shí)驗(yàn)項(xiàng)目表操作系統(tǒng)實(shí)驗(yàn)是綜合性設(shè)計(jì)性實(shí)驗(yàn)，每位同學(xué)根據(jù)自己能力選擇一個。該實(shí)驗(yàn)是模擬實(shí)驗(yàn)，即不要求對真實(shí)操作系統(tǒng)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，而是對你自己所設(shè)置的一些數(shù)據(jù)結(jié)構(gòu)（如數(shù)組、鏈表或隊(duì)列）進(jìn)行操作，來模擬實(shí)現(xiàn)操作系統(tǒng)中的算法或調(diào)度行為。當(dāng)然你可以采用任何你熟悉的語言編寫。最終需要上交書面實(shí)驗(yàn)報告。二、操作系統(tǒng)實(shí)驗(yàn)教學(xué)規(guī)范1、實(shí)驗(yàn)課的意義實(shí)驗(yàn)是對學(xué)生的一種全面綜合訓(xùn)練。是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個教學(xué)環(huán)節(jié)。通常，實(shí)驗(yàn)題

4、中的問題比平時的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)驗(yàn)著眼于原理與應(yīng)用的結(jié)合點(diǎn)，使學(xué)生學(xué)會如何把書上學(xué)到的知識用于解決實(shí)際問題，培養(yǎng)軟件工作所需要的動手能力；另一方面，能使書上的知識變"活"，起到深化理解和靈活掌握教學(xué)內(nèi)容的目的。平時的練習(xí)較偏重于如何編寫功能單一的"小"算法，而實(shí)驗(yàn)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧，多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，還有很重要的一點(diǎn)是：機(jī)器是比任何教師都嚴(yán)厲的檢查者。2、實(shí)驗(yàn)步驟常用的軟件開發(fā)方法，是將軟件開發(fā)過程劃分為分析、設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)四

5、個階段。雖然操作系統(tǒng)課程中的實(shí)驗(yàn)題目遠(yuǎn)不如實(shí)際問題中的復(fù)雜程度高，但為了培養(yǎng)一個軟件工作者所應(yīng)具備的科學(xué)工作的方法和作風(fēng)，也應(yīng)遵循以下五個步驟來完成實(shí)驗(yàn)題目：1）問題分析和任務(wù)定義在進(jìn)行設(shè)計(jì)之前，首先應(yīng)該充分地分析和理解問題，明確問題要求做什么，限制條件是什么。本步驟強(qiáng)調(diào)的是做什么，而不是怎么做。對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對所需完成的任務(wù)作出明確的回答。例如：輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值的范圍及輸出的形式；若是會話式的輸入，則結(jié)束標(biāo)志是什么，是否接受非法的輸入，對非法輸入的回答方式是什么等。還應(yīng)該為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非

6、法形式的輸入數(shù)據(jù)。2）邏輯設(shè)計(jì)和詳細(xì)設(shè)計(jì)在設(shè)計(jì)這一步驟中需分邏輯設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步實(shí)現(xiàn)。邏輯設(shè)計(jì)指的是，對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型；詳細(xì)設(shè)計(jì)則為定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。作為邏輯設(shè)計(jì)的結(jié)果，應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作

7、作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。在求精的過程中，應(yīng)盡量避免陷入語言細(xì)節(jié)，不必過早表述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。3）編碼實(shí)現(xiàn)和靜態(tài)檢查編碼是把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。如果基于詳細(xì)設(shè)計(jì)的偽碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機(jī)準(zhǔn)備之后進(jìn)行，即在上機(jī)調(diào)試之前直接用鍵盤輸入。然而，不管你是否寫出編碼的程序，在上機(jī)之前，認(rèn)真的靜態(tài)檢查是必不可少的。靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序(通常應(yīng)先分模塊檢查)；二是通過對程序深入全面地理解程序邏輯，在這個過程中再加入一些注解和斷言。如

8、果程序中邏輯概念清楚，后者將比前者有效。4）上機(jī)準(zhǔn)備和上機(jī)調(diào)試上機(jī)準(zhǔn)備包括以下幾個方面：(1)注意同一高級語言文本之間的差別。(2)熟悉機(jī)器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進(jìn)行上機(jī)的基本活動。(3)掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計(jì)測試數(shù)據(jù)并手工得出正確結(jié)果。應(yīng)該能夠熟練運(yùn)用高級語言的程序調(diào)試器DBBUG調(diào)試程序。(4)上機(jī)調(diào)試程序時要帶一本高級語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向上，即先調(diào)試低層函數(shù)。在調(diào)試過程中可以不斷借助DEBUG的各種功能，提高調(diào)試效率。調(diào)試中遇到的各種異?，F(xiàn)象往往是預(yù)料不到的，此時應(yīng)動手確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)

9、試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。5）總結(jié)和整理實(shí)驗(yàn)報告：按照實(shí)驗(yàn)報告規(guī)范撰寫實(shí)驗(yàn)報告。3、實(shí)驗(yàn)報告規(guī)范實(shí)驗(yàn)報告的開頭應(yīng)首先包括如下成績單表格，并填寫班級、學(xué)號、姓名、題目等信息。在成績單之后另起一新頁，開始你的實(shí)驗(yàn)報告主體。華 南 農(nóng) 業(yè) 大 學(xué) 信 息（軟 件） 學(xué) 院操作系統(tǒng)綜合性、設(shè)計(jì)性實(shí)驗(yàn)成績單開設(shè)時間： 學(xué)年第 學(xué)期專業(yè)班級學(xué)號姓名實(shí) 驗(yàn) 題 目（把你選的題目都寫在這里）自 我 評 價（即 實(shí)驗(yàn)體會和心得部分）教 師 評 語評價指標(biāo)：l 題目要求完成情況 優(yōu) 良 中 差 l 對算法原理的理解程度 優(yōu) 良 中 差 l 程序設(shè)計(jì)水平 優(yōu) 良 中 差

10、 l 實(shí)驗(yàn)報告結(jié)構(gòu)清晰 優(yōu) 良 中 差 l 流程圖及內(nèi)容表述清楚 優(yōu) 良 中 差 l 實(shí)驗(yàn)總結(jié)和分析詳盡 優(yōu) 良 中 差 成績教師簽名然后，在實(shí)驗(yàn)報告主體中包括以下六個內(nèi)容：一、需求分析 明確陳述說明程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么，主要包括：(1)輸入的形式和輸入值的范圍；(2)輸出的形式；(3)程序所能達(dá)到的功能；(4)測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。二、概要設(shè)計(jì)說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。三、詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽碼算法；對主程序和其他模塊也都需

11、要寫出偽碼算法(偽碼算法達(dá)到的詳細(xì)程度應(yīng)能夠按照偽碼算法在計(jì)算機(jī)鍵盤上直接輸入高級程序設(shè)計(jì)語言程序)；畫出函數(shù)的調(diào)用關(guān)系圖。四、調(diào)試分析內(nèi)容包括：(1) 調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的討論和分析；(2) 算法的時間復(fù)雜性(包括基本操作和其他算法的時間復(fù)雜性的分析)和改進(jìn)設(shè)想；(3) 設(shè)計(jì)過程的經(jīng)驗(yàn)和體會；(4) 實(shí)現(xiàn)過程中出現(xiàn)的主要問題及解決方法。五、用戶使用說明說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。六、測試與運(yùn)行結(jié)果 列出你的測試結(jié)果和運(yùn)行情況（即運(yùn)行時的關(guān)鍵畫面），包括輸入和輸出。這里的測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多于需求分析中所列。值得注意的是，實(shí)驗(yàn)報告

12、的各種文檔資料，要在程序開發(fā)的過程中逐漸充實(shí)形成，而不是最后補(bǔ)寫。必要時可在實(shí)驗(yàn)報告中附部分關(guān)鍵源代碼，但不需要附全部源代碼。4、實(shí)驗(yàn)考核1）考核點(diǎn)：編程(Programming: 50分)、測試分析(Testing & Analyzing: 20分)、實(shí)驗(yàn)報告(Documentation: 30分)；2）上交內(nèi)容： 源代碼及可執(zhí)行程序（電子版）；實(shí)驗(yàn)報告（電子版）； 上交時間與地點(diǎn)由任課教師指定。請各班學(xué)習(xí)委員注意：上交電子版文件時每位同學(xué)的內(nèi)容各自放在單獨(dú)的一個文件夾中，文件夾的名字格式形如：200831000101陳陳，即只包含學(xué)號姓名，且學(xué)號和姓名之間沒有任何空格及其它符號。第

13、二部分 實(shí)驗(yàn)內(nèi)容在以下實(shí)驗(yàn)中，經(jīng)常需要產(chǎn)生隨機(jī)數(shù)，涉及到以下兩個函數(shù)（以C為例）：void srand(int a) 根據(jù)a產(chǎn)生一個隨機(jī)種子。為使隨后產(chǎn)生的隨機(jī)數(shù)不至于相同，常用系統(tǒng)時間作為a。但由于系統(tǒng)運(yùn)行速度很快，所以兩次產(chǎn)生隨機(jī)數(shù)應(yīng)間隔一小段時間；int rand() 根據(jù)種子，返回一個隨機(jī)數(shù)。例如：srand(unsigned)time(NULL); randnum=rand()%10+1; 產(chǎn)生110的隨機(jī)整數(shù)。另外，實(shí)驗(yàn)提示內(nèi)容只是一種思路，但不局限于此。實(shí)現(xiàn)時可根據(jù)具體情況進(jìn)行調(diào)整或修改。實(shí)驗(yàn)一 進(jìn)程同步互斥不死鎖的哲學(xué)家問題一、實(shí)驗(yàn)?zāi)康? 掌握基本的同步與互斥算法，理解生產(chǎn)者消

14、費(fèi)者模型。2 掌握進(jìn)程并發(fā)執(zhí)行的原理，及其所引起的同步、互斥問題的方法。二、實(shí)驗(yàn)內(nèi)容及要求自己編寫P、V操作和信號量的模擬程序，然后用它們解決不死鎖的哲學(xué)家問題，并把哲學(xué)家們的活動過程用文字或可視化表示出來。（提示：首先設(shè)置一個“PCB”數(shù)組或隊(duì)列，其中一個字段表示“阻塞原因兼阻塞標(biāo)志”，本實(shí)驗(yàn)中，該數(shù)組有5個元素表示5個哲學(xué)家即可。它們隨機(jī)提出申請以及進(jìn)行“思考”“吃”的行為。再設(shè)一個“筷子”數(shù)組。還需要設(shè)置哪些數(shù)據(jù)結(jié)構(gòu)以及需要哪些字段自己考慮。示例圖如下，但不要求做得那么美觀，尤其是在TC中）實(shí)驗(yàn)二 進(jìn)程同步互斥讀者寫者問題一、實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)現(xiàn)經(jīng)典的讀者寫者問題，鞏固對線程及其同步機(jī)制的學(xué)

15、習(xí)效果，加深對相關(guān)基本概念的理解，并學(xué)習(xí)如何將基本原理和實(shí)際設(shè)計(jì)有機(jī)的結(jié)合。二、實(shí)驗(yàn)內(nèi)容 在Windows 2000/XP環(huán)境下，使用多線程和信號量機(jī)制實(shí)現(xiàn)讀者優(yōu)先或?qū)懻邇?yōu)先的讀者-寫者問題，每個線程代表一個讀者或一個寫者。三、提示與講解創(chuàng)建一個控制臺進(jìn)程。此進(jìn)程包含n個線程。用這n個線程來表示n個讀者或?qū)懻摺Ｃ總€線程按相應(yīng)測試數(shù)據(jù)文件的要求進(jìn)行讀寫操作。 讀者-寫者問題的讀寫操作限制(讀者優(yōu)先和寫者優(yōu)先均適用)： 1)寫-寫互斥，即不能有兩個寫者同時進(jìn)行寫操作。 2)讀-寫互斥，即不能同時有一個線程在讀，而另一個線程在寫。 3)讀-讀允許，即可以有一個或多個讀者在讀。 讀者優(yōu)先的附加限制：如

16、果一個讀者申請進(jìn)行讀操作時已有另一個讀者正在進(jìn)行讀操作，則該讀者可直接開始讀操作。但任何寫者必須等到?jīng)]有讀者時才能開始寫操作。 寫者優(yōu)先的附加限制：如果一個讀者申請進(jìn)行讀操作時已有另一寫者在等待訪問共享資源，則該讀者必須等到?jīng)]有寫者處于等待狀態(tài)后才能開始讀操作。運(yùn)行結(jié)果顯示要求：要求在每個線程創(chuàng)建、發(fā)出讀寫操作申請、開始讀寫操作和結(jié)束讀寫操作時分別顯示一行提示信息，以確定所有處理都遵守相應(yīng)的讀寫操作限制。測試數(shù)據(jù)文件包括n行測試數(shù)據(jù)，分別描述創(chuàng)建的n個線程是讀者還是寫者，以及讀寫操作的開始時間和持續(xù)時間。每行測試數(shù)據(jù)包括四個字段，各個字段間用空格分隔。第一字段為一個正整數(shù)，表示線程序號。第二字

17、段表示相應(yīng)線程角色，R表示讀者，w表示寫者。第三字段為一個正數(shù)，表示讀寫操作的開始時間：線程創(chuàng)建后，延遲相應(yīng)時間(單位為秒)后發(fā)出對共享資源的讀寫申請。第四字段為一個正數(shù)，表示讀寫操作的持續(xù)時間。當(dāng)線程讀寫申請成功后，開始對共享資源的讀寫操作，該操作持續(xù)相應(yīng)時間后結(jié)束，并釋放共享資源。下面是一個測試數(shù)據(jù)文件的例子：1 R 3 52 W 4 53 R 5 24 R 6 55 W 5 3讀者優(yōu)先或?qū)懻邇?yōu)先實(shí)現(xiàn)其中一個即達(dá)到基本要求，但有能力的同學(xué)可以實(shí)現(xiàn)一個通用的讀者-寫者問題（包含讀者優(yōu)先和寫者優(yōu)先），通過不同選項(xiàng)來運(yùn)行讀者優(yōu)先或?qū)懻邇?yōu)先?？赡苡玫降腁PI函數(shù)：CreateThread()在調(diào)用

18、進(jìn)程的地址空間上創(chuàng)建一個線程ExitThread()用于結(jié)束當(dāng)前線程Sleep()可在指定的時間內(nèi)掛起當(dāng)前線程CreateMutex()創(chuàng)建一個互斥對象，返回對象句柄OpenMutex()打開并返回一個已存在的互斥對象句柄，用于后續(xù)訪問ReleaseMutex()釋放對互斥對象的占用，使之成為可用WaitForSingleObject()可在指定的時間內(nèi)等待指定對象為可用狀態(tài)InitializeCriticalSection()初始化臨界區(qū)對象EnterCriticalSection()等待指定臨界區(qū)對象的所有權(quán)LeaveCriticalSection()釋放指定臨界區(qū)對象的所有權(quán)Create

19、Semaphore()創(chuàng)建一個信號量對象ReleaseSemaphore()將所指信號量加上指定大小的一個量實(shí)驗(yàn)三 頁式虛擬存儲管理中地址轉(zhuǎn)換和缺頁中斷一、實(shí)驗(yàn)?zāi)康?深入了解頁式存儲管理如何實(shí)現(xiàn)地址轉(zhuǎn)換；2進(jìn)一步認(rèn)識頁式虛擬存儲管理中如何處理缺頁中斷。二、實(shí)驗(yàn)內(nèi)容及要求編寫程序完成頁式虛擬存儲管理中地址轉(zhuǎn)換過程和模擬缺頁中斷的處理。實(shí)驗(yàn)具體包括：首先對給定的地址進(jìn)行地址轉(zhuǎn)換工作，若發(fā)生缺頁則進(jìn)行缺頁中斷處理，然后再進(jìn)行地址轉(zhuǎn)換；最后編寫主函數(shù)對所作工作進(jìn)行測試。假定主存64KB，每個主存塊1024字節(jié)，作業(yè)最大支持到64KB，系統(tǒng)中每個作業(yè)分得主存塊4塊。三、提示與講解頁式存儲管理中地址轉(zhuǎn)換過

20、程很簡單，假定主存塊的大小為2n字節(jié)，主存大小為2m字節(jié)，邏輯地址m位，則進(jìn)行地址轉(zhuǎn)換時，首先從邏輯地址中的高m-n位中取得頁號，然后根據(jù)頁號查頁表，得到塊號，并將塊號放入物理地址的高m-n位，最后從邏輯地址中取得第n位放入物理地址的低n位就得到了物理地址。地址轉(zhuǎn)換是由硬件完成的，實(shí)驗(yàn)中使用軟件程序模擬地址轉(zhuǎn)換過程。實(shí)驗(yàn)中假定主存64KB，每個主存塊1024字節(jié)，即n=10，m=16，物理地址中塊號6位。塊內(nèi)地址10位；作業(yè)最大64KB，即m=16，邏輯地址中頁號6位，頁內(nèi)地址10位。在頁式虛擬存儲管理方式中，作業(yè)信息作為副本放在磁盤上，作業(yè)執(zhí)行時僅把作業(yè)信息的部分頁面裝入主存儲器，作業(yè)執(zhí)行時

21、若訪問的頁面在主存中，則按上述方式進(jìn)行地址轉(zhuǎn)換，若訪問的頁面不在主存中，則產(chǎn)生一個缺頁中斷，由操作系統(tǒng)把當(dāng)前所需的頁面裝入主存儲器后，再次執(zhí)行時才可以按上述方法進(jìn)行地址轉(zhuǎn)換。頁式虛擬存儲管理方式中頁表除頁號和該頁對應(yīng)的主存塊號外，至少還要包括存在標(biāo)志（該頁是否在主存），磁盤位置（該頁的副本在磁盤上的位置）和修改標(biāo)志（該頁是否被修改過）。在實(shí)驗(yàn)中頁表可用數(shù)組模擬，頁表數(shù)據(jù)結(jié)構(gòu)的定義為：#define n 32 /實(shí)驗(yàn)中假定的頁表長度struct int lnumber; /頁號 int flag; /表示該頁是否在主存，“1”表示在主存，“0”表示不在主存 int pnumber; /該頁所在主

22、存塊的塊號 int write; /該頁是否被修改過，“1”表示修改過，“0”表示沒有修改過 int dnumber; /該頁存放在磁盤上的位置，即磁盤塊號pagen; /頁表定義實(shí)際系統(tǒng)中的缺頁處理過程簡單闡述如下：（1） 根據(jù)當(dāng)前執(zhí)行指令中邏輯地址的頁號查頁表，判斷該頁是否在主存中，若該頁標(biāo)志為“0”，形成缺頁中斷。中斷裝置通過交換PSW讓操作系統(tǒng)的中斷處理程序占用處理器；（2） 操作系統(tǒng)處理缺頁中斷的方法就是查主存分配表，找一個空閑主存塊；若無空閑塊，查頁表，選擇一個已在主存的頁面，把它暫時調(diào)出主存。若在執(zhí)行過程中該頁被修改過，則需將該頁信息寫回磁盤，否則不必寫回。（3） 找出該頁的磁盤

23、位置，啟動磁盤讀出該頁信息，把磁盤上讀出的信息裝入第2步找到的主存塊，修改頁表中該頁的標(biāo)志為“1”；（4） 由于產(chǎn)生缺頁中斷的那條指令沒有執(zhí)行完，所以頁面裝入后應(yīng)重新執(zhí)行被中斷的指令。當(dāng)重新執(zhí)行該指令時，由于要訪問的頁面已在主存中，所以可正常執(zhí)行。關(guān)于第2步查找裝入新頁面的主存塊處理方式，不同系統(tǒng)采用的策略可能有所不同，這里采用局部置換算法，就是每個作業(yè)分得一定的主存塊，只能在分得的主存塊內(nèi)查找空閑塊，若無空閑主存塊，則從該作業(yè)中選擇一個頁面淘汰出主存。使用局部置換算法時，存在這樣一個問題：就是在分配給作業(yè)主存空間時，裝入哪些頁？有的系統(tǒng)采取不裝入任何一頁，當(dāng)執(zhí)行過程中需要時才將其調(diào)入。有的系

24、統(tǒng)采用頁面預(yù)置的方法，就是估計(jì)可能某些頁面會先用到，在分配主存塊后將這些頁面裝入。實(shí)驗(yàn)中，采用第二種方法，分配主存空間時將前幾頁調(diào)入主存，假定系統(tǒng)中每個作業(yè)分得主存塊m（m=4）塊，則將第0m-1頁裝入主存。因?yàn)槭悄M硬件工作，所以實(shí)驗(yàn)中如果訪問的頁不在主存時，則輸出該頁頁號，表示硬件產(chǎn)生缺頁中斷，然后直接去缺頁中斷處理；由于采用頁面預(yù)置方法，在給定的主存塊中一定無空閑塊，只能淘汰已在主存中的一頁；沒有啟動磁盤的工作，淘汰的頁需要寫回磁盤時，用輸出頁號表示，調(diào)入新的一頁時，將該頁在頁表中的存在標(biāo)志置為“1”，輸出頁號表示將該頁調(diào)入主存。主存中無空閑塊時，為裝入一個頁面，必須按某種算法從已在主存

25、的頁中選擇一頁，將它暫時調(diào)出主存，讓出主存空間，用來存放需裝入的頁面，這個工作稱為“頁面置換”。如何選擇調(diào)出的頁是很重要的，常用的頁面置換算法有先進(jìn)先出算法（FIFO），最近最少使用算法（LRU）等。實(shí)驗(yàn)中使用先進(jìn)先出算法。先進(jìn)先出算法總是選擇駐留在主存時間最長的一頁調(diào)出。先進(jìn)先出算法簡單，易實(shí)現(xiàn)?？梢园言谥鞔娴捻摰捻撎柊催M(jìn)入主存的先后次序排成隊(duì)列，每次總是調(diào)出隊(duì)首的頁，當(dāng)裝入一個新頁后，把新頁的頁號排入隊(duì)尾。實(shí)驗(yàn)中，用一個數(shù)組存放頁號的隊(duì)列。假定分配給作業(yè)的主存塊數(shù)為m，數(shù)組可由m個元素組成，p0，p1pm-1；隊(duì)首指針head；采用頁面預(yù)置的方法，頁號隊(duì)列的長度總是m，tail=(head

26、+1)%m。因此可以使用一個指針，只用head即可。在裝入一個新的頁時，裝入頁和淘汰頁同時執(zhí)行，當(dāng)裝入一個新的頁時，將其頁號存入數(shù)組：淘汰頁的頁號=phead；phead=新裝入頁的頁號；head=(head+1)%m；實(shí)驗(yàn)執(zhí)行一條指令時，不模擬指令的執(zhí)行，只是考慮指令執(zhí)行是否修改頁面，若修改頁面，則將該頁的頁表中修改標(biāo)志位置“1”，然后輸出轉(zhuǎn)換后的物理地址，并輸出物理地址來表示一條指令執(zhí)行完成；如果訪問的頁不在主存時，則產(chǎn)生缺頁中斷，然后直接轉(zhuǎn)去缺頁中斷處理，最后模擬中斷返回，就是返回重新進(jìn)行地址轉(zhuǎn)換。因?yàn)闆]有實(shí)際主存，所以在模擬程序中首先隨機(jī)生成頁表信息，創(chuàng)建該作業(yè)的頁表；然后循環(huán)執(zhí)行假定

27、的指令（僅考慮指令中操作數(shù)的邏輯地址和“讀/寫操作”即可，可事先準(zhǔn)備好100條左右），觀察地址轉(zhuǎn)換情況。實(shí)驗(yàn)四 單處理器系統(tǒng)的時間片輪轉(zhuǎn)進(jìn)程調(diào)度一、實(shí)驗(yàn)?zāi)康?. 加深對進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別。2. 深入了解系統(tǒng)如何組織進(jìn)程、創(chuàng)建進(jìn)程。3. 進(jìn)一步認(rèn)識如何實(shí)現(xiàn)處理器調(diào)度。二、實(shí)驗(yàn)內(nèi)容編寫程序完成單處理器系統(tǒng)中的進(jìn)程調(diào)度，要求采用時間片輪轉(zhuǎn)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定進(jìn)程控制塊的內(nèi)容，進(jìn)程控制塊的組成方式；然后完成進(jìn)程創(chuàng)建原語和進(jìn)程調(diào)度原語；最后編寫主函數(shù)對所作工作進(jìn)行測試。模擬程序只對你所設(shè)置的“虛擬PCB”進(jìn)行相應(yīng)的調(diào)度模擬操作，即每發(fā)生“調(diào)度”時，顯示出當(dāng)前運(yùn)行進(jìn)程的“進(jìn)程

28、標(biāo)識符”、“優(yōu)先數(shù)”、“剩余運(yùn)行時間”以及調(diào)度一次后進(jìn)程隊(duì)列的變化等，而不需要對系統(tǒng)中真正的PCB等數(shù)據(jù)進(jìn)行修改。三、提示與講解本實(shí)驗(yàn)和實(shí)驗(yàn)“單處理器系統(tǒng)的優(yōu)先數(shù)進(jìn)程調(diào)度”的提示是互通的，區(qū)別就是要實(shí)現(xiàn)的進(jìn)程調(diào)度算法不同。這個實(shí)驗(yàn)主要考慮三個問題：如何組織進(jìn)程、如何創(chuàng)建進(jìn)程和如何實(shí)現(xiàn)處理器調(diào)度?？紤]如何組織進(jìn)程，首先要設(shè)定進(jìn)程控制塊的內(nèi)容。進(jìn)程控制塊PCB記錄各個進(jìn)程執(zhí)行時的情況。不同的操作系統(tǒng)，進(jìn)程控制塊記錄的信息內(nèi)容不一樣。操作系統(tǒng)功能越強(qiáng)，軟件也越龐大，進(jìn)程控制塊的內(nèi)容也就越多。這里的實(shí)驗(yàn)只使用必不可少的信息。一般操作系統(tǒng)中，無論進(jìn)程控制塊中信息量多少，信息都可以大致分為以下四類：（1）

29、 標(biāo)識信息每個進(jìn)程都要有一個唯一的標(biāo)識符，用來標(biāo)識進(jìn)程的存在和區(qū)別于其他進(jìn)程。這個標(biāo)識符是必不可少的，可以用符號或編號實(shí)現(xiàn)，它必須是操作系統(tǒng)分配的。例如采用編號方式，也就是為每個進(jìn)程依次分配一個不相同的正整數(shù)。（2） 說明信息用于記錄進(jìn)程的基本情況，例如進(jìn)程的狀態(tài)、等待原因、進(jìn)程程序存放位置、進(jìn)程數(shù)據(jù)存放位置等等。實(shí)驗(yàn)中，因?yàn)檫M(jìn)程沒有數(shù)據(jù)和程序，僅使用模擬的進(jìn)程控制塊，所以這部分內(nèi)容僅包含進(jìn)程狀態(tài)。進(jìn)程狀態(tài)可假設(shè)只有就緒、運(yùn)行、終止三種。如果要設(shè)置“等待（阻塞）”狀態(tài)，需要隨機(jī)生成“阻塞時間”，阻塞時間到時轉(zhuǎn)為就緒態(tài)。（3） 現(xiàn)場信息現(xiàn)場信息記錄各個寄存器的內(nèi)容。當(dāng)進(jìn)程由于某種原因讓出處理器時

30、，需要將現(xiàn)場信息記錄在進(jìn)程控制塊中，當(dāng)進(jìn)行進(jìn)程調(diào)度時，從選中進(jìn)程的進(jìn)程控制塊中讀取現(xiàn)場信息進(jìn)行現(xiàn)場恢復(fù)?，F(xiàn)場信息就是處理器的相關(guān)寄存器內(nèi)容，包括通用寄存器、程序計(jì)數(shù)器和程序狀態(tài)字寄存器等。在實(shí)驗(yàn)中，可選取幾個寄存器作為代表。用大寫的全局變量AX、BX、CX、DX模擬通用寄存器，大寫的全局變量PC模擬程序計(jì)數(shù)器，大寫的全局變量PSW模擬程序狀態(tài)字寄存器。（4） 管理信息管理信息記錄進(jìn)程管理和調(diào)度的信息。例如進(jìn)程優(yōu)先數(shù)、進(jìn)程隊(duì)列指針等。另外為了模擬進(jìn)程的不同運(yùn)行時間，再添加一個“剩余運(yùn)行時間”屬性。因此可將進(jìn)程控制塊結(jié)構(gòu)定義如下：struct pcb int name; /進(jìn)程標(biāo)識符 int st

31、atus; /進(jìn)程狀態(tài) int ax,bx,cx,dx; /進(jìn)程現(xiàn)場信息，通用寄存器內(nèi)容 int pc; /進(jìn)程現(xiàn)場信息，程序計(jì)數(shù)器內(nèi)容 int psw; /進(jìn)程現(xiàn)場信息，程序狀態(tài)字寄存器內(nèi)容 int pri; /進(jìn)程優(yōu)先數(shù) int time; /剩余運(yùn)行時間，以時間片為單位，當(dāng)減至0時該進(jìn)程終止 int next; /下一個進(jìn)程控制塊的位置確定進(jìn)程控制塊內(nèi)容后，要考慮的就是如何將進(jìn)程控制塊組織在一起。多道程序設(shè)計(jì)系統(tǒng)中，往往同時創(chuàng)建多個進(jìn)程。在單處理器的情況下，每次只能有一個進(jìn)程處于運(yùn)行態(tài)，其它的進(jìn)程處于就緒狀態(tài)或者等待狀態(tài)。為了便于管理，通常把處于相同狀態(tài)的進(jìn)程的進(jìn)程控制塊鏈接在一起。單處

32、理器系統(tǒng)中，正在運(yùn)行的進(jìn)程只有一個，因此，單處理器系統(tǒng)中進(jìn)程控制塊分成一個正在運(yùn)行進(jìn)程的進(jìn)程控制塊，就緒進(jìn)程的進(jìn)程控制塊組成的就緒隊(duì)列，和等待進(jìn)程的控制塊組成的等待隊(duì)列。由于實(shí)驗(yàn)?zāi)M的是進(jìn)程調(diào)度，沒有對等待隊(duì)列的操作，所以實(shí)驗(yàn)中只有一個指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針和一個就緒進(jìn)程的進(jìn)程控制塊隊(duì)列指針。操作系統(tǒng)實(shí)現(xiàn)中，系統(tǒng)往往在主存中劃分出一個連續(xù)的專門區(qū)域存放系統(tǒng)的進(jìn)程控制塊，實(shí)驗(yàn)中應(yīng)該用數(shù)組模擬這個專門的進(jìn)程控制塊區(qū)域，定義如下：#define n 10 /假定系統(tǒng)允許進(jìn)程個數(shù)為nstruct pcb pcbarean; /模擬進(jìn)程控制塊區(qū)域的數(shù)組這樣，進(jìn)程控制塊的鏈表實(shí)際上是數(shù)據(jù)結(jié)構(gòu)中使

33、用的靜態(tài)鏈表。進(jìn)程控制塊的鏈接方式可以采用單向和雙向鏈表，實(shí)驗(yàn)中，進(jìn)程控制塊隊(duì)列采用單向不循環(huán)靜態(tài)鏈表。為了管理空閑進(jìn)程控制塊，還應(yīng)該將空閑控制塊鏈接成一個隊(duì)列。實(shí)驗(yàn)中采用時間片輪轉(zhuǎn)調(diào)度算法，這種算法是將進(jìn)程控制塊按照進(jìn)入就緒隊(duì)列的先后次序排成隊(duì)列。關(guān)于就緒隊(duì)列的操作就是從隊(duì)頭摘下一個進(jìn)程控制塊和從隊(duì)尾掛入一個進(jìn)程控制塊。因此為就緒隊(duì)列定義兩個指針，一個頭指針，指向就緒隊(duì)列的第一個進(jìn)程控制塊；一個尾指針，指向就緒隊(duì)列的最后一個進(jìn)程控制塊。實(shí)驗(yàn)中指向運(yùn)行進(jìn)程的進(jìn)程控制塊指針、就緒隊(duì)列指針和空閑進(jìn)程控制塊隊(duì)列指針定義如下：int run; /定義指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊的指針struct in

34、t head; int tail; /定義指向就緒隊(duì)列的頭指針head和尾指針tailready;int pfree; /定義指向空閑進(jìn)程控制塊隊(duì)列的指針以上是如何組織進(jìn)程，下面考慮如何創(chuàng)建進(jìn)程。進(jìn)程創(chuàng)建是一個原語，因此在實(shí)驗(yàn)中應(yīng)該用一個函數(shù)實(shí)現(xiàn)，進(jìn)程創(chuàng)建的過程應(yīng)該包括：（1） 申請進(jìn)程控制塊進(jìn)程控制塊的數(shù)量是有限的，如果沒有空閑進(jìn)程控制塊，則進(jìn)程不能創(chuàng)建；只有申請成功才可以執(zhí)行第二步。（2） 申請資源除了進(jìn)程控制塊外，還需要有必要的資源才能創(chuàng)建進(jìn)程，如果申請資源不成功，則不能創(chuàng)建進(jìn)程，并且歸還已申請的進(jìn)程控制塊；如果申請成功，則執(zhí)行第三步，實(shí)驗(yàn)無法申請資源，所以模擬程序可忽略申請資源這一步。

35、（3） 填寫進(jìn)程控制塊將該進(jìn)程信息寫入進(jìn)程控制塊內(nèi)。進(jìn)程標(biāo)識符應(yīng)該隨機(jī)生成并且是唯一，優(yōu)先數(shù)和剩余運(yùn)行時間隨機(jī)生成，每個進(jìn)程控制現(xiàn)場信息中的寄存器內(nèi)容由于沒有具體數(shù)據(jù)而暫時為空，剛剛創(chuàng)建的進(jìn)程應(yīng)該為就緒態(tài)，然后轉(zhuǎn)去執(zhí)行第四步。（4） 掛入就緒隊(duì)列如果原來就緒隊(duì)列不為空，則將該進(jìn)程掛入就緒隊(duì)列尾部，并修改就緒隊(duì)列尾部指針；如果原來就緒隊(duì)列為空，則將就緒隊(duì)列的頭指針、尾指針均指向該進(jìn)程控制塊，進(jìn)程創(chuàng)建完成。多道程序設(shè)計(jì)的系統(tǒng)中，處于就緒狀態(tài)的進(jìn)程往往是多個，它們都要求占用處理器，可是單處理器系統(tǒng)的處理器只有一個，進(jìn)程調(diào)度就是解決這個處理器競爭問題的。進(jìn)程調(diào)度的任務(wù)就是按照某種算法從就緒進(jìn)程隊(duì)列中選

36、擇一個進(jìn)程，讓它占有處理器。因此進(jìn)程調(diào)度程序就應(yīng)該包括兩部分，一部分是在進(jìn)程就緒隊(duì)列中選擇一個進(jìn)程，并將其進(jìn)程控制塊從進(jìn)程就緒隊(duì)列中摘下來，另一部分工作就是分配處理器給選中的進(jìn)程，也就是將指向正在運(yùn)行進(jìn)程的進(jìn)程控制塊指針指向該進(jìn)程的進(jìn)程控制塊，并將該進(jìn)程的進(jìn)程控制塊信息寫入處理器的各個寄存器中。提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運(yùn)行時，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作。本實(shí)驗(yàn)中采用時間片輪轉(zhuǎn)調(diào)度算法（此時優(yōu)先數(shù)實(shí)際無用）。時間片輪轉(zhuǎn)調(diào)度算法讓就緒進(jìn)程按就緒的先后次序排成隊(duì)列，每次總是選擇就緒隊(duì)列中的第一個進(jìn)程占有處理器，但是規(guī)

37、定只能使用一個“時間片”。時間片就是規(guī)定進(jìn)程一次使用處理器的最長時間。實(shí)驗(yàn)中采用每個進(jìn)程都使用相同的不變時間片。每被調(diào)度1次，將其 剩余運(yùn)行時間1。進(jìn)程運(yùn)行一次后，若剩余運(yùn)行時間不等于0，則再將它加入就緒隊(duì)列尾；若剩余運(yùn)行時間等于0，則把它的狀態(tài)修改成“終止”，且退出隊(duì)列。若就緒進(jìn)程隊(duì)列不為空，則重復(fù)調(diào)度，直到所有進(jìn)程都“終止”。最好能動態(tài)地隨機(jī)生成新進(jìn)程添加到就緒隊(duì)列中。完成上述功能后，編寫主函數(shù)進(jìn)行測試：首先建立一個就緒隊(duì)列，隨機(jī)生成信息建立若干個進(jìn)程；然后進(jìn)行進(jìn)程調(diào)度；將正在運(yùn)行進(jìn)程指針指向的進(jìn)程控制塊的內(nèi)容以及調(diào)度一次后進(jìn)程隊(duì)列的現(xiàn)狀輸出，查看結(jié)果。有能力的同學(xué)最好能將本實(shí)驗(yàn)和實(shí)驗(yàn)“單

38、處理器系統(tǒng)的優(yōu)先數(shù)進(jìn)程調(diào)度”結(jié)合起來編寫一個通用的進(jìn)程調(diào)度程序，通過優(yōu)先數(shù)的不同設(shè)置方法來選擇運(yùn)行不同的調(diào)度算法。實(shí)驗(yàn)五 單處理器系統(tǒng)的優(yōu)先數(shù)進(jìn)程調(diào)度一、實(shí)驗(yàn)?zāi)康?. 加深對進(jìn)程概念的理解，明確進(jìn)程和程序的區(qū)別。2. 深入了解系統(tǒng)如何組織進(jìn)程、創(chuàng)建進(jìn)程。3. 進(jìn)一步認(rèn)識如何實(shí)現(xiàn)處理器調(diào)度。二、實(shí)驗(yàn)內(nèi)容編寫程序完成單處理器系統(tǒng)中的進(jìn)程調(diào)度，要求采用優(yōu)先數(shù)調(diào)度算法。實(shí)驗(yàn)具體包括：首先確定進(jìn)程控制塊的內(nèi)容，進(jìn)程控制塊的組成方式；然后完成進(jìn)程創(chuàng)建原語和進(jìn)程調(diào)度原語；最后編寫主函數(shù)對所作工作進(jìn)行測試。模擬程序只對你所設(shè)置的“虛擬PCB”進(jìn)行相應(yīng)的調(diào)度模擬操作，即每發(fā)生“調(diào)度”時，顯示出當(dāng)前運(yùn)行進(jìn)程的“進(jìn)

39、程標(biāo)識符”、“優(yōu)先數(shù)”、“剩余運(yùn)行時間”等，而不需要對系統(tǒng)中真正的PCB等數(shù)據(jù)進(jìn)行修改。三、提示與講解本實(shí)驗(yàn)和實(shí)驗(yàn)“單處理器系統(tǒng)的時間片輪轉(zhuǎn)進(jìn)程調(diào)度”的提示是互通的，區(qū)別就是要實(shí)現(xiàn)的進(jìn)程調(diào)度算法不同。關(guān)于“如何組織進(jìn)程、如何創(chuàng)建進(jìn)程”部分可參見實(shí)驗(yàn)“單處理器系統(tǒng)的時間片輪轉(zhuǎn)進(jìn)程調(diào)度”的提示。創(chuàng)建進(jìn)程時“優(yōu)先數(shù)”和“剩余運(yùn)行時間”一般是不相等的。本實(shí)驗(yàn)中采用優(yōu)先數(shù)調(diào)度算法。處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一次優(yōu)先數(shù)就減“1”，即被調(diào)度時執(zhí)行：優(yōu)先數(shù)1剩余運(yùn)行時間1來模擬進(jìn)程的一次運(yùn)行。進(jìn)程運(yùn)行一次后，若剩余運(yùn)行時間不等于0，則再將它加入隊(duì)列（按優(yōu)先數(shù)大小插入，且

40、置隊(duì)首標(biāo)志）；若剩余運(yùn)行時間等于0，則把它的狀態(tài)修改成“終止”，且退出隊(duì)列。若就緒進(jìn)程隊(duì)列不為空，則重復(fù)調(diào)度，直到所有進(jìn)程都“終止”。最好能動態(tài)地隨機(jī)生成新進(jìn)程添加到就緒隊(duì)列中。有能力的同學(xué)最好能將本實(shí)驗(yàn)和實(shí)驗(yàn)“單處理器系統(tǒng)的時間片輪轉(zhuǎn)進(jìn)程調(diào)度”結(jié)合起來編寫一個通用的進(jìn)程調(diào)度程序，通過優(yōu)先數(shù)的不同設(shè)置方法來選擇運(yùn)行不同的調(diào)度算法。實(shí)驗(yàn)六 內(nèi)存分配和回收三種適應(yīng)法一、實(shí)驗(yàn)?zāi)康牧私庥脩舫绦蚍峙鋬?nèi)存以及回收所用內(nèi)存的過程，加深對操作系統(tǒng)存儲管理的理解。二、實(shí)驗(yàn)內(nèi)容采用首次適應(yīng)法、最佳適應(yīng)法或最差適應(yīng)法，編寫一內(nèi)存分配和回收模擬程序。三、提示與講解由于這個實(shí)驗(yàn)的重點(diǎn)在于內(nèi)存分配，所以不考慮與某內(nèi)存區(qū)相

41、關(guān)的進(jìn)程情況?？勺兎謪^(qū)方式是按作業(yè)需要的內(nèi)存空間大小來分割分區(qū)的。當(dāng)要裝入一個作業(yè)時，根據(jù)作業(yè)需要的內(nèi)存量查看是否有足夠的空閑空間，若有，則按需要量分割一個分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，內(nèi)存空間被分成許多個分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：05k10k14k26k32k128k操作系統(tǒng)作業(yè)1作業(yè)3空閑區(qū)作業(yè)2空閑區(qū)(1) 為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，格式如下：起 址長 度狀 態(tài)第一欄14 K12 K未 分 配第二欄32 K96 K未 分 配MM空 表 目空 表 目MM其中，起址指出一個空閑區(qū)的內(nèi)存起始地

42、址。 長度指出從起始地址開始的一個連續(xù)空閑的長度。 狀態(tài)有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對應(yīng)的由起址指出的某個長度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對應(yīng)的登記項(xiàng)目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應(yīng)找一個“空表目”欄登記歸還區(qū)的起址和長度且修改狀態(tài)）。由于分區(qū)的個數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。上述的這張說明表的登記情況是按上例裝入三個作業(yè)占用主存區(qū)域后的情況填寫的。(2) 當(dāng)有一個新作業(yè)要求裝入主存時，必須查空閑區(qū)說明表，從中找出一個足夠大的空閑區(qū)。有時找到的空閑區(qū)可能大于作業(yè)需要量，這時應(yīng)把原來的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個空閑區(qū)按其地址順序登記，即每個后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。(3) 例如：采用最先適應(yīng)算法分配主存空間。按照作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。由于本實(shí)驗(yàn)是模擬內(nèi)存