第八章 動態(tài)存儲管理

1、第第8章章 動態(tài)存儲管理動態(tài)存儲管理8.1 概述概述8.2 可利用空間表可利用空間表8.3 邊界標(biāo)識法邊界標(biāo)識法練習(xí)與作業(yè)練習(xí)與作業(yè) 在前面各章數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，對每一種數(shù)據(jù)在前面各章數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)中，對每一種數(shù)據(jù)結(jié)構(gòu)雖然介紹了它們在內(nèi)存儲器中的映象，但只是結(jié)構(gòu)雖然介紹了它們在內(nèi)存儲器中的映象，但只是借助高級語言中的變量說明加以描述，并沒涉及具借助高級語言中的變量說明加以描述，并沒涉及具體的體的存儲分配存儲分配。 而實(shí)際上，結(jié)構(gòu)中的每個數(shù)據(jù)元素都占有一定而實(shí)際上，結(jié)構(gòu)中的每個數(shù)據(jù)元素都占有一定的內(nèi)存位置在程序執(zhí)行的過程中，數(shù)據(jù)元素的存的內(nèi)存位置在程序執(zhí)行的過程中，數(shù)據(jù)元素的存取是通過對應(yīng)的存儲

2、單元來進(jìn)行的。取是通過對應(yīng)的存儲單元來進(jìn)行的。 在早期的計算機(jī)上，這個存儲管理的工作是由在早期的計算機(jī)上，這個存儲管理的工作是由程序員自己完成的，在程序執(zhí)行之前首先需要用程序員自己完成的，在程序執(zhí)行之前首先需要用機(jī)器語言或匯編語言編寫的程序輸送到內(nèi)存的某個機(jī)器語言或匯編語言編寫的程序輸送到內(nèi)存的某個固定區(qū)域上，并預(yù)先給變量和數(shù)據(jù)分配好對應(yīng)的內(nèi)固定區(qū)域上，并預(yù)先給變量和數(shù)據(jù)分配好對應(yīng)的內(nèi)存地址存地址(絕對地址或相對地址絕對地址或相對地址)。 在有了高級語言之后，程序員不需要直接和內(nèi)在有了高級語言之后，程序員不需要直接和內(nèi)存地址打交道，程序中使用的存儲單元都由邏輯變存地址打交道，程序中使用的存儲單

3、元都由邏輯變量量(標(biāo)識符標(biāo)識符)來表示它們對應(yīng)的內(nèi)存地址都是由編來表示它們對應(yīng)的內(nèi)存地址都是由編譯程序在編譯或執(zhí)行時進(jìn)行分配。譯程序在編譯或執(zhí)行時進(jìn)行分配。 當(dāng)計算機(jī)是被單個用戶使用時，那么整個內(nèi)存當(dāng)計算機(jī)是被單個用戶使用時，那么整個內(nèi)存除操作系統(tǒng)占用一部分之外，都?xì)w這個用戶的程序除操作系統(tǒng)占用一部分之外，都?xì)w這個用戶的程序使用。但在多用戶分時并發(fā)系統(tǒng)中多個用戶程序使用。但在多用戶分時并發(fā)系統(tǒng)中多個用戶程序共享一個內(nèi)存區(qū)域，此時每個用戶程序使用的內(nèi)存共享一個內(nèi)存區(qū)域，此時每個用戶程序使用的內(nèi)存就由操作系統(tǒng)來進(jìn)行分配了。就由操作系統(tǒng)來進(jìn)行分配了。 對操作系統(tǒng)和編譯程序來說，存儲管理是一個對操作系

