編譯原理第六章運(yùn)行時(shí)存儲(chǔ)空間的組織和管理

1、第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 術(shù)語術(shù)語過程的過程的活動(dòng)活動(dòng)過程的一次執(zhí)行稱為過程的一次活動(dòng)過程的一次執(zhí)行稱為過程的一次活動(dòng) 活動(dòng)記錄活動(dòng)記錄過程的活動(dòng)需要可執(zhí)行代碼和存放所需信息的存儲(chǔ)空間過程的活動(dòng)需要可執(zhí)行代碼和存放所需信息的存儲(chǔ)空間, ,后者稱為活動(dòng)記錄后者稱為活動(dòng)記錄本章內(nèi)容本章內(nèi)容 討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)布局討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)布局 程序執(zhí)行過程中，所有活動(dòng)記錄的組織方式程序執(zhí)行過程中，所有活動(dòng)記錄的組織方式 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 影響存儲(chǔ)分配策略的語言特征影響存儲(chǔ)分配策略的語言特征 過程能否遞歸

2、過程能否遞歸 當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要保留當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要保留 過程能否訪問非局部變量過程能否訪問非局部變量 過程調(diào)用的參數(shù)傳遞方式過程調(diào)用的參數(shù)傳遞方式 過程能否作為參數(shù)被傳遞過程能否作為參數(shù)被傳遞 過程能否作為結(jié)果值傳遞過程能否作為結(jié)果值傳遞 存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配存儲(chǔ)塊是否必須顯式地釋放存儲(chǔ)塊是否必須顯式地釋放6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配6.1.1 過程過程語言概念：語言概念：過程定義、過程定義、過程過程調(diào)用、形式參數(shù)、實(shí)在參調(diào)用、形式參數(shù)、實(shí)在參數(shù)、數(shù)、活動(dòng)的活動(dòng)的生存期生存期6.1 局部存儲(chǔ)

3、分配局部存儲(chǔ)分配6.1.2 名字的作用域和綁定名字的作用域和綁定1、名字的作用域、名字的作用域 一個(gè)聲明起作用的程序部分稱為該聲明的一個(gè)聲明起作用的程序部分稱為該聲明的作作用域用域6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配2、環(huán)境和狀態(tài)、環(huán)境和狀態(tài) 環(huán)境把名字映射到左值，而狀態(tài)把左值映射環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值（即到右值（即名字到值有兩步映射名字到值有兩步映射） 賦值改變狀態(tài)，但不改變環(huán)境賦值改變狀態(tài)，但不改變環(huán)境 過程調(diào)用改變環(huán)境過程調(diào)用改變環(huán)境 如果環(huán)境將名字如果環(huán)境將名字x映射到存儲(chǔ)單元映射到存儲(chǔ)單元s，則說則說x被被綁定綁定到到s名字名字存儲(chǔ)單元存儲(chǔ)單元狀態(tài)狀態(tài)值值環(huán)境環(huán)境6

4、.1 局部存儲(chǔ)分配局部存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜靜 態(tài)態(tài) 概概 念念 動(dòng)動(dòng) 態(tài)態(tài) 對(duì)對(duì) 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動(dòng)過程的活動(dòng) 6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜靜 態(tài)態(tài) 概概 念念 動(dòng)動(dòng) 態(tài)態(tài) 對(duì)對(duì) 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動(dòng)過程的活動(dòng) 名字的聲明名字的聲明 名字的綁定名字的綁定 6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配3、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)、靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜靜 態(tài)態(tài) 概概 念念 動(dòng)動(dòng) 態(tài)態(tài) 對(duì)對(duì) 應(yīng)應(yīng) 過程的定義過程的定義 過程的活動(dòng)過程的活動(dòng) 名字的聲明名字的聲明 名

5、字的綁定名字的綁定 聲明的作用域聲明的作用域 綁定的生存期綁定的生存期 6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配6.1.3 活動(dòng)記錄活動(dòng)記錄活動(dòng)記錄的常見布局活動(dòng)記錄的常見布局返返 回回 值值臨臨 時(shí)時(shí) 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配6.1.4 局部數(shù)據(jù)的布局局部數(shù)據(jù)的布局 字節(jié)是可編址內(nèi)存的最小單位字節(jié)是可編址內(nèi)存的最小單位 一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間 局部數(shù)據(jù)的地址可以

