第9章運(yùn)行時(shí)存儲(chǔ)空間組織

第九章運(yùn)行時(shí)存儲(chǔ)空間組織

在程序的執(zhí)行過(guò)程中，程序中數(shù)據(jù)的存取是通過(guò)與之對(duì)應(yīng)的存儲(chǔ)單元來(lái)進(jìn)行的。

程序中使用的存儲(chǔ)單元都由標(biāo)識(shí)符來(lái)表示。 標(biāo)識(shí)符對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。第九章運(yùn)行時(shí)存儲(chǔ)空間組織9.1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)9.2運(yùn)行時(shí)存儲(chǔ)器的劃分9.3靜態(tài)存儲(chǔ)分配9.4簡(jiǎn)單的棧式存儲(chǔ)分配9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)9.6堆式動(dòng)態(tài)存儲(chǔ)分配1、過(guò)程的活動(dòng)

P2409.1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)2、參數(shù)傳遞（1）傳值（2）傳地址（3）傳名（4）得結(jié)果9.1目標(biāo)程序運(yùn)行時(shí)的活動(dòng)例：procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end;若存在調(diào)用：swap(i,k(i))（1）傳值（2）傳地址（3）傳名：

j:=i;i:=K(i);k(i):=j;例：procedureswap(n,m:real);varj:real;beginj:=n;n:=m;m:=j;end;若存在調(diào)用：swap(i,k(i))(4)得結(jié)果

swap(m,n)addr(i),iaddr(k(i)),K(i)9.2運(yùn)行時(shí)存儲(chǔ)器的劃分一、運(yùn)行時(shí)存儲(chǔ)器的劃分

1、編譯器需要在存儲(chǔ)區(qū)保護(hù)的對(duì)象 （1）目標(biāo)代碼編譯是可確定，故可放在一個(gè)靜態(tài)確 定的區(qū)域 （2）數(shù)據(jù)對(duì)象部分?jǐn)?shù)據(jù)對(duì)象的大小在編譯時(shí)可確 定，故也可放在一個(gè)靜態(tài)確定的區(qū)域 （3）跟蹤過(guò)程活動(dòng)的控制棧目標(biāo)代碼靜態(tài)數(shù)據(jù)?！?.2運(yùn)行時(shí)存儲(chǔ)器的劃分2、棧和堆

A、棧：用擴(kuò)充的棧來(lái)管理過(guò)程的活動(dòng)，當(dāng)發(fā)生過(guò)程 調(diào)用時(shí)，中斷當(dāng)前活動(dòng)的執(zhí)行，激活新被調(diào) 用過(guò)程的活動(dòng)，并把包含在這個(gè)活動(dòng)生存期 中的數(shù)據(jù)對(duì)象以及該活動(dòng)有關(guān)的其它信息存 入棧中。當(dāng)控制從調(diào)用返回時(shí)，將所占存儲(chǔ) 空間彈出棧頂。同時(shí)，被中斷的活動(dòng)恢復(fù)執(zhí)行。B、堆（heap）——存放動(dòng)態(tài)數(shù)據(jù)，大小可隨程序的運(yùn) 行而改變。9.2運(yùn)行時(shí)存儲(chǔ)器的劃分二、活動(dòng)記錄

1、活動(dòng)記錄：為了管理過(guò)程在一次執(zhí)行中所需要 的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，該連 續(xù)的存儲(chǔ)塊叫活動(dòng)記錄。

當(dāng)過(guò)程調(diào)用時(shí)，產(chǎn)生一個(gè)過(guò)程的新的活動(dòng)，用一 個(gè)活動(dòng)記錄表示該活動(dòng)的相關(guān)信息，并將 其壓入棧。

當(dāng)過(guò)程返回時(shí)，將該活動(dòng)記錄從棧中彈出。PascalC9.2運(yùn)行時(shí)存儲(chǔ)器的劃分2、活動(dòng)記錄的內(nèi)容（1）連接數(shù)據(jù)

SP指向現(xiàn)行過(guò)程的活動(dòng)記錄在棧里的起始位置。

返回地址

動(dòng)態(tài)鏈——

指向調(diào)用該過(guò)程前的最新活動(dòng)記錄地址 的指針。運(yùn)行時(shí)，使運(yùn)行棧上各數(shù)據(jù)全動(dòng)態(tài)建 立的次序結(jié)成鏈。鏈頭為棧頂起始位置。

