第章運行時存儲空間的組織和管理編譯原理中國科

編譯原理和技術中國科學技術大學計算機科學與技術學院陳意云第六章運行時存儲空間的組織和管理

術語過程的活動

過程的一次執(zhí)行稱為過程的一次活動活動記錄 過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間,后者稱為活動記錄本章內容討論一個活動記錄中的數(shù)據(jù)布局程序執(zhí)行過程中，所有活動記錄的組織方式

第六章運行時存儲空間的組織和管理

影響存儲分配策略的語言特征

過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結果值傳遞存儲塊能否在程序控制下動態(tài)地分配存儲塊是否必須顯式地釋放6.1

局部存儲分配6.1.1過程語言概念： 過程定義、過程調用、形式參數(shù)、實在參數(shù)、活動的生存期6.1

局部存儲分配6.1.2名字的作用域和綁定1、名字的作用域一個聲明起作用的程序部分稱為該聲明的作用域即使一個名字在程序中只聲明一次，該名字在程序運行時也可能表示不同的數(shù)據(jù)對象6.1

局部存儲分配2、環(huán)境和狀態(tài)環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值（即名字到值有兩步映射）賦值改變狀態(tài)，但不改變環(huán)境

過程調用改變環(huán)境如果環(huán)境將名字x映射到存儲單元s，則說x被綁定到s名字存儲單元狀態(tài)值環(huán)境6.1

局部存儲分配3、靜態(tài)概念和動態(tài)概念的對應

靜

態(tài)

概

念

動

態(tài)

對

應

過程的定義

過程的活動

6.1

局部存儲分配3、靜態(tài)概念和動態(tài)概念的對應

靜

態(tài)

概

念

動

態(tài)

對

應

過程的定義

過程的活動

名字的聲明

名字的綁定

6.1

局部存儲分配3、靜態(tài)概念和動態(tài)概念的對應

靜

態(tài)

概

念

動

態(tài)

對

應

過程的定義

過程的活動

名字的聲明

名字的綁定

聲明的作用域

綁定的生存期

6.1

局部存儲分配6.1.3活動記錄 活動記錄的常見布局返回值臨時數(shù)據(jù)參數(shù)控制鏈訪問鏈機器狀態(tài)局部數(shù)據(jù)6.1局部存儲分分配6.1.4局部數(shù)數(shù)據(jù)的布局局字節(jié)是可編編址內存的的最小單位位變量所需的的存儲空間間可以根據(jù)據(jù)其類型而而靜態(tài)確定定一個過程所所聲明的局局部變量，，按這些變變量聲明時時出現(xiàn)的次次序，在局局部數(shù)據(jù)域域中依次分分配空間局部數(shù)據(jù)的的地址可以以用相對于于活動記錄錄中某個位位置的地址址來表示數(shù)據(jù)對象的的存儲布局局還有一個個對齊問題題6.1局部存儲分分配例 在SPARC/Solaris工作站上下下面兩個結結構體的size分別是24和16，為什么不不一樣？typedefstruct_a{typedefstruct_b{charc1;charc1;longi;char c2;charc2;longi;doublef;doublef;}a;}b;對齊：char:1,long:4,double:86.1局部存儲分分配例 在SPARC/Solaris工作站上下下面兩個結結構體的size分別是24和16，為什么不不一樣？typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;16doublef;8}a;}b;對齊：char:1,long:4,double:86.1局部存儲分分配例 在X86/Linux機器的結果果和SPARC/Solaris工作站不一一樣，是20和16。typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;12doublef;8}a;}b;對齊：char:1,long:4,double:46.1局部存儲分分配6.1.5程序塊本身含有局局部變量聲聲明的語句句可以嵌套最接近的嵌嵌套作用域規(guī)則則并列程序塊塊不會同時時活躍并列程序塊塊的變量可可以重疊分分配6.1局部存儲分分配main()/例/{/beginofB0/inta=0;intb=0;{/beginofB1/intb=1;{/beginofB2/inta=2;}/endofB2/{/beginofB3/intb=3;}/endofB3/}/endofB1/}/endofB0/6.1局部存儲分分配main()/例/{/beginofB0/inta=0;intb=0;{/beginofB1/intb=1;{/beginofB2/inta=2;}/endofB2/{/beginofB3/intb=3;}/endofB3/}/endofB1/}/endofB0/聲

明

作

用

域