4、統(tǒng)和編譯程序來說，存儲管理是一個復(fù)雜而又重要的問題。復(fù)雜而又重要的問題。 動態(tài)存儲管理的基本問題是：動態(tài)存儲管理的基本問題是：系統(tǒng)如響應(yīng)用戶提出的系統(tǒng)如響應(yīng)用戶提出的“請求請求”分配內(nèi)存分配內(nèi)存?又如何回收那些用戶不再使用而又如何回收那些用戶不再使用而“釋放釋放”的內(nèi)的內(nèi)存，以備新的存，以備新的”請求請求”產(chǎn)生時重新進(jìn)行分配產(chǎn)生時重新進(jìn)行分配? 提出請求的用戶要求分配的內(nèi)存量大小不同例提出請求的用戶要求分配的內(nèi)存量大小不同例如，在編譯程序中是一個或幾十字，而在系統(tǒng)中則如，在編譯程序中是一個或幾十字，而在系統(tǒng)中則是幾千、幾萬，甚至是幾十萬。通常，系統(tǒng)每次分是幾千、幾萬，甚至是幾十萬。通常，系統(tǒng)每

5、次分配給用戶配給用戶(不論大?。┒际且粋€地址連續(xù)的內(nèi)存區(qū)。不論大?。┒际且粋€地址連續(xù)的內(nèi)存區(qū)。 將系統(tǒng)已分配給用戶使用的地址連續(xù)的內(nèi)存區(qū)為將系統(tǒng)已分配給用戶使用的地址連續(xù)的內(nèi)存區(qū)為“占用占用塊塊”，稱未曾分配的地址連續(xù)的內(nèi)存區(qū)為，稱未曾分配的地址連續(xù)的內(nèi)存區(qū)為“可利用空間塊可利用空間塊”或或“空閑塊空閑塊”。 不管什么樣的動態(tài)存儲管理系統(tǒng)在剛開工時，整個內(nèi)不管什么樣的動態(tài)存儲管理系統(tǒng)在剛開工時，整個內(nèi)存區(qū)是一個存區(qū)是一個“空閑塊空閑塊” 。隨著用戶進(jìn)入系統(tǒng)，先后提出存。隨著用戶進(jìn)入系統(tǒng)，先后提出存儲請求，系統(tǒng)依次進(jìn)行分配。因此，在系境運(yùn)行的初期，儲請求，系統(tǒng)依次進(jìn)行分配。因此，在系境運(yùn)行的初期

6、，整個內(nèi)存區(qū)基本上分隔成兩大部分，整個內(nèi)存區(qū)基本上分隔成兩大部分， 低地址區(qū)低地址區(qū)包含若干占用塊；包含若干占用塊； 高地址區(qū)高地址區(qū)(即分配后的剩余部分即分配后的剩余部分)是一個是一個“空閑塊空閑塊。 經(jīng)過一段時間以后，有的用戶運(yùn)行結(jié)束，它所占用的內(nèi)經(jīng)過一段時間以后，有的用戶運(yùn)行結(jié)束，它所占用的內(nèi)存區(qū)變成空閑塊，這使整個內(nèi)存區(qū)呈現(xiàn)出占用塊和空閑塊存區(qū)變成空閑塊，這使整個內(nèi)存區(qū)呈現(xiàn)出占用塊和空閑塊交錯的狀態(tài)。交錯的狀態(tài)。 U0U1U2U3U4U5U0 U3U5 有新的用戶進(jìn)入系統(tǒng)請求分配內(nèi)存，那么系統(tǒng)將如間做呢？有新的用戶進(jìn)入系統(tǒng)請求分配內(nèi)存，那么系統(tǒng)將如間做呢？ 系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)

7、行分配，面不理會已分配給系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，面不理會已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行(即剩的空閑塊即剩的空閑塊不能滿足分配的請求不能滿足分配的請求)時，系統(tǒng)才去回收所有用戶不再使用的時，系統(tǒng)才去回收所有用戶不再使用的空閑塊，并且重新組織內(nèi)存，將所有空閑的內(nèi)存區(qū)連接在一空閑塊，并且重新組織內(nèi)存，將所有空閑的內(nèi)存區(qū)連接在一起成為一個大的空閑塊。起成為一個大的空閑塊。用戶一旦運(yùn)行結(jié)束，便將它所占內(nèi)存區(qū)釋放成為空閑塊同用戶一旦運(yùn)行結(jié)束，便將它所占內(nèi)存區(qū)釋放成為空閑塊同時，每當(dāng)新的用戶請求分配內(nèi)存時，系統(tǒng)需要巡視整個內(nèi)存時，每當(dāng)新的

