編譯原理 第8章 程序運(yùn)行時的存儲組織課件

編譯原理第8章程序運(yùn)行時的存儲組織1第8章程序運(yùn)行時的存儲組織及管理(P158)8.1程序運(yùn)行時的存儲組織8.2靜態(tài)存儲分配8.3棧式動態(tài)存儲分配8.4堆式動態(tài)存儲分配第8章程序運(yùn)行時的存儲組織及管理(P158)2學(xué)習(xí)重點(diǎn)影響存儲分配策略的語言特征靜態(tài)存儲分配動態(tài)存儲分配活動記錄堆式存儲分配變長塊的方法學(xué)習(xí)重點(diǎn)3影響存儲分配策略的語言特征:

過程能否遞歸過程能否嵌套過程調(diào)用時參數(shù)如何傳遞哪些實(shí)體可以作為參數(shù)和返回值是否允許動態(tài)的為對象分配和撤銷存儲空間存儲空間是否必須顯式地釋放……第8章程序運(yùn)行時的存儲組織及管理影響存儲分配策略的語言特征:第8章程序運(yùn)行時的存儲組4程序運(yùn)行時，系統(tǒng)將為程序分配一塊存儲空間。這塊空間用來存儲程序的目標(biāo)代碼以及目標(biāo)代碼運(yùn)行時需要或產(chǎn)生的各種數(shù)據(jù)。從用途上看，這塊空間可分為以下幾個部分：1）目標(biāo)程序區(qū)：用來存放目標(biāo)代碼。2）靜態(tài)數(shù)據(jù)區(qū)：用來存放編譯時就能確定存儲空間的數(shù)據(jù)。3）運(yùn)行棧區(qū)：用來存放運(yùn)行時才能確定存儲空間的數(shù)據(jù)。4）運(yùn)行堆區(qū)：用來存放運(yùn)行時用戶動態(tài)申請存儲空間的數(shù)據(jù)。8.1程序運(yùn)行時的存儲組織程序運(yùn)行時，系統(tǒng)將為程序分配一塊存儲空間。這塊空間用來存儲程5靜態(tài)存儲分配方式：對于源程序中出現(xiàn)的各種數(shù)據(jù)項(xiàng)，如常量、簡單變量、常界數(shù)組、非變體記錄等,在編譯時就給它們分配固定的存儲空間，而且在目標(biāo)程序運(yùn)行時，總是使用這些在編譯時就分配好的存儲單元作為它們的數(shù)據(jù)空間。8.2靜態(tài)存儲分配采用靜態(tài)存儲分配的語言必須滿足下列條件：1）不允許過程有遞歸調(diào)用。2）不允許有可變大小的數(shù)據(jù)項(xiàng)，如可變數(shù)組或可變字符串。3）不允許用戶動態(tài)建立數(shù)據(jù)實(shí)體。靜態(tài)存儲分配方式：對于源程序中出現(xiàn)的各種數(shù)據(jù)項(xiàng)，如常量、簡單6FORTRAN語言沒有長度可變的串，也沒有動態(tài)數(shù)組，其子程序和函數(shù)也不允許遞歸調(diào)用，所以FORTRAN語言采用靜態(tài)存儲分配方式。

8.2靜態(tài)存儲分配隱式參數(shù)

形式參數(shù)

簡單變量、數(shù)組及其它程序變量

例(P159)一個FORTRAN程序模塊靜態(tài)存儲分配的典型數(shù)據(jù)區(qū)格局如右圖所示，其中：1)隱式參數(shù)主要用于和主調(diào)模塊的通訊，它可以是主調(diào)過程的返回地址，或是函數(shù)返回值。2)形式參數(shù)存放相應(yīng)實(shí)在參數(shù)的地址或值。3)程序變量部分將作為簡單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的臨時變量的存儲空間。FORTRAN語言沒有長度可變的串，也沒有動態(tài)數(shù)組，其子程序78.2靜態(tài)存儲分配實(shí)現(xiàn)靜態(tài)存儲分配策略：編譯程序?qū)υ闯绦蜻M(jìn)行處理時，對每個變量在符號表中創(chuàng)建一個記錄，保存該變量的屬性，其中包括為變量分配的存儲空間地址即目標(biāo)地址。由于每個變量需要的空間大小已知,可將數(shù)據(jù)區(qū)開始位置的地址A分配給第一個變量,設(shè)第一個變量占n1個字節(jié)，則A+n1分配給第二個變量，設(shè)第二個變量占n2個字節(jié)，同理，