inta=0;B0

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

a0b0b1a2,b3重疊分配存儲單元

6.2全局局棧棧式式存存儲儲分分配配本節(jié)介紹紹介紹程序序運行時時所需的的各個活活動記錄錄在存儲儲空間的的分配策策略描述過程程的目標標代碼怎怎樣訪問問綁定到到局部名名字的存存儲單元元介紹三種種分配策策略靜態(tài)分配配策略棧式分配配策略堆式分配配策略6.2全局棧式式存儲分分配6.2.1運行時內內存的劃劃分代碼靜態(tài)數(shù)據(jù)堆棧6.2全局棧式式存儲分分配1、靜態(tài)分分配名字在程程序被編編譯時綁綁定到存存儲單元元，不需需要運行行時的任任何支持持綁定的生生存期是是程序的的整個運運行期間間6.2全局棧式式存儲分分配2、靜態(tài)分分配給語語言帶來來限制遞歸過程程不被允允許數(shù)據(jù)對象象的長度度和它在在內存中中位置的的限制，，必須是是在編譯譯時可以以知道的的數(shù)據(jù)結構構不能動動態(tài)建立立6.2全局棧式式存儲分分配例C程序的外外部變量量、靜態(tài)態(tài)局部變變量以及及程序中中出現(xiàn)的的常量都都可以靜靜態(tài)分配配聲明在函函數(shù)外面面外部變量量--靜態(tài)分配配靜態(tài)外部部變量--靜態(tài)分配配聲明在函函數(shù)里面面靜態(tài)局部部變量--也是靜態(tài)態(tài)分配自動變量量--不能靜態(tài)態(tài)分配6.2全局棧式式存儲分分配活動樹和和運行棧棧1、活動樹樹用樹來描描繪控制制進入和和離開活活動的方方式mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2全局棧式式存儲分分配活動樹的的特點每個結點點代表某某過程的的一個活活動根結點代代表主程程序的活活動結點a是結點b的父結點點，當且且僅當控控制流從從a的活動進進入b的活動結點a處于結點點b的左邊，，當且僅僅當a的生存期期先于b的生存期期mq(1,9)rp(1,9)q(1,3)....q(5,9)....6.2全局棧式式存儲分分配當前活躍躍著的過過程活動動可以保保存在一一個棧中中例控控制棧的的內容：：m,q(1,9),q(1,3),q(2,3)mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2全局棧式式存儲分分配2、運行棧棧：把控制棧棧中的信信息拓廣廣到包括括過程活活動所需需的所有有局部信信息（即即活動記記錄）6.2全局棧式式存儲分分配2、運行棧棧：把控制棧棧中的信信息拓廣廣到包括括過程活活動所需需的所有有局部信信息（即即活動記記錄）ma:arraym6.2全局棧式式存儲分分配2、運行棧棧：把控制棧棧中的信信息拓廣廣到包括括過程活活動所需需的所有有局部信信息（即即活動記記錄）mi:integerra:arraymr6.2全局棧式式存儲分分配2、運行棧棧：把控制棧棧中的信信息拓廣廣到包括括過程活活動所需需的所有有局部信信息（即即活動記記錄）mk:integerq(1,9)a:arraymq(1,9)r6.2全局棧式式存儲分分配2、運行棧棧：把控制棧棧中的信信息拓廣廣到包括括過程活活動所需需的所有有局部信信息（即即活動記記錄）mk:integerq(1,9)a:arrayq(1,3)k:integermq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)6.2全局棧式式存儲分分配調用序列列過程調用用和過程程返回都都需要執(zhí)執(zhí)行一些些代碼來來管理活活動記錄錄棧，保保存或恢恢復機器器狀態(tài)等等過程調用用序列過程調用用時執(zhí)行行的分配配活動記記錄，把把信息填填入它的的域中，，使被調調用過程程可以開開始執(zhí)行行的代碼碼過程返回回序列被調用過過程返回回時執(zhí)行行的恢復復機器狀狀態(tài)，釋釋放被調調用過程程活動記記錄，使使調用過過程能夠夠繼續(xù)執(zhí)執(zhí)行的代代碼調用序列列和返回回序列常常都分分成兩部部分，分分處于調調用過程程和被調調用過程程中6.2全局棧式式存儲分分配即使是同同一種語語言，過過程調用用序列、、返回序序列和活活動記錄錄中各域域的排放放次序，，也會因因實現(xiàn)而而異設計這些些序列和和活動記記錄的一些原原則以活動記記錄中間間的某個個位置作為為基地址址長度能較較早確定定的域放放在活動記錄錄的中間間返回值臨時數(shù)據(jù)參數(shù)控制鏈訪問鏈機器狀態(tài)局部數(shù)據(jù)6.2全局棧式式存儲分分配即使是同同一種語語言，過過程調用用序列、、返回序序列和活活動記錄錄中各域域的排放放次序，，也會因因實現(xiàn)而而異設計這些些序列和和活動記記錄的一些原原則一般把臨臨時數(shù)據(jù)據(jù)域放在在局部數(shù)據(jù)據(jù)域的后后面把參數(shù)域域和可能能有的返返回值域放在在緊靠調調用者活活動記錄的地地方返回值臨時數(shù)據(jù)參數(shù)控制鏈訪問鏈機器狀態(tài)局部數(shù)據(jù)6.2全局棧式式存儲分分配即使是同同一種語語言，過過程調用用序列、、返回序序列和活活動記錄錄中各域域的排放放次序，，也會因因實現(xiàn)而而異設計這些些序列和和活動記記錄的一些原原則用同樣的的代碼來來執(zhí)行各各個活動的保保存和恢恢復返回值臨時數(shù)據(jù)參數(shù)控制鏈訪問鏈機器狀態(tài)局部數(shù)據(jù)6.2全局棧式式存儲分分配1、過程p調用過程程q的調用序序列返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

