操作系統(tǒng)課程設(shè)計(jì)說明

1、<p><b>　　操作系統(tǒng)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)目的</b></p><p>　　本課程設(shè)計(jì)是學(xué)習(xí)完《操作系統(tǒng)原理》課程后，進(jìn)行的一次全面的綜合訓(xùn)練。通過這次課程設(shè)計(jì)，讓我們更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法,加深對(duì)操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)動(dòng)手能力。</p><p>&

2、lt;b>　　實(shí)驗(yàn)環(huán)境</b></p><p>　　環(huán)境不限，可以在vc和java,, C#等環(huán)境下完成，操作系統(tǒng)平臺(tái)可以選擇Windows，Linux等平臺(tái)。</p><p><b>　　實(shí)驗(yàn)內(nèi)容</b></p><p>　　以下幾項(xiàng)實(shí)驗(yàn)內(nèi)容可任選一項(xiàng)完成即可。可分組進(jìn)行（2人一組），也可獨(dú)立完成。</p>&

3、lt;p>　　進(jìn)程調(diào)度算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　銀行家算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　分區(qū)分配與回收算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　假脫機(jī)技術(shù)算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　文件系統(tǒng)管理算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　四、報(bào)告目錄要求（以銀行家算法為例）</p><p

4、><b>　　一、設(shè)計(jì)目的3</b></p><p><b>　　二、設(shè)計(jì)內(nèi)容3</b></p><p>　　三、銀行家算法的基本思想3</p><p><b>　　（一）死鎖3</b></p><p>　?。ǘ┫到y(tǒng)安全狀態(tài)4</p><

5、;p>　?。ㄈ┿y行家算法避免死鎖4</p><p>　　1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)4</p><p><b>　　2、銀行家算法4</b></p><p><b>　　3、安全性算法5</b></p><p>　　四、系統(tǒng)模塊間關(guān)系圖，流程圖6</p><p&g

6、t;　　五、系統(tǒng)子模塊結(jié)構(gòu)圖7</p><p>　　六、輸入、輸出數(shù)據(jù)9</p><p>　　七、源程序及系統(tǒng)文件使用說明12</p><p><b>　?。ㄒ唬┰闯绦?2</b></p><p>　?。ǘ┫到y(tǒng)文件使用說明25</p><p><b>　　八、心得體會(huì)26&

7、lt;/b></p><p><b>　　九、參考文獻(xiàn)26</b></p><p><b>　　五、各算法實(shí)現(xiàn)說明</b></p><p>　　進(jìn)程調(diào)度算法設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　要求</b></p><p>　　選用優(yōu)先數(shù)法和多

8、級(jí)反饋隊(duì)列調(diào)度算法對(duì)n個(gè)進(jìn)程進(jìn)行調(diào)度。</p><p>　　進(jìn)程是操作系統(tǒng)最終要的概念之一，進(jìn)程調(diào)度又是操作系統(tǒng)核心的主要內(nèi)容。本設(shè)計(jì)要求學(xué)生獨(dú)立的用高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)進(jìn)程調(diào)度程序。調(diào)度算法包括：優(yōu)先權(quán)調(diào)度算法、多級(jí)反饋隊(duì)列調(diào)度算法（可設(shè)置菜單由用戶選擇采取何種調(diào)度算法，也可添加自行設(shè)計(jì)的調(diào)度算法）。通過本設(shè)計(jì)加深對(duì)于進(jìn)程調(diào)度和各種調(diào)度算法的理解，加深理解有關(guān)進(jìn)程控制塊、進(jìn)程隊(duì)列的概念，并體會(huì)和了解優(yōu)先數(shù)和時(shí)

9、間片輪轉(zhuǎn)調(diào)度算法的具體實(shí)施辦法。</p><p><b>　　說明與提示</b></p><p>　　設(shè)計(jì)一個(gè)有n個(gè)進(jìn)程（可假定系統(tǒng)有五個(gè)進(jìn)程）共行的進(jìn)程調(diào)度程序。每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表。PCB中應(yīng)包含下列信息：進(jìn)程名、進(jìn)程優(yōu)先數(shù)、進(jìn)程需要運(yùn)行的時(shí)間、占用CPU的時(shí)間及進(jìn)程的狀態(tài)等，且可按調(diào)度算法的不同而增減。各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間片數(shù)，以及進(jìn)程運(yùn)行

