試驗(yàn)三最佳適應(yīng)算法試驗(yàn)報(bào)告

1、最佳適應(yīng)算法實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康牧私馐状芜m應(yīng)算法、最佳適應(yīng)方法、最差適應(yīng)算法二、實(shí)驗(yàn)方法修改 Minix 操作系統(tǒng)的內(nèi)存分配源碼，實(shí)現(xiàn)最佳適應(yīng)算法三、實(shí)驗(yàn)任務(wù)修改 Minix 操作系統(tǒng)中的內(nèi)存分配源碼，將首次適應(yīng)算法更改為最佳適應(yīng)算 法。重新編譯系統(tǒng)映像文件，觀察實(shí)驗(yàn)結(jié)果。四、實(shí)驗(yàn)要點(diǎn)內(nèi)存分配、首次適應(yīng)算法、最佳適應(yīng)算法。五、實(shí)驗(yàn)內(nèi)容5.1 minix 內(nèi)存分配源碼安裝好 minix 操作系統(tǒng)以后， minix 系統(tǒng)的源碼位于 /usr/src 目錄中。其中， 與內(nèi)存分配的相關(guān)源碼則在 /usr/src/servers/pm/alloc.c 中。 minix 系統(tǒng)初始的內(nèi) 存分配算法為首次適應(yīng)

2、算法。在 minix 系統(tǒng)中，空閑的內(nèi)存空間信息采用鏈表的信息儲(chǔ)存起來(lái)，而操作系 統(tǒng)分配內(nèi)存空間的過(guò)程則是在這個(gè)鏈表中尋找一個(gè)合適空間，返回內(nèi)存空間的 地址，再更改鏈表中的內(nèi)存空間信息。這就是 minix 系統(tǒng)分配內(nèi)存的實(shí)質(zhì)。5.2 分析首次適應(yīng)算法首次適應(yīng)算法，指的從空閑內(nèi)存塊鏈表的第一個(gè)結(jié)點(diǎn)開始查找，把最先找 到的滿足需求的空閑內(nèi)存塊分配出去。這種算法的優(yōu)點(diǎn)是分配所需的時(shí)間較 短，但這種算法會(huì)形成低地址部分形成很多的空間碎片，高地址區(qū)保留大量長(zhǎng) 度較長(zhǎng)的空閑內(nèi)存塊。內(nèi)存分配的操作在 /usr/src/servers/pm/alloc.c 源文件中的 alloc_mem 函數(shù)中 完成。在函數(shù)

3、的初始位置，定義了兩個(gè)用于遍歷鏈表的指針變量，兩個(gè)指針變 量的定義如下：registerstruct hole *hp, *prev_ptr;而 hole 結(jié)構(gòu)體的定義如下：PRIVATE struct hole struct hole *h_next;phys_clicksh_base;phys_clicksh_len; holeNR_HOLES;先分析這個(gè)結(jié)構(gòu)體的定義，這個(gè)結(jié)構(gòu)體中，有三個(gè)變量， h_next 是一個(gè)指 向鏈表下一個(gè)結(jié)點(diǎn)的指針變量； h_base 則是指向這個(gè)鏈表所表示的空閑內(nèi)存空 間的地址，h_len則是這個(gè)空閑內(nèi)存空間的長(zhǎng)度；phys_clicks的定義可以在 /usr

4、/src/include/minix/type.h 中找至U, phys_clicks 的定義為：typedef unsigned intpyhs_clicks;phys_clicks其實(shí)就是無(wú)符號(hào)的整數(shù)類型。另外，在函數(shù)中，還有一個(gè)變量，old_base,數(shù)據(jù)類型為phys_clicks用于 保存找至的內(nèi)存空間地址。在尋找合適的內(nèi)存空間之前,先初始化兩個(gè)指針變量的值：prev_ptr = NIL_HOLE;hp = hole_head;這兩句代碼把 hp 這個(gè)指針變量指向了儲(chǔ)存空閑內(nèi)存空間鏈表的頭結(jié)點(diǎn)。而 prev_ptr指針在指針遍歷的過(guò)程中指向hp指針變量指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；此 時(shí), h