6.2全局棧式式存儲分分配1、過程p調用過程程q的調用序序列(1)p計算實實參，，依次次放入入棧頂頂，并并在棧棧頂留留出放放返回回值的的空間間。top_sp的值在在此過過程中中被改改變返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

返回值和參數(shù)top_sp

6.2全局棧棧式存存儲分分配1、過程程p調用過過程q的調用用序列列(2)p把返回回地址址和當當前base_sp的值存存入q的活動動記錄錄中，，建立立q的訪問問鏈，，增加加base_sp的值返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

返回值和參數(shù)控制鏈和返回地址base_sp

top_sp

6.2全局棧棧式存存儲分分配1、過程程p調用過過程q的調用用序列列(3)q保存存寄存存器的的值和和其它它機器器狀態(tài)態(tài)信息息返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

返回值和參數(shù)控制鏈和保存的機器狀態(tài)6.2全局棧棧式存存儲分分配1、過程程p調用過過程q的調用用序列列(4)q根據(jù)局局部數(shù)數(shù)據(jù)域域和臨臨時數(shù)數(shù)據(jù)域域的大大小增增加top_sp的值，，初始始化它它的局局部數(shù)數(shù)據(jù)，，并開開始執(zhí)執(zhí)行過過程體體臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)

控制鏈和保存的機器狀態(tài)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

6.2全局棧棧式存存儲分分配調用者者p和被調調用者者q之間的的任務務劃分分被調用者q的責任調用者p的責任調用者p的活動記錄被調用者q的活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

6.2全局棧棧式存存儲分分配2、過程程p調用過過程q的返回回序列列臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

6.2全局棧棧式存存儲分分配2、過程程p調用過過程q的返回回序列列臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(1)q把返返回值值置入入鄰近近p的的活動動記錄錄的地地方參數(shù)個個數(shù)可可變場場合難難以確確定存存放返返回值值的位位置，，因此此通常常用寄寄存器器傳遞遞返回回值6.2全局棧棧式存存儲分分配2、過程程p調用過過程q的返回回序列列(2)q對應調調用序序列的的步驟驟(4)，減小小top_sp的值返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

返回值和參數(shù)控制鏈和保存的機器狀態(tài)6.2全局棧棧式存存儲分分配2、過程程p調用過過程q的返回回序列列(3)q恢復寄寄存器器(包括base_sp)和機器器狀態(tài)態(tài)，返返回p返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

返回值和參數(shù)6.2全局棧棧式存存儲分分配2、過程程p調用過過程q的返回回序列列返回值和參數(shù)top_sp

base_sp

臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(4)p根據(jù)參參數(shù)個個數(shù)與與類型型和返返回值值類型型調整整top_sp，然后取取出返返回值值6.2全局棧棧式存存儲分分配3、過過程的的參數(shù)數(shù)個數(shù)數(shù)可變變的情情況臨時數(shù)據(jù)局部數(shù)據(jù)參數(shù)參數(shù)

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(1)函函數(shù)返返回值值改成成用寄寄存器器傳遞遞6.2全局棧棧式存存儲分分配3、過過程的的參數(shù)數(shù)個數(shù)數(shù)可變變的情情況臨時數(shù)據(jù)局部數(shù)據(jù)參數(shù)1,…,參數(shù)n參數(shù)1,…,參數(shù)m

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(2)編編譯器器產(chǎn)生生將實實參表表達式式逆序序計算算并將將結果果進棧棧的代代碼自上而而下依依次是是參數(shù)數(shù)1,……,參參數(shù)數(shù)n6.2全局棧棧式存存儲分分配3、過過程的的參數(shù)數(shù)個數(shù)數(shù)可變變的情情況臨時數(shù)據(jù)局部數(shù)據(jù)參數(shù)1,…,參數(shù)n參數(shù)1,…,參數(shù)m

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(3)被被調用用函數(shù)數(shù)能準準確地地知道道第一一個參參數(shù)的的位置置6.2全局棧棧式存存儲分分配3、過過程的的參數(shù)數(shù)個數(shù)數(shù)可變變的情情況臨時數(shù)據(jù)局部數(shù)據(jù)參數(shù)1,…,參數(shù)n參數(shù)1,…,參數(shù)m

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

(4)被被調用用函數(shù)數(shù)根據(jù)據(jù)第一一個參參數(shù)到到棧中中取第第二、、第三三個參參數(shù)等等等6.2全局棧棧式存存儲分分配3、過過程的的參數(shù)數(shù)個數(shù)數(shù)可變變的情情況臨時數(shù)據(jù)局部數(shù)據(jù)參數(shù)1,…,參數(shù)n參數(shù)1,…,參數(shù)m

控制鏈和保存的機器狀態(tài)top_sp

base_sp

棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈和保存的機器狀態(tài)

C語言言的printf函函數(shù)就是是按此此方式式，用C語語言編編寫的的下面語語句的的輸出出？printf(“%d,%d,%d\n””);6.2全局棧棧式存存儲分分配棧上可可變長長數(shù)據(jù)據(jù)活動記記錄的的長度度在編編譯時時不能能確定定的情例：局部數(shù)組的大小要等到過程激活時才能確定備注：

Java語言的實現(xiàn)是將它們分配在堆上6.2全局棧棧式存存儲分分配訪問動動態(tài)分分配的的數(shù)組組控制鏈數(shù)組A的指針數(shù)組B的指針top_sp

base_sp

.........棧(1)編編譯時時，在在活動動記錄錄中為為這樣樣的數(shù)數(shù)組分分配存存放數(shù)數(shù)組指指針的的單元元6.2全局棧棧式存存儲分分配訪問動動態(tài)分分配的的數(shù)組組(2)運運行時時，這這些指指針指指向分分配在在棧頂頂?shù)臄?shù)數(shù)組存存儲空空間控制鏈數(shù)組A的指針數(shù)組B的指針top_sp

base_sp

.........棧數(shù)組A數(shù)組B6.2全局棧棧式存存儲分分配訪問動動態(tài)分分配的的數(shù)組組(3)運運行時時，對對數(shù)組組A和和B的的訪問問都要要通過過相應應指針針來間間接訪訪問控制鏈數(shù)組A的指針數(shù)組B的指針top_sp

base_sp

.........棧數(shù)組A數(shù)組B6.2全局棧棧式存存儲分分配訪問動動態(tài)分分配的的數(shù)組組q的數(shù)組q的活動記錄p的數(shù)組p的活動記錄控制鏈top_sp

base_sp