10、需要地時(shí)間片數(shù)，均由偽隨機(jī)數(shù)發(fā)生器產(chǎn)生。</p><p>　　調(diào)度程序應(yīng)包含2~3種不同的調(diào)度算法，運(yùn)行時(shí)可任選一種。</p><p>　　每個(gè)進(jìn)程處于運(yùn)行R、就緒W和完成F三種狀態(tài)之一，假定初始狀態(tài)都為就緒狀態(tài)W。</p><p>　　系統(tǒng)能顯示或打印各進(jìn)程狀態(tài)和參數(shù)的變化情況。</p><p>　　為便于處理，程序中進(jìn)程的運(yùn)行時(shí)間以時(shí)間片

11、為基本計(jì)算單位。</p><p>　　進(jìn)程控制塊PCB的格式為：</p><p>　　優(yōu)先數(shù)算法：進(jìn)程就緒鏈按優(yōu)先數(shù)大小排列，鏈?zhǔn)资紫韧度脒\(yùn)行。每過一個(gè)時(shí)間片，運(yùn)行進(jìn)程所需運(yùn)行的時(shí)間片數(shù)減1，說明它已運(yùn)行了一個(gè)時(shí)間片，優(yōu)先數(shù)也減3，理由是該進(jìn)程如果在一個(gè)時(shí)間片中完成不了，優(yōu)先數(shù)應(yīng)降低一級(jí)。接著比較現(xiàn)行進(jìn)程和就緒鏈?zhǔn)走M(jìn)程的優(yōu)先數(shù)，如果仍是現(xiàn)行進(jìn)程高或者相同，就讓現(xiàn)行進(jìn)程繼續(xù)運(yùn)行，否則，調(diào)度就

12、緒鏈的鏈?zhǔn)走M(jìn)程投入運(yùn)行。原運(yùn)行進(jìn)程再按照其優(yōu)先數(shù)大小插入就緒鏈，且改變它們對(duì)應(yīng)的進(jìn)程狀態(tài)，直至所有進(jìn)程都運(yùn)行完各自的時(shí)間片數(shù)。</p><p>　　簡(jiǎn)單輪轉(zhuǎn)法：進(jìn)程就緒鏈按各進(jìn)程進(jìn)入的先后次序排列，進(jìn)程每次占用處理機(jī)的輪轉(zhuǎn)時(shí)間按其重要程度登入進(jìn)程控制塊中的輪轉(zhuǎn)時(shí)間片數(shù)記錄項(xiàng)（相應(yīng)于優(yōu)先數(shù)法的優(yōu)先數(shù)記錄項(xiàng)位置）。每過一個(gè)時(shí)間片，運(yùn)行進(jìn)程占用處理機(jī)的時(shí)間片數(shù)加1，然后比較占用處理機(jī)的時(shí)間片數(shù)是否與該進(jìn)程的輪轉(zhuǎn)時(shí)間片數(shù)

13、相等，若相等說明已到達(dá)輪轉(zhuǎn)時(shí)間，應(yīng)將現(xiàn)運(yùn)行進(jìn)程排到就緒鏈末尾，調(diào)度鏈?zhǔn)走M(jìn)程占用處理機(jī)，且改變它們的進(jìn)程狀態(tài)，直至所有進(jìn)程完成各自的時(shí)間片。</p><p><b>　　進(jìn)程控制塊鏈結(jié)構(gòu)：</b></p><p>　　RUN HEAD TAIL</p><p&g

14、t;<b>　　其中：</b></p><p>　　RUN ——當(dāng)前運(yùn)行進(jìn)程指針；</p><p>　　HEAD——進(jìn)程就緒鏈鏈?zhǔn)字羔槪?lt;/p><p>　　TAIL ——進(jìn)程就緒鏈鏈尾指針。</p><p>　　5． 隨即函數(shù)rand()通常的使用方法：</p><p>　　rand()不需要參

15、數(shù)，它會(huì)返回一個(gè)從0到最大隨機(jī)數(shù)的任意整數(shù)，最大隨機(jī)數(shù)的大小通常是固定的一個(gè)大整數(shù)。</p><p>　　這樣，如果你要產(chǎn)生0~10的10個(gè)整數(shù)，可以表達(dá)為：</p><p>　　int N = rand() % 11；</p><p>　　這樣，N的值就是一個(gè)0~10的隨機(jī)數(shù)，如果要產(chǎn)生1~10，則是這樣：</p><p>　　int N

