第9章運(yùn)行時(shí)的存儲(chǔ)組織SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點(diǎn)：符號(hào)表的內(nèi)容、組織，過(guò)程調(diào)用實(shí)現(xiàn)，靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配的基本方法。

難點(diǎn)：參數(shù)傳遞，過(guò)程說(shuō)明語(yǔ)句代碼結(jié)構(gòu)，過(guò)程調(diào)用語(yǔ)句的代碼結(jié)構(gòu)，過(guò)程調(diào)用語(yǔ)句的語(yǔ)法制導(dǎo)定義，棧式存儲(chǔ)分配。2023/1/122第9章

運(yùn)行時(shí)的存儲(chǔ)組織9.1與存儲(chǔ)組織有關(guān)的源語(yǔ)言概念與特征9.2存儲(chǔ)組織9.3靜態(tài)存儲(chǔ)分配9.4棧式存儲(chǔ)分配9.5棧中非局部數(shù)據(jù)的訪問(wèn)9.6堆管理9.7本章小結(jié)2023/1/1239.1與存儲(chǔ)組織有關(guān)的源語(yǔ)言概念與特征編譯程序必須準(zhǔn)確地實(shí)現(xiàn)包含在源程序中的各種抽象概念，如名字、作用域、數(shù)據(jù)類型、操作符、過(guò)程、參數(shù)和控制流結(jié)構(gòu)等，這些概念反映了源語(yǔ)言所具有的一些特征，對(duì)它們的支持往往會(huì)影響運(yùn)行時(shí)的存儲(chǔ)組織和分配策略給定一個(gè)源程序，編譯程序必須根據(jù)源語(yǔ)言的特征(規(guī)定)為源程序中的許多問(wèn)題做出決策，包括何時(shí)、怎樣為名字分配內(nèi)存地址。靜態(tài)策略：在編譯時(shí)即可做出決定的策略動(dòng)態(tài)策略：直到程序執(zhí)行時(shí)才能做出決定的策略2023/1/1249.1.1名字及其綁定“名字”、“變量”和“標(biāo)識(shí)符”的區(qū)別與聯(lián)系名字和變量分別表示編譯時(shí)的名字和運(yùn)行時(shí)該名字所代表的內(nèi)存位置。標(biāo)識(shí)符則是一個(gè)字符串，用于指示數(shù)據(jù)對(duì)象、過(guò)程、類或?qū)ο蟮娜肟?。所有?biāo)識(shí)符都是名字，但并不是所有的名字都是標(biāo)識(shí)符，名字還可以是表達(dá)式。例如，名字x.y可能表示x所代表結(jié)構(gòu)的域y。同一標(biāo)識(shí)符可以被聲明多次，但每個(gè)聲明都引入一個(gè)新的變量。即使每個(gè)標(biāo)識(shí)符只被聲明一次，局部于某個(gè)遞歸過(guò)程的標(biāo)識(shí)符在不同的運(yùn)行時(shí)刻也將指向不同的內(nèi)存位置。2023/1/125名字的綁定從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值賦值改變狀態(tài)，但不改變環(huán)境。

如果環(huán)境將名字x映射到存儲(chǔ)單元s，我們就說(shuō)x被綁定到s

名字內(nèi)存位置(變量)狀態(tài)值環(huán)境2023/1/1269.1.2聲明的作用域x的聲明的作用域是程序中的這樣一段區(qū)域，在該區(qū)域中，x的引用均指向x的這一聲明。對(duì)于某種程序設(shè)計(jì)語(yǔ)言，如果只通過(guò)考察其程序就可以確定某個(gè)聲明的作用域，則稱該語(yǔ)言使用靜態(tài)作用域；否則稱該語(yǔ)言使用動(dòng)態(tài)作用域。C++、Java和C#等還提供了對(duì)作用域的顯式控制，其方法是使用public、private和protected這樣的關(guān)鍵字。聲明的作用域是通過(guò)符號(hào)表進(jìn)行管理的，詳見(jiàn)8.4節(jié)的討論。2023/1/1271.靜態(tài)作用域在具有程序塊結(jié)構(gòu)的語(yǔ)言中，變量聲明的靜態(tài)作用域規(guī)則如下：如果名字x的聲明D屬于程序塊B，則D的作用域是B的所有語(yǔ)句，只有滿足如下條件的程序塊B‘除外：B’嵌套在B中(可以是任意的嵌套深度)，且B‘中具有同一名字x的一個(gè)新的聲明。令B1,B2,…,Bk是包圍x的本次引用的所有程序塊，Bk-1是Bk的直接外層程序塊，Bk-2是Bk-1的直接外層程序塊，如此類推。找到使x的某個(gè)聲明屬于Bi的最大i，則x的本次引用指向Bi中的這個(gè)聲明。換句話說(shuō)，x的本次引用處在Bi中的這個(gè)聲明的作用域中。2023/1/1281.靜態(tài)作用域表9.1圖8.10所示程序中聲明的作用域2023/1/1292.顯式訪問(wèn)控制類和結(jié)構(gòu)為其成員引入了一種新的作用域如果p是某個(gè)帶有域(成員)x的類的對(duì)象，則p.x中x的引用將指向該類定義中的域x。與程序塊結(jié)構(gòu)類似的是，類D中成員x的聲明的作用域?qū)?huì)擴(kuò)展到D的任何子類D'，除非D'中具有同一名字x的一個(gè)局部聲明。2023/1/12102.顯式訪問(wèn)控制通過(guò)使用像public、private和protected這樣的關(guān)鍵字，C++或Java類的面向?qū)ο笳Z(yǔ)言提供了一種對(duì)超類中成員名字的顯式訪問(wèn)控制。這些關(guān)鍵字通過(guò)限制訪問(wèn)來(lái)支持封裝。因此，私有名的作用域只包含與該類及其友類相關(guān)聯(lián)的方法聲明和定義，保護(hù)名只對(duì)其子類是可訪問(wèn)的，而公用名從類的外部也是可以訪問(wèn)的。2023/1/12113.動(dòng)態(tài)作用域動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間而靜態(tài)作用域規(guī)則相對(duì)于空間靜態(tài)作用域規(guī)則要求我們找出某個(gè)引用所指向的聲明，條件是該聲明處在包圍該引用的“空間上最近的”單元(程序塊)中。動(dòng)態(tài)作用域也是要求我們找出某個(gè)引用所指向的聲明，但條件是該聲明處在包圍該引用的“時(shí)間上最近的”單元(過(guò)程活動(dòng))中。2023/1/12123.動(dòng)態(tài)作用域“動(dòng)態(tài)作用域”通常是指下面的策略名字x的引用指向帶有x聲明的最近被調(diào)用的過(guò)程中x的這個(gè)聲明。例如，過(guò)程被當(dāng)做參數(shù)進(jìn)行傳遞時(shí)2023/1/12139.1.3過(guò)程及其活動(dòng)將“過(guò)程、函數(shù)和方法”統(tǒng)稱為“過(guò)程”過(guò)程定義是一個(gè)聲明，它的最簡(jiǎn)單形式是把一個(gè)標(biāo)識(shí)符和一個(gè)語(yǔ)句聯(lián)系起來(lái)。該標(biāo)識(shí)符是過(guò)程名，而這個(gè)語(yǔ)句是過(guò)程體。當(dāng)過(guò)程名出現(xiàn)在可執(zhí)行語(yǔ)句中時(shí)，稱相應(yīng)的過(guò)程在該點(diǎn)被調(diào)用。過(guò)程調(diào)用就是執(zhí)行被調(diào)用過(guò)程的過(guò)程體。注意，過(guò)程調(diào)用也可以出現(xiàn)在表達(dá)式中。2023/1/12149.1.3過(guò)程及其活動(dòng)出現(xiàn)在過(guò)程定義中的某些標(biāo)識(shí)符具有特殊的意義，稱為該過(guò)程的形式參數(shù)，簡(jiǎn)稱為形參。調(diào)用過(guò)程時(shí)，表達(dá)式作為實(shí)在參數(shù)(或?qū)崊?傳遞給被調(diào)用的過(guò)程，以替換出現(xiàn)在過(guò)程體中的對(duì)應(yīng)形式參數(shù)。9.1.4節(jié)將討論實(shí)參和形參的結(jié)合方法。過(guò)程體的每次執(zhí)行叫做該過(guò)程的一個(gè)活動(dòng)。過(guò)程p的一個(gè)活動(dòng)的生存期是從過(guò)程體執(zhí)行的第一步到最后一步，包括執(zhí)行被p調(diào)用的過(guò)程的時(shí)間，以及再由這樣的過(guò)程調(diào)用其它過(guò)程所花的時(shí)間，等等。

