運(yùn)行時(shí)存儲(chǔ)空間組織和管理PPT課件

1、第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 影響存儲(chǔ)分配策略的語(yǔ)言特征 過(guò)程能否遞歸 當(dāng)控制從過(guò)程的活動(dòng)返回時(shí)，局部變量的值是否要保留 過(guò)程能否訪問(wèn)非局部變量 過(guò)程調(diào)用的參數(shù)傳遞方式 過(guò)程能否作為參數(shù)被傳遞 過(guò)程能否作為結(jié)果值傳遞 存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配 存儲(chǔ)塊是否必須顯式地釋放第1頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配6.1.1 過(guò)程語(yǔ)言概念：過(guò)程定義、過(guò)程調(diào)用、形式參數(shù)、實(shí)在參數(shù)、活動(dòng)的生存期第2頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配6.1.2 名字的作用域和綁定1、名字的作用域 一個(gè)聲明起作用的程序部分稱為該聲明的作用域 即使一個(gè)名字在程序中只聲明一次，該名字在程序運(yùn)行時(shí)也可能表示不同的數(shù)據(jù)對(duì)

2、象第3頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配2、環(huán)境和狀態(tài) 環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值（即名字到值有兩步映射） 賦值改變狀態(tài)，但不改變環(huán)境 過(guò)程調(diào)用改變環(huán)境 如果環(huán)境將名字x映射到存儲(chǔ)單元s，則說(shuō)x被綁定到s名字存儲(chǔ)單元狀態(tài)值環(huán)境第4頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配3、靜態(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) 過(guò)程的定義過(guò)程的定義 過(guò)程的活動(dòng)過(guò)程的活動(dòng) 第5頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配3、靜態(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) 過(guò)程的定義過(guò)程的定義 過(guò)程的活動(dòng)過(guò)程的活動(dòng) 名字的聲明名字的聲明 名字的綁定名字的綁

3、定 第6頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配3、靜態(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) 過(guò)程的定義過(guò)程的定義 過(guò)程的活動(dòng)過(guò)程的活動(dòng) 名字的聲明名字的聲明 名字的綁定名字的綁定 聲明的作用域聲明的作用域 綁定的生存期綁定的生存期 第7頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配6.1.3 活動(dòng)記錄活動(dòng)記錄的常見(jiàn)布局臨 時(shí) 數(shù) 據(jù)參 數(shù)局 部 數(shù) 據(jù)機(jī) 器 狀 態(tài)訪 問(wèn) 鏈控 制 鏈返 回 值第8頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配6.1.4 局部數(shù)據(jù)的布局 字節(jié)是可編址內(nèi)存的最小單位 變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定 一個(gè)過(guò)程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次

