編譯原理-第10章(清華大學(xué))

第10章目標(biāo)程序運(yùn)行時(shí)的組織

10.1概述2數(shù)據(jù)表示10.3目標(biāo)程序運(yùn)行時(shí)的棧式存儲(chǔ)組織10.4參數(shù)傳遞10.5堆式存儲(chǔ)組織的討論1概述-代碼生成解決語義gap

高級(jí)語言支持的概念TypevalueexpressionVariableprocedureFunctionparameters目標(biāo)機(jī)支持的概念bitsbyteswordsRegistersStackaddressRoutine(subroutine)2概述代碼生成前如何安排目標(biāo)機(jī)資源運(yùn)行時(shí)組織的幾個(gè)問題數(shù)據(jù)表示-如何在目標(biāo)機(jī)中表示每個(gè)源語言類型的值表達(dá)式求值-如何組織表達(dá)式的計(jì)算存儲(chǔ)分配-如何組織不同作用域變量的存儲(chǔ)過程實(shí)現(xiàn)-如何以例程實(shí)現(xiàn)過程，函數(shù)，參數(shù)傳遞

3概述

任務(wù)：編譯程序?qū)δ繕?biāo)程序運(yùn)行時(shí)的組織（設(shè)計(jì)運(yùn)行環(huán)境和分配存儲(chǔ)）如通常存儲(chǔ)區(qū)布局可為：

目標(biāo)代碼區(qū)

靜態(tài)數(shù)據(jù)區(qū)

Stackheap 4運(yùn)行環(huán)境和存儲(chǔ)分配

設(shè)計(jì)分析邏輯階段：在目標(biāo)代碼生成前，作準(zhǔn)備實(shí)質(zhì)：

關(guān)聯(lián)（Binding）將源程序的文本

程序運(yùn)行動(dòng)作的實(shí)現(xiàn)源文件中的名字N

運(yùn)行時(shí)的存儲(chǔ)S在語義學(xué)中，使用術(shù)語environment函數(shù)表示env:N→S(N到S的映射)5決定運(yùn)行管理復(fù)雜程度的因素——源語言本身1.允許的數(shù)據(jù)類型的多少2．語言中允許的數(shù)據(jù)項(xiàng)是靜態(tài)確定動(dòng)態(tài)確定3．程序結(jié)構(gòu)決定名字的作用域的規(guī)則和結(jié)構(gòu)A．段結(jié)構(gòu)B．過程定義不嵌套，只允許過程遞歸調(diào)用C．分程序結(jié)構(gòu)分程序嵌套過程定義嵌套4存儲(chǔ)類別的多少GlobalStaticLocaldynamic6術(shù)語靜態(tài)：如果一個(gè)名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動(dòng)態(tài)：如果名字的性質(zhì)只有在程序運(yùn)行時(shí)才能知道，則稱這種性質(zhì)為“動(dòng)態(tài)”確定的。7例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;8數(shù)據(jù)表示（各種數(shù)據(jù)對(duì)象的存儲(chǔ)分配）數(shù)據(jù)對(duì)象的屬性name名字，名稱type類型location內(nèi)存地址value值component成分

9數(shù)據(jù)表示（固定長度，直接或間接表示）簡單變量：char:1byteintegers:2or4bytesfloats:4to16bytesbooleans:1bit(butusually1byte)指針：unsignedintegers一維數(shù)組：一塊連續(xù)的存儲(chǔ)區(qū)多維數(shù)組：一塊連續(xù)的存儲(chǔ)區(qū)，按行存放結(jié)構(gòu)（記錄）：把所有域（field)存放在一塊連續(xù)的存儲(chǔ)區(qū)對(duì)象：類的實(shí)例變量象結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲(chǔ)區(qū)，但方法（成員函數(shù)）不存在該對(duì)象里指令：10l可變(動(dòng)態(tài))數(shù)組：若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定數(shù)組，否則稱為可變(動(dòng)態(tài))數(shù)組。數(shù)組內(nèi)情向量：編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的“內(nèi)情向量”A[l1:u1,l2:u2,,ln:un]l1u1l2u2::typea（首地址）nC11目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織存儲(chǔ)分配策略：簡單的棧式分配方案嵌套過程的棧式分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配——棧式堆式12l術(shù)語-過程活動(dòng)記錄AR:為說明方便，假定程序是由過程組成，過程區(qū)分為源文本，運(yùn)行時(shí)稱作過程的激活。一個(gè)過程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來管理，這個(gè)區(qū)（塊）叫做一個(gè)活動(dòng)記錄或frame（幀）一般這個(gè)段要記錄：l臨時(shí)值，如計(jì)算表達(dá)式時(shí)的中間工作單元。l局部變量（數(shù)據(jù)）l保存運(yùn)行過程前的狀態(tài)（返回地址，寄存器值……）l存取鏈（可選）對(duì)于非局部量的引用。l控制鏈（可選）指向調(diào)用者的活動(dòng)記錄，釋放棧。l實(shí)參（形式單元）l返回值（對(duì)函數(shù)）（有時(shí)可使用寄存器存放返回值）13簡單的棧式分配方案

