第十目標程序運行時的組織

第十目標程序運行時的組織第1頁，課件共91頁，創(chuàng)作于2023年2月概述-代碼生成解決語義gap

高級語言支持的概念TypevalueexpressionVariableprocedureFunctionparameters目標機支持的概念

bitsbyteswordsRegistersStackaddressRoutine(subroutine)第2頁，課件共91頁，創(chuàng)作于2023年2月概述代碼生成前如何安排目標機資源運行時組織的幾個問題數(shù)據(jù)表示-如何在目標機中表示每個源語言類型的值表達式求值-如何組織表達式的計算存儲分配-如何組織不同作用域變量的存儲過程實現(xiàn)-如何以例程實現(xiàn)過程，函數(shù)，參數(shù)傳遞

第3頁，課件共91頁，創(chuàng)作于2023年2月概述

任務(wù)：編譯程序?qū)δ繕顺绦蜻\行時的組織（設(shè)計運行環(huán)境和分配存儲）如通常存儲區(qū)布局可為：

目標代碼區(qū)

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

Stackheap 第4頁，課件共91頁，創(chuàng)作于2023年2月運行環(huán)境和存儲分配

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

關(guān)聯(lián)（Binding）將源程序的文本程序運行動作的實現(xiàn)源文件中的名字N

運行時的存儲S在語義學中，使用術(shù)語environment函數(shù)表示env:N→S(N到S的映射)第5頁，課件共91頁，創(chuàng)作于2023年2月第6頁，課件共91頁，創(chuàng)作于2023年2月決定運行管理復(fù)雜程度的因素——源語言本身1.允許的數(shù)據(jù)類型的多少2．語言中允許的數(shù)據(jù)項是

靜態(tài)確定

動態(tài)確定3．程序結(jié)構(gòu)

決定名字的作用域的規(guī)則和結(jié)構(gòu)A．

段結(jié)構(gòu)B．

過程定義不嵌套，只允許過程遞歸調(diào)用C．

分程序結(jié)構(gòu)分程序嵌套過程定義嵌套

4存儲類別的多少GlobalStaticLocaldynamic第7頁，課件共91頁，創(chuàng)作于2023年2月術(shù)語靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動態(tài)：如果名字的性質(zhì)只有在程序運行時才能知道，則稱這種性質(zhì)為“動態(tài)”確定的。第8頁，課件共91頁，創(chuàng)作于2023年2月例procedureA(m,n:integer);beginrealz;arrayB[m:n];begin···end;

end;第9頁，課件共91頁，創(chuàng)作于2023年2月第10頁，課件共91頁，創(chuàng)作于2023年2月第11頁，課件共91頁，創(chuàng)作于2023年2月數(shù)據(jù)表示各種數(shù)據(jù)對象的存儲分配數(shù)據(jù)對象的屬性

name名字，名稱

type類型

location內(nèi)存地址

value值

component成分

第12頁，課件共91頁，創(chuàng)作于2023年2月數(shù)據(jù)表示（固定長度，直接或間接表示）簡單變量：

char:1byteintegers:2or4bytesfloats:4to16bytesbooleans:1bit(butusually1byte)指針：unsignedintegers一維數(shù)組：一塊連續(xù)的存儲區(qū)多維數(shù)組：一塊連續(xù)的存儲區(qū)，按行存放結(jié)構(gòu)（記錄）：把所有域（field)存放在一塊連續(xù)的存儲區(qū)對象：類的實例變量象結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲區(qū)，但方法（成員函數(shù)）不存在該對象里指令：第13頁，課件共91頁，創(chuàng)作于2023年2月第14頁，課件共91頁，創(chuàng)作于2023年2月第15頁，課件共91頁，創(chuàng)作于2023年2月第16頁，課件共91頁，創(chuàng)作于2023年2月l

可變(動態(tài))數(shù)組：若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為可變(動態(tài))數(shù)組。數(shù)組內(nèi)情向量：:

編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的“內(nèi)情向量”A[l1:u1,l2:u2,

,ln

:un]

l1

u1

l2

u2

:

:

type

a（首地址）

nC第17頁，課件共91頁，創(chuàng)作于2023年2月目標程序運行時的存儲組織存儲分配策略：簡單的棧式分配方案嵌套過程的棧式分配方案分程序結(jié)構(gòu)的存儲分配方案靜態(tài)存儲分配動態(tài)存儲分配——棧式堆式第18頁，課件共91頁，創(chuàng)作于2023年2月l

