運行時的存儲組織

第9章運行時的存儲組織SchoolofComputerScience&TechnologyHarbinInstituteofTechnology重點：符號表的內容、組織，過程調用實現(xiàn)，靜態(tài)存儲分配、動態(tài)存儲分配的基本方法。

難點：參數(shù)傳遞，過程說明語句代碼結構，過程調用語句的代碼結構，過程調用語句的語法制導定義，棧式存儲分配。2023/1/122第9章

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

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

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

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

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

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

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

vartemp:integer; begin 調用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傳值結果：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臨時單元:T:A+B=52023/1/1223編譯程序組織存儲空間時必須考慮的問題過程能否遞歸？當控制從過程的活動返回時，局部變量的值是否要保留？過程能否訪問非局部變量？過程調用的參數(shù)傳遞方式？過程能否作為參數(shù)被傳遞？過程能否作為結果值傳遞？存儲塊能否在程序控制下動態(tài)地分配？存儲塊是否必須顯式地釋放？2023/1/12249.2存儲組織9.2.1運行時內存的劃分9.2.2活動記錄9.2.3局部數(shù)據的組織9.2.4全局存儲分配策略2023/1/12257.2.1運行時內存的劃分目標代碼靜態(tài)數(shù)據棧堆空閑空間2023/1/1226過程的每個活動所需要的信息用一塊連續(xù)的存儲區(qū)來管理，這塊存儲區(qū)叫做活動記錄

假定語言的特點為:允許過程遞歸調用、允許過程含有可變數(shù)組，過程定義允許/不允許嵌套。采用棧式存儲分配機制活動記錄：運行時，每當進入一個過程就有一個相應的活動記錄壓入棧頂?；顒佑涗浺话愫羞B接數(shù)據、形式單元、局部變量、局部數(shù)組的內情向量和臨時工作單元等。9.2.2活動記錄2023/1/1227對任何局部變量X的引用可表示為變址訪問:dx[SP]dx:變量X相對于活動記錄起點的地址，在編譯時可確定。參數(shù)個數(shù)返回地址形式單元臨時變量數(shù)組內情向量簡單變量SP012舊SPTOP每個過程的活動記錄內容

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

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

——嵌套語言(如Pascal)2023/1/1229形式單元：存放相應的實在參數(shù)的地址或值。局部數(shù)據區(qū)：局部變量、內情向量、臨時工作單元(如存放對表達式求值的結果)。靜態(tài)鏈動態(tài)鏈形式單元臨時變量數(shù)組內情向量局部變量SP012返回地址TOP每個過程的活動記錄內容2023/1/12309.2.3局部數(shù)據的組織字節(jié)是可編址內存的最小單位。變量所需的存儲空間可以根據其類型而靜態(tài)確定。一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據域中依次分配空間。局部數(shù)據的地址可以用相對于某個位置的地址來表示。數(shù)據對象的存儲安排還有對齊的問題。整數(shù)必須放在內存中特定的位置，如被2、4、8整除 的地址2023/1/12319.2.3局部數(shù)據的組織在SPARC/Solaris工作站上下面兩個結構的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ù)據的組織在SPARC/Solaris工作站上下面兩個結構的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ù)據的組織在X86/Linux機器的結果和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)存儲分配策略(FORTRAN)

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

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

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

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

或dx[top]2023/1/12419.4.1調用序列和返回序列

過程調用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復機器狀態(tài)等過程調用和返回是通過在目標代碼中生成調用序列和返回序列來實現(xiàn)的

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

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

x1 param

x2 … param

xn callp，n9.4.2C語言的過程調用和返回

2023/1/12481)每個param

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

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

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

sp調用過程的活動記錄老sp參數(shù)個數(shù)形式單元形式單元2023/1/12493)進入過程p后，首先應執(zhí)行下述指令:

sp:=top+1

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

(保護返回地址)

top:=top+L

(新top)

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

在編譯時可確定。

參數(shù)個數(shù)返回地址形式單元內情向量局部變量老sp臨時單元TOP調用過程的活動記錄返回地址topsp2023/1/12504)過程返回時，應執(zhí)行下列指令:

top:=sp-1 (恢復調用前top)

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

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

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

全局數(shù)據說明main(){ main中的數(shù)據說明}voidR(){ R中的數(shù)據說明}…voidQ(){Q中的數(shù)據說明}主程序→過程Q→過程RQ的活動記錄主程序活動記錄TOPR的活動記錄SP參數(shù)個數(shù)返回地址形式單元內情向量局部變量老SP臨時單元全局數(shù)據區(qū)2023/1/12589.5.2有過程嵌套的靜態(tài)作用域假定語言不僅允許過程的遞歸調用(和可變數(shù)組)，而且允許過程定義的嵌套，如PASCAL，PL語言。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有過程嵌套的靜態(tài)作用域引入概念：過程嵌套深度sort 1

readarray 2 exchange 2

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

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

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

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

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

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

nx

+1次，到達了靜態(tài)包圍x和p的且離它們最近的那個過程的最新活動記錄所到達的訪問鏈就是x的活動記錄中的訪問鏈應該指向的那個訪問鏈2023/1/12679.5.2有過程嵌套的靜態(tài)作用域2.過程型參數(shù)的訪問鏈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.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈從b的訪問鏈難以建立f的訪問鏈激活fc傳遞參數(shù)f時，像調用f一樣為f建立一個訪問鏈，該訪問鏈同f一起傳遞給b。f被激活時用這個訪問鏈建立f的活動記錄的訪問鏈2023/1/12689.5.2有過程嵌套的靜態(tài)作用域programparam(input,output);（過程作為參數(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有過程嵌套的靜態(tài)作用域programret(input,output);（過程作為返回值）

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被調過程addm活動的生存期超出了調用過程a活動的生存期棧式存儲分配策略失效！！活動樹2023/1/12703.Display表

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

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

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

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

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

2.Display表由一組寄存器實現(xiàn)。9.5.2有過程嵌套的靜態(tài)作用域2023/1/1272一個例子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過程

S過程

Q過程

R過程

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

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

S

過程

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

S

過程

Q

過程

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

S

過程

Q

過程

R

過程

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

S

過程

Q

過程

R

過程

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

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

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

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

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

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

S過程

Q過程

R過程

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

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

S

過程

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

S

過程

Q

過程

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

S

過程

Q

過程

R

過程

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

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

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

程序運行時，一個名字a實施其影響，直到含a的聲明的一個過程開始執(zhí)行時暫停，此過程停止時，該影響恢復。設有下面的的調用序列：

ABCP

過程P中有對x的非局部引用，沿動態(tài)鏈（紅鏈）查找，最先找到的便是。2023/1/12999.5.3動態(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動態(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.125show;small;writeln; 0.250 0.125show;small;writelnend.dynamicshowsmallsmallshowshowshow2023/1/121019.5.3動態(tài)作用域實現(xiàn)動態(tài)作用域的方法深訪問(訪問非局部名字時的開銷大,易于實現(xiàn)過程類參數(shù))

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