A+n1+n2分配給第三個變量等。8.2靜態(tài)存儲分配實(shí)現(xiàn)靜態(tài)存儲分配策略：編譯程序?qū)υ闯绦蜻M(jìn)8例chararray[16];inti,j;reala,b;假設(shè):數(shù)據(jù)區(qū)開始位置的地址264字符型占2個存貯單元整型占4個存貯單元實(shí)型占8個存貯單元8.2靜態(tài)存儲分配例8.2靜態(tài)存儲分配9目標(biāo)地址可采用的地址形式：絕對地址如果編寫的編譯程序是用于單任務(wù)環(huán)境，那么，通常采用絕對地址作為目標(biāo)地址。相對地址如果編譯程序是在多程序任務(wù)的環(huán)境中，那么目標(biāo)地址可采用相對于程序數(shù)據(jù)區(qū)的基地址的相對地址。若使用相對地址方式，那么程序的每一次執(zhí)行，程序及其數(shù)據(jù)區(qū)可以處在不同的存儲區(qū)內(nèi)。8.2靜態(tài)存儲分配目標(biāo)地址可采用的地址形式：8.2靜態(tài)存儲分配10動態(tài)存儲分配方式：有些語言允許有長度可變的串、動態(tài)數(shù)組，并允許過程遞歸調(diào)用，那么在編譯時就無法確定數(shù)據(jù)空間的具體大小，故其存儲分配必須留到目標(biāo)程序運(yùn)行時動態(tài)地進(jìn)行。8.3棧式動態(tài)存儲分配動態(tài)存儲分配方式的分類：棧式分配方式：主要采用一個棧作為動態(tài)存儲分配的存儲空間。當(dāng)調(diào)用一個程序時，過程中各數(shù)據(jù)項(xiàng)所需的存儲空間動態(tài)地分配于棧頂，當(dāng)過程結(jié)束時，就釋放這部分空間。C、PASCAL等語言即采用這種存儲分配方式。堆式分配方式：主要通過給運(yùn)行程序分配一個大的存儲空間(稱為堆)，每當(dāng)運(yùn)行需要時，就從這片空間中借用一塊，用過之后再退還給堆。動態(tài)存儲分配方式：有些語言允許有長度可變的串、動態(tài)數(shù)組，并允11棧式動態(tài)分配方式的實(shí)現(xiàn)：1)申請：在程序運(yùn)行中，當(dāng)程序模塊被調(diào)用時，就從總的數(shù)據(jù)區(qū)中請求一個空間作為其數(shù)據(jù)區(qū)(即加入運(yùn)行棧中)，并保留該空間直到執(zhí)行完整個模塊為止。2)釋放：當(dāng)模塊執(zhí)行完畢，退出模塊時，釋放它所占有的數(shù)據(jù)空間(即從運(yùn)行棧中彈出)。3)嵌套調(diào)用：從模塊被調(diào)用到它運(yùn)行結(jié)束之間，還可以通過過程調(diào)用或程序塊入口進(jìn)入其他的模塊，此時，也按上面所介紹的方法將這些模塊的數(shù)據(jù)區(qū)壓入或彈出運(yùn)行棧。當(dāng)嵌套的被調(diào)程序運(yùn)行結(jié)束返回到主調(diào)程序中的調(diào)用點(diǎn)時，運(yùn)行棧中的格局和內(nèi)容會恢復(fù)到調(diào)用之前的情況。8.3棧式動態(tài)存儲分配棧式動態(tài)分配方式的實(shí)現(xiàn)：8.3棧式動態(tài)存儲分配12例(P160)設(shè)有如下C程序，其運(yùn)行棧的變化情況如下圖所示。realx;…塊1intm1(intind)……………塊2{intx;x=m2(ind+1);}intm2(intj)………………塊3{{intf[10];……………塊4booltest1;}}main()………塊5{intx;x=2;printf("%d\n",m1(x/5));}塊4數(shù)據(jù)區(qū)

塊3數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊3數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

(a)程序剛開始

(b)運(yùn)行main(c)運(yùn)行m1

(d)運(yùn)行m2(e)運(yùn)行塊4對于C語言，函數(shù)是程序塊，一對花括號內(nèi)的程序即復(fù)合語句也可以看成是一個程序塊。

例(P160)設(shè)有如下C程序，其運(yùn)行棧的變化情況如下圖所示。13上例說明：當(dāng)這段程序剛開始運(yùn)行時，其存儲分配為圖(a)所示，接下來主函數(shù)main運(yùn)行，則為主函數(shù)main分配數(shù)據(jù)區(qū)，運(yùn)行棧為圖(b)，在main中調(diào)用了函數(shù)m1，當(dāng)函數(shù)m1運(yùn)行時，運(yùn)行棧為圖(c)，在函數(shù)m1中又調(diào)用了函數(shù)m2，當(dāng)函數(shù)m2運(yùn)行時的運(yùn)行棧如圖(d)所示，由于函數(shù)m2中嵌套著塊4，當(dāng)運(yùn)行塊4時，運(yùn)行棧為圖(e)所示。當(dāng)塊4運(yùn)行完后，塊4數(shù)據(jù)區(qū)出棧，運(yùn)行?；謴?fù)到圖(d)所示。當(dāng)函數(shù)m2運(yùn)行完后，運(yùn)行棧恢復(fù)到圖(c)所示。當(dāng)函數(shù)m1運(yùn)行完后，運(yùn)行?；謴?fù)到圖(b)所示。當(dāng)所有程序運(yùn)行后，運(yùn)行棧為空。8.3棧式動態(tài)存儲分配上例說明：當(dāng)這段程序剛開始運(yùn)行時，其存儲分配為圖(a)所14活動記錄：當(dāng)程序運(yùn)行進(jìn)入一個程序模塊時，就在運(yùn)行棧的棧頂創(chuàng)建一個專用數(shù)據(jù)區(qū)，該數(shù)據(jù)區(qū)通常稱為活動記錄。8.3棧式動態(tài)存儲分配當(dāng)程序模塊執(zhí)行結(jié)束時(即到達(dá)模塊的出口)，其相應(yīng)的活動記錄將從運(yùn)行棧的棧頂刪除。因此在該模塊中所定義的變量在該模塊的外部是不存在的。活動記錄：當(dāng)程序運(yùn)行進(jìn)入一個程序模塊時，就在運(yùn)行棧的棧頂創(chuàng)建15一個典型的活動記錄結(jié)構(gòu)如右圖所示。1、參數(shù)區(qū)1)

隱式參數(shù)：返回地址：主調(diào)程序中調(diào)用語句的下一條可執(zhí)行語句的地址。指向前一個活動記錄起始位置的指針：該基地址指針存放該模塊的主調(diào)模塊的活動記錄的基地址，用于確?？刂品祷刂髡{(diào)過程時，能使運(yùn)行環(huán)境恢復(fù)到調(diào)用前的格局。函數(shù)返回值：有的隱式參數(shù)區(qū)包含此項(xiàng)，有的不包括，還有更好的處理返回值的方法。2)顯式參數(shù)：顯式參數(shù)區(qū)是形式參數(shù)的通訊區(qū)。

形式參數(shù)的傳遞有傳值、傳地址、傳名等方法。局部數(shù)據(jù)區(qū)參數(shù)區(qū)display區(qū)8.3棧式動態(tài)存儲分配一個典型的活動記錄結(jié)構(gòu)如右圖所示。局部數(shù)據(jù)區(qū)參數(shù)區(qū)displ162、display區(qū)(嵌套層次顯示表)display區(qū)用于保存對當(dāng)前正在執(zhí)行的模塊來說是全局的程序變量區(qū)的信息，它由一系列地址指針?biāo)M成，每一個指針指向一個程序塊的活動記錄的開始位置，而這個程序塊對于當(dāng)前正在執(zhí)行的程序塊來說是全局的。

8.3棧式動態(tài)存儲分配2、display區(qū)(嵌套層次顯示表)8.3棧式動態(tài)存儲分17realx;…塊1intm1(intind)……………塊2{intx;x=m2(ind+1);}intm2(intj)………………塊3{{intf[10];……………塊4booltest1;}}main()………塊5{intx;x=2;printf("%d\n",m1(x/5));}jOS無前記錄