數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈.........棧6.2全局棧棧式存存儲分分配懸空引引用懸空引引用：：引用某某個已已被釋釋放的的存儲儲單元元6.2全局棧棧式存存儲分分配懸空引引用懸空引引用：：引用某某個已已被釋釋放的的存儲儲單元元例：main中引用用p指向的的對象象main(){|intdangle(){intq;|intj=20;q=dangle();|return&j;}|}6.3非局部部名字字的訪訪問本節(jié)介介紹無過程程嵌套套的靜靜態(tài)作作用域域（C語言））有過程程嵌套套的靜靜態(tài)作作用域域（Pascal語言））動態(tài)作作用域域（Lisp語言）6.3非局部名字字的訪問過程體中的非局部引用可以直接使用靜態(tài)確定的地址（非局部數(shù)據(jù)此時就是全局數(shù)據(jù)）局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳遞，也可以作為結果來返回6.3非局部名字字的訪問6.3.2有過程嵌套套的靜態(tài)作作用域sortreadarrayexchangequicksortpartition6.3非局部名字字的訪問6.3.2有過程嵌套套的靜態(tài)作作用域過程嵌套深度sort1readarray 2exchange2quicksort 2partition 3變量的嵌套深度作為該名字的嵌套深度訪問鏈用來尋尋找非非局部部名字的的存儲儲單元元sa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈6.3非非局局部名名字的的訪問問6.3非局部部名字字的訪訪問訪問非非局部部名字字的存存儲單單元假定過過程p的嵌套套深度度為np，它引用用嵌套套深度度為na的變量量a，nanp，如何何訪問問a的存儲儲單元元sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈6.3非局部部名字字的訪訪問訪問非非局部部名字字的存存儲單單元假定過過程p的嵌套套深度度為np，它引用用嵌套套深度度為na的變量a，nanp，如何訪問a的存儲單元從棧頂?shù)幕顒觿佑涗涢_始，，追蹤訪問鏈鏈npna次到達a的聲明所在過過程的活動記記錄訪問鏈的追蹤蹤用間接操作作就可完成sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈訪問非局部名名字的存儲單單元sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈6.3非非局部名字的的訪問6.3非局部名字的的訪問過程p對變量a訪問時，a的地址由下面面的二元組表表示：（npna，a在活動記錄中中的偏移）6.3非局部名字的的訪問建立訪問鏈假定嵌套深度度為np的過程p調用嵌套深度度為nx的過程x(1)np<nx的情況sort1readarray2exchange2quicksort2partition3這時x肯定就聲明在在p中6.3非局部名字的的訪問建立訪問鏈假定嵌套深度度為np的過程p調用嵌套深度度為nx的過程x(1)np<nx的情況被調用過程的的訪問鏈必須須指向調用過過程的活動記記錄的訪問鏈鏈訪問非局部名名字的存儲單單元sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈6.3非非局部名字的的訪問6.3非局部名字的的訪問建立訪問鏈假定嵌套深度度為np的過程p調用嵌套深度度為nx的過程x(2)npnx的情況sort1readarray2exchange2quicksort2partition3這時p和x的嵌套深度分分別為1，2，…，nx1的外圍過程肯肯定相同6.3非局部名字的的訪問建立訪問鏈假定嵌套深度度為np的過程p調用嵌套深度度為nx的過程x(2)npnx的情況追蹤訪問鏈npnx+1次，到達了靜靜態(tài)包圍x和p的且離它們最最近的那個過過程的最新活活動記錄所到達的活動動記錄就是x的活動記錄中中的訪問鏈應應該指向的那那個活動記錄錄訪問非局部名名字的存儲單單元sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈e(1,3)訪問鏈sa,xq(1,3)k,v訪問鏈q(1,9)k,v訪問鏈p(1,3)i,j訪問鏈6.3非非局部名字的的訪問6.3非局部名字的的訪問programparam(input,output);（過程作為參數(shù)數(shù)）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};begincend.函數(shù)f作為參數(shù)數(shù)傳遞時時，怎樣樣在f6.3非局部名名字的訪訪問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};begincend.從b的訪問鏈鏈難以建建立f的訪問鏈鏈訪問鏈訪問鏈paramcmb

<f>6.3非局部名名字的訪訪問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};begincend.f作為參數(shù)數(shù)傳遞時時，它的的起始地地址連同同它的訪訪問鏈一一起傳遞遞訪問鏈訪問鏈paramcmb

<f,>6.3非局部名名字的訪訪問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};begincend.b調用f時，用傳傳遞過來來的訪問問鏈來建建立f的訪問鏈鏈訪問鏈訪問鏈paramcmb