4、序，在局部數(shù)據(jù)域中依次分配空間 局部數(shù)據(jù)的地址可以用相對(duì)于活動(dòng)記錄中某個(gè)位置的地址來(lái)表示 數(shù)據(jù)對(duì)象的存儲(chǔ)布局還有一個(gè)對(duì)齊問(wèn)題第9頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配 例在SPARC/Solaris工作站上下面兩個(gè)結(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;對(duì)齊：char : 1, long : 4, double : 8第10頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配 例在SPARC/Sol

5、aris工作站上下面兩個(gè)結(jié)構(gòu)體的size分別是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;對(duì)齊：char : 1, long : 4, double : 8第11頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配 例在X86/Linux機(jī)器的結(jié)果和SPARC/Solaris工作站不一樣，是20和16。typedef struct _atypedef struct _bchar c1;0 char

6、 c1;0long i;4 char c2; 1charc2;8 long i; 4double f;12 double f; 8a; b;對(duì)齊：char : 1, long : 4, double : 4第12頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配6.1.5 程序塊 本身含有局部變量聲明的語(yǔ)句 可以嵌套 最接近的嵌套作用域規(guī)則 并列程序塊不會(huì)同時(shí)活躍 并列程序塊的變量可以重疊分配第13頁(yè)/共149頁(yè)6.1 局部存儲(chǔ)分配main() / 例 / / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B

7、2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / end of B0 /第14頁(yè)/共149頁(yè)6.1 局部存儲(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 /

8、聲聲 明明 作作 用用 域域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲(chǔ)單元 第15頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配本節(jié)介紹 介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略 描述過(guò)程的目標(biāo)代碼怎樣訪問(wèn)綁定到局部名字的存儲(chǔ)單元 介紹三種分配策略 靜態(tài)分配策略 棧式分配策略 堆式分配策略第16頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配6.2.1 運(yùn)行時(shí)內(nèi)存的劃分代 碼靜 態(tài) 數(shù) 據(jù)堆棧第17頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1、靜態(tài)分配 名

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

10、活動(dòng)樹(shù) 用樹(shù)來(lái)描繪控制進(jìn)入和離開(kāi)活動(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)第21頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配 活動(dòng)樹(shù)的特點(diǎn) 每個(gè)結(jié)點(diǎn)代表某過(guò)程的一個(gè)活動(dòng) 根結(jié)點(diǎn)代表主程序的活動(dòng) 結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng) 結(jié)點(diǎn)a處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期mq(1,9)rp(1,9)q(1,3) . . . .q(5,9) . . . .第22頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配

11、當(dāng)前活躍著的過(guò)程活動(dòng)可以保存在一個(gè)棧中 例 控制棧的內(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)第23頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） 第24頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） ma : arraym第25頁(yè)/共

12、149頁(yè)6.2 全局棧式存儲(chǔ)分配2、運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mi: integerra : arraymr第26頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mk: integerq (1, 9)a : arraymq(1,9)r第27頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、運(yùn)行棧：把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） mk: integerq (1, 9)a : arrayq (1, 3)k: integermq(1,9)rp(1,9)q

13、(1,3)q(1,0)p(1,3)第28頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配6.2.3 調(diào)用序列 過(guò)程調(diào)用和過(guò)程返回都需要執(zhí)行一些代碼來(lái)管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過(guò)程調(diào)用序列過(guò)程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中，使被調(diào)用過(guò)程可以開(kāi)始執(zhí)行的代碼 過(guò)程返回序列被調(diào)用過(guò)程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放被調(diào)用過(guò)程活動(dòng)記錄，使調(diào)用過(guò)程能夠繼續(xù)執(zhí)行的代碼 調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過(guò)程和被調(diào)用過(guò)程中第29頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配 即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則

14、以活動(dòng)記錄中間的某個(gè)位置作為基地址 長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間臨 時(shí) 數(shù) 據(jù)參 數(shù)局 部 數(shù) 據(jù)機(jī) 器 狀 態(tài)訪 問(wèn) 鏈控 制 鏈返 回 值第30頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配 即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則 一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面 把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)記錄的地方臨 時(shí) 數(shù) 據(jù)參 數(shù)局 部 數(shù) 據(jù)機(jī) 器 狀 態(tài)訪 問(wèn) 鏈控 制 鏈返 回 值第31頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配 即使是同一種語(yǔ)言，過(guò)程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也

15、會(huì)因?qū)崿F(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則 用同樣的代碼來(lái)執(zhí)行各個(gè)活動(dòng)的保存和恢復(fù)臨 時(shí) 數(shù) 據(jù)參 數(shù)局 部 數(shù) 據(jù)機(jī) 器 狀 態(tài)訪 問(wèn) 鏈控 制 鏈返 回 值第32頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1、過(guò)程p調(diào)用過(guò)程q的調(diào)用序列返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 第33頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1、過(guò)程p調(diào)用過(guò)程q的調(diào)用序列(1) p計(jì)算實(shí)參，依次放入棧頂，并在棧頂留出放返回值的空間。top_sp的值在此過(guò)程中被改變返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 返回值和參數(shù)top_sp

16、第34頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1、過(guò)程p調(diào)用過(guò)程q的調(diào)用序列(2) p把返回地址和當(dāng)前base_sp的值存入q的活動(dòng)記錄中，建立q的訪問(wèn)鏈，增加base_sp的值返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 返回值和參數(shù)控制鏈和返回地址base_sp top_sp 第35頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1、過(guò)程p調(diào)用過(guò)程q的調(diào)用序列(3) q保存寄存器的值和其它機(jī)器狀態(tài)信息返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 返回值和參數(shù)控制鏈 和保存的機(jī)器狀態(tài)第36頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配1

17、、過(guò)程p調(diào)用過(guò)程q的調(diào)用序列(4) q根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小增加top_sp的值，初始化它的局部數(shù)據(jù)，并開(kāi)始執(zhí)行過(guò)程體臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 第37頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配調(diào)用者p和被調(diào)用者q之間的任務(wù)劃分被調(diào)用者q的責(zé)任調(diào)用者p的責(zé)任調(diào)用者p的活動(dòng)記錄被調(diào)用者q的活動(dòng)記錄臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 第38頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)

