計(jì)算機(jī)操作系統(tǒng)課程設(shè)計(jì)報(bào)告《存儲(chǔ)管理-動(dòng)態(tài)分區(qū)分配算法的模擬》

《計(jì)算機(jī)操作系》程計(jì)題專年

目：業(yè)：級(jí)：

存儲(chǔ)管——?jiǎng)討B(tài)分分配算的模擬軟件工程2012級(jí)小組成：指導(dǎo)教：時(shí)地

間：點(diǎn)：2012年5月目錄目錄.概述.2.課程設(shè)計(jì)任務(wù)及要求.12.1設(shè)計(jì)任務(wù)2.2設(shè)計(jì)要求3課程設(shè)計(jì)任務(wù)安排算法及數(shù)據(jù)結(jié)構(gòu).3.1算法的總體思想（流程）3.2首次適應(yīng)算法.3.2.1功能3.2.2數(shù)據(jù)結(jié)構(gòu)（包括變量的定義，要注釋！）3.2.3算法（流程圖表示，或偽表示）3.3循環(huán)首次適應(yīng)算法.3.3.1功能.3.3.2數(shù)據(jù)結(jié)構(gòu)3.3.3算法.3.4最佳適應(yīng)算法.3.4.1功能.3.4.2數(shù)據(jù)結(jié)構(gòu)3.4.3算法.3.5最壞適應(yīng)算法.3.5.1功能.3.5.2數(shù)據(jù)結(jié)構(gòu)5.3算法.程序設(shè)計(jì)與實(shí)現(xiàn).4.1程序流程圖4.2程序代碼（要注釋）3實(shí)驗(yàn)結(jié)果結(jié)論.收獲、體會(huì)和建議。的總結(jié)：的總結(jié)：7.參考文獻(xiàn)。2概述動(dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要?jiǎng)討B(tài)地為之分配內(nèi)存空間而在分配時(shí)須按照一定的分配算法從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。在本實(shí)驗(yàn)中運(yùn)用了五種分配算法，分別是：首次適應(yīng)算法循環(huán)首次適應(yīng)算法最壞適應(yīng)算法最佳適應(yīng)算法快速適應(yīng)算法2.課程設(shè)計(jì)務(wù)及要求2.1設(shè)計(jì)任務(wù)要求設(shè)計(jì)主界面以靈活選擇其中算法，種算法都要求實(shí)現(xiàn)。2.2設(shè)計(jì)要求1）

首先由系統(tǒng)生成當(dāng)前的內(nèi)存狀態(tài)，要求未分配的分區(qū)數(shù)量不少于3個(gè)，且空間大小隨機(jī)，然后隨機(jī)生成一個(gè)數(shù)，表示等待分配進(jìn)程的大小。2）

然后顯示上述算法由用戶選擇，結(jié)果顯示分配后的狀態(tài)。2.3課程設(shè)計(jì)任務(wù)安排日期星期三下午星期四早上星期四下午星期五早上星期五下午

A研究算法設(shè)計(jì)算法設(shè)計(jì)算法，編寫界面編寫算法程序測(cè)試并優(yōu)化

B研究算法參與設(shè)計(jì)參與設(shè)計(jì)完成部分文檔程序測(cè)試，完成文檔33.算法及數(shù)結(jié)構(gòu)3.1算法的總體思想（流程）設(shè)計(jì)程序模擬四種動(dòng)態(tài)分區(qū)分配算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法最佳適應(yīng)算法和最壞適應(yīng)算法的工作過程假設(shè)內(nèi)存中空閑分區(qū)個(gè)數(shù)為n，空閑分區(qū)大小分別為P,…,P，在動(dòng)態(tài)分區(qū)分配過程中需要分配的進(jìn)1n程個(gè)數(shù)為m（m≤n們需要的分區(qū)大小分別為S,…,S，分別利用1m四種動(dòng)態(tài)分區(qū)分配算法將m個(gè)進(jìn)程放入n個(gè)空閑分區(qū)，進(jìn)程在空閑分區(qū)中的分配情況。3.2首次適應(yīng)算法3.2.1功能在首次適應(yīng)算法中，是從已建立好的數(shù)組中順序查找，直至找到第一個(gè)大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空間令開辟一塊新的地址，大小為原來的大小減去作業(yè)大小，若查找結(jié)束都不能找到一個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗。3.2.2數(shù)據(jù)結(jié)構(gòu)包括變的定義，要釋?。﹑rivatestaticint