靜態(tài)鏈——指向靜態(tài)直接外層最新活動(dòng)記錄地址的 指針，用來(lái)訪問(wèn)非局部數(shù)據(jù)（2）形式單元——存放相應(yīng)的實(shí)在參數(shù)的地址或值（3）局部數(shù)據(jù)區(qū)

局部變量——簡(jiǎn)單變量

內(nèi)情向量——局部數(shù)據(jù)的內(nèi)情向量，即數(shù)組元素

臨時(shí)工作單元——存放對(duì)表達(dá)式求值的結(jié)果9.2運(yùn)行時(shí)存儲(chǔ)器的劃分三、存儲(chǔ)分配策略

1、靜態(tài)存儲(chǔ)分配策略 在編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變。

2、棧式動(dòng)態(tài)分配策略 在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過(guò)程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦退出，它所占空間就予以釋放。

3、堆式動(dòng)態(tài)分配策略 在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還（回收），凡申請(qǐng)者從堆中分給一塊，凡釋放者退回給堆9.3靜態(tài)存儲(chǔ)分配P2469.4簡(jiǎn)單的棧式存儲(chǔ)分配1、前提：假設(shè)程序語(yǔ)言無(wú)分程序結(jié)構(gòu)，過(guò)程定義不允 許嵌套，但允許過(guò)程的遞歸調(diào)用。

例如：C語(yǔ)言2、過(guò)程：運(yùn)行時(shí)

每當(dāng)進(jìn)入一個(gè)過(guò)程——即一個(gè)過(guò)程的活動(dòng)開(kāi)始，就把其 它活動(dòng)記錄壓入棧（置于棧頂），從而 形成過(guò)程工作時(shí)的數(shù)據(jù)區(qū)

當(dāng)活動(dòng)結(jié)束——即過(guò)程退出時(shí)，再把其活動(dòng)記錄彈出 棧，這樣，它在棧頂上的數(shù)據(jù)區(qū)在隨即 不復(fù)存在9.4簡(jiǎn)單的棧式存儲(chǔ)分配3、舉例（1）主程序調(diào)用過(guò)程Q，而Q又調(diào)用R，在R進(jìn) 入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)（2）主程序調(diào)用過(guò)程Q，Q遞歸調(diào)用自己，在Q

過(guò)程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)（3）主程序先調(diào)用過(guò)程Q，然后主程序調(diào)用R， 且過(guò)程Q不調(diào)用Q和R?Q和R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖所示：R的活動(dòng)記錄Q的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)SPTOP靜態(tài)分配9.4簡(jiǎn)單的棧式存儲(chǔ)分配4、指示器SP——總是指向現(xiàn)行過(guò)程活動(dòng)記錄的 起點(diǎn)，用于訪問(wèn)局部數(shù)據(jù)

指示器TOP——始終指向（已占用）棧頂單元9.4簡(jiǎn)單的棧式存儲(chǔ)分配一、C的活動(dòng)記錄

1、C的活動(dòng)記錄的項(xiàng)目（1）連接數(shù)據(jù)——A、老SP值:

即前一活動(dòng)記錄的地址

B、返回地址（2）參數(shù)個(gè)數(shù)（3）形式單元——存放實(shí)在參數(shù)的值或地址（4）過(guò)程的局部變量臨時(shí)工作單元內(nèi)情向量簡(jiǎn)單變量形式單元參數(shù)個(gè)數(shù)返回地址老SPTOPSP9.4簡(jiǎn)單的棧式存儲(chǔ)分配2、（1）不允許過(guò)程嵌套——非局部量?jī)H能出現(xiàn)在源程 序頭，可采用靜態(tài)存儲(chǔ)分配，編譯時(shí)可確定其地址

（2）局部變量或形參在活動(dòng)記錄中的位置確定 其地址是相對(duì)于活動(dòng)記錄的基地址SP的

絕對(duì)地址=活動(dòng)記錄基地址+相對(duì)地址

變址訪問(wèn)X[SP]X——代表相對(duì)數(shù)，即相對(duì)于活動(dòng)記 錄起點(diǎn)的地址，編譯時(shí)可完全確定下來(lái)9.4簡(jiǎn)單的棧式存儲(chǔ)分配二、C的過(guò)程調(diào)用，過(guò)程進(jìn)入、數(shù)組空間分配和過(guò)程返回已知過(guò)程調(diào)用的四元式序列為：parT1