5、p 指針變量指向的是鏈表的頭結(jié)點(diǎn),所以 prev_ptr 的變量值為 NIL_HOLE。在為這兩個(gè)指針變量賦值以后，是通過(guò)一個(gè) while 循環(huán)，直到找到滿足需要 的內(nèi)存大小塊。循環(huán)代碼如下：while (hp != NIL_HOLE &hp-h_baseh_baseh_le n= clicks) prev_ptr=hp;hp=hp-h_next;結(jié)合上面對(duì)結(jié)構(gòu)體的分析，如果hp指向的鏈表結(jié)點(diǎn)中，空閑空間的長(zhǎng)度大于或等于請(qǐng)求分配的大小，則進(jìn)入if代碼塊；否則，prev_ptr和hp指向下一個(gè) 結(jié)點(diǎn)。如果找到操作系統(tǒng)找到了符合條件的空閑內(nèi)存塊，進(jìn)入if代碼塊；if代碼塊中的代碼，簡(jiǎn)單來(lái)說(shuō)可以分成

6、兩部分，第一部分是修改儲(chǔ)存空閑內(nèi)存塊信息 的鏈表；另外一部分就是把找到的地址返回。其中，第一部分的代碼如下：old_base = hp-h_base;hp-h_base += clicks;hp-h_len -= clicks;if (hp-h_len = 0)del_slot(prev_ptr, hp);第一行代碼，使用一個(gè)變量，把分配出去的內(nèi)存塊的首地址記錄下來(lái)；第 二行代碼，因?yàn)橐咽椎刂窞?hp-h_base,大小為clicks的內(nèi)存空間分配出去，所以要把這個(gè)空閑內(nèi)存塊的起始地址往后移動(dòng)clicks，即對(duì)hp-h_base變量進(jìn)行加法運(yùn)算；第三行代碼，更改空閑內(nèi)存塊的大小，即對(duì)hp-h