18、分配2、過(guò)程p調(diào)用過(guò)程q的返回序列臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 第39頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、過(guò)程p調(diào)用過(guò)程q的返回序列臨時(shí)數(shù)據(jù)局部數(shù)據(jù)返回值和參數(shù)返回值和參數(shù) 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (1) q把返回值置入鄰近p的活動(dòng)記錄的地方 參數(shù)個(gè)數(shù)可變場(chǎng)合難以確定存放返回值的位置，因此通常用寄存器傳遞返回值第40頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、過(guò)程p調(diào)用過(guò)程q的返回序列(2)

19、q對(duì)應(yīng)調(diào)用序列的步驟(4)，減小top_sp的值返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 返回值和參數(shù)控制鏈 和保存的機(jī)器狀態(tài)第41頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、過(guò)程p調(diào)用過(guò)程q的返回序列(3) q恢復(fù)寄存器(包括base_sp)和機(jī)器狀態(tài)，返回p返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) 返回值和參數(shù)第42頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配2、過(guò)程p調(diào)用過(guò)程q的返回序列返回值和參數(shù)top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (4) p根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類型調(diào)整

20、top_sp，然后取出返回值第43頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配3、過(guò)程的參數(shù)個(gè)數(shù)可變的情況臨時(shí)數(shù)據(jù)局部數(shù)據(jù)參 數(shù)參 數(shù) 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (1) 函數(shù)返回值改成用寄存器傳遞第44頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配3、過(guò)程的參數(shù)個(gè)數(shù)可變的情況臨時(shí)數(shù)據(jù)局部數(shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (2) 編譯器產(chǎn)生將實(shí)參表達(dá)式逆序計(jì)算并將結(jié)果進(jìn)棧的代碼 自上而下依次是參數(shù)1, , 參數(shù)n第4

21、5頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配3、過(guò)程的參數(shù)個(gè)數(shù)可變的情況臨時(shí)數(shù)據(jù)局部數(shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (3) 被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置第46頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配3、過(guò)程的參數(shù)個(gè)數(shù)可變的情況臨時(shí)數(shù)據(jù)局部數(shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) (4) 被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等第47頁(yè)/共149頁(yè)6.2 全

22、局棧式存儲(chǔ)分配3、過(guò)程的參數(shù)個(gè)數(shù)可變的情況臨時(shí)數(shù)據(jù)局部數(shù)據(jù)參數(shù)1, , 參數(shù)n參數(shù)1, ,參數(shù)m 控制鏈 和保存的機(jī)器狀態(tài)top_sp base_sp 棧增長(zhǎng)方向臨時(shí)數(shù)據(jù)局部數(shù)據(jù)控制鏈 和保存的機(jī)器狀態(tài) C語(yǔ)言的printf函數(shù)就是按此方式，用C語(yǔ)言編寫(xiě)的下面語(yǔ)句的輸出？printf(“%d, %d, %dn”);第48頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配6.2.4 棧上可變長(zhǎng)數(shù)據(jù)活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況 例：局部數(shù)組的大小要等到過(guò)程激活時(shí)才能確定備注： Java語(yǔ)言的實(shí)現(xiàn)是將它們分配在堆上第49頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配訪問(wèn)動(dòng)態(tài)分配的數(shù)組控制鏈數(shù)組A的指針數(shù)組B的指

23、針top_sp base_sp . . . . . . .棧(1) 編譯時(shí)，在活動(dòng)記錄中為這樣的數(shù)組分配存放數(shù)組指針的單元第50頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配訪問(wèn)動(dòng)態(tài)分配的數(shù)組(2) 運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)臄?shù)組存儲(chǔ)空間控制鏈數(shù)組A的指針數(shù)組B的指針top_sp base_sp . . . . . . .棧數(shù)組A數(shù)組B第51頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配訪問(wèn)動(dòng)態(tài)分配的數(shù)組(3) 運(yùn)行時(shí)，對(duì)數(shù)組A和B的訪問(wèn)都要通過(guò)相應(yīng)指針來(lái)間接訪問(wèn)控制鏈數(shù)組A的指針數(shù)組B的指針top_sp base_sp . . . . . . .棧數(shù)組A數(shù)組B第52頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分

