部颯％號(hào)

LIAOCHENGUNIVERSITY

計(jì)算機(jī)操作系統(tǒng)

實(shí)驗(yàn)播導(dǎo)零

作者：計(jì)算機(jī)操作系統(tǒng)課程組

聊城大學(xué)計(jì)算機(jī)學(xué)院

2015年3月

前言

操作系統(tǒng)是計(jì)算機(jī)的核心和靈魂。操作系統(tǒng)軟件的設(shè)計(jì)對(duì)整個(gè)計(jì)算機(jī)的功能和性能

起著至關(guān)重要的作用，所以此門課也是必不可少的，是面向計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工

程、軟件工程等大多數(shù)計(jì)算機(jī)專業(yè)本科生開設(shè)的一門計(jì)算機(jī)專業(yè)課程。

操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的核心，《操作系統(tǒng)》課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的重要

必修課。本課程的目的是使學(xué)生掌握現(xiàn)代計(jì)算機(jī)操作系統(tǒng)的基本原理.、基本設(shè)計(jì)方法及

實(shí)現(xiàn)技術(shù)，具有分析現(xiàn)行操作系統(tǒng)和設(shè)計(jì)、開發(fā)實(shí)際操作系統(tǒng)的基本能力。

操作系統(tǒng)實(shí)驗(yàn)是操作系統(tǒng)課程的重要組成部分，屬于學(xué)科基礎(chǔ)實(shí)驗(yàn)范疇。作為與相

關(guān)教學(xué)內(nèi)容配合的實(shí)踐性教學(xué)環(huán)節(jié)，應(yīng)在操作系統(tǒng)理論課教學(xué)過程中開設(shè)。

操作系統(tǒng)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)必修的專業(yè)基礎(chǔ)課程，操作系統(tǒng)實(shí)驗(yàn)的作用是：

理解操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)思路，掌握典型算法。基本要求是：理解進(jìn)程的概念，理解

死鎖，掌握銀行家算法：掌握請(qǐng)求頁式存儲(chǔ)管理的實(shí)現(xiàn)原理及頁面置換算法。學(xué)生應(yīng)具

有高級(jí)語言編程能力、具有數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)知識(shí)。

說明：本實(shí)驗(yàn)指導(dǎo)書所提供的源程序均已在c語言環(huán)境下調(diào)試運(yùn)行過。

目錄

《計(jì)算機(jī)操作系統(tǒng)》課程實(shí)驗(yàn)教學(xué)大綱錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)一單處理器系統(tǒng)的進(jìn)程調(diào)度錯(cuò)誤!未定義書簽。

基本信息錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)?zāi)康腻e(cuò)誤!未定義書簽。

實(shí)驗(yàn)內(nèi)容錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)原理及設(shè)計(jì)錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)條件錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)過程錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)要求錯(cuò)誤!未定義書簽。

思考題錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)二動(dòng)態(tài)資源分配實(shí)驗(yàn)錯(cuò)誤!未定義書簽。

基本信息錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)?zāi)康腻e(cuò)誤!未定義書簽。

實(shí)驗(yàn)內(nèi)容錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)原理及設(shè)計(jì)錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)條件錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)過程錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)要求錯(cuò)誤!未定義書簽。

思考題錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)三請(qǐng)求頁式存儲(chǔ)管理錯(cuò)誤!未定義書簽。

基本信息錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)?zāi)康腻e(cuò)誤!未定義書簽。

實(shí)驗(yàn)內(nèi)容錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)原理及設(shè)計(jì)錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)條件錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)過程錯(cuò)誤!未定義書簽。

實(shí)驗(yàn)要求錯(cuò)誤!未定義書簽。

思考題錯(cuò)誤!未定義書簽。

《計(jì)算機(jī)操作系統(tǒng)》課程實(shí)驗(yàn)教學(xué)大綱

課程名稱：計(jì)算機(jī)操作系統(tǒng)

英文名稱：ComputerOperatingSystems

設(shè)置形式：非獨(dú)立設(shè)課課程模塊專業(yè)核心課

實(shí)驗(yàn)課性質(zhì)：專業(yè)實(shí)驗(yàn)課程編號(hào)509311

課程負(fù)責(zé)人：姜華大綱主撰人姜華

大綱審核人：左風(fēng)朝

一、學(xué)時(shí)、學(xué)分

課程總學(xué)時(shí)：78實(shí)驗(yàn)學(xué)時(shí)：16課程學(xué)分：4

二、適用專業(yè)及年級(jí)

計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程專業(yè)二、三年級(jí)

三、課程目標(biāo)與基本要求

操作系統(tǒng)是計(jì)算機(jī)教學(xué)中最重要的環(huán)節(jié)之一，也是計(jì)算機(jī)及其相關(guān)專業(yè)學(xué)生的一門重要的專業(yè)

課程。操作系統(tǒng)課程主要內(nèi)容包括：進(jìn)程管理、處理機(jī)調(diào)度與死鎖、存儲(chǔ)管理、設(shè)備管理、文件系

統(tǒng)、操作系統(tǒng)接口、網(wǎng)絡(luò)操作系統(tǒng)、操作系統(tǒng)安全性以及Unix系統(tǒng)內(nèi)核結(jié)構(gòu)。由于操作系統(tǒng)涉及計(jì)

算機(jī)系統(tǒng)中各種軟硬件資源的管理，內(nèi)容比較繁瑣，具有很強(qiáng)的實(shí)踐性。要學(xué)好這門課程，必須把

理論與實(shí)踐緊密結(jié)合，才能取得較好的學(xué)習(xí)效果。

