作業系統實驗報告

學院計算機

專業電腦科學與技術

班級 04級7班

學號 3204006765

姓名唐敏儀

指導教師胡欣如老師

2007 年 5 月日

計算機學院計算機專業七班學號： 3204006765

姓名：唐敏儀協作者教師評定

實驗__一__題目__ 程序排程_______ 第 7 周星期二

實驗__二__題目__ 作業排程_______ 第 7 周星期二

實驗__三__題目__ 檔案系統_______ 第 11 周星期二

實驗__設計性_題目_主存空間的分配與** _第 13 周星期二

實驗平台：

1、計算機及作業系統：pc機, windows xp

2、程式設計環境：c++

源程式名和可執行程式名：

實驗一： 1-1．cpp ， 1-1．exe ，，

實驗二： 2．cpp，

實驗三：

實驗（設計性）：5．cpp ，

備註：實驗__一__題目__ 程序排程_______ 第 7 周星期二

一、實驗目的

用高階語言編寫和除錯乙個程序排程程式，以加深對程序的概念及程序排程演算法的理解．

二、實驗內容和要求

設計乙個有 n個程序共行的程序排程程式。

程序排程演算法：

· 採用最高優先數優先的排程演算法（即把處理機分配給優先數最高的程序）和先來先服務演算法。

· 每個程序有乙個程序控制塊（ pcb）表示。程序控制塊可以包含如下資訊：程序名、優先數、到達時間、需要執行時間、已用cpu時間、程序狀態等等。

· 程序的優先數及需要的執行時間可以事先人為地指定（也可以由隨機數產生）。程序的到達時間為程序輸入的時間。程序的執行時間以時間片為單位進行計算。

· 每個程序的狀態可以是就緒 w（wait）、執行r（run）、或完成f（finish）三種狀態之一。

· 就緒程序獲得 cpu後都只能執行乙個時間片。用已占用cpu時間加1來表示。

· 如果執行乙個時間片後，程序的已占用 cpu時間已達到所需要的執行時間，則撤消該程序，如果執行乙個時間片後程序的已占用cpu時間還未達所需要的執行時間，也就是程序還需要繼續執行，此時應將程序的優先數減1（即降低一級），然後把它插入就緒佇列等待cpu。每進行一次排程程式都列印一次執行程序、就緒佇列、以及各個程序的 pcb，以便進行檢查。

重複以上過程，直到所要程序都完成為止。

三、源程式名及執行程式名

1-1．cpp ， 1-1．exe ，，

四、實驗設計方案及原理：

程序排程演算法：採用最高優先數優先的排程演算法（即把處理機分配給優先數最高的程序）和輪轉法演算法。

1、最高優先數優先法基本思想：把cpu分配給就緒佇列中優先數最高的程序。靜態優先數是在建立程序時確定的，並在整個程序執行期間不再改變。

動態優先數是指程序的優先數在建立程序時可以給定乙個初始值，並且可以按一定原則修改優先數。在本實驗的演算法中就是在程序獲得一次cpu後就將其優先數減少1，然後放入就緒佇列，再重新按各程序優先數從高到低排列。

*其演算法如下：

（1）設定系統中有五個程序，每乙個程序用乙個程序控制塊（ pcb）表示，程序佇列採用

鍊錶資料結構。

（2）程序控制塊可以包含如下資訊：程序名、優先數、到達時間、需要執行時間、已用cpu

時間、程序狀態等等。

（3）在每次執行設計的處理排程程式之前，由終端輸入五個程序的「優先數」和「要求運

行時間」。

（4）程序的優先數及需要的執行時間可以事先人為地指定（也可以由隨機數產生）。程序的

到達時間為程序輸入的時間。程序的執行時間以時間片為單位進行計算。

（5）如果採用優先權排程演算法，則將五個程序按給定的優先數從大到小連成就緒佇列。用

頭指標指出佇列首程序，佇列採用鍊錶結構。

（6）處理機排程總是選佇列首程序執行。如果採用動態優先數辦法，則程序每執行一次優

先數減「1」，同時將執行時間減「1」。

（7）程序執行一次後，若要求執行時間不等於零，則再將它加入就緒佇列；若要求執行時

間為零，則將其狀態置為「結束」,且退出就緒佇列。

（8）「就緒」狀態的程序佇列不為空，則重複上面6，7步驟，指導所有程序都成為「結束」

狀態。（9）在設計的程式中應有輸入語句，輸入5個程序的「優先數」和「要求執行時間」，也應

有顯示或列印語句，能顯示或列印每次被選中程序的程序名、執行一次後佇列的變化，

以及結束程序的程序名。