2023/1/12159.1.3過(guò)程及其活動(dòng)如果a和b是過(guò)程的活動(dòng)，那么它們的生存期或者不交迭，或者嵌套。也就是說(shuō)，如果在a結(jié)束之前b就開(kāi)始了，那么b必須在a結(jié)束之前結(jié)束。如果同一個(gè)過(guò)程的一次新的活動(dòng)可以在前一次活動(dòng)結(jié)束前開(kāi)始，則稱這樣的過(guò)程是遞歸的。遞歸過(guò)程p也可以間接地調(diào)用自己。如果某個(gè)過(guò)程是遞歸的，則在某一時(shí)刻可能有它的幾個(gè)活動(dòng)同時(shí)活躍，這時(shí)必須合理組織這些同時(shí)活躍著的活動(dòng)的內(nèi)存空間。2023/1/12169.1.4參數(shù)傳遞方式當(dāng)一個(gè)過(guò)程調(diào)用另一個(gè)過(guò)程時(shí)，它們之間交換信息的方法通常是通過(guò)非局部名字和被調(diào)用過(guò)程的參數(shù)來(lái)實(shí)現(xiàn)的。傳值傳地址傳值結(jié)果傳名其主要區(qū)別在于實(shí)參所代表的究竟是左值、右值還是實(shí)參的正文本身2023/1/12171.傳值計(jì)算實(shí)參并將其右值傳遞給被調(diào)用過(guò)程傳值方式可以如下實(shí)現(xiàn)：被調(diào)用過(guò)程為每個(gè)形參開(kāi)辟一個(gè)稱為形式單元的存儲(chǔ)單元，用于存放相應(yīng)實(shí)參的值。

調(diào)用過(guò)程計(jì)算實(shí)參，并把右值放入相應(yīng)的形式單元中。調(diào)用者被調(diào)用者直接使用A實(shí)際參數(shù)A形式參數(shù)XA的值單向傳值2023/1/12182.傳地址調(diào)用過(guò)程將實(shí)參的地址傳遞給被調(diào)用過(guò)程

傳地址方式可以如下實(shí)現(xiàn)：如果實(shí)參是一個(gè)具有左值的名字或表達(dá)式，則傳遞該左值本身如果實(shí)參是a+b或2這樣的沒(méi)有左值的表達(dá)式，則調(diào)用過(guò)程首先計(jì)算實(shí)參的值并將其存入一個(gè)新的存儲(chǔ)單元，然后將這個(gè)新單元的地址傳遞給被調(diào)用過(guò)程調(diào)用者被調(diào)用者間址訪問(wèn)A實(shí)際參數(shù)A形式參數(shù)XA的地址傳地址2023/1/12193.傳值結(jié)果傳值結(jié)果就是將傳值和傳地址這兩種方式結(jié)合起來(lái)傳值結(jié)果方式可以如下實(shí)現(xiàn)：

實(shí)參的右值和左值同時(shí)傳給被調(diào)用過(guò)程。 在被調(diào)用過(guò)程中，像傳值方式那樣使用實(shí)參的右值。 當(dāng)控制返回調(diào)用過(guò)程時(shí)，根據(jù)傳遞來(lái)的實(shí)參的左值，將形參當(dāng)前的值復(fù)制到實(shí)參存儲(chǔ)單元。調(diào)用者被調(diào)用者A實(shí)際參數(shù)A形式參數(shù)XA的值傳值/傳地址A的地址2023/1/12204.傳名用實(shí)參表達(dá)式對(duì)形參進(jìn)行文字替換。傳名方式可以如下實(shí)現(xiàn)：在調(diào)用過(guò)程中設(shè)置計(jì)算實(shí)參左值或右值的形實(shí)轉(zhuǎn)換子程序。被調(diào)用過(guò)程為每個(gè)形參開(kāi)辟一個(gè)存儲(chǔ)單元，用于存放該實(shí)參的形實(shí)轉(zhuǎn)換子程序的入口地址。被調(diào)過(guò)程執(zhí)行時(shí)，每當(dāng)要向形參賦值或取該形參的值時(shí)，就調(diào)用相應(yīng)于該形參的形實(shí)轉(zhuǎn)換子程序，以獲得相應(yīng)的實(shí)參地址或值。注意，形實(shí)轉(zhuǎn)換子程序的運(yùn)行環(huán)境是調(diào)用程序。形實(shí)轉(zhuǎn)換子程序又稱為換名子程序thunk。2023/1/1221例procedureswap(varx,y:integer);

