目標(biāo)程序運(yùn)行時(shí)的.ppt

1、第十章 目標(biāo)程序運(yùn)行時(shí)的組織,10.1 概述 2數(shù)據(jù)表示 10.3目標(biāo)程序運(yùn)行時(shí)的棧式存儲(chǔ)組織 10.4 參數(shù)傳遞 10.5堆式存儲(chǔ)組織的討論,概述-代碼生成解決語義gap,高級(jí)語言支持的概念 Type value expression Variable procedure Function parameters,目標(biāo)機(jī)支持的概念 bits bytes words Registers Stack address Routine(sub routine),概述,代碼生成前如何安排目標(biāo)機(jī)資源 運(yùn)行時(shí)組織的幾個(gè)問題 數(shù)據(jù)表示-如何在目標(biāo)機(jī)中表示每個(gè)源語言類型的值 表達(dá)式求值-如何組織表達(dá)式的計(jì)算 存

2、儲(chǔ)分配-如何組織不同作用域變量的存儲(chǔ) 過程實(shí)現(xiàn)-如何以例程實(shí)現(xiàn)過程，函數(shù)，參數(shù)傳遞,概述,任務(wù)：編譯程序?qū)δ繕?biāo)程序運(yùn)行時(shí)的組織（設(shè)計(jì)運(yùn)行環(huán)境和分配存儲(chǔ)） 如 通常存儲(chǔ)區(qū)布局可為：,目標(biāo)代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū) Stack heap,運(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: NS (N到S的映射),決定運(yùn)行管理復(fù)雜程度的因素源語言本身,1.,允許的數(shù)據(jù)類型的多少,2,語言中允許的數(shù)據(jù)項(xiàng)是,靜態(tài)確定,動(dòng)態(tài)確定,3,程序結(jié)

3、構(gòu),決定名字的作用域的規(guī)則和結(jié)構(gòu),A,段結(jié)構(gòu),B,過程定義不嵌套，只允許過程遞歸調(diào)用,C,分程序結(jié)構(gòu),分程序嵌套,過程定義嵌套,4存儲(chǔ)類別的多少,Global Static Local dynamic,術(shù)語,靜態(tài)：如果一個(gè)名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。 動(dòng)態(tài)：如果名字的性質(zhì)只有在程序運(yùn)行時(shí)才能知道，則稱這種性質(zhì)為“動(dòng)態(tài)”確定的。,例 procedure A(m,n:integer); begin real z; array Bm:n; begin end; end;,數(shù)據(jù)表示各種數(shù)據(jù)對(duì)象的存儲(chǔ)分配,數(shù)據(jù)對(duì)象的屬性 name 名字，名稱 type 類型

4、location 內(nèi)存地址 value 值 component 成分,數(shù)據(jù)表示（固定長度，直接或間接表示）,簡單變量： char: 1 byte integers: 2 or 4 bytes floats: 4 to 16 bytes booleans: 1 bit (but usually 1 byte) 指針：unsigned integers 一維數(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ì)象里 指令：,l,可變 (動(dòng)態(tài))數(shù)組

5、： 若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定數(shù)組，否則稱為可變(動(dòng)態(tài))數(shù)組。 數(shù)組內(nèi)情向量：,:,編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的,“內(nèi),情向量”,Al,1,:u,1,l,2,:u,2,l,n,:,u,n,l,1,u,1,l,2,u,2,:,:,type,a,（首地址）,n C,目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織,存儲(chǔ)分配策略： 簡單的棧式分配方案 嵌套過程的棧式分配方案 分程序結(jié)構(gòu)的存儲(chǔ)分配方案,靜態(tài)存儲(chǔ)分配,動(dòng)態(tài)存儲(chǔ)分配棧式,堆式,l,術(shù)語-過程活動(dòng)記錄,AR,:,為說明方便，假定程序是由過程組成，過程區(qū)分為源文本，,運(yùn)行時(shí)稱作過程的激活。,一個(gè)過程的一次執(zhí)行所需

6、要的信息使用一個(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í)可使用寄存器存放返回值）,簡單的棧式分配方案,程序結(jié)構(gòu)特點(diǎn):過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組; 例: main 全局變量的說明 proc R end R; proc Q end Q; 主程序執(zhí)行語句 en

7、d main,嵌套過程語言的棧式分配方案,主要特點(diǎn)： （語言）一個(gè)過程可以引用包圍它的任一外層過程所定義的標(biāo)識(shí)符（如變量，數(shù)組或過程等）。 （實(shí)現(xiàn)）一個(gè)過程可以引用它的任一外層過程的最新活動(dòng)記錄中的某些數(shù)據(jù)。,關(guān)鍵技術(shù)：解決對(duì)非局部量的引用（存?。?。 設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄AR的位置。 跟蹤辦法： 1. 用靜態(tài)鏈（如PL/0的SL）。 2. 用DISPLAY表。,const a=10;var b,c;procedure p; begin c:=b+a; end;begin read(b); while b#0 do begin call p; write(2*c); read(b)

8、; endend.,( 0) jmp 0 8 轉(zhuǎn)向主程序入口 ( 1) jmp 0 2 轉(zhuǎn)向過程p入口 ( 2) int 0 3 過程p入口,為過程p開辟空間 ( 3) lod 1 3 取變量b的值到棧頂 ( 4) lit 0 10 取常數(shù)10到棧頂 ( 5) opr 0 2 次棧頂與棧頂相加 ( 6) sto 1 4 棧頂值送變量c中 ( 7) opr 0 0 退棧并返回調(diào)用點(diǎn)(16) ( 8) int 0 5 主程序入口開辟5個(gè)?？臻g ( 9) opr 0 16 從命令行讀入值置于棧頂 (10) sto 0 3 將棧頂值存入變量b中 (11) lod 0 3 將變量b的值取至棧頂 (12)

9、 lit 0 0 將常數(shù)值0進(jìn)棧 (13) opr 0 9 次棧頂與棧頂是否不等 (14) jpc 0 24 等時(shí)轉(zhuǎn)(24)（條件不滿足轉(zhuǎn)） (15) cal 0 2 調(diào)用過程p (16) lit 0 2 常數(shù)值2進(jìn)棧 (17) lod 0 4 將變量c的值取至棧頂 (18) opr 0 4 次棧頂與棧頂相乘(2*c) (19) opr 0 14 棧頂值輸出至屏幕 (20) opr 0 15 換行 (21) opr 0 16 從命令行讀取值到棧頂 (22) sto 0 3 棧頂值送變量b中 (23) jmp 0 11 無條件轉(zhuǎn)到循環(huán)入口(11) (24) opr 0 0 結(jié)束退棧,目標(biāo)代碼解釋

10、執(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é)果,目標(biāo)代碼的解釋執(zhí)行 運(yùn)行棧S,M調(diào)用過程P,RA DL SL,b,. .,t,t,b,P,M,解決對(duì)非局部量的引用（存?。┯肈isplay表,Display表-嵌套層次顯示表 當(dāng)前激活過程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層直至最外

11、層的每一過程的最新活動(dòng)記錄的基地址,用Display表的方案,(1)主程序-(2)P-(3)Q-(4)R,P 的 活動(dòng)記錄 主程序的 活動(dòng)記錄,d1 d0,display,sp,top,主程序的 活動(dòng)記錄,d0,sp,display,top,（1）,（2）,用Display表的方案,主程序-P-Q-R,R 的 活動(dòng)記錄 Q 的 活動(dòng)記錄 P 的 活動(dòng)記錄 主程序的 活動(dòng)記錄,Q 的 活動(dòng)記錄 P 的 活動(dòng)記錄 主程序的 活動(dòng)記錄,display,d2 d1 d0,d1 d0,display,sp,top,top,sp,（3）,（4）,DISPLAY表的維護(hù)和建立,DISPLAY表d 運(yùn)行棧 0

12、 主程活動(dòng)記錄地址 1 R活動(dòng)記錄地址,.,當(dāng)過程的層次為n，它的 display為n+1個(gè)值。 一個(gè)過程被調(diào)用時(shí)，從調(diào)用過程的DISPLAY表中自下向上抄錄n個(gè)SP值，再加上本層的SP值。 全局DISPLAY地址,分程序結(jié)構(gòu) Procedure A(m,n); integer m,n; B1:begin real z; array Bm:n; B2:begin real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end;,分程序結(jié)構(gòu)的存儲(chǔ)分配方案,處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種

13、簡單辦法是，把分程序看成 “無名無參過 程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲(chǔ)辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。 一則，每逢進(jìn)入 一個(gè)分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。 二則 ，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可能同時(shí)要結(jié)束若干個(gè)分程序。,按照過程處理辦法，意味著必須一層一層地通過“返回” 來恢復(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)入

14、時(shí)的TOP呢？唯一的辦法是從 5,4,3和2各層順序退出。但這種辦法是很浪費(fèi)時(shí)間的。,為了解決上述問題，可采取兩種措施。第一，對(duì)每個(gè)過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器, 每個(gè)TOP的值保存在各自活動(dòng)記錄中。這樣，上述的第二個(gè)問題便可解決。第二，不把分程序看作“無參過程”，每個(gè)分程序享用包圍它的那個(gè)最近過程的DISPLAY。每個(gè)分程序都隸屬于某個(gè)確定的過程，分程序的層次是相對(duì)于它所屬的那個(gè)過程進(jìn)行編號(hào)的。,：,每個(gè)過程被當(dāng)作是0層分程序。而過程體分程序（假定是一個(gè)分程序）當(dāng)作是它所管轄的第1層分程序。 這樣，每個(gè)過程的活動(dòng)記錄所含的內(nèi)容有： 1.過程的TOP

15、值，它指向過程活動(dòng)記錄的棧頂位置。 2.連接數(shù)據(jù)，共四項(xiàng)： （1)老SP值； （2)返回地址； (3)全局DISPAY地址； （4)調(diào)用時(shí)的棧頂單元地址，老TOP。,3. 參數(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í)工作單元。,B,Z,B,1,T,O,D I S P L A Y,D I S P L A Y,形式單元,m,n,2,形式單元,m,n,2,連,接,數(shù),據(jù),連接,數(shù),