課程目標(biāo)：培養(yǎng)學(xué)生的系統(tǒng)程序設(shè)計(jì)能力，是操作系統(tǒng)課程的?個(gè)非常重要的環(huán)節(jié)。通過操作

系統(tǒng)上機(jī)實(shí)驗(yàn)，可以培養(yǎng)學(xué)生程序設(shè)計(jì)的方法和技巧，提高學(xué)生編制清晰、合理、可讀性好的系統(tǒng)

程序的能力，加深對(duì)操作系統(tǒng)課程的理解。使學(xué)生更好地掌握操作系統(tǒng)的基本概念、基本原理、及

基本功能，具有分析實(shí)際操作系統(tǒng)、設(shè)計(jì)、構(gòu)造和開發(fā)現(xiàn)代操作系統(tǒng)的基本能力。

基本要求：

1.通過對(duì)操作系統(tǒng)中經(jīng)典算法的模擬，是學(xué)生深入理解算法的實(shí)現(xiàn)和應(yīng)用，了解操作系統(tǒng)在

計(jì)算機(jī)系統(tǒng)中的作用，培養(yǎng)學(xué)生在實(shí)驗(yàn)過程中發(fā)現(xiàn)問題、分析問題和解決問題的能力。

2.掌握系統(tǒng)程序設(shè)計(jì)的基本方法和有關(guān)開發(fā)環(huán)境的使用。通過實(shí)驗(yàn)著重培養(yǎng)學(xué)生閱讀參考資

料、算法分析和設(shè)計(jì)、程序調(diào)試、處理實(shí)驗(yàn)數(shù)據(jù)以及分析與總結(jié)實(shí)驗(yàn)結(jié)果等方面的能力。

3.通過實(shí)驗(yàn)加深對(duì)計(jì)算機(jī)操作系統(tǒng)原理的理解，培養(yǎng)實(shí)事求是、踏實(shí)細(xì)致、嚴(yán)肅認(rèn)真的科學(xué)

態(tài)度和克服困難、堅(jiān)韌不拔的工作作風(fēng)，以及科學(xué)、良好的實(shí)驗(yàn)素質(zhì)和習(xí)慣。

四、主要儀器設(shè)備

硬件：臺(tái)式計(jì)算機(jī)；軟件：C、C++環(huán)境。

五、實(shí)驗(yàn)項(xiàng)目及教學(xué)安排

序項(xiàng)目項(xiàng)目每組教學(xué)

實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)基本方法和內(nèi)容

號(hào)學(xué)時(shí)類型人數(shù)要求

用C/C++編寫和調(diào)試單處理器進(jìn)程調(diào)度

1進(jìn)程調(diào)度實(shí)驗(yàn)的模擬程序，觀察調(diào)度過程，以加深對(duì)進(jìn)程4設(shè)計(jì)型1必修

的概念及進(jìn)程調(diào)度算法的理解。

用C/C++編寫和調(diào)試系統(tǒng)動(dòng)態(tài)分配資源的

2資源管理實(shí)驗(yàn)6設(shè)計(jì)型1必修

簡(jiǎn)單模擬程序，采用銀行家算法，有效地防

止和避免死鎖的發(fā)生。

用C/C++編寫和調(diào)試虛擬內(nèi)存管理的模擬

程序，通過虛存管理的地址轉(zhuǎn)換過程和各種

3存儲(chǔ)器管理實(shí)驗(yàn)6綜合型1必修

頁面淘汰算法的編程實(shí)現(xiàn)，加深對(duì)存儲(chǔ)管理

方案的理解。

六、考核方式及成績(jī)?cè)u(píng)定

認(rèn)真學(xué)習(xí)教學(xué)過程中講授的與實(shí)驗(yàn)相關(guān)的內(nèi)容，提前做好實(shí)驗(yàn)預(yù)習(xí)。按實(shí)驗(yàn)指導(dǎo)書要求事先編

好程序；準(zhǔn)備好需要輸入的中間數(shù)據(jù)；估計(jì)可能出現(xiàn)的問題；預(yù)計(jì)可能得到的運(yùn)行結(jié)果。做到在每

個(gè)實(shí)驗(yàn)前明確實(shí)驗(yàn)FI的、掌握實(shí)驗(yàn)的基本內(nèi)容及操作方法；在實(shí)驗(yàn)中正確使用實(shí)驗(yàn)設(shè)備，認(rèn)真觀察、

分析實(shí)驗(yàn)結(jié)果；實(shí)驗(yàn)后要根據(jù)要求做好總結(jié)，上交實(shí)驗(yàn)報(bào)告。

根據(jù)學(xué)生實(shí)驗(yàn)出勤情況、實(shí)驗(yàn)態(tài)度、實(shí)驗(yàn)報(bào)告成績(jī)等評(píng)定實(shí)驗(yàn)成績(jī)。實(shí)驗(yàn)報(bào)告（含實(shí)驗(yàn)理論）

占實(shí)驗(yàn)成績(jī)的60%一U）%,實(shí)驗(yàn)技能（含實(shí)驗(yàn)態(tài)度）占實(shí)驗(yàn)成績(jī)的40%—60%。各次實(shí)驗(yàn)成績(jī)的平

均值為最終實(shí)驗(yàn)成績(jī)，占該課程考核總成績(jī)的20%—30%。

七、實(shí)驗(yàn)教科書、參考書

1.實(shí)驗(yàn)教科書

自編實(shí)驗(yàn)指導(dǎo)書。

2.實(shí)驗(yàn)參考書

郁紅英、李春強(qiáng)，計(jì)算機(jī)操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)，清華大學(xué)出版社，2008.9

實(shí)驗(yàn)一單處理器系統(tǒng)的進(jìn)程調(diào)度

基本信息