xd1abp0x,2d1return2abp1indx,0d1return3abp2d1d2abp3ftest1塊4活動記錄abp4

m2活動記錄abp3

m1活動記錄abp2

main活動記錄abp1abp0display區(qū)參數(shù)區(qū)局部數(shù)據(jù)區(qū)應(yīng)是main,m2,m1,xrealx;…塊1jOS無前記錄x18構(gòu)造一個display區(qū)的算法(P162)：如果j=i+1(即進(jìn)入一個程序塊)，則復(fù)制i層的display，然后增加一個指向i層模塊活動記錄基地址的指針。如果j≤i(即調(diào)用對當(dāng)前模塊來說是屬于全程聲明的過程模塊)，則來自i層模塊活動記錄中的display區(qū)前面j-1個入口將組成j層模塊的display區(qū)。jOS無前記錄

xd1abp0xd1return2abp1indxd1return3abp2d1d2abp3ftest1塊4活動記錄abp4

m2活動記錄abp3

m1活動記錄abp2

main活動記錄abp1abp0構(gòu)造一個display區(qū)的算法(P162)：jOS無前記錄198.3棧式動態(tài)存儲分配根據(jù)變量的二元地址(BL，ON)和display區(qū)的結(jié)構(gòu)可以計算出變量在運(yùn)行棧中的地址，從而找到變量的值。如果所引用的變量是一個外層模塊的局部變量，則它的層次號BL值必須小于當(dāng)前正在執(zhí)行的模塊的層次號。對這種情況而言，包含該變量單元的活動記錄能夠間接通過當(dāng)前活動記錄中display區(qū)中的相應(yīng)指針來獲取。

8.3棧式動態(tài)存儲分配根據(jù)變量的二元地址(BL，ON)和d20給定一個要訪問的具有地址為(BL，ON)的變量，設(shè)該變量在LEV層的一個模塊中。該變量的地址ADDR可按如下方法計算(P163)：

ifBL=LEVthenADDR=abp+(BL-1)+nip+ON//局部變量elseifBL<LEVthen//全局變量ADDR=display[BL]+(BL-1)+nip+ONelsewrite(“地址錯，不合法的模塊層次”)在上式中，abp是當(dāng)前活動記錄基址指針值，display[BL]指當(dāng)前活動記錄中display區(qū)中第BL個元素，nip是指隱式參數(shù)的數(shù)目。

注意：表達(dá)式(BL-1)+nip可解釋為display區(qū)的大小加隱式參數(shù)區(qū)的大小。8.3棧式動態(tài)存儲分配給定一個要訪問的具有地址為(BL，ON)的變量，設(shè)該變量在L218.3棧式動態(tài)存儲分配對于具有遞歸塊程序結(jié)構(gòu)的語言來說，一個程序模塊可以和多個活動記錄相關(guān)。當(dāng)程序運(yùn)行時，隨著遞歸函數(shù)的每一次調(diào)用，在運(yùn)行棧棧頂將設(shè)置一個新的活動記錄，返回地址也與每個活動記錄相聯(lián)系。8.3棧式動態(tài)存儲分配對于具有遞歸塊程序結(jié)構(gòu)的語言來說，一22地址內(nèi)容說明

abp4n,2第3次調(diào)fact函數(shù)n=2，返回2給全局變量區(qū)的fact單元abp3ret2abp0

abp3n,3第2次調(diào)fact函數(shù)n=3，返回6給全局變量區(qū)的fact單元abp2ret2abp0

abp2n,4第1次調(diào)fact函數(shù)n=4。返回24給全局變量區(qū)的fact單元abp1ret1abp0

abp1m,4主函數(shù)運(yùn)行，m=4，調(diào)fact函數(shù)。ret0是運(yùn)行完main后返回的地址,可以是OS或留空abp0ret0abp0

abp0mainfact用于保存fact函數(shù)的返回值，開始時無值，最后fact函數(shù)返回后為24。fact,2,6,24無前記錄OS例(P163)C程序在程序執(zhí)行期間其運(yùn)行棧的變化情況如右圖所示。intfact(intn){if(n<3)return(n)elsereturn(n*fact(n-1));}main(){intm;

m=4;printf("%d!=%d\n",m,fact(m));}備注：返回地址ret1指示從fact函數(shù)的特定動作返回到main函數(shù)內(nèi)部的調(diào)用點(diǎn)之后。返回地址ret2指示從fact函數(shù)的特定動作返回到fact函數(shù)內(nèi)部的調(diào)用點(diǎn)之后。

ret2ret1地址內(nèi)容說明

n,2第3次調(diào)fact函數(shù)n=2，返回2給全238.3棧式動態(tài)存儲分配棧式存儲分配適合那些過程允許嵌套定義、遞歸調(diào)用的語言，其過程的進(jìn)入和退出具有“后進(jìn)先出”的特點(diǎn)。如果語言允許動態(tài)申請和釋放存儲空間，那么，棧式存儲分配就不適合了，這時，可以采用堆式動態(tài)存儲分配策略。8.3棧式動態(tài)存儲分配棧式存儲分配適合那些過程允許嵌套定義24堆式分配策略的基本思路：假設(shè)程序運(yùn)行時有一個大的連續(xù)的存儲空間（堆），當(dāng)存儲管理程序接收到運(yùn)行程序的存儲空間請求時，就從堆中分配一塊空間給運(yùn)行程序。當(dāng)運(yùn)行程序用完后再退還給堆（即釋放）。管理程序回收其存儲空間以備后面使用。由于每塊空間可以按任意順序釋放，這樣，程序經(jīng)過一段運(yùn)行后，堆將被劃分成若干已用塊和空閑塊。8.4堆式動態(tài)存儲分配u1u3u4u7u8程序運(yùn)行一段時間后

程序運(yùn)行初期