vartemp:integer; begin 調(diào)用swap(i,a[i])

temp:=x;

temp:=i;

x:=y;

i:=a[i];

y:=temp

a[i]:=temp end2023/1/1222子程序P(X,Y,Z);{Y:=Y+1;Z:=Z+X}傳值：2傳地址：X=T=5,Y=Z=A=2A:=A+1=2+1A:=A+T=3+58傳值結(jié)果：X=T=5,Y=Z=A=2Y:=Y+1=3Z:=Z+X=5+2=7Y A=3Z A=77傳名A:=A+1=3A:=A+A+B=3+3+39主程序A:=2;B:=3;P(A+B,A,A);printA臨時(shí)單元:T:A+B=52023/1/1223編譯程序組織存儲(chǔ)空間時(shí)必須考慮的問(wèn)題過(guò)程能否遞歸？當(dāng)控制從過(guò)程的活動(dòng)返回時(shí)，局部變量的值是否要保留？過(guò)程能否訪問(wèn)非局部變量？過(guò)程調(diào)用的參數(shù)傳遞方式？過(guò)程能否作為參數(shù)被傳遞？過(guò)程能否作為結(jié)果值傳遞？存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配？存儲(chǔ)塊是否必須顯式地釋放？2023/1/12249.2存儲(chǔ)組織9.2.1運(yùn)行時(shí)內(nèi)存的劃分9.2.2活動(dòng)記錄9.2.3局部數(shù)據(jù)的組織9.2.4全局存儲(chǔ)分配策略2023/1/12257.2.1運(yùn)行時(shí)內(nèi)存的劃分目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆空閑空間2023/1/1226過(guò)程的每個(gè)活動(dòng)所需要的信息用一塊連續(xù)的存儲(chǔ)區(qū)來(lái)管理，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄

假定語(yǔ)言的特點(diǎn)為:允許過(guò)程遞歸調(diào)用、允許過(guò)程含有可變數(shù)組，過(guò)程定義允許/不允許嵌套。采用棧式存儲(chǔ)分配機(jī)制活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過(guò)程就有一個(gè)相應(yīng)的活動(dòng)記錄壓入棧頂。活動(dòng)記錄一般含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。9.2.2活動(dòng)記錄2023/1/1227對(duì)任何局部變量X的引用可表示為變址訪問(wèn):dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)變量數(shù)組內(nèi)情向量簡(jiǎn)單變量SP012舊SPTOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容

——非嵌套語(yǔ)言(如C)2023/1/1228

連接數(shù)據(jù)返回地址動(dòng)態(tài)鏈：指向調(diào)用該過(guò)程前的最新活動(dòng)記錄地址的指針。靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來(lái)訪問(wèn)非局部數(shù)據(jù)。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)變量數(shù)組內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容

——嵌套語(yǔ)言(如Pascal)2023/1/1229形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元(如存放對(duì)表達(dá)式求值的結(jié)果)。靜態(tài)鏈動(dòng)態(tài)鏈形式單元臨時(shí)變量數(shù)組內(nèi)情向量局部變量SP012返回地址TOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容2023/1/12309.2.3局部數(shù)據(jù)的組織字節(jié)是可編址內(nèi)存的最小單位。變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。一個(gè)過(guò)程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來(lái)表示。數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有對(duì)齊的問(wèn)題。整數(shù)必須放在內(nèi)存中特定的位置，如被2、4、8整除 的地址2023/1/12319.2.3局部數(shù)據(jù)的組織在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef

struct_a{ typedef

struct_b{ char c1; charc1; long i; char c2; char c2; longi; doublef; doublef;}a; }b;2023/1/12329.2.3局部數(shù)據(jù)的組織在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef

struct_a{ typedef

struct_b{ char c1; 0 charc1; 0 long i; 4 char c2;1 char c2; 8 longi;4 doublef; 16 doublef;8}a; }b;2023/1/12339.2.3局部數(shù)據(jù)的組織在X86/Linux機(jī)器的結(jié)果和SPARC/Solaris工作站不一樣，是20和16。typedef

struct_a{ typedef

struct_b{ char c1; 0 charc1; 0 long i; 4 char c2;1 char c2; 8 longi;4 doublef; 12 doublef;8}a; }b;2023/1/1234靜態(tài)存儲(chǔ)分配策略(FORTRAN)

如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲(chǔ)空間中的位置。動(dòng)態(tài)存儲(chǔ)分配策略(PASCAL)

如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動(dòng)態(tài)分配方法。允許遞歸過(guò)程及動(dòng)態(tài)申請(qǐng)、釋放內(nèi)存。棧式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配9.2.4全局存儲(chǔ)分配策略

2023/1/12359.3靜態(tài)存儲(chǔ)分配策略如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址，存儲(chǔ)空間的這種分配方法稱為靜態(tài)存儲(chǔ)分配。必須滿足如下條件：數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置在編譯時(shí)必須是已知的；不允許過(guò)程的遞歸調(diào)用，因?yàn)橐粋€(gè)過(guò)程的所有活動(dòng)都是用同樣的局部名字綁定的；數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆](méi)有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。2023/1/1236某分段式程序運(yùn)行時(shí)的內(nèi)存劃分2023/1/1237每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該區(qū)中的相對(duì)位置。考慮子程序段：SUBROUTINESWAP(A,B)T=AA=BB=TRETURNEND寄存器保護(hù)區(qū)返回地址ATB01a2023/1/1238靜態(tài)存儲(chǔ)分配策略順序分配算法（基于調(diào)用圖）按照程序段出現(xiàn)的先后順序逐段分配1/222/153/184/176/105/23程序段區(qū)域