16、= 1 + rand() % 11；</p><p>　　總結(jié)來說，可以表示為：</p><p>　　a + rand() %n ；</p><p>　　其中的a是起始值，n是整數(shù)的范圍。</p><p>　　若要0~1的小數(shù)，則可以先取得0~10的整數(shù)，然后均除以10即可得到隨機(jī)到十分位的10個(gè)隨機(jī)小數(shù)，若要得到隨機(jī)到百分位的隨機(jī)小數(shù)，則需

17、要先得到0~100的10個(gè)整數(shù)，然后均除以100，其它情況依此類推。</p><p>　　通常rand()產(chǎn)生的隨機(jī)數(shù)在每次運(yùn)行的時(shí)候都是與上一次相同的，這是有意這樣設(shè)計(jì)的，是為了便于程序的調(diào)試。若要產(chǎn)生每次不同的隨機(jī)數(shù)，可以使用srand( seed )函數(shù)進(jìn)行隨機(jī)化，隨著seed的不同，就能夠產(chǎn)生不同的隨機(jī)數(shù)。此外，還可以包含time.h頭文件，然后使用srand( time(0))來使用當(dāng)前時(shí)間使隨機(jī)數(shù)發(fā)生

18、器隨機(jī)化，這樣就可以保證每?jī)纱芜\(yùn)行時(shí)可以得到不同的隨機(jī)數(shù)序列(只要兩次行的間隔超過1秒)。</p><p>　?。ǘ┿y行家算法設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　要求</b></p><p>　　編制銀行家算法通用程序，并檢測(cè)所給狀態(tài)的系統(tǒng)安全性。</p><p><b>　　說明與提示</b>

19、;</p><p><b>　　（一）死鎖</b></p><p>　　在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)——死鎖。所謂死鎖，是指多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)。</p><p>　　產(chǎn)生死鎖

20、的原因可歸結(jié)為如下兩點(diǎn)：</p><p><b>　　（1）競(jìng)爭(zhēng)資源。</b></p><p>　?。?）進(jìn)程間推進(jìn)順序非法。</p><p>　　死鎖的發(fā)生必須具備下列四個(gè)必要條件：</p><p><b>　?。?）互斥條件。</b></p><p>　?。?）請(qǐng)求和保持

21、條件。</p><p><b>　?。?）不剝奪條件。</b></p><p>　?。?）環(huán)路等待條件。</p><p><b>　?。ǘ┫到y(tǒng)安全狀態(tài)</b></p><p>　　避免死鎖的實(shí)質(zhì)在于：系統(tǒng)在進(jìn)行資源分配時(shí)，如何使系統(tǒng)不進(jìn)入不安全狀態(tài)。</p><p>　　所

22、謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序（P1，P2，……，Pn）（稱<P1，P2，……，Pn>序列為安全序列），來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利的完成。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。</p><p>　?。ㄈ┿y行家算法避免死鎖</p><p>　　為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。<

23、;/p><p>　　1、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)</p><p>　?。?）可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。</p><p>　?。?）最大需求矩陣M

24、ax。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i，j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。</p><p>　?。?）分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i，j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。</p><p>

25、　?。?）需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i，j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。</p><p>　　上述三個(gè)矩陣存在如下關(guān)系：</p><p>　　Need[i,j]= Max[i，j]- Allocation[i，j]</p><p><b>　　2、銀行家算法<

26、;/b></p><p>　　設(shè)Request[i] 是進(jìn)程Pi的請(qǐng)求向量，如果Request[i，j]=K,表示進(jìn)程需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：</p><p>　?。?）如果Request[i，j]<= Need[i，j]，便轉(zhuǎn)向步驟（2）；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。</p><p

27、>　?。?）如果Request[i，j]<= Available[j]，便轉(zhuǎn)向步驟（3）；否則，表示尚無(wú)足夠資源，Pi須等待。</p><p>　　（3）系統(tǒng)嘗試著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：</p><p>　　Available[j]= Available[j]- Request[i，j]；</p><p>　　Allocati

28、on[i，j]= Allocation[i，j]+ Request[i，j]；</p><p>　　Need[i，j]= Need[i，j]- Request[i，j]；</p><p>　　（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的嘗試分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。</p