堆式分配策略的基本思路：假設(shè)程序運(yùn)行時有一個大的連續(xù)的存儲空258.4堆式動態(tài)存儲分配堆式存儲分配需要解決的問題：一是堆空間的分配當(dāng)運(yùn)行程序需要一塊空間時，應(yīng)該分配哪一塊給它。二是分配空間的釋放由于返回給堆的不用空間是按任意次序進(jìn)行的，所以需要專門研究釋放的策略。8.4堆式動態(tài)存儲分配堆式存儲分配需要解決的問題：26新用戶請求分配內(nèi)存時，系統(tǒng)分配空間策略：系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行(即剩余的空閑塊不能滿足分配的請求)時，系統(tǒng)才去回收所有用戶不再使用的空閑塊。用戶使用一旦結(jié)束，便將所占內(nèi)存區(qū)釋放成空閑塊。同時，每當(dāng)新的用戶請求分配內(nèi)存時，系統(tǒng)需要巡視整個內(nèi)存中所有空閑塊，并從中找出一個“合適”的空閑塊加以分配。由此，系統(tǒng)需建立一張記錄所有空閑塊的“可利用空間表”，表的結(jié)構(gòu)可以采用目錄表或鏈表。8.4堆式動態(tài)存儲分配新用戶請求分配內(nèi)存時，系統(tǒng)分配空間策略：8.4堆式動態(tài)存儲27…………0100002000030000(a)內(nèi)存狀態(tài)起始地址內(nèi)存大小使用情況100005000空閑200003000空閑300008000空閑(b)可利用空間目錄表0500020000030003000008000#10000HEAD100002000030000(c)可利用空間鏈表堆式存儲管理的可利用空間表…………01000028TAGSIZELINKSPACE8.4堆式動態(tài)存儲分配“可利用空間鏈表”中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下∶TAG：標(biāo)記，0表示空閑，1表示占用。SIZE：記錄結(jié)點(diǎn)大小，指示空閑塊的存儲量。LINK:指向下一個結(jié)點(diǎn)。SPACE：地址連續(xù)的內(nèi)存空間。

TAGSIZELINKSPACE8.4堆式動態(tài)存儲分配“可29堆式存儲管理方法：1、定長塊的管理將總的可被利用的堆存儲區(qū)劃分成大小適當(dāng)?shù)囊幌盗袎K。這些塊通過每塊中的LINK域連接起來形成單向線性鏈表（即可利用空間鏈表）。然后由一個分配程序來處理。8.4堆式動態(tài)存儲分配堆式存儲管理方法：8.4堆式動態(tài)存儲分配30對一個存儲塊的請求，其定長塊分配程序算法如下：FunctionGET_BLOCK(HEAD)//HEAD為指向可用存儲塊鏈表上第一個塊的指針，GET_BLOCK返回一個可用塊的地址p。(1)溢出嗎?ifHEAD=NULLthen轉(zhuǎn)錯誤處理程序；(2)分配存儲塊p=HEADHEAD=p↑.LINKreturn(p)由于各塊大小相同，故在分配函數(shù)中不用查找，只需將頭指針?biāo)傅牡谝粔K分配給申請空間的程序，然后頭指針指向下一個空閑塊。同樣，當(dāng)用戶釋放內(nèi)存時，系統(tǒng)只要將用戶釋放的空間塊插入到表頭即可。0800200000800300000800#10000HEAD100002000030000對一個存儲塊的請求，其定長塊分配程序算法如下：31堆式存儲管理方法：2、變長塊的管理（常用）系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請求而變。8.4堆式動態(tài)存儲分配堆式存儲管理方法：8.4堆式動態(tài)存儲分配32變長塊的分配策略：假設(shè)用戶請求一個大小為n的存儲塊，而“可利用空間鏈表”中僅有一塊大小為m(m≥n)的空閑塊，則分配時只需將大小為n的部分分配給申請的用戶，同時將剩余的m-n部分作為一個結(jié)點(diǎn)留在鏈表中即可。若可利用空間表中有若干個大于n的空閑塊時，可采用首次滿足法、最優(yōu)滿足法或最差滿足法來分配塊。8.4堆式動態(tài)存儲分配變長塊的分配策略：8.4堆式動態(tài)存儲分配33首次滿足法：從表頭指針開始查找可利用空間表，將找到的第一個大小不小于n的空閑塊的一部分分配給用戶?？衫每臻g表本身既不按結(jié)點(diǎn)的初始地址排序，也不按結(jié)點(diǎn)的大小排序。在回收時，只要將釋放的空閑塊插入在鏈表的表頭即可。

8.4堆式動態(tài)存儲分配最優(yōu)滿足法：系統(tǒng)在分配前首先要對可利用空間表從頭至尾掃描一遍，然后從中找出一塊不小于n且最接近n空閑塊進(jìn)行分配給用戶。為了提高效率，通常預(yù)先將“可利用空間表”按空間的大小從小到大進(jìn)行排序。在回收時，必須將釋放的空閑塊插入到合適的位置上去。首次滿足法：從表頭指針開始查找可利用空間表，將找到的第一個大34最差滿足法：將可利用空間表中不小于n且是鏈表中最大的空閑塊的一部分分配給用戶。為了減少查找時間，應(yīng)該對“可利用空間表”按空閑塊的大小從大到小排序。每次分配時無需查找，只需從鏈表中刪除第一個結(jié)點(diǎn)，并將其中一部分分配給用戶，而將剩余部分作為一個新的結(jié)點(diǎn)插入到可利用空間表的適當(dāng)位置上?；厥諘r也將釋放的空閑塊插入到鏈表的適當(dāng)位置上。

8.4堆式動態(tài)存儲分配最差滿足法：將可利用空間表中不小于n且是鏈表中最大的空閑塊的35在選擇變長塊的分配策略時需考慮的因素：用戶的邏輯要求，請求的內(nèi)存空間的大小分布；分配和釋放的頻率以及效率對系統(tǒng)的重要性等因素。8.4堆式動態(tài)存儲分配最優(yōu)滿足法比較適合于請求分配的內(nèi)存大小范圍較廣的系統(tǒng)，但最費(fèi)時間；最差滿足法比較適合于請求分配的內(nèi)存大小范圍較窄的系統(tǒng)；首次滿足法介于前兩者之間。在選擇變長塊的分配策略時需考慮的因素：用戶的邏輯要求，請求的36堆式存儲管理方法：3、釋放方法最簡單的釋放方法是作為一個新的空閑塊插入到無序的可利用空間表中。但會導(dǎo)致可用空間表中會含有大量的小塊。處理辦法是將兩個連續(xù)的塊合并成一個塊，需要對可利用空間鏈表按塊的地址順序進(jìn)行組織，同時為了要確定當(dāng)前釋放塊的插入位置，還需要對可利用空間鏈表進(jìn)行搜索。有的程序設(shè)計語言干脆不做釋放的工作，直到內(nèi)存空間用完為止。這樣做的缺點(diǎn)是浪費(fèi)空間，但如果系統(tǒng)的內(nèi)存很大，這種方法也是可行的。8.4堆式動態(tài)存儲分配堆式存儲管理方法：8.4堆式動態(tài)存儲分配37小結(jié)