程序結(jié)構(gòu)特點(diǎn):過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組;例:main全局變量的說明procR……endR;procQ……endQ;主程序執(zhí)行語句endmain14嵌套過程語言的棧式

分配方案

主要特點(diǎn)：（語言）一個(gè)過程可以引用包圍它的任一外層過程所定義的標(biāo)識(shí)符（如變量，數(shù)組或過程等）。（實(shí)現(xiàn)）一個(gè)過程可以引用它的任一外層過程的最新活動(dòng)記錄中的某些數(shù)據(jù)。15關(guān)鍵技術(shù)：解決對(duì)非局部量的引用（存?。ＴO(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄AR的位置。跟蹤辦法：1.用靜態(tài)鏈（如PL/0的SL）。2.用DISPLAY表。16consta=10;

varb,c;

procedurep;

begin

c:=b+a;

end;

begin

read(b);

whileb#0do

begin

callp;

write(2*c);

read(b);

end

end.

(0)jmp08轉(zhuǎn)向主程序入口(1)jmp02轉(zhuǎn)向過程p入口(2)

int03過程p入口,為過程p開辟空間(3)lod13取變量b的值到棧頂(4)lit010取常數(shù)10到棧頂(5)opr02次棧頂與棧頂相加(6)sto14棧頂值送變量c中(7)opr00退棧并返回調(diào)用點(diǎn)(16)(8)

int05主程序入口開辟5個(gè)?？臻g(9)opr016從命令行讀入值置于棧頂(10)sto03將棧頂值存入變量b中(11)lod03將變量b的值取至棧頂(12)lit00將常數(shù)值0進(jìn)棧(13)opr09次棧頂與棧頂是否不等(14)jpc024等時(shí)轉(zhuǎn)(24)（條件不滿足轉(zhuǎn)）(15)cal02

調(diào)用過程p(16)lit02常數(shù)值2進(jìn)棧(17)lod04將變量c的值取至棧頂(18)opr04次棧頂與棧頂相乘(2*c)(19)opr014棧頂值輸出至屏幕(20)opr015換行(21)opr016從命令行讀取值到棧頂(22)sto03棧頂值送變量b中(23)jmp011無條件轉(zhuǎn)到循環(huán)入口(11)(24)opr00結(jié)束退棧17目標(biāo)代碼解釋執(zhí)行時(shí)數(shù)據(jù)棧的布局（運(yùn)行棧的存儲(chǔ)分配）每個(gè)過程的AR有3個(gè)聯(lián)系單元：SL：靜態(tài)鏈，指向定義該過程的直接外過程

（或主程序）運(yùn)行時(shí)最新數(shù)據(jù)段的基地址。DL：動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過 程的數(shù)據(jù)段基地址。RA：返回地址，記錄調(diào)用該過程時(shí)目標(biāo)程序的斷點(diǎn)，即調(diào)用過程指令的下一條指令的地址。局部變量中間結(jié)果18目標(biāo)代碼的解釋執(zhí)行運(yùn)行棧SM調(diào)用過程PRADLSLb..ttbPM19解決對(duì)非局部量的引用（存取）

用Display表Display表---嵌套層次顯示表當(dāng)前激活過程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過程的最新活動(dòng)記錄的基地址20用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R

P的活動(dòng)記錄主程序的活動(dòng)記錄d[1]d[0]displaysptop主程序的活動(dòng)記錄d[0]spdisplaytop（1）（2）21用Display表的方案主程序--->P--->Q--->RR的活動(dòng)記錄Q的活動(dòng)記錄P的活動(dòng)記錄主程序的活動(dòng)記錄Q的活動(dòng)記錄P的活動(dòng)記錄主程序的活動(dòng)記錄displayd[2]d[1]d[0]d[1]d[0]

displaysptoptopsp（3）（4）22DISPLAY表的維護(hù)和建立

DISPLAY表d運(yùn)行棧0主程活動(dòng)記錄地址 1R活動(dòng)記錄地址

...

23

當(dāng)過程的層次為n，它的display為n+1個(gè)值。一個(gè)過程被調(diào)用時(shí)，從調(diào)用過程的DISPLAY表中自下向上抄錄n個(gè)SP值，再加上本層的SP值。全局DISPLAY地址24分程序結(jié)構(gòu)ProcedureA(m,n);integerm,n;

B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;25分程序結(jié)構(gòu)的存儲(chǔ)

分配方案

處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種簡單辦法是，把分程序看成“無名無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲(chǔ)辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。一則，每逢進(jìn)入一個(gè)分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。二則，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可能同時(shí)要結(jié)束若干個(gè)分程序。26按照過程處理辦法，意味著必須一層一層地通過“返回”來恢復(fù)所要到達(dá)的那個(gè)分程序的數(shù)據(jù)區(qū)，但不能直接到達(dá)。例如：如果有一個(gè)從第5層分程序轉(zhuǎn)出到達(dá)第1層分程序的標(biāo)號(hào)L，雖然在第5層分程序工作時(shí)知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動(dòng)記錄基址（SP），但是怎么知道第1層分程序進(jìn)入時(shí)的TOP呢？唯一的辦法是從5,4,3和2各層順序退出。但這種辦法是很浪費(fèi)時(shí)間的。27為了解決上述問題，可采取兩種措施。第一，對(duì)每個(gè)過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器,每個(gè)TOP的值保存在各自活動(dòng)記錄中。這樣，上述的第二個(gè)問題便可解決。第二，不把分程序看作“無參過程”，每個(gè)分程序享用包圍它的那個(gè)最近過程的DISPLAY。每個(gè)分程序都隸屬于某個(gè)確定的過程，分程序的層次是相對(duì)于它所屬的那個(gè)過程進(jìn)行編號(hào)的。28：每個(gè)過程被當(dāng)作是0層分程序。而過程體分程序（假定是一個(gè)分程序）當(dāng)作是它所管轄的第1層分程序。這樣，每個(gè)過程的活動(dòng)記錄所含的內(nèi)容有：1.過程的TOP值，它指向過程活動(dòng)記錄的棧頂位置。2.連接數(shù)據(jù)，共四項(xiàng)：（1)老SP值；（2)返回地址；(3)全局DISPAY地址；（4)調(diào)用時(shí)的棧頂單元地址，老TOP。293.參數(shù)個(gè)數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對(duì)于每個(gè)分程序來說，它們包括：（1)分程序的TOP值。當(dāng)進(jìn)入分程序時(shí)它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時(shí)工作單元。30BZB1TO31數(shù)組B數(shù)組BedB22的TOPB的內(nèi)情向量B的內(nèi)情向量zzB1的TOPB1的TOPDISPLAYDISPLAY形式單元m,n2形式單元m,n2連接數(shù)據(jù)連接數(shù)據(jù)A的TOPA的TOP∶∶∶∶(c)(d)(c)數(shù)組B分配之后；（d）進(jìn)入分程序B22;32參數(shù)傳遞

