編譯原理運行時存儲空間的組織和管理學習培訓模板課件

1、第六章 運行時存儲空間的組織和管理 過程的活動過程的一次執(zhí)行稱為過程的一次活動第六章 運行時存儲空間的組織和管理 過程的活動過程的一次執(zhí)行稱為過程的一次活動活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間,后者稱為活動記錄第六章 運行時存儲空間的組織和管理 過程的活動過程的一次執(zhí)行稱為過程的一次活動活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間,后者稱為活動記錄本章內(nèi)容討論一個活動記錄中的數(shù)據(jù)安排第六章 運行時存儲空間的組織和管理 過程的活動過程的一次執(zhí)行稱為過程的一次活動活動記錄過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間,后者稱為活動記錄本章內(nèi)容討論一個活動記錄中的數(shù)

2、據(jù)安排程序執(zhí)行過程中，所有活動記錄的組織方式 第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式第六章 運行時存儲空間的組織和管理 影響

3、存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲塊能否在程序控制下動態(tài)

4、地分配第六章 運行時存儲空間的組織和管理 影響存儲分配策略的語言特征 過程能否遞歸當控制從過程的活動返回時，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲塊能否在程序控制下動態(tài)地分配存儲塊是否必須顯式地釋放6.1 局部存儲分配6.1.1 過程過程定義、過程調(diào)用、形式參數(shù)、實在參數(shù)、活動的生存期6.1 局部存儲分配6.1.2 名字的作用域和綁定名字的作用域一個聲明起作用的程序部分稱為該聲明的作用域即使一個名字在程序中只聲明一次，該名字在程序運行時也可能表示不同的數(shù)據(jù)對象6.1 局部存儲分配從名字到值的兩步映射名字存儲單元狀態(tài)值環(huán)

5、境6.1 局部存儲分配從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值名字存儲單元狀態(tài)值環(huán)境6.1 局部存儲分配從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值賦值改變狀態(tài)，但不改變環(huán)境 名字存儲單元狀態(tài)值環(huán)境6.1 局部存儲分配從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值賦值改變狀態(tài)，但不改變環(huán)境 過程調(diào)用改變環(huán)境名字存儲單元狀態(tài)值環(huán)境6.1 局部存儲分配從名字到值的兩步映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值賦值改變狀態(tài)，但不改變環(huán)境 過程調(diào)用改變環(huán)境如果環(huán)境將名字x映射到存儲單元s，我們就說x被綁定到s名字存儲單元狀態(tài)值環(huán)境6.