術(shù)語-過程活動記錄AR:為說明方便，假定程序是由過程組成，過程區(qū)分為源文本，運行時稱作過程的激活。一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū)

（塊）叫做一個活動記錄或frame（幀）一般這個段要記錄：l

臨時值，如計算表達式時的中間工作單元。l

局部變量（數(shù)據(jù)）l

保存運行過程前的狀態(tài)（返回地址，寄存器值……）l

存取鏈（可選）

對于非局部量的引用。l

控制鏈（可選）

指向調(diào)用者的活動記錄，釋放棧。l

實參（形式單元）l

返回值（對函數(shù)）（有時可使用寄存器存放返回值）第19頁，課件共91頁，創(chuàng)作于2023年2月簡單的棧式分配方案

程序結(jié)構(gòu)特點:過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組;例:main

全局變量的說明procR……endR;procQ……endQ;主程序執(zhí)行語句endmain第20頁，課件共91頁，創(chuàng)作于2023年2月第21頁，課件共91頁，創(chuàng)作于2023年2月第22頁，課件共91頁，創(chuàng)作于2023年2月嵌套過程語言的棧式

分配方案

主要特點：（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，數(shù)組或過程等）。（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。第23頁，課件共91頁，創(chuàng)作于2023年2月

關(guān)鍵技術(shù)：解決對非局部量的引用（存?。?。設(shè)法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤辦法：

1.用靜態(tài)鏈（如PL/0的SL）。

2.用DISPLAY表。第24頁，課件共91頁，創(chuàng)作于2023年2月consta=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)用點(16)(8)

int05主程序入口開辟5個?？臻g(9)opr016從命令行讀入值置于棧頂(10)sto03將棧頂值存入變量b中(11)lod03將變量b的值取至棧頂(12)lit00將常數(shù)值0進棧(13)opr09次棧頂與棧頂是否不等(14)jpc024

等時轉(zhuǎn)(24)（條件不滿足轉(zhuǎn)）(15)cal02

調(diào)用過程p(16)lit02常數(shù)值2進棧(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é)束退棧第25頁，課件共91頁，創(chuàng)作于2023年2月目標代碼解釋執(zhí)行時數(shù)據(jù)棧的布局（運行棧的存儲分配）每個過程的AR有3個聯(lián)系單元：SL：靜態(tài)鏈，指向定義該過程的直接外過程

（或主程序）運行時最新數(shù)據(jù)段的基地址。DL：動態(tài)鏈，指向調(diào)用該過程前正在運行過 程的數(shù)據(jù)段基地址。RA：返回地址，記錄調(diào)用該過程時目標程序的斷點，即調(diào)用過程指令的下一條指令的地址。局部變量中間結(jié)果第26頁，課件共91頁，創(chuàng)作于2023年2月目標代碼的解釋執(zhí)行運行棧SM調(diào)用過程P

RADLSLb..ttbPM第27頁，課件共91頁，創(chuàng)作于2023年2月解決對非局部量的引用（存?。?/p>

用Display表Display表---嵌套層次顯示表當前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過程的最新活動記錄的基地址第28頁，課件共91頁，創(chuàng)作于2023年2月第29頁，課件共91頁，創(chuàng)作于2023年2月用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R

P的活動記錄主程序的活動記錄

d[1]d[0]displaysptop主程序的活動記錄

d[0]spdisplaytop（1）（2）第30頁，課件共91頁，創(chuàng)作于2023年2月用Display表的方案主程序--->P--->Q--->RR的活動記錄Q的活動記錄

P的活動記錄主程序的活動記錄Q的活動記錄

P的活動記錄主程序的活動記錄

displayd[2]d[1]d[0]

d[1]d[0]

displaysptoptopsp（3）（4）第31頁，課件共91頁，創(chuàng)作于2023年2月DISPLAY表的維護和建立

DISPLAY表d運行棧

0主程活動記錄地址

1R活動記錄地址

...

第32頁，課件共91頁，創(chuàng)作于2023年2月

