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

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

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

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

P2409.1目標(biāo)程序運(yùn)行時(shí)的活動2、參數(shù)傳遞（1）傳值（2）傳地址（3）傳名（4）得結(jié)果9.1目標(biāo)程序運(yùn)行時(shí)的活動例：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í)存儲器的劃分一、運(yùn)行時(shí)存儲器的劃分

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

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

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

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

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

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

返回地址

動態(tài)鏈——

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

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

局部變量——簡單變量

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

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

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

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

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

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

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

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

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

指示器TOP——始終指向（已占用）棧頂單元9.4簡單的棧式存儲分配一、C的活動記錄

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

即前一活動記錄的地址

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

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

絕對地址=活動記錄基地址+相對地址

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

… parTn callP,nC語言過程調(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+活動單元數(shù)Return(E)TOP:=SP－1SP:=0[SP]X:=2[TOP]UJ0[x]/*UJ:無條件轉(zhuǎn)移*/9.5嵌套過程語言的棧式實(shí)現(xiàn)前提：假定允許過程定義嵌套，如Pascal語言，但去掉Pascal中的“文件”類型

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

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

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

動態(tài)鏈——活動記錄一個(gè)域，從一個(gè)過程的當(dāng)前活動 記錄指向調(diào)用該過程前正在運(yùn)行的過程的最新 的活動記錄的基地址。B、活動記錄結(jié)構(gòu)——P259圖9.16形式單元參數(shù)個(gè)數(shù)靜態(tài)鏈動態(tài)鏈（老SP）返回地址簡單變量內(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í)棧的變化過程——舉例：ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址0ic0(形參個(gè)數(shù))0返回地址0xa0返回地址0過程P中調(diào)用S時(shí)161514131211109876543210SPTOPTOPSP109876543210過程S中調(diào)用Q時(shí)dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址0TOPSP1211109876543210242322212019181716151413過程Q中調(diào)用R時(shí)dcvu211返回地址17dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0xa0返回地址032313029282726252423222120191817161514131211109876543210SPTOP過程R中遞歸調(diào)用R9.5嵌套過程語言的棧式實(shí)現(xiàn)D、含義：

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

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

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

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

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

絕對地址=display[靜態(tài)層數(shù)]+相對地址D、活動記錄結(jié)構(gòu)：TOPa321SP0臨時(shí)單元內(nèi)情向量簡單變量display形參單元參數(shù)個(gè)數(shù)全局Display返回地址老SP(動態(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)鏈方法與顯示表方法的比較： 通過向示表訪問非局部量要比沿著靜態(tài)鏈訪問非局部量的速度快。

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

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

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

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

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

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

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

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

1、定長塊管理

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

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

2、變長塊管理

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

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