8、用戶請求分配內(nèi)存時，系統(tǒng)需要巡視整個內(nèi)存區(qū)中所有空閑塊，并從中找出一個區(qū)中所有空閑塊，并從中找出一個“合適合適的空閑塊分配之。的空閑塊分配之。 系統(tǒng)需要建立一張記錄所有空閑塊的系統(tǒng)需要建立一張記錄所有空閑塊的“可利用空間表可利用空間表”，其結(jié)構(gòu)可以是其結(jié)構(gòu)可以是“目錄表目錄表”，也可以是，也可以是“鏈表鏈表”。 0 10000 31000 59000 99999 25000 3900001000015000空閑空閑310008000空閑空閑5900041000空閑空閑起始地址起始地址 內(nèi)存塊大小內(nèi)存塊大小 使用情況使用情況01500010000080003100004100059000av返回

9、返回 本節(jié)主要學(xué)習(xí)利用基于鏈表結(jié)構(gòu)的可利用本節(jié)主要學(xué)習(xí)利用基于鏈表結(jié)構(gòu)的可利用空間表進(jìn)行動態(tài)存儲分配的方法空間表進(jìn)行動態(tài)存儲分配的方法 。一、可利用空間表的三種結(jié)構(gòu)一、可利用空間表的三種結(jié)構(gòu) 可利用空間表中包含所有可分配的空閑可利用空間表中包含所有可分配的空閑塊，每一塊是鏈表中的一個結(jié)點(diǎn)。當(dāng)用戶請塊，每一塊是鏈表中的一個結(jié)點(diǎn)。當(dāng)用戶請求分配時，系統(tǒng)從可利用空間表中刪除一個求分配時，系統(tǒng)從可利用空間表中刪除一個結(jié)點(diǎn)分配之；當(dāng)用戶釋放其所占內(nèi)存時，系結(jié)點(diǎn)分配之；當(dāng)用戶釋放其所占內(nèi)存時，系統(tǒng)即回收并將它插入到可利用空間表中。因統(tǒng)即回收并將它插入到可利用空間表中。因此，可利用空間表亦稱作此，可利用空間

10、表亦稱作“存儲池存儲池”。根據(jù)。根據(jù)系統(tǒng)運(yùn)行的不同情況，可利用空間表可以有系統(tǒng)運(yùn)行的不同情況，可利用空間表可以有下列三種不同的結(jié)構(gòu)形式：下列三種不同的結(jié)構(gòu)形式： 系統(tǒng)運(yùn)行期間所有用戶請求分配的存儲量系統(tǒng)運(yùn)行期間所有用戶請求分配的存儲量大小相同。大小相同。 動態(tài)存儲分配策略：在系統(tǒng)開始運(yùn)行時將動態(tài)存儲分配策略：在系統(tǒng)開始運(yùn)行時將歸它使用的內(nèi)存區(qū)按所需大小歸它使用的內(nèi)存區(qū)按所需大小分割成若于分割成若于大小相同的塊大小相同的塊，然后用指針鏈接成一個可，然后用指針鏈接成一個可利用空間表。由于表中節(jié)點(diǎn)大小相同，則利用空間表。由于表中節(jié)點(diǎn)大小相同，則分配時無需查找，只要將第一個結(jié)點(diǎn)分配分配時無需查找，只要