MaxNum=100;//空閑分區(qū)個(gè)數(shù)privatestaticn//作業(yè)個(gè)數(shù)privatestatic//空閑分區(qū)大小privatestatic

;[]=newint[MaxNum];//作業(yè)名稱privatestaticcharProcessName=newcharMaxNum];//作業(yè)需求空間大小privatestatic

[]=newint[MaxNum];4//作業(yè)分配標(biāo)志privatestaticboolean

state[]=newboolean

MaxNum];//空閑分區(qū)個(gè)數(shù)privatestatic//作業(yè)個(gè)數(shù)ProcessNumprivatestatic//記錄作業(yè)分配privatestaticchar[][]=newchar

MaxNum][

MaxNum];3.2.3算法（流圖表示或偽C表）publicstaticvoidFirst(){for(

=0;<;

++){for(

=0;

<n

++){//找到第一個(gè)合適的空閑分區(qū)if((ProcessNeed[]<=FreePartitionj])&&(!statei])){for(

k=0;

k<3;

k++)

//記錄作業(yè)分配{if([][k==0){

//為空[

][

]=

[i];break}elsecontinue}[]=FreePartitionj]-[istatei]=true;5}}}}3.3循環(huán)首次適應(yīng)算法3.3.1能該算法是由首次適應(yīng)算法演變而成在為進(jìn)程分配內(nèi)存空間時(shí)不再是每次都從第一個(gè)空間開始查找是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找直至找到第一個(gè)能滿足要求的空閑分區(qū)從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)，為實(shí)現(xiàn)本算法，設(shè)置一個(gè)全局變量f，來控制循環(huán)查找，當(dāng)f%N==0時(shí)，f=0；若查找結(jié)束都不能找到一個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗。3.3.2數(shù)據(jù)結(jié)構(gòu)privatestaticint

MaxNum=100;//空閑分區(qū)個(gè)數(shù)privatestatic//作業(yè)個(gè)數(shù)privatestatic//空閑分區(qū)大小

n;privatestatic

[]=newint[

];//作業(yè)名稱privatestaticcharProcessName=newcharMaxNum];//作業(yè)需求空間大小privatestatic

[]=newint[

MaxNum];//作業(yè)分配標(biāo)志privatestaticboolean

state[]=newboolean

MaxNum];//空閑分區(qū)個(gè)數(shù)privatestatic//作業(yè)個(gè)數(shù)

6privatestatic

ProcessNum//記錄作業(yè)分配privatestaticchar[][]=newchar][];3.3.3法publicstaticvoidCycleFirst(){=0;=0;while((i<)&&(<)){if

[]<=FreePartitionj])&&(!state[

])){for(k=0;<3;k++){

//記錄作業(yè)分配if([

][

]==0){[][k]=ProcessNamei];break}elsecontinue}FreePartitionj]=statei]=true;++;}else++;

[j

[];}}73.4最佳適應(yīng)算法3.4.1能最佳適應(yīng)分配算法是每次為作業(yè)分配內(nèi)存時(shí)掃描整個(gè)數(shù)組總是把能滿足條件的，又是最小的空閑分區(qū)分配給作業(yè)，避免“大材小用算法要求將所有的空閑分區(qū)按其容量以從小到大的順序形成一空閑分區(qū)鏈這樣第一次找到的能滿足要求的空閑區(qū)必然是最佳的。3.4.2數(shù)據(jù)結(jié)構(gòu)privatestaticint

MaxNum=100;//空閑分區(qū)個(gè)數(shù)privatestaticn//作業(yè)個(gè)數(shù)privatestatic//空閑分區(qū)大小privatestatic

;[]=newint[MaxNum];//作業(yè)名稱privatestaticcharProcessName=newcharMaxNum];//作業(yè)需求空間大小privatestatic//作業(yè)分配標(biāo)志

[]=newint[MaxNum];privatestaticboolean

state[]=newboolean

MaxNum];//空閑分區(qū)個(gè)數(shù)privatestatic//作業(yè)個(gè)數(shù)privatestatic

ProcessNum//記錄作業(yè)分配privatestaticchar[][]=newchar][];3.4.3法8publicstaticvoidBest(){for(=0;i<m++){temp=[0];=0;//找到第一個(gè)合適的空閑分區(qū)while{

[i]>)++;temp=[];}for(

=0;

<n

++){//按最佳適應(yīng)算法找到符合的空閑區(qū)if((ProcessNeed[]<=FreePartitionj])&&(

temp>[])&&(!

[

])){=FreePartition];k;}elsecontinue}for(

d

<3;

d++)

//記錄作業(yè)分配{iforder[][]==0){[