6、用相對(duì)于某個(gè)位置的地址來表局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示示 數(shù)據(jù)對(duì)象的存儲(chǔ)布局還有一個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)布局還有一個(gè)對(duì)齊問題對(duì)齊問題6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配 例例 在在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)體的工作站上下面兩個(gè)結(jié)構(gòu)體的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;char c2; long i;double f; double f;a; b;對(duì)齊：對(duì)齊：char : 1, long : 4, doub

7、le : 86.1 局部存儲(chǔ)分配局部存儲(chǔ)分配 例例 在在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)體的工作站上下面兩個(gè)結(jié)構(gòu)體的size分別是分別是24和和16，為什么不一樣？，為什么不一樣？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1char c2;8 long i; 4double f;16 double f; 8a; b;對(duì)齊：對(duì)齊：char : 1, long : 4, double : 86.1 局部存儲(chǔ)分配局部存儲(chǔ)分配 例例 在在X86/Linux機(jī)器的結(jié)果和機(jī)器的結(jié)果和SPARC

8、/Solaris工作工作站不一樣，是站不一樣，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1char c2;8 long i; 4double f;12 double f; 8a; b;對(duì)齊：對(duì)齊：char : 1, long : 4, double : 46.1 局部存儲(chǔ)分配局部存儲(chǔ)分配6.1.5 程序塊程序塊 本身含有局部變量聲明的語句本身含有局部變量聲明的語句 可以嵌套可以嵌套 最接近的嵌套最接近的嵌套作用域規(guī)則作用域規(guī)則 并列程序塊不會(huì)同時(shí)活躍并列程序塊不會(huì)同時(shí)活躍 并列程

9、序塊的變量可以重疊分配并列程序塊的變量可以重疊分配6.1 局部存儲(chǔ)分配局部存儲(chǔ)分配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 /聲聲 明明 作作 用用 域域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a =

10、 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲(chǔ)單元重疊分配存儲(chǔ)單元 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配本節(jié)介紹本節(jié)介紹 描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元儲(chǔ)單元 介紹三種分配策略介紹三種分配策略 靜態(tài)分配策略靜態(tài)分配策略 棧式分配策略棧式分配策略 堆式分配策略堆式分配策略6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.1 運(yùn)行時(shí)內(nèi)存的劃分運(yùn)行時(shí)內(nèi)存的劃分代代 碼碼靜靜 態(tài)態(tài) 數(shù)數(shù) 據(jù)據(jù)堆堆棧棧6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、靜態(tài)分配、靜態(tài)分配 名字在程序被編譯時(shí)綁定到存儲(chǔ)單元，不需名字在程

11、序被編譯時(shí)綁定到存儲(chǔ)單元，不需要運(yùn)行時(shí)的任何支持要運(yùn)行時(shí)的任何支持 綁定的生存期是程序的整個(gè)運(yùn)行期間綁定的生存期是程序的整個(gè)運(yùn)行期間6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、靜態(tài)分配給語言帶來限制、靜態(tài)分配給語言帶來限制 遞歸過程不被允許遞歸過程不被允許 數(shù)據(jù)對(duì)象的長度和它在內(nèi)存中位置的限制，數(shù)據(jù)對(duì)象的長度和它在內(nèi)存中位置的限制，必須是在編譯時(shí)可以知道的必須是在編譯時(shí)可以知道的 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 例例 C程序的外部變量、靜態(tài)局部變量以及程程序的外部變量、靜態(tài)局部變量以及程序中出現(xiàn)的常量都可以靜態(tài)分配序中出現(xiàn)的常量都可以靜態(tài)分配

12、聲明在函數(shù)外面聲明在函數(shù)外面外部變量外部變量 靜態(tài)分配靜態(tài)分配靜態(tài)外部變量靜態(tài)外部變量 靜態(tài)分配靜態(tài)分配 聲明在函數(shù)里面聲明在函數(shù)里面靜態(tài)局部變量靜態(tài)局部變量 也是靜態(tài)分配也是靜態(tài)分配自動(dòng)變量自動(dòng)變量 不能靜態(tài)分配不能靜態(tài)分配6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.2 活動(dòng)樹和運(yùn)行?；顒?dòng)樹和運(yùn)行棧1、活動(dòng)樹、活動(dòng)樹用樹來描繪控制進(jìn)入和離開活動(dòng)的方式用樹來描繪控制進(jìn)入和離開活動(dòng)的方式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 全局