6、1 局部存儲分配靜態(tài)概念和動態(tài)概念的對應靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 6.1 局部存儲分配靜態(tài)概念和動態(tài)概念的對應靜 態(tài) 概 念 動 態(tài) 對 應 過程的定義 過程的活動 名字的聲明 名字的綁定 6.1 局部存儲分配靜態(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ù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位6.1 局部存儲分

7、配6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定6.1 局部存儲分配6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間6.1 局部存儲分配6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示6.1 局部存儲分配6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單

8、位變量所需的存儲空間可以根據(jù)其類型而靜態(tài)確定一個過程所聲明的局部變量，按這些變量聲明時出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間局部數(shù)據(jù)的地址可以用相對于某個位置的地址來表示數(shù)據(jù)對象的存儲安排還有一個對齊問題6.1 局部存儲分配在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的size分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a; b;6.1 局部存儲分配在SPARC/Solaris工作站上下面兩個結(jié)構(gòu)的si

9、ze分別是24和16，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1charc2;8 long i; 4double f;16 double f; 8a; b;6.1 局部存儲分配在X86/Linux機器的結(jié)果和SPARC/Solaris工作站不一樣，是20和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1charc2;8 long i; 4double f;12 double f;

10、 8a; b;6.1 局部存儲分配6.1.5 程序塊本身含有局部變量聲明的語句可以嵌套最接近的嵌套作用域規(guī)則并列程序塊不會同時活躍并列程序塊的變量可以重疊分配6.1 局部存儲分配main() / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /6.1 局部存儲分配main() / begin of B0 /

11、 int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 6.1 局部存儲分配main() / begin of B0 / int a = 0; int b = 0; /

12、 begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲單元 6.2 全局棧式存儲分配介紹程序運行時所需的各個活動記錄在存儲空間的分配策略6.2 全局棧式存儲分配介紹程序運行時所需

13、的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲單元6.2 全局棧式存儲分配介紹程序運行時所需的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲單元介紹三種分配策略靜態(tài)分配策略6.2 全局棧式存儲分配介紹程序運行時所需的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲單元介紹三種分配策略靜態(tài)分配策略棧式分配策略6.2 全局棧式存儲分配介紹程序運行時所需的各個活動記錄在存儲空間的分配策略描述過程的目標代碼怎樣訪問綁定到局部名字的存儲單元介紹三種分配策略靜態(tài)分配策略棧式分配策略堆式分配策略6.2 全局棧式存

14、儲分配6.2.1 運行時內(nèi)存的劃分代 碼靜 態(tài) 數(shù) 據(jù)堆棧6.2 全局棧式存儲分配靜態(tài)分配名字在程序被編譯時綁定到存儲單元，不需要運行時的任何支持6.2 全局棧式存儲分配靜態(tài)分配名字在程序被編譯時綁定到存儲單元，不需要運行時的任何支持綁定的生存期是程序的整個運行期間6.2 全局棧式存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許6.2 全局棧式存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的6.2 全局棧式存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時可以知道的數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立6.

15、2 全局棧式存儲分配 C語言程序的外部變量和程序中出現(xiàn)的常量都可以靜態(tài)分配聲明在函數(shù)外面外部變量 靜態(tài)分配靜態(tài)外部變量 靜態(tài)分配聲明在函數(shù)里面靜態(tài)局部變量 也是靜態(tài)分配自動變量 不能靜態(tài)分配6.2 全局棧式存儲分配6.2.2 活動樹和運行?；顒訕?用樹來描繪控制進入和離開活動的方式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 全局棧式存儲分配活動樹的特點每個結(jié)點代表某過程的一個活動根結(jié)點代表主程序的活動結(jié)點a是結(jié)點b的父結(jié)點，當且僅當控制

16、流從a的活動進入b的活動結(jié)點a處于結(jié)點b的左邊，當且僅當a的生存期先于b的生存期6.2 全局棧式存儲分配當前活躍著的過程活動可以保存在一個棧中控制棧的內(nèi)容：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 全局棧式存儲分配運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） 6.2 全局棧式存儲分配運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息

17、（即活動記錄） ma : arraym6.2 全局棧式存儲分配運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） mi: integerra : arraymr6.2 全局棧式存儲分配運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） mk: integerq (1, 9)a : arraymq(1,9)r6.2 全局棧式存儲分配運行棧：把控制棧中的信息拓廣到包括過程活動所需的所有局部信息（即活動記錄） mk: integerq (1, 9)a : arrayq (1, 3)k: integermq(1,9)rp(1,9)q(1,3)q(1,0)

18、p(1,3)6.2 全局棧式存儲分配6.2.3 調(diào)用序列過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復機器狀態(tài)等6.2 全局棧式存儲分配6.2.3 調(diào)用序列過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復機器狀態(tài)等過程調(diào)用序列過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼6.2 全局棧式存儲分配6.2.3 調(diào)用序列過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復機器狀態(tài)等過程調(diào)用序列過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼過程返回序列過程返回時執(zhí)行的恢復機器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼6.2 全局棧式存

19、儲分配過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動記錄棧，保存或恢復機器狀態(tài)等過程調(diào)用序列過程調(diào)用時執(zhí)行的分配活動記錄，把信息填入它的域中的代碼過程返回序列過程返回時執(zhí)行的恢復機器狀態(tài)，釋放活動記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則返 回 值臨 時 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序

20、，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則以活動記錄中間的某個位置作為基地址返 回 值臨 時 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則以活動記錄中間的某個位置作為基地址長度能較早確定的域放在活動記錄的中間返 回 值臨 時 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則一般把臨時數(shù)據(jù)域

21、放在局部數(shù)據(jù)域的后面返 回 值臨 時 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則一般把臨時數(shù)據(jù)域放在局部數(shù)據(jù)域的后面把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動記錄的地方返 回 值臨 時 數(shù) 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配即使是同一種語言，過程調(diào)用序列、返回序列和活動記錄中各域的排放次序，也會因?qū)崿F(xiàn)而異設計這些序列和活動記錄的一些原則用同樣的代碼來執(zhí)行各個活動的保存和恢復返 回 值臨 時 數(shù)

