計算機操作系統(tǒng)實驗報告

操作系統(tǒng)實驗報告

學院計算機學院

專業(yè)網(wǎng)絡工程_______________

班級_____________________

學號_________________

姓名_____________________

指導教師______________________

2011年11月

計算機學院網(wǎng)絡工程專業(yè)班學號：

姓名：協(xié)作者：教師評定：

程序運行情況實驗技能實驗報告

考勤情況

程序質量創(chuàng)新精神設計文檔

實驗一題目進程調度____________第8周星期1

實驗二題目作業(yè)調度____________第9周星期1

實驗一三（綜合性）題目主存空間的分配與回收第11周星期1

實驗四題目文件系統(tǒng)第14周星期1

實驗平臺：

1.計算機及操作系統(tǒng)：IBMThinkPad,WindowsXP

2.編程環(huán)境：MicrosoftVisualC++6.0,JavaDevelopmentKit運行環(huán)境

源程序名和可執(zhí)行程序名：

實驗一：源程序名：最高優(yōu)先數(shù)優(yōu)先.CPP，簡單輪轉法.cpp,多級反饋.cpp

可執(zhí)行程序：最高優(yōu)先數(shù)優(yōu)先.exe,簡單輪轉法.exe,多級反饋.exe

實驗二：源程序名：單道處理系統(tǒng).cpp,JBCNode.java,CreateJBC.java,Running.java,

OSJob.javao可執(zhí)行程序：單道處理系統(tǒng).exe,多道處理系統(tǒng).html

實驗三：源程序名：主存的分配和回收.CPP

可執(zhí)行程序：主存的分配和回收.exe

實驗四：源程序名：文件系統(tǒng).cpp

可執(zhí)行程序：文件系統(tǒng).cpp

備注：多通道處理系統(tǒng)用java程序編寫。

學號：—姓名：協(xié)作者：

實驗一題目進程調度第8周星期1

一、實驗目的

通過這次實驗，加深對進程概念的理解，進一步掌握進程狀態(tài)的轉變、進程調度的策略

及對系統(tǒng)性能的評價方法

二、實驗內容和要求

設計一個有N個進程共行的進程調度程序.

進程調度算法：

?采用“輪轉法”調度算法對五個進程進行調度。簡單輪轉法的基本思想是：所有就緒

進程按FCFS排成一個隊列，總是把處理機分配給隊首的進程，各進程占用CPU的時間片相

同。如果運行進程用完它的時間片后還為完成，就把它送回到就緒隊列的末尾，把處理機重

新分配給隊首的進程。直至所有的進程運行完畢。

?采用最高優(yōu)先數(shù)優(yōu)先的調度算法（即把處理機分配給優(yōu)先數(shù)最高的進程）和先來先服

務算法。

?每個進程有一個進程控制塊（PCB）表示。進程控制塊可以包含如下信息：進程名、

優(yōu)先數(shù)、到達時間、需要運行時間、已用CPU時間、進程狀態(tài)等等。

?進程的優(yōu)先數(shù)及需要的運行時間可以事先人為地指定（也可以由隨機數(shù)產(chǎn)生）。進程

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

?每個進程的狀態(tài)可以是就緒W（Wait）、運行R（Run）、或完成F（Finish）三種狀態(tài)

之一。

?就緒進程獲得CPU后都只能運行一個時間片。用已占用CPU時間加1來表示。

?如果運行一個時間片后，進程的已占用CPU時間已達到所需要的運行時間，則撤消

該進程，如果運行一個時間片后進程的已占用CPU時間還未達所需要的運行時間，也就是進

程還需要繼續(xù)運行，此時應將進程的優(yōu)先數(shù)減1（即降低?級），然后把它插入就緒隊列等

待CPUo每進行一次調度程序都打印一次運行進程、就緒隊列、以及各個進程的PCB,以

便進行檢查。

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

三、實驗主要儀器設備和材料

實驗環(huán)境

硬件環(huán)境：IBM-PC或兼容機

軟件環(huán)境：C++,C語言編程環(huán)境

四、實驗原理及設計方案

1.實驗原理

“最高優(yōu)先數(shù)優(yōu)先”算法常用于批處理系統(tǒng)中。在進程調度中，每次調度時，系統(tǒng)把處

理機分配給就緒隊列中優(yōu)先數(shù)最高的進程。在非搶占式優(yōu)先數(shù)算法下系統(tǒng)一旦把處理機分

配給就緒隊列中優(yōu)先數(shù)最高的進程后，這個進程就會一直運行，直到完成或發(fā)生某事件使它

放棄處理機，這時系統(tǒng)才能重新將處理機分配給就緒隊列中的另一個優(yōu)先數(shù)最高的進程。靜

態(tài)優(yōu)先數(shù)是在創(chuàng)建進程時確定的，并在整個進程運行期間不再改變。動態(tài)優(yōu)先數(shù)是指進程的

優(yōu)先數(shù)在創(chuàng)建進程時可以給定一個初始值，并且可以按一定原則修改優(yōu)先數(shù)。程序將使用動

態(tài)優(yōu)先數(shù)。