(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;帶有非局部變量和形參的PASCAL過程非局變量a[i]和a[j]的值進(jìn)行交換，i,j為形參（在這里是傳值）33(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp:integer;(5)begin(6)temp:=x;(7)x:=y;(8)y:=temp(9)end;(10)begin(11)a:=1;b:=2;(12)s);(13)writeln(‘a(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.帶有過程s程序34傳地址（變量參數(shù)）例如：過程sx,y:integer);s）；（a,b為調(diào)用時(shí)的實(shí)參）調(diào)用結(jié)果a,b的值被改變。傳值（值調(diào)用）特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。例如：過程s);s）；其結(jié)果：a,b調(diào)用前的值不改變。35傳值的實(shí)現(xiàn)1.形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說的形式單元（用以存放實(shí)參）。2.調(diào)用過程計(jì)算實(shí)參的值，并將其放在對(duì)應(yīng)形式單元開辟的空間中。3.被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。36procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用s)過程將不會(huì)影響a和b的值。其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：x:=a；y:=b；temp:=x；x:=y；y:=temp37傳地址的實(shí)現(xiàn)（call-by-reference)(call-by-address)(call-by-location)把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過程相應(yīng)的形參：1實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式----傳遞左值2實(shí)在參數(shù)是無左值的表達(dá)式----計(jì)算值，放入一存儲(chǔ)單元，傳此存儲(chǔ)單元地址3目標(biāo)代碼中，被調(diào)用過程對(duì)形參的引用變成對(duì)傳遞給被調(diào)用過程的指針的間接引用38procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用s[i])其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：1把i和a[i]的地址分別放到x和y相應(yīng)的單元a1,a22(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容3(x:=y;)a1所指單元的內(nèi)容置為a2所指單元值4(y:=temp)a2所指單元的內(nèi)容置為temp的值39(1)s)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)s);(9)printf(“aisnow%d,bisnow%d\n”,a,b);(10)}在一個(gè)值調(diào)用過程中使用指針的C程序在C程序中無傳地址所以用指針實(shí)現(xiàn)。40過程調(diào)用的四元式序列S