22、 據(jù)參 數(shù)控 制 鏈訪 問 鏈機 器 狀 態(tài)局 部 數(shù) 據(jù)6.2 全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務劃分被調(diào)用者的責任調(diào)用者的責任調(diào)用者的活動記錄被調(diào)用者的活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機器狀態(tài)top_sp base_sp 棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機器狀態(tài) 6.2 全局棧式存儲分配過程p調(diào)用過程q的調(diào)用序列p計算實參，依次放入棧頂，并在棧頂留出放返回值的空間。top_sp的值在此過程中被改變p把返回地址和當前base_sp的值存入q的活動記錄中，建立q的訪問鏈，增加base_sp的值q保存寄存器的值和其它機器狀態(tài)信息q根據(jù)局部數(shù)據(jù)域

23、和臨時數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體6.2 全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務劃分被調(diào)用者的責任調(diào)用者的責任調(diào)用者的活動記錄被調(diào)用者的活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機器狀態(tài)top_sp base_sp 棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機器狀態(tài) 6.2 全局棧式存儲分配過程p調(diào)用過程q的返回序列q把返回值置入鄰近p的活動記錄的地方q對應調(diào)用序列的步驟（4），減小top_sp的值 q恢復寄存器（包括base_sp）和機器狀態(tài)，返回pp根據(jù)參數(shù)個數(shù)與類型和返回值類型調(diào)整top_sp，然后取出返回值6.2 全

24、局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務劃分被調(diào)用者的責任調(diào)用者的責任調(diào)用者的活動記錄被調(diào)用者的活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機器狀態(tài)top_sp base_sp 棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機器狀態(tài) 6.2 全局棧式存儲分配過程的參數(shù)個數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進棧的代碼被調(diào)用函數(shù)能準確地知道第一個參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個參數(shù)到棧中取第二、第三個參數(shù)等等6.2 全局棧式存儲分配調(diào)用者和被調(diào)用者之間的任務劃分被調(diào)用者的責任調(diào)用者的責任調(diào)用者的活動記錄被調(diào)用者的活動記錄臨時數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和

25、參數(shù) 控制鏈 和保存的機器狀態(tài)top_sp base_sp 棧增長方向臨時數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機器狀態(tài) 6.2 全局棧式存儲分配6.2.4 棧上可變長數(shù)據(jù)活動記錄的長度在編譯時不能確定的情況局部數(shù)組的大小要等到過程激活時才能確定在活動記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運行時，這些指針指向分配在棧頂?shù)拇鎯臻g6.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.5 懸空引用懸空引用：引用某個已被釋放的存儲單元6.2 全

26、局棧式存儲分配6.2.5 懸空引用懸空引用：引用某個已被釋放的存儲單元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( );|return &j;|6.3 非局部名字的訪問本節(jié)介紹無過程嵌套的靜態(tài)作用域（C語言）有過程嵌套的靜態(tài)作用域（Pascal語言）動態(tài)作用域（Lisp語言）6.3 非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址6.3 非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指