“輪轉法”算法中，系統(tǒng)將所有的就緒進程按先來先服務的原則，排成一個隊列，每次

調度時，把CPU分配給隊首進程，并令其執(zhí)行?個時間片。時間片的大小從幾ms到幾百ms。

當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調度程序便據(jù)此信號來停止該進

程的執(zhí)行，并將它送往就緒隊列的末尾;然后，再把處理機分配給就緒隊列中新的隊首進程,

同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內，

均能獲得一時間片的處理機執(zhí)行時間。

“多級反饋隊列調度”算法中，進程在進入待調度的隊列等待時，首先進入優(yōu)先級最高

的隊列等待。先調度優(yōu)先級高的隊列中的進程，若高優(yōu)先級中隊列中已沒有調度的進程，則

調度次優(yōu)先級隊列中的進程。對于同一個隊列中的各個進程，按照時間片輪轉法調度。在低

優(yōu)先級的隊列中的進程在運行時，又有新到達的作業(yè)，那么在運行完這個時間片后，CPU馬

上分配給新到達的作業(yè)（搶占式）。

2.設計方案

1）最高優(yōu)先數(shù)優(yōu)先算法

從鍵盤輸入若干個進程，進程包括進程名，進程優(yōu)先數(shù)，進程運行時間。就緒隊列按照

優(yōu)先級從高到低排列，進程調度中，獲取就緒隊列隊首進程，即優(yōu)先級最高的進程，在進程

獲得一次CPU后，就將該進程的優(yōu)先數(shù)減1。重新排列就緒隊列，獲取就緒隊列隊首進程進

行調度。

2）簡單輪轉法

從鍵盤輸入若干個進程，進程包括進程名，進程運行時間。就緒隊列按照先到服務的算

法排列，進程調度中，獲取就緒隊列隊首進程，即最早到達的進程，在進程獲得CPU的一個

時間片，若在該時間片內，該進程完成，釋放節(jié)點，否則，就將該進程的排到隊尾。重新獲

取就緒隊列隊首進程進行調度。

3）多級反饋調度算法

從鍵盤輸入一個進程，包括進程名，運行時間等，將該進程放入第一列的隊尾，按先到

先服務的短發(fā)排列。進程調度中，從第一列檢查，獲取優(yōu)先級最高的隊列中的（若第一列無

進程，則調用第二列進程，依次推類）隊首進程，在進程獲得CPU的一個時間片，若在該時

間片內，該進程完成，釋放節(jié)點，否則，就將該進程排到下一列隊尾。重新從第一列檢查，

獲取優(yōu)先級最高的隊列中的隊首進程。

3、相關數(shù)據(jù)結構的說明

1）最高優(yōu)先數(shù)優(yōu)先算法

typedefstructpcb

（

stringname;〃進程名稱，C++字符串

charstate;〃進程狀態(tài)

intneedtime;〃需要運行時間

intruntime;〃已運行時間

intsuper;〃優(yōu)先級

structpcb*next;〃指向下一個

}PCB;

2）簡單輪轉法

constintTIME=4;〃定義時間片為4個CPU時間

typedefstructpcb

（

stringname;〃進程名稱，C++字符串

charstate;〃進程狀態(tài)

intneedtime;〃需要運行時間

intruntime;〃已運行時間

structpcb*next;〃指向下一個

}PCB;

3）多級反餓調度算法

constintTIMEM;〃定義時間片為4個CPU時間

typedefstructpcb

（

stringname;〃進程名稱，C++字符串

charstate;〃進程狀態(tài)

intneedtime;〃需要運行時間

intruntime;〃已運行時間

structpcb*next;〃指向下一個

JpcbNode,*PCB;

typedefstructqueue〃就緒隊列

（

PCBready;〃就緒隊列

intterm;〃就緒隊列的等級，第一列或者第n列

structqueue*next;

}QNode,*Queue;

4、程序流程圖

1）最高優(yōu)先數(shù)優(yōu)先算法

2）簡單輪轉法

3）多級反饋調度算法

5、給出程序中源程序名和可執(zhí)行程序名。

1）最高優(yōu)先數(shù)優(yōu)先算法

源程序：最高優(yōu)先數(shù)優(yōu)先.cpp

可執(zhí)行程序：最高優(yōu)先數(shù)優(yōu)先.exe

2)簡單輪轉法

源程序：簡單輪轉法.cpp

可執(zhí)行程序：簡單輪轉法.exe

3)多級反饋調度算法

源程序：多級反饋.cpp

可執(zhí)行程序：多級反饋.exe

6、程序清單

1)最高優(yōu)先數(shù)優(yōu)先算法

#include<iostream>

#include<string>

usingnamespacestd;

ftdefineNULL0

typedefstructpcb

(

stringname;

charstate;

intneedtime;

intruntime;

intsuper;

structpcb*next;

}PCB;

PCB*head=NULL;

inttime;

intcheckstr(stringstrl,stringstr2)

(

intflag=O;

if(strl==str2)

flag=l;

returnflag;

)

voidsort(PCB*p)