影響存儲分配策略的語言特征：遞歸、可變數(shù)據(jù)項(xiàng)/數(shù)據(jù)實(shí)體等靜態(tài)存儲分配：編譯時安排所有數(shù)據(jù)對象的存儲動態(tài)存儲分配：棧分配策略：按棧的方式管理運(yùn)行時的數(shù)據(jù)存儲空間；堆分配策略：在運(yùn)行時根據(jù)要求從堆數(shù)據(jù)區(qū)動態(tài)地分配和釋放數(shù)據(jù)存儲空間。活動記錄：局部數(shù)據(jù)區(qū)、參數(shù)區(qū)和display區(qū)堆式存儲分配變長塊的方法：首次滿足法、最優(yōu)滿足法、最差滿足法。小結(jié)影響存儲分配策略的語言特征：遞歸、可變數(shù)據(jù)項(xiàng)/數(shù)據(jù)實(shí)38習(xí)題(P168)1.什么是靜態(tài)存儲分配？什么是動態(tài)存儲分配？它們有什么不同？2.活動記錄哪幾部分組成？display的作用是什么？3.靜態(tài)存儲分配對語言有何要求？4.只有采用動態(tài)存儲分配的程序設(shè)計語言允許有過程遞歸調(diào)用，為什么？習(xí)題(P168)1.什么是靜態(tài)存儲分配？什么是動態(tài)存儲分39習(xí)題5.畫出下段程序運(yùn)行到a點(diǎn)和b點(diǎn)時的運(yùn)行棧內(nèi)容。

intf(intb){intc;c=10;{intd;d=10;b=c+d;………………breturn(b);}}main(){inta;…a

a=f(5);printf(“%d\n”,a);}習(xí)題5.畫出下段程序運(yùn)行到a點(diǎn)和b點(diǎn)時的運(yùn)行棧內(nèi)容。 40a點(diǎn)的棧內(nèi)容：

abp1aabp0abp0

abp0mainf無前記錄OSb點(diǎn)的棧內(nèi)容：地址內(nèi)容

abp3d,10abp2

abp2abp0

abp2c,10b,20abp1return2abp0

abp1aabp0abp0

abp0mainf無前記錄OS解：a點(diǎn)的棧內(nèi)容：aabp0abp0

mainf無前記錄OSb點(diǎn)41編譯原理第8章程序運(yùn)行時的存儲組織42第8章程序運(yùn)行時的存儲組織及管理(P158)8.1程序運(yùn)行時的存儲組織8.2靜態(tài)存儲分配8.3棧式動態(tài)存儲分配8.4堆式動態(tài)存儲分配第8章程序運(yùn)行時的存儲組織及管理(P158)43學(xué)習(xí)重點(diǎn)影響存儲分配策略的語言特征靜態(tài)存儲分配動態(tài)存儲分配活動記錄堆式存儲分配變長塊的方法學(xué)習(xí)重點(diǎn)44影響存儲分配策略的語言特征:

過程能否遞歸過程能否嵌套過程調(diào)用時參數(shù)如何傳遞哪些實(shí)體可以作為參數(shù)和返回值是否允許動態(tài)的為對象分配和撤銷存儲空間存儲空間是否必須顯式地釋放……第8章程序運(yùn)行時的存儲組織及管理影響存儲分配策略的語言特征:第8章程序運(yùn)行時的存儲組45程序運(yùn)行時，系統(tǒng)將為程序分配一塊存儲空間。這塊空間用來存儲程序的目標(biāo)代碼以及目標(biāo)代碼運(yùn)行時需要或產(chǎn)生的各種數(shù)據(jù)。從用途上看，這塊空間可分為以下幾個部分：1）目標(biāo)程序區(qū)：用來存放目標(biāo)代碼。2）靜態(tài)數(shù)據(jù)區(qū)：用來存放編譯時就能確定存儲空間的數(shù)據(jù)。3）運(yùn)行棧區(qū)：用來存放運(yùn)行時才能確定存儲空間的數(shù)據(jù)。4）運(yùn)行堆區(qū)：用來存放運(yùn)行時用戶動態(tài)申請存儲空間的數(shù)據(jù)。8.1程序運(yùn)行時的存儲組織程序運(yùn)行時，系統(tǒng)將為程序分配一塊存儲空間。這塊空間用來存儲程46靜態(tài)存儲分配方式：對于源程序中出現(xiàn)的各種數(shù)據(jù)項(xiàng)，如常量、簡單變量、常界數(shù)組、非變體記錄等,在編譯時就給它們分配固定的存儲空間，而且在目標(biāo)程序運(yùn)行時，總是使用這些在編譯時就分配好的存儲單元作為它們的數(shù)據(jù)空間。8.2靜態(tài)存儲分配采用靜態(tài)存儲分配的語言必須滿足下列條件：1）不允許過程有遞歸調(diào)用。2）不允許有可變大小的數(shù)據(jù)項(xiàng)，如可變數(shù)組或可變字符串。3）不允許用戶動態(tài)建立數(shù)據(jù)實(shí)體。靜態(tài)存儲分配方式：對于源程序中出現(xiàn)的各種數(shù)據(jù)項(xiàng)，如常量、簡單47FORTRAN語言沒有長度可變的串，也沒有動態(tài)數(shù)組，其子程序和函數(shù)也不允許遞歸調(diào)用，所以FORTRAN語言采用靜態(tài)存儲分配方式。

8.2靜態(tài)存儲分配隱式參數(shù)

形式參數(shù)

簡單變量、數(shù)組及其它程序變量