13、棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 活動(dòng)樹的特點(diǎn)活動(dòng)樹的特點(diǎn)每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)根結(jié)點(diǎn)代表主程序的活動(dòng)根結(jié)點(diǎn)代表主程序的活動(dòng)結(jié)點(diǎn)結(jié)點(diǎn)a是結(jié)點(diǎn)是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的的活動(dòng)進(jìn)入活動(dòng)進(jìn)入b的活動(dòng)的活動(dòng)結(jié)點(diǎn)結(jié)點(diǎn)a處于結(jié)點(diǎn)處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)?shù)淖筮?，?dāng)且僅當(dāng)a的生存期先的生存期先于于b的生存期的生存期6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中 例例 控制棧的內(nèi)容：控制棧的內(nèi)容：m, q (1, 9), q (1, 3), q (2, 3) mq(1,9

14、)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 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、運(yùn)行棧：、運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、運(yùn)行棧：、運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） ma : arraym6

15、.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、運(yùn)行棧：、運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mint ira : arraymr6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、運(yùn)行棧：、運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mq(1,9)rmint iq (1, 9)a : arrayint m, n6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、運(yùn)行棧：、運(yùn)行棧：把控制棧中的信息拓廣到包括過程把控

16、制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄）活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)q (1, 9)mint ia : arrayint m, nint m, nint iq (1, 3)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.3 調(diào)用序列調(diào)用序列 過程調(diào)用序列過程調(diào)用序列過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄、把信息填入域中的代碼過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄、把信息填入域中的代碼 過程返回序列過程返回序列過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠

17、繼續(xù)執(zhí)行的代碼程能夠繼續(xù)執(zhí)行的代碼6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配 即使是同一種語言，過程調(diào)用序列、返回序列和活即使是同一種語言，過程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄的原則設(shè)計(jì)這些序列和活動(dòng)記錄的原則調(diào)用者和被調(diào)用者交流的數(shù)據(jù)放在調(diào)用者和被調(diào)用者交流的數(shù)據(jù)放在活動(dòng)記錄開始處，并盡可能靠近調(diào)用活動(dòng)記錄開始處，并盡可能靠近調(diào)用者的活動(dòng)記錄者的活動(dòng)記錄固定長度的項(xiàng)放在活動(dòng)記錄中間。固定長度的項(xiàng)放在活動(dòng)記錄中間。在編譯時(shí)不能及時(shí)知道大小的項(xiàng)目在編譯時(shí)不能及時(shí)知道大小的項(xiàng)目放在活動(dòng)記錄末端放在活動(dòng)記錄末端返