(

if(head==NULLIp->super>head->super)

(

p->next=head;

head二p;

return;

}

if(head->next==NULL)

(

head->next=p;

return;

)

PCB*pl,*p2;

pl=head;

p2=head->next;

while(p2)

(

if(p->super>p2->super)

(

pl->next=p;

p->next=p2;

return;

)

pl=pl->next;

p2=p2-〉next;

}

pl->next=p;

)

intinput()

(

intcount=0;

stringstr;

system(〃cls〃)；

cout<X〃\n二二二二二二二二進程輸入二二二二二二二二〃((end];

while(1)

(

count++;

PCB*p=newPCB;

cout?”\n輸入進程名：〃;

fflush(stdin);

cin?p->name;

cout<<〃輸入進程優(yōu)先數(shù)：〃；

cin?p->super;

cout?！ㄝ斎脒M程運行時間：〃；

cin>>p->needtime;

p->next=NULL;

p->runtime=O;

p->state=，w';

sort(p);

cout〈<"\n是否繼續(xù)輸入進程？(按N停止，其他任意鍵繼續(xù))〃；

fflush(stdin);

getline(cin,str);

intflagl=checkstr(str,Z，NZ/);

intflag2二checkstr(str,〃n〃)；

if(flagl||flag2)

break;

)

returncount;

)

voidoutput(PCB*p,intflag)

(

cout?z，\n正在運行進程到達時間："<<time〈〈endl;

if(flag)

cout<<"進程〈〃已完成，完成時間：〃;

cout?/z?----------1----------1----------1----------1----------1^?endl;

cout?/z|進程名稱|優(yōu)先數(shù)級|運行時間|需要時間|進程狀態(tài)|〃*endl;

cout.setf(iosbase::left);

cout<<〃|〃；

cout.width(8);

cout<<p->name;

cout?"|〃；

cout.width(8);

cout?p->super;

cout?z，|z/;

cout.width(8);

cout<<p->runtime;

cout<<"|〃；

cout.width(8);

cout?p->needtime;

cout<<〃|〃；

cout.width(8);

cout?p->state;

cout?/z|〃<<endl;

cout?/z1----------1----------1----------1----------1----------1，，?endl;

if(head)

(

cout<<，z\n就緒隊列狀態(tài)如下："<<endl;

cout<<，/?----------1----------1----------1----------1----------1zz?endl;

cout?，z|進程名稱|優(yōu)先數(shù)級|運行時間|需要時間|進程狀態(tài)|〃<<endl;

for(PCB*q=head;q;q=q->next)

cout?z，|

cout.width(8);

cout<<q->name;

cout<</，|〃；

cout.width(8);

cout<<q->super;

coutV|〃；

cout.width(8);

cout<<q->runtime;

cout<<，z|，z;

cout.width(8);

cout<<q->needtime;

cout?/，|〃；

cout.width(8);

cout?q->state;

cout<<z，|，z<<endl;

)

COUt?，Z1--------------------1--------------------1-----------z/?endl;

}

else

cout〈〈〃\n就緒隊列狀中已無進程！〃;

}

voidrunning()

(

intflag=0;

PCB*p;

p=head;

head=p->next;

p->next=NULL;

p->state=,r;

(p->runtime)++;

if(p->runtime-p->needtime)

flag=l;

output(p,flag);

(p->super)一;

if(flag)

deletep;

else

(

p->state=，w，;

sort(p);

)

time++;

)

intmain()

(

while(l)

(

system(〃cls〃);

，//z

cout<<\n=======iJ^S-i!^^========\n?endl;

cout<<〃是否開始進行進程調度演示？(按N退出，其他任意鍵開始)〃;

stringstr;

getline(cin,str);

intflagl二checkstr(str,〃N〃)；

intflag2=checkstr(str,〃n〃)；

if(flagl||flag2)

exit(0);

intcount=input();

cout?，z\n本次演示共〃〈〈count6〃個進程,按任意鍵進入演示.〃；

system("pause");

system(〃cls〃)；

cout<<〃\n====運行進程=====\n〃<<end];

time=0;

while(head)

(

running();

system(z，pausezz);

}

cout?〃\n所有進程已完成！〃；

system(，，pausez，);

}

return0;

}

2)簡單輪轉法

#inc1ude<iostream>

#include<string>

#include<Windows.h>

usingnamespacestd;

ftdefineNULL0

constintTIME=4;

typedefstructpcb

|

stringname;

charstate;

intneedtime;

intruntime;

structpcb*next;

}PCB;

PCB*head=NULL;

inttime;

intcheckstr(stringstrl,stringstr2)

(

intflag=O;

if(strl==str2)

flag=l;

returnflag;

)

voidsort(PCB*p)

(

if(head==NULL)

{

head=p;

return;

}

PCB*q;

q二head;

while(q->next)

q=q->next;

q->next=p;

)

intinput()