k][

d]=

[];break}9elsecontinue}FreePartitionkstatei]=true;

FreePartition]-ProcessNeed];}}3.5最壞適應(yīng)算法3.5.1能最壞適應(yīng)分配算法選擇空閑分區(qū)的策略正好與最佳適應(yīng)算法相反每次為作業(yè)分配內(nèi)存時(shí)掃描整個(gè)數(shù)組總是把能滿足條件的又是最大的空閑分區(qū)分配給作業(yè)。對(duì)中小作業(yè)有利，同時(shí)查找效率很高。3.5.2數(shù)據(jù)結(jié)構(gòu)privatestaticint

MaxNum=100;//空閑分區(qū)個(gè)數(shù)privatestaticn//作業(yè)個(gè)數(shù)privatestatic//空閑分區(qū)大小privatestatic

;[]=newint[MaxNum];//作業(yè)名稱privatestaticcharProcessName=newcharMaxNum];//作業(yè)需求空間大小privatestatic//作業(yè)分配標(biāo)志

[]=newint[MaxNum];privatestaticboolean

state[]=newboolean

MaxNum];//空閑分區(qū)個(gè)數(shù)privatestatic//作業(yè)個(gè)數(shù)

10privatestatic

ProcessNum//記錄作業(yè)分配privatestaticchar[][]=newchar][];3.5.3法publicstaticvoidWorst(){for(

=0;i;

++){=FreePartition[0];=0;for(

=0;

<n

++){//按最壞適應(yīng)算法找到合適的空閑分區(qū)if

[]<=FreePartitionj])&&(

temp<[])&&(!{

statei]))=[j];k;}elsecontinue}for(

=0;

d<3;

++)

//記錄作業(yè)分配{if({

[][]==0)order[k][

d]=

[i];break}else11}FreePartitionkFreePartitionk[istate

]=true;}}4.程序設(shè)計(jì)實(shí)現(xiàn)4.1程序流程圖4.2程序代碼（要注釋）D_ProcessPartition.javaimportjava.io.BufferedInputStream;importjava.io.FileInputStream;importjava.io.FileNotFoundException;importjava.util.Random;importjava.util.Scanner;publicclassD_ProcessPartition{privatestatic//空閑分區(qū)個(gè)數(shù)privatestatic

MaxNum=100;n//作業(yè)個(gè)數(shù)privatestatic;//空閑分區(qū)大小privatestatic

[]=newint[

];//作業(yè)名稱privatestaticcharProcessName=newcharMaxNum];//作業(yè)需求空間大小privatestatic

[]=newint[

MaxNum];//作業(yè)分配標(biāo)志privatestaticboolean[]=booleanMaxNum];//空閑分區(qū)個(gè)數(shù)12privatestatic//作業(yè)個(gè)數(shù)ProcessNumprivatestatic//記錄作業(yè)分配privatestaticchar[][]=newchar

MaxNum][

MaxNum];//?????privatestaticcharch=newcharMaxNum//臨時(shí)變量privatestatic

;//算法選擇//1-首次適應(yīng)算法//2-循環(huán)首次適應(yīng)算法//3-最佳適應(yīng)算法//4-最壞適應(yīng)算法privatestatic=0;//for循環(huán)中使用privatestaticprivatestatic

;;privatestatickprivatestatic

;privatestaticScannerstdin;publicStringD_ProcessPartition(intoption,intn)FileNotFoundException{Stringxinxi="";Stringzuoyexinxi="";StringsuanfaString="";//輸入數(shù)據(jù)xinxi=

input(n);//選擇算法13//1-首次適應(yīng)算法//2-循環(huán)首次適應(yīng)算法//3-最佳適應(yīng)算法//4-最壞適應(yīng)算法switch(option){case1:suanfaString=首次適應(yīng)算法";First(n);zuoyexinxi="對(duì)作業(yè)用首次適應(yīng)算法進(jìn)行空間分配:\n"+(n);breakcase2:suanfaString=循環(huán)首次適應(yīng)算法";(n);zuoyexinxi="對(duì)作業(yè)用循環(huán)首次適應(yīng)算法進(jìn)行空間分配:\n"+(n);breakcase3:suanfaString=最佳適應(yīng)算法";zuoyexinxi="對(duì)作業(yè)用最佳適應(yīng)算法進(jìn)行空間分配:\n"+(n);breakcase4:suanfaString=最壞適應(yīng)算法";Worst(n);zuoyexinxi="對(duì)作業(yè)用最壞適應(yīng)算法進(jìn)行空間分配:\n"+(n);break14}//返回?cái)?shù)據(jù)在JTA上顯示出來Stringall="你選擇了"+suanfaString+"\n\n"+xinxi+"\n\n"+zuoyexinxi;returnall;}//輸入數(shù)據(jù)publicstaticStringinput(intn)throwsFileNotFoundException{//算法選擇//1-首次適應(yīng)算法//2-循環(huán)首次適應(yīng)算法//3-最佳適應(yīng)算法//4-最壞適應(yīng)算法Stringresult="";//請(qǐng)依次輸入空閑分區(qū)大小(KB)for(

=0;

<n;

++){FreePartitioni]=RandomTest);result=result+