18、返 回回 值值臨臨 時(shí)時(shí) 數(shù)數(shù) 據(jù)據(jù)參參 數(shù)數(shù)控控 制制 鏈鏈訪訪 問問 鏈鏈機(jī)機(jī) 器器 狀狀 態(tài)態(tài)局局 部部 數(shù)數(shù) 據(jù)據(jù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、過程、過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、過程、過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列(1) p計(jì)算實(shí)參，依計(jì)算實(shí)參，依次放入棧頂，并在次放入棧頂，并在棧頂留出放返回值棧頂留出放返回值的空間。的空間。top_sp的的值在此過程中被改值在此過程

19、中被改變變返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 返回值和參數(shù)返回值和參數(shù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、過程、過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列(2) p把返回地址和把返回地址和當(dāng)前當(dāng)前base_sp的值的值存入存入q的活動(dòng)記錄的活動(dòng)記錄中，建立中，建立q的訪問的訪問鏈，增加鏈，增加base_sp的值的值返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 返回值和參數(shù)返回值和參數(shù)控制鏈和返回地址控

20、制鏈和返回地址6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、過程、過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列(3) q保存寄存器的保存寄存器的值和其它機(jī)器狀態(tài)值和其它機(jī)器狀態(tài)信息信息返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 返回值和參數(shù)返回值和參數(shù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配1、過程、過程p調(diào)用過程調(diào)用過程q的調(diào)用序列的調(diào)用序列(4) q根據(jù)局部數(shù)據(jù)根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的域和臨時(shí)數(shù)據(jù)域的大小增加大小增加top_sp的的值，初始化它的局值，初

21、始化它的局部數(shù)據(jù)，并開始執(zhí)部數(shù)據(jù)，并開始執(zhí)行過程體行過程體臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配調(diào)用者調(diào)用者p和被調(diào)用者和被調(diào)用者q之間的任務(wù)劃分之間的任務(wù)劃分被調(diào)用者被調(diào)用者q的責(zé)任的責(zé)任調(diào)用者調(diào)用者p的責(zé)任的責(zé)任調(diào)用者調(diào)用者p的的活動(dòng)記錄活動(dòng)記錄被被調(diào)用者調(diào)用者q的活動(dòng)記錄的活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回

22、值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、過程、過程p調(diào)用過程調(diào)用過程q的返回序列的返回序列臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、過程、過程p調(diào)用過

23、程調(diào)用過程q的返回序列的返回序列臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值返回值和參數(shù)和參數(shù)返回值和參數(shù)返回值和參數(shù) 控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)top_sp base_sp 棧棧增增長長方方向向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) (1) q把返回值置入鄰把返回值置入鄰近近p的活動(dòng)記錄存放的活動(dòng)記錄存放返回值的地方返回值的地方 6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、過程、過程p調(diào)用過程調(diào)用過程q的返回序列的返回序列(2) q對(duì)應(yīng)調(diào)用序列對(duì)應(yīng)調(diào)用序列的步驟的步驟(4)，減小，減小top_sp的值的值返回值和參數(shù)返回值和參數(shù)top_s

24、p base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 返回值和參數(shù)返回值和參數(shù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、過程、過程p調(diào)用過程調(diào)用過程q的返回序列的返回序列(3) q恢復(fù)寄存器恢復(fù)寄存器(包包括括base_sp)和機(jī)器和機(jī)器狀態(tài)，返回狀態(tài)，返回p返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) 返回值和參數(shù)返回值和參數(shù)6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配2、過程、過程p調(diào)用過程調(diào)用過程q的返回序列的返

25、回序列返回值和參數(shù)返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈控制鏈 和保存的機(jī)器狀態(tài)和保存的機(jī)器狀態(tài) (4) p根據(jù)參數(shù)個(gè)數(shù)根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類與類型和返回值類型調(diào)整型調(diào)整top_sp，然然后取出返回值后取出返回值6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.4 棧上可變長數(shù)據(jù)棧上可變長數(shù)據(jù)活動(dòng)記錄的長度在編譯時(shí)不能確定的情況活動(dòng)記錄的長度在編譯時(shí)不能確定的情況 例：局部數(shù)組的大小要等到過程激活時(shí)才能例：局部數(shù)組的大小要等到過程激活時(shí)才能確定確定備注：備注： Java語言的實(shí)現(xiàn)是將它們分配在堆上語言的實(shí)現(xiàn)是將它們分配在堆上6.2 全局棧式存儲(chǔ)分配

26、全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組訪問動(dòng)態(tài)分配的數(shù)組控制鏈控制鏈數(shù)組數(shù)組A的指針的指針數(shù)組數(shù)組B的指針的指針top_sp base_sp . . . . . . .棧棧(1) 編譯時(shí)，在活編譯時(shí)，在活動(dòng)記錄中為這樣動(dòng)記錄中為這樣的數(shù)組分別存放的數(shù)組分別存放數(shù)組指針的單元數(shù)組指針的單元6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組訪問動(dòng)態(tài)分配的數(shù)組(2) 運(yùn)行時(shí)，運(yùn)行時(shí)，這些指針指向這些指針指向分配在棧頂?shù)姆峙湓跅ｍ數(shù)拇鎯?chǔ)空間存儲(chǔ)空間控制鏈控制鏈數(shù)組數(shù)組A的指針的指針數(shù)組數(shù)組B的指針的指針top_sp base_sp . . . . . . .棧棧數(shù)組數(shù)組A數(shù)組數(shù)組B6.2 全局棧式

27、存儲(chǔ)分配全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組訪問動(dòng)態(tài)分配的數(shù)組(3) 運(yùn)行時(shí)，運(yùn)行時(shí)，對(duì)數(shù)組對(duì)數(shù)組A和和B的訪問都要通的訪問都要通過相應(yīng)指針來過相應(yīng)指針來間接訪問間接訪問控制鏈控制鏈數(shù)組數(shù)組A的指針的指針數(shù)組數(shù)組B的指針的指針top_sp base_sp . . . . . . .棧棧數(shù)組數(shù)組A數(shù)組數(shù)組B6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配訪問動(dòng)態(tài)分配的數(shù)組訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組的數(shù)組q的活動(dòng)記錄的活動(dòng)記錄p的數(shù)組的數(shù)組p的活動(dòng)記錄的活動(dòng)記錄控制鏈控制鏈top_sp base_sp 數(shù)組數(shù)組A的指針的指針數(shù)組數(shù)組B的指針的指針數(shù)組數(shù)組A數(shù)組數(shù)組B控制鏈控制鏈. . . . . . .棧棧