16、據(jù),A,的,T O P,A,的,T O P,(c),(d),(c ),數(shù)組,B,分配之后；,（,d,）進(jìn)入分程序,B2,2,;,參數(shù)傳遞,(1)procedure exchangel(i,j:integer); (2) var x:integer; (3) begin; (4) x:=ai; ai:=aj; aj:=x (5) end; 帶有非局部變量和形參的PASCAL過程 非局變量ai和aj的值進(jìn)行交換，i,j為形參（在這里是傳值）,(1)program reference(input,output); (2)var a,b:integer; (3)procedure swap(var x

17、,y:integer); (4) var temp:integer; (5) begin (6) temp:=x; (7) x:=y; (8) y:=temp (9) end; (10)begin (11) a:=1; b:=2; (12) swap(a,b); (13) writeln(a=,a);writeln(b=,b) (14)end. 帶有過程swap的PASCAL程序,傳地址（變量參數(shù)） 例如：過程 swap(var x,y:integer); swap(a,b）；（ a,b為調(diào)用時(shí)的實(shí)參 ） 調(diào)用結(jié)果a,b的值被改變。 傳值（值調(diào)用） 特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。

18、例如：過程 swap(x,y:integer); swap(a,b）；其結(jié)果： a,b調(diào)用前的值不改變。,傳值的實(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í)，就像使用局部變量一樣使用這些形式單元。,procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調(diào)用swap(a,b) 過程將不會(huì)影響a和b的值。 其結(jié)

19、果等價(jià)于執(zhí)行下列運(yùn)算： x :=a； y :=b； temp :=x； x :=y； y :=temp,傳地址的實(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)用過程的指針的間接引用,procedure swap( x,y:integer); v

20、ar temp:integer; begin temp:=x; x:=y； y:=temp end； 調(diào)用swap(i,ai) 其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算： 1把 i和ai的地址分別放到x和y相應(yīng)的單元a1,a2 2( temp :=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容 3 (x :=y;) a1所指單元的內(nèi)容置為a2所指單元值 4( y :=temp) a2所指單元的內(nèi)容置為temp的值,(1)swap(x,y) (2)int *x,*y; (3) int temp; (4) temp=*x; *x=*y; *y=temp; (5) (6)main( ) (7) int a=1,b=

21、2; (8) swap( (10) 在一個(gè)值調(diào)用過程中使用指針的C程序 在C程序中無傳地址所以用指針實(shí)現(xiàn)。,過程調(diào)用的四元式序列,S call id() ,E E par T1 par T2 par Tn call id,n,過程調(diào)用的四元式序列,(1)S call id()for 隊(duì)列.q的 每一項(xiàng)P do gen(par,-,-,p);n:=n+1; gen(call,-,-,entry(id) (2) 1,E把E.place排在.q 的末端； (3) E,過程作為參數(shù)傳遞,三種環(huán)境：詞法環(huán)境 傳遞環(huán)境 活動(dòng)環(huán)境,program param(input,output); procedure

22、 b(function h(n:integer):integer); (*) var m:integer; begin m:=3; writeln(h(2) endb; procedure c; (*) var m:integer; function f(n:integer):integr; ( b(f) end c begin c end.,(1)program param(input,output); (2)procedure b(function h(n:integer):integer); (3) begin writeln(h(2) endb; (4)procedure c; (5)

23、 var m:integer; (6) function f(n:integer):integr; (7) begin f:=m+n endf; (8)begin m := 0; b(f) end c; (9)begin (10) c (11)end 圖10-27 嵌套過程作為參數(shù)傳遞,值結(jié)果傳遞,除了未建立真正的別名之外，這個(gè)機(jī)制得到的結(jié)果與引用傳遞類似：在過程中復(fù)制和使用自變量的值，然后當(dāng)過程退出時(shí)，再將參數(shù)的最終值復(fù)制回自變量的地址。因此，這個(gè)方法有時(shí)也被稱為復(fù)制進(jìn)，復(fù)制出，或復(fù)制存儲(chǔ)。 值結(jié)果傳遞與引用傳遞的唯一區(qū)別在于別名的表現(xiàn)不同。例如，在以下的代碼中（C語法）：void p (i

24、nt x, int y) +x; +y; main() int a=1; p(a,a); return 0; 在調(diào)用p之后，若使用了引用傳遞，則a的值為3；若使用了值結(jié)果傳遞，則a的值為2。,名字傳遞,這是傳遞機(jī)制中最復(fù)雜的參數(shù)了。由于名字傳遞的思想是直到在被調(diào)用的程序真正使用了自變量（作為一個(gè)參數(shù)）之后才對(duì)這個(gè)自變量賦值，所以它還稱作延盡賦值（delayed evaluation）。因此，自變量的名稱或是它在調(diào)用點(diǎn)上的結(jié)構(gòu)表示取代了它對(duì)應(yīng)的參數(shù)的名字。例如在代碼 void p (int x) +x; 中，若做了一個(gè)如p(ai)的調(diào)用時(shí)，其結(jié)果是計(jì)算+(ai)。因此，若在p中使用x之前改變i，

25、那么它的結(jié)果就與在引用傳遞或在值結(jié)果傳遞中的不同,int i; int a 10; void p (int x) +i; +x; main () i=1; a1=1; a2=2; p(ai); return 0; 對(duì)p的調(diào)用的結(jié)果是將a2設(shè)置為3并保持a1不變。,名字傳遞的解釋如下：在調(diào)用點(diǎn)上的自變量的文本被看作是它自己右邊的函數(shù)，生當(dāng)在被用的過程的代碼中到達(dá)相應(yīng)的參數(shù)名時(shí)，就要計(jì)算它。我們總是在調(diào)用程序的環(huán)境中計(jì)算自變，而總是在過程的定義環(huán)境中執(zhí)行過程。,建立內(nèi)情向量，分配內(nèi)存的目標(biāo)代碼,（n維可變數(shù)組, type-每個(gè)元素占一個(gè)字） begin k:=1;n:=1;c:=0; while

26、k=n do begin di:=ui-li+ 1; m:=m*di; c:=c*di+li; 把li,ui和di填進(jìn)內(nèi)情向量表區(qū)； k:=k+1 end; 申請(qǐng)m個(gè)空間, 令首地址為a;把n,c,type ,a填進(jìn)內(nèi)情 向量表區(qū) end,賦值中數(shù)組元素的翻譯,A V:=E V id | id ,E | E V | id , E | id E,結(jié)構(gòu)（記錄），抽象數(shù)據(jù)類型對(duì)象,類實(shí)例變量的存儲(chǔ)結(jié)構(gòu)(CIR) class parent | class parent public int a,b,c; | public a,b,c; public void draw() .; | public vi

27、rtual void draw() ; | . class child:public parent | public d,e; | public void sift(); | void draw() ;,堆式動(dòng)態(tài)存儲(chǔ)分配,堆變量 堆空間的管理策略 減少碎片的技術(shù) 空間的釋放,C+的堆變量,Int *Ptr; Ptr=new int(5)； Int *ptr= new int 10,Delete ptr Delete ptr 堆變量是可以在程序運(yùn)行時(shí)根據(jù)需要隨時(shí)創(chuàng)建或刪除的變量,C+的堆對(duì)象,#include Class Myclass Public: Myclass(); Myclass(in

28、t k,int j); void Set(int,int)m=k;n=j; Myclass(); Private: int m,n; ;,Myclass:Myclass() Set(0,0); CoutDefaultendl; Myclass:Myclass(int k,int j) Set(k,j); Cout“m=“mendl; Myclass: Myclass() Cout“Destructor”endl; ,使用new和delete的示例,#include Int main() Cout“one”endl; Myclass *ptr1=new Myclass; Delete ptr1;

29、 Cout“two”endl; Ptr1=new Myclass(5,10); Delete ptr1; Return 0; ,one Defalt Destructor two m=5 Destructor,堆式動(dòng)態(tài)存儲(chǔ)分配,Const int ArraySize=24;/ default size Class IntArray Public: /operations performed on arrays IntArray(int sz=ArraySize); IntArray(const IntArray,IntArray()函數(shù)的實(shí)現(xiàn)，引入新的運(yùn)算符new IntArray:IntAr

30、ray （int sz) size= sz; / allocate an integer array of size / and set ia to point to it ia= new int size; / initialize array for (int i=0;isz;+i) iai=0; ,C+語言中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，它們都

31、是標(biāo)準(zhǔn)庫（stdlib.h）的一部分,堆式動(dòng)態(tài)存儲(chǔ)分配,需求： 一個(gè)程序語言允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過程而且有進(jìn)程（process）的程序結(jié)構(gòu)， 操作： 堆提供兩個(gè)操作，分配操作和釋放操作 情況: 經(jīng)一段運(yùn)行時(shí)間之后，這個(gè)大空間就必定被分劃成許多塊塊，有些占用，有些無用（空閑）-碎片問題,堆式動(dòng)態(tài)儲(chǔ)分配,當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？ 運(yùn)行程序要求一塊體積為N的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑塊的總和卻要比N大得多 如果運(yùn)行程序要求一塊積為N的空間，但所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做垃圾

32、回收的辦法來對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放的占用塊,堆管理,堆空間的管理策略 減少碎片的技術(shù) 空間的釋放,堆空間的管理策略,1 定長塊管理 2 變長塊管理,堆式動(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所指的塊之前，然后avail

33、able指向新歸還的塊。,2 變長塊管理 除了按定長塊進(jìn)行分配之外，還可以根據(jù)需要分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢？通常有三種不同的分配策略,不同的情況應(yīng)采用不同的方法。通常在選擇時(shí)需考慮下列因素：用戶的要求；請(qǐng)求分配量的大

34、小分布；分配和釋放的頻率以及效率對(duì)系統(tǒng)的重要等等。,（1）首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊，就進(jìn)行分配。 （2）最優(yōu)滿足法：將空閑塊鏈表中一個(gè)不小于申請(qǐng)塊且最接近于申請(qǐng)塊的空閑塊分配給用戶，則系統(tǒng)在分配前首先要對(duì)空閑塊鏈表從頭至尾描一遍，然后從中找出一塊，為避免每次分配都要掃描整個(gè)鏈表，通常將空閑塊鏈表空間的大小從小到大排序。 （3）最差滿足法：將空閑塊表中不小于申請(qǐng)塊且是最大的空閑的一部全分配給用戶。此時(shí)的空閑塊鏈表按空閑的塊的大小從大到小排序。只需從鏈表中刪除第一個(gè)結(jié)點(diǎn)，并將其中一部分分配給用戶，而其它部分作為一個(gè)新的結(jié)點(diǎn)插入到空閑塊表的適當(dāng)置上去。,減少碎片的技術(shù),1分配

35、時(shí)，找最小的足夠大的塊-需保持空閑塊的大小排序 2 釋放時(shí)，合并任何相鄰的塊-搜索全部空閑塊表，或其它算法 3 將堆變量緊縮在一起,空間的釋放,1顯式釋放 2隱式（自動(dòng)）釋放,顯式釋放,程序設(shè)計(jì)語言提供機(jī)制 如：pascal 的 dispose C 的free 程序員必須編寫分配和釋放存儲(chǔ)的明確的調(diào)用 注意的問題 1 堆變量是不可訪問的（垃圾） 2 懸掛（不安全）指針,堆式分配和釋放的C語言描述,#define NULL 0 # define MEMSIZE 8096 /* change for different sizes */ typedef fdouble Align; typedef

36、 union header struct union header *next; unsigned usedsize; unsigned freesize; s; Align a; Header;/數(shù)據(jù)類型Header保存每個(gè)存儲(chǔ)塊的簿記信息 static Header mem MEMSIZE; static Header *memptr= NULL; void *malloc (unsigned nbytes) Header *p, *newp; unsigned nunits; nunits= (nbytes+sizeof (Header)-1/ sizeof (Header)+1; if

37、 (memptr = NULL),memptr-s. next = memptr = mem; memptr-s. usedsize = 1; memptr-s. freesize = MEMSIZE-1; for (p=memptr; (p-s. next!= memptr) ,newp-s.next = p-s. next; p-s. freesize=0; p-s. next= newp; memptr=newp; return (void *)(newp+1); void free (void *ap) Header * bp, *p, *prev; bp= (Header *) ap 1; for (prev= memptr, p=memptr-s. next; (p!=bp) ,堆的自動(dòng)管理-隱式存儲(chǔ)回收,在一種需要完全動(dòng)態(tài)的運(yùn)行時(shí)環(huán)境的語言（OO語言，函數(shù)式語言Lisp,ML)中，堆也必須類似地自動(dòng)管理。自動(dòng)存儲(chǔ)器管理涉及到了前面分配的但不再使用的存儲(chǔ)器的回收，可能是在它被分配的很久以后，而沒有明確的對(duì)free的調(diào)用。這個(gè)過程稱作垃圾回收（grabage collection）。,垃圾回收,垃圾回收程序-尋找可被引用的所有存儲(chǔ)器并釋所有未引用的存儲(chǔ)器