11、將第一個結(jié)點(diǎn)分配給用戶即可；同樣，當(dāng)用戶釋放內(nèi)存時，給用戶即可；同樣，當(dāng)用戶釋放內(nèi)存時，系統(tǒng)只要將用戶釋放的空閑塊插入在表頭系統(tǒng)只要將用戶釋放的空閑塊插入在表頭即可，可見這種情況下的可利用空間表實(shí)即可，可見這種情況下的可利用空間表實(shí)質(zhì)上是一個鏈棧。質(zhì)上是一個鏈棧。 系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有若干種大小的規(guī)格。系統(tǒng)運(yùn)行期間用戶請求分配的存儲量有若干種大小的規(guī)格。 動態(tài)存儲分配策略：動態(tài)存儲分配策略：建立若干個可利用空間表，同一鏈表建立若干個可利用空間表，同一鏈表中的結(jié)點(diǎn)大小相同。中的結(jié)點(diǎn)大小相同。 例如，某動態(tài)存儲管理系統(tǒng)中的用戶將請求分配例如，某動態(tài)存儲管理系統(tǒng)中的用戶將請求分配2個字

12、、個字、4個字或個字或8個字的內(nèi)存塊，則系統(tǒng)建立三個結(jié)點(diǎn)大小分別為個字的內(nèi)存塊，則系統(tǒng)建立三個結(jié)點(diǎn)大小分別為3個字、個字、5個字和個字和9個字的鏈表，它們的表頭指針分別為個字的鏈表，它們的表頭指針分別為av2、av4和和av8 tagtypelinkvalue標(biāo)志域標(biāo)志域 類型域類型域 鏈域鏈域tag 0 空閑塊空閑塊 1 占用塊占用塊tag 0 大小為大小為2個字個字 1 大小為大小為4個字個字 2 大小為大小為8個字個字000000av2010101av4020202av8 分配和回收策略：和第一種情況類似，只是當(dāng)分配和回收策略：和第一種情況類似，只是當(dāng)結(jié)點(diǎn)大小和請求分配的量相同的鏈表為空

13、時，需結(jié)點(diǎn)大小和請求分配的量相同的鏈表為空時，需查詢結(jié)點(diǎn)較大的鏈表，并從中取出一個結(jié)點(diǎn)，將查詢結(jié)點(diǎn)較大的鏈表，并從中取出一個結(jié)點(diǎn)，將其中一部分內(nèi)存分配給用戶，而將剩余部分插入其中一部分內(nèi)存分配給用戶，而將剩余部分插入到相應(yīng)大小的鏈表中?；厥諘r，也只要將釋放的到相應(yīng)大小的鏈表中。回收時，也只要將釋放的空閑塊插入到相應(yīng)大小的鏈表的表頭中去即可?？臻e塊插入到相應(yīng)大小的鏈表的表頭中去即可。 需要處理的一個特殊的問題：需要處理的一個特殊的問題：即當(dāng)結(jié)點(diǎn)與請求即當(dāng)結(jié)點(diǎn)與請求相符的鏈表和結(jié)點(diǎn)更大的鏈表均為空時，分配不相符的鏈表和結(jié)點(diǎn)更大的鏈表均為空時，分配不能進(jìn)行，而實(shí)際上內(nèi)存空間并不一定不存在所需能進(jìn)行，

14、而實(shí)際上內(nèi)存空間并不一定不存在所需大小的連續(xù)空間，只是由于在系統(tǒng)運(yùn)行過程中，大小的連續(xù)空間，只是由于在系統(tǒng)運(yùn)行過程中，頻繁出現(xiàn)小塊的分配和回收、使得大結(jié)點(diǎn)鏈表中頻繁出現(xiàn)小塊的分配和回收、使得大結(jié)點(diǎn)鏈表中的空閑塊被分隔成小塊后插入在小結(jié)點(diǎn)的鏈表中，的空閑塊被分隔成小塊后插入在小結(jié)點(diǎn)的鏈表中，此時若要使系統(tǒng)繼續(xù)運(yùn)行，就必須重新組織內(nèi)存，此時若要使系統(tǒng)繼續(xù)運(yùn)行，就必須重新組織內(nèi)存，即執(zhí)行即執(zhí)行“存儲緊縮存儲緊縮”的操作。的操作。 系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請求而變。因此，可利用空間表中的結(jié)點(diǎn)即空可以隨請求而變。因此，可利用空間表