7、_len變量進(jìn)行減法操作。最后，進(jìn)行一個(gè)簡(jiǎn)單的判斷。如果長(zhǎng)度為 0，即表示這個(gè)鏈表結(jié)點(diǎn)表示的 空閑內(nèi)存塊已經(jīng)全部被分出去，要在鏈表中刪除這個(gè)結(jié)點(diǎn)。第二部分的代碼只有一句：return (old_base)把找到的滿足條件的內(nèi)存塊的首地址返回。上面整個(gè)的內(nèi)存塊尋找過(guò)程是放在一個(gè)dowhile循環(huán)中。循環(huán)語(yǔ)句為do while (swap_out()swap_out 函數(shù)的作用是尋找一個(gè)可以被從內(nèi)存中轉(zhuǎn)移到磁盤中的進(jìn)程，并 把它轉(zhuǎn)移到磁盤之中以騰出相應(yīng)的內(nèi)存空間。也就是說(shuō)，如果找不到合適的儲(chǔ) 存空間，系統(tǒng)會(huì)先嘗試把部分的進(jìn)程從內(nèi)存移動(dòng)到磁盤中；如果找不到合適的 內(nèi)存空間，而且也沒(méi)有可以被移動(dòng)到磁盤

8、的進(jìn)程時(shí)，整個(gè)函數(shù)就會(huì)返回NO_MEM,表示系統(tǒng)找不到合適的內(nèi)存空間。5.3 改寫為最佳適應(yīng)算法最佳適應(yīng)算法是從所有適合的空閑內(nèi)存塊找出最小的空閑內(nèi)存塊，這種方 法的優(yōu)點(diǎn)是產(chǎn)生的空閑內(nèi)存塊碎片最小。缺點(diǎn)是搜索合適內(nèi)存塊的空閑時(shí)間比 首次適應(yīng)算法長(zhǎng)，效率低。跟首次適應(yīng)算法不一樣的是，最佳適應(yīng)算法中，需要有一個(gè)變量，在查找 過(guò)程中記錄找到最小空閑內(nèi)存塊的大小和地址，如果剛好找到一個(gè)大小等于所 需要大小的空閑內(nèi)存塊，則立即返回，不再尋找。在函數(shù)的起始位置聲明一些變量，代碼如下：registerstruct hole *hp, *prev_ptr, *min_hp;phys_clicksold_bas

9、e, min_size, found = 0;其中， hp, prev_ptr 和 old_base 的變量含義與首次適應(yīng)算法中這些變兩個(gè)的 含義相同。 min_hp 是用于記錄儲(chǔ)存有大小最小并滿足需要的空閑內(nèi)存塊信息的 鏈表結(jié)點(diǎn)， min_size 則表示到目前為止找到的空閑內(nèi)存塊的最小的大小值，用 于查找過(guò)程中的大小比對(duì)。 found 則是一個(gè)標(biāo)記位，表示是否已經(jīng)找到了合適的 空閑內(nèi)存塊。修改以后，跟首次適應(yīng)算法一樣，查找空閑內(nèi)存塊的代碼放在一個(gè)dowhile循環(huán)中，其意義在于當(dāng)不能找到合適的空閑內(nèi)存塊時(shí)，操作系統(tǒng)先進(jìn) 行交換，再尋找空閑的內(nèi)存地址塊；如果對(duì)內(nèi)存空間進(jìn)行交換以后仍然沒(méi)有合

10、適的空閑內(nèi)存塊，則會(huì)返回一個(gè)內(nèi)存不足的錯(cuò)誤信息。在進(jìn)行尋找前，需要對(duì)一些變量進(jìn)行賦初值變量，賦初值的語(yǔ)句為：prev_ptr=NIL_HOLE;hp=hole_head;min_hp=NIL_HOLE;min_size=0xFFFF;found = 0;上面兩句代碼的意義與首次適應(yīng)算法中的語(yǔ)句意義相同，都是為了設(shè)置鏈 表遍歷操作的起點(diǎn)位置。把指向最小內(nèi)存塊對(duì)應(yīng)的鏈表結(jié)點(diǎn)的指針變量設(shè)置為 NIL_HOLE同時(shí)將標(biāo)記位設(shè)置為0,表示沒(méi)有找到滿足條件的空閑內(nèi)存塊。把 min_size的值設(shè)置為0xFFFF(unsigned in能夠表示的最大整數(shù))，以確保第一個(gè)空 閑的鏈表結(jié)點(diǎn)能夠始終滿足比 min

11、_size小的條件。用于尋找空閑內(nèi)存塊的代碼跟首次適應(yīng)算法一樣，都是通過(guò)while循環(huán)實(shí)現(xiàn),代碼如下：while (hp != NIL_HOLE &hp-h_baseh_len=clicks) old_base=hp-h_base;del_slot(prev_ptr, hp);return (old_base); else if (hp-h_lenclicks &hp-h_lenh_len;found = 1;prev_ptr=hp;hp=hp-h_next;如果 hp 指向鏈表結(jié)點(diǎn)內(nèi)存塊大小剛好與所請(qǐng)求的大小相等，這種是最佳適 應(yīng)算法最好的情況。把這個(gè)內(nèi)存塊的地址儲(chǔ)存起來(lái)，在鏈表中刪除這個(gè)結(jié)

12、點(diǎn)， 然后把這個(gè)地址返回。如果鏈表結(jié)點(diǎn)表示的空閑內(nèi)存塊大小比需要的大小大，但是比目前找到最 小的空閑內(nèi)存塊還要小，則把當(dāng)前這個(gè)結(jié)點(diǎn)記錄下來(lái)，再把標(biāo)記為置1，表示已經(jīng)找到可以分配出去的內(nèi)存空間。然后在通過(guò)移動(dòng) prev_ptr 和 hp 兩個(gè)指針變量 和 while 循環(huán)，遍歷整個(gè)鏈表。在整個(gè)鏈表遍歷完成以后， min_hp 則會(huì)指向滿 足需要內(nèi)存塊之中大小最小的內(nèi)存塊。第二部分的代碼是根據(jù)第一部分找到的內(nèi)存塊信息修改鏈表并把這個(gè)內(nèi)存 塊地址返回，這部分的代碼為：if (found = 1) old_base = min_hp-b_base;min_hp-h_base += clicks;min

13、_hp-h_len -= clicks;retur n （old_base）;這部分代碼先判斷標(biāo)記位，如果已經(jīng)找到了內(nèi)存塊，先把 內(nèi)存塊的地址記錄下來(lái)，然后把空閑地址往后移動(dòng)clicks，長(zhǎng)度減clicks。然后再把內(nèi)存塊的地址返回，這些操作與首次適應(yīng)算法是一樣的。5.4 minix 系統(tǒng)映像文件的編譯對(duì)代碼進(jìn)行修改以后，需要對(duì)代碼進(jìn)行編譯，再構(gòu)建映像文件。5.4.1 代碼的編譯代碼的編譯通過(guò) make工具進(jìn)行編譯。make工具會(huì)根據(jù)Makefile文件，自 動(dòng)編譯代碼文件。make工具可以避免了編譯過(guò)程中大量命令的輸入；同時(shí)，也 不需要程序員手動(dòng)理清各個(gè)代碼文件和各個(gè)模塊之間的依賴關(guān)系，大大提高開 發(fā)效率。退出編輯器，定位到目錄 /usr/src/servers/pm 下，輸入 make， make 工 具會(huì)自動(dòng)編譯源碼，當(dāng)沒(méi)有錯(cuò)誤以后，開始重新編譯系統(tǒng)映像文件。5.4.2 映像文件編譯與代碼的編譯類似，映像文件的編譯同樣是通過(guò)make工具實(shí)現(xiàn)。用于編譯系統(tǒng)映像文件的 Makefile在/usr/src/tools中