實(shí)驗(yàn)課程：計(jì)算機(jī)操作系統(tǒng)設(shè)課形式：非獨(dú)立

課程學(xué)分：4實(shí)驗(yàn)項(xiàng)目：進(jìn)程調(diào)度

項(xiàng)目類型：設(shè)計(jì)型項(xiàng)目學(xué)時(shí)：4

實(shí)驗(yàn)?zāi)康?/p>

通過模擬進(jìn)程控制方法及單處理機(jī)系統(tǒng)的進(jìn)程調(diào)度，了解進(jìn)程的結(jié)構(gòu)，進(jìn)程的創(chuàng)建

與撤消，進(jìn)程的組織及進(jìn)程的狀態(tài)及其轉(zhuǎn)換，掌握進(jìn)程調(diào)度策略。

實(shí)驗(yàn)內(nèi)容

本實(shí)驗(yàn)為單機(jī)模擬進(jìn)程調(diào)度算法，在程序設(shè)計(jì)時(shí)不需真正地建立線程或者進(jìn)程。實(shí)

驗(yàn)?zāi)M創(chuàng)建若干進(jìn)程（人為輸入或隨機(jī)數(shù)產(chǎn)生），選擇一種或幾種單處理機(jī)的進(jìn)程調(diào)度

算法，如FCFS（先來先服務(wù)），SPF（短進(jìn)程優(yōu)先），RR（時(shí)間片輪轉(zhuǎn)法），優(yōu)先級(jí)算法等,

模擬進(jìn)行進(jìn)程調(diào)度。每進(jìn)行一次調(diào)度，都打印一次運(yùn)行進(jìn)程、就緒隊(duì)列、以及各個(gè)進(jìn)程

的PCB,并能在進(jìn)程完成后及時(shí)撤消該進(jìn)程。

實(shí)驗(yàn)原理及設(shè)計(jì)

設(shè)計(jì)一個(gè)按優(yōu)先數(shù)調(diào)度算法實(shí)現(xiàn)處理滯調(diào)度的算法流程描述。

（1）假定系統(tǒng)有五個(gè)進(jìn)程，每一個(gè)進(jìn)程用一個(gè)進(jìn)程控制塊PCB來代表，進(jìn)程控制塊

的格式為：

進(jìn)程名

指針

要求運(yùn)行時(shí)間

優(yōu)先數(shù)

狀態(tài)

進(jìn)程名一一作為進(jìn)程的標(biāo)識(shí)，假設(shè)五個(gè)進(jìn)程的進(jìn)程名分別為Pl,P2,P3,P4,P5。

指針一一按優(yōu)先數(shù)的大小把五個(gè)進(jìn)程連成隊(duì)列，用指針指出下一個(gè)進(jìn)程的進(jìn)程控制

塊的首地址，最后一個(gè)進(jìn)程中的指針為“0”。

要求運(yùn)行時(shí)間一一假設(shè)進(jìn)程需要運(yùn)行的單位時(shí)恒數(shù)。

優(yōu)先數(shù)一一賦予進(jìn)程的優(yōu)先數(shù)，調(diào)度時(shí)總是選取優(yōu)先數(shù)大的進(jìn)程先執(zhí)行。

狀態(tài)一一可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個(gè)進(jìn)程的初始狀態(tài)

都為“就緒”，用“R”表示，當(dāng)一個(gè)進(jìn)程運(yùn)行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”

表示。

(2)在每次運(yùn)行你所設(shè)計(jì)的處理器調(diào)度程序之前，為每個(gè)進(jìn)程任意確定它的“優(yōu)先

數(shù)”和“要求運(yùn)行時(shí)間”,

(3)為了調(diào)度方便，把五個(gè)進(jìn)程按給定的優(yōu)先數(shù)從大到小連成隊(duì)列。用一單元指出

隊(duì)首進(jìn)程，用指針指出隊(duì)列的連接情況。例：

隊(duì)首標(biāo)志

K,KK

PiK2P23P3K4P45P5

0K4K5K3Ki

23124

15342

RRRRR

PCB1PCB2PCB3PCB4PCB5

(4)處理器調(diào)度總是選隊(duì)首進(jìn)程運(yùn)行。采用動(dòng)態(tài)改變優(yōu)先數(shù)的辦法，進(jìn)程每運(yùn)行一

次優(yōu)先數(shù)就減“1”。由于本實(shí)驗(yàn)是模擬處理器調(diào)度，所以，對(duì)被選中的進(jìn)程并不實(shí)際

的啟動(dòng)運(yùn)行，而是執(zhí)行：

優(yōu)先數(shù)-1

要求運(yùn)行時(shí)間-1

來模擬進(jìn)程的一次運(yùn)行。

提醒注意的是：在實(shí)際的系統(tǒng)中，當(dāng)一個(gè)進(jìn)程被選中運(yùn)行時(shí).，必須恢復(fù)進(jìn)程的現(xiàn)場(chǎng),

讓它占有處理器運(yùn)行，直到出現(xiàn)等待事件或運(yùn)行結(jié)束。在這里省去了這些工作°

(5)進(jìn)程運(yùn)行一次后，若要求運(yùn)行時(shí)間M,則再將它加入隊(duì)列(按優(yōu)先數(shù)大小插入,

且置隊(duì)首標(biāo)志)；若要求運(yùn)行時(shí)間=0,則把它的狀態(tài)修改成“結(jié)束”(E),且退出隊(duì)列。

(6)若“就緒”狀態(tài)的進(jìn)程隊(duì)列不為空，則重復(fù)上面(4)和(5)的步驟，直到所

有進(jìn)程都成為“結(jié)束”狀態(tài)。