callid(<arglist>)<arglist>

<arglist>,E<arglist>

EparT1parT2parTncallid,n41(1)S

callid(<arglist>){for隊(duì)列<arglist>.q的每一項(xiàng)Pdo{gen(par,-,-,p);n:=n+1};gen(call,-,-,entry(id))}(2)<arglist>

<arglist>1,E{把E.place排在<arglist>.q的末端；(3)<arglist>

E42過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動(dòng)環(huán)境43programparam(input,output);procedureb(functionh(n:integer):integer);(*)varm:integer;beginm:=3;writeln(h(2))end;procedurec;(*)varm:integer;functionf(n:integer):integr;(&)beginf:=m+nend{f};beginm:=0;b(f)end{c}begincend.

44(1)programparam(input,output);(2)procedureb(functionh(n:integer):integer);(3)beginwriteln(h(2))end;(4)procedurec;(5)varm:integer;(6)functionf(n:integer):integr;(7)beginf:=m+nend{f};(8)beginm:=0;b(f)end{c};(9)begin(10)c(11)end

圖10-27嵌套過程作為參數(shù)傳遞45值結(jié)果傳遞除了未建立真正的別名之外，這個(gè)機(jī)制得到的結(jié)果與引用傳遞類似：在過程中復(fù)制和使用自變量的值，然后當(dāng)過程退出時(shí)，再將參數(shù)的最終值復(fù)制回自變量的地址。因此，這個(gè)方法有時(shí)也被稱為復(fù)制進(jìn)，復(fù)制出，或復(fù)制存儲(chǔ)。值結(jié)果傳遞與引用傳遞的唯一區(qū)別在于別名的表現(xiàn)不同。例如，在以下的代碼中（C語法）：voidp(intx,inty){++x;++y;}main(){inta=1;p(a,a);return0;}在調(diào)用p之后，若使用了引用傳遞，則a的值為3；若使用了值結(jié)果傳遞，則a的值為2。46名字傳遞這是傳遞機(jī)制中最復(fù)雜的參數(shù)了。由于名字傳遞的思想是直到在被調(diào)用的程序真正使用了自變量（作為一個(gè)參數(shù)）之后才對(duì)這個(gè)自變量賦值，所以它還稱作延盡賦值（delayedevaluation）。因此，自變量的名稱或是它在調(diào)用點(diǎn)上的結(jié)構(gòu)表示取代了它對(duì)應(yīng)的參數(shù)的名字。例如在代碼voidp(intx){++x;}中，若做了一個(gè)如p(a[i])的調(diào)用時(shí)，其結(jié)果是計(jì)算++(a[i])。因此，若在p中使用x之前改變i，那么它的結(jié)果就與在引用傳遞或在值結(jié)果傳遞中的不同47inti;inta[10];voidp(intx){++i;++x;}main(){i=1;a[1]=1;a[2]=2;p(a[i]);return0;}對(duì)p的調(diào)用的結(jié)果是將a[2]設(shè)置為3并保持a[1]不變。48名字傳遞的解釋如下：在調(diào)用點(diǎn)上的自變量的文本被看作是它自己右邊的函數(shù)，生當(dāng)在被用的過程的代碼中到達(dá)相應(yīng)的參數(shù)名時(shí)，就要計(jì)算它。我們總是在調(diào)用程序的環(huán)境中計(jì)算自變，而總是在過程的定義環(huán)境中執(zhí)行過程。49建立內(nèi)情向量，分配內(nèi)存的目標(biāo)代碼（n維可變數(shù)組,type--每個(gè)元素占一個(gè)字）begink:=1;n:=1;c:=0;whilek<=ndobegindi:=ui-li+1;m:=m*di;c:=c*di+li;把li,ui和di填進(jìn)內(nèi)情向量表區(qū)；k:=k+1end;申請m個(gè)空間,令首地址為a;把n,c,type,a填進(jìn)內(nèi)情向量表區(qū)end50賦值中數(shù)組元素的翻譯A

V:=EV

id[<elist>]|id<elist>

<elist>,E|EV

<elist>]|id<elist>