(

intcount=0;

stringstr;

system(〃cls");

cout<<〃\n======進程輸入===二===〃〈(endl;

while(1)

(

count++;

PCB*p=newPCB;

cout?”\n輸入進程名：〃;

fflush(stdin);

cin>>p->name;

cout*〃輸入進程運行時間：〃；

cin?p->needtime;

p->next=NULL;

p->runtime=O;

p->state=，w*;

sort(p);

cout〈〈〃\n是否繼續(xù)輸入進程？(按N停止，其他任意鍵繼續(xù))〃;

fflush(stdin);

getline(cin,str);

intflagl二checkstr(str,〃N〃)；

intflag2=checkstr(str,〃n〃)；

if(flagl|flag2)

break;

)

returncount;

)

voidoutput()

(

if(head)

(

cout<<，，\n就緒隊列狀態(tài)如下："<Xendl;

cout<<〃?----------1----------1----------1----------1z，?endl;

cout?/，|進程名稱|運行時間|需要時間|進程狀態(tài)|〃《endl;

cout.setf(ios_base::left);

for(PCB*q=head;q;q=q->next)

{

cout<<"I

cout.width(8);

cout<<q->name;

cout<<"|

cout.width(8);

cout<<q->runtime;

cout<<〃|〃；

cout.width(8);

cout<<q->needtime;

cout?，z|，z;

cout.width(8);

cout<<q->state;

cout<<z，|/z?endl;

)

cout<<z，1----------1----------1----------1----------1，z?endl;

)

else

cout?〃\n就緒隊列狀中已無進程！〃;

}

voidrunning()

(

intflag=0;

PCB*p;

p=head;

head=p->next;

p->next=NULL;

p->state=，r;

cout?/z\n正在運行進程〃<<p->name<<”,到達時間：”《tinie<<endl;

cout?”CPU時間：0〃;

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

{

Sleep(1000);

cout?，，\b，，?i+l;

(p->runtime)++;

time++;

if(p->runtime==p->needtime)

(

flag=l；

break;

)

}

cout<<endl;

if(flag)

(

cout<<"進程〃<<p->name<<”已完成，完成時間：〃<<time?endl;

deletep;

}

else

(

p->state=，ur，;

sort(p);

)

output();

)

intmain()

{

while(l)

system(，zcls，z);

cout〈〈〃\n=======進程調度\nz/?endl;

cout〈〈”是否開始進行進程調度演示？(按N退出，其他任意鍵開始)

stringstr;

getline(cin,str);

intflagl=checkstr(str,Z，NZ，);

intflag2二checkstr(str,〃n〃)；

if(flagl||flag2)

exit(0);

intcount=input();

cout?，z\n本次演示共〃《count*〃個進程,按任意鍵進入演示.〃；

system("pause");

system("cls〃);

cout〈〈〃\n=====運行進程=二二二二二二\n〃(〈end];

time=0;

output();

while(head)

(

running();

system("pause");

)

cout〈〈〃\n所有進程已完成！〃；

system("pause");

)

return0;

)

3)多級反饋調度算法

#include<iostream>

#include<string>

usingnamespacestd;

#defineNULL0

typedefstructpcb

(

stringname;

charstate;

intneedtime;

intruntime;

intsuper;

structpcb*next;

}PCB;

PCB*head=NULL;

inttime;

intcheckstr(stringstrl,stringstr2)

(

intflag=O;

if(strl==str2)

flag=l;

returnflag;

)

voidsort(PCB*p)

(

if(head==NULL|；p->super>head->super)

(

p->next=head;

head=p;

return;

)

if(head->next==NULL)

(

head->next:zp;

return;

)

PCB*pl,*p2;

pl=head;

p2=head->next;

while(p2)

(

if(p->super>p2->super)

(

pl->next=p;

p->next=p2;

return;

)

pl=pl->next;

p2=p2->next;

)

pl->next=p;

}

intinput()

(

intcount=0;

stringstr;

system(〃cls〃)；

cout?/z\n;:進程輸入:，，?endl;

while(1)

count++;

PCB*p=newPCB;

cout〈〈〃\n輸入進程名：〃；

fflush(stdin);

cin>>p->name;

cout"〃輸入進程優(yōu)先數(shù)：〃；

cin>>p->super;

cout?〃輸入進程運行時間：〃；

cin?p->needtime;

p->next=NULL;

p->runtime=O;

p->state=，w，;

sort(p);

cout?〃\n是否繼續(xù)輸入進程？(按N停止，其他任意鍵繼續(xù))〃；

fflush(stdin);

getline(cin,str);

intflagl=checkstr(str,Z，NZ/);

intflag2=checkstr(str,〃n〃)；

if(flagl||flag2)

break;

)

returncount;

)

voidoutput(PCB*p,intflag)

