第9章運(yùn)行時(shí)存儲(chǔ)空間組織_第1頁
第9章運(yùn)行時(shí)存儲(chǔ)空間組織_第2頁
第9章運(yùn)行時(shí)存儲(chǔ)空間組織_第3頁
第9章運(yùn)行時(shí)存儲(chǔ)空間組織_第4頁
第9章運(yùn)行時(shí)存儲(chǔ)空間組織_第5頁
已閱讀5頁,還剩41頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

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

程序中使用的存儲(chǔ)單元都由標(biāo)識(shí)符來表示。 標(biāo)識(shí)符對應(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簡單的棧式存儲(chǔ)分配9.5嵌套過程語言的棧式實(shí)現(xiàn)9.6堆式動(dòng)態(tài)存儲(chǔ)分配1、過程的活動(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ù)的對象 (1)目標(biāo)代碼編譯是可確定,故可放在一個(gè)靜態(tài)確 定的區(qū)域 (2)數(shù)據(jù)對象部分?jǐn)?shù)據(jù)對象的大小在編譯時(shí)可確 定,故也可放在一個(gè)靜態(tài)確定的區(qū)域 (3)跟蹤過程活動(dòng)的控制棧目標(biāo)代碼靜態(tài)數(shù)據(jù)?!?.2運(yùn)行時(shí)存儲(chǔ)器的劃分2、棧和堆

A、棧:用擴(kuò)充的棧來管理過程的活動(dòng),當(dāng)發(fā)生過程 調(diào)用時(shí),中斷當(dāng)前活動(dòng)的執(zhí)行,激活新被調(diào) 用過程的活動(dòng),并把包含在這個(gè)活動(dòng)生存期 中的數(shù)據(jù)對象以及該活動(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)記錄:為了管理過程在一次執(zhí)行中所需要 的信息,使用一個(gè)連續(xù)的存儲(chǔ)塊,該連 續(xù)的存儲(chǔ)塊叫活動(dòng)記錄。

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

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

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

返回地址

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

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

靜態(tài)鏈——指向靜態(tài)直接外層最新活動(dòng)記錄地址的 指針,用來訪問非局部數(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í)存儲(chǔ)器的劃分三、存儲(chǔ)分配策略

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

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

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

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

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

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

過程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)(3)主程序先調(diào)用過程Q,然后主程序調(diào)用R, 且過程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簡單的棧式存儲(chǔ)分配4、指示器SP——總是指向現(xiàn)行過程活動(dòng)記錄的 起點(diǎn),用于訪問局部數(shù)據(jù)

指示器TOP——始終指向(已占用)棧頂單元9.4簡單的棧式存儲(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)過程的局部變量臨時(shí)工作單元內(nèi)情向量簡單變量形式單元參數(shù)個(gè)數(shù)返回地址老SPTOPSP9.4簡單的棧式存儲(chǔ)分配2、(1)不允許過程嵌套——非局部量僅能出現(xiàn)在源程 序頭,可采用靜態(tài)存儲(chǔ)分配,編譯時(shí)可確定其地址

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

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

變址訪問X[SP]X——代表相對數(shù),即相對于活動(dòng)記 錄起點(diǎn)的地址,編譯時(shí)可完全確定下來9.4簡單的棧式存儲(chǔ)分配二、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+活動(dòng)單元數(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)鏈和活動(dòng)記錄

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

動(dòng)態(tài)鏈——活動(dòng)記錄一個(gè)域,從一個(gè)過程的當(dāng)前活動(dòng) 記錄指向調(diào)用該過程前正在運(yùn)行的過程的最新 的活動(dòng)記錄的基地址。B、活動(dòng)記錄結(jié)構(gòu)——P259圖9.16形式單元參數(shù)個(gè)數(shù)靜態(tài)鏈動(dòng)態(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)前過程/活動(dòng)可以引用的“非局部變量”的過程的活動(dòng)記錄的基址,從而找到要引用的“非局部變量”

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

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

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

含有i+1個(gè)單元。該表本身是一個(gè)小棧,自頂向 下每個(gè)單元依次存放現(xiàn)行層,直接外層……,直 到最外層(0層主程序?qū)樱┑让恳粚舆^程的最新 活動(dòng)記錄的基地址。舉例:令過程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嵌套過程語言的棧式實(shí)現(xiàn)C、“非局部量”地址的確定:

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

原因:——因?yàn)橥ㄟ^顯示表的一個(gè)域,可以確定任意 外層活動(dòng)記錄的指針,再沿著這個(gè)指針便可 以找到處于外層活動(dòng)記錄的非局部量。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)號(hà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堆式動(dòng)態(tài)存儲(chǔ)分配1、堆式動(dòng)態(tài)存儲(chǔ)分配使用的情況(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堆式動(dòng)態(tài)存儲(chǔ)分配一、堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn)

1、定長塊管理

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

(2)優(yōu)點(diǎn):

2、變長塊管理

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論