[i"";}result="隨機(jī)的"+n+"個(gè)空閑分區(qū)大小為"+result+"\n"+"隨機(jī)的作業(yè)大小為:";//請(qǐng)輸入作業(yè)個(gè)數(shù),按題目要求默認(rèn)為可設(shè)置m=1;//固定的作業(yè)名稱15[i]="Process".charAt(0);[

]=ProcessNamei];//按題目要求隨機(jī)作業(yè)大小(KB)for(

=0;i;

++){[]=RandomTest);state

]=false;result=result+}returnresult;

ProcessNeedi}publicstaticintRandomTest(){intmin=1;Randomrandom=newRandom();intsrandom.nextInt()%(

-min+1)+min;System.out.println(s);returns;}//1——首次適應(yīng)算法publicstaticvoidFirst(intn){for(

=0;i;

++){for(

=0;

<n;

++){//找到第一個(gè)合適的空閑分區(qū)if{

[]<=FreePartitionj])&&(!

[i]))for(kk<3;++)

//記錄作業(yè)分配16{if

[][

]==0)

//為空{(diào)order[

][

]=

[];}

break}elsecontinue}[]=[j]-ProcessNeedi];[]=true}}}//2——循環(huán)首次適應(yīng)算法publicstaticvoidCycleFirst(intn){=0;=0;while(({

<n)&&(

<mif

[]<=FreePartitionj])&&(!

[

])){for(k=0;

k<3;

++)

//記錄作業(yè)分配{

if{

[][

]==0)order[][break

]=

[];17}elsecontinue}FreePartitionj]=

[j]-ProcessNeed[i];[

]=true}

++;}else++;}//3——最佳適應(yīng)算法publicstaticvoidBest(intn){for(=0;<m++){=FreePartition[0];=0;//找到第一個(gè)合適的空閑分區(qū)while(

[i>){++;temp=[];}for(

=0;

<n;

++){//按最佳適應(yīng)算法找到符合的空閑區(qū)if

[]<=FreePartitionj])&&(

temp>[])&&(!{

statei]))=[j];18k;}elsecontinue}for(

=0;

d<3;

++)

//記錄作業(yè)分配{if({

[][

]==0)order[k][

d]=

[i];break}elsecontinue}FreePartitionkFreePartitionk

[istate

]=true;}}//4——最壞適應(yīng)算法publicstaticvoidWorst(intn){for(=0;<m++){=FreePartition[0];=0;for(=0;j<n;++){//按最壞適應(yīng)算法找到合適的空閑分區(qū)if

[]<=FreePartitionj])&&(

temp<[])&&(!statei]))19{=[j];k;}elsecontinue}for(

=0;

d<3;

++)

//記錄作業(yè)分配{if({

[][

]==0)order[k][

d]=

[i];break}elsecontinue}FreePartitionkFreePartitionk

[istatei]=true}}//結(jié)果輸出publicstaticStringoutput(intn){StringresultString="";for({

=0;i<n;

++)System.out.print("|");resultString=resultString+;for(

=0;

<3;

++){20if({

[][

]==0)System.out.print("");resultString=resultString+";}elseSystem.out.print([][]);resultString=resultString+

order[

i][];}}}System.out.print("|\n");resultString=resultString+;//清空緩沖區(qū)for({

=0;i<n;

++)for(=0;j<3;++){[][

j]=0;}}returnresultString;}}實(shí)驗(yàn)結(jié)21225.結(jié)論在上學(xué)期末幾天的時(shí)間中，我們對(duì)操作系統(tǒng)認(rèn)識(shí)還不是很清楚，所以兩個(gè)人的團(tuán)隊(duì)只設(shè)計(jì)了算法代碼還不完善在閱讀了各方面書籍和上網(wǎng)查了資料之后，經(jīng)過一個(gè)寒假的算法設(shè)計(jì)和測(cè)試，已經(jīng)能在MYec