29、><p><b>　　3、安全性算法</b></p><p>　　系統(tǒng)所執(zhí)行的安全性算法可描述如下：</p><p>　?。?）設(shè)置兩個(gè)向量：①工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available；②Finish：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。

30、開始時(shí)先做Finish[i]=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]=true。</p><p>　　（2）從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：</p><p>　?、貴inish[i]=false；②Need[i，j] <= Work[j]；若找到，執(zhí)行步驟（3），否則，執(zhí)行步驟（4）。</p><p>　?。?）當(dāng)進(jìn)程Pi獲得資

31、源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：</p><p>　　Work[j]= Work[j]+ Allocation[i，j]；</p><p>　　Finish[i]=true；</p><p>　　go to step 2；</p><p>　　（4）如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于

32、安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。</p><p>　?。ㄋ模┛赡苡玫降闹饕獢?shù)據(jù)結(jié)構(gòu)說明</p><p>　　#include "stdafx.h"</p><p>　　#include<iostream.h></p><p>　　#include<fstream.h></p>&l

33、t;p>　　#include<windows.h></p><p>　　#include<stdlib.h></p><p>　　#define MAX_PROCESS 32 //最大進(jìn)程數(shù)</p><p>　　#define MAX_COURCE 64 //最大資源類別</p&

34、gt;<p>　　int MAX_FACT_PROCESS; //實(shí)際總進(jìn)程數(shù)</p><p>　　int MAX_FACT_COURCE; //實(shí)際資源類別數(shù)</p><p>　　int Available[MAX_COURCE]; //可利用資源向量</p><p&g

35、t;　　int Max[MAX_PROCESS][MAX_COURCE]; //最大需求矩陣</p><p>　　int Allocation[MAX_PROCESS][MAX_COURCE]; //分配矩陣</p><p>　　int Need[MAX_PROCESS][MAX_COURCE]; //需求矩陣</p><p>

36、　　int Request_PROCESS; //發(fā)出請(qǐng)求的進(jìn)程</p><p>　　int Request_COURCE; //被請(qǐng)求資源類別</p><p>　　int Request_COURCE_NEMBER; //請(qǐng)求資源數(shù)</p><p&

37、gt;　?。ㄈ┓謪^(qū)分配與回收算法設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　要求</b></p><p>　　模擬分頁(yè)式存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和產(chǎn)生缺頁(yè)中斷，用先進(jìn)先出（FIFO）頁(yè)面調(diào)度算法和最近最少用（LRU）頁(yè)面調(diào)度算法處理缺頁(yè)中斷。</p><p><b>　　說明與提示</b></p><p&

38、gt;　　分頁(yè)式存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和產(chǎn)生缺頁(yè)中斷</p><p>　　分頁(yè)式虛擬存儲(chǔ)系統(tǒng)是把作業(yè)信息的副本存放在磁盤上，當(dāng)作業(yè)被選中時(shí)，可把作業(yè)的開始幾頁(yè)先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁(yè)表時(shí)，應(yīng)說明哪些頁(yè)已在主存，哪些頁(yè)尚未裝入主存，頁(yè)表的格式為：</p><p>　　其中，標(biāo)志----用來表示對(duì)應(yīng)頁(yè)是否已經(jīng)裝入主存，標(biāo)志位=1，則表示該頁(yè)已經(jīng)在主存，標(biāo)志位=0，則表示該頁(yè)

39、尚未裝入主存。</p><p>　　主存塊號(hào)----用來表示已經(jīng)裝入主存的頁(yè)所占的塊號(hào)。</p><p>　　在磁盤上的位置----用來指出作業(yè)副本的每一頁(yè)被存放在磁盤上的位置。</p><p>　　作業(yè)執(zhí)行時(shí)，指令中的邏輯地址指出了參加運(yùn)算的操作存放的頁(yè)號(hào)和單元號(hào)，硬件的地址轉(zhuǎn)換機(jī)構(gòu)按頁(yè)號(hào)查頁(yè)表，若該頁(yè)對(duì)應(yīng)標(biāo)志為“1”，則表示該頁(yè)已在主存，這時(shí)根據(jù)關(guān)系式：<