27、針來訪問6.3 非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈6.3 非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域過程體中的非局部引用可以直接使用靜態(tài)確定的地址局部變量在棧頂?shù)幕顒佑涗浿?，可以通過base_sp指針來訪問無須深入棧中取數(shù)據(jù)，無須訪問鏈過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回6.3 非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域sortreadarrayexchangequicksortpartition6.3 非局部名字的訪問

28、6.3.2 有過程嵌套的靜態(tài)作用域過程嵌套深度sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域過程嵌套深度sort1readarray2exchange2quicksort2partition3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度6.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,

29、 3)i, j訪問鏈e (1, 3)訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈p (1, 3)i, j訪問鏈6.3 非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何訪問a的存儲單元sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何訪問a的存儲單元從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次6.3 非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何

30、訪問a的存儲單元從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次到達a的聲明所在過程的活動記錄6.3 非局部名字的訪問假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何訪問a的存儲單元從棧頂?shù)幕顒佑涗涢_始，追蹤訪問鏈np na次到達a的聲明所在過程的活動記錄訪問鏈的追蹤用間接操作就可完成6.3 非局部名字的訪問訪問非局部名字的存儲單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (

31、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 非局部名字的訪問過程p對變量a訪問時，a的地址由下面的二元組表示：（np na，a在活動記錄中的偏移）6.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況x肯定就聲明在p中6.

32、3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況x肯定就聲明在p中被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動記錄的訪問鏈6.3 非局部名字的訪問建立訪問鏈sort readarray exchange quicksort partitionsa, 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,

33、 3)i, j訪問鏈6.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況sort1readarray2exchange2quicksort2partition36.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況p和x的嵌套深度分別為1，2，nx 1的外圍過程肯定相同6.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況p和x的嵌套深度分別為1，2，nx 1的外圍過程肯定相同追蹤訪問鏈np nx + 1次，到達了靜態(tài)包圍x和p的且離它們最近的那個過

34、程的最新活動記錄6.3 非局部名字的訪問建立訪問鏈假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程xnp nx的情況p和x的嵌套深度分別為1，2，nx 1的外圍過程肯定相同追蹤訪問鏈np nx + 1次，到達了靜態(tài)包圍x和p的且離它們最近的那個過程的最新活動記錄所到達的活動記錄就是x的活動記錄中的訪問鏈應該指向的那個活動記錄6.3 非局部名字的訪問建立訪問鏈sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q (1, 9)k, v訪問鏈sa, xq (1, 3)k, v訪問鏈q

