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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、習效果，加深對相關基本概念的理解，并學習如何將基本原理和實際設計有機的結合。二、實驗內容 在Windows 2000/XP環境下，使用多線程和信號量機制實現讀者優先或寫者優先的讀者-寫者問題，每個線程代表一個讀者或一個寫者。三、提示與講解創建一個控制臺進程。此進程包含n個線程。用這n個線程來表示n個讀者或寫者。每個線程按相應測試數據文件的要求進行讀寫操作。 讀者-寫者問題的讀寫操作限制(讀者優先和寫者優先均適用)： 1)寫-寫互斥，即不能有兩個寫者同時進行寫操作。 2)讀-寫互斥，即不能同時有一個線程在讀，而另一個線程在寫。 3)讀-讀允許，即可以有一個或多個讀者在讀。 讀者優先的附加限制：如

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

17、段表示相應線程角色，R表示讀者，w表示寫者。第三字段為一個正數，表示讀寫操作的開始時間：線程創建后，延遲相應時間(單位為秒)后發出對共享資源的讀寫申請。第四字段為一個正數，表示讀寫操作的持續時間。當線程讀寫申請成功后，開始對共享資源的讀寫操作，該操作持續相應時間后結束，并釋放共享資源。下面是一個測試數據文件的例子：1 R 3 52 W 4 53 R 5 24 R 6 55 W 5 3讀者優先或寫者優先實現其中一個即達到基本要求，但有能力的同學可以實現一個通用的讀者-寫者問題（包含讀者優先和寫者優先），通過不同選項來運行讀者優先或寫者優先。可能用到的API函數：CreateThread()在調用

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

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

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

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

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

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

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

25、的頁中選擇一頁，將它暫時調出主存，讓出主存空間，用來存放需裝入的頁面，這個工作稱為“頁面置換”。如何選擇調出的頁是很重要的，常用的頁面置換算法有先進先出算法（FIFO），最近最少使用算法（LRU）等。實驗中使用先進先出算法。先進先出算法總是選擇駐留在主存時間最長的一頁調出。先進先出算法簡單，易實現。可以把在主存的頁的頁號按進入主存的先后次序排成隊列，每次總是調出隊首的頁，當裝入一個新頁后，把新頁的頁號排入隊尾。實驗中，用一個數組存放頁號的隊列。假定分配給作業的主存塊數為m，數組可由m個元素組成，p0，p1pm-1；隊首指針head；采用頁面預置的方法，頁號隊列的長度總是m，tail=(head

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

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

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

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

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

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

32、理器系統中，正在運行的進程只有一個，因此，單處理器系統中進程控制塊分成一個正在運行進程的進程控制塊，就緒進程的進程控制塊組成的就緒隊列，和等待進程的控制塊組成的等待隊列。由于實驗模擬的是進程調度，沒有對等待隊列的操作，所以實驗中只有一個指向正在運行進程的進程控制塊指針和一個就緒進程的進程控制塊隊列指針。操作系統實現中，系統往往在主存中劃分出一個連續的專門區域存放系統的進程控制塊，實驗中應該用數組模擬這個專門的進程控制塊區域，定義如下：#define n 10 /假定系統允許進程個數為nstruct pcb pcbarean; /模擬進程控制塊區域的數組這樣，進程控制塊的鏈表實際上是數據結構中使

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

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

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

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

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

38、處理器系統的優先數進程調度”結合起來編寫一個通用的進程調度程序，通過優先數的不同設置方法來選擇運行不同的調度算法。實驗五 單處理器系統的優先數進程調度一、實驗目的1. 加深對進程概念的理解，明確進程和程序的區別。2. 深入了解系統如何組織進程、創建進程。3. 進一步認識如何實現處理器調度。二、實驗內容編寫程序完成單處理器系統中的進程調度，要求采用優先數調度算法。實驗具體包括：首先確定進程控制塊的內容，進程控制塊的組成方式；然后完成進程創建原語和進程調度原語；最后編寫主函數對所作工作進行測試。模擬程序只對你所設置的“虛擬PCB”進行相應的調度模擬操作，即每發生“調度”時，顯示出當前運行進程的“進

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

40、置隊首標志）；若剩余運行時間等于0，則把它的狀態修改成“終止”，且退出隊列。若就緒進程隊列不為空，則重復調度，直到所有進程都“終止”。最好能動態地隨機生成新進程添加到就緒隊列中。有能力的同學最好能將本實驗和實驗“單處理器系統的時間片輪轉進程調度”結合起來編寫一個通用的進程調度程序，通過優先數的不同設置方法來選擇運行不同的調度算法。實驗六 內存分配和回收三種適應法一、實驗目的了解用戶程序分配內存以及回收所用內存的過程，加深對操作系統存儲管理的理解。二、實驗內容采用首次適應法、最佳適應法或最差適應法，編寫一內存分配和回收模擬程序。三、提示與講解由于這個實驗的重點在于內存分配，所以不考慮與某內存區相

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

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