<elist>,E|id[E51結(jié)構(gòu)（記錄），抽象數(shù)據(jù)類型對(duì)象類實(shí)例變量的存儲(chǔ)結(jié)構(gòu)(CIR)classparent{|classparent{publicinta,b,c;|publica,b,c;publicvoiddraw(){..};|publicvirtualvoiddraw()};|...classchild:publicparent{|publicd,e;|publicvoidsift(){…};|voiddraw(){…}};52堆式動(dòng)態(tài)存儲(chǔ)分配堆變量堆空間的管理策略減少碎片的技術(shù)空間的釋放53C++的堆變量Int*Ptr;Ptr=newint(5)；

Int*ptr=newint[10]DeleteptrDelete[]ptr堆變量是可以在程序運(yùn)行時(shí)根據(jù)需要隨時(shí)創(chuàng)建或刪除的變量54#include<iostream.h>ClassMyclass{Public:Myclass();Myclass(intk,intj);voidSet(int,int){m=k;n=j;}

Myclass();Private:intm,n;};Myclass::Myclass(){Set(0,0);Cout<<Default<<endl;}Myclass::Myclass(intk,intj){Set(k,j);Cout<<“m=“<<m<<endl;}Myclass::

Myclass(){Cout<<“Destructor”<<endl;}55使用new和delete的示例#include<iostream.h>Intmain(){Cout<<“one”<<endl;Myclass*ptr1=newMyclass;Deleteptr1;Cout<<“two”<<endl;Ptr1=newMyclass(5,10);Deleteptr1;Return0;}oneDefaltDestructortwom=5Destructor56堆式動(dòng)態(tài)存儲(chǔ)分配ConstintArraySize=24;//defaultsizeClassIntArray{Public://operationsperformedonarraysIntArray(intsz=ArraySize);IntArray(constIntArray&);~IntArray(){deleteia;}IntArray&operator=(constIntArray&);int&operator[](int);intgetSize(){returnsize;}protected://internaldatarepresentationintsize;int*ia;};

IntArray()函數(shù)的實(shí)現(xiàn)，引入新的運(yùn)算符newIntArray::IntArray（intsz){size=sz;//allocateanintegerarrayofsize//andsetiatopointtoitia=newint[size];//initializearrayfor(inti=0;i<sz;++i)ia[i]=0;}57C++語言中new操作符施加在一個(gè)類型標(biāo)識(shí)符上（包括類名）Pascal語言中，標(biāo)準(zhǔn)過程new能夠動(dòng)態(tài)建立存儲(chǔ)空間并相應(yīng)地置上指針。標(biāo)準(zhǔn)過程dispose是釋放空間.new與dispose不斷改變著堆存儲(chǔ)器的使用情況。C語言中有這些操作的若干個(gè)版本，但最基本的是malloc和free，它們都是標(biāo)準(zhǔn)庫（stdlib.h）的一部分58需求：一個(gè)程序語言允許用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過程而且有進(jìn)程（process）的程序結(jié)構(gòu)，操作：堆提供兩個(gè)操作，分配操作和釋放操作情況:

經(jīng)一段運(yùn)行時(shí)間之后，這個(gè)大空間就必定被分劃成許多塊塊，有些占用，有些無用（空閑）--碎片問題59當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？運(yùn)行程序要求一塊體積為N的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑塊的總和卻要比N大得多如果運(yùn)行程序要求一塊積為N的空間，但所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放的占用塊60堆管理堆空間的管理策略減少碎片的技術(shù)空間的釋放61堆空間的管理策略

1定長塊管理2變長塊管理62堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)

