




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、過(guò)程的每一次運(yùn)行(或執(zhí)行)被稱為一次活動(dòng)(activation)?;顒?dòng)是一個(gè)動(dòng)態(tài)的概念,除了設(shè)計(jì)為永不停機(jī)的過(guò)程(如操作系統(tǒng)等),或者是因設(shè)計(jì)錯(cuò)誤而出現(xiàn)死循環(huán)的過(guò)程之外,任何過(guò)程的活動(dòng)均有有限的生存期(life time)。,第九章 運(yùn)行時(shí)存儲(chǔ)空間組織,概述:編譯程序必須在生成目標(biāo)代碼前分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間變量、常量的存放和訪問(wèn),9.1目標(biāo)程序運(yùn)行時(shí)的活動(dòng),一. 過(guò)程(procedure)的活動(dòng) 過(guò)程的概念(定義,p241): 靜態(tài)源程序,過(guò)程體,函數(shù) 動(dòng)態(tài)目標(biāo)程序的運(yùn)行活動(dòng),過(guò)程:為討論方便,將整個(gè)程序、函數(shù)均視為過(guò)程。,過(guò)程的活動(dòng):是指該過(guò)程的一次執(zhí)行。,過(guò)程的活動(dòng)生存期:指從該過(guò)
2、程體第一步操作到最后一步操作之間的操作序。兩個(gè)過(guò)程的活動(dòng)生存期或嵌套或不重疊。,一個(gè)標(biāo)識(shí)符說(shuō)明在程序中能起作用的范圍稱為該說(shuō)明的作用域。,生存期和作用域?qū)Q定分配目標(biāo)程序數(shù)據(jù)空間的基本策略。 ex: Fig 9.1 program,例:寫(xiě)出參數(shù)傳遞的結(jié)果 Program simple(output); var x:integer; procedure change(y:integer); begin y:=1 end; begin x:=0; change(x); write(x) End.,傳值: x=0 傳地址: x=1,二、參數(shù)傳遞 :傳地址、傳值、傳名、得結(jié)果p241,9.2 運(yùn)行時(shí)存
3、儲(chǔ)器的劃分,一、存儲(chǔ)器的劃分,程序運(yùn)行時(shí)必須由操作系統(tǒng)分配一定的存儲(chǔ)空間,編譯程序應(yīng)完成對(duì)該存儲(chǔ)空間劃分:,存放編譯時(shí)可確定大小的數(shù)據(jù)對(duì)象,如目標(biāo)代碼、如FROTRUN,過(guò)程的活動(dòng)在編譯時(shí)不確定,在運(yùn)行時(shí)當(dāng)有新過(guò)程被調(diào)用,則將該過(guò)程的相關(guān)數(shù)據(jù)放入棧中(在生存周期內(nèi)的所有對(duì)象及其相關(guān)信息),棧的lifo特性正好對(duì)應(yīng)過(guò)程的嵌套調(diào)用,存放動(dòng)態(tài)數(shù)據(jù)(如鏈表等不符合lifo協(xié)議的動(dòng)態(tài)數(shù)據(jù)),二. 活動(dòng)記錄,為管理過(guò)程的活動(dòng),用一個(gè)活動(dòng)記錄(Activation Record,連續(xù)的存儲(chǔ)塊)來(lái)表示其相應(yīng)的所有信息。,活動(dòng)記錄的結(jié)構(gòu): 1. 臨時(shí)單元(存放表達(dá)式求值等)、內(nèi)情向量、局部變量為局部數(shù)據(jù)區(qū);,2
4、. 形式單元:存放實(shí)在參數(shù)的地址或值;,3. 靜態(tài)鏈:指向直接外層過(guò)程的最新活動(dòng)記錄,用于訪問(wèn)非局部變量;,4. 動(dòng)態(tài)鏈:指向調(diào)用本過(guò)程的最新活動(dòng)記錄的起始地址;各數(shù)據(jù)區(qū)構(gòu)成次序鏈。,作用:過(guò)程被調(diào)用時(shí)產(chǎn)生新的活動(dòng),并將相關(guān)信息(活動(dòng)記錄),并壓入棧。,指向現(xiàn)行(最新)過(guò)程,每個(gè)活動(dòng)記錄的大小在編譯時(shí)可以確定( 除動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)外 ),因此以SP為變址器可方便的訪問(wèn)各個(gè)數(shù)據(jù)。,三. 存儲(chǔ)分配策略不同的編譯程序有不同的策略,靜態(tài)存儲(chǔ)分配:編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元(地址空間),運(yùn)行時(shí)始終不變。,棧式動(dòng)態(tài)存儲(chǔ)分配:為每個(gè)過(guò)程建立活動(dòng)記錄,運(yùn)行時(shí)每當(dāng)調(diào)用一個(gè)過(guò)程,就將活動(dòng)記錄動(dòng)態(tài)的分配于棧
5、頂,過(guò)程活動(dòng)結(jié)束,則活動(dòng)記錄退出棧頂(釋放所占用的空間)。,堆式動(dòng)態(tài)存儲(chǔ)分配:運(yùn)行時(shí)將存儲(chǔ)空間組織成堆結(jié)構(gòu),以便用戶可以隨時(shí)申請(qǐng)或釋放存儲(chǔ)空間。,一個(gè)編譯系統(tǒng)采取怎樣的分配策略,取決于源語(yǔ)言中作用域及生命期的定義規(guī)則。如: FORTRAN不允許遞歸,故用靜態(tài)策略(以下不再敘述)。 Pascal和C,運(yùn)行時(shí)難以確定遞歸激活和遞歸深度,故用棧式堆式,9.3 簡(jiǎn)單的棧式存儲(chǔ)分配,以C語(yǔ)言為例,由于不允許嵌套定義過(guò)程,但允許過(guò)程遞歸調(diào)用,因此可采用簡(jiǎn)單的棧式存儲(chǔ)分配。,例有右邊的程序結(jié)構(gòu):,全局?jǐn)?shù)據(jù)說(shuō)明 Main( ) Main中的數(shù)據(jù)說(shuō)明 Q ; void R( ) R中的數(shù)據(jù)說(shuō)明 . void Q
6、( ) Q中的數(shù)據(jù)說(shuō)明 R;,當(dāng) Main調(diào)用了Q, Q又調(diào)用了R后,其存儲(chǔ)空間分配如下:,TOP:始終指向已占用的棧頂單元。進(jìn)入一個(gè)過(guò)程時(shí)指向該過(guò)程創(chuàng)建的活動(dòng)記錄的頂端,在分配數(shù)組之后,改指向數(shù)組區(qū)的頂端。,一. C 的活動(dòng)記錄,相當(dāng)于動(dòng)態(tài)鏈,SP: 總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn),用于局部數(shù)據(jù)的訪問(wèn);,對(duì)任何局部變量或形參的引用均可表示為:XSP, X表示變量的相對(duì)地址(編譯時(shí)可確定) 相對(duì)與活動(dòng)記錄的起始位置(SP)。 由于不允許嵌套,非局部變量的定義只能位于源程序的頭,并采用靜態(tài)分配。,二. C 的過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回,如前所述p200,過(guò)程調(diào)用的四元式序列如下: TOP總是指
7、向棧頂,而形式單元和SP間的距離是3,故:,par T1 par T2 par Tn call p, n,(i+3)TOP:=Ti (傳值) 或 (i+3)TOP:=addr (Ti) (傳地址),1TOP:=SP (保存現(xiàn)行的老sp) 3TOP:=n (傳送參數(shù)個(gè)數(shù)) JSR P (轉(zhuǎn)子 指令,轉(zhuǎn)向p 的第一條指令),1. 過(guò)程調(diào)用,2. 過(guò)程進(jìn)入,進(jìn)入過(guò)程后,應(yīng)執(zhí)行以下指令,為新活動(dòng)記錄賦初值,SP:=TOP+1 (定義新的SP) 1SP:=返回地址 (保護(hù)返回地址) TOP:=TOP+L (定義新的top,L為活動(dòng)記錄的單元 數(shù),可在編譯時(shí)靜態(tài)計(jì)算出來(lái)) 過(guò)程段執(zhí)行語(yǔ)句時(shí),對(duì)形式參數(shù)、局
8、部變量和數(shù)組的引用都是以SP為變址器進(jìn)行變址訪問(wèn)的。,3. 過(guò)程返回,對(duì)于以 return(E) 或 end 為結(jié)束返回的過(guò)程,應(yīng)執(zhí)行以下指令:,TOP:=SP-1 SP:=0SP X:=2TOP X為某一變 址器,返址 UJ 0X 無(wú)條件轉(zhuǎn)移,以 return(E)返回時(shí),還應(yīng)將表達(dá)式E的值計(jì)算出來(lái)并放于臨時(shí)變量T中通過(guò)特定的寄存器傳回。然后恢復(fù)SP和TOP到進(jìn)入過(guò)程前的舊值,無(wú)條件返回到原地址,如左:,9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn) Pascal允許過(guò)程嵌套即過(guò)程定義嵌套,在討論嵌套層次時(shí),假定主程序的嵌套層次為0。如圖,p258 圖9.15 概念:直接外層,直接內(nèi)層。層數(shù)將作為過(guò)程名的重
9、要屬性予以登記。 層數(shù)計(jì)算: proc Begin時(shí)1 Proc End時(shí)1 9.5.1非局部名字的訪問(wèn)實(shí)現(xiàn) 一、靜態(tài)鏈和活動(dòng)記錄 結(jié)構(gòu):,SP,TOP,為了在活動(dòng)記錄中查找非局部名字所對(duì)應(yīng)的存儲(chǔ)空間,當(dāng)前過(guò)程Q需要知道其所有外層過(guò)程的最新活動(dòng)記錄的地址,即跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄位置。 跟蹤方法:靜態(tài)鏈、顯示表。 1.靜態(tài)鏈:指向直接外層過(guò)程的最新活動(dòng)記錄,用于(允許)訪問(wèn)各外層的變量(非局部變量)。程序的每個(gè)過(guò)程的靜態(tài)結(jié)構(gòu)(嵌套層次)的確定的,故稱靜態(tài),如 (圖9.17 (b) 程序運(yùn)行時(shí)棧的變化如:P260圖9.17SP總是指向當(dāng)前活動(dòng)過(guò)程的活動(dòng)記錄的基地址。 動(dòng)態(tài)鏈,指向調(diào)用給過(guò)
10、程前正在運(yùn)行(活動(dòng))的過(guò)程的最新活動(dòng)記錄的基地址,即當(dāng)調(diào)用結(jié)束時(shí),可以由動(dòng)態(tài)鏈得到調(diào)用前的過(guò)程的活動(dòng)記錄的基地址。 靜態(tài)鏈指向其靜態(tài)直接外層的活動(dòng)記錄的基地址。,二、嵌套層次顯示表(display) 和活動(dòng)記錄 為了提高訪問(wèn)非局部變量的速度,動(dòng)態(tài)地組織一個(gè)嵌套層次顯示表(display)放入活動(dòng)記錄中。 display中存有本層及各外層的活動(dòng)記錄首地址。為了快速動(dòng)態(tài)生成display表,需將調(diào)用過(guò)程的display表地址(全局display)作為連接數(shù)據(jù)傳遞,因此,活動(dòng)記錄結(jié)構(gòu)改為右圖所示: Diplay表構(gòu)成了一個(gè)小的棧結(jié)構(gòu)。 p262(a),Display表的生成過(guò)程:由于過(guò)程的層數(shù)可以靜
11、態(tài)確定,故每個(gè)過(guò)程的display表的大小可以在編譯時(shí)靜態(tài)確定。,0層(主過(guò)程)的display僅含一項(xiàng):0層SP;,1層的display含兩項(xiàng): 0層的display+1層SP;,設(shè)過(guò)程p1調(diào)用p2,則p1與p2的靜態(tài)關(guān)系如右圖所示有(a), (b)兩種情況:,p1是p2的外層,由p1的display加上p2的SP即生成P2的display;,(b) p1與p2同層,且有共同的外層, 由p1 display表的前 i 項(xiàng)(p2為i層) 加上p2的SP即生成P2的display。,因此,非局部變量的絕對(duì)地址: 絕對(duì)地址diplay(靜態(tài)層數(shù))相對(duì)地址 Diplay表的相對(duì)地址:位于形式單元的上
12、方,而形式單元的數(shù)目是靜態(tài)的,故display表的相對(duì)地址也是靜態(tài)可確定的。 過(guò)程運(yùn)行時(shí)棧的display表的內(nèi)容變化過(guò)程,見(jiàn)p263,圖9.19 0層的diplay表:只含有主程序開(kāi)始工作時(shí)建立的SP值。 由此可見(jiàn),使用display表比使用靜態(tài)鏈效率要高。,9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)(PASCAL語(yǔ)言) 例:program p; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer;var v:integer); var c,d:integer; begin if u=1 then R
13、(u+1,v) v:=(a+c)*(b-d); . end R begin . R(1,x); . end Q procedure S; var c,i:integer; begin a=1;Q(c); .end S begin a=0;S; 過(guò)程調(diào)用時(shí)活動(dòng)記錄的變化 end 見(jiàn)p260,262,9.6 堆(heep)式動(dòng)態(tài)存儲(chǔ)分配,若源程序語(yǔ)言允許用戶自由地申請(qǐng)和退還數(shù)據(jù)空間(即不滿足lifo 原則),則應(yīng)用堆式存儲(chǔ)分配,其管理方式較為復(fù)雜,如圖9.21Pascal的建立new、釋放despose交替而改變堆的使用狀況。這里我們僅討論幾個(gè)主要問(wèn)題。 分配原則問(wèn)題:類似于磁盤空間的分配管理碎片問(wèn)題、廢空間回收問(wèn)題如何判斷廢空間?,一. 堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn),1. 定長(zhǎng)塊管理 存儲(chǔ)空間按一定長(zhǎng)度分成若干塊,組織成鏈表,由avaiable指示,以塊為單位進(jìn)行分配、回收。類似FAT表 有申請(qǐng)時(shí),從avaiable鏈表中取下若干塊分配。
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 高中蒙數(shù)學(xué)試卷
- 福州十九中一模數(shù)學(xué)試卷
- 肉牛生產(chǎn)技術(shù)課件
- 2025年廣東東莞市第六人民醫(yī)院招聘納入崗位管理編制外人員3人筆試歷年專業(yè)考點(diǎn)(難、易錯(cuò)點(diǎn))附帶答案詳解
- 2025年云南臨滄市臨翔區(qū)醫(yī)共體鄉(xiāng)村醫(yī)生招聘(5人)筆試歷年專業(yè)考點(diǎn)(難、易錯(cuò)點(diǎn))附帶答案詳解
- 2025年02月四川省臨床醫(yī)學(xué)研究中心(兒童腎病)專職科研人員招聘1人筆試歷年專業(yè)考點(diǎn)(難、易錯(cuò)點(diǎn))附帶答案詳解
- 中心靜脈狹窄介入治療課件
- 2025至2030財(cái)務(wù)管理系統(tǒng)行業(yè)市場(chǎng)深度研究與戰(zhàn)略咨詢分析報(bào)告
- 高中性價(jià)比高的數(shù)學(xué)試卷
- 碳排放權(quán)交易市場(chǎng)與能源效率提升的關(guān)聯(lián)性研究考核試卷
- JJG 169-2010互感器校驗(yàn)儀
- 建設(shè)工程監(jiān)理合同(住房和城鄉(xiāng)建設(shè)部2023)
- GB/T 28267.1-2021鋼絲繩芯輸送帶第1部分:普通用途輸送帶的設(shè)計(jì)、尺寸和機(jī)械要求
- 中醫(yī)內(nèi)科學(xué)癭病
- 品牌戰(zhàn)略定位課件
- 醫(yī)療技術(shù)分級(jí)授權(quán)與再授權(quán)申請(qǐng)表
- 項(xiàng)目管理九大過(guò)程英漢對(duì)照表
- 拖欠工資起訴狀模版
- 醫(yī)療技術(shù)臨床應(yīng)用管理信息系統(tǒng)操作手冊(cè)
- 北師大版小學(xué)數(shù)學(xué)四年級(jí)下冊(cè)《優(yōu)化》同步練習(xí)附答案
- 商業(yè)銀行風(fēng)險(xiǎn)預(yù)警系統(tǒng)整體架構(gòu)設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論