15、中的結(jié)點(diǎn)即空閑塊的大小也是隨意的。通常，操作系統(tǒng)中的可利用閑塊的大小也是隨意的。通常，操作系統(tǒng)中的可利用空間表屬這種類型。例如：空間表屬這種類型。例如：U0U1U2U3U4U5U0 U3U5tagsizelinkspacetag 0 空閑塊空閑塊 1 占用塊占用塊size：指示空閑塊的存儲量：指示空閑塊的存儲量 假設(shè)某用戶需大小為假設(shè)某用戶需大小為n的內(nèi)存，而可利用空間表中僅的內(nèi)存，而可利用空間表中僅有一塊大小為有一塊大小為mn的空閑塊，剛只需將其中大小為的空閑塊，剛只需將其中大小為n的的一部分分配給申請分配的用戶，同時將剩余大小為一部分分配給申請分配的用戶，同時將剩余大小為mn的部分作為一個

16、節(jié)點(diǎn)留在鏈表中即可。然而，若可利的部分作為一個節(jié)點(diǎn)留在鏈表中即可。然而，若可利用空間表中有若干個不小于用空間表中有若干個不小于n的空閑塊時，該分配哪一的空閑塊時，該分配哪一塊呢塊呢?通常，可有三種不同的分配策略：通常，可有三種不同的分配策略： 1、首次擬合法首次擬合法：從在頭指針開查找可利田空間表，將：從在頭指針開查找可利田空間表，將找到的第一個大小不小于找到的第一個大小不小于n的空閑塊的的空閑塊的部分分配給用部分分配給用戶。戶。 可利用空間表本身既不按結(jié)點(diǎn)的初始地址有序，也可利用空間表本身既不按結(jié)點(diǎn)的初始地址有序，也不按結(jié)點(diǎn)的大小有序。在回收時，只將釋放的空閑塊不按結(jié)點(diǎn)的大小有序。在回收時，

17、只將釋放的空閑塊插入在鏈表的表頭即可。插入在鏈表的表頭即可。15000010000800003100041000059000av例如，如上圖所示的空間狀態(tài)下，一個用戶進(jìn)入系統(tǒng)并申請例如，如上圖所示的空間狀態(tài)下，一個用戶進(jìn)入系統(tǒng)并申請7K的內(nèi)存，如何進(jìn)行分配？的內(nèi)存，如何進(jìn)行分配？ 系統(tǒng)在可利用空間表中進(jìn)行查詢，發(fā)現(xiàn)第一個空閑塊即系統(tǒng)在可利用空間表中進(jìn)行查詢，發(fā)現(xiàn)第一個空閑塊即滿足要求，則將此塊中大小為滿足要求，則將此塊中大小為7K的一部分分配之，剩余的一部分分配之，剩余8k的的空閘塊仍在鏈表中空閘塊仍在鏈表中15000010000800003100041000059000av700011800

18、02、最佳擬合法。將可利用空間表中一個不小于、最佳擬合法。將可利用空間表中一個不小于n且最接近且最接近n的的空閑塊的一部分分配給用戶。則系統(tǒng)在分配前首先要對可利空閑塊的一部分分配給用戶。則系統(tǒng)在分配前首先要對可利用空間表從頭到尾掃視一遍，然后從中找出一塊不小于用空間表從頭到尾掃視一遍，然后從中找出一塊不小于n且且最接近最接近n的空閑塊進(jìn)行分配。的空閑塊進(jìn)行分配。 15000010000100003100041000059000av700013200015000010000800003100041000059000av預(yù)先設(shè)定可利用預(yù)先設(shè)定可利用空間表的結(jié)構(gòu)按空間表的結(jié)構(gòu)按空間塊的空間塊的大小自