0~2122~3637~5455~7172~9495~104共需要105個(gè)存儲(chǔ)單元程序段號(hào)/所需數(shù)據(jù)空間能用更少的空間么？2023/1/1239分層分配算法允許程序段之間的覆蓋（覆蓋可能性分析）程序段 區(qū)域6 0~95 0~224 0~163 23~402 17~311 41~62共需要63個(gè)存儲(chǔ)單元1/222/153/184/176/105/23思考：如何設(shè)計(jì)分配算法？7/802023/1/12409.4棧式存儲(chǔ)分配策略如果過(guò)程允許遞歸某一時(shí)刻過(guò)程A可能已被自己調(diào)用了若干次，但只有最近一次處于執(zhí)行狀態(tài)。其余各次等待返回被中斷的那次調(diào)用必須保存每次調(diào)用相應(yīng)的數(shù)據(jù)區(qū)內(nèi)容（活動(dòng)記錄）引入一個(gè)運(yùn)行棧讓過(guò)程的每次執(zhí)行和過(guò)程的活動(dòng)記錄相對(duì)應(yīng)。每調(diào)用一次過(guò)程，就把該過(guò)程的活動(dòng)記錄壓入棧中，返回時(shí)彈出。假設(shè)寄存器top標(biāo)記棧頂，局部名字x的相對(duì)地址為dx，則x的地址為top+dx

或dx[top]2023/1/12419.4.1調(diào)用序列和返回序列

過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過(guò)程調(diào)用和返回是通過(guò)在目標(biāo)代碼中生成調(diào)用序列和返回序列來(lái)實(shí)現(xiàn)的

調(diào)用序列負(fù)責(zé)分配活動(dòng)記錄，并將相關(guān)信息填入活動(dòng)記錄中返回序列負(fù)責(zé)恢復(fù)機(jī)器狀態(tài)，使調(diào)用過(guò)程能夠繼續(xù)執(zhí)行調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過(guò)程和被調(diào)用過(guò)程中2023/1/12429.4.1調(diào)用序列和返回序列即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則：以活動(dòng)記錄中間的某個(gè)位置作為基地址；長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間；一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面，以便其長(zhǎng)度的改變不會(huì)影響數(shù)據(jù)對(duì)象相對(duì)于中間那些域的位置；用同樣的代碼來(lái)執(zhí)行各個(gè)活動(dòng)的狀態(tài)保存和恢復(fù)；把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)記錄的地方。2023/1/12439.4.1調(diào)用序列和返回序列調(diào)用者和被調(diào)用者之間的任務(wù)劃分2023/1/12449.4.1調(diào)用序列和返回序列一種可能的調(diào)用序列：調(diào)用者計(jì)算實(shí)參調(diào)用者把返回地址和sp的舊值存入被調(diào)用者的活動(dòng)記錄中，然后將sp移過(guò)調(diào)用者的局部數(shù)據(jù)域和臨時(shí)變量域，以及被調(diào)用者的參數(shù)域和狀態(tài)域被調(diào)用者保存寄存器值和其它機(jī)器狀態(tài)信息被調(diào)用者初始化其局部數(shù)據(jù)，并開(kāi)始執(zhí)行。2023/1/12459.4.1調(diào)用序列和返回序列一種可能的返回序列：

被調(diào)用者將返回值放入臨近調(diào)用者的活動(dòng)記錄的地方。利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)sp和其它寄存器，并且按調(diào)用者代碼中的返回地址返回。盡管sp的值減小了，調(diào)用者仍然可以將返回值復(fù)制到自己的活動(dòng)記錄中，并用它來(lái)計(jì)算一個(gè)表達(dá)式。2023/1/12469.4.1調(diào)用序列和返回序列過(guò)程的參數(shù)個(gè)數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等如C語(yǔ)言的printf2023/1/1247過(guò)程調(diào)用的三地址碼: param

x1 param

x2 … param

xn callp，n9.4.2C語(yǔ)言的過(guò)程調(diào)用和返回

2023/1/12481)每個(gè)param

xi(i=1,2,…n)可直接翻譯成如下指令: (i+3)[top]:=xi

(傳值) (i+3)[top]:=addr(xi)

(傳地址)2)callp，n被翻譯成如下指令:1[top]:=sp(保護(hù)現(xiàn)行sp)3[top]:=n(傳遞參數(shù)個(gè)數(shù))JSRp(轉(zhuǎn)子指令)參數(shù)個(gè)數(shù)返回地址內(nèi)情向量局部變量老sp臨時(shí)單元對(duì)于par和call產(chǎn)生的目標(biāo)代碼top

sp調(diào)用過(guò)程的活動(dòng)記錄老sp參數(shù)個(gè)數(shù)形式單元形式單元2023/1/12493)進(jìn)入過(guò)程p后，首先應(yīng)執(zhí)行下述指令:

sp:=top+1

(定義新的sp) 1[sp]:=返回地址

(保護(hù)返回地址)

top:=top+L

(新top)

L：過(guò)程P的活動(dòng)記錄所需單元數(shù)，

在編譯時(shí)可確定。

參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老sp臨時(shí)單元TOP調(diào)用過(guò)程的活動(dòng)記錄返回地址topsp2023/1/12504)過(guò)程返回時(shí)，應(yīng)執(zhí)行下列指令:

top:=sp-1 (恢復(fù)調(diào)用前top)

sp:=0[sp] (恢復(fù)調(diào)用前SP) X:=2[top] (把返回地址取到X中) UJ0[X] (按X返回)