(7)在所設(shè)計(jì)的程序中應(yīng)有顯示或打印語句，能顯示或打印每次被選中進(jìn)程的進(jìn)程

名以及運(yùn)行一次后進(jìn)程隊(duì)列的變化。

(8)為五個(gè)進(jìn)程任意確定一組“優(yōu)先數(shù)”和“要求運(yùn)行時(shí)間”，啟動(dòng)所設(shè)計(jì)的處理

器調(diào)度程序，顯示或打印逐次被選中進(jìn)程的進(jìn)程名以及進(jìn)程控制塊的動(dòng)態(tài)變化過程。

開始

圖1優(yōu)先權(quán)進(jìn)程調(diào)度流程圖

實(shí)驗(yàn)條件

1、裝有Windows操作系統(tǒng)的微型計(jì)算機(jī)；

2、BorlandC++軟件,

實(shí)驗(yàn)過程

1、根據(jù)實(shí)驗(yàn)預(yù)習(xí)階段的實(shí)驗(yàn)設(shè)計(jì)方案，編寫應(yīng)用程序。參考代碼如下。

#include"stdio.h"

#include<stdlib.h>

#include<conio.h>

#definegetpch(type)(type*)nialloc(sizeof(type))

#dcfincNULLO

structpcb{/*定義進(jìn)程控制塊PCB*/

cliarnaiiie[10];

charstate;

in(super;

inintime;

in(rtime;

structpcb*link;

}*ready=NULL,*p;

typedefstructpcbPCB;

voidsort()/*建立對(duì)進(jìn)程進(jìn)行優(yōu)先級(jí)排列函數(shù)*/

}

voidinputo/*建立進(jìn)程控制塊函數(shù)*/

{

inti,num;

printf("\n請(qǐng)輸入進(jìn)程數(shù)量?)

scanf(u%d",&num);

for(i=0;i<num:i++)

(

printfC'Vn進(jìn)程號(hào)No.%d:\n';i);

p=getpch(HCB);

printf("\n輸入進(jìn)程名

scanf("%s",p->name);

prinlfC'Vn輸入進(jìn)程優(yōu)先數(shù):")；

scanf("%d",&p->super);

printf("\n輸入進(jìn)程運(yùn)行時(shí)間:")；

scanf("%d".&p->ntime);

pnntf(M\n");

p->rtime=O;p->state=,w';

p->link=NULL;

sort。;/*調(diào)用sort函數(shù)*/

intspace()

{

int1=0;PCB*pr=ready;

while(pr!=NULL)

(

1++；

pr=pr->link;

)

return(l);

)

voiddisp(PCB*pr)/*建立進(jìn)程顯示函數(shù)，用于顯示當(dāng)前進(jìn)程*/

{

prinlf("\nqname\tstate\tsuper\tndtime\truntime\n");

printf("|%s\t",pr->name);

printf(H|%c\t",pr->state);

printf("|%d\t",pr->super);

printf("|%d\t",pr->ntime);

printf("|%d\t",pr->rtime);

printf("\n");

)

voidcheck()/*建立進(jìn)程查看函數(shù)*/

PCB*pr;

printf("\n****當(dāng)前iE在運(yùn)行的進(jìn)程是:％$",p->name);/*顯示當(dāng)前運(yùn)行進(jìn)程*/

disp(p);

pr=ready;

piintf("\n**"當(dāng)前就緒隊(duì)列狀態(tài)為:\n”);/*顯示就緒隊(duì)列狀態(tài)*/

while(pr!=NULL)

|

disp(pr);

pr=pr->link;

)

)

voiddestroy。/*建立進(jìn)程撤消函數(shù)(進(jìn)程運(yùn)行結(jié)束撤消進(jìn)程)*/

{

prinlf("\n進(jìn)程［%s］已完成.\n",p->name);

free(p);

I

voidrunningO/*建立進(jìn)程就緒函數(shù)(進(jìn)程運(yùn)行時(shí)間至(置就緒狀態(tài)*/

|

(p->rtime)++;

if(p->rtime==p->ntinie)

dcstroyO;/*調(diào)用destroy函數(shù)*/

else

(

(p->super)-;

p->stale=,w';

sort();/*調(diào)用sort函數(shù)*/

I

)

voidmain()/*主函數(shù)*/

(

intlen,h=0;

charch;

input。；

lcn=space();

whilc((lcn!=O)&&(rcady!=NULL))

(

ch=getchar();

h++;

printf("\nTheexecutenumber:%d\n",h);

p=ready;

ready=p->link;

p->link=NULL;

p->state='R';

check();

runningO;

printf(H\n按任一鍵繼續(xù)");

ch=getchar();

printf("\n\n進(jìn)程已經(jīng)完成An");

ch=getchar();

)

2、編譯、鏈接、運(yùn)行程序

實(shí)驗(yàn)要求

1、完成上述實(shí)驗(yàn)示例程序，按照優(yōu)先級(jí)算法補(bǔ)充出sort。子程序的內(nèi)容。

2、分析結(jié)果含義并寫出自己的心得體會(huì)。

思考題

1、若實(shí)驗(yàn)內(nèi)容中，在修改優(yōu)先數(shù)時(shí)增加下列原則：進(jìn)程等待的時(shí)間超過某一時(shí)限

時(shí)增加其優(yōu)先數(shù)，參考上述例程，寫出程序。

2、若采用基于時(shí)間片輪轉(zhuǎn)的調(diào)度算法模擬進(jìn)程調(diào)度，試設(shè)計(jì)算法與程序。

實(shí)驗(yàn)二動(dòng)態(tài)資源分配實(shí)驗(yàn)

基本信息

實(shí)驗(yàn)課程：計(jì)算機(jī)操作系統(tǒng)設(shè)課形式：非獨(dú)立

課程學(xué)分：4實(shí)驗(yàn)項(xiàng)目：資源分配

項(xiàng)目類型：設(shè)計(jì)項(xiàng)目學(xué)時(shí)：4

實(shí)驗(yàn)?zāi)康?/p>

本實(shí)習(xí)要求學(xué)生編寫和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生

的條件，并采用適當(dāng)銀行家算法，有效地防止和避免死鎖的發(fā)生。

實(shí)驗(yàn)內(nèi)容

利用銀行家算法實(shí)現(xiàn)進(jìn)程的動(dòng)態(tài)資源分配。對(duì)進(jìn)程運(yùn)行過程中提出的資源請(qǐng)求進(jìn)行

檢查，若分配后系統(tǒng)處于安全狀態(tài)，則滿足請(qǐng)求，否則拒絕申請(qǐng)。

實(shí)驗(yàn)原理及設(shè)計(jì)

1.銀行家算法基本思想

先對(duì)用戶提出的請(qǐng)求進(jìn)行合法性檢查，即檢查請(qǐng)求的是不大于需要的，是否不大

于可利用的。若請(qǐng)求合法，則進(jìn)行試分配。最后對(duì)試分配后的狀態(tài)調(diào)用安全性檢查算法

進(jìn)行安全性檢查。若安全，則分配，否則,不分配，恢復(fù)原來狀態(tài)，拒絕申請(qǐng)C

2.銀行家算法中用到的主要數(shù)據(jù)結(jié)構(gòu)

可利用資源向量intAvailable[j]j為資源的種類。

最大需求矩陣intMax[i][j]i為進(jìn)程的數(shù)量。

分配矩陣intAllocation[i][j]

需求矩陣inineed[i][j]=Max[i][j]-Allocaiion[i]fjl

申請(qǐng)各類資源數(shù)量iniRequestiU]i進(jìn)程申請(qǐng)j資源的數(shù)量

工作向量imWork[xJintFinish[y]

3.銀行家算法bank。

進(jìn)程i發(fā)出請(qǐng)求申請(qǐng)k個(gè)j資源，Requesti[j]=k

(1)檢查申請(qǐng)量是否不大于需求量：Requesti[j]<:need[i,j],若條件不符重新輸入，不

允許申請(qǐng)大于需求量。

(2)檢查申請(qǐng)量是否小于系統(tǒng)中的可利用資源數(shù)量：Requesti[j]<=available[i,j],若

條件不符就申請(qǐng)失敗，阻塞該進(jìn)程，用gol。語句跳轉(zhuǎn)到重新申請(qǐng)資源。

(3)若以上兩個(gè)條件都滿足，則系統(tǒng)試探著將資源分配給申請(qǐng)的進(jìn)程，并修改下面

數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[i,j]=Available[i,j]-Requesti[j]；

Allocation[i][j]=Allocation[i][j]+Requesti[j]；

need[i][j]=need[i][j]-Requesti[j]；

(4)試分配后，執(zhí)行安全性檢查，調(diào)用safe。函數(shù)檢查此次資源分配后系統(tǒng)是否處于

安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程；否則本次試探分配作廢，恢復(fù)原來的資

源分配狀態(tài)，讓該進(jìn)程等待。

(5)用do{…}while循環(huán)語句實(shí)現(xiàn)輸入字符y/n判斷是否繼續(xù)進(jìn)行資源申請(qǐng)。

4.安全性檢查算法(safe。函數(shù))

(1)設(shè)置兩個(gè)向量：

工作向量Work,它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，在執(zhí)行

安全性算法開始時(shí)，Work=Availableo

Finish,它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做

Finish用=0；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，再令Finish[i]=l。

(2)在進(jìn)程中查找符合以下條件的進(jìn)程：

條件1；Finish[i]=O；

條件2：need[i]|j]<=Work|j]

若找到，則執(zhí)行步驟⑶否則，執(zhí)行步驟(4)

(3)當(dāng)進(jìn)程獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)

執(zhí)行：

Work[j]=Work[j]+Allocation]皿;

Finish[i]=l；

gotostep2；

(4)如果所有的Finish[i]=l都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全

狀態(tài)。

5、算法流程如圖2所示。

6、具體實(shí)驗(yàn)設(shè)計(jì)

(1)設(shè)計(jì)一個(gè)3個(gè)并發(fā)進(jìn)程共享10個(gè)同類資源的系統(tǒng)，進(jìn)程可動(dòng)態(tài)地申請(qǐng)資源和釋

放資源，系統(tǒng)按各進(jìn)程的申請(qǐng)動(dòng)態(tài)地分配資源。

(2)用銀行家算法，實(shí)現(xiàn)資源分配程序，應(yīng)具有顯示或打印各進(jìn)程依次要求申請(qǐng)的資

源數(shù)以及依次分配資源的情況。

(3)打印輸出銀行家算法的資源申請(qǐng)情況和安全性狀況。

實(shí)驗(yàn)條件

1、裝有Windows操作系統(tǒng)的微型計(jì)算機(jī)；

2^BorlandC++軟件c

J_____初始化函數(shù)chushihua()開始_____1

圖2銀行算法模擬流程

實(shí)驗(yàn)過程

1、根據(jù)實(shí)驗(yàn)預(yù)習(xí)階段的實(shí)驗(yàn)設(shè)計(jì)方案，編寫應(yīng)用程序。參考代碼如下。

#includc<iostream.h>

#include<stdio.h>

#includc<stdlib.h>

#include<slring.h>

〃定義全局變量

constintx=10,y=10;〃常量，便于修改

intAvailable[x];〃各資源可利用的數(shù)量

in(Allocation[y][y];〃各進(jìn)程當(dāng)前已分配的資源數(shù)量

intMax[y][y];〃各進(jìn)程對(duì)各類資源的最大需求數(shù)

intNeed[y][y];〃尚需多少資源

intRequest[x];〃申請(qǐng)多少資源

intWork[x];〃工作向量，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)量

inlFinish[y];〃表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，1為是

intp[y];〃存儲(chǔ)安全序列

inti,j;〃i表示進(jìn)程，j表示資源

intn,m;〃n為進(jìn)程i的數(shù)量,m為資源j種類數(shù)

int1=0;//I用來記錄有幾個(gè)進(jìn)程是FinishliJ=l的，當(dāng)l=n是說明系統(tǒng)狀態(tài)是安全的

in(counter=0;

〃函數(shù)聲明

voidchushihua();〃初始化函數(shù)

voidsafe();〃安全性算法

voidshow();〃函數(shù)show,輸出當(dāng)前狀態(tài)

voidbank();〃銀行家算法

voidjieshuO;〃結(jié)束函數(shù)

voidchushihua()

(

coutvv”輸入進(jìn)程的數(shù)量：”;〃從此開始輸入有關(guān)數(shù)據(jù)

cin?n;

COUIVV”輸入資源種類數(shù)：”；

cin?m;

cout?endl<〈”輸入各種資源當(dāng)前可用的數(shù)量(種):"?endl;

for(j=0;j<m;j++)

(

couivv”輸入資源"vvjvv”可利用的數(shù)量AvailaMe「'wjvv"]:"；

cin?Available|j]；〃輸入數(shù)字的過程…

Work[j]=AvailableJl;〃初始化Workfj],它的初始值就是當(dāng)前可用的資源數(shù)

)

coutvvendlvv"輸入各進(jìn)程當(dāng)前已分配的資源數(shù)量Allocation["?n?"]["?m?"]:

"?cndl;

for(i=0;i<n;i++)

for(j=0;j<m;j++)

cout?"輸入進(jìn)程"?i?"當(dāng)前已分配的資源"?j?"數(shù)量：”；

cin?AIIocationli]|j];

)