… parTn callP,nC語(yǔ)言過(guò)程調(diào)用與返回ParTi(i+3)[TOP]:=Ti（傳值）或(i+3)[TOP]:=addr(Ti)（傳地址）CallP,n1[TOP]:=SP3[TOP]:=nJSRP(轉(zhuǎn)P)SP:=TOP+11[SP]:=返回地址TOP:=TOP+活動(dòng)單元數(shù)Return(E)TOP:=SP－1SP:=0[SP]X:=2[TOP]UJ0[x]/*UJ:無(wú)條件轉(zhuǎn)移*/9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)前提：假定允許過(guò)程定義嵌套，如Pascal語(yǔ)言，但去掉Pascal中的“文件”類(lèi)型

程序舉例：——課本P258圖9.159.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)一、非局部名字的訪問(wèn)的實(shí)現(xiàn)說(shuō)明——非局部名字的訪問(wèn)

1、靜態(tài)鏈和活動(dòng)記錄

A、靜態(tài)鏈——活動(dòng)記錄的一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活 動(dòng)記錄指向其靜態(tài)直接外層的最新活動(dòng)記錄。

動(dòng)態(tài)鏈——活動(dòng)記錄一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活動(dòng) 記錄指向調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的最新 的活動(dòng)記錄的基地址。B、活動(dòng)記錄結(jié)構(gòu)——P259圖9.16形式單元參數(shù)個(gè)數(shù)靜態(tài)鏈動(dòng)態(tài)鏈（老SP）返回地址簡(jiǎn)單變量?jī)?nèi)情向量臨時(shí)工作單元SPTOPprogramP;vara,x:integer;

procQ(b:integer);vari:integer;

procR(u:integer,varv:integer);varc,d:integer;begin…end;begin…end;

procS;varc,i:integer;begin…end;begin…cP;

procQ;procR;begin…R(..,..);…end;

begin…R(…,…)…end;

procS;

begin…

Q(…)

…end;begin…

S;…end.

01234567890返回地址0ax0返回地址00（形參個(gè)數(shù)）csptopi10sptopC、程序運(yùn)行時(shí)棧的變化過(guò)程——舉例：ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址0ic0(形參個(gè)數(shù))0返回地址0xa0返回地址0過(guò)程P中調(diào)用S時(shí)161514131211109876543210SPTOPTOPSP109876543210過(guò)程S中調(diào)用Q時(shí)dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址0TOPSP1211109876543210242322212019181716151413過(guò)程Q中調(diào)用R時(shí)dcvu211返回地址17dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP過(guò)程R中遞歸調(diào)用R9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)D、含義：

靜態(tài)鏈：通過(guò)其值可以找到當(dāng)前過(guò)程/活動(dòng)可以引用的“非局部變量”的過(guò)程的活動(dòng)記錄的基址，從而找到要引用的“非局部變量”

動(dòng)態(tài)鏈：通過(guò)其值可以找到當(dāng)前過(guò)程/活動(dòng)結(jié)束后，需要返回的上一層活動(dòng)記錄的基址SP9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)2、嵌套層次顯示表（display）和活動(dòng)記錄

A、嵌套層次顯示表：每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)區(qū)的同時(shí)建立該表

B、表的內(nèi)容：假定現(xiàn)進(jìn)行的過(guò)程的層數(shù)為i，則其display

含有i+1個(gè)單元。該表本身是一個(gè)小棧，自頂向 下每個(gè)單元依次存放現(xiàn)行層，直接外層……,直 到最外層（0層主程序?qū)樱┑让恳粚舆^(guò)程的最新 活動(dòng)記錄的基地址。舉例：令過(guò)程R的外層為Q，Q的外層為P，則R運(yùn)行時(shí)display表為2R的現(xiàn)行活動(dòng)記錄地址（SP的現(xiàn)行值）1Q的最新活動(dòng)記錄的地址0P的活動(dòng)記里的地址9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)C、“非局部量”地址的確定：