40、/p><p>　　絕對(duì)地址=塊號(hào)×塊長(zhǎng)+單元號(hào)</p><p>　　計(jì)算出欲訪問的主存單元地址。如果塊長(zhǎng)為2的冪次，則可把塊號(hào)作為高地址部分，把單元號(hào)作為低地址部分，兩者拼接而成絕對(duì)地址。若訪問的頁(yè)對(duì)應(yīng)標(biāo)志為“0”，則表示該頁(yè)不在主存，這時(shí)硬件發(fā)“缺頁(yè)中斷”信號(hào)，有操作系統(tǒng)按該頁(yè)在磁盤上的位置，把該頁(yè)信息從磁盤讀出裝入主存后再重新執(zhí)行這條指令。</p><p>

41、;　　設(shè)計(jì)一個(gè)“地址轉(zhuǎn)換”程序來模擬硬件的地址轉(zhuǎn)換工作。當(dāng)訪問的頁(yè)在主存時(shí)，則形成絕對(duì)地址，但不去模擬指令的執(zhí)行，而用輸出轉(zhuǎn)換后的地址來代替一條指令的執(zhí)行。當(dāng)訪問的頁(yè)不在主存時(shí)，則輸出“* 該頁(yè)頁(yè)號(hào)”，表示產(chǎn)生了一次缺頁(yè)中斷。該模擬程序的算法如圖4-1。</p><p>　　圖4-1 地址轉(zhuǎn)換模擬算法</p><p>　　假定主存的每塊長(zhǎng)度為128個(gè)字節(jié)；現(xiàn)有一個(gè)共七頁(yè)的作業(yè)，其中第0頁(yè)

42、至第3頁(yè)已經(jīng)裝入主存，其余三頁(yè)尚未裝入主存；該作業(yè)的頁(yè)表為：</p><p>　　如果作業(yè)依次執(zhí)行的指令序列為：</p><p>　　運(yùn)行設(shè)計(jì)的地址轉(zhuǎn)換程序，顯示或打印運(yùn)行結(jié)果。因僅模擬地址轉(zhuǎn)換，并不模擬指令的執(zhí)行，故可不考慮上述指令序列中的操作。</p><p>　　用先進(jìn)先出（FIFO）頁(yè)面調(diào)度算法處理缺頁(yè)中斷。</p><p>　　在分

43、頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁(yè)中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如果主存中已經(jīng)沒有空閑塊，則可用FIFO頁(yè)面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁(yè)調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁(yè)裝入該塊。調(diào)出和裝入后都要修改頁(yè)表頁(yè)表中對(duì)應(yīng)頁(yè)的標(biāo)志。</p><p>　　FIFO頁(yè)面調(diào)度算法總是淘汰該作業(yè)中最先進(jìn)入主存的那一頁(yè)，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁(yè)面。假定作業(yè)被選中時(shí)，把開始的m個(gè)頁(yè)面裝

44、入主存，則數(shù)組的元素可定為m個(gè)。例如：</p><p>　　P[0]，P[1]，….，P[m-1]</p><p>　　其中每一個(gè)P[i]（i=0，1，….，m-1）表示一個(gè)在主存中的頁(yè)面號(hào)。它們的初值為：</p><p>　　P[0]:=0，P[1]:=1，….，P[m-1]:=m-1</p><p>　　用一指針k指示當(dāng)要裝入新頁(yè)時(shí)，應(yīng)淘

45、汰的頁(yè)在數(shù)組中的位置，k的初值為“0”。</p><p>　　當(dāng)產(chǎn)生缺頁(yè)中斷后，操作系統(tǒng)選擇P[k]所指出的頁(yè)面調(diào)出，然后執(zhí)行：</p><p>　　P[k]:=要裝入頁(yè)的頁(yè)號(hào)</p><p>　　k:=(k+1) mod m</p><p>　　再由裝入程序把要訪問的一頁(yè)信息裝入到主存中。重新啟動(dòng)剛才那條指令執(zhí)行。</p>&

46、lt;p>　　編制一個(gè)FIFO頁(yè)面調(diào)度程序，為了提高系統(tǒng)效率，如果應(yīng)淘汰的頁(yè)在執(zhí)行中沒有修改過，則可不必把該頁(yè)調(diào)出（因在磁盤上已有副本）而直接裝入一個(gè)新頁(yè)將其覆蓋。因此在頁(yè)表中增加是否修改過的標(biāo)志，為“1”表示修改過，為“0”表示未修改過，格式為：</p><p>　　由于是模擬調(diào)度算法，所以，不實(shí)際啟動(dòng)輸出一頁(yè)和裝入一頁(yè)的程序，而用輸出調(diào)出的頁(yè)號(hào)和裝入的頁(yè)號(hào)來代替一次調(diào)出和裝入的過程。</p>

