操作系統(tǒng)第二次實(shí)驗(yàn)first-fit,next-fit

1、操作系統(tǒng)第二次實(shí)驗(yàn)報(bào)告物聯(lián)網(wǎng)1301 齊亨 13516110一、實(shí)驗(yàn)簡(jiǎn)介本實(shí)驗(yàn)要求建造一個(gè)沒(méi)有虛擬功能的內(nèi)存管理系統(tǒng)。任務(wù)如下： 設(shè)計(jì)一個(gè)內(nèi)存管理器，支持至少兩種分配策略, 如first-fit, next-fit,best-fit, worst-fit 等。 對(duì)不同分配策略的性能進(jìn)行評(píng)估。二、實(shí)驗(yàn)過(guò)程1、first fit(首次適應(yīng))首次適應(yīng)策略的思路是，分配時(shí)在空閑塊列表中搜索，找到第一個(gè)能夠滿足請(qǐng)求的塊即停止搜索，然后把搜索到的塊分割，一部分返回給請(qǐng)求者，另一部分仍然作為空閑塊留在空閑列表的原來(lái)位置。首次適應(yīng)策略的問(wèn)題在于，鏈表頭部區(qū)域的塊傾向于被首先分割，經(jīng)過(guò)一段時(shí)間后，空閑鏈表頭部可

2、能堆積大量小的空閑塊，這會(huì)導(dǎo)致搜索時(shí)間的增加，因?yàn)楫?dāng)請(qǐng)求一個(gè)頭部區(qū)域的小塊無(wú)法滿足的塊時(shí)，需要順次檢查這些小塊。代碼如下：#include #include #include int array99;int *array_request(int n)int count=0;int *p=&array0;int *l=&array99;while(countn & p!=l)if(*p=0)count+;p+;elsecount=0;p+;if(countn & p=l)return NULL;elsep=p-n;int *point;point=p;for(int a=0;an;a+)*p=1

3、;p+;return point;int array_release(int *p,int m)for(int n=0;nm;n+)*p=0;p+;return 0;int main()int i=0;for(;i99;i+)arrayi=0;int m_array20;int *pp20;int t=0,tt=0;int number=0,count=0;for(i=0;i=15 | r=2);m_arraynumber=r;printf(n第%d塊內(nèi)存的大小為 %d n,number,r);ppnumber=array_request(m_arraynumber);if(ppnumber=

4、NULL)printf(溢出n);return 0;elseprintf(寫(xiě)入內(nèi)存后n);for(int k=0;k99;k+)if(k%10=0)printf(“n”);printf(%d,arrayk);else if(choice=2)printf(n請(qǐng)輸入要釋放的內(nèi)存塊號(hào)數(shù) 1-%d n,number);count-;scanf(%d,&tt);array_release(pptt,m_arraytt);printf(n釋放后n);for(int k=0;k99;k+)if(k%10=0)printf(“n”);printf(%d,arrayk);elseprintf(errorn);

5、return 0;（1） 釋放第2,3塊內(nèi)存，以使內(nèi)存分裂成塊（2） 繼續(xù)寫(xiě)入內(nèi)存,按照f(shuō)irst fit的原理，靠前的內(nèi)存塊首先被分割（3） 當(dāng)處于前位置的內(nèi)存塊不足以容納數(shù)據(jù)時(shí)，開(kāi)始分配靠后的數(shù)據(jù)塊（4） 當(dāng)所剩數(shù)據(jù)塊不夠時(shí)，報(bào)溢出錯(cuò)誤，不夠的數(shù)據(jù)塊不再分配（此圖是重新執(zhí)行之后的圖，所以與之前的數(shù)據(jù)有所不一樣）2、next fitnext fit（下次適應(yīng)）策略是作為first fit 的優(yōu)化策略提出的。在nextfit 策略下，使用一個(gè)指針記錄上次搜索完成時(shí)的位置。下次分配時(shí)，從該記錄位置開(kāi)始搜索，到達(dá)鏈表尾部時(shí)則繞回。如此，多次分配時(shí)，該指針便在空閑鏈表內(nèi)循環(huán)游動(dòng)，從而避免在鏈表頭部區(qū)

6、域堆積過(guò)多的小碎片，提高搜索效率。代碼如下：#include #include #include int array99;int *p=&array0;int *array_request(int n)int count=0;int *l=&array99;int k=0;while(countn&k99 )/if (*p=0)count+;p+;else if(*p=1)count=0;p+;k+;if(k=99)/return NULL;elsep=p-n;int *point;point=p;for(int a=0;an;a+)*p=1;p+;return point;int array