24、配訪問(wèn)動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組p的活動(dòng)記錄控制鏈top_sp base_sp 數(shù)組A的指針數(shù)組B的指針數(shù)組A數(shù)組B控制鏈. . . . . . .棧第53頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配6.2.5 懸空引用懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元第54頁(yè)/共149頁(yè)6.2 全局棧式存儲(chǔ)分配6.2.5 懸空引用懸空引用：引用某個(gè)已被釋放的存儲(chǔ)單元例：main中引用p指向的對(duì)象main( ) |int dangle ( ) int q;|int j = 20; q = dangle ( ); |return &j;|第55頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)本節(jié)介紹

25、無(wú)過(guò)程嵌套的靜態(tài)作用域（C語(yǔ)言） 有過(guò)程嵌套的靜態(tài)作用域（Pascal語(yǔ)言） 動(dòng)態(tài)作用域（Lisp語(yǔ)言）第56頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)6.3.1 無(wú)過(guò)程嵌套的靜態(tài)作用域 過(guò)程體中的非局部引用可以直接使用靜態(tài)確定的地址（非局部數(shù)據(jù)此時(shí)就是全局?jǐn)?shù)據(jù)） 局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過(guò)base_sp指針來(lái)訪問(wèn) 無(wú)須深入棧中取數(shù)據(jù)，無(wú)須訪問(wèn)鏈 過(guò)程可以作為參數(shù)來(lái)傳遞，也可以作為結(jié)果來(lái)返回第57頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)6.3.2 有過(guò)程嵌套的靜態(tài)作用域sortreadarrayexchangequicksortpartition第58頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)

26、6.3.2 有過(guò)程嵌套的靜態(tài)作用域 過(guò)程嵌套深度sort1readarray2exchange2quicksort2partition3 變量的嵌套深度：它的聲明所在過(guò)程的嵌套深度作為該名字的嵌套深度第59頁(yè)/共149頁(yè) 訪問(wèn)鏈 用來(lái)尋找非局部名字的存儲(chǔ)單元sa, xq (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈e (1, 3)訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈6.3 非

27、局部名字的訪問(wèn)第60頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 訪問(wèn)非局部名字的存儲(chǔ)單元 假定過(guò)程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np，如何訪問(wèn)a的存儲(chǔ)單元sort1readarray2exchange2quicksort2partition 3sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈第61頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 訪問(wèn)非局部名字的存儲(chǔ)單元 假定過(guò)程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np，如何訪問(wèn)a的存儲(chǔ)單元 從棧頂?shù)幕顒?dòng)記錄開(kāi)始，追蹤訪問(wèn)鏈np na次 到達(dá)a的聲明所在過(guò)程的活動(dòng)記錄 訪問(wèn)鏈的追蹤用間接操作

28、就可完成sort1readarray2exchange2quicksort2partition 3sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈第62頁(yè)/共149頁(yè) 訪問(wèn)非局部名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈e (1, 3)訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪

29、問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈6.3 非局部名字的訪問(wèn)第63頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 過(guò)程p對(duì)變量a訪問(wèn)時(shí)，a的地址由下面的二元組表示：（np na，a在活動(dòng)記錄中的偏移）第64頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 建立訪問(wèn)鏈 假定嵌套深度為np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程x(1) np nx的情況sort1readarray2exchange2quicksort2partition 3 這時(shí)x肯定就聲明在p中第65頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 建立訪問(wèn)鏈 假定嵌套深度為np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程x(1) np nx的情況 被調(diào)用過(guò)程的訪問(wèn)鏈必須指向

30、調(diào)用過(guò)程的活動(dòng)記錄的訪問(wèn)鏈第66頁(yè)/共149頁(yè) 訪問(wèn)非局部名字的存儲(chǔ)單元 sort readarray exchange quicksort partitionsa, xq (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈e (1, 3)訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈6.3 非局部名字的訪問(wèn)第67頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 建立訪問(wèn)鏈 假定嵌套深度為np的過(guò)程p

31、調(diào)用嵌套深度為nx的過(guò)程x(2) np nx的情況sort1readarray2exchange2quicksort2partition 3 這時(shí)p和x的嵌套深度分別為1，2，nx 1的外圍過(guò)程肯定相同第68頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) 建立訪問(wèn)鏈 假定嵌套深度為np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程x(2) np nx的情況 追蹤訪問(wèn)鏈np nx + 1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過(guò)程的最新活動(dòng)記錄 所到達(dá)的活動(dòng)記錄就是x的活動(dòng)記錄中的訪問(wèn)鏈應(yīng)該指向的那個(gè)活動(dòng)記錄第69頁(yè)/共149頁(yè) 訪問(wèn)非局部名字的存儲(chǔ)單元 sort readarray exchange quick

