目錄

任務(wù)一2

任務(wù)二4

任務(wù)三13

任務(wù)四19

任務(wù)五25

實(shí)訓(xùn)總結(jié)36

任務(wù)一分析操作系統(tǒng)所面臨的操作需求

【實(shí)訓(xùn)目的】

讓學(xué)生可以更好的理解、掌握和應(yīng)用操作系統(tǒng)中的進(jìn)程管理、存儲管理、設(shè)備管理和文

件管理等功能。

【實(shí)訓(xùn)內(nèi)容】

1.熟悉實(shí)訓(xùn)環(huán)境；

2.分析操作系統(tǒng)的操作需求；

3.資料搜集與整理，進(jìn)行實(shí)訓(xùn)的前期準(zhǔn)備。

【實(shí)訓(xùn)步驟】

1.分析與設(shè)計(jì)

模擬操作系統(tǒng)

進(jìn)程管理存儲管理

先

兩

生產(chǎn)者與消最

進(jìn)程調(diào)度

進(jìn)

近

費(fèi)者問題種

先

最

淘

出

少

汰

先短高

淘

使M

來作優(yōu)

汰

用

法

先業(yè)

先算

淘

比

服優(yōu)權(quán)法

汰

較

務(wù)先優(yōu)算

尊算先法

法法篇

法

2

圖IT實(shí)訓(xùn)總體結(jié)構(gòu)圖

【思考題】

1.操作系統(tǒng)中各模塊有怎樣的功能？

答：進(jìn)程管理模塊用于分配和控制處理機(jī)；設(shè)備管理模塊主要負(fù)責(zé)對I/O設(shè)備的分

配與操縱；文件管理模塊主要負(fù)責(zé)文件的存取、共享和保護(hù)；存儲管理模塊主要負(fù)責(zé)的

分配與回收。

2.它們之間有怎樣的聯(lián)系？

答：設(shè)備管理、文件管理和儲存管理都需要進(jìn)程的管理；文件需要文件管理進(jìn)行存

儲，同時也需要儲存管理來對文件存儲分配空間等等。

3.針對某一特定的應(yīng)用環(huán)境，如何完善操作系統(tǒng)的功能？

答：要想完善操作系統(tǒng)的功能，必須要合理安排各個功能模塊，并利用有效的算法

對各個功能進(jìn)行管理和處理。

任務(wù)二進(jìn)程管理

【實(shí)訓(xùn)目的】

掌握臨界區(qū)的概念及臨界區(qū)的設(shè)計(jì)原則；掌握信號量的概念、PV操作的含義以及應(yīng)用P

V操作實(shí)現(xiàn)進(jìn)程的同步與互斥；分析進(jìn)程爭用資源的現(xiàn)象，學(xué)習(xí)解決進(jìn)程互斥的方法；掌握

進(jìn)程的狀態(tài)及狀態(tài)轉(zhuǎn)換；掌握常用的進(jìn)程調(diào)度算法。

【實(shí)訓(xùn)內(nèi)容】

1.分析進(jìn)程的同步與互斥現(xiàn)象，編程實(shí)現(xiàn)經(jīng)典的進(jìn)程同步問題——生產(chǎn)者消費(fèi)者問題的

模擬；

2.編寫允許進(jìn)程并行執(zhí)行的進(jìn)程調(diào)度程序，在常用的進(jìn)程（作業(yè)）調(diào)度算法：先來先服

務(wù)算法、短作業(yè)優(yōu)先算法、最高響應(yīng)比優(yōu)先算法、高優(yōu)先權(quán)優(yōu)先算法等調(diào)度算法中選擇種

調(diào)度算法進(jìn)行簡單模擬，并輸出平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。

3

【實(shí)訓(xùn)步驟】

一.生產(chǎn)者與消費(fèi)者問題

1.分析與設(shè)計(jì)

圖2-1生產(chǎn)者與消費(fèi)者問題分析圖

2.程序代碼

^include<windows.h>

#include<iostream>

constunsignedshortBUFFER=5;〃緩沖區(qū)長度

unsignedshortProductID=0;〃產(chǎn)品號

unsignedshortConsumelD=0;//將被消耗的產(chǎn)品號

unsignedshortin=0;//產(chǎn)品進(jìn)緩沖區(qū)時的緩沖區(qū)產(chǎn)品個數(shù)

4

unsignedshortout=0;〃產(chǎn)品出緩沖區(qū)時的緩沖區(qū)產(chǎn)品個數(shù)