7、_release(int *p,int m)for(int n=0;nm;n+) *p=0;p+;return 0;int main()for (int c=0;c99;c+)arrayc=0; int m_array9;int *pp9;int t=0,tt=0;int number=0,count=0;for (int c=0;c=25|r=2);m_arraynumber=r;ppnumber=0;printf(%dn,number,r);ppnumber=array_request(m_arraynumber);if(ppnumber=NULL)printf(溢出n);return 0

8、;elseprintf(寫(xiě)入內(nèi)存后n);for (int k=0;k99;k+)printf(%d,arrayk);else if(a=2)printf(n請(qǐng)輸入想要的內(nèi)存號(hào)%dn,number);count-;scanf(%d,&tt);array_release(pptt, m_arraytt);printf(n釋放后n);for (int k=0;k99;k+)printf(%d,arrayk);elseprintf(errorn);return 0;運(yùn)行截圖如下：（1）首先分配4塊內(nèi)存，內(nèi)存大小由rand()隨機(jī)數(shù)決定已分配過(guò)的內(nèi)存置為1未占用的內(nèi)存置為04塊內(nèi)存的大小分別為8，12,

9、3,9（2） 釋放第2,3塊內(nèi)存，以使內(nèi)存分裂成塊（3） 繼續(xù)寫(xiě)入內(nèi)存,按照next fit的原理，靠前的內(nèi)存塊不做變化，繼續(xù)分配較后的內(nèi)存塊一直分配到內(nèi)存近滿（3）繼續(xù)分配內(nèi)存塊 ，指針繞道內(nèi)存頭部繼續(xù)分配（4） 當(dāng)所剩任何一個(gè)數(shù)據(jù)塊都不夠容納數(shù)據(jù)時(shí)，報(bào)溢出錯(cuò)誤，不夠的數(shù)據(jù)塊不再分配四、實(shí)驗(yàn)分析First_fit內(nèi)存利用率實(shí)驗(yàn)程序#include #include #include int array999;int countt=0;int *array_request(int n)int *p=&array0;int count=0;int *l=&array999;while(count

10、n& p!=l )if (*p=0)count+;p+;else count=0;p+;countt+;if(countreturn NULL;elsep=p-n;int *point;point=p;for(int a=0;an;a+)*p=1;p+;return point;int array_release(int *p,int m)for(int n=0;nm;n+) *p=0;p+;*p=NULL;return 0;int main()for (int c=0;c999;c+)/arrayc=0; int m_array999;int *pp999;int number=0,coun

11、t=0;for (int c=0;c=15|r=2);m_arraynumber=r;ppnumber=array_request(m_arraynumber);if(ppnumber=NULL)printf(first_fitn);for(int n=0;n=15|r=2);m_arraynumber=r;ppnumber=array_request(m_arraynumber);if(ppnumber=NULL)printf(first_fitn);int num=0;for(int n=0;ncount|ppsuiji2=NULL);array_release(ppsuiji2, m_a

12、rraysuiji2);count-;return 0;試驗(yàn)截圖如下：Next_fit內(nèi)存利用率實(shí)驗(yàn)程序：#include #include #include int array999;int *p=&array0;int countt=0;int *array_request(int n)int count=0;int *l=&array999;int *t=&array0;int k=0;while(countn&k999 )if(p=l)p=t;count=0;elseif (*p=0)count+;p+;else if(*p=1)count=0;countt+;p+;k+;if(k=9

13、99)return NULL;elsep=p-n;int *point;point=p;for(int a=0;an;a+)*p=1;p+;return point;int array_release(int *p,int m)for(int n=0;nm;n+) *p=0;p+;*p=NULL;return 0;int main()for (int c=0;c999;c+)arrayc=0; int m_array999;int *pp999;int number=0,count=0;for (int c=0;c=15|r=2);m_arraynumber=r;ppnumber=array_request(m_arraynumber);if(ppnumber=NULL)printf(next_fitn);for(int n=0;n=15|r=2);m_arraynumber=r;ppnumber=array_request(m_arraynumber);if(ppnumber=NULL)int aa=0;printf(next_fitn);for(int n=0;ncount|ppsuiji2=NULL);array_rel