研究生院第七章

第七章 運行環(huán)境源語言問題存儲組織存儲分配策略訪問非局部名字參數(shù)傳遞靜態(tài)和動態(tài)靜態(tài)和動態(tài)的聯(lián)系名字和數(shù)據對象數(shù)據對象的動態(tài)表示名字的作用域數(shù)據對象的存儲分配過程和活動參數(shù)處理運行時支撐程序包源語言問題（1）過程及其執(zhí)行過程定義：是一個聲明，最簡單形式是把一個標識符和一個語句聯(lián)系起來該標識符稱為過程名語句是過程體函數(shù)：返回值的過程過程調用過程名出現(xiàn)在可執(zhí)行語句中時，則稱這個過程在這點被調用調用者、被調用者和調用點參數(shù)形式參數(shù)：與局部變量有不同實在參數(shù)：在調用點，將其傳遞給被調用的過程源語言問題（2）

programsort(input,output); vara:array[0..10]ofinteger; procedurereadarray; vari:integer; begin fori:=1to9read(a[i]) end; functionpartition(m,n:integer); vari,j,x,v:integer; begin …. end; procedurequicksort(m,n:integer); vari:integer; begin if(n>m)thenbegin i:=partiton(m,n);quicksort(m,i–1);quicksort(i+1,n); end end; begin a[0]:=-9999;a[10]:=9999;readarray;quicksort(1,9) end.源語言問題（3）過程的執(zhí)行的表示：活動樹控制流的假設控制流是連續(xù)的過程的每次執(zhí)行都從過程體的起點開始，最后控制返回到直接跟隨本次調用點的位置過程間的控制流可以用樹表示（調用樹）活動：過程體的一次執(zhí)行活動的生存期：過程體執(zhí)行的第一步和最后一步之間的步序列包括直接或間接被這個過程調用的其它過程的時間過程的活動的生存期要么是不重疊的，要么是嵌套的遞歸：如果一個過程的前一個活動結束前，它的一個新的活動又開始遞歸的兩種緣起源語言問題（4）活動樹描述控制進入和離開活動：每個結點代表過程的一個活動根結點代表主程序的活動結點a是結點b的父結點，當且僅當控制流從a的活動進入ba結點處于b結點的左邊，當且僅當a的生存期先于b的生存期結點和活動是一一對應的源語言問題（5）幻燈片4中程序的活動樹源語言問題（6）控制?？刂茥Ｓ糜诒４婊钴S著的過程棧的內容表示活動樹上到根結點的一條路徑源語言問題（7）名字與數(shù)據對象聲明的作用域區(qū)分同名程序聲明：最接近的嵌套規(guī)則