（10）最後，為五個程序任意確定一組「優先數」和「要求執行時間」，執行並除錯所設計

的程式，顯示或列印出逐次被選中程序的程序名及其程序控制塊的動態變化過程。

2、簡單輪轉法的基本思想：所有就緒程序按 fcfs排成乙個佇列，總是把處理機分配給隊首的程序，各程序占用cpu的時間片相同。即將cpu的處理時間劃分成乙個個相同的時間片，就緒佇列的諸程序輪流執行乙個時間片。

當乙個時間片結束時，如果執行程序用完它的時間片後還未完成，就強迫執行機制程序讓出cpu，就把它送回到就緒佇列的末尾，等待下一次排程。同時，程序排程又去選擇就緒佇列中的隊首程序，分配給它一時間片，以投入執行。直至所有的程序執行完畢。

*其演算法如下：

（1）假設系統有5個程序，每個程序用乙個程序控制塊pcb來代表。

（2）為每個程序任意確定乙個要求執行時間和到達時間。

（3）按照程序到達的先後順序排成乙個迴圈佇列。再設乙個隊首指標指向第乙個到達程序

的首址。

（4）執行處理機排程時，開始選擇隊首的第乙個程序執行。另外，再設乙個當前執行程序

的指標，指向當前正在執行的程序。

（5）由於本實驗是模擬實驗，所以對選中的程序並不實際啟動執行，而只是執行：

估計執行時間減一

輸出當前執行程序的名字

用這兩個操作來模擬程序的一次執行。

（6）程序執行一次後，以後的排程則將當前指標依此下移乙個位置，指向下乙個程序，即

調整當前執行指標指向該程序的鏈結指標所指程序，以指示應執行程序。同時還應判

斷該程序的剩餘執行時間是否為零。若不為零，則等待下一輪的執行，若該程序的剩

餘執行時間為零，則將該程序的狀態置為完成態c，並退出迴圈佇列。

（7）若就緒佇列不空，則重複上述的（5）和（6）步驟直到所有的程序都執行完為止。

在所設計的排程程式中，應包含顯示或列印語句。顯示或列印每次選中的程序的名稱及執行一次後佇列的變化情況。

3、多佇列輪轉法基本思想：在系統中設定多個就緒佇列，各隊優先權不同。cpu總是優先分配給優先權高的佇列中的程序，僅當優先權高的佇列空閒時，cpu才執行下一級佇列中的程序。

優先權越高的佇列，其中的程序執行時所獲得的時間片越小。程序並非總是固定在某一佇列中，系統總是把新建立的程序首先放入優先權最高的佇列，若它執行乙個時間片後尚未完成，系統便把它放入下一級佇列的末尾，即程序的優先權在逐步降低。除最低優先權佇列外的所有其他佇列，均採用相同的程序排程演算法。

當程序進入最低優先權佇列時，便可採用時間片輪轉演算法或其他方式執行。

*其演算法如下：

（1）在系統中設定多個就緒佇列，每個佇列對應乙個優先順序，第乙個佇列的優先順序最高，

第二佇列次之。以下各佇列的優先順序逐步低。

（2）各就緒佇列中的程序的執行時間片不同，高優先順序佇列的時間片小，低優先順序佇列的

時間片大。

除最低優先權佇列外的所有其他佇列，均採用相同的程序排程演算法，即按時間片輪

轉的fifo（先進先出）演算法。

最後乙個佇列中的程序按fcfs策略進行排程。

（3）程序並非總是固定在某一佇列中，新程序進入系統後，被存放在第乙個佇列的末尾。

如果某個程序在規定的時間片內沒有完成工作，則把它轉入到下乙個佇列的末尾，直

至進入最後乙個佇列。

（4）系統先執行第乙個佇列中的程序。當第一隊列為空時，才執行第二個佇列中的程序。

依此類推，僅當前面所有的佇列都為空時，才執行最後乙個佇列中的程序。當處理器

正在第i個佇列中為某個程序服務時，又有新程序進入優先順序最高的佇列（第1—（i-1）

中的任何乙個對列），則此新程序要搶占正在執行程序的處理器，即由排程程式把正在

執行的程序放回第i佇列的末尾，把處理器分配給新到的高優先順序程序。

五、程式流程圖：

1、最高優先數優先法的流程圖如下 :

2、簡單輪轉法的流程圖如下 :

3、多佇列輪轉法的流程圖如下 :

六、程式清單

（1）輪轉法

#include ""

#include <>

#define getpch(type) (type*)malloc(sizeof(type))

#define null 0

struct pcb { /* 定義程序控制塊pcb */

作業系統實驗報告

作業系統實驗報告

作業系統實驗報告

作業系統實驗報告

相關推薦