例(P159)一個FORTRAN程序模塊靜態(tài)存儲分配的典型數(shù)據(jù)區(qū)格局如右圖所示，其中：1)隱式參數(shù)主要用于和主調(diào)模塊的通訊，它可以是主調(diào)過程的返回地址，或是函數(shù)返回值。2)形式參數(shù)存放相應(yīng)實(shí)在參數(shù)的地址或值。3)程序變量部分將作為簡單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的臨時變量的存儲空間。FORTRAN語言沒有長度可變的串，也沒有動態(tài)數(shù)組，其子程序488.2靜態(tài)存儲分配實(shí)現(xiàn)靜態(tài)存儲分配策略：編譯程序?qū)υ闯绦蜻M(jìn)行處理時，對每個變量在符號表中創(chuàng)建一個記錄，保存該變量的屬性，其中包括為變量分配的存儲空間地址即目標(biāo)地址。由于每個變量需要的空間大小已知,可將數(shù)據(jù)區(qū)開始位置的地址A分配給第一個變量,設(shè)第一個變量占n1個字節(jié)，則A+n1分配給第二個變量，設(shè)第二個變量占n2個字節(jié)，同理，

A+n1+n2分配給第三個變量等。8.2靜態(tài)存儲分配實(shí)現(xiàn)靜態(tài)存儲分配策略：編譯程序?qū)υ闯绦蜻M(jìn)49例chararray[16];inti,j;reala,b;假設(shè):數(shù)據(jù)區(qū)開始位置的地址264字符型占2個存貯單元整型占4個存貯單元實(shí)型占8個存貯單元8.2靜態(tài)存儲分配例8.2靜態(tài)存儲分配50目標(biāo)地址可采用的地址形式：絕對地址如果編寫的編譯程序是用于單任務(wù)環(huán)境，那么，通常采用絕對地址作為目標(biāo)地址。相對地址如果編譯程序是在多程序任務(wù)的環(huán)境中，那么目標(biāo)地址可采用相對于程序數(shù)據(jù)區(qū)的基地址的相對地址。若使用相對地址方式，那么程序的每一次執(zhí)行，程序及其數(shù)據(jù)區(qū)可以處在不同的存儲區(qū)內(nèi)。8.2靜態(tài)存儲分配目標(biāo)地址可采用的地址形式：8.2靜態(tài)存儲分配51動態(tài)存儲分配方式：有些語言允許有長度可變的串、動態(tài)數(shù)組，并允許過程遞歸調(diào)用，那么在編譯時就無法確定數(shù)據(jù)空間的具體大小，故其存儲分配必須留到目標(biāo)程序運(yùn)行時動態(tài)地進(jìn)行。8.3棧式動態(tài)存儲分配動態(tài)存儲分配方式的分類：棧式分配方式：主要采用一個棧作為動態(tài)存儲分配的存儲空間。當(dāng)調(diào)用一個程序時，過程中各數(shù)據(jù)項(xiàng)所需的存儲空間動態(tài)地分配于棧頂，當(dāng)過程結(jié)束時，就釋放這部分空間。C、PASCAL等語言即采用這種存儲分配方式。堆式分配方式：主要通過給運(yùn)行程序分配一個大的存儲空間(稱為堆)，每當(dāng)運(yùn)行需要時，就從這片空間中借用一塊，用過之后再退還給堆。動態(tài)存儲分配方式：有些語言允許有長度可變的串、動態(tài)數(shù)組，并允52棧式動態(tài)分配方式的實(shí)現(xiàn)：1)申請：在程序運(yùn)行中，當(dāng)程序模塊被調(diào)用時，就從總的數(shù)據(jù)區(qū)中請求一個空間作為其數(shù)據(jù)區(qū)(即加入運(yùn)行棧中)，并保留該空間直到執(zhí)行完整個模塊為止。2)釋放：當(dāng)模塊執(zhí)行完畢，退出模塊時，釋放它所占有的數(shù)據(jù)空間(即從運(yùn)行棧中彈出)。3)嵌套調(diào)用：從模塊被調(diào)用到它運(yùn)行結(jié)束之間，還可以通過過程調(diào)用或程序塊入口進(jìn)入其他的模塊，此時，也按上面所介紹的方法將這些模塊的數(shù)據(jù)區(qū)壓入或彈出運(yùn)行棧。當(dāng)嵌套的被調(diào)程序運(yùn)行結(jié)束返回到主調(diào)程序中的調(diào)用點(diǎn)時，運(yùn)行棧中的格局和內(nèi)容會恢復(fù)到調(diào)用之前的情況。8.3棧式動態(tài)存儲分配棧式動態(tài)分配方式的實(shí)現(xiàn)：8.3棧式動態(tài)存儲分配53例(P160)設(shè)有如下C程序，其運(yùn)行棧的變化情況如下圖所示。realx;…塊1intm1(intind)……………塊2{intx;x=m2(ind+1);}intm2(intj)………………塊3{{intf[10];……………塊4booltest1;}}main()………塊5{intx;x=2;printf("%d\n",m1(x/5));}塊4數(shù)據(jù)區(qū)

塊3數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊3數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊2數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊5數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

塊1數(shù)據(jù)區(qū)

(a)程序剛開始

(b)運(yùn)行main(c)運(yùn)行m1

(d)運(yùn)行m2(e)運(yùn)行塊4對于C語言，函數(shù)是程序塊，一對花括號內(nèi)的程序即復(fù)合語句也可以看成是一個程序塊。

例(P160)設(shè)有如下C程序，其運(yùn)行棧的變化情況如下圖所示。54上例說明：當(dāng)這段程序剛開始運(yùn)行時，其存儲分配為圖(a)所示，接下來主函數(shù)main運(yùn)行，則為主函數(shù)main分配數(shù)據(jù)區(qū)，運(yùn)行棧為圖(b)，在main中調(diào)用了函數(shù)m1，當(dāng)函數(shù)m1運(yùn)行時，運(yùn)行棧為圖(c)，在函數(shù)m1中又調(diào)用了函數(shù)m2，當(dāng)函數(shù)m2運(yùn)行時的運(yùn)行棧如圖(d)所示，由于函數(shù)m2中嵌套著塊4，當(dāng)運(yùn)行塊4時，運(yùn)行棧為圖(e)所示。當(dāng)塊4運(yùn)行完后，塊4數(shù)據(jù)區(qū)出棧，運(yùn)行棧恢復(fù)到圖(d)所示。當(dāng)函數(shù)m2運(yùn)行完后，運(yùn)行棧恢復(fù)到圖(c)所示。當(dāng)函數(shù)m1運(yùn)行完后，運(yùn)行棧恢復(fù)到圖(b)所示。當(dāng)所有程序運(yùn)行后，運(yùn)行棧為空。8.3棧式動態(tài)存儲分配上例說明：當(dāng)這段程序剛開始運(yùn)行時，其存儲分配為圖(a)所55活動記錄：當(dāng)程序運(yùn)行進(jìn)入一個程序模塊時，就在運(yùn)行棧的棧頂創(chuàng)建一個專用數(shù)據(jù)區(qū)，該數(shù)據(jù)區(qū)通常稱為活動記錄。8.3棧式動態(tài)存儲分配當(dāng)程序模塊執(zhí)行結(jié)束時(即到達(dá)模塊的出口)，其相應(yīng)的活動記錄將從運(yùn)行棧的棧頂刪除。因此在該模塊中所定義的變量在該模塊的外部是不存在的?；顒佑涗洠寒?dāng)程序運(yùn)行進(jìn)入一個程序模塊時，就在運(yùn)行棧的棧頂創(chuàng)建56一個典型的活動記錄結(jié)構(gòu)如右圖所示。1、參數(shù)區(qū)1)