{

cout?z，\n正在運行進程到達時間：;

if(flag)

cout<<〃進程〃《p->name?〃已完成，完成時間：〃<<time+l?endl;

cout?/z?-----------1-----------1-----------1-----------1-----------1/z<<endl;

cout?，/|進程名稱|優(yōu)先數(shù)級|運行時間|需要時間|進程狀態(tài)|〃《endl;

cout.setf(ios_base::left);

cout?/z|

cout.width(8);

cout<<p->name;

cout?"|〃；

cout.width(8);

cout?p->super;

cout<<〃|〃；

cout.width(8);

cout<<p->runtime;

COUt<<〃I

cout.width(8);

cout?p->needtime;

cout<<〃|〃；

cout.width(8);

cout<<p->state;

cout<<〃|”<<endl;

cout?z，1----------1----------1----------1----------1----------1，，?endl;

if(head)

{

cout?”\n就緒隊列狀態(tài)如下：”《endl;

cout<<〃?----------1----------1----------1----------1----------1〃<<endl;

cout?/，|進程名稱|優(yōu)先數(shù)級|運行時間|需要時間|進程狀態(tài)|〃"endl;

for(PCB*q=head;q;q=q->next)

(

cout?z，Iz，;

cout.width(8);

cout<<q->name;

cout<</，|〃；

cout.width(8);

cout<<q->super;

cout?z，|

cout.width(8);

cout<<q->runtime;

cout<<"|〃；

cout.width(8);

cout<<q->needtime;

coutV|

cout.width(8);

cout<<q->state;

cout<<，?|，z?endl;

)

cout<<〃1----------1----------1----------1----------1----------1，z?endl;

)

else

cout?〃\n就緒隊列狀中已無進程！〃；

}

voidrunning()

(

intflag=0;

PCB*p;

p=head;

head=p->next;

p->next=NULL;

p->state=,r;

(p->runtime)++;

if(p->runtime==p->needtime)

flag=l;

output(p,flag);

(p->super)--；

if(flag)

deletep;

else

(

p-〉state='w';

sort(p);

)

time++;

)

intmain()

(

while(l)

(

system("cls〃);

cout<<〃\n=====進程調度===二二二\11"<<endl;

cout<<〃是否開始進行進程調度演示？(按N退出，其他任意鍵開始)〃;

stringstr;

getline(cin,str);

intflagl=checkstr(str,〃N〃)；

intflag2二checkstr(str,〃n〃)；

if(flagl'|flag2)

exit(0);

intcount=input();

cout?z，\n本次演示共〃《count<〈〃個進程,按任意鍵進入演示.〃；

system("pause");

system(〃cls〃);

cout<<"\n二二二二二二二二運行進程二二二二二二二二、n"<<end1;

time=0;

while(head)

(

running();

system("pause");

}

cout?〃\n所有進程已完成！〃；

system("pause");

}

return0;

)

五、實驗結果及分析

1、運行結果

1）最高優(yōu)先數(shù)優(yōu)先算法

a.開始菜單。

========進程調度========

L否開始進行進程調度演示？（按N退出，其他任意鍵開始）

b.輸入進程，本次演示中為節(jié)省時間，盡可能把進程數(shù)量和運行時間縮短。

========進程輸入========

海人進住名：jobl

隅入進崔優(yōu)先數(shù)：2

同人進槨層行時間:

2

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）y

除入進程名：Job2

屈入進崔優(yōu)先數(shù)：1

的入進能行時間:

卜否繼續(xù)輸入進程?

（按N停止，其他任意鍵繼續(xù)）y

，入進程名：job3

髓入進崔優(yōu)先數(shù)：3

輸入進建岔行時間:3

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）n

四次演示共3個進程，按任意鍵進入演示.請按任意鍵繼續(xù)...

c.運行進程

正在運行進程job3,到達時間：0

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

job3313r

就緒隊列狀態(tài)如下:

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

jobl202W

job2101

請按任意鍵繼續(xù)...

工在運行進程jobi,到達時間：1

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

jobl212

就緒隊列狀態(tài)如下：

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

job3213

job2101

請按任意鍵繼續(xù)...

正在運行進程Job3,到達時間：2

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

job32231*

就緒隊列狀態(tài)如下：

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

Job2101

jobl112

請按任意鍵繼續(xù),..

正在運行進程job2,到達時間：3

進程Job22完成，完成時|同：4

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

job21111%

就緒隊列狀態(tài)如下：

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

jobl112

job3123W

請按任意鍵繼續(xù)...

E在運行進程jobl,到達時間：4I

進程jobln完成，完成時間：51

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

jobl1221*

就緒隊列狀態(tài)如下：

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

Job3123

請按任意鍵繼續(xù).?一

正在運行進程job3,到達時間：5

進程job3口完成，完成時間：6

進程名稱優(yōu)先數(shù)級運行時間需要時間進程狀態(tài)

job3133r

就緒隊列狀中已無進程！請按任意鍵繼續(xù)...

所有進程已完成！請按任意鍵繼續(xù)...?

d.返回菜單

========進程調度========

、否開始進行進程調度演示？（按N退出，其他任意鍵開始）

2）簡單輪轉法

a.開始菜單，和最高優(yōu)先數(shù)算法一樣。

b.輸入進程，本次演示中為節(jié)省時間，盡可能把進程數(shù)量和運行時間縮短。

?=======進程輸入========

捌八世隹名：jobl

輸入進槨運行時間:9

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）y

i揄ll入進程名：job2

輸入進程運行時間:2

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）y

摘入進翼名：Job3

輸入進槿運行時間:6

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）n

庫次演示共3個進程，按任意鍵進入演示.請按任意鍵繼續(xù)...

c.運行，本次調度的時間片為4

........運行進程========

就緒隊列狀態(tài)如下：

進程名稱運行時間需要時間進程狀態(tài)

jobl09W

job202W

job306W

正在運行進程job],到達時間：10

CPU時間：4

就緒隊列狀態(tài)如下：

進程名稱運行時間需要時間進程狀態(tài)

job346

jobl89

請按任意鍵繼續(xù)...

正在運行進程job3,到達時間：14

CPU時間：2

溫程job3已完成，完成時間：16

就緒隊列狀態(tài)如下：

進程名稱運行時間需要時間進程狀態(tài)

job189

請按任意鍵繼續(xù)..?

正在運行進程jobi,到達時間：16

CPU時間

泥程jobi已完成，完成時間：17

就緒隊列狀中已無進程！請按任意鍵繼續(xù)...

所有進程已完成！請按任意鍵繼續(xù)...?

d.返回菜單

3）多級反饋調度算法

a.選擇菜單

========進程調度

1.新建進程

2.運行進住

0.退出

情輸入選擇：.

b.新建進程，為演示方便，輸入較少的進程

=======進程輸入========

富人進蜃名：job]