UJ為無(wú)條件轉(zhuǎn)移指令，即按X中的返回地址實(shí)行變址轉(zhuǎn)移參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老sp臨時(shí)單元調(diào)用過(guò)程的活動(dòng)記錄topspsptop2023/1/12519.4.3棧中的可變長(zhǎng)數(shù)據(jù)活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況局部數(shù)組的大小要等到過(guò)程激活時(shí)才能確定在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間2023/1/12529.4.3棧中的可變長(zhǎng)數(shù)據(jù)圖9.13訪問(wèn)動(dòng)態(tài)分配的數(shù)組2023/1/1253棧式存儲(chǔ)分配策略的局限棧式分配策略在下列情況下行不通：過(guò)程活動(dòng)停止后，局部名字的值還必須維持被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期更長(zhǎng)，此時(shí)活動(dòng)樹(shù)不能正確描繪程序的控制流不遵守棧式規(guī)則的有Pascal語(yǔ)言和C語(yǔ)言的動(dòng)態(tài)變量Java禁止程序員自己釋放空間2023/1/12549.5棧中非局部數(shù)據(jù)的訪問(wèn)本節(jié)內(nèi)容無(wú)嵌套過(guò)程的靜態(tài)作用域的實(shí)現(xiàn)（C語(yǔ)言）包含嵌套過(guò)程的靜態(tài)作用域的實(shí)現(xiàn)（Pascal語(yǔ)言）動(dòng)態(tài)作用域的實(shí)現(xiàn)（Lisp語(yǔ)言）2023/1/12559.5.1無(wú)過(guò)程嵌套的靜態(tài)作用域假定:允許過(guò)程遞歸調(diào)用、允許過(guò)程含有可變數(shù)組，但過(guò)程定義不允許嵌套，如C語(yǔ)言。過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)sp指針來(lái)訪問(wèn)無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈過(guò)程可以作為參數(shù)來(lái)傳遞，也可以作為結(jié)果來(lái)返回

C語(yǔ)言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問(wèn)的數(shù)據(jù)分成兩種情況:非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)9.5.1無(wú)過(guò)程嵌套的靜態(tài)作用域2023/1/12562023/1/1257

全局?jǐn)?shù)據(jù)說(shuō)明main(){ main中的數(shù)據(jù)說(shuō)明}voidR(){ R中的數(shù)據(jù)說(shuō)明}…voidQ(){Q中的數(shù)據(jù)說(shuō)明}主程序→過(guò)程Q→過(guò)程RQ的活動(dòng)記錄主程序活動(dòng)記錄TOPR的活動(dòng)記錄SP參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元全局?jǐn)?shù)據(jù)區(qū)2023/1/12589.5.2有過(guò)程嵌套的靜態(tài)作用域假定語(yǔ)言不僅允許過(guò)程的遞歸調(diào)用(和可變數(shù)組)，而且允許過(guò)程定義的嵌套，如PASCAL，PL語(yǔ)言。sort

readarray

exchange

quicksort

partition 2023/1/1259（1）programsort(input,output)（2）vara:array[0..10]ofinteger;（3）procedurereadarray;（4）vari:integer;（5）begin（6）fori:=1to9doread(a[i])（7）end;（8）functionpartition(y,z:integer):integer;（9）var

i:integer;（10）begin......（11）end;programsortprocedurereadarray

functionpartition(yprocedurequicksort2023/1/1260（12）procedurequicksort(m,n:integer);（13）var

i:integer;（14）begin（15）if(n>m)thenbegin（16）i:=partition(m,n);（17）

quicksort(m,i-1);（18）quicksort(i+1,n)（19）end;（20）end;（21）begin（22）a[0]:=-9999;a[10]:=9999;（23）readarray;（24）quicksort(1,9)（25）gramsortprocedurereadarray

functionpartition(yprocedurequicksort2023/1/12619.5.2有過(guò)程嵌套的靜態(tài)作用域引入概念：過(guò)程嵌套深度sort 1

readarray 2 exchange 2

quicksort 2 partition 3變量的嵌套深度：它的聲明所在過(guò)程的嵌套深度作為該名字的嵌套深度2023/1/12629.5.2有過(guò)程嵌套的靜態(tài)作用域1.訪問(wèn)鏈

2023/1/12639.5.2有過(guò)程嵌套的靜態(tài)作用域假定過(guò)程p的嵌套深度為np，它引用嵌套深度為na的變量a，na

np。如何訪問(wèn)a的存儲(chǔ)單元？從棧頂?shù)幕顒?dòng)記錄開(kāi)始,追蹤訪問(wèn)鏈np-na次。到達(dá)a的聲明所在過(guò)程的活動(dòng)記錄。訪問(wèn)鏈的追蹤用間接操作就可完成。2023/1/12649.5.2有過(guò)程嵌套的靜態(tài)作用域過(guò)程p對(duì)變量a訪問(wèn)時(shí)，a的地址由下面的二元組表示：（np

na，a在活動(dòng)記錄中的偏移）2023/1/12659.5.2有過(guò)程嵌套的靜態(tài)作用域如何建立訪問(wèn)鏈假定嵌套深度為np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程xnp

<nx的情況x必須在p中進(jìn)行定義，否則它對(duì)于p來(lái)說(shuō)就是不可訪問(wèn)的被調(diào)用過(guò)程的訪問(wèn)鏈必須指向調(diào)用過(guò)程的活動(dòng)記錄的訪問(wèn)鏈2023/1/12669.5.2有過(guò)程嵌套的靜態(tài)作用域如何建立訪問(wèn)鏈假定嵌套深度為np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程xnp

nx的情況p和x的嵌套深度分別為1，2，…，nx1的外圍過(guò)程肯定相同追蹤訪問(wèn)鏈np

nx

+1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過(guò)程的最新活動(dòng)記錄所到達(dá)的訪問(wèn)鏈就是x的活動(dòng)記錄中的訪問(wèn)鏈應(yīng)該指向的那個(gè)訪問(wèn)鏈2023/1/12679.5.2有過(guò)程嵌套的靜態(tài)作用域2.過(guò)程型參數(shù)的訪問(wèn)鏈programparam(input,output);

procedureb(function

h(n:integer):integer); beginwriteln(h(2))end;

procedurec;

varm:integer;

functionf(n:integer):integer; beginf:=m+nend{f};

beginm:=0;b(f)end{c};begin c end.過(guò)程作為參數(shù)傳遞時(shí)，怎樣在該過(guò)程被激活時(shí)建立它的訪問(wèn)鏈從b的訪問(wèn)鏈難以建立f的訪問(wèn)鏈激活fc傳遞參數(shù)f時(shí)，像調(diào)用f一樣為f建立一個(gè)訪問(wèn)鏈，該訪問(wèn)鏈同f一起傳遞給b。f被激活時(shí)用這個(gè)訪問(wèn)鏈建立f的活動(dòng)記錄的訪問(wèn)鏈2023/1/12689.5.2有過(guò)程嵌套的靜態(tài)作用域programparam(input,output);（過(guò)程作為參數(shù)）