47、<p>　　把第一題中程序稍作修改，與本題結(jié)合起來，F(xiàn)IFO頁(yè)面調(diào)度模擬算法如圖4-2。</p><p>　　磁盤上，在磁盤上的存放地址以及已裝入主存的頁(yè)和作業(yè)依次執(zhí)行的指令序列都同第一題中（4）所示。于是增加了“修改標(biāo)志”后的初始頁(yè)表為：</p><p>　　按依次執(zhí)行的指令序列，運(yùn)行你所設(shè)計(jì)的程序，顯示或打印每次調(diào)出和裝入的頁(yè)號(hào)，以及執(zhí)行了最后一條指令后的數(shù)組P的值。&l

48、t;/p><p>　　為了檢查程序的正確性，可再任意確定一組指令序列，運(yùn)行設(shè)計(jì)的程序，核對(duì)執(zhí)行的結(jié)果。</p><p>　　用最近最少用（LRU）頁(yè)面調(diào)度算法處理缺頁(yè)中斷。</p><p><b>　　[提示]</b></p><p>　　在分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁(yè)中斷”后，引出操作系統(tǒng)來處理這個(gè)中斷事件。如果

49、主存中已經(jīng)沒有空閑塊，則可用LRU頁(yè)面調(diào)度算法把該作業(yè)中最先進(jìn)入主存的一頁(yè)調(diào)出，存放到磁盤上，然后再把當(dāng)前要訪問的頁(yè)裝入該塊。調(diào)出和裝入后都要修改頁(yè)表頁(yè)表中對(duì)應(yīng)頁(yè)的標(biāo)志。</p><p>　　LRU頁(yè)面調(diào)度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒有訪問過的那一頁(yè)，因此可以用一個(gè)數(shù)組來表示該作業(yè)已在主存的頁(yè)面。數(shù)組中的第一個(gè)元素總是指出當(dāng)前剛訪問的頁(yè)號(hào)，因此最久沒被訪問的頁(yè)總是由最后一個(gè)元素指出。如果主存中只有四塊空閑塊且

50、執(zhí)行第一題提示（4）假設(shè)的指令序列，采用LRU頁(yè)面調(diào)度算法，那麼在主存中的頁(yè)面變化情況如下：</p><p>　　編制一個(gè)LRU頁(yè)面調(diào)度程序，為了提高系統(tǒng)效率，如果應(yīng)淘汰的頁(yè)在執(zhí)行中沒有修改過，則可不必把該頁(yè)調(diào)出。參看第二題中提示（3）。模擬調(diào)度算法不實(shí)際啟動(dòng)輸出一頁(yè)和裝入一頁(yè)的程序，而用輸出調(diào)出的頁(yè)號(hào)和裝入的頁(yè)號(hào)來代替。把第一題中的程序稍作</p><p>　　改動(dòng)，與本題集合起來，LR

51、U頁(yè)面調(diào)度模擬算法如圖4-3。</p><p>　　按第一題中提示（4）的要求，建立一張初始頁(yè)表，表中為每一頁(yè)增加“修改標(biāo)志”位（參考第二題中提示（4））。然后按依次執(zhí)行的指令序列，運(yùn)行你所設(shè)計(jì)的程序，顯示或打印每次調(diào)出和裝入的頁(yè)號(hào)，以及執(zhí)行了最后一條指令后的數(shù)組中的值。</p><p>　　為了檢查程序的正確性，可再任意確定一組指令序列，運(yùn)行設(shè)計(jì)的程序，核對(duì)執(zhí)行的結(jié)果。</p>

52、;<p>　?。ㄋ模┘倜摍C(jī)技術(shù)算法設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　（假脫機(jī)技術(shù)或稱Spooling技術(shù)）</p><p><b>　　要求</b></p><p>　　假脫機(jī)（Spooling）技術(shù)是廣泛用于各種系統(tǒng)的一種行之有效的輸入輸出手段，這種技術(shù)使用比較簡(jiǎn)單的方法，緩和了處理機(jī)與低速輸入輸出設(shè)備速度不匹配的矛盾，提高設(shè)備的