19、大小自小至大有序小至大有序，由，由此只需找到第此只需找到第一塊大于一塊大于n的空閑的空閑塊即可進(jìn)行分配，塊即可進(jìn)行分配，但在回收時，必但在回收時，必須將釋放的空鬧須將釋放的空鬧塊插入到合適的塊插入到合適的位置上去。位置上去。3、最差擬合法：將可利用空間表中不小于、最差擬合法：將可利用空間表中不小于n且是鏈表中最大且是鏈表中最大的空閑塊的一部分分配給用戶。的空閑塊的一部分分配給用戶。 15000010000800003100034000059000av700019300015000010000800003100041000059000av為了節(jié)省時間，此時的可為了節(jié)省時間，此時的可利用空間表的結(jié)

20、構(gòu)按空閑利用空間表的結(jié)構(gòu)按空閑塊的大小塊的大小自大至小有序自大至小有序。這樣，每次分配無需查找，這樣，每次分配無需查找，只需從鏈表中刪除第只需從鏈表中刪除第一個結(jié)點(diǎn)，并將其中一部一個結(jié)點(diǎn)，并將其中一部分分配給用戶，而剩余部分分配給用戶，而剩余部分作為一個新的結(jié)點(diǎn)插入分作為一個新的結(jié)點(diǎn)插入到可利用空間表的適當(dāng)位到可利用空間表的適當(dāng)位置上去。當(dāng)然，在回收時置上去。當(dāng)然，在回收時亦需將釋放的空間塊插入亦需將釋放的空間塊插入到鏈表的適當(dāng)位置上去。到鏈表的適當(dāng)位置上去。三種方法的比較：三種方法的比較：各有所長。各有所長。 最佳擬合法最佳擬合法適用于請求分配大小范圍較廣的系統(tǒng)。問題是適用于請求分配大小范圍

21、較廣的系統(tǒng)。問題是在分配的過程中找到大小最相近的空閑塊，因此容易產(chǎn)生在分配的過程中找到大小最相近的空閑塊，因此容易產(chǎn)生無法利用的較小內(nèi)存片，同時，也保留較大的內(nèi)存塊以備無法利用的較小內(nèi)存片，同時，也保留較大的內(nèi)存塊以備后續(xù)使用。后續(xù)使用。 最差擬合法最差擬合法每次都從內(nèi)存量最大的結(jié)點(diǎn)中進(jìn)行分配，從而每次都從內(nèi)存量最大的結(jié)點(diǎn)中進(jìn)行分配，從而使鏈表中的結(jié)點(diǎn)大小趨于均勻，四此它適用于請求分配的使鏈表中的結(jié)點(diǎn)大小趨于均勻，四此它適用于請求分配的內(nèi)存大小范圍較窄的系繞。內(nèi)存大小范圍較窄的系繞。 首次擬合法首次擬合法的分配是隨機(jī)的，因此它介于兩者之間，通常的分配是隨機(jī)的，因此它介于兩者之間，通常適用于系統(tǒng)

22、事先不掌握運(yùn)行期間可能出現(xiàn)的請求分配和釋適用于系統(tǒng)事先不掌握運(yùn)行期間可能出現(xiàn)的請求分配和釋放的信息的情況。放的信息的情況。 從時間上來比較，首次擬合在分配時需查詢可利用空間表從時間上來比較，首次擬合在分配時需查詢可利用空間表而回收時僅需插入在表頭即可；最差擬合恰相反，分配時而回收時僅需插入在表頭即可；最差擬合恰相反，分配時無需查詢鏈表，而回收時為將新的空閑塊插入在鏈表中適無需查詢鏈表，而回收時為將新的空閑塊插入在鏈表中適當(dāng)?shù)奈恢蒙?，需先進(jìn)行查找；最佳擬合無論分配和回收，當(dāng)?shù)奈恢蒙?，需先進(jìn)行查找；最佳擬合無論分配和回收，均需查找鏈表，因此最費(fèi)時間。均需查找鏈表，因此最費(fèi)時間。選取原則：選取原則：