28、6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.5 懸空引用懸空引用懸空引用：懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元引用某個(gè)已被釋放的存儲(chǔ)單元6.2 全局棧式存儲(chǔ)分配全局棧式存儲(chǔ)分配6.2.5 懸空引用懸空引用懸空引用：懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元引用某個(gè)已被釋放的存儲(chǔ)單元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( ); |return &j;|*6.3 非局部名字的訪問非局部名字的訪問本節(jié)介紹本節(jié)介紹 無過程嵌套的靜態(tài)作用域（無過程嵌套的靜態(tài)作用域（C語言）語言） 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域（Pasca

29、l語言）語言） 動(dòng)態(tài)作用域動(dòng)態(tài)作用域（Lisp語言）語言）* 6.3 非局部名字的訪問非局部名字的訪問6.3.1 無過程嵌套的靜態(tài)作用域無過程嵌套的靜態(tài)作用域 過程體中的非局部引用可以直接使用靜態(tài)確過程體中的非局部引用可以直接使用靜態(tài)確定的地址定的地址 局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過base_sp指針來訪問指針來訪問 無須深入棧中取數(shù)據(jù)，無須訪問鏈無須深入棧中取數(shù)據(jù)，無須訪問鏈 過程可以作為參數(shù)來傳遞，也可以作為結(jié)果過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回來返回*6.3 非局部名字的訪問非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域有過程嵌套的

30、靜態(tài)作用域sortreadarrayexchangequicksortpartition*6.3 非局部名字的訪問非局部名字的訪問6.3.2 有過程嵌套的靜態(tài)作用域有過程嵌套的靜態(tài)作用域 過程過程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3 變量的嵌套深度：它的聲明所在過程的嵌套變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度深度作為該名字的嵌套深度 訪問鏈訪問鏈用來尋找非局部用來尋找非局部名字的存儲(chǔ)單元名字的存儲(chǔ)單元sa, xq (1, 9)k, v訪問鏈訪問鏈sa, xq (1, 3)k, v訪問鏈訪問鏈q (1,

31、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 非局部名字的訪問非局部名字的訪問 訪問非局部名字的存儲(chǔ)單元訪問非局部名字的存儲(chǔ)單元 假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度為它引用嵌套深度為na的變量的變量a，na np。如何訪問如何訪問a的存儲(chǔ)單元的存儲(chǔ)單元sort1readarra

32、y2exchange2quicksort2partition3*6.3 非局部名字的訪問非局部名字的訪問 訪問非局部名字的存儲(chǔ)單元訪問非局部名字的存儲(chǔ)單元 假定過程假定過程p的嵌套深度為的嵌套深度為np，它引用嵌套深度為它引用嵌套深度為na的變量的變量a，na np。如何訪問如何訪問a的存儲(chǔ)單元的存儲(chǔ)單元 從棧頂?shù)幕顒?dòng)記錄開始，追蹤訪問鏈從棧頂?shù)幕顒?dòng)記錄開始，追蹤訪問鏈np na次次到達(dá)到達(dá)a的聲明所在過程的活動(dòng)記錄的聲明所在過程的活動(dòng)記錄 訪問鏈的追蹤用間接操作就可完成訪問鏈的追蹤用間接操作就可完成sort1readarray2exchange2quicksort2partition3 訪問

33、非局部名字的存儲(chǔ)單元訪問非局部名字的存儲(chǔ)單元 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, 3)i, j訪問鏈訪問鏈*6.3 非局部名字的訪問非局部名字的訪問*6.3 非局部名字的訪問非局部名

34、字的訪問 C語言的函數(shù)聲明不能嵌套，函數(shù)不論在什語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況么情況下激活，要訪問的數(shù)據(jù)分成兩種情況非靜態(tài)局部變量（包括形式參數(shù)），它們分配在非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中外部變量（包括定義在其它源文件之中的外部變外部變量（包括定義在其它源文件之中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū)區(qū)6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.1 值調(diào)用值調(diào)用 實(shí)參的右值傳給被調(diào)用過程實(shí)參的右值傳給被調(diào)用過程 值調(diào)用可以如下實(shí)現(xiàn)值調(diào)