cout?endl;

Finish[i]=O;〃初始化Finish[i]

I

coutvvendlvv”輸入各進(jìn)程對(duì)各類資源的最大需求Max["?n?"]["?m?"]:"?endl：

for(i=0;i<n;i++)

(

for(j=0;j<m;j++)

I

cout?H輸入進(jìn)程"?i?"對(duì)資源"?j?M的最大需求數(shù):"；

cin?Max|il(j];

if(Max[i]U]>=AHocation1]U])〃若最大需求大于己分配，則計(jì)算需求量

Need[i][j]=Max[i][j]-Allocation[i][j];

else

Nccd[i][j]=O;〃Max小于已分配的時(shí)候，此類資源己足夠不需再申請(qǐng)

(

cout?endl;

}

coutvvendlvv"初始化完成"vvendl;

)

〃安全性算法函數(shù)

voidsafe()

(

}

〃顯示當(dāng)前狀態(tài)函數(shù)

voidshow?！ê瘮?shù)show,輸出當(dāng)前資源分配情況

{

inti,j;〃局部變量

iniA*y];〃各種資源的總數(shù)量

intLl;〃局部變量U

couivv”當(dāng)前的狀態(tài)為:"?endl;

cout<<”各種資源的總數(shù)量:"《endl;

for(j=O;j<nKj++)