絕對(duì)地址=display[靜態(tài)層數(shù)]+相對(duì)地址D、活動(dòng)記錄結(jié)構(gòu)：TOPa321SP0臨時(shí)單元內(nèi)情向量簡(jiǎn)單變量display形參單元參數(shù)個(gè)數(shù)全局Display返回地址老SP(動(dòng)態(tài)鏈)p1調(diào)用P2的兩種不同嵌套：P1P2P0P2P1k-1kk-1kkp1調(diào)用P2的兩種不同嵌套：P1P2k-1k…DisplayK項(xiàng)………P1P2P1的displayk項(xiàng)p2的sptopsptopspp1調(diào)用P2的兩種不同嵌套：P0P2P1k-1kk…DisplayK+1項(xiàng)………P1P2P1的display前k項(xiàng)p2的sptopsptopsp00返回地址10（display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510C11i12sptoptopspdisplayF、靜態(tài)鏈方法與顯示表方法的比較： 通過(guò)向示表訪問(wèn)非局部量要比沿著靜態(tài)鏈訪問(wèn)非局部量的速度快。

原因：——因?yàn)橥ㄟ^(guò)顯示表的一個(gè)域，可以確定任意 外層活動(dòng)記錄的指針，再沿著這個(gè)指針便可 以找到處于外層活動(dòng)記錄的非局部量。9.5嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)二、參數(shù)傳遞的實(shí)現(xiàn)

1、parT T——為數(shù)組 （1）或者傳遞數(shù)組T的首地址 （2）或者傳遞數(shù)組T的內(nèi)情向量地址

2、ParT T——為過(guò)程 假設(shè)：過(guò)程P把過(guò)程T作為實(shí)在參數(shù)傳遞過(guò)程Q，隨 后，Q又通過(guò)引用相應(yīng)的形式參數(shù)調(diào)用T。

3、Par T——為標(biāo)號(hào)?在進(jìn)入T之后，為了建立T自己的display，T必須知道它直接外層的display。又P的display或者正好就是這個(gè)外層的display， 或者包含了這個(gè)外層display而由于T的層數(shù)是已知的?只要知道P的display，T就可以用它來(lái)建立自己的display，即假定T的層數(shù)為1，則T的display乃是由P的display的前1個(gè)單元的內(nèi)容和SP的現(xiàn)行值所組成。?為了使得過(guò)程T工作時(shí)能夠知道過(guò)程P的display，必須在P把T作為使 參傳遞給Q的時(shí)候把P自身的display地址也傳過(guò)去即：過(guò)程P中的parT的作用可刻畫(huà)為建立如下所示的兩個(gè)相繼臨時(shí)單元：

第一個(gè)臨時(shí)單元B1：過(guò)程T的入口地址

第二個(gè)臨時(shí)單元B2：過(guò)程T的display地址。；然后執(zhí)行（i+1）[TOP]:=addr(B1)把第一臨時(shí)單元B1的地址傳給Q假定過(guò)程Q現(xiàn)在執(zhí)行到調(diào)用語(yǔ)句callZ,mZ——形式參數(shù)，形式單元Z中已含有上述B1的地址?故B1的內(nèi)容將用來(lái)作為轉(zhuǎn)子指令的目的地址 （即轉(zhuǎn)進(jìn)過(guò)程T）

B2的內(nèi)容將作為“全局display地址” （第三項(xiàng)連接數(shù)據(jù)）傳送給T9.6堆式動(dòng)態(tài)存儲(chǔ)分配1、堆式動(dòng)態(tài)存儲(chǔ)分配使用的情況（1）允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還空間（2）不僅有過(guò)程而且有進(jìn)程的程序結(jié)構(gòu) 即空間的使用未必服從“先請(qǐng)后還，后請(qǐng)先還”的原則

例如：pascal語(yǔ)言中的標(biāo)準(zhǔn)過(guò)程new-dispose2、該種分配方法必須考慮的幾個(gè)主要問(wèn)題（1）當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，我的應(yīng)該分配那一塊給它？（2）如果運(yùn)行程序要求一塊體積為N的空間，但所有空閑 塊的總和也不夠N，那該怎么辦？9.6堆式動(dòng)態(tài)存儲(chǔ)分配一、堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn)

1、定長(zhǎng)塊管理

（1）實(shí)現(xiàn)方法：

（2）優(yōu)點(diǎn)：

2、變長(zhǎng)塊管理

（1）實(shí)現(xiàn)方法

（2）實(shí)現(xiàn)的分配策略 首次滿足法