intg_buffer[BUFFER];〃緩沖區(qū)為循環(huán)隊(duì)列

boolg_continue=true;〃控制程序結(jié)束

HANDLEg_hMutex;//線程間互斥對像

HANDLEg_hFullSemaphore;〃滿則生產(chǎn)者等待

HANDLEg_hEmptySemaphore;〃空則消費(fèi)者等待

DWORDWINAPIProducer(LPVOID);//生產(chǎn)者線程

DWORDWINAPIConsumer(LPVOID);〃消費(fèi)者線程

〃主程序

intmain()

(

〃創(chuàng)建各個互斥信號

g_hMutex=CreateMutex(NULL,FALSE,NULL);

g_hFu11Semaphore=CreateSemaphore(NULL,BUFFER-1,BUFFER-1,NULL);

g_hEmptySemaphore=CreateSemaphore(NULL,0,BUFFER-1,NULL);

constunsignedshortPRODUCERS_COUNT=2;//生產(chǎn)者的個數(shù)

constunsignedshortCONSUMERS_COUNT=1;〃消費(fèi)者的個數(shù)

〃總的線程數(shù)

constunsignedshortTHREADS_COUNT=PRODUCERS工OUNT+CONSUMERS_COUNT;

HANDLEhThreads[PRODUCERS_COUNT];〃各線程的handle

DWORDproducerlD[CONSUMERSCOUNT];〃生產(chǎn)者線程的標(biāo)識符

DWORDconsumerID[THREADS_COUNT];〃消費(fèi)者線程的標(biāo)識符

〃創(chuàng)建生產(chǎn)者線程

for(inti=0;i<PRODUCERSCOUNT;++i)

hThreads[i]=CreateThread(NULL,0,Producer,NULL,0,&producerID[i]);

if(hThreads[i]==NULD

return-1;

)

〃創(chuàng)建消費(fèi)者線程

for(i=0;iCONSUMERSCOUNT;++i)

(

hThreads[PRODUCERS_COUNT+i]=CreateThread(NULL,0,Consumer,NULL,0,&consumerID[i]);

if(hThreads[i]==NULL)

return-1;

)

while(g_continue)

(

if(getchar())

(

gcontinue=false;〃按回車后終止程序運(yùn)行

}

)

return0;

}

〃生產(chǎn)一個產(chǎn)品，把新生產(chǎn)的產(chǎn)品放入緩沖區(qū)

voidProduce()

5

std::cerr?〃生產(chǎn)產(chǎn)品〃?++ProductID<<std::endl;

std::cerr<<“將新的產(chǎn)品”;

g_buffer[in]=ProductID;

in=(in+l)%BUFFER;

std::cerr?〃放入緩沖區(qū)"?std::endl;

〃輸出緩沖區(qū)當(dāng)前的狀態(tài)

for(inti=O;i<BUFFER;++i)

(

std::cout?i<<〃：〃<<g_buffer[i];

if(i二二in)std::cout?〃=生產(chǎn)〃；

if(i==out)std::cout?〃一消費(fèi)〃；

std::cout?std::endl;

)

)

〃從緩沖區(qū)中取出一個產(chǎn)品，并將其消耗

voidConsume()

(

std::cerr?〃從緩沖區(qū)中取出產(chǎn)品〃；

ConsumelD=g_buffer[out];

out=(out+l)%BUFFER;

std::cout?std::endl;

〃輸出緩沖區(qū)當(dāng)前的狀態(tài)

for(inti=0;i〈BUFFER;++i)

(

std::cout?i<<":〃?g_buffer[i];

if(i==in)std::cout?〃一壬產(chǎn)〃；

if(i==out)std::cout?〃一消費(fèi)”;

std::cout?std::endl;

)

std::cerr?〃消耗一個產(chǎn)品〃<<ConsumelD?std::endl;

)

〃生產(chǎn)者

DWORDWINAPIProducer(LPVOIDIpPara)

(

while(gcontinue)

(

WaitForSingleObject(ghFullSemaphore,INFINITE);

WaitForSingleObject(g_hMutex,INFINITE);

Produce0;

Sleep(1500);〃此處以毫秒為單位

ReleaseMutex(g_hMutex);

ReleaseSemaphore(ghEmptySemaphore,1,NULL);

)

return0;

)

〃消費(fèi)者

DWORDWINAPIConsumer(LPVOIDIpPara)

while(g_continue)

6

WaitForSingleObject(g_hEmptySemaphore,INFINITE);

WaitForSingleObject(g_hMutex,INFINITE);

Consume();

Sleep(1500);〃此處以毫秒為單位

ReleaseMutex(ghMutex);

Re1easeSemaphore(g_hFu11Semaphore,1,NULL);

)

return0;

)

3.程序運(yùn)行截圖

1?C:\Users\LErnNG\De$ktop\Debug浮揚(yáng),exe*

3：4

4：5y消費(fèi)

道耗一個產(chǎn)品4

生產(chǎn)產(chǎn)品7

將新的產(chǎn)品放入緩沖區(qū)

06

17

E

3-胡

5-消費(fèi)

緩沖區(qū)中里出產(chǎn)品

6*-宿費(fèi)

7

3*-胡

4

澧耗一個產(chǎn)品5

生產(chǎn)產(chǎn)品8

將新的產(chǎn)品放入緩沖區(qū)

0：6一消費(fèi)

1：7

2：8

3：46生產(chǎn)

圖2-2生產(chǎn)者與消費(fèi)者問題運(yùn)行截圖

7

先來先服務(wù)算法

1.分析與設(shè)計(jì)

圖2-3先來先服務(wù)算法設(shè)計(jì)圖

2.程序代碼

ttinclude<stdio.h>

〃定義進(jìn)程的結(jié)構(gòu)體

structfcfs

charname[10];〃進(jìn)程名稱

intpriority;〃進(jìn)程優(yōu)先數(shù)

floatarrivetime;〃到達(dá)時間

floatservicetime;〃運(yùn)行時間

floatstarttime;〃開始時間

floatfinishtime;〃完成時間

floatreturntime;〃周轉(zhuǎn)時間

floatwreturntime;〃帶權(quán)周轉(zhuǎn)時間

8

);

fcfsa[50];

〃程序的輸入顯示及提示

voidinput(fcfs*p,intN)

(

inti;

printf(〃請依次輸入進(jìn)程名稱一到達(dá)時間一運(yùn)行時間一進(jìn)程優(yōu)先數(shù):\n〃)；

for(i=0;i<=N-l;i++)

(

printf(z，\n輸入%d號進(jìn)程信息:\n〃,i+1);

scanf&p[i].name,&p[i].arrivetime,&p[i].servicetime,priority);

)

)

〃程序的輸出顯示

voidPrint(fcfs*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floa

treturntime,floatwreturntime,intpriority,intN)

(

intk;

printf(〃運(yùn)行指令：〃)；

printf(〃％s〃,p[0].name);

for(k=l;k<N;k++)

(

printfp[k].name);

)

printf(，z\n進(jìn)程信息：\n〃);

printfC\n進(jìn)程\t到達(dá)\t運(yùn)行\(zhòng)t開始\t結(jié)束\t周轉(zhuǎn)\t帶權(quán)周轉(zhuǎn)進(jìn)程優(yōu)先數(shù)\n〃)；

for(k=0;k<=N-l;k++)

(

printf(，z%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%~.2f\t%-.2f\t\t%d\n〃，p[k].name,p[k].arr

ivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].returntime,p[k].wretu

rntime,p[k].priority);

)

)

〃排序采用冒泡排序法進(jìn)行排序，排序順序從小到大

voidsort(fcfs*p,intN)

(

for(inti=0;i<=N-l;i++)

for(intj=0;j<=i;j++)

if(p[i].arrivetime<p[j],arrivetime)

(

fcfstemp;

temp=p[i];

p[i>p[jL

p[j]=temp;

)

)

〃運(yùn)行階段

voidfunciton(fcfs*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,

float&returntime,float&wreturntime,intpriority,intN)

9

intk;

for(k=0;k<=N-l;k++)

(

if(p[k].arrivetime>p[k-l].finishtime)

{

p[k].starttime=p[k].arrivetime;

p[k].finishtime二p[k].arrivetime+p[k].servicetime;

)

else

{

p[k].starttime=p[k-l].finishtime;

p[k].finishtime=p[k-1].finishtime+p[k].servicetime;

)

)

for(k=0;k<=N-l;k++)

(

p[k].returntime=p[k].finishtime-p[k].arrivetime;

p[k].wreturntime=p[k].returntime/p[k].servicetime;

)

)

〃模擬操作系統(tǒng)的先來先服務(wù)算法

voidFCFS(fcfs*p,intN)

(

floatarrivetime=O,servicetime=O,starttime=O,finishtime=O,returntime=O,wreturntime=O,pr

iority=0;

sort(p,N);

funciton(p,arrivetime,servicetime,starttime,finishtime,returntime,wreturntime,priority,

N);

Print(p,arrivetime,servicetime,starttime,finishtime,returntime,wreturntime,priority,N);

)

〃主函數(shù)

voidmain()

(

intN;

printf(〃\t\t\t進(jìn)程調(diào)度之先來先服務(wù)調(diào)度算法\n〃)；

printf(〃請輸入進(jìn)程數(shù):\n〃)；

scanf&N);

input(a,N);

FCFS(a,N);

10

3.程序運(yùn)行截圖

圖2-4先來先服務(wù)調(diào)度算法運(yùn)行截圖

【思考題】

1.針對某一具體應(yīng)用環(huán)境，如何選擇合適的調(diào)度算法？

答：應(yīng)根據(jù)具體情況來選用合適的調(diào)度算法。比如，在批處理系統(tǒng)中，為了照顧為

數(shù)眾多的短作業(yè)，應(yīng)采用短作業(yè)優(yōu)先調(diào)度的調(diào)度算法；在分時系統(tǒng)中，為了保證系統(tǒng)具

有合理的響應(yīng)時間，應(yīng)采用輪轉(zhuǎn)法進(jìn)行調(diào)度。非搶占式調(diào)度算法，有利于長作業(yè)，不利

于短作業(yè)。

11

任務(wù)三存儲管理

【實(shí)訓(xùn)目的】

掌握物理內(nèi)存和虛擬內(nèi)存的基本概念；掌握重定位的基本概念及其要點(diǎn)，理解邏輯地址

與絕對地址；掌握各種存儲管理的實(shí)現(xiàn)方法，包括基本原理、地址變換和缺頁中斷、主存空

間的分配及分配算法；掌握常用淘汰算法。

【實(shí)訓(xùn)內(nèi)容】

編寫一個模擬的動態(tài)頁式存儲管理程序，實(shí)現(xiàn)對動態(tài)頁式存儲的淘汰算法的模擬（在先

進(jìn)先出淘汰算法、最近最少使用淘汰算法、最不經(jīng)常使用淘汰算法三種算法中選擇一種進(jìn)行

模擬）并計(jì)算各個算法的缺頁率；并且頁面淘汰算法在淘汰一頁時，只將該頁在頁表中抹去,

而不再判斷它是否被改寫過，也不將它寫回到輔存

【實(shí)訓(xùn)步驟】

1.分析與設(shè)計(jì)

設(shè)置一個后進(jìn)先出棧，棧大小為分配給這個進(jìn)程的頁面數(shù)。在在系統(tǒng)中設(shè)定一個計(jì)數(shù)器,

進(jìn)程進(jìn)程進(jìn)行訪問內(nèi)頁面操作都把計(jì)數(shù)器的值加1,把結(jié)果值賦值給訪問的頁面，在淘汰頁

面時選擇計(jì)數(shù)器值最小的頁面淘汰。這樣的棧頂上總是保存著最近被訪問的頁面號，而棧底

保存的就是最近最久沒有被訪問的頁面號。如圖3-1所示

12

圖37最近最久未使用置換算法分析圖

2.程序代碼

^include<stdio.h>

ttinclude<stdlib.h>

〃最近最久未使用置換算法

〃參數(shù)說明:P地址流,n地址流的個數(shù),pageSize頁面大小，pageTable頁表,count頁表大小

voidLRU(intp[],intn,intpageSize,intpageTable[],intcount)

(

inti,pageNo,j,pagecount,k;

floatsum;

int*stack=(int*)malloc(sizeof(int)*count);

pagecount=0;

k=0;

sum=0;

system(〃cls〃);

13

printf(，z\n\n\t\t\t存儲管理--最近最少使用淘汰算法\n\n〃)；

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

(

pageNo=p[i]/pageSize;

printf(〃\t\t調(diào)入頁號%d后\t〃，pageNo);

printf(〃\t\t頁表:〃)；

for(j=0;j<pagecount;j++)〃判斷頁號是否在頁表中

(

if(pageNo==pageTable[j])〃如果頁號在頁表中

{

for(k=0;k<count;k++)〃設(shè)置棧中各頁面使用情況

(

if(stack[k]==pageNo)

(

if(k!=count-1)

(

for(;k<count-1;k++)

(

stack[k]=stack[k+1];

)

stack[k]=pageNo;

)

)

)

break;

)

)

〃頁號不在頁表中，插入頁表

if(j==pagecount)

(

〃如果頁表不滿

if(pagecount<count)

(

pageTable[pagecount++]=pageNo;

stack[pagecount-1]=pageNo;

)

〃如果頁表已滿

else

(

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

(

if(pageTable[j]==stack[0])

(

pageTable[j]=pageNo;

for(k=0;k<count-1;k++)〃設(shè)置棧中各頁面使用情況

(

stack[k]=stack[k+1];

14

stack[k]=pageNo;

break;

)

)

)

sum++;〃缺頁數(shù)

)

〃打印頁表

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

(

if(pageTable[j]>=0)

(

printf("%d〃，pageTable[j]);

)

)

printf(〃\n〃)；

)

sum/=n;

sum*=100;

printf("\t\t\t缺頁率:%.lf%%\n\nz，,sum);

free(stack);

}

voidmain()

(

intn,pageSize=1024,pageTable[3];

int*p,i;

FILE*fp;

system(〃cls〃);

printf(，z\n\n\t\t\t存儲管理—最近最少使用淘汰算法\n\n\n〃)；

printf(〃請確認(rèn)在\"Address.txt\〃文件中已輸入地址流.\n〃);

printf(〃如果沒有，請自行新建后再運(yùn)行.\n\n\n\n〃)；

system("pause");

if((fp=fopen("Address.txt",〃r+〃))==NULL)

(

printf(〃打開文件出錯!\n〃)；

system("pause");

return;

)

fscanf(fp,〃%d〃，&n);

p=(int*)malloc(sizeof(int)*n);

printf("\n\n\n讀取到以下的地址流:\n〃);

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

15

fscanf(fp,"%d”,&p[i]);

printf(〃%d〃，p[i]);

)

printf(〃\n\n〃)；

fclose(fp);

system("pause");

system(〃cls〃)；

LRU(p,n,pageSize,pageTable,3);

)

3.程序運(yùn)行截圖

圖3-2最近最久未使用置換算法程序截圖

16

■C:\U5R0LETnNG\Desktop\Debug序稼exe,

存儲管理--最近最少使用淘汰算法

入

表

調(diào)

頁號

頁0

入

表

調(diào)

號0.3

-頁03

頁

入

調(diào)

表

號2032

-頁

入

調(diào)

表

號1132

頁-

頁

調(diào)入

表

號-2132

詞入

號

表

頁

0頁102

調(diào)

入

號

1表102

頁

頁-

調(diào)

入

號

7表107

,.頁

調(diào)

號

入

0表107

頁-

頁7

謂10

號

入

1表

齦

率

60.0z

Pressan9keytocontinue

圖3-3最近最久未使用置換算法程序截圖

【思考題】

1.各種不同的頁面淘汰算法有哪些優(yōu)缺點(diǎn)？為什么會產(chǎn)生頁面抖動？什么是belady

現(xiàn)象？這種現(xiàn)象該如何避免？

答：最佳值換算法其所選擇的被淘汰頁將是以后用不適用的，或許是在最長（未來）

時間內(nèi)不再被訪問的頁面。采用最佳值換算法通常可保證獲得最低的缺頁率。但是由于

人們目前還無法預(yù)知一個進(jìn)程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不

再被訪問的，因此該算法是無法實(shí)現(xiàn)的，但可以利用該算法去評價其它算法。先進(jìn)先出

置換算法（FIFO）是最直觀的算法，由于它可能是性能最差的算法，故實(shí)際應(yīng)用極少。

最近最久未使用置換算法（LRU）雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬

件。

因?yàn)閯偙惶蕴鋈サ捻?，過后不久又要訪問它，需要再次調(diào)入，而調(diào)入后不久又再

次被淘汰，然后又要訪問，如此反復(fù)，使得系統(tǒng)的把大部分時間用在頁面的調(diào)進(jìn)調(diào)出上,

這種形象稱為“抖動”。

隨著物理塊數(shù)的增多缺頁率增大，從而造成Belady異?，F(xiàn)象。盡量避免物理塊數(shù)不

斷增多缺頁率最大。

17

任務(wù)四設(shè)備管理

【實(shí)訓(xùn)目的】

掌握獨(dú)占設(shè)備的使用方式，以及設(shè)備的分配和回收；掌握用死鎖避免方法來處理申請獨(dú)

占設(shè)備可能帶來死鎖。

【實(shí)訓(xùn)內(nèi)容】

用死鎖避免方法來處理申請獨(dú)占設(shè)備可能造成的死鎖，程序?qū)崿F(xiàn)對銀行家算發(fā)的模擬。

【實(shí)訓(xùn)步驟】

1、分析與設(shè)計(jì)

1.1、銀行家算法：

設(shè)進(jìn)程x提出請求Request[y],則銀行家算法按如下規(guī)則進(jìn)行判斷。

(1)如果Request[y]>Need[x,y],則報(bào)錯返回。

⑵如果Request[y]>Available,則進(jìn)程i進(jìn)入等待資源狀態(tài)，返回。

(3)假設(shè)進(jìn)程n的申請已獲批準(zhǔn)，于是修改系統(tǒng)狀態(tài)：

Available=Available-Request

Allocation=Allocation+Request

Need=Need-Request

(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀,

進(jìn)程等待。

1.2.安全性檢查：

(1)設(shè)置兩個工作向量Work=Available；Finish[z]=False

(2)從進(jìn)程集合中找到一個滿足下述條件的進(jìn)程，

Finish[x]=False

Need<=Work

如找到，執(zhí)行(3)；否則，執(zhí)行(4)

(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。

Work=Work+Allocation

Finish=True

18

GOTO2

(4)如所有的進(jìn)程Finish[z]=true,則表示安全；否則系統(tǒng)不安全

1.3銀行家算法實(shí)現(xiàn)流程圖，如圖4T所示。

圖4-1銀行家算法實(shí)現(xiàn)流程圖

2、程序代碼

ttinclude<string.h>

#include<stdio.h>

ttinclude<stdlib.h>

#defineX5〃總進(jìn)程數(shù)

ttdefineY3〃總資源數(shù)

〃銀行家算法定義結(jié)構(gòu)體

structbanker

intmax[X][Y];〃最大需求矩陣

intallocation[X][Y];〃分配矩陣

intneed[X][Y];〃需求矩陣

19

intavailable[Y];〃可利用資源向量

)；

〃初始化

voidinitilize(banker&x)

inti,j;

printf(“請輸入數(shù)據(jù)(系統(tǒng)設(shè)定總進(jìn)程數(shù)為5,總資源數(shù)為3):\n");

printf("最大需求矩陣:\n");

for(i=0;i〈X;i++)〃設(shè)置最大需求矩陣

(

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

(

scanf&x.max[i][j]);

)

)

printf("分配矩陣:\n");

for(i=0;i<X;i++)//設(shè)置分配矩陣

(

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

(

scanf("%d”,&x.allocation[i][j]);

)

for(i=0;i<X;i++)〃設(shè)置需求矩陣

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

{

x.need[i][j]=x.max[i][j]-x.allocation[i][j];

)

)

printf(〃可利用資源向量:\n");

for(i=0;i<Y;i++)〃設(shè)置可利用資源向量

scanf&x.available[i]);

)

〃檢查安全性

intsafe(bankerx)

(

inti,j;

intsafeprocess[X];〃安全序列向量

intwork[Y];〃空閑資源矩陣

intFinish[X];〃進(jìn)程完成標(biāo)志矩陣

for(i=0;i〈Y;i++)〃開始時可利用資源向量就是空閑資源矩陣

work[i]=x.avaiTable[i];

for(i=0;i<X;i++)//初始化標(biāo)志矩陣為false

Finish[i]=false;

intk=0;〃安全序列排列號

for(i=0;i<X;i++)〃每次都從第一個進(jìn)程開始做循環(huán)

20

if(Finish[i]==false)

(

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

(

if(x.need[i][j]>work[j])〃判斷當(dāng)前進(jìn)程需求矩陣能否得到滿足

break;〃不滿足則跳出

)

if(j=Y)〃第i個進(jìn)程滿足執(zhí)行條件

(

safeprocess[k++]=i;〃將進(jìn)程號存入安全序列向量

for(intq=0;q<Y;q++)〃修改空閑資源矩陣

work[q]+=x.allocation[i][q];

Finish[i]=true;〃標(biāo)志該進(jìn)程可完成

i=-1；〃下次檢查從第一個進(jìn)程重新查起

)

)

)

for(i=0;i<X;i++)〃檢查標(biāo)志數(shù)組，若有一個為false則找不到安全序列

if(!Finish[i])

(

printf(〃無法找到安全序列,系統(tǒng)處于不安全狀態(tài)!\n〃)；

return0;

)

printf(〃安全序列為:〃)；〃找到安全序列并顯示該序列

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

printf(z/%d號進(jìn)程〃，safeprocess[i]+l);

printf(〃\n〃)；

return1;

)

〃系統(tǒng)對進(jìn)程資源申請的處理

voidallocate(banker&x)

bankertemp=x;〃臨時變量存儲x的初值

intRequest[Y];〃請求向量

intnumber;〃進(jìn)程號

inti;

printf(〃請輸入要申請資源的進(jìn)程序號:\n〃)；

scanf("%d〃,&number);

printf(〃請輸入請求向量:\n〃);

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

scanf(〃％d〃,&Request[i]);〃輸入請求向量

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

(

if(Request[i]>x.need[numberT][i])〃所需資源數(shù)大于需求量

(

printf(〃錯誤！進(jìn)程所需要的資源數(shù)已超過最大值。\n〃)；

return;

21

if(Request[i]>x.available[i])//所需資源數(shù)大于可利用資源

printf（"錯誤！系統(tǒng)中沒有足夠的資源滿足進(jìn)程的申請。\n"）;

return;

}

)

for(i=0;i<Y;i++)〃假設(shè)系統(tǒng)將申請資源數(shù)分配給該進(jìn)程，對數(shù)據(jù)進(jìn)行相關(guān)修改

(

x.available"]Request[i];

x.need[number-1][i]-=Request[i];

x.allocationLnumber-1][i]+=Request[i];

)

if(safe(x))〃安全性檢查結(jié)果為安全

(

printf("系統(tǒng)可以為該進(jìn)程分配資源.\n");

return;

）

else//安全性檢查結(jié)果為不安全

（

printf（"系統(tǒng)不為該進(jìn)程分配資源\n"）;

x=temp;〃將相關(guān)矩陣修改過來，表示資源不分配資源

return;

)

}

〃主程序

voidmain(void)

(

bankercurrent;〃定義變量

initilize(current);〃初始化

safe(current);〃檢查安全性

while(l)〃循環(huán)執(zhí)行進(jìn)程申請資源和系統(tǒng)對申請的處理

allocate(current);

)

}

22

3、運(yùn)行并測試程序，并給出程序運(yùn)行界面。

**G\Users\LEmNG\Desktop\D<

圖4-2銀行家算法運(yùn)行截圖

【思考題】

1.如果產(chǎn)生了死鎖，應(yīng)如何解除？

答：當(dāng)發(fā)現(xiàn)有死鎖時，便應(yīng)立即把它們從死鎖狀態(tài)中解脫出來。常采用解除死鎖的

兩種方法是：

(1)剝奪資源。從其它進(jìn)程剝奪足夠數(shù)量的資源給死鎖進(jìn)程，以解除死鎖狀態(tài)。

(2)撤銷進(jìn)程。最簡單的撤銷進(jìn)程的方法是使全部死鎖狀態(tài)進(jìn)程都夭折掉；稍微溫和一點(diǎn)的方法

是按照某種順序逐個的撤銷進(jìn)程，直至有足夠的資源可用，使死鎖狀態(tài)消除為止。

23

任務(wù)五文件管理

【實(shí)訓(xùn)目的】

掌握文件的存取方法；掌握文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；掌握存儲空間的分配和回收；

掌握磁盤管理與調(diào)度。

【實(shí)訓(xùn)內(nèi)容】

用程序模擬磁盤的調(diào)度過程，并計(jì)算各磁盤調(diào)度算法包括先來先服務(wù)算法、最短尋道時

間優(yōu)先算法、掃描算法和循環(huán)掃描算法的平均尋道長度。

【實(shí)訓(xùn)步驟】

1、分析與設(shè)計(jì)

圖5-1先來先服務(wù)算法流程圖

24

圖5-2最短尋道時間算法流程圖

25

圖5-3掃描算法流程圖

2、程序代碼

#include〃stdio.h〃

#include"stdlib.h〃

intNAI1=0;

intBest[5][2];〃用作尋道長度由低到高排序時存放的數(shù)組

intLimit=0;〃輸入尋找的范圍磁道數(shù)i

intJage;

floatAver=0;

〃數(shù)組Sour復(fù)制到數(shù)組Dist,復(fù)制到x個數(shù)

26

voidCopyL(intSour[],intDist[],intx)

(

inti;

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

(

Dist[i]=Sour[i];

)

}

〃打印輸出數(shù)組

voidPrint(intPri[],intx)

(

inti;

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

(

printf(飛5d”,Pri[i]);

)

)

〃隨機(jī)生成磁道數(shù)

voidSetDI(intDiscL[])

(

inti;

for(i=0;i〈=9;i++)

(

DiscL[i]=rand()%Limit;//隨機(jī)生成10個磁道號

)

system("cis");

printfC\n\n\n需要尋找的磁道號：”)；

Print(DiscL,9);〃輸Hl隨機(jī)生成的磁道號

printf("\n");

)

〃數(shù)組Sour把x位置的數(shù)刪除，并把y前面的數(shù)向前移動

voidDellnq(intSour[],intx,inty)

(

inti;

for(i=x;i<y;i++)

(

Sour[i]=Sour[i+l];

x++;

)

}

〃先來先服務(wù)算法(FCFS)

voidFCFS(intHan,intDiscL口)

{

intRLine[10];〃將隨機(jī)生成的磁道數(shù)數(shù)組Disci口復(fù)制給數(shù)組RLine口

inti,k,AH,Temp;〃Temp是計(jì)算移動的磁道距離的臨時變量

All=0;〃統(tǒng)計(jì)全部的磁道數(shù)變量

k=9;〃限定10個的磁道數(shù)

CopyL(DiscL,RLine,9);〃復(fù)制磁道號到臨時數(shù)組RLine

printfC\n按照FCFS算法磁道的訪問順序?yàn)椋骸?；

27

All=Han-RLine[0];

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

(

Temp=RLine[O]-RLine[l];〃求出移動磁道數(shù),前一個磁道數(shù)減去后一個磁道數(shù)得出臨時的移動

距離

if(Temp<0)

Temp=(-Tenip);〃移動磁道數(shù)為負(fù)數(shù)時，算出相反數(shù)作為移動磁道數(shù)

printf("%5d”,RLine[0]);

All=Temp+Al1;〃求全部磁道數(shù)的總和

Dellnq(RLine,0,k);〃每個磁道數(shù)向前移動一位

k—;

)

Best[Jage][1]=A11;//Best[][1]存放移動磁道數(shù)

Best[Jage][0]=l;//Best口[0]存放算法的序號為：1

Jage++;〃排序的序號加1

Aver=((float)Al1)/10;〃求平均尋道次數(shù)

printf("\n移動磁道數(shù):〈%5d>”,All);

printfC\n平均尋道長度:*%0.2f*",Aver);

)

〃最短尋道時間優(yōu)先算法(SSTF)

voidSSTF(intHan,intDiscL[])

(

inti,j,k,h,All;

intTemp;〃Tenip是計(jì)算移動的磁道距離的臨時變量

intRLine[10];〃將隨機(jī)生成的磁道數(shù)數(shù)組Disci口復(fù)制給數(shù)組RLine口

intMin;

All=0;〃統(tǒng)計(jì)全部的磁道數(shù)變量

k=9;〃限定10個的磁道數(shù)

CopyL(DiscL,RLine,9);〃復(fù)制磁道號到臨時數(shù)組RLine

printfC\n按照SSTF算法磁道的訪問順序?yàn)椋?);

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

(

Min=64000;

for(j=0;j<=k;j++)〃內(nèi)循環(huán)尋找與當(dāng)前磁道號最短尋道的時間的磁道號

(

if(RLine[j]>Han)〃如果第一個隨機(jī)生成的磁道號大于當(dāng)前的磁道號，執(zhí)行下一句

Temp=RLine[j]-Han;//求出臨時的移動距離

else

Temp=Han-RLine[j];〃求出臨時的移動距離

if(Temp<Min)〃如果每求出一次的移動距離小于Min,執(zhí)行下一句

(

Min=Temp;〃Temp臨時值賦予Min

h=j;〃把最近當(dāng)前磁道號的數(shù)組下標(biāo)賦予h

}

)

A11=A11+Min;〃統(tǒng)計(jì)一共移動的距離

printf("%5d”,RLine[h]);

Han=RLine[h];

Dellnq(RLine,h,k);〃每個磁道數(shù)向前移動-一位

28

k-

Best[Jage];〃Best□[1]存放移動磁道數(shù)

Best[Jage][0]-2;//Best[][0]存放算法的序號為:2

Jage++;〃排序序號加1

Aver=((float)All)/10;〃求平均尋道次數(shù)

printf("\n移動磁道數(shù):<%5d>",All);

printf("\n平均尋道長度:*%0.2f*”,Aver);

)

〃掃描算法(SCAN)

intSCAN(intHan,intDiscL[],intx,inty)

(

intj,n,k,h,m,All;

intt=0;

intTemp;

intMin;

intRLine