當過程的層次為n，它的display為n+1個值。一個過程被調(diào)用時，從調(diào)用過程的DISPLAY表中自下向上抄錄n個SP值，再加上本層的SP值。全局DISPLAY地址第33頁，課件共91頁，創(chuàng)作于2023年2月分程序結(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;第34頁，課件共91頁，創(chuàng)作于2023年2月分程序結(jié)構(gòu)的存儲

分配方案

處理分程序結(jié)構(gòu)存儲分配方案的一種簡單辦法是，把分程序看成“無名無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。一則，每逢進入一個分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。二則，當從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。第35頁，課件共91頁，創(chuàng)作于2023年2月

按照過程處理辦法，意味著必須一層一層地通過“返回”來恢復(fù)所要到達的那個分程序的數(shù)據(jù)區(qū)，但不能直接到達。例如：如果有一個從第5層分程序轉(zhuǎn)出到達第1層分程序的標號L，雖然在第5層分程序工作時知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動記錄基址（SP），但是怎么知道第1層分程序進入時的TOP呢？唯一的辦法是從5,4,3和2各層順序退出。但這種辦法是很浪費時間的。第36頁，課件共91頁，創(chuàng)作于2023年2月

為了解決上述問題，可采取兩種措施。第一，對每個過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器,每個TOP的值保存在各自活動記錄中。這樣，上述的第二個問題便可解決。第二，不把分程序看作“無參過程”，每個分程序享用包圍它的那個最近過程的DISPLAY。每個分程序都隸屬于某個確定的過程，分程序的層次是相對于它所屬的那個過程進行編號的。第37頁，課件共91頁，創(chuàng)作于2023年2月：每個過程被當作是0層分程序。而過程體分程序（假定是一個分程序）當作是它所管轄的第1層分程序。這樣，每個過程的活動記錄所含的內(nèi)容有：1.過程的TOP值，它指向過程活動記錄的棧頂位置。2.連接數(shù)據(jù)，共四項：（1)老SP值；（2)返回地址；

(3)全局DISPAY地址；（4)調(diào)用時的棧頂單元地址，老TOP。第38頁，課件共91頁，創(chuàng)作于2023年2月

3.參數(shù)個數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對于每個分程序來說，它們包括：（1)分程序的TOP值。當進入分程序時它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時工作單元。第39頁，課件共91頁，創(chuàng)作于2023年2月第40頁，課件共91頁，創(chuàng)作于2023年2月B

Z

B1T

O第41頁，課件共91頁，創(chuàng)作于2023年2月

數(shù)

組B

數(shù)

組B

e

dB22的TOPB的

內(nèi)

情

向

量B的

內(nèi)

情

向

量

z

zB1的TOPB1的TOPDISPLAYDISPLAY

形式單元

m,n

2

形式單元

m,n

2連

接

數(shù)

據(jù)連接

數(shù)

據(jù)A的TOPA的TOP

∶

∶

∶

∶

(c)(d)(c)數(shù)組B分配之后；

（d）進入分程序B22;第42頁，課件共91頁，創(chuàng)作于2023年2月第43頁，課件共91頁，創(chuàng)作于2023年2月參數(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]的值進行交換，i,j為形參（在這里是傳值）第44頁，課件共91頁，創(chuàng)作于2023年2月