inta,b; int*p; intfoo(inta) { intb,c; char*p; p=malloc(sizeof(char)); b=foo(1);… }作用域：一個聲明起作用的程序部分稱為該聲明的作用域局部和非局部：過程中名字的出現(xiàn)，如果是在該過程的一個聲明的作用域內，則這個出現(xiàn)稱為局部于該過程源語言問題（8）名字的結合程序中聲明的名字和動態(tài)數(shù)據對象的關系數(shù)據對象是保存值的存儲單元一個名字可能代表不同的數(shù)據對象環(huán)境：表示將名字映射到存儲單元（即名字的左值）的函數(shù)狀態(tài)：表示將存儲單元映射到它所保存的值（即名字的右值）的函數(shù)賦值操作只改變狀態(tài)，但不改變環(huán)境結合：如果環(huán)境把存儲單元s聯(lián)系到名字x，則稱x結合到s，這個聯(lián)系本身稱為x的結合 靜態(tài)概念 動態(tài)概念過程的定義 過程的活動名字的聲明 名字的結合聲明的作用域 結合的生存期源語言問題（9）名字結合要考慮的問題過程是否遞歸當控制從過程的活動返回時，局部名字的值是否要保留過程能否引用非局部的名字過程調用時參數(shù)是如何傳遞的過程是否可以作為參數(shù)被傳遞過程能否作為結果值返回存儲區(qū)能否在程序控制下動態(tài)地分配存儲區(qū)是否必須顯式地釋放存儲組織（1）運行時內存的劃分程序運行時如何使用內存：目標代碼的存放目標代碼可以存放在靜態(tài)確定的區(qū)域，其長度在編譯時即可確定數(shù)據對象可靜態(tài)分配的數(shù)據對象，其地址可以編譯到目標代碼中動態(tài)分配控制棧：記錄過程活動堆：可以存放動態(tài)分配的數(shù)據等，但開銷要比棧大存儲組織（2）活動記錄定義：過程的一次執(zhí)行所需要的信息用一塊連續(xù)的存儲區(qū)來管理，這塊存儲區(qū)叫做活動記錄或幀一般的活動記錄結構如右圖，但不是所有的語言或編譯器都是如此寄存器的使用活動記錄的操作：過程被調用時入棧過程返回時出棧存儲組織（3）活動記錄的各個域的作用臨時數(shù)據域：臨時變量的存儲等局部數(shù)據域：局部于過程執(zhí)行的數(shù)據機器狀態(tài)：保存過程調用前的機器狀態(tài)信息返回地址可選的訪問鏈：用于非局部數(shù)據的訪問可選的控制鏈：指向調用者的活動記錄實在參數(shù)域：參數(shù)個數(shù)較少時，可以考慮用寄存器傳遞，效率高；參數(shù)多時用用這個域傳遞返回值域：用于存放被調用過程返回給調用過程的值，也可以用寄存器返回（效率高，但形式受限制）存儲組織（4）過程調用時，每個域的長度都可以確定，大部分域的長度可以在編譯時刻確定運行框架安排的設計這個框架的設計要考慮指令集體系結構（ISA）特性和要編譯的程序語言本身的特點有些系統(tǒng)提供商為他們的體系結構提供一種標準的運行框架安排，使得可以實現(xiàn)不同的語言編寫的函數(shù)間的調用這個運行框架的設計通常在運行時支撐系統(tǒng)要考慮存儲組織（5）編譯時的局部數(shù)據安排名字所需的存儲空間的大小可以由它的類型確定基本數(shù)據對象（字符、整數(shù)或實數(shù)）可以用幾個連續(xù)的字節(jié)保存聚合類型（記錄、數(shù)組等）一塊足夠大的空間存放所有成分連續(xù)的字節(jié)區(qū)局部數(shù)據域在編譯過程中的聲明時安排長度可變的數(shù)據不保存在這個區(qū)域數(shù)據對象的相對地址（偏移）是數(shù)據對象地址相對于特定點（例如活動記錄的開始點）的地址差數(shù)據對齊：數(shù)據對象的存儲安排受目標機器尋址限制的影響如10個字符的數(shù)組可以被編譯器分配12個字節(jié)不用的2個字節(jié)稱為襯墊空白區(qū)存儲組織（6）兩個C編譯器的數(shù)據布局形式：存儲分配策略（1）靜態(tài)分配名字的結合：編譯時實現(xiàn)，不需要運行時支撐程序名字和存儲的結合是固定的允許名字的值在過程停止活動后保持根據名字的類型，編譯器可以在靜態(tài)時刻確定該名字所需的存儲空間，效率局限：數(shù)據對象的長度和它在內存中位置的限制必須在編譯時知道不允許遞歸過程不允許有動態(tài)數(shù)據結構在FORTRAN77中，靜態(tài)存儲分配策略，每個過程的活動記錄可以與它的代碼放在一起存儲分配策略（2）