|

cout?"資源

All[j]=Available[j];〃總數(shù)量二可用的+已分配的

for(i=0;i<n;i++)Ali[j]+=Allocation[i][j];

cout?All[j]?""；

)

cout?endl?"^前各種資源可用的量為(available):"?endl;

for(j=O;j<m;j++)

coul<<“資源,,?Available[j]?"”；

coutvvendlvv"各進(jìn)程已經(jīng)得到的資源量(allocation):"?endl;

fbr(i=0;i<=m;i++)

(

for(j=iy<my++)cout?"資源"<<j;

cout?endl;

for(L1=O;Ll<n;Ll++)

{

coutvv”進(jìn)程"vvLlvv":";

for(j=i;j<m;j++)cout?Allocation[L1][j

cout?endl;

)

}

cout?endlv<"各進(jìn)程還需要的資源量(need):"?endl;

for(i=0;i<=m;i++)

(

for(j=i;j<m;j++)cout?"資源"<vj;

cou(?endl;

for(Ll=0;Ll<n;Ll十十)

I

cout?"進(jìn)程"<vLl?":"；

for(j=i;j<m;j+-)cout?Need[Ll

cout?endl;

〃銀行家算法函數(shù)

voidbank()

{

cout?endl<v"進(jìn)程申請(qǐng)分配資源："〈〈endI;

intk=0;//用于輸入進(jìn)程編號(hào)

boolr=false;〃初值為假，輸入Y繼續(xù)申請(qǐng)則置為真

do{〃輸入請(qǐng)求

cout<〈”輸入申請(qǐng)資源的進(jìn)程("<<n-l<<"):

cin?k;

cout?endl;

while(k>n-l)〃輸入錯(cuò)誤處理

{

coutvvendlvv”輸入錯(cuò)誤，重新輸入：”《endl;

cout?endl?"^A申請(qǐng)資源的進(jìn)程(0」《n-1vv")：

cin?k;

cout?endl;

)

cout?endl<<"輸入該進(jìn)程申請(qǐng)各類資源的數(shù)量:"?endl;

for(j=0;j<m;j++)

do{//dowhile循環(huán)判斷申請(qǐng)輸入的情況

coutv<”進(jìn)程H?k?"申請(qǐng)資源的數(shù)量:"；

cin?Request[j];

cout?endl;

if(Request[jl>Need[k][jl){〃申請(qǐng)大于需求量時(shí)出錯(cuò)、提示重新輸入(貸款數(shù)目不允許

超過需求數(shù)目)

cout<v”申請(qǐng)大于需要量!"?endl;

coutvv”申請(qǐng)的資源""jvv”的數(shù)量為“vvRequesl[jkv”,大于進(jìn)程"wkvv”對(duì)該資源

需求量“vvNeed[k][j]vv"。"vvendl;

coutvv”重新輸入!"vvendl;

)

else//先判斷是否申請(qǐng)大于需求量，再判斷是否申請(qǐng)大于可利用量

if(RequestU]>Available[j]){〃申請(qǐng)大于可利用量，應(yīng)該阻塞等待？……？？？

cou(?n\n沒有那么多資源，目前可利用資源"<vj<<"數(shù)量為”《Available[jk<”,本次申

請(qǐng)不成功，進(jìn)程等待!”"endl;

Finish[k]=0;〃該進(jìn)程等待

gotoppp;//goto語句跳轉(zhuǎn)，結(jié)束本次申請(qǐng)

}

}while(Request[j]>Need[k][jJ);//Request[jl>Available[j]||

)

〃改變Avilable、AllocationxNeed的值

for(j=O;j<m;j++){

Availablc[j]=Available[j]-Rcquest[j|;

Alloca(ion[k][j]=Allocation[k][j]+Request[j];

Nccd[k][j]=Need[k][j]-Request[j];

Work[j]=Available[j];

}

〃判斷當(dāng)前狀態(tài)的安全性

safe():〃調(diào)用安全性算法函數(shù)

if(l<n)

(

1=0;

cout?"\n試分配后，狀態(tài)不安全，所以不予分配!恢復(fù)原狀態(tài)”《endl;

〃恢復(fù)數(shù)據(jù)

for(j=0;j<m;j++)

(

Availablc(jJ=Availablc[jJ+Rcqucst|j];

Allocation[k]|j]=Allocation[k][j]-Requestfj];

Nccd[k][j]=Nccd[k][j]+Rcqucst|j];

Work[j]=Availablefjl;

}

for(i=0;i<n;i++)

Finish[i]=0;〃進(jìn)程置為未分配狀態(tài)

I

else

1=0;

cout?"\n申請(qǐng)資源成功!!!”<<endl;

for(j=0;j<m;j++)

{

if(Need[k][j]==0);

else{〃有一種資源還沒全部申請(qǐng)到，則該進(jìn)程不可執(zhí)行，不能釋放擁有的資源

1=1；〃置1為1,作為判斷標(biāo)志

break;

)

)

if(l!=i){〃進(jìn)程可以執(zhí)行，則釋放該進(jìn)程的所有資源

for(j=0;j<m;j++){

Available(j]=Available[j]+Allocation[k][j];

Allocation|k]|j]=0;

}

cout<〈”該進(jìn)程已得到所有需求資源，執(zhí)行后將釋放其所有擁有資源！"<<endl;

)

1=0;〃歸零

cout?"\n安全的狀態(tài)!”vvendl;

cout<〈”安全序列為：

cout<<endl<<“進(jìn)程“<v"("vvp⑼<<")"；〃輸出安全序列，考慮顯示格式，先輸出第一

個(gè)

Finish[0]=0;

fbr(i=l;i<n;i++){

cout<<"==>>”<<“進(jìn)程”<<"("<<p[i]<<")”；

Finish川=0;〃所有進(jìn)程置為未分配狀態(tài)

}

cout?endl?endl;

I

show();//顯示當(dāng)前狀態(tài)

ppp：〃申請(qǐng)大于可利用量，應(yīng)該阻塞等待，結(jié)束本次資源申請(qǐng)，GOTO語句跳轉(zhuǎn)至此

cout?endl<<”是否繼續(xù)申請(qǐng)資源(y/n)?”；

char*b=newchar;〃輸入y/n,判斷是否繼續(xù)申請(qǐng)?endl

cin?b:

cout?endl;

cout?",,?endl?endl;

cout?cndl;

if(*b=='y,||*b==,Y')

r=true;

else{

r=false;〃輸入非Y則令R=false

jieshuO;〃調(diào)用結(jié)束函數(shù)

)

}while(r==truc);

〃結(jié)束函數(shù)

voidjieshu()

cout?endl?endl;

coui?"\t\l演示計(jì)算完畢"wendl;

cout?endl?endl;

)

〃主函數(shù)

intmain()

{

cout?endl?endl?','.t\t\t\t模擬銀行家算法"vvendlv<endl;

chush由ua();〃初始化函數(shù)調(diào)用

cout?endl;

show();〃輸出當(dāng)前狀態(tài)

safe();〃判斷當(dāng)前狀態(tài)的安全性

if(l<n)//I在safe中是用來記錄安全的進(jìn)程的個(gè)數(shù)的

{

coutvv”\n當(dāng)前狀態(tài)不安全，拒絕申請(qǐng)！"vvendl;

cout?endl;

return0;

)

else

(

inti;〃局部變量

1=0;

8111<<33<<”\11當(dāng)前的狀態(tài)是安全的!安全序列為:“<<55;

coutvv”進(jìn)程“vv"(“vvp⑼《")”；〃輸出安全序列

for(i=l;i<n;i++)coutvv"?》“v<“進(jìn)程“<v"("<<p[i]vv”)”；

for(i=0;i<n;i++)Finish[i]=0;〃所有進(jìn)程置為未分配狀態(tài)

cout?endl;

I

bank();〃調(diào)用銀行家算法函數(shù)

cout?M\t\t演示計(jì)算完畢"vvendl;

return0;

)

2、編譯、鏈接、運(yùn)行程序。

實(shí)驗(yàn)要求

1、完成上述實(shí)驗(yàn)示例程序，按照銀行家算法流程補(bǔ)充出safe。函數(shù)即安全性檢測(cè)

算法的內(nèi)容.

2、分析bank。中的多種判斷的含義以及數(shù)據(jù)結(jié)構(gòu)的變化。

3、思考銀行家算法中引入安全性檢測(cè)的目的。

4、寫出自己的心得體會(huì)。

思考題

如何實(shí)現(xiàn)并發(fā)執(zhí)行的進(jìn)程對(duì)資源的動(dòng)態(tài)申請(qǐng)和動(dòng)態(tài)分配。

實(shí)驗(yàn)三請(qǐng)求頁式存儲(chǔ)管理

基本信息

實(shí)驗(yàn)課程：計(jì)算機(jī)操作系統(tǒng)設(shè)課形式：非獨(dú)立

課程學(xué)分：4實(shí)驗(yàn)項(xiàng)目：存儲(chǔ)器管理實(shí)驗(yàn)

項(xiàng)目類型：綜合項(xiàng)目學(xué)時(shí)：6

實(shí)驗(yàn)?zāi)康?/p>

用C/C++編寫和調(diào)試虛擬內(nèi)存管理的模擬程序，通過虛存管理的地址轉(zhuǎn)換過程和各

種頁面淘汰算法的編程實(shí)現(xiàn)，加深對(duì)存儲(chǔ)管理方案的理解。

實(shí)驗(yàn)內(nèi)容

根據(jù)虛擬內(nèi)存管理的請(qǐng)求分頁管理機(jī)制，設(shè)計(jì)頁表結(jié)構(gòu)，模擬實(shí)現(xiàn)虛存管理中邏輯

地址到物理地址的轉(zhuǎn)換，按照先進(jìn)先出頁面淘汰算法模擬實(shí)現(xiàn)缺頁中斷處理及頁面置

換，并輸出顯示執(zhí)行和置換過程。

實(shí)驗(yàn)原理及設(shè)計(jì)

1、設(shè)計(jì)頁表。分頁式虛擬存儲(chǔ)系統(tǒng)是把作業(yè)的副本存放在磁盤上，當(dāng)作業(yè)被選中

時(shí)，可把作業(yè)的開始幾頁先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁表時(shí)，應(yīng)說明

哪些頁已在主存，哪些頁尚未裝入主存，頁表的格式為：

頁號(hào)標(biāo)志主存塊號(hào)在磁盤上的位置

2、地址計(jì)算。作業(yè)執(zhí)行時(shí)?，指令中的邏輯地址指出了參加運(yùn)算的操作數(shù)存放的頁

號(hào)和單元號(hào)，硬件的地址轉(zhuǎn)換機(jī)構(gòu)按頁號(hào)查頁表，若該頁對(duì)應(yīng)標(biāo)志為“1”，則表示該頁

己在主存，這時(shí)根據(jù)關(guān)系式：

絕對(duì)地址=塊號(hào)*塊長(zhǎng)單元號(hào)

計(jì)算出欲訪問的主存單元地址。按計(jì)算出的絕對(duì)地址可以取到操作數(shù)，完成一條指

令的執(zhí)行。若訪問的頁標(biāo)志為“0”，則表示該頁不在主存，這時(shí)硬件發(fā)“缺頁中斷”信

號(hào)，由OS按該頁在磁盤上的位置，把該頁信息從磁盤讀出裝入主存后再重新執(zhí)行這條

指令。

3、設(shè)計(jì)“地址轉(zhuǎn)換”程序模擬硬件的地址轉(zhuǎn)換工作。當(dāng)訪問的頁在主存時(shí)，則形

成絕對(duì)地址，但不去模擬指令的執(zhí)行，而用輸出轉(zhuǎn)換后的地址來代替一條指令的執(zhí)行。

當(dāng)訪問的頁不在主存時(shí)，則輸出“*該頁頁號(hào)”，表示產(chǎn)生了一次缺頁中斷，執(zhí)行缺頁中

斷程序。該模擬程序的算法如圖3所示。

圖3地址轉(zhuǎn)換模擬流程圖

4、缺頁中斷模擬。如果訪問頁不在主存且頁表未滿，則調(diào)入一頁并打印頁表情況;

如果該頁不在主存且頁表已滿，則產(chǎn)生缺頁中斷，模擬算法如圖4所示。

實(shí)驗(yàn)中采用FIFO算法進(jìn)行頁面淘汰。把在主存的頁的頁號(hào)按進(jìn)入主存的先后次序

排成隊(duì)列，每次總是調(diào)出隊(duì)首頁。用數(shù)組存放頁號(hào)的隊(duì)列。若分配給該作業(yè)的物理塊數(shù)

為m,則數(shù)組由m個(gè)元素組成，p[0bp[l]p[m-l],隊(duì)首指針head,隊(duì)尾指針tail。

當(dāng)裝入新頁時(shí)，將其頁號(hào)裝入數(shù)組。

5、具體實(shí)驗(yàn)設(shè)計(jì)。

(1)假定主存的每塊長(zhǎng)度為128個(gè)字節(jié)；現(xiàn)有一個(gè)共七頁的作業(yè)，其中的第0頁至第3

頁已經(jīng)裝入主存，其余三頁未裝入主存，主存；該作業(yè)的頁表為：

015011

118012

219013