1定長塊管理堆式動(dòng)態(tài)儲(chǔ)分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針available指向鏈表中的第一塊。分配時(shí)每次都分配指針available所指的塊，然后available指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表。考慮插入方便，可以把所歸還的塊插在available所指的塊之前，然后available指向新歸還的塊。632變長塊管理除了按定長塊進(jìn)行分配之外，還可以根據(jù)需要分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢？通常有三種不同的分配策略64

不同的情況應(yīng)采用不同的方法。通常在選擇時(shí)需考慮下列因素：用戶的要求；請求分配量的大小分布；分配和釋放的頻率以及效率對(duì)系統(tǒng)的重要等等。（1）首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊，就進(jìn)行分配。（2）最優(yōu)滿足法：將空閑塊鏈表中一個(gè)不小于申請塊且最接近于申請塊的空閑塊分配給用戶，則系統(tǒng)在分配前首先要對(duì)空閑塊鏈表從頭至尾描一遍，然后從中找出一塊，為避免每次分配都要掃描整個(gè)鏈表，通常將空閑塊鏈表空間的大小從小到大排序。（3）最差滿足法：將空閑塊表中不小于申請塊且是最大的空閑的一部全分配給用戶。此時(shí)的空閑塊鏈表按空閑的塊的大小從大到小排序。只需從鏈表中刪除第一個(gè)結(jié)點(diǎn)，并將其中一部分分配給用戶，而其它部分作為一個(gè)新的結(jié)點(diǎn)插入到空閑塊表的適當(dāng)置上去。65減少碎片的技術(shù)1分配時(shí)，找最小的足夠大的塊---需保持空閑塊的大小排序2釋放時(shí)，合并任何相鄰的塊---搜索全部空閑塊表，或其它算法3將堆變量緊縮在一起66空間的釋放1顯式釋放2隱式（自動(dòng)）釋放67顯式釋放程序設(shè)計(jì)語言提供機(jī)制如：pascal的disposeC的free程序員必須編寫分配和釋放存儲(chǔ)的明確的調(diào)用注意的問題1堆變量是不可訪問的（垃圾）2懸掛（不安全）指針68堆式分配和釋放的C語言描述#defineNULL0#defineMEMSIZE8096/*changefordifferentsizes*/typedeffdoubleAlign;typedefunionheader{struct{unionheader*next;unsignedusedsize;unsignedfreesize;}s;Aligna;}Header;//數(shù)據(jù)類型Header保存每個(gè)存儲(chǔ)塊的簿記信息staticHeadermem[MEMSIZE];staticHeader*memptr=NULL;void*malloc(unsignednbytes){Header*p,*newp;unsignednunits;nunits=(nbytes+sizeof(Header)-1/sizeof(Header)+1;if(memptr==NULL)69{memptr->s.next=memptr=mem;memptr->s.usedsize=1;memptr->s.freesize=MEMSIZE-1;}for(p=memptr;(p->s.next!=memptr)&&(p->s.freesize<nunits);p=p->s.next);if(p->s.freesize<>nunits)returnNULL;/*noblockbigenough*/newp=p+p->s.usedsize;newp->s.usedsize=nunits;newp->s.freesize=p->s.freesize-nunits;70newp->s.next=p->s.next;p->s.freesize=0;p->s.next=newp;memptr=newp;return(void*)(newp+1);}voidfree(void*ap){Header*bp,*p,*prev;bp=(Header*)ap–1;for(prev=memptr,p=memptr->s.next;(p!=bp)&&(p!=memptr);prev=p,p=p->s.next);if(p!=bp)return;