32、sort partitionsa, xq (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈e (1, 3)訪問(wèn)鏈sa, xq (1, 3)k, v訪問(wèn)鏈q (1, 9)k, v訪問(wèn)鏈p (1, 3)i, j訪問(wèn)鏈6.3 非局部名字的訪問(wèn)第70頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program param(input, output);（過(guò)程作為參數(shù)）procedure b(function h(n: integer): integer); beg

33、in 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ù)f作為參數(shù)傳遞時(shí)，怎樣在f被激活時(shí)建立它的訪問(wèn)鏈第71頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program param(input, output);（過(guò)程作為參數(shù)）procedure b(function h( begin writeln(h(2) end ;procedure c; var m: inte

34、ger; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin cend. 從b的訪問(wèn)鏈難以建立f的訪問(wèn)鏈訪 問(wèn) 鏈訪 問(wèn) 鏈paramcmb 第72頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program param(input, output);（過(guò)程作為參數(shù)）procedure b(function h( begin writeln(h(2) end ;procedure c; var m: integer; function f(n: integer) begin f := m+n end

35、f; begin m := 0; b(f) end c; begin cend. f作為參數(shù)傳遞時(shí)，它的起始地址連同它的訪問(wèn)鏈一起傳遞訪 問(wèn) 鏈訪 問(wèn) 鏈paramcmb 第73頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program param(input, output);（過(guò)程作為參數(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 c

36、end. b調(diào)用f時(shí)，用傳遞過(guò)來(lái)的訪問(wèn)鏈來(lái)建立f的訪問(wèn)鏈訪 問(wèn) 鏈訪 問(wèn) 鏈paramcmb 訪 問(wèn) 鏈b第74頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program ret (input, output);（過(guò)程作為返回值） var f: function (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; proced

37、ure b (g: function (integer): integer); begin writeln (g(2) end; begin f := a; b(f) end.aretbaddm第75頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program ret (input, output);（過(guò)程作為返回值） var f: function (integer): integer;function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m

38、+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.aretbaddm 執(zhí)行addm時(shí)，a的活動(dòng)記錄已不存在，取不到m的值第76頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn) C語(yǔ)言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問(wèn)的數(shù)據(jù)分成兩種情況 非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中 外部變量（包括定義在其它源文件之中的外部變量）和靜態(tài)的局部變量，它們都

39、分配在靜態(tài)數(shù)據(jù)區(qū) 因此C語(yǔ)言允許函數(shù)（的指針）作為返回值第77頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)6.3.3 動(dòng)態(tài)作用域 被調(diào)用過(guò)程的非局部名字a和它在調(diào)用過(guò)程中引用的是同樣的存儲(chǔ)單元 基于運(yùn)行時(shí)的調(diào)用關(guān)系 而不是基于靜態(tài)作用域來(lái)確定 新的綁定僅為被調(diào)用過(guò)程的局部名字建立，這些名字在被調(diào)用過(guò)程的活動(dòng)記錄中占用存儲(chǔ)單元 這一點(diǎn)與靜態(tài)作用域沒(méi)有區(qū)別第78頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small;

40、var r: real; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow第79頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)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

41、end; begin靜態(tài)作用域 r := 0.25;0.2500.250 show; small; writeln;0.2500.250 show; small; writeln end.dynamicshowsmallsmallshowshowshow第80頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)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動(dòng)

42、態(tài)作用域 r := 0.25;0.250 0.125 show; small; writeln;0.250 0.125 show; small; writeln end.dynamicshowsmallsmallshowshowshow第81頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)實(shí)現(xiàn)動(dòng)態(tài)作用域的方法 深訪問(wèn)用控制鏈搜索運(yùn)行棧，尋找包含該非局部名字的第一個(gè)活動(dòng)記錄 淺訪問(wèn) 為每個(gè)名字在靜態(tài)分配的存儲(chǔ)空間中保存它的當(dāng)前值 當(dāng)過(guò)程p的新活動(dòng)出現(xiàn)時(shí)，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的存儲(chǔ)單元。n的先前值保存在p的活動(dòng)記錄中，當(dāng)p的活動(dòng)結(jié)束時(shí)再恢復(fù)第82頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)pro

43、gram 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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow?r 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方dynamicr?第83頁(yè)/共149頁(yè)6.3 非局部名字

44、的訪問(wèn)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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0 . 25rdynamicr? 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方第84頁(yè)/共14

45、9頁(yè)6.3 非局部名字的訪問(wèn)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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0 . 25rdynamicr?s h ow 靜態(tài)區(qū)使用值的地方

46、 棧區(qū)暫存值的地方第85頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowshowshow0 . 25rdynamicr

47、?smallr0.25 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方第86頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamicshowsmallsmallshowsh

48、owshow0.125rdynamicr?smallr0.25 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方第87頁(yè)/共149頁(yè)6.3 非局部名字的訪問(wèn)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 (綠色表示已執(zhí)行部分) r := 0.25; show; small; writeln; show; small; writeln end.dynamic

49、showsmallsmallshowshowshow0.25rdynamicr? 靜態(tài)區(qū)使用值的地方 棧區(qū)暫存值的地方第88頁(yè)/共149頁(yè)6.4 參 數(shù) 傳 遞6.4.1 值調(diào)用 實(shí)參的右值傳給被調(diào)用過(guò)程 值調(diào)用可以如下實(shí)現(xiàn) 把形參當(dāng)作所在過(guò)程的局部名看待，形參的存儲(chǔ)單元在該過(guò)程的活動(dòng)記錄中 調(diào)用過(guò)程計(jì)算實(shí)參，并把其右值放入被調(diào)用過(guò)程形參的存儲(chǔ)單元中第89頁(yè)/共149頁(yè)6.4 參 數(shù) 傳 遞6.4.2 引用調(diào)用 實(shí)參的左值傳給被調(diào)用過(guò)程 引用調(diào)用可以如下實(shí)現(xiàn)： 把形參當(dāng)作所在過(guò)程的局部名看待，形參的存儲(chǔ)單元在該過(guò)程的活動(dòng)記錄中 調(diào)用過(guò)程計(jì)算實(shí)參，把實(shí)參的左值放入被調(diào)用過(guò)程形參的存儲(chǔ)單元 在被調(diào)

50、用過(guò)程的目標(biāo)代碼中，任何對(duì)形參的引用都是通過(guò)傳給該過(guò)程的指針來(lái)間接引用實(shí)參第90頁(yè)/共149頁(yè)6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用從概念上說(shuō)，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer; begin temp := x; x := y; y := temp end第91頁(yè)/共149頁(yè)6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用從概念上說(shuō)，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp:

51、integer ;例如：調(diào)用swap(i, ai) begin temp := x; x := y; y := temp end第92頁(yè)/共149頁(yè)6.4 參 數(shù) 傳 遞6.4.3 換名調(diào)用從概念上說(shuō)，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer ;例如：調(diào)用swap(i, ai) b e g i n 替 換 結(jié) 果 ： temp := i; temp := x; i := ai; x := y; ai := temp y := temp end第93頁(yè)/共149頁(yè)6.4 參 數(shù) 傳

52、 遞6.4.3 換名調(diào)用從概念上說(shuō)，每次調(diào)用時(shí)，用實(shí)參表達(dá)式對(duì)形參進(jìn)行正文替換，然后再執(zhí)行procedure swap(var x, y: integer);var temp: integer ;例如：調(diào)用swap(i, ai) b e g i n 替 換 結(jié) 果 ： temp := i; temp := x; i := ai; x := y; ai := temp y := temp 交換兩個(gè)數(shù)據(jù)的程序 end并非總是正確第94頁(yè)/共149頁(yè)6.5 堆 管 理堆式分配 堆用來(lái)存放生存期不確定的數(shù)據(jù) C+和Java允許程序員用new創(chuàng)建對(duì)象，它們的生存期沒(méi)有被約束在創(chuàng)建它們的過(guò)程活動(dòng)的生成期之

53、內(nèi) 實(shí)現(xiàn)內(nèi)存回收是內(nèi)存管理器的責(zé)任 堆空間的回收有兩種不同方式 程序顯式釋放空間：free（C）或delete（C+） 垃圾收集器自動(dòng)收集（Java）。11.3節(jié)介紹垃圾收集算法，本課程不做介紹第95頁(yè)/共149頁(yè)6.5 堆 管 理6.5.1 內(nèi)存管理器 內(nèi)存管理器把握的基本信息是堆中空閑空間 分配函數(shù) 回收函數(shù) 內(nèi)存管理器應(yīng)具有下列性質(zhì) 空間有效性：極小化程序需要的堆空間總量 程序有效性：較好地利用內(nèi)存子系統(tǒng)，使得程序能運(yùn)行得快一些 低開(kāi)銷(xiāo)：分配和回收操作所花時(shí)間在整個(gè)程序執(zhí)行時(shí)間中的比例盡量小第96頁(yè)/共149頁(yè)6.5 堆 管 理6.5.2 計(jì)算機(jī)內(nèi)存分層虛擬內(nèi)存(磁盤(pán))物理內(nèi)存2級(jí)緩存1

54、級(jí)緩存寄存器(處理器)典型大小 2千兆字節(jié)256兆2千兆字節(jié)128千4兆字節(jié)1664千字節(jié)32字典型訪問(wèn)時(shí)間315微秒100150納秒4060納秒510納秒1納秒第97頁(yè)/共149頁(yè)6.5 堆 管 理6.5.2 計(jì)算機(jī)內(nèi)存分層 現(xiàn)代計(jì)算機(jī)都設(shè)計(jì)成程序員不用關(guān)心內(nèi)存子系統(tǒng)的細(xì)節(jié)就可以寫(xiě)出正確的程序 程序的效率不僅取決于被執(zhí)行的指令數(shù)，還取決于執(zhí)行每條指令需要多長(zhǎng)時(shí)間 執(zhí)行一條指令的時(shí)間區(qū)別非?？捎^ 差異源于硬件技術(shù)的基本局限：構(gòu)造不了大容量的高速存儲(chǔ)器 數(shù)據(jù)以塊（緩存行、頁(yè)）為單位在相鄰層次之間進(jìn)行傳送 數(shù)據(jù)密集型程序可從恰當(dāng)利用內(nèi)存子系統(tǒng)中獲益第98頁(yè)/共149頁(yè)6.5 堆 管 理6.5.3

55、程序局部性 大多數(shù)程序的大部分時(shí)間在執(zhí)行一小部分代碼，并且僅涉及一小部分?jǐn)?shù)據(jù) 時(shí)間局部性 程序訪問(wèn)的內(nèi)存單元在很短的時(shí)間內(nèi)可能再次被程序訪問(wèn) 空間局部性 毗鄰被訪問(wèn)單元的內(nèi)存單元在很短的時(shí)間內(nèi)可能被訪問(wèn)第99頁(yè)/共149頁(yè)6.5 堆 管 理6.5.3 程序局部性 即使知道哪些指令會(huì)被頻繁執(zhí)行，最快的緩存也可能沒(méi)有大到足以把它們同時(shí)放在其中，因此必須動(dòng)態(tài)調(diào)整最快緩存的內(nèi)容 把最近使用的指令保存在緩存是一種較好的最優(yōu)化利用內(nèi)存分層的策略 改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪問(wèn)的時(shí)間和空間局部性第100頁(yè)/共149頁(yè)6.5 堆 管 理例： 一個(gè)結(jié)構(gòu)體大數(shù)組分拆成若干個(gè)數(shù)組 struct stu

56、dent int num10000; i n t n u m ;c h a r name1000020; char name20; struct student st10000; 若是順序處理每個(gè)結(jié)構(gòu)體的多個(gè)域，左邊方式的數(shù)據(jù)局部性較好 若是先順序處理每個(gè)結(jié)構(gòu)的num域，再處理每個(gè)結(jié)構(gòu)的name域，則右邊方式的數(shù)據(jù)局部性較好 最好是按左邊方式編程，由編譯器決定是否需要將數(shù)據(jù)按右邊方式布局第101頁(yè)/共149頁(yè)6.5 堆 管 理6.5.4 手工回收請(qǐng)求 程序員在程序中顯式釋放堆塊來(lái)達(dá)到回收堆塊的目的 內(nèi)存泄漏：沒(méi)有釋放程序已經(jīng)引用不到的堆塊 只要內(nèi)存沒(méi)有用盡，它就不影響程序的正確性 自動(dòng)無(wú)用單元

57、收集通過(guò)回收所有無(wú)用單元來(lái)擺脫內(nèi)存泄漏 懸空引用：引用已經(jīng)被釋放的堆塊 過(guò)分熱心地釋放數(shù)據(jù)對(duì)象而引起 懸空引用容易導(dǎo)致不會(huì)被捕獲的錯(cuò)誤 第102頁(yè)/共149頁(yè)本 章 要 點(diǎn) 影響存儲(chǔ)分配策略的語(yǔ)言特征 各種存儲(chǔ)分配策略，主要了解靜態(tài)分配和動(dòng)態(tài)棧式分配 活動(dòng)記錄中各種數(shù)據(jù)域的作用和布局 非局部數(shù)據(jù)訪問(wèn)的實(shí)現(xiàn)方法 各種參數(shù)傳遞方式及其實(shí)現(xiàn) 堆管理第103頁(yè)/共149頁(yè)例 題 1一個(gè)C語(yǔ)言程序及其在X86/Linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來(lái)解釋程序中四個(gè)變量的存儲(chǔ)分配、生存期、作用域和置初值方式等方面的區(qū)別static long aa = 10;short bb = 20;f

58、unc( ) static long cc = 30; short dd = 40;第104頁(yè)/共149頁(yè)例 題 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|. . .static long aa =

59、 10;short bb = 20;func( ) static long cc = 30; short dd = 40; 第105頁(yè)/共149頁(yè)例 題 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|.

60、 . .static long aa = 10;short bb = 20;func( ) static long cc = 30; short dd = 40; 第106頁(yè)/共149頁(yè)例 題 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(