隱式參數(shù)：返回地址：主調(diào)程序中調(diào)用語句的下一條可執(zhí)行語句的地址。指向前一個活動記錄起始位置的指針：該基地址指針存放該模塊的主調(diào)模塊的活動記錄的基地址，用于確保控制返回主調(diào)過程時，能使運(yùn)行環(huán)境恢復(fù)到調(diào)用前的格局。函數(shù)返回值：有的隱式參數(shù)區(qū)包含此項(xiàng)，有的不包括，還有更好的處理返回值的方法。2)顯式參數(shù)：顯式參數(shù)區(qū)是形式參數(shù)的通訊區(qū)。

形式參數(shù)的傳遞有傳值、傳地址、傳名等方法。局部數(shù)據(jù)區(qū)參數(shù)區(qū)display區(qū)8.3棧式動態(tài)存儲分配一個典型的活動記錄結(jié)構(gòu)如右圖所示。局部數(shù)據(jù)區(qū)參數(shù)區(qū)displ572、display區(qū)(嵌套層次顯示表)display區(qū)用于保存對當(dāng)前正在執(zhí)行的模塊來說是全局的程序變量區(qū)的信息，它由一系列地址指針?biāo)M成，每一個指針指向一個程序塊的活動記錄的開始位置，而這個程序塊對于當(dāng)前正在執(zhí)行的程序塊來說是全局的。

8.3棧式動態(tài)存儲分配2、display區(qū)(嵌套層次顯示表)8.3棧式動態(tài)存儲分58realx;…塊1intm1(intind)……………塊2{intx;x=m2(ind+1);}intm2(intj)………………塊3{{intf[10];……………塊4booltest1;}}main()………塊5{intx;x=2;printf("%d\n",m1(x/5));}jOS無前記錄

xd1abp0x,2d1return2abp1indx,0d1return3abp2d1d2abp3ftest1塊4活動記錄abp4

m2活動記錄abp3

m1活動記錄abp2

main活動記錄abp1abp0display區(qū)參數(shù)區(qū)局部數(shù)據(jù)區(qū)應(yīng)是main,m2,m1,xrealx;…塊1jOS無前記錄x59構(gòu)造一個display區(qū)的算法(P162)：如果j=i+1(即進(jìn)入一個程序塊)，則復(fù)制i層的display，然后增加一個指向i層模塊活動記錄基地址的指針。如果j≤i(即調(diào)用對當(dāng)前模塊來說是屬于全程聲明的過程模塊)，則來自i層模塊活動記錄中的display區(qū)前面j-1個入口將組成j層模塊的display區(qū)。jOS無前記錄

xd1abp0xd1return2abp1indxd1return3abp2d1d2abp3ftest1塊4活動記錄abp4

m2活動記錄abp3

m1活動記錄abp2

main活動記錄abp1abp0構(gòu)造一個display區(qū)的算法(P162)：jOS無前記錄608.3棧式動態(tài)存儲分配根據(jù)變量的二元地址(BL，ON)和display區(qū)的結(jié)構(gòu)可以計算出變量在運(yùn)行棧中的地址，從而找到變量的值。如果所引用的變量是一個外層模塊的局部變量，則它的層次號BL值必須小于當(dāng)前正在執(zhí)行的模塊的層次號。對這種情況而言，包含該變量單元的活動記錄能夠間接通過當(dāng)前活動記錄中display區(qū)中的相應(yīng)指針來獲取。

8.3棧式動態(tài)存儲分配根據(jù)變量的二元地址(BL，ON)和d61給定一個要訪問的具有地址為(BL，ON)的變量，設(shè)該變量在LEV層的一個模塊中。該變量的地址ADDR可按如下方法計算(P163)：

ifBL=LEVthenADDR=abp+(BL-1)+nip+ON//局部變量elseifBL<LEVthen//全局變量ADDR=display[BL]+(BL-1)+nip+ONelsewrite(“地址錯，不合法的模塊層次”)在上式中，abp是當(dāng)前活動記錄基址指針值，display[BL]指當(dāng)前活動記錄中display區(qū)中第BL個元素，nip是指隱式參數(shù)的數(shù)目。

注意：表達(dá)式(BL-1)+nip可解釋為display區(qū)的大小加隱式參數(shù)區(qū)的大小。8.3棧式動態(tài)存儲分配給定一個要訪問的具有地址為(BL，ON)的變量，設(shè)該變量在L628.3棧式動態(tài)存儲分配對于具有遞歸塊程序結(jié)構(gòu)的語言來說，一個程序模塊可以和多個活動記錄相關(guān)。當(dāng)程序運(yùn)行時，隨著遞歸函數(shù)的每一次調(diào)用，在運(yùn)行棧棧頂將設(shè)置一個新的活動記錄，返回地址也與每個活動記錄相聯(lián)系。8.3棧式動態(tài)存儲分配對于具有遞歸塊程序結(jié)構(gòu)的語言來說，一63地址內(nèi)容說明

abp4n,2第3次調(diào)fact函數(shù)n=2，返回2給全局變量區(qū)的fact單元abp3ret2abp0

abp3n,3第2次調(diào)fact函數(shù)n=3，返回6給全局變量區(qū)的fact單元abp2ret2abp0