procedureb(functionh(… beginwriteln(h(2))end;

procedurec;

varm:integer;

functionf(n:integer)… beginf:=m+nend{f};

beginm:=0;b(f)end{c};begin c end.2023/1/12699.5.2有過(guò)程嵌套的靜態(tài)作用域programret(input,output);（過(guò)程作為返回值）

varf:function(integer):integer;

functiona:function(integer):integer;

var

m:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.retabaddm被調(diào)過(guò)程addm活動(dòng)的生存期超出了調(diào)用過(guò)程a活動(dòng)的生存期棧式存儲(chǔ)分配策略失效！！活動(dòng)樹(shù)2023/1/12703.Display表

Display表是一個(gè)指針數(shù)組d，在運(yùn)行過(guò)程中，若當(dāng)前活動(dòng)的過(guò)程的嵌套深度為i，則d[i]中存放當(dāng)前的活動(dòng)記錄地址，d[i-1],d[i-2],…,d[1]中依次存放著當(dāng)前活動(dòng)的過(guò)程的直接外層，…,

直至最外層（主程序）等每一層過(guò)程的最新活動(dòng)地址。 這樣，嵌套深度為j的變量a存放在由d[j]所指出的活動(dòng)記錄中。 在運(yùn)行過(guò)程中維持一個(gè)Display表實(shí)現(xiàn)非局部訪問(wèn)比存取鏈效率要高。9.5.2有過(guò)程嵌套的靜態(tài)作用域2023/1/1271Display表的維護(hù)（過(guò)程不作為參數(shù)傳遞）當(dāng)嵌套深度為i的過(guò)程的活動(dòng)記錄壓在棧頂時(shí)：

(1)在新的活動(dòng)記錄中保存d[i]的值；

(2)置d[i]指向新的活動(dòng)記錄。在一個(gè)活動(dòng)結(jié)束前，d[i]置成保存的舊值。用Display表如何訪問(wèn)非局部量？

1.Display表是一個(gè)數(shù)組，開(kāi)始地址用通用寄存器指出；

2.Display表由一組寄存器實(shí)現(xiàn)。9.5.2有過(guò)程嵌套的靜態(tài)作用域2023/1/1272一個(gè)例子programP;vara,x:integer;procedureQ(b:integer);

vari:integer; procedureR(u:integer;varv:integer);

varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS;

varc,i:integer; begin a:=1;

Q(c); ...... end{S}begin a:=0; S; ......end.{P}主程序P過(guò)程

S過(guò)程

Q過(guò)程

R過(guò)程

R2023/1/1273一、通過(guò)靜態(tài)鏈訪問(wèn)非局部數(shù)據(jù)靜態(tài)鏈：指向本過(guò)程的直接外層過(guò)程的活動(dòng)記錄的起始地址，也稱訪問(wèn)鏈。動(dòng)態(tài)鏈：指向本過(guò)程的調(diào)用過(guò)程的活動(dòng)記錄的起始地址，也稱控制鏈。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012動(dòng)態(tài)鏈(老SP)TOP靜態(tài)鏈2023/1/12740002a3x4SPTOP主程序P1返回地址2023/1/1275002a3x405070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過(guò)程

S問(wèn)：第N層過(guò)程調(diào)用第N+1層過(guò)程，如何確定被調(diào)用過(guò)程(第N+1層)的靜態(tài)鏈？答：調(diào)用過(guò)程(第N層過(guò)程)的最新活動(dòng)記錄的起始地址.01返回地址6返回地址2023/1/12760002a3x4056070(形參個(gè)數(shù))8c9i10SPTOP動(dòng)態(tài)鏈靜態(tài)鏈主程序P過(guò)程

S

過(guò)程

Q5110131(形參個(gè)數(shù))14b(形參)15i16問(wèn)：第N層過(guò)程調(diào)用第N層過(guò)程，如何確定被調(diào)用過(guò)程(第N層)的靜態(tài)鏈？答：調(diào)用過(guò)程(第N層過(guò)程)的靜態(tài)鏈的值。返回地址12返回地址1返回地址2023/1/127700102a3x4056070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過(guò)程

S

過(guò)程

Q

過(guò)程

R511120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24SPTOP返回地址返回地址返回地址2023/1/127800102a3x4056070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過(guò)程

S

過(guò)程

Q

過(guò)程

R

過(guò)程

R511120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d241725返回地址2611272(形參個(gè)數(shù))28u(形參)29v(形參)30c31d32TOPSP返回地址返回地址返回地址2023/1/127900返回地址102a3x405返回地址6070(形參個(gè)數(shù))8c9i10動(dòng)態(tài)鏈靜態(tài)鏈主程序P過(guò)程

S

過(guò)程

Q

過(guò)程

R

過(guò)程

Q511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192(形參個(gè)數(shù))20u(形參)21v(形參)22c23d24TOPSP1725返回地址260271(形參個(gè)數(shù))28b(形參)29i30問(wèn)：第N層過(guò)程調(diào)用第N-x層過(guò)程，如何確定被調(diào)用過(guò)程(第N-x層)過(guò)程的靜態(tài)鏈？答:沿著調(diào)用過(guò)程(第N層過(guò)程)的靜態(tài)鏈向前走x步到達(dá)的活動(dòng)記錄的靜態(tài)鏈的值。2023/1/1280二、通過(guò)Display表

訪問(wèn)非局部數(shù)據(jù)SPn為第n層過(guò)程數(shù)據(jù)區(qū)首址9.5.2有過(guò)程嵌套的靜態(tài)作用域SPnSPn-1……SP1SP0數(shù)組存儲(chǔ)區(qū)本過(guò)程……所轄分第臨時(shí)工作單元程一序?qū)泳植繑?shù)組說(shuō)明存分儲(chǔ)程局部變量區(qū)序分程序TOP本過(guò)程Display形式單元（m+1個(gè)）連主調(diào)分程序TOP接全局Display地址數(shù)返回地址據(jù)主調(diào)過(guò)程SP本過(guò)程TOPSP2023/1/1281令過(guò)程R的外層為Q，Q的外層為主程序P，則過(guò)程R運(yùn)行時(shí)的DISPLAY表內(nèi)容為：2023/1/1282問(wèn)題：當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P0P2P1P0P1P22023/1/1283問(wèn)題：當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2l2:P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址l2:

P2的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過(guò)l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。2023/1/1284問(wèn)題：當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P2P1l2-1:

P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址P1的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過(guò)l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址2023/1/1285問(wèn)題：當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？P0P1P2P1的最新活動(dòng)記錄的起始地址P0的最新活動(dòng)記錄的起始地址P1的display表P0的最新活動(dòng)記錄的起始地址…………P2的display表從P1的display表中自底而上地取過(guò)l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。l2:

P2的最新活動(dòng)記錄的起始地址l2:P2的最新活動(dòng)記錄的起始地址2023/1/1286問(wèn)題：當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？答案：從P1的display表中自底而上地取過(guò)l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。把P1的display表地址作為連接數(shù)據(jù)之一(稱為全局display地址)傳送給P2就能夠建立P2的display表。P0P1P2P0P2P1P0P1P22023/1/1287diaplay表在活動(dòng)記錄中的相對(duì)地址d在編譯時(shí)能完全確定。假定在現(xiàn)行過(guò)程中引用了某層過(guò)程(令其層次為k)的X變量，那么，可用下面兩條指令獲得X的地址:LDR1(d+k)[SP]LDR2dx[R1]嵌套過(guò)程語(yǔ)言活動(dòng)記錄參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量SP012老SPTOPDisplay表全局Display3d…2023/1/1288一個(gè)例子programP;vara,x:integer;procedureQ(b:integer);

vari:integer; procedureR(u:integer;varv:integer);

varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS;

varc,i:integer; begin a:=1;

Q(c); ...... end{S}begin a:=0; S; ......end.{P}主程序P過(guò)程

S過(guò)程

Q過(guò)程

R過(guò)程

R2023/1/128900返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序過(guò)程

Sc11i12TOPSP動(dòng)態(tài)鏈2023/1/129000返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過(guò)程

S

過(guò)程

Qc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i20TOPSP2023/1/129100返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過(guò)程

S

過(guò)程

Q

過(guò)程

Rc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個(gè)數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP2023/1/129200返回地址10(display)2a3x405返回地址62(全局display)70(形參個(gè)數(shù))809510主程序P過(guò)程

S

過(guò)程

Q

過(guò)程

R

過(guò)程

Rc11i12動(dòng)態(tài)鏈513返回地址149(全局display)151(形參個(gè)數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個(gè)數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP2132返回地址3327(全局display)342(形參個(gè)數(shù))35u(形參)36v(形參)3703813393240c41d422023/1/1293過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回每個(gè)parTi(i=1,2,…n)可直接翻譯成如下指令: (i+4)[TOP]:=Ti

(傳值)(i+4)[TOP]:=addr(Ti)(傳地址)參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局DisplayTOPSP調(diào)用過(guò)程的活動(dòng)記錄……形式單元2023/1/1294參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局Display2.callP，n被翻譯成:1[TOP]:=SP(保護(hù)現(xiàn)行SP)3[TOP]:=SP+d(傳送現(xiàn)行display地址)4[TOP]:=n(傳遞參數(shù)個(gè)數(shù))JSR(轉(zhuǎn)子指令)過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回TOPSP調(diào)用過(guò)程的活動(dòng)記錄……老SP全局Display參數(shù)個(gè)數(shù)2023/1/12953.轉(zhuǎn)進(jìn)過(guò)程P后，首先定義新的SP和TOP，保存返回地址。4.根據(jù)"全局display"建立現(xiàn)行過(guò)程的display：從全局display表中自底向上地取l個(gè)單元，在添上進(jìn)入P后新建立的SP值就構(gòu)成了P的display。參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局DisplayTOPSP調(diào)用過(guò)程的活動(dòng)記錄……返回地址Display表過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回2023/1/12965.過(guò)程返回時(shí)，執(zhí)行下述指令: TOP:=SP-1 SP:=0[SP] X:=2[TOP] UJ0[X]參數(shù)個(gè)數(shù)返回地址形式單元臨時(shí)單元內(nèi)情向量局部變量老SPDisplay表全局DisplayTOPSP調(diào)用過(guò)程的活動(dòng)記錄……TOPSP過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回2023/1/12979.5.3動(dòng)態(tài)作用域的實(shí)現(xiàn)

從技術(shù)上講，如果作用域策略需要基于程序運(yùn)行時(shí)才能知道的因素，則任何作用域策略都將是動(dòng)態(tài)的。但“動(dòng)態(tài)作用域”這個(gè)術(shù)語(yǔ)通常是指下面的策略：名字x的引用指向帶有x聲明的最近被調(diào)用的過(guò)程中x的這個(gè)聲明。在某種意義上說(shuō)，動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間，而靜態(tài)作用域規(guī)則相對(duì)于空間。2023/1/12989.5.3動(dòng)態(tài)作用域

程序運(yùn)行時(shí)，一個(gè)名字a實(shí)施其影響，直到含a的聲明的一個(gè)過(guò)程開(kāi)始執(zhí)行時(shí)暫停，此過(guò)程停止時(shí)，該影響恢復(fù)。設(shè)有下面的的調(diào)用序列：

ABCP

過(guò)程P中有對(duì)x的非局部引用，沿動(dòng)態(tài)鏈（紅鏈）查找，最先找到的便是。2023/1/12999.5.3動(dòng)態(tài)作用域programdynamic(input,output);

varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;

varr:real;beginr:=0.125;showend;begin 靜態(tài)作用域

r:=0.25; 0.250 0.250

show;small;writeln; 0.250 0.250

show;small;writelnend.dynamicshowsmallsmallshowshowshow2023/1/121009.5.3動(dòng)態(tài)作用域programdynamic(input,output);

varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;

varr:real;beginr:=0.125;showend;begin 動(dòng)態(tài)作用域

r:=0.25; 0.250 0.125show;small;writeln; 0.250 0.125show;small;writelnend.dynamicshowsmallsmallshowshowshow2023/1/121019.5.3動(dòng)態(tài)作用域?qū)崿F(xiàn)動(dòng)態(tài)作用域的方法深訪問(wèn)(訪問(wèn)非局部名字時(shí)的開(kāi)銷大,易于實(shí)現(xiàn)過(guò)程類參數(shù))