53、利用率。為了更好地掌握這種技術(shù)，本設(shè)計(jì)要求學(xué)生獨(dú)立地用高級(jí)語(yǔ)言編寫一個(gè)Spooling程序來模擬假脫機(jī)輸入輸出過程。</p><p>　　可將Spooling輸入輸出程序編制成一個(gè)獨(dú)立的進(jìn)程與其它要求輸入輸出的進(jìn)程并發(fā)工作。Spooling進(jìn)程負(fù)責(zé)從卡片機(jī)或光電讀帶機(jī)等設(shè)備讀入信息送到磁盤或磁鼓的輸入井中，或是把磁盤、磁鼓輸出井的信息塊送到打印機(jī)或CRT等設(shè)備輸出。其余進(jìn)程只要求編寫輸入輸出部分的程序，可不考慮其

54、它操作。</p><p><b>　　說明與提示</b></p><p>　　1、本示例編制一個(gè)Spooling輸出進(jìn)程與另外二個(gè)要求輸出的進(jìn)程并發(fā)運(yùn)行。要求輸出進(jìn)程每運(yùn)行一次只輸出一項(xiàng)信息到輸出井，待輸出到一個(gè)結(jié)束標(biāo)志時(shí)，表示一批信息輸出完成，在輸出井中形成一輸出信息塊，再由Spooling進(jìn)程把整個(gè)信息塊實(shí)際輸出到打印機(jī)或CRT。因此，進(jìn)程的運(yùn)行必須考慮同步問題。

55、</p><p>　　采用進(jìn)程的隨機(jī)調(diào)度法模擬Spooling輸出是合適的，因?yàn)楦鬟M(jìn)程的輸出應(yīng)是隨機(jī)的。</p><p>　?。?）進(jìn)程調(diào)度采用隨機(jī)調(diào)度法，二個(gè)要求輸出進(jìn)程的調(diào)度概率各為45%，Spooling進(jìn)程為10%。</p><p>　?。?）可為進(jìn)程設(shè)置三種工作狀態(tài)：可運(yùn)行狀態(tài)，不可運(yùn)行狀態(tài)和結(jié)束狀態(tài)。為了區(qū)分要求輸出進(jìn)程和Spooling進(jìn)程處于不可運(yùn)行

56、狀態(tài)的不同原因，又把不可運(yùn)行狀態(tài)分成不可運(yùn)行狀態(tài)1和2。分別敘述如下：</p><p>　?、龠M(jìn)程執(zhí)行完畢后應(yīng)置成“結(jié)束狀態(tài)”。</p><p>　?、谝筝敵鲞M(jìn)程在輸出信息時(shí)，如發(fā)現(xiàn)輸出井已滿，應(yīng)置成“不可運(yùn)行狀態(tài)1”。</p><p>　?、跾pooling進(jìn)程在輸出井空時(shí)應(yīng)置成“不可運(yùn)行狀態(tài)2”。</p><p>　?、躍pooling

57、進(jìn)程輸出一個(gè)信息塊后，應(yīng)釋放該信息塊所占的輸出井位置，并將正在等待輸出的進(jìn)程置成“可運(yùn)行狀態(tài)”。</p><p>　?、菀筝敵鲞M(jìn)程在輸出信息到輸出井并形成信息塊后，應(yīng)將Spooling進(jìn)程置成“可運(yùn)行狀態(tài)”。</p><p>　?。?）程序中使用的數(shù)據(jù)結(jié)構(gòu)有：</p><p>　?、龠M(jìn)程控制塊（PCB）</p><p><b>　

58、?、谳敵稣?qǐng)求塊</b></p><p>　　每構(gòu)成一個(gè)輸出信息塊時(shí)（即遇到結(jié)束標(biāo)志），應(yīng)形成一輸出請(qǐng)求塊，待Spooling進(jìn)程運(yùn)行時(shí)控制輸出，結(jié)構(gòu)如下：</p><p><b>　?、圯敵鼍?lt;/b></p><p>　　要求輸出的進(jìn)程在輸出井中應(yīng)有自己的區(qū)域，不應(yīng)與其它的輸出進(jìn)程混淆。</p><p>　　