35、用可以如下實(shí)現(xiàn) 把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中單元在該過程的活動(dòng)記錄中調(diào)用過程計(jì)算實(shí)參，并把其右值放入形參的存儲(chǔ)調(diào)用過程計(jì)算實(shí)參，并把其右值放入形參的存儲(chǔ)單元中單元中6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.2 引用調(diào)用引用調(diào)用 實(shí)參的左值傳給被調(diào)用過程實(shí)參的左值傳給被調(diào)用過程 引用調(diào)用可以如下實(shí)現(xiàn)：引用調(diào)用可以如下實(shí)現(xiàn)： 把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)把形參當(dāng)作所在過程的局部名看待，形參的存儲(chǔ)單元在該過程的活動(dòng)記錄中單元在該過程的活動(dòng)記錄中調(diào)用過程計(jì)算實(shí)參，調(diào)用過程計(jì)算實(shí)參，把實(shí)參的左值放入形參的存把實(shí)參的

36、左值放入形參的存儲(chǔ)單元儲(chǔ)單元 在被調(diào)用過程的目標(biāo)代碼中，任何對(duì)形參的引用在被調(diào)用過程的目標(biāo)代碼中，任何對(duì)形參的引用都是通過傳給該過程的指針來間接引用實(shí)參都是通過傳給該過程的指針來間接引用實(shí)參6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.3 換名調(diào)用換名調(diào)用從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer; begin temp := x; x := y; y := temp end6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.

37、3 換名調(diào)用換名調(diào)用從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer;例如：例如：調(diào)用調(diào)用swap(i, ai) begin temp := x; x := y; y := temp end6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.3 換名調(diào)用換名調(diào)用從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(va

38、r x, y: integer);var temp: integer;例如：例如：調(diào)用調(diào)用swap(i, ai) begin 替換結(jié)果：替換結(jié)果： temp := i; temp := x; i := ai; x := y; ai := temp y := temp end6.4 參參 數(shù)數(shù) 傳傳 遞遞6.4.3 換名調(diào)用換名調(diào)用從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)從概念上說，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer;例如：例如：調(diào)用調(diào)用swap(i

39、, ai) begin 替換結(jié)果：替換結(jié)果： temp := i; temp := x; i := ai; x := y; ai := temp y := temp 交換兩個(gè)數(shù)據(jù)的程序交換兩個(gè)數(shù)據(jù)的程序 end并非總是正確并非總是正確 棧式存儲(chǔ)分配策略在下列情況下不能使用：棧式存儲(chǔ)分配策略在下列情況下不能使用： 活動(dòng)結(jié)束時(shí)必須保持局部名字的值活動(dòng)結(jié)束時(shí)必須保持局部名字的值 被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期長。被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期長。 堆式存儲(chǔ)器的策略：（堆管理器管理堆空間）堆式存儲(chǔ)器的策略：（堆管理器管理堆空間） 把連續(xù)存儲(chǔ)區(qū)域分成塊，當(dāng)活動(dòng)記錄或其他對(duì)象把連續(xù)存儲(chǔ)區(qū)域分成

40、塊，當(dāng)活動(dòng)記錄或其他對(duì)象需要時(shí)就分配。需要時(shí)就分配。 塊的釋放可以按任意次序進(jìn)行，所以經(jīng)過一段時(shí)塊的釋放可以按任意次序進(jìn)行，所以經(jīng)過一段時(shí)間后，堆可能包含交錯(cuò)的正在使用的和已經(jīng)釋放間后，堆可能包含交錯(cuò)的正在使用的和已經(jīng)釋放的區(qū)域的區(qū)域6.5 堆堆 管管 理理6.5 堆堆 管管 理理堆式分配堆式分配 堆用來存放生存期不確定的數(shù)據(jù)堆用來存放生存期不確定的數(shù)據(jù) C+和和Java允許程序員用允許程序員用new創(chuàng)建對(duì)象，它們的生存期沒創(chuàng)建對(duì)象，它們的生存期沒有被約束在創(chuàng)建它們的過程活動(dòng)的生成期之內(nèi)有被約束在創(chuàng)建它們的過程活動(dòng)的生成期之內(nèi) 實(shí)現(xiàn)內(nèi)存回收是內(nèi)存管理器的責(zé)任實(shí)現(xiàn)內(nèi)存回收是內(nèi)存管理器的責(zé)任 堆空

41、間的回收有兩種不同方式堆空間的回收有兩種不同方式 程序顯式釋放空間：程序顯式釋放空間：free（C）或）或delete（C+） 垃圾收集器自動(dòng)收集（垃圾收集器自動(dòng)收集（Java）。）。6.5 堆堆 管管 理理6.5.1 內(nèi)存管理器內(nèi)存管理器 內(nèi)存管理器把握的基本信息是堆中空閑空間內(nèi)存管理器把握的基本信息是堆中空閑空間 分配函數(shù)分配函數(shù) 回收函數(shù)回收函數(shù) 內(nèi)存管理器應(yīng)具有下列性質(zhì)內(nèi)存管理器應(yīng)具有下列性質(zhì) 空間有效性：極小化程序需要的堆空間總量空間有效性：極小化程序需要的堆空間總量 程序有效性：較好地利用內(nèi)存子系統(tǒng)，使得程序能運(yùn)行程序有效性：較好地利用內(nèi)存子系統(tǒng)，使得程序能運(yùn)行得快一些得快一些 低