35、 (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 非局部名字的訪問program param(input, output);（過程作為參數(shù)）procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin

36、m := 0; b(f) end c; begin cend.6.3 非局部名字的訪問program param(input, output);（過程作為參數(shù)）procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈6

37、.3 非局部名字的訪問program param(input, output);（過程作為參數(shù)）procedure b(function h(n: integer): integer); begin writeln(h(2) end b;procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin cend.過程作為參數(shù)傳遞時，怎樣在該過程被激活時建立它的訪問鏈 從b的訪問鏈難以建立f的訪問鏈6.3 非局部名字的訪問progr

38、am param(input, output);（過程作為參數(shù)）procedure b(function h( begin writeln(h(2) end ;procedure c; var m: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend.訪 問 鏈訪 問 鏈paramcmb 6.3 非局部名字的訪問program ret (input, output);（過程作為返回值） var f: function (integer): integer;funct

39、ion a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln ( g(2) end; begin f := a; b(f) end.6.3 非局部名字的訪問program ret (input, output);（過程作為返回值） var f: functio

40、n (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln ( g(2) end; begin f := a; b(f) end.retabaddm6.3 非局部名字的訪問C語言的函數(shù)聲明不能嵌套，函數(shù)不論

41、在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況:非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動記錄棧頂?shù)哪莻€活動記錄中外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū) 6.3 非局部名字的訪問6.3.3 動態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲單元6.3 非局部名字的訪問6.3.3 動態(tài)作用域被調(diào)用過程的非局部名字a和它在調(diào)用過程中引用的是同樣的存儲單元新的綁定僅為被調(diào)用過程的局部名字建立，這些名字在被調(diào)用過程的活動記錄中占用的存儲單元6.3 非局部名字的訪問program dynamic(input, output); var r:

42、 real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real;

43、begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin靜態(tài)作用域 r := 0.

44、25;0.2500.250 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin動態(tài)作用域 r := 0.25;0.250 0.125 show;

45、small; writeln;0.250 0.125 show; small; writeln end.dynamicshowsmallsmallshowshowshow6.3 非局部名字的訪問實現(xiàn)動態(tài)作用域的方法深訪問用控制鏈搜索運行棧，尋找包含該非局部名字的第一個活動記錄淺訪問為每個名字在靜態(tài)分配的存儲空間中保存它的當前值當過程p的新活動出現(xiàn)時，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的存儲單元。n的先前值可以保存在p的活動記錄中，當p的活動結(jié)束時再恢復6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure sho

46、w; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow?r 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方dynamicr?6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; b

47、egin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr? 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r:

48、 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?show 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) en

49、d; procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr?smallr0.25 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end;

50、procedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.125rdynamicr?smallr0.25 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方6.3 非局部名字的訪問program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; pr

51、ocedure small; var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0.25rdynamicr? 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方6.4 參 數(shù) 傳 遞6.4.1 值調(diào)用實參的右值傳給被調(diào)用過程 值調(diào)用可以如下實現(xiàn)把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中6.4 參 數(shù) 傳 遞6.4.1 值調(diào)用實參的右值傳給被調(diào)用過程 值調(diào)用可以如

52、下實現(xiàn)把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中調(diào)用過程計算實參，并把其右值放入形參的存儲單元中6.4 參 數(shù) 傳 遞6.4.2 引用調(diào)用實參的左值傳給被調(diào)用過程 引用調(diào)用可以如下實現(xiàn)：把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中調(diào)用過程計算實參，把實參的左值放入形參的存儲單元6.4 參 數(shù) 傳 遞6.4.2 引用調(diào)用實參的左值傳給被調(diào)用過程 引用調(diào)用可以如下實現(xiàn)：把形參當作所在過程的局部名看待，形參的存儲單元在該過程的活動記錄中調(diào)用過程計算實參，把實參的左值放入形參的存儲單元在被調(diào)用過程的目標代碼中，任何對形參的引用都是通過傳給該過程的指針來間接

53、引用實參6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用用實參表達式對形參進行正文替換procedure s x, y: integer);var temp: integer; begin temp := x; x := y; y := temp end6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用用實參表達式對形參進行正文替換procedure s x, y: integer);var temp: integer; begin 調(diào)用swap(i, ai) temp := x; x := y; y := temp end6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用用實參表達式對形參進行正文替換proced

54、ure s x, y: integer);var temp: integer; begin 調(diào)用swap(i, ai) temp := x;temp := i; x := y;i := ai; y := tempai := temp end6.5 堆 管 理堆式分配堆用來存放生存期不確定的數(shù)據(jù) C+和Java允許程序員用new創(chuàng)建對象，它們的生存期沒有被約束在創(chuàng)建它們的過程活動的生成期之內(nèi)實現(xiàn)內(nèi)存回收是內(nèi)存管理器的責任堆空間的回收有兩種不同方式 程序顯式釋放空間：free（C）或delete（C+） 垃圾收集器自動收集（Java）6.5 堆 管 理6.5.1 內(nèi)存管理器內(nèi)存管理器把握的基本信息

55、是堆中空閑空間 分配函數(shù) 回收函數(shù)內(nèi)存管理器應具有下列性質(zhì) 空間有效性：極小化程序需要的堆空間總量 程序有效性：較好地利用內(nèi)存子系統(tǒng)，使得程序能運行得快一些 低開銷：分配和回收操作所花時間在整個程序執(zhí)行時間中的比例盡量小6.5 堆 管 理6.5.2 計算機內(nèi)存分層虛擬內(nèi)存(磁盤)物理內(nèi)存2級緩存1級緩存寄存器(處理器)典型大小 2千兆字節(jié)256兆2千兆字節(jié)128千4兆字節(jié)1664千字節(jié)32字典型訪問時間315微秒100150納秒4060納秒510納秒1納秒6.5 堆 管 理6.5.2 計算機內(nèi)存分層 現(xiàn)代計算機都設計成程序員不用關心內(nèi)存子系統(tǒng)的細節(jié)就可以寫出正確的程序 程序的效率不僅取決于被執(zhí)

56、行的指令數(shù)，還取決于執(zhí)行每條指令需要多長時間 執(zhí)行一條指令的時間區(qū)別非?？捎^ 差異源于硬件技術(shù)的基本局限：構(gòu)造不了大容量的高速存儲器 數(shù)據(jù)以塊（緩存行、頁）為單位在相鄰層次之間進行傳送 數(shù)據(jù)密集型程序可從恰當利用內(nèi)存子系統(tǒng)中獲益6.5 堆 管 理6.5.3 程序局部性大多數(shù)程序的大部分時間在執(zhí)行一小部分代碼，并且僅涉及一小部分數(shù)據(jù)時間局部性 程序訪問的內(nèi)存單元在很短的時間內(nèi)可能再次被程序訪問空間局部性毗鄰被訪問單元的內(nèi)存單元在很短的時間內(nèi)可能被訪問6.5 堆 管 理6.5.3 程序局部性 從代碼本身很難看出哪部分代碼會被頻繁使用,必須動態(tài)調(diào)整最快緩存的內(nèi)容 把最近使用的指令保存在緩存是一種較好

57、的最優(yōu)化利用內(nèi)存分層的策略 改變數(shù)據(jù)布局或計算次序也可以改進程序數(shù)據(jù)訪問的時間和空間局部性6.5 堆 管 理6.5.4 手工回收請求程序員在程序中顯式釋放堆塊來達到回收堆塊的目的 內(nèi)存泄漏：沒有釋放已經(jīng)引用不到的堆塊 只要內(nèi)存沒有用盡，它就不影響程序的正確性 自動無用單元收集通過回收所有無用單元來擺脫內(nèi)存泄漏懸空引用：引用已經(jīng)被釋放的堆塊 過分熱心地釋放數(shù)據(jù)對象而引起 懸空引用容易導致不會被捕獲的錯誤 本 章 要 點影響存儲分配策略的語言特征各種存儲分配策略，主要了解靜態(tài)分配和動態(tài)棧式分配活動記錄中各種數(shù)據(jù)域的作用和安排非局部數(shù)據(jù)訪問的實現(xiàn)方法各種參數(shù)傳遞方式及其實現(xiàn)堆管理例 題 1一個C語言

58、程序及其在X86/Linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個變量的存儲分配、作用域、生存期和置初值方式等方面的區(qū)別static long aa = 10;short bb = 20;func() static long cc = 30; short dd = 40;例 題 1.data|.align 4.align 4|.type cc.2,object.type aa,object|.size cc.2,4.size aa,4| cc.2:aa:|.long 30.long 10| .text.globl bb|.align 4.align 2| .globl

59、func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例 題 2main()char *cp1, *cp2;cp1 = 12345;cp2 = abcdefghij;strcpy(cp1,cp2);printf(cp1 = %sncp2 = %sn, cp1, cp2);在某些系統(tǒng)上的運行結(jié)果是：cp1 = abcdefghijcp2 = ghij為什么cp2所指的串被修改了？例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b

60、c d e f g h i j 0 cp1 cp2例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2執(zhí)行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2例 題 2因為常量串“12345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前：1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2執(zhí)行后：a b c d e f g h i j 0 f g h i j 0 cp1 cp2現(xiàn)在的編譯器大都把程序中的串常量單獨存