<f,>訪問鏈b6.3非局部名名字的訪訪問programret(input,output);（過程作為為返回值值）varf:function(integer):integer;functiona:function(integer):integer;varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.aretbaddm6.3非局部名名字的訪訪問programret(input,output);（過程作為為返回值值）varf:function(integer):integer;functiona:function(integer):integer;varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2))end;beginf:=a;b(f)end.aretbaddm執(zhí)行addm時，a的活動記記錄已不不存在，，取不到到m的值6.3非局部名名字的訪訪問C語言的函函數(shù)聲明明不能嵌嵌套，函函數(shù)不論論在什么么情況下下激活，，要訪問問的數(shù)據(jù)據(jù)分成兩兩種情況況非靜靜態(tài)態(tài)局局部部變變量量（（包包括括形形式式參參數(shù)數(shù)）），，它它們們分分配外部變量（包括定義在其它源文件之中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)因此C語言允許函數(shù)（的指針）作為返回值6.3非局局部部名名字6.3.3動態(tài)態(tài)作作用用域域被調調用用過過程程的的非非局局部部名名字字a和它它在在調調用基于運行時的調用關系而不是基于靜態(tài)作用域來確定新的綁定僅為被調用過程的局部名字建立，這些名字在被調用過程的活動記錄中占用存儲單元這一點與靜態(tài)作用域沒有區(qū)別6.3非局局部部名名字字的的訪訪問問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局局部programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin靜態(tài)態(tài)作作用用域域show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局局部部名名字字programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin動態(tài)作用域show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局部名字的的訪問實現(xiàn)動態(tài)作用用域的方法深訪問用控制鏈搜索索運行棧，尋尋找包含該非非局部名字的的第一個活動動記錄淺訪問為每個名字在靜態(tài)分配的存存儲空間中保存它的當當前值當過程p的新活動出現(xiàn)現(xiàn)時，p的局部名字n使用在靜態(tài)數(shù)數(shù)據(jù)區(qū)分配給給n的存儲單元。。n的先前值保存存在p的活動記錄中，當p的活動結束時時再恢復6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow?r靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方dynamicr?6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?show靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?smallr0.25靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.125rdynamicr?smallr0.25靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方6.3非局部名字的的訪問programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(綠色表示已執(zhí)執(zhí)行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?靜態(tài)區(qū)使用值的地方棧區(qū)暫存值的地方6.4參數(shù)數(shù)傳傳遞遞值調用用實參的的右值值傳給給被調調用過過程值調用用可以以如下下實現(xiàn)現(xiàn)把形參參當作作所在在過程程的局局部名名看待待，形形參的的存儲儲單元元在該該過程程的活活動記記錄中中調用過過程計算實實參，，并把把其右右值放放入被調用用過程程形參的的存儲儲單元元中6.4參數(shù)數(shù)傳傳遞遞引用調調用實參的的左值值傳給給被調調用過過程引用調調用可可以如如下實實現(xiàn)：：把形參參當作作所在在過程程的局局部名名看待待，形形參的的存儲儲單元元在該該過程程的活活動記記錄中中調用過過程計算算實參參，把實參參的左左值放放入被被調用用過程程形參參的存存儲單單元在被調調用過過程的的目標標代碼碼中，，任何何對形形參的的引用用都是是通過過傳給給該過過程的的指針針來間間接引引用實實參6.4參數(shù)數(shù)傳傳遞遞換名調調用從概念念上說說，每每次調調用時時，用用實參參表達達式對對形參進進行正正文替替換，，然后后再執(zhí)執(zhí)行procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend6.4參數(shù)數(shù)傳傳遞遞換名調調用從概念念上說說，每每次調調用時時，用用實參參表達達式對對形參進進行正正文替替換，，然后后再執(zhí)執(zhí)行procedureswap(varx,y:integer);vartemp:integer;例如：：調用swap(i,a[i])begintemp:=x;x:=y;y:=tempend6.4參數(shù)數(shù)傳傳遞遞換名調調用從概念念上說說，每每次調調用時時，用用實參參表達達式對對形參進進行正正文替替換，，然后后再執(zhí)執(zhí)行procedureswap(varx,y:integer);vartemp:integer;例如：：調用swap(i,a[i])begin替換結結果：：temp:=i;temp:=x;i:=a[i];x:=y;a[i]:=tempy:=tempend6.4參數(shù)數(shù)傳傳遞遞換名調調用從概念念上說說，每每次調調用時時，用用實參參表達達式對對形參進進行正正文替替換，，然后后再執(zhí)執(zhí)行procedureswap(varx,y:integer);vartemp:integer;例如：：調用swap(i,a[i])begin替換結結果：：temp:=i;temp:=x;i:=a[i];x:=y;a[i]:=tempy:=temp交換兩兩個數(shù)數(shù)據(jù)的的程序序end并非總總是正正確6.5堆管管理理堆式式分分配配堆用用來來存存放放生生存存期期不不確確定定的的數(shù)數(shù)據(jù)據(jù)C++和Java允許許程程序序員員用用new創(chuàng)建建對對象象，，它它們們的的生生存存期期沒沒有有被被約約束束在在創(chuàng)創(chuàng)建建它它們們的的過過程程活活動動的的生生成成期期之之內內實現(xiàn)現(xiàn)內內存存回回收收是是內內存存管管理理器器的的責責任任堆空空間間的的回回收收有有兩兩種種不不同同方方式式程序序顯顯式式釋釋放放空空間間：：free（C）或或delete（C++）垃圾圾收收集集器器自自動動收收集集（（Java）。。11.3節(jié)介介紹紹垃垃圾圾收收集集算算法法，，本本課課程程不不做做介介紹紹6.5堆管管理理6.5.1內存存管管理理器器內存存管管理理器器把把握握的的基基本本信信息息是是堆堆中中空空閑閑空空間間分配配函函數(shù)數(shù)回收收函函數(shù)數(shù)內存存管管理理器器應應具具有有下下列列性性質質空間間有有效效性性：：極極小小化化程程序序需需要要的的堆堆空空間間總總量量程序有效性性：較好地地利用內存存子系統(tǒng)，，使得程序序能運行得得快一些低開銷：分配和回收收操作所花花時間在整整個程序執(zhí)執(zhí)行時間中中的比例盡盡量小6.5堆管理理6.5.2計算機內存存分層虛擬內存(磁盤)物理內存2級緩存1級緩存寄存器(處理器)典型大小>2千兆字節(jié)256兆2千兆字節(jié)128千4兆字節(jié)1664千字節(jié)32字典型訪問時間315微秒100150納秒4060納秒510納秒1納秒6.5堆管理理6.5.2計算機內存存分層現(xiàn)代計算機機都設計成成程序員不不用關心內內存子系統(tǒng)統(tǒng)的細節(jié)就就可以寫出出正確的程程序程序的效率率不僅取決決于被執(zhí)行行的指令數(shù)數(shù)，還取決決于執(zhí)行每每條指令需需要多長時時間執(zhí)行一條指指令的時間間區(qū)別非常?？捎^差異源于硬硬件技術的的基本局限限：構造不不了大容量量的高速存存儲器數(shù)據(jù)以塊（（緩存行、、頁）為單單位在相鄰鄰層次之間間進行傳送送數(shù)據(jù)密集型型程序可從從恰當利用用內存子系系統(tǒng)中獲益益6.5堆管理理6.5.3程序局部性性大多數(shù)程序序的大部分分時間在執(zhí)執(zhí)行一小部部分代碼，，并且僅涉涉及一小部部分數(shù)據(jù)時間局部性性程序訪問的的內存單元元在很短的的時間內可可能再次被被程序訪問問空間局部性性毗鄰被訪問問單元的內內存單元在在很短的時時間內可能能被訪問6.5堆管理理6.5.3程序局部性性即使知道哪哪些指令會會被頻繁執(zhí)執(zhí)行，最快快的緩存也也可能沒有有大到足以以把它們同同時放在其其中，因此必須須動態(tài)調整整最快緩存存的內容把最近使用用的指令保保存在緩存存是一種較較好的最優(yōu)優(yōu)化利用內內存分層的的策略改變數(shù)據(jù)布布局或計算算次序也可可以改進程程序數(shù)據(jù)訪訪問的時間間和空間局局部性6.5堆管理理例：一個個結構體大大數(shù)組分分拆成若干干個數(shù)組structstudent{intnum[10000];intnum;charname[10000][20];charname[20];…… …… …}structstudentst[10000];若是順序處處理每個結結構體的多多個域，左左邊方式的的數(shù)據(jù)局部部性較好若是先順序序處理每個個結構的num域，再處理理每個結構構的name域，…，則右邊方方式的數(shù)據(jù)據(jù)局部性較較好最好是按左左邊方式編編程，由編編譯器決定定是否需要要將數(shù)據(jù)按按右邊方式式布局6.5堆管理理6.5.4手工回收請請求程序員在程程序中顯式式釋放堆塊塊來達到回回收堆塊的的目的內存泄漏：：沒有釋放放程序已經(jīng)經(jīng)引用不到到的堆塊只要內存沒沒有用盡，，它就不影影響程序的的正確性自動無用單單元收集通通過回收所所有無用單單元來擺脫脫內存泄漏漏懸空引用：：引用已經(jīng)經(jīng)被釋放的的堆塊過分熱心地地釋放數(shù)據(jù)據(jù)對象而引引起懸空引用容容易導致不不會被捕獲獲的錯誤本章要要點點影響存儲分分配策略的的語言特征征各種存儲分分配策略，，主要了解解靜態(tài)分配配和動態(tài)棧棧式分配活動記錄中各種數(shù)據(jù)域的作用和布局非局部數(shù)據(jù)訪問的實現(xiàn)方法各種參數(shù)傳遞方式及其實現(xiàn)堆管理例題題1一個C語言程序及及其在X86/Linux操作系統(tǒng)上上的編譯結結果如下。根根據(jù)所生成成的匯編程程序來解釋釋程序中四四個變量的存儲分分配、生存存期、作用用域和置初初值方式等等方面的區(qū)別staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data|.align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2| ...bb:|movw$40,-2(%ebp).value20 |...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data| .align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2| ...bb:|movw$40,-2(%ebp).value20 |...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data| .align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2|...bb:|movw$40,-2(%ebp).value20|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2|...bb:|movw$40,-2(%ebp).value20|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2|...bb:|movw$40,-2(%ebp).value20|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2|...bb:|movw$40,-2(%ebp).value20|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例題題2func(i)longi;{longj;j=i-1;func(j);}例題題2func(i)func:longi;pushl%ebp老的基基地址址指針針壓棧棧{movl%esp,%ebp修改基地址址指針針longj;subl$4,%esp為j分配空空間j=i-1;movl8(%ebp),%edx取i到寄存器器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參參j的值壓壓棧callfunc函數(shù)調調用addl$4,%esp恢復棧棧頂指指針L1:leave即movebp,esp;popebpret即popeip(下條指令令地址））...參數(shù)i返址控制鏈變量j...ebp

esp

棧低高例題題2func(i)func:longi;pushl%ebp老的基地地址指針針壓棧{movl%esp,%ebp修改基地址指指針longj;subl$4,%esp為j分配空間間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參j的值壓棧棧callfunc函數(shù)調用用addl$4,%esp恢復棧頂頂指針L1:leave即movebp,esp;popebpret即popeip(下條指令令地址））......ebp

esp

例題題2func(i)func:longi;pushl%ebp老的基地地址指針針壓棧{movl%esp,%ebp修改基地址指指針longj;subl$4,%esp為j分配空間間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參j的值壓棧棧callfunc函數(shù)調用用addl$4,%esp恢復棧頂頂指針L1:leave即movebp,esp;popebpret即popeip(下條指令令地址））......ebp

esp

參數(shù)i例題題2func(i)func:longi;pushl%ebp老的基地地址指針針壓棧{movl%esp,%ebp修改基地址指指針longj;subl$4,%esp為j分配空間間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參j的值壓棧棧callfunc函數(shù)調用用addl$4,%esp恢復棧頂頂指針L1:leave即movebp,esp;popebpret即popeip(下條指令地地址）......ebp

esp

參數(shù)i返址例題題2func(i)func:longi;pushl%ebp老的基地址址指針壓棧棧{movl%esp,%ebp修改基地址指針針longj;subl$4,%esp為j分配空間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參j的值壓棧callfunc函數(shù)調用addl$4,%esp恢復棧頂指指針L1:leave即movebp,esp;popebpret即popeip(下條指令地地址）......ebp

esp

參數(shù)i返址控制鏈例題題2func(i)func:longi;pushl%ebp老的基地址址指針壓棧棧{movl%esp,%ebp修改基地址指針針longj;subl$4,%esp為j分配空間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把實參j的值壓棧callfunc函數(shù)調用addl$4,%esp恢復棧頂指指針L1:leave即movebp,esp;popebpret即popeip(下條指令地地址）......ebp

esp

參數(shù)i返址控制鏈例題題2func(i)func:longi;pushl%ebp老的基地址址指針壓棧棧{movl%esp,%ebp修改基地址指針針longj;subl$4,%esp為j分配空間j=i-1;movl8(%ebp),%edx取i到寄存器func(j);decl%edxi–1}movl%edx,-4(%ebp)i–