PROGRAMCNSUME CHARACTER*50 BUF INTEGER NEXT CHARACTER C,PRDUCE DATANEXT/1/,BUF/‘’/6 C=PRDUCE() BUF(NEXT,NEXT)=C NEXT=NEXT+1 IF(C.NE.‘’)GOTO6 WRITE(*,‘(A)’)BUF END CHARACTERFUNCTIONPRDUCE() CHARACTER*80 BUFFER INTEGER NEXT SAVEBUFFER,NEXT DATANEXT/81/ IF(NEXT.GT.80)THEN READ(*,‘(A)’)BUFFER NEXT=1 ENDIF PRDUCE=BUFFER(NEXT,NEXT) NEXT=NEXT+1 END存儲分配策略（3）存儲分配策略（4）棧分配遞歸過程要求棧分配允許動態(tài)數(shù)據對象的存在滿足先入后出的次序控制棧：活動記錄和棧的關系局部量的存儲空間包含在對應調用的活動記錄中局部量的值會隨著過程調用結束而丟失控制棧top的變化和活動記錄的長度相關通常，局部量相對于活動記錄開始點的偏移量可以記錄在符號表中存儲分配策略（5）例：活動記錄在棧中的分配存儲分配策略（6）例：編譯時確定長度的數(shù)據對象偏移量在符號表中的存放存儲分配策略（7）過程調用的實現(xiàn)：通過過程調用序列（callingsequences）實現(xiàn)，包括調用序列和返回序列調用序列：分配活動記錄，信息的保存和填充參數(shù)、返回地址、老的控制棧top、寄存器的保存、局部對象的初始化等返回序列：恢復機器狀態(tài)，是調用者繼續(xù)執(zhí)行返回值、寄存器的恢復、重置控制棧top、跳轉到返回地址調用序列和活動記錄不是一成不變的，語言、實現(xiàn)等都會導致不同過程調用序列的代碼分成兩部分，分別由調用過程和被調用過程負責，但劃分的界限不是唯一的存儲分配策略（8）圖：調用者和被調用者間的任務劃分存儲分配策略（9）調用序列（callsequences），過程p調用過程qp計算實參，依次放入q的活動記錄中（也可以利用寄存器傳遞參數(shù)），改變top_sp的值p把返回地址和當前的base_sp的值存入q的活動記錄中，建立q的訪問鏈，增加base_sp的值q保存寄存器的值（包括top_sp的值）和其它機器狀態(tài)信息q增加top_sp的值，初始化它的局部數(shù)據，并開始執(zhí)行存儲分配策略（10）返回序列（returnsequences），過程p調用過程qq把返回值置入鄰近p的活動記錄的地方（也可以利用特定的寄存器傳遞返回值）q恢復寄存器的值（包括top_sp和base_sp）和其它機器狀態(tài)信息q根據返回地址將控制返回pp根據參數(shù)個數(shù)調整top_sp的值，把返回值放入自己的活動記錄中參數(shù)個數(shù)不確定？C語言中的printf保存描述參數(shù)的信息，如printf首先處理的第一個變元（它的位置是確定的）指出了其它參數(shù)的性質存儲分配策略（11）動態(tài)數(shù)組數(shù)組的界在編譯時刻無法確定，只能在運行時刻確定procedure(n) integern,m[n] …end動態(tài)數(shù)組不能分配在活動記錄中在動態(tài)數(shù)組的大小確定后，在該過程的活動記錄緊鄰的棧中分配空間動態(tài)數(shù)組的描述也可以考慮用內情向量的方式存儲分配策略（12）動態(tài)數(shù)組訪問的示意存儲分配策略（13）懸空引用引用某個已釋放的存儲單元稱為懸空引用這是由于存儲空間可以釋放這是一個邏輯錯誤：在大多數(shù)語言中，釋放的存儲單元的值是沒有定義的