23、不同的情景需采用不同的方法不同的情景需采用不同的方法 因素：用戶的邏輯要求；請求分配量的大小分布；分配和因素：用戶的邏輯要求；請求分配量的大小分布；分配和釋放的頻率以及效率對系統(tǒng)的重要性等等。釋放的頻率以及效率對系統(tǒng)的重要性等等。 返回返回 邊界標(biāo)識法邊界標(biāo)識法是操作系統(tǒng)中用以進(jìn)行動態(tài)分是操作系統(tǒng)中用以進(jìn)行動態(tài)分配的一種存儲管理方法，屬于第三種情況。配的一種存儲管理方法，屬于第三種情況。將所有的空閑塊鏈接在一個雙重循環(huán)鏈表中：將所有的空閑塊鏈接在一個雙重循環(huán)鏈表中：分配可按首次擬和，也可按最佳擬和進(jìn)行。分配可按首次擬和，也可按最佳擬和進(jìn)行。 特點(diǎn)：每個內(nèi)存區(qū)的頭部和底部兩個邊界分特點(diǎn)：每個內(nèi)存

24、區(qū)的頭部和底部兩個邊界分別設(shè)有標(biāo)識，以標(biāo)識該區(qū)域?yàn)檎加脡K或是空別設(shè)有標(biāo)識，以標(biāo)識該區(qū)域?yàn)檎加脡K或是空閑塊，以便在回收空間十判定相鄰位置是否閑塊，以便在回收空間十判定相鄰位置是否為空閑塊，使得地址連續(xù)的空閑空間組合成為空閑塊，使得地址連續(xù)的空閑空間組合成一個盡可能大的空閑塊。一個盡可能大的空閑塊。一、可利用空間表的結(jié)構(gòu)：一、可利用空間表的結(jié)構(gòu)：taguplinkrlinksizetagllinkheadfootspacespace ：地址連續(xù)存儲單元：地址連續(xù)存儲單元head邊界：邊界：tag0 空閑空閑 1占用占用 size整個節(jié)點(diǎn)大小，包括整個節(jié)點(diǎn)大小，包括head和和foot llink前

25、驅(qū)節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn) rlink后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)Foot邊界：邊界： tag0 空閑空閑 1占用占用 uplink指向本節(jié)點(diǎn)首地址指向本節(jié)點(diǎn)首地址表中不設(shè)置表頭節(jié)點(diǎn)，表頭指針可以在任意節(jié)點(diǎn)。表中不設(shè)置表頭節(jié)點(diǎn)，表頭指針可以在任意節(jié)點(diǎn)。數(shù)據(jù)類型描述：數(shù)據(jù)類型描述： typedef struct WORD/內(nèi)存字內(nèi)存字 union WORD *link; WORD *uplink; int tag; int size; WORD *rlink; WORD,head,foot,*Space;二、分配算法：采用首次擬和法，即從二、分配算法：采用首次擬和法，即從pav開始查找第開始查找第一個容量不小于請求存儲

26、量一個容量不小于請求存儲量n的空閑塊進(jìn)行分配。的空閑塊進(jìn)行分配。 約定：約定： 1、若找到空閑塊大小為、若找到空閑塊大小為m(m=n)，則，若，則，若m-nsizerlink!pav;p=p-rlink); if(!p|p-sizerlink; if(p-size-nllink=p-llink;p-llink-rlink=pav; p-tag=f-tag=1; else f-tag=1;p-size=p-size-n;/修改分配塊底部修改分配塊底部 f=FootLoc(p);/p減小重新定位減小重新定位 f-tag=0; f-uplink=p; p=f+1;p-tag=1;p-size=n； return p; 三、回收算法：通過標(biāo)志位判定占用塊的左右近鄰是否為空閑三、回收算法：通過標(biāo)志位判定占用塊的左右近鄰是否為空閑塊，是否需要進(jìn)行空閑塊合并。塊，是否需要進(jìn)行空閑塊合并。 若釋放空閑塊頭部地址為若釋放空閑塊頭部地址為p，則低地址近鄰的底部地址為，則低地址近鄰的底部地址為p-1，高地址近鄰的頭部地址為，高地址近鄰的頭部地址為p+p-size，