42、開銷低開銷：分配和回收操作所花時(shí)間在整個(gè)程序執(zhí)行時(shí)間分配和回收操作所花時(shí)間在整個(gè)程序執(zhí)行時(shí)間中的比例盡量小中的比例盡量小6.5 堆堆 管管 理理6.5.2 計(jì)算機(jī)內(nèi)存分層計(jì)算機(jī)內(nèi)存分層虛擬內(nèi)存虛擬內(nèi)存(磁盤磁盤)物理內(nèi)存物理內(nèi)存2級(jí)緩存級(jí)緩存1級(jí)緩存級(jí)緩存寄存器寄存器(處理器處理器)典型大小典型大小 2千兆字節(jié)千兆字節(jié)256兆兆 2千兆字節(jié)千兆字節(jié)128千千 4兆字節(jié)兆字節(jié)16 64千字節(jié)千字節(jié)32字字典型訪問時(shí)間典型訪問時(shí)間3 15微秒微秒100 150納秒納秒40 60納秒納秒5 10納秒納秒1納秒納秒6.5 堆堆 管管 理理6.5.2 計(jì)算機(jī)內(nèi)存分層計(jì)算機(jī)內(nèi)存分層 現(xiàn)代計(jì)算機(jī)都設(shè)計(jì)成程序

43、員不用關(guān)心內(nèi)存子系統(tǒng)的細(xì)節(jié)現(xiàn)代計(jì)算機(jī)都設(shè)計(jì)成程序員不用關(guān)心內(nèi)存子系統(tǒng)的細(xì)節(jié)就可以寫出正確的程序就可以寫出正確的程序 程序的效率不僅取決于被執(zhí)行的指令數(shù)，還取決于執(zhí)行程序的效率不僅取決于被執(zhí)行的指令數(shù)，還取決于執(zhí)行每條指令需要多長時(shí)間每條指令需要多長時(shí)間 執(zhí)行一條指令的時(shí)間區(qū)別非常可觀執(zhí)行一條指令的時(shí)間區(qū)別非?？捎^ 差異源于硬件技術(shù)的基本局限：構(gòu)造不了大容量的高速差異源于硬件技術(shù)的基本局限：構(gòu)造不了大容量的高速存儲(chǔ)器存儲(chǔ)器 數(shù)據(jù)以塊（緩存行、頁）為單位在相鄰層次之間進(jìn)行傳數(shù)據(jù)以塊（緩存行、頁）為單位在相鄰層次之間進(jìn)行傳送送 數(shù)據(jù)密集型程序可從恰當(dāng)利用內(nèi)存子系統(tǒng)中獲益數(shù)據(jù)密集型程序可從恰當(dāng)利用內(nèi)存

44、子系統(tǒng)中獲益6.5 堆堆 管管 理理6.5.3 程序局部性程序局部性 大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼，并大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼，并且僅涉及一小部分?jǐn)?shù)據(jù)且僅涉及一小部分?jǐn)?shù)據(jù) 時(shí)間局部性時(shí)間局部性 程序訪問的內(nèi)存單元在很短的時(shí)間內(nèi)可能再次被程序訪程序訪問的內(nèi)存單元在很短的時(shí)間內(nèi)可能再次被程序訪問問 空間局部性空間局部性 毗鄰被訪問單元的內(nèi)存單元在很短的時(shí)間內(nèi)可能被訪問毗鄰被訪問單元的內(nèi)存單元在很短的時(shí)間內(nèi)可能被訪問6.5 堆堆 管管 理理6.5.3 程序局部性程序局部性 從代碼本身很難看出哪部分代碼會(huì)被頻繁使用從代碼本身很難看出哪部分代碼會(huì)被頻繁使用,必必須動(dòng)態(tài)調(diào)整最快

