操作系統原理

課程設計

指導

（第二版）

李印請等編籌

計算機科學與應用系

DepartmentofComputerScienceandApplication

二零零七年十二月

第二版前言

《操作系統課程設計》第一版編寫于2003年，從2000級計算機科學與技術專業投入

教學使用以來，距今已5年。在這5年中，計算機網絡、現代通信技術的發展極其迅速,

人們已經無法想像，如互聯網不通、手機丟失，將會對您的工作、學習和交際帶來的影

響有多么巨大。再者，這期間不僅操作系統開發技術有了很大進展，而且國內高等院校

計算機及相關專業“操作系統原理”課程的實踐教學也有了顯著的變化，對操作系統中

的原理、算法和方法的學習提出了更高的要求，原來沒有開設操作系統原理課程設計的

院校開始開設課程設計，幾年前已開設實驗的院校，已不再停留在操作系統中各種資源

管理的模擬，而是更加強調實踐（實驗或實訓I）的重要性。例如，要求計算機及相關專

業的學生，在校期間要熟練掌握一種操作系統，如MS-DOS或Windows,同時要求了解

另一種操作系統的原理、算法和方法。

這5年期間，本書作者在從事”操作系統原理”課程教學的同時，完成了多項院級

操作系統教學改革教學研究項目，并發表了數篇學術論文，對“操作系統原理”課程的

教學改革作了深入的研究。本書第二版正是在此基礎上并對第一版的內容作了較大的改

動之后撰寫而成的。

全書分為三大部分，共3章。每章中列出的實驗保留了第一版中編寫風格，即每個

實驗包括實驗目的、實驗內容和思考題，同時考慮到一些學生的實際需要，個別實驗還

給出了實驗涉及的基本思想、程序流程圖和供參考的程序代碼。

第1章操作系統基礎實驗是對第一版六個實驗作了較大改動之后編寫的。保留了其

中的進程調度算法的模擬、動態分區方法的模擬、存儲管理方式的模擬以及文件管理系

統的實現等實驗，并對其中的文字部分進行了編輯，程序代碼改用C++程序設計語言來

實現。

保留這一章的目的是要求計算機及相關專業的學生在完成操作系統課程設計教學實

踐環節中至少應完成其中的2個實驗，這是對學生的最低要求。通過這些實驗學生應掌

握操作系統中進程的概念、進程調度算法、操作系統中對存儲資源的管理以及文件系統

的實現方法。

第2章Linux及其實驗是新增的。內容包括Linux的安裝、Linux命令、shell程序設

計、Linux進程管理等方面的實訓。增設這一章的目的是為了使讀者了解Linux操作系統

的基本概念，熟悉該操作系統的使用方法以及掌握基于Linux的進程管理等方面的知識,

進一步提高對操作系統中各種資源管理的理解，基本掌握另一種操作系統，擴大其知識

面。

第3章Minix教學操作系統實踐也是新增的。內容包括Minix操作系統的基本知識

和概念，包括進程、DO系統、內存管理、文件系統等，這一章安排有Minix操作系統的

安裝、運行及退出，Minix命令等方面的實訓內容。

本書由多人合作完成。其中，李印清、荊立夏制定了全書的編寫大綱，趙中堂對第

一版中的實驗進行了修改，包括程序代碼的改寫，第2章由荊立夏編寫，第3章由史軍

勇編寫，李印清對全書進行了統稿。

我們在編寫過程中，盡可能引入新的觀點和方法，力求能反映當代操作系統領域的

I

技術水平。但由于學識淺陋，必有很多不足之處，希同行指正。

編著者

2007年12月于鄭州熊耳河畔

第一版前言

軟件技術是計算機系統的靈魂與核心，而操作系統是計算機系統中最核心和最底層

的軟件。對操作系統的深入學習關系到整個計算機系統運行機制的全面理解。因此，對

于學習操作系統的學生來說，除了需要刻苦努力之外，還需要掌握軟件和操作系統的原

理與設計技巧。學習和掌握它們對于提升自身的創造力和想象力是很有幫助的。

如何學習和掌握操作系統技術的原理與實現技能呢？除了聽課和讀書之外，加強實

踐環節，在設計與實現過程中加深對操作系統原理的理解同樣是重要的。作為計算機專

業的學生，多使用操作系統，多閱讀和分析操作系統源代碼，甚至自己設計一個小型操

作系統，對學習操作系統原理課程是十分有益的。

當前非常流行的Linux操作系統的原始版事實上就是由芬蘭赫爾辛基大學計算機系

大學生LinusTorvalds在從1990年底到1991年的幾個月中為了他自己的操作系統原理課

程學習和后來的上網用途而陸續編寫的。他在自己購買的Intel386PC機上，利用

Tanenbaum教授自行設計的微型UNIX操作系統Minix作為開發平臺，編寫了一個進程

切換器，目的是想看一看Intel386存儲管理軟件是如何工作的。隨后是為他自己上網需

要自行編寫的網絡仿真程序，再后來是為他從網上下載文件的需要而自行編寫的硬盤驅

動程序和文件系統。最終他發現已經實現了一個幾乎完整的操作系統內核。出于對這個

內核的信心和美好的奉獻與發展希望，Linux希望這個內核能夠免費擴散使用，并于1991

年底在赫爾辛基大學的一臺FTP服務器上發了一則消息，用戶可以下載Linux的公開版

本（基于Intel386體系結構）和源代碼。

Internet為Linux的興起創造了一個奇跡。由1992年1月全世界大約只有100個左右

的人在使用Linux,發展到越來越多的商業軟件公司的加盟，使Linux不斷地向高端發展，

開始進入越來越多的公司和企業計算領域，使Linux拓展為全球性的重要的操作系統，

其影響力直逼UNIXo

Linus在赫爾辛基大學本科和碩士畢業后，沒有組建或去任何一家Linux公司,而是于1997年3月

加盟美國加利福尼亞州的SantaClara的Transmeta公司。

基于上述想法，我們編寫了這本《操作系統原理課程設計》，它作為操作系統原理課

程的輔助教材，供計算機專業的學生在操作系統課程設計時使用，以期達到理論與實踐

相結合的目的。

鑒于目前提供給學生課程設計的軟硬件環境，書中共列出了6個利用C語言或C++

語言模擬作業調度、進程控制、進程同步、存儲管理和文件管理的實驗。為了幫助學生

順利完成實驗，我們給出了“作業調度”實驗、“進程調度”實驗和“文件管理”實驗的

部分C++參考編程解答。另外，基于開拓學生自己的創造力和想象力，還提倡由學生自

己按照操作系統中的原理和技術擬定實驗題目，在征得教師同意后，也可以作為課程設

計的題目。

由于Linux操作系統是一個向用戶開放源碼的免費的類UNIX操作系統，它為在校

學生學習操作系統課程提供了一個看得見摸得著的范例。因此，對有條件的學生，我們

建議你完全可以在Linux環境下完成操作系統的課程設計，當然，你應當熟悉Linux的操

III

作和開發環境，如果要安裝Linux系統，可以利用Linux安裝光盤運行安裝，或在下列網

址獲取源碼進行安裝：

ftp:〃

ftp:〃

ftp:〃

編著《操作系統原理課程設計》對作者來講還是初次嘗試，由于編著者的水平與知

識有限，書中完全可能存在錯誤和不妥之處，有待于有識之士的指教。

編著者

2003年4月于熊耳河畔

IV

目錄

第二版前言I

第一版前言III

第一章操作系統基礎實驗1

1.1進程調度算法1

1.1.1實驗目的1

1.1.2實驗內容1

1.1.3進程調度的基本思想4

1.1.4程序流程圖4

1.1.5供參考的部分程序代碼6

1.1.6思考題15

1.2動態分區存儲管理16

1.2.1實驗目的16

1.2.2實驗內容16

1.2.3思考題16

1.3請求調頁存儲管理17

1.3.1實驗目的17

1.3.2實驗內容17

1.3.3思考題18

1.4文件管理系統19

1.4.1目的19

1.4.2實驗內容19

1.4.3程序流程圖21

1.4.4供參考的部分程序代碼21

1.4.5程序運行結果（僅供參考）41

第2章Linux及其實驗44

2.1Linux概述44

2.1.1Linux歷史44

2.1.2Linux的特性44

2.1.3Linux的安裝45

2.2Linux用戶接口47

2.2.1Linux命令47

2.2.2shell程序設計52

2.3Linux進程管理57

2.3.1進程描述57

2.3.2進程狀態57

2.3.3進程控制58

V

2.3.4進程通信60

2.3.5進程管理實驗61

第三章Minix教學操作系統實踐68

3.1Minix操作系統概述68

3.1.1Minix進程68

3.1.2MinixI/O系統69

3.1.3Minix內存管理70

3.1.4Minix文件系統70

3.2Bochs虛擬機71

3.2.1Bochs虛擬機的基本概念71

3.2.2實驗171

3.3Minix操作系統的安裝、運行及退出72

3.3.1Minix操作系統的安裝、運行及退出的基本步驟72

3.3.2實驗274

3.4Minix操作系統命令介紹76

3.4.1目錄操作76

3.4.2文件操作77

3.4.3vi編輯器79

3.4.4系統變量80

3.4.5實驗381

附錄1課程設計報告格式82

附錄2Linux系統sched,h源碼文件88

附錄3Linux系統fork.c源碼文件120

VI

第1章操作系統基礎實驗

1.1進程調度算法

1.1.1實驗目的

通過優先權法和輪轉算法的模擬加深對進程概念和進程調度過程的理解，掌握進程

狀態之間的切換，同時掌握進程調度算法的實現方法和技巧。

1.1.2實驗內容

1.用C語言或C++語言來實現對n個進程采用優先權優先算法以及輪轉算法的進程

調度。

2.每個用來標識進程的進程控制塊PCB用結構來描述，包括以下字段：

(1)進程標識ID,其中0為閑逛進程，用戶進程的標識數為1,2,3...O

(2)進程優先級Priority,閑逛進程(idle)的優先級為0,用戶進程的優先級大于0,

且隨機產生，標識數越大，優先級越高。

(3)進程占用的CPU時間CPUtime,進程每運行一次，累計值等于4。

(4)進程總共需要運行時間Alltime,利用隨機函數產生。

(5)進程狀態，0—就緒態；1一運行態；2—阻塞態。

(6)隊列指針next,用來將多個進程控制塊PCB鏈接為隊列。

3.優先數改變的原則

(1)進程在就緒隊列中每呆一個時間片，優先數增加1。

(2)進程每運行一個時間片，優先數減3。

4.在調度前，系統中擁有的進程數PCB_number由鍵盤輸入，經初始化后，所有的

進程控制塊PCB鏈接成就緒隊列。

5.為了清楚地觀察諸進程的調度過程，程序應將每個時間片內的進程的情況顯示出

來，參照輸出格式如圖1-1、1-2、1-3所示：

1

圖1-1優先權優先調度算法1

圖1-2優先權優先調度算法2

圖1-3優先權優先調度算法3

2

輪轉調度算法的運行結果如圖1-4、1-5所示。

圖1-4輪轉調度算法的運行結果1

圖1-5輪轉調度算法的運行結果2

3

1.1.3進程調度的基本思想

（1）當系統空閑（就緒隊列為空）時，系統運行閑逛進程，否則運行其他進程，發

生變遷1（就緒一運行）。

（2）在運行進程（包括閑逛進程）的過程中，可能發生變遷2（運行一阻塞），即將

運行進程插入到阻塞隊列（閑逛進程不能被阻塞），可能有其他新的進程創建PCB,還可

能喚醒阻塞隊列中的某些進程PCB,發生變遷3（阻塞一就緒），即從阻塞隊列中移出并

插入就緒隊列中。

（3）時間片運行結束后，若進程累計占用CPU時間大于等于進程需要運行的時間，

則進程執行結束，釋放其PCB。若進程累計占用CPU時間小于進程需要運行時間，發生

變遷4（運行一就緒），即將當前運行的進程插入就緒隊列中。

1.1.4程序流程圖

1.動態優先權的進程調度算法模擬流程（請同學們補充）

4

2.輪轉法進程調度算法模擬流程

5

1.1.5供參考的部分程序代碼

/*以下程序在C++環境調試通過*/

ftincludezzstdafx.h〃

ftdefineNULL0

#include<stdio.h>

ftinclude<stdlib.h>

#include<iostream>

usingnamespacestd;

/*以下僅列出動態優先權的進程調度算法模擬*/

/*進程PCB結構*/

structPcb

{

intID;

intpriority;

intCPUtime;

intALLtime;

intState;

structPcb*next;

):

typedefstructPcbPCB;

voidinit();/*產生idle進程，輸入用戶進程數目，調用insert。*/

voidprint(PCB*pcb);/*輸出進程屬性信息*/

voidprint_init(PCB*pcb)/*輸出所有PCB的初始值*/

voidinsert();/*生成進程屬性信息，插入進程就緒隊列*/

voidrun(PCB*pcb);/*運行進程，隨機阻塞進程、產生新進程，插入就緒隊

列，喚醒阻塞進程*/

voidblock(PCB*pcb);/*調用destroy。，將進程插入阻塞隊列*/

voidwakeup();/*喚醒進程，插入就緒隊列*/

voidproc_priority();/*優先權調度算法模擬*/

voidproc_loop();/*輪轉法調度算法模擬*/

voidupdate(PCB*pcb);/*更新進程信息*/

PCB*ready_queue,*block_queue,*idleprocess;/*就緒隊列，阻塞隊列及閑逛進程指

針變量*/

voidmainl()

6

inti=0;

while(1)

(

cout<<(，z\nPleaseselectanumber(1,2,0)〃)；

cout<<(z，\n1--priority〃)；

cout<<(〃\n2--loop");

cout<<(z/\n0--exit\n〃)；

cin?i;

if(i=l)

(

cout<<(zz\nThisisanexampleforpriorityprocessing:\n，z);

init();

::proc_priority();

}

elseif(i=2)

(

cout<<(，z\nThisisanexampleforroundrobinprocessing:\nz/);

init();

proc_loop();

}

elseif(i==0)

exit(1);

/*輸出所有PCB的初始值，此函數用于測試程序*/

voidprintinit(PCB*pcb)

(

PCB*temp=pcb->next;

cout?(，z\nIDpriorityCPUtimeALLtimeState\nz，);

while(temp!=NULL)

(

cout<<，z\nz/<<，z，z<<temp->ID<<z，z，?temp->priority?z/

/，<<temp->CPUtime<<zrz，?temp->ALLtime;

if(temp->State==0)

cout?(〃ready");

elseif(temp->State=l)

cout<<Crunning");

7

else

cout?(/zblocked");

temp=temp->next;

}

)

/*輸出進程屬性信息*/

voidprint(PCB*pcb)

{

PCB*temp;

temp=pcb;

if(pcb->ID==0)

cout<<(zz\n\tTheidleprocessisrunning!，z);

else

{

cout〈<〃\n〃<<〃Z*<<temp->ID<<，//z<<temp->priority?，z

，z<<temp->CPUtime<<，z?temp->ALLtime;

if(temp->State==O)

cout<<(〃ready");

elseif(temp->State==l)

cout<<(〃running");

else

cout<<(，zblocked");

voidinsert_queue(PCB*queue,PCB*item)

{〃將item插入到隊列中，使得插入后，隊列中按照優先級從高到低有序

PCB*p,*q;

q=queue;p=q->next;

while(p!=0&&p->priority>=item->priority)

(

q=p;

p=p->next;

}

if(p=0)

{〃在隊尾插入

item->next=O;

8

q->next=item;

)

else

{〃在q之后、P之前插入

item->next=p;

q->next=item;

)

)

voidpushback_queue(PCB*queue,PCB*item)

{〃將item插入到隊列的尾部

PCB*p,*q;

q=queue;p=q->next;

while(p!=0)

(

q=p;

p=p->next;

)

item->next=q->next;

q->next=item;

}

voidsort_queue(PCB*&queue)

{〃對queue中的結點進行排序，按照優先級從大到小

PCB*temp=newPCB;

temp->next=O;

while(queue->next)

{

PCB*p;

p=queue->next;queue->next=p->next;

::insert_queue(temp,p);

)

queue->next二temp->next;

deletetemp;

/*生成進程屬性信息，插入進程就緒隊列,顯示進程信息*/

voidinsert()

9

PCB*newp=O;

staticlongid=0;

newp=newPCB;

id++;

newp->ID=id;

newp->State=O;

newp->CPUtime=0;

newp->priority=rand()%3+l;

newp->ALLtime=rand()%3+l;

newp->next=NULL;

::pushback_queue(ready_queue,newp);〃將新生成進程插入到就緒隊列尾部

print(newp);

cout<<("\t建立:Creating->ready\n〃)；

}

/*生成n個進程屬性信息，插入進程就緒隊列,顯示進程信息*/

voidinsert(intn)

{

for(inti=l;i<=n;i++)

(

insert();

}

)

/*產生idle進程，輸入用戶進程數目，調用insert。*/

voidinit0

(

〃為每個隊列設立頭結點，便于插入刪除操作

block_queue=newPCB;

block_queue->next=0;

ready_queue=newPCB;

ready_queue->next=O;

inti,pcb_number=-l;

idleprocess=NULL;/*設置閑逛進程PCB各字段值*/

idleprocess=(PCB*)malloc(sizeof(PCB));

idleprocess->ID=0;

idleprocess->State=0;

10

idleprocess->CPUtime=0;

idleprocess->priority=0;

idleprocess->ALLtime=l;

idleprocess->next二NULL;

〃閑逛進程放入就緒隊列

idleprocess->next=ready_queue->next;

ready_queue->next=idleprocess;

//也可假定初始時系統中只有一個idle進程

〃〃輸入初始時進程的個數

//while(pcb_number<0)

//{

//cout<<(，zInputthenumberofthePCBtobestarted/7);

//cin>>pcb_number;

//)

//cout<<C\nIDpriorityCPUtimeALLtimeState");

//for(i=0;i<pcb_number;i++)

//insert();

cout<〈〃就緒隊列初始化成功〃<Xendl;

::print_init(ready_queue);

cout?endl;

}

/*調用destroy。，將進程插入阻塞隊列*/

voidblock(PCB*pcb)

{〃將pcb插入到阻塞隊列

pcb->State=2;/*將PCB所指進程的狀態設置為阻塞*/

pcb->CPUtime-=2;/*設進程執行半個時間片單位后被阻塞*/

/*pcb->next=NULL;*/

print(pcb);

cout?(，z變遷2：running->blocked\n，z);

〃將pcb插入到阻塞隊列

〃按照什么方式插入呢，需要參考喚醒條件

〃因為是隨機喚醒一個進程，所以我們就簡單地把它放置在阻塞隊列的頭部

pcb->next=block_queue->next;

blockqueue->next=pcb;

11

voidupdate(PCB*pcb)

{〃就緒隊列中進程的優先級均增加1

PCB*temp=ready_queue->next;

while(temp&&temp->next)

{〃就緒隊列的最后一個是閑逛進程

temp->priority++;

temp=temp->next;

)

)

/*運行參數PCB所指的進程*/

voidrun(PCB*pcb)

(

〃如果pcb是閑逛進程，則不做處理，再次放入就緒隊列ready_queue

if(pcb->ID==0)

(

::insert_queue(ready_queue,pcb);

print(pcb);

cout<<〃變遷1：ready->running\n/z;

)

else

{〃如果不是閑逛進程，則進行如下處理

pcb->State=l;/*設置該進程的狀態為〃運行〃*/

pcb->CPUtime+=4;/*累計該進程占用CPU的時間*/

pcb->priority=pcb->priority-3;/*每運行一個時間片，其優先數減3*/

if(pcb->priority<l)pcb->priority=l;

print(pcb);

printf(，z變遷1：ready->running\n/z);

if(rand()%3=l)/*PCB不是閑逛進程，滿足條件則阻塞此進程*/

{

if(pcb->CPUtime-2<pcb->ALLtime)

block(pcb);

else

{〃已經執行完畢，應該銷毀進程

cout?endl;

cout<<z，\ttheprocessno”<<pcb-iscompleted!銷毀:

running->Destroy^?endl;

12

deletepcb;

else

{〃否則看改進程是否執行完畢，如果執行完，則釋放，否則再次放入就緒隊列

if(pcb->CPUtime>=pcb->ALLtime)

{〃釋放

cout?endl;

cout<</z\ttheprocessno，/<<pcb->ID?/ziscompleted!銷毀:

running->Destroy^?endl;

deletepcb;

}

else

{〃再次放入就緒隊列,按照優先級有序

::insert_queue(ready_queue,pcb);

}

)

)

update(ready_queue);/*更新就緒隊列進程優先數*/

if(rand()%5=l)

{

insert(3);/*創建3個新進程*/

::sort_queue(ready_queue);

)

if(rand()%7==1)

wakeup();/*喚醒一個進程*/

/*返回當前進程是否被阻塞，1(已阻塞)，0(未阻塞)*/

)

/*喚醒，即從阻塞隊列中選擇一個PCB,且插入就緒隊列中*/

voidwakeup()

{〃隨機喚醒一個阻塞進程

〃這里采取的方法是遍歷阻塞隊列，每訪問一個，就產生一個隨機數

〃如果該隨機數對20求余恰好是1,則當前結點被喚醒，就要納入就緒隊列

if(block_queue->next=0)〃此時沒有被阻塞的進程，無所謂喚醒

return;

PCB*q,*p；〃下面遍歷阻塞隊列，q永遠指向p的前驅

while(true)

13

q=block_queue;

p=q->next;

while(p&&rand()%20!=l)

(

q二P；

p=p->next;

}

if(p!=0)

{〃P就是要喚醒的進程

q->next=p->next;

break;

}

)

p->State=0;

cout<<endl;

::print(p);

cout?/z變遷3：blocked->ready，z<<endl;

::insert_queue(ready_queue,p);

/*優先權優先調度算法*〃/zzt

voidproc_priority()

{

::sort_queue(ready_queue);

PCB*temp=0,*running=0;/"running的PCB指針*/

inttimes;

//block_queue=NULL;/*阻塞隊列為空*/

//for(times=O;times<300;times++)

for(times=0;times<10;times++)

(

〃找到優先級最高的進程，并且從隊列中刪除

cout<<〃本次調度前：〃<<endl;

::print_init(ready_queue);

running=ready_queue->next;/"running指向就緒隊列隊首PCB*/

ready_queue->next=running->next;

14

cout?endl;

cout<<〃本次調度開始〃<<endl;

::run(running);

cout〈<"\n本次調度結束。“<<endl;

}

〃/*輪轉法進程調用算法的模擬由學生設計并予以實現。*/

voidproc_loop()

1.1.6思考題

1.請仔細閱讀動態優先權的進程調度算法的模擬實現代碼，說明該算法與教材中介

紹的算法做了那些簡單化處理。

2.在實際的進程調度中，除了按調度算法選擇下一個執行的進程外，還應處理哪些

工作？

3.為什么對進程的優先數可按上述原則進行修改？

4.請給出設計實現的輪轉法進程調度算法的設計思想。

5.說明這兩種調度算法的應用場合，分析采用不同算法對系統性能的影響。

15

1.2動態分區存儲管理

1.2.1實驗目的

了解動態分區分配中使用的數據結構和分配算法，并進一步加深對動態分區存儲管

理方式及其實現過程的理解。

1.2.2實驗內容

1.用c語言或C++語言分別實現采用首次適應算法和最佳適應算法的動態分區分配

過程alloc()和回收過程free()。其中，空閑分區通過空閑分區鏈表來管理，在進行內存分

配時，系統優先使用空閑區低端的空間。

假設初始狀態如下，可用的內存空間為640KB,并有下列的請求序列；

作業1申請130KB

作業2申請60KB

作業3申請100KB

作業2釋放60KB

作業4申請200KB

作業3釋放100KB

作業1釋放130KB

作業5申請140KB

作業6申請60KB

作業7申請50KB

作業6釋放60KB

請分別采用首次適應算法和最佳適應算法進行內存塊的分配和回收，同時顯示內存

塊分配和回收后空閑內存分區鏈的情況。

1.2.3思考題

1.采用首次適應算法和最優置換算法，對內存的分配和回收速度會造成什么不同的

影響？

2.如何解決因碎片而造成內存分配速度降低的問題？

16

1.3請求調頁存儲管理

1.3.1實驗目的

通過對頁面、頁表、地址轉換和頁面置換過程的模擬，加深對請求調頁系統的原理

和實現過程的理解。

1.3.2實驗內容

1.假設每個頁面中可存放10條指令，分配給作業的內存塊數為4。

2.用C語言或C++語言模擬一個作業的執行過程，該作業共有320條指令，即它的

地址空間為32頁，目前它的所有頁都還未調入內存。在模擬過程中，如果所訪問的指令

已在內存，則顯示其物理地址，并轉下一條指令。如果所訪問的指令還未裝入內存，則

發生缺頁，此時需記錄缺頁的次數，并將相應頁調入內存。如果4個內存塊均已裝入該

作業，則需進行頁面置換，最后顯示其物理地址，并轉下一條指令。

在所有320指令執行完畢后，請計算并顯示作業運行過程中發生的缺頁率。

3.置換算法：請分別考慮最佳置換算法(OPT)、先進先出(FIFO)算法和最近最

久未使用(LRU)算法。

4.作業中指令的訪問次序按下述原則生成；

50%的指令是順序執行的；

25%的指令是均勻分布在前地址部分；

25%的指令均勻分布在后地址部分。

具體的實現辦法是：

(1)在［0,319］之間隨機選取一條起始執行指令，其序號為m；

(2)順序執行下一條指令，其序號為m+1條指令；

(3)通過隨機數，跳轉到前地址部分［0,m-1］中的某條指令處，其序號為ml；

(4)順序執行下一條指令，即序號為ml+1的指令；

(5)通過隨機數，跳轉到后地址部分［ml+2,319］中的某條指令處，其序號為m2；

(6)順序執行下一條指令，則序號為m2+l的指令；

(7)重復跳轉到前地址部分，順序執行，跳轉到后地址部分；順序執行的過程，直

至執行320條指令。

17

1.3.3思考題

1.如果增加分配給作業的內存塊數，將會對作業運行過程中的缺頁率產生什么影

響？

2.為什么在一般情況下，LRU具有比FIFO更好的性能？

18

1.4文件管理系統

1.4.1實驗目的

通過設計一個多用戶文件系統，了解操作系統中文件的組織與管理，熟悉文件管理

所用的數據結構，加深對文件系統內部功能實現過程的理解。

1.4.2實驗內容

1.用C語言或C++語言設計一個最多包括N個用戶的多用戶文件系統，約定每個

用戶最多保存M個文件。同時限制一個用戶在進入系統后，最多打開L個文件。

2.系統應具備一定的健壯性。即能夠檢查用戶所輸入命令的正確性，出錯時顯示出

必要的信息。另外，對文件需設置必要的保護措施。

3.文件目錄結構采用兩級目錄結構：主文件目錄和用戶文件目錄

（1）主文件目錄的數據結構

typedefstructMFD

{charusername[100];/*用戶名*/

charpassword[100];/*用戶口令*/

FILEfp;/*文件目錄指針*/

}MFD;

MFDmainfd[N];/*主文件目錄數組*/

（2）用戶文件目錄的數據結構

typedefstructUFD

{charfilename[256];/*文件名*/

charprotect;/*保護碼*/

intlength;/*文件長度*/

}UFD;

UFDuserfd[M];/*用戶目錄數組*/

（3）打開文件目錄

typedefstructOFD

{charfilename[256];/*打開文件名*/

charopencode;/*打開保護碼*/

intfp;/*讀寫指針*/

）OFD；

OFDopenfd[L];/*打開文件目錄數組*/

19

(4)用戶命令數據結構

typedefstructCOMM

{charstring[256];/*用戶命令串*/

structCOMM*next;/*指向命令各參數所在的結點*/

JCOMM;

5.本實驗要求提供以下有關操作：

dir用于查看系統的當前用戶。

help提供幫助系統，讓用戶了解各種命令的格式及功能。

login用于用戶登錄，用戶第1次登錄時必須設置自己的口令，以后必須根據口令

進入系統。

logout用戶退出系統。

setpass用于用戶修改自己的口令。

create用于創建新文件。

open用于打開文件。

close用于關閉文件。

copy用于復制文件。

delete用于刪除文件。

rename用于文件名改名。

read用于讀文件內容。

write用于寫文件內容。

注：

(1)對文件只有在打開(/r/w/d)的情況下，才能讀、寫、更名、復制、刪除。

(2)操作結束后，用戶退出系統，應關閉所有已打開的文件。

(3)為了簡化系統設計，實現文件的修改時，可以只修改指針，并不要求進行實際

的文件操作。

(4)關于C語言或C++語言的文件操作，請參閱“C語言程序設計教程”，“C++教

在O

20

1.4.3程序流程圖

1.4.4供參考的部分程序代碼

#include<io.h>

#include<conio.h>

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#include<ctype.h>

#defineN30/*用戶數*/

#defineM20/*一個用戶可保存M個文件*/

#defineL5/*用戶只能一次打開L個文件*/

typedefstructMFD/*主文件目錄*/

21

charusername[100];

charpassword[100];

FILEfp;/*文件指針*/

}MFD;

typedefstructUFD/*用戶文件目錄*/

charfilename[256];

charprotect;/*保護碼*/

intlength;/*文件長度*/

}UFD;

typedefstructOFD/*打開文件目錄*/

charfilename[256];

charopencode;/*打開保護碼*/

intfp;/*讀寫指針*/

}OFD;

typedefstructCOMM/*命令串*/

i

charstring[256];/*命令*/

structCOMM*next;/*后繼指針*/

}COMM;

MFDmainfd[N];/*主文件目錄數組*/

UFDuserfdfM];/*用戶文件目錄數組*/

OFDopenfd[L];/*打開文件目錄數組*/

COMM"command;/*命令串指針*/

charusername[10];

intusernum,savenum,opennum;

intworkfile;

voidinit();

voidinit_ufd();/*初始化用戶文件目錄*/

voidmesg();

char*getpass();/*設置口令函數聲明*/

22

char*getuser();/*設置用戶函數聲明*/

COMM*readcommand();/*讀命令串函數聲明*/

voidlogin();/*用戶登錄*/

voidlogout();/*用戶注銷*/

voidsetpass();/*設置口令*/

voidcreate();

voidmydelete();/*刪除*/

voidmyread();/*讀*/

voidmyopen();/*打開*/

voidmyclose();/*關閉*/

voidmywrite();/*寫*/

voidhelp();/*幫助*/

voiddir();/*列文件目錄*/

voidmycopy();/*復制*/

voidmyrename();/*文件改名*/

voidmain()

(

init();

for(;;)

readcommand();

if(strcmp(command->string,"create,,)==0)

create();

elseif(strcmp(command->string,ndelete")==0)

mydelete();

elseif(strcmp(command->string,nopenn)==0)

myopen();

elseif(strcmp(command->string,nclose")==0)

myclose();

elseif(strcmp(command->string,Hread")==0)

myread();

elseif(strcmp(command->string,,,write,,)==0)

mywrite();

elseif(strcmp(command->string,"copy")==0)

mycopy();

elseif(strcmp(command->string,nrename")==0)

myrename();

23

elseif(strcmp(command->string,nloginn)==0)

login();

elseif(strcmp(command->string,"setpassH)==0)

setpass();

elseif(strcmp(command->string,"logout")==0)

logout();

elseif(strcmp(command->string,"helpn)==0)

help();

elseif(strcmp(command->string,,,dir',)==0)

dir();

elseif(strcmp(command->string,"exit")==0)

break;

else

mesg(nBadcommand!");

}

)

voidinit()

(

FILE*fp;/*文件指針*/

chartempname[20],temppass[20];

inti;

usernum=0;/*全局變量初始化*/

savenum=0;

opennum=0;

strcpy(username,";

/*用戶使用時，建立一個mainfile.txt文件,包括每個用戶的用戶名和口令*/

/*然后，才能運行此程序*/

if((fp=fopen(nmainfile.txt","r"))!=NULL)

(

/*i=o；*/

while(!feof(fp))

(

strcpy(tempname,";

fgets(tempname,20,fp);/*讀用戶名*/

if(strcmp(tempname,n")!=O)

(

fgets(temppass,20,fp);

tempname[strlen(tempname)-1]='\0*;/*設置串結束符*/

24

temppass[strlen(temppass)-l]=,\O';

strcpy(mainfd[usernum].username,tempname);/*生成mainfd數組*/

strcpy(mainfd[usemum].password,temppass);/*生成userfd數組*/

usemum++;/*生成usemum的值*/

)

)

fclose(fp);

}

)

voidinit_ufd(char*usemame)/*初始化用戶文件目錄*/

(

FILE*fp;

chartempfile[100],tempprot;

inttemplength;

savenum=0;

opennum=0;

workfile=-1;

if((fp=fopen(usemame,"r+n))!=NULL)/*按用戶名打開文件*/

while(!feof(fp))

strcpy(tempfile,"");

fgets(tempfile,50,fp);/*從fp文件中設置一個長50的串*/

if(strcmp(tempfile,n,,)!=O)

fscanf(fp,n%c",&tempprot);

fscanf(fp,"%d",&templength);

tempfile[strlen(tempfile)-l]=,\O,;

strcpy(userfd[savenum].filename,tempfile);/*文件名*/

userfd[savenum].protect=tempprot;/*保護碼*/

userfd[savenum].length=templength;/*文件長度*/

savenum++;

fgets(tempfile,50,fp);

}

25

char*getuser()

(

charusemame[20];

chartemp;

inti;

username[0]='\0*;

for(i=0;i<10;)

{

while(!kbhit());/*按用戶名規則輸入用戶名*/

temp=getch();

if(isalnum(temp)11temp==,_，lltemp==13)

(

username[i]=temp;

if(username[i]==13)

(

usemame[i]=,\O,;

break;

)

putchar(temp);

i++；

usemame[i]=\O*;

}

)

return(username);

}

char*getpass()

(

charpassword[20];

chartemp;

inti;

password[0]='\0,;

for(i=0;i<10;)

while(!kbhit