>44-±n>-Z-ru-L.'m9

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）y

輸入進程名：job2

輸入進槿運行時間:2

是否繼續(xù)輸入進程?（按N停止，其他任意鍵繼續(xù)）n

共輸入2個進程.請按任意鍵繼續(xù)...

c.運行進程

輸入兩個進程jobl和job2列表下，按先來先服務排列在隊列1

========進程運行========

就緒隊列狀態(tài)如下：

隊列進程名稱運行時間需要時間進程狀態(tài)

1Jobl09

1Job2023

運行進程，獲得隊列1的首部進程，運行CPU4個時間片，由于jobl沒有完成，進入隊

列2。接著運行進程2,進程2在CPU時間內完成，因此就緒隊列中，只有job2。接著因為

隊列1中已經(jīng)沒有進程了，所以運行隊列2的進程隊首進程，即jobl,jobl進程在CUP時

間片內沒有完成，進入隊列3。

H在運行進程job],到達時間：0,所處隊列：1

CPU時間：4

加緒隊列狀態(tài)如下：

隊列進程名稱運行時間需要時間進程狀態(tài)

1Job202VJ

2jobl49VJ

是否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）y

正在運行進程job2,到達時間：4,所處隊列：1

CPU時間：2

揀程Job2已完成，完成時間：6

，緒隊列狀態(tài)如下：

,列

進程名稱運行時間需要時間進程狀態(tài)

jobl49

是否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）y

正在運行進程jobi,到達時間：6,所處隊列：2

CPU時間：4

，緒隊列狀態(tài)如下：

進程名稱運行時間需要時間進程狀態(tài)

jobl89w

回否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）n.

選擇n,返回菜單，進入新建進程，輸入進程3

========進程輸入========

輸入進程名：job3

輸入進槨運行時間:6

是否繼續(xù)輸入進程？（按N停止，其他任意鍵繼續(xù)）n

共輸入1個進程.請按任意鍵繼續(xù)...

繼續(xù)運行，則才新輸入的進程job3排入第一隊列。運行進程，系統(tǒng)獲取優(yōu)先級較高的

隊列的隊首進程，即job3,運行4個CPU時間片，job3沒有完成，轉入隊列2。繼續(xù)運行,

由于隊列1已經(jīng)無進程，則轉向隊列2,隊列2不為空，則獲取隊首進程，即job3,運行4

個CUP時間，沒有完成，則轉入第三隊列的尾部，即job2的尾部。此時，隊列1,2都已經(jīng)

為空，系統(tǒng)獲取隊列三的隊首進程，即job2運行，在規(guī)定時間內job2完成。接著運行job3,

job3也已經(jīng)完成。則內存中已不存在進程，等待進程的輸入。

進程名稱一匡行時間］進程狀態(tài)-

Hoil需要時間

Ljob39

joblLJ9

正在運行進程到達時間：18,所處隊列：1

CPU時間：4

就緒隊列狀態(tài)如下：

隊列進程名稱運行時間需要時間進程狀態(tài)

2job349

3jobl89

是否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）y

正在運行進程job3,到達時間：14,所處隊列：2

CPU時間：4

就緒隊列狀態(tài)如下：

隊列進程名稱運行時間需要時間進程狀態(tài)

3jobl89

3Job389

是否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）y

正在運行進程jobl,到達時間：18,所處隊列:3

CPU時間

施程jobl己完成，完成時間：19

就緒隊列狀態(tài)如下^______

進程名稱運行時間需要時間進程狀態(tài)

job389

是否繼續(xù)運行？（按N停止，其他任意鍵繼續(xù)）y

正在運行進程Job3,到達時間：19,所處隊列：3

CPU時間

泥程job3已完成，完成時間：20

就緒隊列狀中已無進程！

d.我們可以返回菜單繼續(xù)輸入進程，但是由于演示，所以不繼續(xù)了。

2、實驗結果的分析及說明

1）最高優(yōu)先數(shù)優(yōu)先算法

對于“最高優(yōu)先數(shù)優(yōu)先”調度算法，進程的優(yōu)先數(shù)及需要的運行時間事先人為地指定，