(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)swap(a,b);(13)writeln(‘a(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.

帶有過程swap的PASCAL程序第45頁，課件共91頁，創(chuàng)作于2023年2月

傳地址（變量參數(shù)）例如：過程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時的實參）調(diào)用結(jié)果a,b的值被改變。傳值（值調(diào)用）特點是對形式參數(shù)的任何運算不影響實參的值。例如：過程swap(x,y:integer);swap(a,b）；其結(jié)果：a,b調(diào)用前的值不改變。第46頁，課件共91頁，創(chuàng)作于2023年2月傳值的實現(xiàn)1.形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。2.調(diào)用過程計算實參的值，并將其放在對應(yīng)形式單元開辟的空間中。3.被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。第47頁，課件共91頁，創(chuàng)作于2023年2月procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(a,b)過程將不會影響a和b的值。其結(jié)果等價于執(zhí)行下列運算：x:=a；y:=b；temp:=x；x:=y；y:=temp第48頁，課件共91頁，創(chuàng)作于2023年2月傳地址的實現(xiàn)（call-by-reference)(call-by-address)(call-by-location)

把實在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應(yīng)的形參：1實在參數(shù)是一個名字，或具有左值的表達式----傳遞左值2實在參數(shù)是無左值的表達式----計算值，放入一存儲單元，傳此存儲單元地址3目標代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程的指針的間接引用第49頁，課件共91頁，創(chuàng)作于2023年2月procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(i,a[i])其結(jié)果等價于執(zhí)行下列運算：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的值第50頁，課件共91頁，創(chuàng)作于2023年2月

(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)swap(&a,&b);(9)printf(“aisnow%d,bisnow%d\n”,a,b);(10)}

在一個值調(diào)用過程中使用指針的C程序在C程序中無傳地址所以用指針實現(xiàn)。第51頁，課件共91頁，創(chuàng)作于2023年2月過程調(diào)用的四元式序列

Scallid(<arglist>)<arglist><arglist>,E<arglist>EparT1parT2parTncallid,n第52頁，課件共91頁，創(chuàng)作于2023年2月過程調(diào)用的四元式序列(1)Scallid(<arglist>){for隊列<arglist>.q的每一項Pdo{gen(par,-,-,p);n:=n+1};gen(call,-,-,entry(id))}(2)<arglist><arglist>1,E{把E.place排在<arglist>.q

的末端；(3)<arglist>E第53頁，課件共91頁，創(chuàng)作于2023年2月過程作為參數(shù)傳遞三種環(huán)境：詞法環(huán)境傳遞環(huán)境活動環(huán)境第54頁，課件共91頁，創(chuàng)作于2023年2月

programparam(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.

第55頁，課件共91頁，創(chuàng)作于2023年2月(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ù)傳遞第56頁，課件共91頁，創(chuàng)作于2023年2月第57頁，課件共91頁，創(chuàng)作于2023年2月值結(jié)果傳遞除了未建立真正的別名之外，這個機制得到的結(jié)果與引用傳遞類似：在過程中復(fù)制和使用自變量的值，然后當過程退出時，再將參數(shù)的最終值復(fù)制回自變量的地址。因此，這個方法有時也被稱為復(fù)制進，復(fù)制出，或復(fù)制存儲。值結(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。第58頁，課件共91頁，創(chuàng)作于2023年2月名字傳遞這是傳遞機制中最復(fù)雜的參數(shù)了。由于名字傳遞的思想是直到在被調(diào)用的程序真正使用了自變量（作為一個參數(shù)）之后才對這個自變量賦值，所以它還稱作延盡賦值（delayedevaluation）。因此，自變量的名稱或是它在調(diào)用點上的結(jié)構(gòu)表示取代了它對應(yīng)的參數(shù)的名字。例如在代碼voidp(intx){++x;}中，若做了一個如p(a[i])的調(diào)用時，其結(jié)果是計算++(a[i])。因此，若在p中使用x之前改變i，那么它的結(jié)果就與在引用傳遞或在值結(jié)果傳遞中的不同第59頁，課件共91頁，創(chuàng)作于2023年2月inti;inta[10];voidp(intx){++i;++x;}main(){i=1;a[1]=1;a[2]=2;p(a[i]);return0;}對p的調(diào)用的結(jié)果是將a[2]設(shè)置為3并保持a[1]不變。第60頁，課件共91頁，創(chuàng)作于2023年2月名字傳遞的解釋如下：在調(diào)用點上的自變量的文本被看作是它自己右邊的函數(shù)，生當在被用的過程的代碼中到達相應(yīng)的參數(shù)名時，就要計算它。我們總是在調(diào)用程序的環(huán)境中計算自變，而總是在過程的定義環(huán)境中執(zhí)行過程。第61頁，課件共91頁，創(chuàng)作于2023年2月建立內(nèi)情向量，分配內(nèi)存的目標代碼（n維可變數(shù)組,type--每個元素占一個字）begink:=1;n:=1;c:=0;whilek<=ndobegindi:=ui-li+1;m:=m*di;c:=c*di+li;把li,ui和di填進內(nèi)情向量表區(qū)；k:=k+1end;申請m個空間,令首地址為a;把n,c,type,a填進內(nèi)情向量表區(qū)end第62頁，課件共91頁，創(chuàng)作于2023年2月賦值中數(shù)組元素的翻譯AV:=EVid[<elist>]|id<elist><elist>,E|EV<elist>]|id<elist><elist>,E|id[E第63頁，課件共91頁，創(chuàng)作于2023年2月結(jié)構(gòu)（記錄），抽象數(shù)據(jù)類型對象類實例變量的存儲結(jié)構(gòu)(CIR)classparent{|classparent{publicinta,b,c;|publica,b,c;publicvoiddraw(){..};|publicvirtualvoiddraw()};|...classchild:publicparent{|publicd,e;|publicvoidsift(){…};|voiddraw(){…}};第64頁，課件共91頁，創(chuàng)作于2023年2月堆式動態(tài)存儲分配堆變量堆空間的管理策略減少碎片的技術(shù)空間的釋放第65頁，課件共91頁，創(chuàng)作于2023年2月C++的堆變量Int*Ptr;Ptr=newint(5)；

Int*ptr=newint[10]DeleteptrDelete[]ptr堆變量是可以在程序運行時根據(jù)需要隨時創(chuàng)建或刪除的變量第66頁，課件共91頁，創(chuàng)作于2023年2月C++的堆對象#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;}第67頁，課件共91頁，創(chuàng)作于2023年2月使用new和delete的示例#include<iostream.h>Intmain(){Cout<<“one”<<endl;Myclass*ptr1=newMyclass;Deleteptr1;Cout<<“two”<<endl;Ptr1=newMyclass(5,10);Deleteptr1;Return0;}oneDefaltDestructortwom=5Destructor第68頁，課件共91頁，創(chuàng)作于2023年2月堆式動態(tài)存儲分配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ù)的實現(xiàn)，引入新的運算符newIntArray::IntArray（intsz){size=sz;//allocateanintegerarrayofsize//andsetiatopointtoitia=newint[size];//initializearrayfor(inti=0;i<sz;++i)ia[i]=0;}第69頁，課件共91頁，創(chuàng)作于2023年2月C++語言中new操作符施加在一個類型標識符上（包括類名）Pascal語言中，標準過程new能夠動態(tài)建立存儲空間并相應(yīng)地置上指針。標準過程dispose是釋放空間.new與dispose不斷改變著堆存儲器的使用情況。C語言中有這些操作的若干個版本，但最基本的是malloc和free，它們都是標準庫（stdlib.h）的一部分第70頁，課件共91頁，創(chuàng)作于2023年2月堆式動態(tài)存儲分配需求：一個程序語言允許用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過程而且有進程（process）的程序結(jié)構(gòu)，操作：堆提供兩個操作，分配操作和釋放操作情況:

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

1定長塊管理2變長塊管理第74頁，課件共91頁，創(chuàng)作于2023年2月堆式動態(tài)儲分配的實現(xiàn)

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

不同的情況應(yīng)采用不同的方法。通常在選擇時需考慮下列因素：用戶的要求；請求分配量的大小分布；分配和釋放的頻率以及效率對系統(tǒng)的重要等等。（1）首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊，就進行分配。（2）最優(yōu)滿足法：將空閑塊鏈表中一個不小于申請塊且最接近于申請塊的空閑塊分配給用戶，則系統(tǒng)在分配前首先要對空閑塊鏈表從頭至尾描一遍，然后從中找出一塊，為避免每次分配都要掃描整個鏈表，通常將空閑塊鏈表空間的大小從小到大排序。（3）最差滿足法：將空閑塊表中不小于申請塊且是最大的空閑的一部全分配給用戶。此時的空閑塊鏈表按空閑的塊的大小從大到小排序。只需從鏈表中刪除第一個結(jié)點，并將其中一部分分配給用戶，而其它部分作為一個新的結(jié)點插入到空閑塊表的適當置上去。第77頁，課件共91頁，創(chuàng)作于2023年2月減少碎片的技術(shù)1分配時，找最小的足夠大的塊---需保持空閑塊的大小排序2釋放時，合并任何相鄰的塊---搜索全部空閑塊表，或其它算法3將堆變量緊縮在一起第78頁，課件共91頁，創(chuàng)作于2023年2月空間的釋放1顯式釋放2隱式（自動）釋放第79頁，課件共91頁，創(chuàng)作于2023年2月顯式釋放程序設(shè)計語言提供機制如：pascal的disposeC的free程序員必須編寫分配和釋放存儲的明確的調(diào)用注意的問題1堆變量是不可訪問的（垃圾）

2懸掛（不安全）指針第80頁，課件共91頁，創(chuàng)作于2023年2月堆式分配和釋放的C語言描述#defineNULL0#defineMEMSIZE8096/*changefordifferentsizes*/typedeffdoubleAlign;typedefunionheader{struct{unionheader*next;unsignedusedsize;unsignedfreesize;}s;Aligna;}Header;//數(shù)據(jù)類型Header保存每個存儲塊的簿記信息staticHeadermem[MEMSIZE];staticHeader*memptr=NULL;void*malloc(unsignednbytes){Header*p,*newp;unsignednunits;nunits=(nbytes+sizeof(Header)-1/sizeof(Header)+1;if(memptr==NULL)第81頁，課件共91頁，創(chuàng)作于2023年2月{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;第82頁，課件共91頁，創(chuàng)作于2023年2月newp->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,*pre