用控制鏈搜索運(yùn)行棧，尋找包含該非局部名字的第一個(gè)活動(dòng)記錄淺訪問(wèn)(活動(dòng)開(kāi)始和結(jié)束時(shí)的開(kāi)銷大)將每個(gè)名字的當(dāng)前值保存在靜態(tài)分配的內(nèi)存空間中當(dāng)過(guò)程p開(kāi)始一個(gè)新的活動(dòng)時(shí)，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的內(nèi)存單元。n的先前值必須保存在p的活動(dòng)記錄中，當(dāng)p的活動(dòng)結(jié)束時(shí)再恢復(fù)2023/1/121029.6堆管理對(duì)于允許程序?yàn)樽兞吭谶\(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)和釋放存儲(chǔ)空間的語(yǔ)言,采用堆式分配是最有效的解決方案.活動(dòng)結(jié)束時(shí)必須保持局部名字的值。被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期長(zhǎng)。堆式分配的基本思想是,為運(yùn)行的程序劃出適當(dāng)大的空間(稱為堆Heap),每當(dāng)程序申請(qǐng)空間時(shí),就從堆的空閑區(qū)找出一塊空間分配給程序,每當(dāng)釋放時(shí)則回收之.內(nèi)存管理器分配和回收堆區(qū)空間的子系統(tǒng)是應(yīng)用程序和操作系統(tǒng)之間的一個(gè)接口2023/1/121039.6.1內(nèi)存管理器內(nèi)存管理器的基本任務(wù)空間分配。每當(dāng)程序?yàn)槟硞€(gè)變量或?qū)ο笊暾?qǐng)一塊內(nèi)存空間時(shí)，內(nèi)存管理器就產(chǎn)生一塊連續(xù)的具有被請(qǐng)求大小的堆空間?？臻g回收。內(nèi)存管理器把回收的空間返還到空閑空間的緩沖池中，用于滿足其它的分配請(qǐng)求。2023/1/121049.6.1內(nèi)存管理器如果下面兩個(gè)條件成立的話，內(nèi)存管理將會(huì)變得相對(duì)簡(jiǎn)單一些所有的分配請(qǐng)求都要求相同大小的塊；存儲(chǔ)空間按照某種可以預(yù)見(jiàn)的方式來(lái)釋放，如先分配者先釋放。2023/1/121059.6.1內(nèi)存管理器內(nèi)存管理器的設(shè)計(jì)目標(biāo)空間效率。內(nèi)存管理器應(yīng)該使程序所需堆區(qū)空間的總量達(dá)到最小，以便在某個(gè)固定大小的虛擬地址空間中運(yùn)行更大的程序。方法：減少內(nèi)存碎片的數(shù)量。程序效率。內(nèi)存管理器應(yīng)該充分利用內(nèi)存子系統(tǒng)，以便使程序運(yùn)行得更快。方法：利用程序的“局部性”，即程序在訪問(wèn)內(nèi)存時(shí)具有非隨機(jī)性聚集的特性。低開(kāi)銷。由于存儲(chǔ)分配和回收在很多程序中都是常用的操作，所以內(nèi)存管理器應(yīng)該盡可能地提高這些操作的執(zhí)行效率，也就是說(shuō)要盡可能地降低它們的開(kāi)銷。2023/1/121069.6.2內(nèi)存體系要想做好內(nèi)存管理和編譯器優(yōu)化，首先要充分了解內(nèi)存的工作機(jī)理。內(nèi)存訪問(wèn)時(shí)間的巨大差異來(lái)源于硬件技術(shù)的局限。圖9.21典型的內(nèi)存體系2023/1/121079.6.3程序中的局部性程序的局部性程序中的大部分運(yùn)行時(shí)間都花費(fèi)在較少的一部分代碼中，而且只是涉及到一小部分?jǐn)?shù)據(jù)。時(shí)間局部性：如果某個(gè)程序訪問(wèn)的內(nèi)存位置有可能在很短的時(shí)間內(nèi)被再次訪問(wèn)空間局部性：如果被訪問(wèn)過(guò)的內(nèi)存位置的鄰近位置有可能在很短的時(shí)間內(nèi)被再次訪問(wèn)2023/1/121089.6.3程序中的局部性程序的局部性使得我們可以充分利用圖9.21所示的內(nèi)存層次結(jié)構(gòu)，即將最常用的指令和數(shù)據(jù)放在快而小的內(nèi)存中，而將其余部分放在慢而大的內(nèi)存中，這將顯著降低程序的平均內(nèi)存訪問(wèn)時(shí)間很多程序在對(duì)指令和數(shù)據(jù)的訪問(wèn)方式上既表現(xiàn)出時(shí)間局部性，又表現(xiàn)出空間局部性2023/1/121099.6.3程序中的局部性雖然將最近使用過(guò)的數(shù)據(jù)放在最快的內(nèi)存層中在普通程序中可以發(fā)揮很好的作用，但是在某些數(shù)據(jù)密集型的程序中的作用卻并不明顯，如循環(huán)遍歷大數(shù)組的程序。將最近使用過(guò)的指令放在高速緩存中的策略一般都很有效。2023/1/121109.6.3程序中的局部性空間局部性：讓編譯器將可能會(huì)連續(xù)執(zhí)行的指令連續(xù)存放執(zhí)行一條新指令時(shí)，其下一條指令也很有可能被執(zhí)行屬于同一個(gè)循環(huán)或同一個(gè)函數(shù)的指令也極可能被一起執(zhí)行2023/1/121119.6.3程序中的局部性通過(guò)改變數(shù)據(jù)布局或計(jì)算順序也可以改進(jìn)程序中數(shù)據(jù)訪問(wèn)的時(shí)間局部性和空間局部性例如，當(dāng)某些程序反復(fù)訪問(wèn)大量數(shù)據(jù)而每次訪問(wèn)只完成少量計(jì)算時(shí)，它們的性能就不會(huì)很好。我們可以每次將一部分?jǐn)?shù)據(jù)從內(nèi)存層次中的較慢層加載到較快層，并趁它們處于較快層時(shí)執(zhí)行所有針對(duì)這些數(shù)據(jù)的運(yùn)算，這必將大大提高程序的性能。2023/1/121129.6.4降低碎片量的堆區(qū)空間管理策略空閑塊又被稱為孔洞如果對(duì)孔洞的使用不加管理的話，空閑的內(nèi)存空間最終就會(huì)變成若干碎片，即大量