main() { int*p; p:=dangle(); } int*dangle() { inti=23; return&i; }函數(shù)dangle返回后，指針p指向一個已釋放的存儲單元存儲分配策略（14）堆分配棧分配的局限不能使得活動停止時，局部名字的值保持被調用者的活動不能比調用者的活動活得更長（否則，活動樹不能正確描繪過程間的控制流），只能滿足先入后出的次序堆分配把連續(xù)存儲區(qū)域分成塊需要時分配（活動記錄或其它對象）釋放次序任意堆可以與棧分配結合起來C++語言中，基本保持棧的形式，堆用于動態(tài)對象的分配C、Pascal語言中的指針的動態(tài)分配等存儲分配策略（15）堆中，活躍的活動記錄不一定相臨，可能存在空洞存儲分配策略（16）堆的釋放不釋放存儲空間溢出時停止顯式釋放Free（C，PL/1），deallocation（Ada）…有可能引起懸掛引用隱式釋放單引用引用計數(shù)垃圾收集（Garbagecollection）堆的分配和釋放的優(yōu)化訪問非局部名字（1）如何通過活動記錄正確訪問名字，滿足作用域的要求？兩種作用域靜態(tài)作用域根據程序正文決定用于名字的聲明最接近的嵌套規(guī)則程序塊非局部名字的訪問：訪問鏈動態(tài)作用域在運行時，根據現(xiàn)行的活動來決定用于名字的聲明，如Lisp等訪問非局部名字（2）程序塊定義：起源于AlgolC語言中的定義：{declarationsstatements}允許嵌套最接近的嵌套規(guī)則：程序塊B中聲明的作用域包括B如果名字x沒有在B中聲明，則B中x的出現(xiàn)是在外圍程序塊B’的x聲明的作用域中，且滿足：B’有x的聲明B’比其它任何含x聲明的程序塊更接近被嵌套的B訪問非局部名字（3）例：非局部名字的引用main(){inta=0;intb=0;{intb=1;{inta=2;printf(“%d,%d\n”,a,b);}{intb=3;printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}B0B1B2B3聲明作用域inta=0;B0-B2intb=0;B0-B1intb=1;B1-B3inta=2;B2intb=3;B321030100訪問非局部名字（4）名字的存儲分配：基于棧分配：聲明的作用域決不超出它所在的程序塊程序塊當作無參的過程，所以活動記錄可以是程序塊的這類“過程”調用不需要參數(shù)傳遞，控制只能沿靜態(tài)正文進入和退出程序塊每次為一個完整的過程體分配存儲空間只為過程分配活動記錄過程內嵌套的程序塊的生命所需要的存儲空間由過程負責留出要分配的變量在編譯時刻確定，不考慮控制流作用域不重疊的聲明可以共享一個存儲區(qū)域

a0 b0 b1 a2,b3訪問非局部名字（5）無過程嵌套的靜態(tài)作用域一個過程的定義不能出現(xiàn)在另一個過程里面，如C語言對某個過程非局部的名字（過程中程序塊的非局部名字的處理見前面的內容），其聲明在所有函數(shù)之外函數(shù)外聲明的作用域：該聲明后的所有函數(shù)體，但同名的局部聲明的出現(xiàn)將掩蓋全局聲明的作用例： inta[11]; readarray(){……a……} intpartition(y,z)inty,z;{……a……} quicksort(m,n)intm,n;{……} main(){……a……}訪問非局部名字（6）存儲分配比較簡單：聲明在任何過程外的所有名字的存儲單元靜態(tài)分配，其存儲位置在編譯時可知過程中可見的名字：非過程局部的，則使用靜態(tài)確定的地址訪問其它的名字，局部于棧頂?shù)幕顒蛹o錄，可以通過base_sp訪問重要好處：程序中聲明的過程可以作為參數(shù)傳遞和作為結果返回（C語言中是傳遞過程的指針）非局部名字的訪問不受過程激活方式的影響訪問非局部名字（7）例： programpass(input,output); varm:integer; functionf(n:integer):integer; beginf:=m+nend{f}; functiong(n:integer):integer; beging:=m*nend{g}; procedureb(functionh(n:integer):integer); beginwrite(h(2))end; begin

m:=0; b(f);b(g);writeln end.變量m對所有的過程是非局部的，可以靜態(tài)分配它的存儲單元執(zhí)行結果是：20訪問非局部名字（8）有過程嵌套的靜態(tài)作用域非局部名字的訪問：尋找最接近的嵌套聲明，如下面例子中函數(shù)partition對a的訪問

programsort(input,output);

vara:array[0..10ofinteger;x:integer;procedurereadarray;vari:integer;begin…a…end{readarray};procedureexchange(i,j:integer);beginx:=a[i];a[i]:=a[j];a[j]:=x;end{exchange};procedurequicksort(m,n:integer);vark,v:integer; functionpartition(y,z:integer):integer vari,j:integer; begin…a…;…v…;…exchange(i,j);…end begin……end{quicksort};begin……end{sort}.訪問非局部名字（9）嵌套深度：過程的嵌套深度設主程序的嵌套深度是1從一個過程進入一個被包圍的過程，嵌套深度加1名字的每次出現(xiàn)，把它的聲明所在過程的嵌套深度作為該名字的嵌套深度用于實現(xiàn)靜態(tài)作用域訪問鏈：為每個活動記錄增加一個訪問鏈指針，如果過程p在源程序中直接嵌在q中，則p的活動記錄的訪問鏈指向最接近的那個q的活動記錄的訪問鏈實現(xiàn)過程嵌套的靜態(tài)作用域訪問非局部名字（10）幻燈片41程序執(zhí)行時運行棧的瞬像：訪問非局部名字（11）靜態(tài)鏈（訪問鏈）和動態(tài)鏈（控制鏈）的比較：靜態(tài)鏈：指向源程序中包圍本過程的直接外層過程的一個最近活動記錄的訪問鏈通過靜態(tài)鏈實現(xiàn)非局部名字的訪問通過靜態(tài)鏈訪問非局部名字，訪問速度慢動態(tài)鏈：指向調用者的活動記錄ABCDEARofAARofBARofCARofD動態(tài)鏈靜態(tài)鏈訪問非局部名字（12）訪問鏈的建立：假定過程p的嵌套深度為np，它調用一個嵌套深度為nx的過程x：如果np<nx：如幻燈片44的B調用D過程x比過程p嵌得更深，x必定在p中聲明訪問鏈指向棧中剛好在它下面的調用過程的活動記錄如果np

>=nx：如幻燈片44的C調用E過程x和p的嵌套深度為1，2，…，nx–1的外圍過程必定相同從調用過程追蹤訪問鏈np-nx+1次，即到達靜態(tài)包圍x和p的最內過程的最新活動記錄，這個訪問鏈就是x必須指向的訪問鏈np-nx+1可以在編譯時計算特別地，如果np=nx，如幻燈片44的C調用D，則D的訪問鏈指向與C的訪問鏈指向相同訪問非局部名字（13）通過訪問鏈訪問非局部名字：假定過程p的嵌套深度為np，它引用一個嵌套深度為na的變量a，na<=np，則a的存儲單元可以如下找到：當控制在p中時，p的一個活動記錄必定在棧頂從棧頂追蹤訪問鏈np-na次（這個次數(shù)編譯時刻可以計算）追蹤訪問鏈np-na次后，到達a的聲明所在過程的活動記錄，根據a的偏移量可以訪問綜述：過程p中變量a的地址可以如下表示： （np-na

，a在活動記錄中的偏移）過程調用發(fā)生時，非局部名字到存儲單元的結合可能發(fā)生變化訪問非局部名字（14）過程作參數(shù)的處理：作為參數(shù)傳遞的過程必須取它的訪問鏈和它一起傳遞例：

programparam(input,output); procedureb(functionh(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.訪問非局部名字（15）訪問非局部名字（16）Display表：d[i]通過數(shù)組存放訪問鏈，提高對非局部名字的訪問效率如果當前的活動記錄對應的過程p的嵌套深度為j，則Display表有j項，前j-1項指向依次嵌套在過程p外面的過程的最新活動記錄，第j項指向過程p的這次活動記錄同一個過程的不同活動記錄間可以利用訪問鏈鏈結，在調用序列和返回序列中進行更新操作當一個嵌套深度i的過程被調用時，建立一個新的活動記錄在新的活動記錄中保存d[i]的值令d[i]指向新的活動記錄在一個活動結束前，恢復d[i]被保存的值訪問非局部名字（17）訪問非局部名字（18）Display表的維護如果j<i，有i=j+1，被調用過程嵌套在調用過程中，Display表的前j項不需要變更，將d[i]指向新的活動記錄，如上頁的c圖如果j>=i，調用者和被調用者外面包圍的嵌套深度為1，2，…，i-1的過程是同樣的，在新的活動記錄中保存老的d[i]，置d[i]指向新的活動記錄，保持Display表的前i–1項不變，如上頁的d圖Display表的保存可以放在寄存器中，受限于寄存器個數(shù)和非局部名字訪問的頻繁程度可以在編譯時刻知道Display表的最大長度，因此也可以將Display表存放為一個單獨的表或作為活動記錄的一部分訪問非局部名字（19）動態(tài)作用域：當一個過程被調用時，它的非局部名字到存儲單元的結合不會改變，即被調用過程的非局部名字a和它在調用過程中引用的是同樣的存儲單元新的結合僅為被調用過程的局部名字建立，這些名字占用新活動記錄中的存儲單元在運行時，一個名字a實施其影響，直到含a的聲明的一個過程開始執(zhí)行時暫停；此過程停止時，該影響恢復訪問非局部名字（20）例：動態(tài)作用域和靜態(tài)作用域的對比

programdynamic(input,output); varr:real; procedureshow; beginwrite(r:5:3)end; proceduresmall; varr:real; beginr:=0.125;showend; begin r:=0.25; show;small;writeln; show;small;writeln; end靜態(tài)作用域的輸出： 動態(tài)作用域的輸出： 0.2500.250 0.2500.125 0.2500.250 0.2500.125訪問非局部名字（21）動態(tài)作用域的實現(xiàn)：深訪問訪問鏈指向的活動記錄和控制鏈指向的活動記錄一樣，則實現(xiàn)了動態(tài)作用域，因此可以省卻訪問鏈，通過控制鏈搜索棧編譯時刻不能確定搜索的深度訪問非局部名字需要較長的時間，但活動的開始和結束不需要額外開銷淺訪問為每個名字在靜態(tài)分配的存儲空間中保存它的當前值當過程p的新活動出現(xiàn)時，p的局部名字n接管分配給n的存儲單元，n的先前值可以保存在p的活動記錄中，當p的活動結束時再恢復可以直接訪問非局部名字，但活動的開始和結束需要維護的開銷參數(shù)傳遞（1）過程和其調用者交換信息的方法：非局部名字參數(shù)返回值參數(shù)傳遞的方法：實現(xiàn)形參和實參聯(lián)系的方法不同的參數(shù)傳遞方法是因為對表達式所表達的內容的不同解釋左值右值參數(shù)傳遞的種類值調用（Call-by-Value）引用調用（Call-by-Reference）復寫-恢復調用（Copy-Restore）換名調用（Call-by-Name）……參數(shù)傳遞（2）值調用計算實參，并把它的右值傳遞給被調用過程C語言、Pascal語言支持這種方式形參當作局部名，其存儲單元在被調用過程的活動記錄中調用者計算實參，并把右值放在形參的存儲單元中形參的運算不影響調用者活動記錄中的值被調用過程可以通過非局部名字或通過顯式傳遞的指針值影響調用者參數(shù)傳遞（3）

swap(x,y) int*x,*y; { inttemp; temp=*x;*x=*y;*y=temp; } main() { inta=1,b=2; swap(&a,&b); printf(“aisnow%d,bisnow%d\n”,a,b); }參數(shù)傳遞（4）引用調用也稱為地址調用（call-by-address）或位置調用（call-by-location）調用者將參數(shù)的左值傳遞給被調用的過程如果實參是有左值的名字或表達式，則傳遞這個左值本身如果實參實沒有左值的表達式（如a+b或2等），則把它的值計算到新的存儲單元，然后傳遞這個單元的地址如Pascal語言中var參數(shù)是用這種方式傳遞的數(shù)組一般是用這種方式傳遞的參數(shù)傳遞（5）復寫-恢復值調用和引用調用的混合，也稱為復寫入和復寫出（copy-incopy-out）或值-結果（value-result）在控制流到被調用過程之前計算實參，實參的右值按值調用方式傳遞被調用過程，如果實參有左值，則在調用前確定它的左值當控制返回時，將形參的當前右值復寫回到實參的左值，該左值是上述調用前確定的左值。只有有左值的實參被復寫某些Fortran的實現(xiàn)使用了這種參數(shù)傳遞方式參數(shù)傳遞（6）使用復寫-恢復方式的原因避免了一個過程調用