59、圖 假脫機(jī)輸出系統(tǒng)框圖</p><p>　　圖 請(qǐng)求輸出進(jìn)程程序框圖</p><p>　　圖 Spooling進(jìn)程程序框圖</p><p>　?。?）請(qǐng)求輸出程序簡(jiǎn)單地設(shè)計(jì)成每運(yùn)行一次，隨機(jī)輸出一個(gè)0~9之間，為了方便，把“0”作為輸出結(jié)束標(biāo)志。當(dāng)輸出為“0”時(shí)，就可形成一個(gè)信息塊輸出。</p><p>　?。?）程序中的有關(guān)變量說明如

60、下：</p><p>　　L1 空閑輸出請(qǐng)求塊計(jì)數(shù)器。初值為10，即系統(tǒng)最多可設(shè)置十個(gè)輸出信息塊。</p><p>　　B1 進(jìn)程輸出請(qǐng)求塊鏈鏈?zhǔn)字羔?。初值?。</p><p>　　B2 空閑輸出請(qǐng)求塊鏈鏈?zhǔn)字羔槨３踔禐?。</p><p>　　L2（1）、L2（2） 二個(gè)輸出井的計(jì)數(shù)器，初值為100，即每個(gè)井能存放100個(gè)信息項(xiàng)。<

61、/p><p>　　K（1）、K（2） 用來控制二個(gè)請(qǐng)求輸出進(jìn)程的輸出文件數(shù)，避免系統(tǒng)無(wú)限循環(huán)下去。</p><p>　?。?）程序啟動(dòng)后，屏幕上應(yīng)顯示：</p><p>　　“Input the times of user1’s output file”和 “Input the times of user2’s output file”要求用戶先后打入二個(gè)輸出進(jìn)程所要求

62、的輸出文件數(shù)，控制程序的整個(gè)運(yùn)行時(shí)間。隨后，系統(tǒng)自行調(diào)度Spooling進(jìn)程輸出，并在打印機(jī)上打印二個(gè)進(jìn)程的假脫機(jī)輸出過程，待完成各自輸出文件數(shù)后停止。</p><p>　?。ㄎ澹┪募到y(tǒng)管理算法設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　要求</b></p><p>　　設(shè)計(jì)一個(gè)10個(gè)用戶的文件系統(tǒng)，每次用戶可保存10個(gè)文件，一次運(yùn)行用戶可以打開

63、5個(gè)文件。</p><p><b>　　提示與說明</b></p><p>　　隨著社會(huì)信息量的極大增長(zhǎng)，要求計(jì)算機(jī)處理的信息與日俱增，涉及到社會(huì)生活的各個(gè)方面。因此，文件管理是操作系統(tǒng)的一個(gè)非常重要的組成部分。學(xué)生應(yīng)獨(dú)立用高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)簡(jiǎn)單的文件系統(tǒng)，模擬文件管理的工作過程。從而對(duì)各種文件操作命令的實(shí)質(zhì)內(nèi)容和執(zhí)行過程有比較深入的了解，掌握它們的實(shí)施方法，加深

64、理解課堂上講授過的知識(shí)。</p><p>　　文件系統(tǒng)算法流程圖：</p><p>　　用高級(jí)語(yǔ)言編寫和調(diào)試一個(gè)簡(jiǎn)單的文件系統(tǒng)，模擬文件管理的工作過程。要求設(shè)計(jì)一個(gè)10個(gè)用戶的文件系統(tǒng)，每次用戶可保存10個(gè)文件，一次運(yùn)行用戶可以打開5個(gè)文件。系統(tǒng)能夠檢查打入命令的正確性，出錯(cuò)時(shí)能顯示出錯(cuò)原因。對(duì)文件必須設(shè)置保護(hù)措施，例如只能執(zhí)行，允許讀等。在每次打開文件時(shí)，根據(jù)本次打開的要求，在此設(shè)置保護(hù)

65、級(jí)別，即有二級(jí)保護(hù)。文件的操作至少有Create、delete、open、close、read、write等命令。</p><p>　　所編寫的程序應(yīng)采用二級(jí)文件目錄，即設(shè)置主文件目錄和用戶文件目錄。前者應(yīng)包含文件主及它們的目錄區(qū)指針；后者應(yīng)給出每個(gè)文件占有的文件目錄，即文件名，保護(hù)碼，文件長(zhǎng)度以及它們存放的位置等。另外為打開文件設(shè)置運(yùn)行文件目錄（AFD），在文件打開時(shí)應(yīng)填入打開文件號(hào)，本次打開保護(hù)碼和讀寫指針等