進程的到達時間為進程輸入的時間。進程的運行時間以時間片為單位進行計算，運行一個

時間片后進程的已運行的時間還未達所需要的運行時間，也就是進程還未結束，此時應將進

程的優(yōu)先數(shù)減1（即降低一級），然后把它按某各調度算法插入就緒隊列等待CPU。每進行

一次調度程序都打印一次運行進程、就緒隊列、以及各個進程的PCB,以便進行檢查。重復

以上過程，直到所要進程都完成為止。

2）簡單輪轉法

對于“輪轉法”調度算法，所有就緒進程按FCFS排成隊列，然后把處理機分配給隊首

的進程，各進程占用CPU的忖間片相同（T=4）。如果運行進程用完它的時間片后還未完成,

就把它送回到就緒隊列的末尾，把處理機重新分配給隊首的進程。直至所有的進程運行完畢。

3）多級反饋調度算法

對于“多級反饋調度算法”調度算法，所有新進入的進程按FCFS排在第一隊列。運行

進程時，系統(tǒng)從第一隊列依次檢查，獲取優(yōu)先級高的隊列的隊首元素，假設第1隊列為空，

則尋找第二隊列，依次推類。找到第n（n>0）列隊，把處理機分配給隊首的進程，各進程

占用CPU的時間片相同（為4）。如果運行進程用完它的時間片后還未完成，就把它轉到就

緒隊列下一隊列（n+l）的末尾。系統(tǒng)重新尋找符合條件的的進程，把處理機分配給它。直

至所有的進程運行完畢。

六、調試總結及心得體會

由于本實驗比較簡單，實驗說明書上有代碼可以參考驗證，通過對本實驗的調試，對進

程最高優(yōu)先數(shù)優(yōu)先調度算法和簡單輪轉法調度算法以及多級反饋調度算法的基本思想和原

理有了比較深刻的理解，全部調度過程都與期待的調度過程相同。

這次實驗使我加深對處理機進程調度機制的理解，對進程的概念有了更深一層次的認

識。通過實現(xiàn)不同調度算法來實現(xiàn)調度進程，比較了不同調度算法的優(yōu)缺點，掌握進程狀態(tài)

轉換過程和處理機調度策略的實現(xiàn)。在編程中我不僅對課本內容有了更好的理解也提高了自

己的編程能力。

七、思考題

1、分析不同調度算法的調度策略，比較不同調度算法的優(yōu)缺點，總結它們的適用范圍

答：1）最高優(yōu)先權法：

優(yōu)點：咐于緊急的任務能得到較快的響應。

缺點：設計比較復雜，對于優(yōu)先級低的進程有可能一直沒有機會獲得運行。

適用范圍：實時系統(tǒng)。

2）時間輪轉法：

優(yōu)點：設計比較簡單，實現(xiàn)容易，對于系統(tǒng)中的每個進程都能有平等的機會獲得CPU,

得到響應。

缺點：對于緊迫性的任務可能得不到足夠多的運行機會，造成系統(tǒng)問題。

適用范圍：分時系統(tǒng)。

3）多級反饋隊列：

多級反饋隊列算法是輪轉算法和優(yōu)先級算法的綜合和發(fā)展。

優(yōu)點：為提高系統(tǒng)吞吐量和縮短平均周轉時間而照顧短進程。為獲得較好的I/O設備利

用率和縮短響應時間而照顧I/O型進程。不必估計進程的執(zhí)行時間，動態(tài)調節(jié)。

2、哪種進程最適合于多級反饋隊列調度，是偏重于處理機型還是偏重于I/O型？

偏重I/O的進程最適合多級反饋隊列調度，因為偏重I/O的進程的總體服務時間中，需要

CPU的時間相對要少許多，它到達不了深層的隊列就已經(jīng)執(zhí)行完畢了。偏重處理機的進程

則不然，由于需要處理機的時間很長，所以要到達很深層的隊列后才能逐步執(zhí)行完畢。

米4?4/多

學號：姓名：協(xié)作者：

實驗二題目作業(yè)調度第9周星期1

一、實驗目的

本實驗要求學生模擬作業(yè)調度的實現(xiàn),用高級語言編寫和調試一個或多個作業(yè)調度的模

擬程序，了解作業(yè)調度在操作系統(tǒng)中的作用，以加深對作業(yè)調度算法的理解。

二、實驗內容和要求

1、為單道批處理系統(tǒng)設計一個作業(yè)調度程序

(1)、編寫并調試?個單道處理系統(tǒng)的作業(yè)調度模擬程序。

(2)、作業(yè)調度算法：分別采用先來先服務(FCFS),最短作業(yè)優(yōu)先(SJF)、響應比高者

優(yōu)先(HRN)的調度算法。

(3)、由于在單道批處理系統(tǒng)中，作業(yè)一投入運行，它就占有計算機的一切資源直到作

業(yè)完成為止，因此調度作業(yè)時不必考慮它所需要的資源是否得到滿足，它所占用的CPU時

限等因素。

