【正文】 編譯原理和技術(shù) 中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 陳意云 第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 術(shù)語(yǔ) – 過(guò)程的 活動(dòng) 過(guò)程的一次執(zhí)行稱為過(guò)程的一次活動(dòng) – 活動(dòng)記錄 過(guò)程的活動(dòng)需要可執(zhí)行代碼和存放所需信息的存儲(chǔ)空間 ,后者稱為活動(dòng)記錄 本章內(nèi)容 ? 討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)布局 ? 程序執(zhí)行過(guò)程中，所有活動(dòng)記錄的組織方式 第六章 運(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ǔ)塊是否必須顯式地釋放 局部存儲(chǔ)分配 過(guò)程 語(yǔ)言概念： 過(guò)程定義、 過(guò)程 調(diào)用、形式參數(shù)、實(shí)在參數(shù)、 活動(dòng)的 生存期 局部存儲(chǔ)分配 名字的作用域和綁定 名字的作用域 ? 一個(gè)聲明起作用的程序部分稱為該聲明的 作用域 ? 即使一個(gè)名字在程序中只聲明一次，該名字在程序運(yùn)行時(shí)也可能表示不同的數(shù)據(jù)對(duì)象 局部存儲(chǔ)分配 環(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)境 局部存儲(chǔ)分配 靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng) 靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過(guò)程的定義 過(guò)程的活動(dòng) 局部存儲(chǔ)分配 靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng) 靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過(guò)程的定義 過(guò)程的活動(dòng) 名字的聲明 名字的綁定 局部存儲(chǔ)分配 靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng) 靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過(guò)程的定義 過(guò)程的活動(dòng) 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 局部存儲(chǔ)分配 活動(dòng)記錄 活動(dòng)記錄的常見(jiàn)布局 返 回 值 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 控 制 鏈 訪 問(wèn) 鏈 機(jī) 器 狀 態(tài) 局 部 數(shù) 據(jù) 局部存儲(chǔ)分配 局部數(shù)據(jù)的布局 ? 字節(jié)是可編址內(nèi)存的最小單位 ? 變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定 ? 一個(gè)過(guò)程所聲明的局部變量 ， 按這些變量聲明時(shí)出現(xiàn)的次序 ， 在局部數(shù)據(jù)域中依次分配空間 ? 局部數(shù)據(jù)的地址可以用相對(duì)于活動(dòng)記錄中某個(gè)位置的地址來(lái)表示 ? 數(shù)據(jù)對(duì)象的存儲(chǔ)布局還有一個(gè)對(duì)齊問(wèn)題 局部存儲(chǔ)分配 ? 例 在 SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)體的 size分別是 24和 16， 為什么不一樣 ？ typedef struct _a{ typedef struct _b{ char c1。 char c1。 long i。 char c2。 char c2。 long i。 double f。 double f。 }a。 }b。 對(duì)齊： char : 1, long : 4, double : 8 局部存儲(chǔ)分配 ? 例 在 SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)體的 size分別是 24和 16， 為什么不一樣 ？ typedef struct _a{ typedef struct _b{ char c1。 0 char c1。 0 long i。 4 char c2。 1 char c2。 8 long i。 4 double f。 16 double f。 8 }a。 }b。 對(duì)齊： char : 1, long : 4, double : 8 局部存儲(chǔ)分配 ? 例 在 X86/Linux機(jī)器的結(jié)果和 SPARC/Solaris工作站不一樣 ， 是 20和 16。 typedef struct _a{ typedef struct _b{ char c1。 0 char c1。 0 long i。 4 char c2。 1 char c2。 8 long i。 4 double f。 12 double f。 8 }a。 }b。 對(duì)齊： char : 1, long : 4, double : 4 局部存儲(chǔ)分配 程序塊 ? 本身含有局部變量聲明的語(yǔ)句 ? 可以嵌套 ? 最接近的嵌套 作用域規(guī)則 ? 并列程序塊不會(huì)同時(shí)活躍 ? 并列程序塊的變量可以重疊分配 局部存儲(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 ?/ 局部存儲(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 = 2。 B2 int b = 3。 B3 a0 b0 b1 a2, b3 重疊分配存儲(chǔ)單元 全局棧式存儲(chǔ)分配 本節(jié)介紹 ? 介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略 ? 描述過(guò)程的目標(biāo)代碼怎樣訪問(wèn)綁定到局部名字的存儲(chǔ)單元 ? 介紹三種分配策略 – 靜態(tài)分配策略 – 棧式分配策略 – 堆式分配策略 全局棧式存儲(chǔ)分配 運(yùn)行時(shí)內(nèi)存的劃分 代 碼 靜 態(tài) 數(shù) 據(jù) 堆 棧 全局棧式存儲(chǔ)分配 靜態(tài)分配 ? 名字在程序被編譯時(shí)綁定到存儲(chǔ)單元 ， 不需要運(yùn)行時(shí)的任何支持 ? 綁定的生存期是程序的整個(gè)運(yùn)行期間 全局棧式存儲(chǔ)分配 靜態(tài)分配給語(yǔ)言帶來(lái)限制 ? 遞歸過(guò)程不被允許 ? 數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中位置的限制 ，必須是在編譯時(shí)可以知道的 ? 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立 全局棧式存儲(chǔ)分配 ? 例 C程序的外部變量 、 靜態(tài)局部變量以及程序中出現(xiàn)的常量都可以靜態(tài)分配 ? 聲明在函數(shù)外面 – 外部變量 靜態(tài)分配 – 靜態(tài)外部變量 靜態(tài)分配 ? 聲明在函數(shù)里面 – 靜態(tài)局部變量 也是靜態(tài)分配 – 自動(dòng)變量 不能靜態(tài)分配 全局棧式存儲(chǔ)分配 活動(dòng)樹(shù)和運(yùn)行棧 活動(dòng)樹(shù) – 用樹(shù)來(lái)描繪控制進(jìn)入和離開(kāi)活動(dòng)的方式 m q(1,9) r p(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) 全局棧式存儲(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的生存期 m q(1,9) r p(1,9) q(1,3) . . . . q(5,9) . . . . 全局棧式存儲(chǔ)分配 ? 當(dāng)前活躍著的過(guò)程活動(dòng)可以保存在一個(gè)棧中 – 例 控制棧的內(nèi)容： m, q (1, 9), q (1, 3), q (2, 3) m q(1,9) r p(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) 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） m a : array m 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） m i: integer r a : array m r 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） m k: integer q (1, 9) a : array m q(1,9) r 全局棧式存儲(chǔ)分配 運(yùn)行棧： 把控制棧中的信息拓廣到包括過(guò)程活動(dòng)所需的所有局部信息 （ 即活動(dòng)記錄 ） m k: integer q (1, 9) a : array q (1, 3) k: integer m q(1,9) r p(1,9) q(1,3) q(1,0) p(1,3) 全局棧式存儲(chǔ)分配 調(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ò)程中 全局棧式存儲(chǔ)分配 ? 即使是同一種語(yǔ)言 ， 過(guò)程調(diào)用序列 、 返回序列和活動(dòng)記錄中各域的排放次序 ， 也會(huì)因?qū)崿F(xiàn)而異 ? 設(shè)計(jì)這些序列和活動(dòng)記錄 的一些原則 – 以活動(dòng)記錄中間的某個(gè) 位置作為基地址 – 長(zhǎng)度能較早確定的域放在 活動(dòng)記錄的中間 返 回 值 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 控 制 鏈 訪 問(wèn) 鏈 機(jī) 器 狀 態(tài) 局 部 數(shù) 據(jù) 全局棧式存儲(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ù) 控 制 鏈 訪 問(wèn) 鏈 機(jī) 器 狀 態(tài) 局 部 數(shù) 據(jù) 全局棧式存儲(chǔ)分配 ? 即使是同一種語(yǔ)言 ， 過(guò)程調(diào)用序列 、 返回序列和活動(dòng)記錄中各域的排放次序 ， 也會(huì)因?qū)崿F(xiàn)而異 ? 設(shè)計(jì)這些序列和活動(dòng)記錄 的一些原則 – 用同樣的代碼來(lái)執(zhí)行各個(gè) 活動(dòng)的保存和恢復(fù) 返 回 值 臨 時(shí) 數(shù) 據(jù) 參 數(shù) 控 制 鏈 訪 問(wèn) 鏈 機(jī) 器 狀 態(tài) 局 部 數(shù) 據(jù) 全局棧式存儲(chǔ)分配 過(guò)程 p調(diào)用過(guò)程 q的調(diào)用序列 返回值和參數(shù) top_sp base_sp 臨時(shí)數(shù)據(jù)局部數(shù)據(jù) 控制鏈 和保存的機(jī)器狀態(tài) ? ? ?