abp2n,4第1次調(diào)fact函數(shù)n=4。返回24給全局變量區(qū)的fact單元abp1ret1abp0

abp1m,4主函數(shù)運(yùn)行，m=4，調(diào)fact函數(shù)。ret0是運(yùn)行完main后返回的地址,可以是OS或留空abp0ret0abp0

abp0mainfact用于保存fact函數(shù)的返回值，開始時無值，最后fact函數(shù)返回后為24。fact,2,6,24無前記錄OS例(P163)C程序在程序執(zhí)行期間其運(yùn)行棧的變化情況如右圖所示。intfact(intn){if(n<3)return(n)elsereturn(n*fact(n-1));}main(){intm;

m=4;printf("%d!=%d\n",m,fact(m));}備注：返回地址ret1指示從fact函數(shù)的特定動作返回到main函數(shù)內(nèi)部的調(diào)用點(diǎn)之后。返回地址ret2指示從fact函數(shù)的特定動作返回到fact函數(shù)內(nèi)部的調(diào)用點(diǎn)之后。

ret2ret1地址內(nèi)容說明

n,2第3次調(diào)fact函數(shù)n=2，返回2給全648.3棧式動態(tài)存儲分配棧式存儲分配適合那些過程允許嵌套定義、遞歸調(diào)用的語言，其過程的進(jìn)入和退出具有“后進(jìn)先出”的特點(diǎn)。如果語言允許動態(tài)申請和釋放存儲空間，那么，棧式存儲分配就不適合了，這時，可以采用堆式動態(tài)存儲分配策略。8.3棧式動態(tài)存儲分配棧式存儲分配適合那些過程允許嵌套定義65堆式分配策略的基本思路：假設(shè)程序運(yùn)行時有一個大的連續(xù)的存儲空間（堆），當(dāng)存儲管理程序接收到運(yùn)行程序的存儲空間請求時，就從堆中分配一塊空間給運(yùn)行程序。當(dāng)運(yùn)行程序用完后再退還給堆（即釋放）。管理程序回收其存儲空間以備后面使用。由于每塊空間可以按任意順序釋放，這樣，程序經(jīng)過一段運(yùn)行后，堆將被劃分成若干已用塊和空閑塊。8.4堆式動態(tài)存儲分配u1u3u4u7u8程序運(yùn)行一段時間后

程序運(yùn)行初期

堆式分配策略的基本思路：假設(shè)程序運(yùn)行時有一個大的連續(xù)的存儲空668.4堆式動態(tài)存儲分配堆式存儲分配需要解決的問題：一是堆空間的分配當(dāng)運(yùn)行程序需要一塊空間時，應(yīng)該分配哪一塊給它。二是分配空間的釋放由于返回給堆的不用空間是按任意次序進(jìn)行的，所以需要專門研究釋放的策略。8.4堆式動態(tài)存儲分配堆式存儲分配需要解決的問題：67新用戶請求分配內(nèi)存時，系統(tǒng)分配空間策略：系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行(即剩余的空閑塊不能滿足分配的請求)時，系統(tǒng)才去回收所有用戶不再使用的空閑塊。用戶使用一旦結(jié)束，便將所占內(nèi)存區(qū)釋放成空閑塊。同時，每當(dāng)新的用戶請求分配內(nèi)存時，系統(tǒng)需要巡視整個內(nèi)存中所有空閑塊，并從中找出一個“合適”的空閑塊加以分配。由此，系統(tǒng)需建立一張記錄所有空閑塊的“可利用空間表”，表的結(jié)構(gòu)可以采用目錄表或鏈表。8.4堆式動態(tài)存儲分配新用戶請求分配內(nèi)存時，系統(tǒng)分配空間策略：8.4堆式動態(tài)存儲68…………0100002000030000(a)內(nèi)存狀態(tài)起始地址內(nèi)存大小使用情況100005000空閑200003000空閑300008000空閑(b)可利用空間目錄表0500020000030003000008000#10000HEAD100002000030000(c)可利用空間鏈表堆式存儲管理的可利用空間表…………01000069TAGSIZELINKSPACE8.4堆式動態(tài)存儲分配“可利用空間鏈表”中結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下∶TAG：標(biāo)記，0表示空閑，1表示占用。SIZE：記錄結(jié)點(diǎn)大小，指示空閑塊的存儲量。LINK:指向下一個結(jié)點(diǎn)。SPACE：地址連續(xù)的內(nèi)存空間。

TAGSIZELINKSPACE8.4堆式動態(tài)存儲分配“可70堆式存儲管理方法：1、定長塊的管理將總的可被利用的堆存儲區(qū)劃分成大小適當(dāng)?shù)囊幌盗袎K。這些塊通過每塊中的LINK域連接起來形成單向線性鏈表（即可利用空間鏈表）。然后由一個分配程序來處理。8.4堆式動態(tài)存儲分配堆式存儲管理方法：8.4堆式動態(tài)存儲分配71對一個存儲塊的請求，其定長塊分配程序算法如下：FunctionGET_BLOCK(HEAD)//HEAD為指向可用存儲塊鏈表上第一個塊的指針，GET_BLOCK返回一個可用塊的地址p。(1)溢出嗎?ifHEAD=NULLthen轉(zhuǎn)錯誤處理程序；(2)分配存儲塊p=HEADHEAD=p↑.LINKreturn(p)由于各塊大小相同，故在分配函數(shù)中不用查找，只需將頭指針?biāo)傅牡谝粔K分配給申請空間的程序，然后頭指針指向下一個空閑塊。同樣，當(dāng)用戶釋放內(nèi)存時，系統(tǒng)只要將用戶釋放的空間塊插入到表頭即可。0800200000800300000800#10000HEAD100002000030000對一個存儲塊的請求，其定長塊分配程序算法如下：72堆式存儲管理方法：2、變長塊的管理（常用）系統(tǒng)在運(yùn)行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請求而變。8.4堆式動態(tài)存儲分配堆式存儲管理方法：8.4堆式動態(tài)存儲分配73變長塊的分配策略：假設(shè)用戶請求一個大小為n的存儲塊，而“可利用空間鏈表”中僅有一塊大小為m(m≥n)的空閑塊，則分配時只需將大小為n的部分分配給申請的用戶，同時將剩余的m-n部分作為一個結(jié)點(diǎn)留在鏈表中即可。若可利用空間表中