(4)、每個作業(yè)由一個作業(yè)控制塊JCB表示，JCB可以包含如下信息：作業(yè)名、提交時

間、所需的運行時間、所需的資源、作業(yè)狀態(tài)、鏈指針等等。作業(yè)的狀態(tài)可以是等待W(Wait)、

運行R(Run)和完成F(Finish)三種狀態(tài)之一。每個作業(yè)的最初狀態(tài)總是等待乳

(5)、對每種調度算法都要求打印每個作業(yè)開始運行時刻、完成時刻、周轉時間、帶權

周轉時間，以及這組作業(yè)的平均周轉時間及帶權平均周轉時間，并比較各種算法的優(yōu)缺點。

2、模擬批處理多道操作系統(tǒng)的作業(yè)調度

(1)、寫并調試一個作業(yè)調度模擬程序。

(2)、作業(yè)調度算法：分別采用先來先服務(FCFS)和短作業(yè)優(yōu)先調度算法。

(3)、在批處理系統(tǒng)中，要假定系統(tǒng)中具有的各種資源及數(shù)量、調度作業(yè)時必須考慮到

每個作業(yè)的資源要求，所需要的資源是否得到滿足。

作業(yè)調度程序負責從輸入井選擇若干個作業(yè)進入主存，為它們分配必要的資源，當它們

能夠被進程調度選中時，就可占用處理器運行。作業(yè)調度選擇一個作業(yè)的必要條件是系統(tǒng)中

現(xiàn)有的尚未分配的資源可滿足該作業(yè)的資源要求。但有時系統(tǒng)中現(xiàn)有的尚未分配的資源既可

滿足某個作業(yè)的要求也可滿足其它一些作業(yè)的要求，那么，作業(yè)調度必須按一定的算法在這

些作業(yè)中作出選擇。當作業(yè)正常運行完畢或因發(fā)生錯誤非正常終止時，作業(yè)進入完成狀態(tài)，

此時，系統(tǒng)將收回該作業(yè)所占用的全部資源，并清除有關的JCB。并輸出顯示作業(yè)運行情況

及作業(yè)輸出結果。

三、實驗主要儀器設備和材料

實驗環(huán)境

硬件環(huán)境：IBM-PC或兼容機

軟件環(huán)境：C++,C語言編程環(huán)境，JavaDevelopmentKit運行環(huán)境

四、實驗原理及設計方案

1.實驗原理

1)先來先服務算法

先來先服務算法，就是只考慮進程進入就緒隊列的時間先后。如果早就緒的進程排在就

緒隊列的前面，遲就緒的進程排在就緒隊列的后面，那么先來先服務(FCFS:firstcome

firstservice)總是把當前處于就緒隊列之首的那個進程調度到運行狀態(tài)。也就說，它只考

慮進程進入就緒隊列的先后，而不考慮它的下一個CPU周期的長短及其他因素。

2)最短作業(yè)優(yōu)先算法

短作業(yè)優(yōu)先(SJF：ShortestJobFirst),就是短作業(yè)優(yōu)先調度的算法，處理機總是

把當前處于就緒隊列中最短的的那個作業(yè)進程調度到運行狀態(tài)。

3)響應比高者優(yōu)先算法

最高響應比優(yōu)先法(HRN,HighestResponse_ratioNext)是對FCFS方式和SJF方式的

一種綜合平衡。FCFS方式只考慮每個作業(yè)的等待時間而未考慮執(zhí)行時間的長短，而SJF方

式只考慮執(zhí)行時間而未考慮等待時間的長短。因此，這兩種調度算法在某些極端情況下會帶

來某些不便。HRN調度策略同時考慮每個作業(yè)的等待時間長短和估計需要的執(zhí)行時間長短，

從中選出響應比最高的作業(yè)投入執(zhí)行。

響應比R定義如下：R=(W+T)/T=1+W/To

其中T為該作業(yè)估計需要的執(zhí)行時間，W為作業(yè)在后備狀態(tài)隊列中的等待時間。每當要

進行作業(yè)調度時，系統(tǒng)計算每個作業(yè)的響應比，選擇其中R最大者投入執(zhí)行。這樣，即使是

長作業(yè)，隨著它等待時間的增加，W/T也就隨著增加，也就有機會獲得調度執(zhí)行。這種算

法是介于FCFS和SJF之間的一種折中算法。由于長作業(yè)也有機會投入運行，在同一時間內

處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRN方式時其吞吐量將小于采用SJF法時的吞

吐量.另外，由于每次調度前要計算響應比，系統(tǒng)開銷也要相應增加。

作業(yè)等待時間相等時。則服務時間越短，優(yōu)先級越高，符合SJF思想。作業(yè)服務時間相

等時，則等待時間越長，優(yōu)先級越高，符合FCFS思想。對于長作業(yè)，只要其等待時間足夠

長，也能獲得處理機。

4)多道程序系統(tǒng)

多道程序系統(tǒng)是在計算機內存中同時存放幾道相互獨立的程序，使它們在管理程序控制

之下，相互穿插的運行。兩個或兩個以上程序在計算機系統(tǒng)中同處于開始和結束之間的狀態(tài)。

所謂多道程序設