45、緩存的內(nèi)容須動(dòng)態(tài)調(diào)整最快緩存的內(nèi)容 把最近使用的指令保存在緩存是一種較好的最優(yōu)把最近使用的指令保存在緩存是一種較好的最優(yōu)化利用內(nèi)存分層的策略化利用內(nèi)存分層的策略 改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪問的時(shí)間和空間局部性問的時(shí)間和空間局部性6.5 堆堆 管管 理理6.5.4 手工回收請(qǐng)求手工回收請(qǐng)求 程序員在程序中顯式釋放堆塊來達(dá)到回收堆塊的目程序員在程序中顯式釋放堆塊來達(dá)到回收堆塊的目的的 內(nèi)存泄漏：沒有釋放已經(jīng)引用不到的堆塊內(nèi)存泄漏：沒有釋放已經(jīng)引用不到的堆塊 只要內(nèi)存沒有用盡，它就不影響程序的正確性只要內(nèi)存沒有用盡，它就不影響程序的正確性 自

46、動(dòng)無用單元收集通過回收所有無用單元來擺脫內(nèi)存自動(dòng)無用單元收集通過回收所有無用單元來擺脫內(nèi)存泄漏泄漏 懸空引用：引用已經(jīng)被釋放的堆塊懸空引用：引用已經(jīng)被釋放的堆塊 過分熱心地釋放數(shù)據(jù)對(duì)象而引起過分熱心地釋放數(shù)據(jù)對(duì)象而引起 懸空引用容易導(dǎo)致不會(huì)被捕獲的錯(cuò)誤懸空引用容易導(dǎo)致不會(huì)被捕獲的錯(cuò)誤 本本 章章 要要 點(diǎn)點(diǎn) 影響存儲(chǔ)分配策略的語言特征影響存儲(chǔ)分配策略的語言特征 各種存儲(chǔ)分配策略，主要了解靜態(tài)分配和動(dòng)各種存儲(chǔ)分配策略，主要了解靜態(tài)分配和動(dòng)態(tài)棧式分配態(tài)棧式分配 活動(dòng)記錄中各種數(shù)據(jù)域的作用和布局活動(dòng)記錄中各種數(shù)據(jù)域的作用和布局 非局部數(shù)據(jù)訪問的實(shí)現(xiàn)方法非局部數(shù)據(jù)訪問的實(shí)現(xiàn)方法 各種參數(shù)傳遞方式及其實(shí)

47、現(xiàn)各種參數(shù)傳遞方式及其實(shí)現(xiàn) 堆管理堆管理例例 題題 1一個(gè)一個(gè)C語言程序及其在語言程序及其在X86/Linux操作系統(tǒng)上的編譯結(jié)操作系統(tǒng)上的編譯結(jié)果如下。果如下。根據(jù)所生成的匯編程序來解釋程序中四個(gè)變根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的存儲(chǔ)分配、作用域、生存期和置初值方式等方面量的存儲(chǔ)分配、作用域、生存期和置初值方式等方面的區(qū)別的區(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

48、aa,object|.size cc.2,4.size aa,4| cc.2:aa:|.long 30.long 10| .text.globl bb|.align 4.align 2| .globl func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 題題 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.

49、globl bb|.align 4.align 2| .globl func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 題題 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 func .type bb,object| func:.size

50、bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 題題 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 func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 題題 2func(i)long i;

51、long j;j= i -1;func(j);例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl

52、$4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . .參數(shù)參數(shù)i返址返址控制鏈控制鏈變量變量j. . .ebp esp 棧棧低低高高例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl

53、 %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . . . .ebp esp 例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j;

54、 subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . . . .ebp esp 參數(shù)參數(shù)i例例 題題 2func

55、(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 m

56、ov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . . . .ebp esp 參數(shù)參數(shù)i返址返址例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%ea

57、x pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . . . .ebp esp 參數(shù)參數(shù)i返址返址控制鏈控制鏈例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; mo

58、vl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下條指令地址）下條指令地址）. . . . .ebp esp 參數(shù)參數(shù)i返址返址控制鏈控制鏈例例 題題 2func(i)func: long i; pushl %ebp

59、 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把實(shí)參把實(shí)參j的值壓棧的值壓棧 call func 函數(shù)調(diào)用函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針恢復(fù)棧頂指針L1: leave 即即 mov ebp, esp; pop ebp ret 即即

60、 pop eip(下條指令地址）下條指令地址）. . .參數(shù)參數(shù)i返址返址控制鏈控制鏈變量變量j. . .ebp esp 棧棧低低高高例例 題題 2func(i)func: long i; pushl %ebp 老的基地址指針壓棧老的基地址指針壓棧 movl %esp,%ebp修改修改基地址指針基地址指針 long j; subl $4,%esp 為為j分配空間分配空間 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %