【正文】 。 subl $4,%esp 為 j分配空間 j= i 1。 pop ebp ret 即 pop eip(下條指令地址 ） . . . . . . ebp esp 參數(shù) i 返址 控制鏈 例 題 2 func(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í)參 j的值壓棧 call func 函數(shù)調(diào)用 addl $4,%esp 恢復(fù)棧頂指針 L1: leave 即 mov ebp, esp。 pop ebp ret 即 pop eip(下條指令地址 ） . . . . . . ebp esp 例 題 2 func(i) func: long i。 pushl %ebp 老的基地址指針壓棧 { movl %esp,%ebp修改 基地址指針 long j。 subl $4,%esp 為 j分配空間 j= i 1。 j= i 1。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 func( ) { static long cc = 30。 … … … … } struct student st[10000]。 收集算法 ， 本課程不做介紹 堆 管 理 內(nèi)存管理器 ? 內(nèi)存管理器把握的基本信息是堆中空閑空間 – 分配函數(shù) – 回收函數(shù) ? 內(nèi)存管理器應(yīng)具有下列性質(zhì) – 空間有效性：極小化程序需要的堆空間總量 – 程序有效性：較好地利用內(nèi)存子系統(tǒng) ， 使得程序能運(yùn)行得快一些 – 低開銷 ： 分配和回收操作所花時(shí)間在整個(gè)程序執(zhí)行時(shí)間中的比例盡量小 堆 管 理 計(jì)算機(jī)內(nèi)存分層 虛擬內(nèi)存 (磁盤 ) 物理內(nèi)存 2級(jí)緩存 1級(jí)緩存 寄存器 (處理器 ) 典型大小 2千兆字節(jié) 256兆 ?2千兆字節(jié) 128千 ?4兆字節(jié) 16?64千字節(jié) 32字 典型訪問(wèn)時(shí)間 3?15微秒 100?150納秒 40?60納秒 5?10納秒 1納秒 堆 管 理 計(jì)算機(jī)內(nèi)存分層 – 現(xiàn)代計(jì)算機(jī)都設(shè)計(jì)成程序員不用關(guān)心內(nèi)存子系統(tǒng)的細(xì)節(jié)就可以寫出正確的程序 – 程序的效率不僅取決于被執(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)中獲益 堆 管 理 程序局部性 ? 大多數(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) 堆 管 理 程序局部性 – 即使知道哪些指令會(huì)被頻繁執(zhí)行 ， 最快的緩存也可能沒有大到足以把它們同時(shí)放在其中 ， 因此必須動(dòng)態(tài)調(diào)整最快緩存的內(nèi)容 – 把最近使用的指令保存在緩存是一種較好的最優(yōu)化利用內(nèi)存分層的策略 – 改變數(shù)據(jù)布局或計(jì)算次序也可以改進(jìn)程序數(shù)據(jù)訪問(wèn)的時(shí)間和空間局部性 堆 管 理 例： 一個(gè)結(jié)構(gòu)體大數(shù)組 分拆成若干個(gè)數(shù)組 struct student { int num[10000]。 temp := x。 x := y。 var temp: integer。 var temp: integer。 var temp: integer。 writeln。 show end。 begin write(r: 5: 3) end。 small。 show。 var r: real。 var r: real。 writeln。 show end。 begin write(r: 5: 3) end。 small。 show。 var r: real。 var r: real。 writeln。 show end。 begin write(r: 5: 3) end。 small。 show。 var r: real。 var r: real。 show。 begin 動(dòng) 態(tài)作用域 r := 。 procedure small。 writeln end. dynamic show small small show show show 非局部名字的訪問(wèn) program dynamic(input, output)。 small。 begin r := 。 procedure show。 show。 begin r := 。 procedure small。 b(f) end. a ret b addm 執(zhí)行 addm時(shí)， a的活動(dòng)記錄已不存在，取不到 m的值 非局部名字的訪問(wèn) ? C語(yǔ)言的函數(shù)聲明不能嵌套 ， 函數(shù)不論在什么情況下激活 ， 要訪問(wèn)的數(shù)據(jù)分成兩種情況 – 非靜態(tài)局部變量 （ 包括形式參數(shù) ） ， 它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中 – 外部變量 （ 包括定義在其它源文件之中的外部變量 ） 和靜態(tài)的局部變量 ， 它們都分配在靜態(tài)數(shù)據(jù)區(qū) – 因此 C語(yǔ)言允許函數(shù) （ 的指針 ） 作為返回值 非局部名字的訪問(wèn) 動(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)作用域沒有區(qū)別 非局部名字的訪問(wèn) program dynamic(input, output)。 return addm end。 var m: integer。 begin f := a。 begin m:= 0。 function a: function (integer): integer。 begin m := 0。（ 過(guò)程作為參數(shù) ） procedure b(function h(… begin writeln(h(2)) end 。 function f(n: integer)… begin f := m+n end {f}。 begin c end. 從 b的訪問(wèn)鏈難以建立 f的訪問(wèn)鏈 訪 問(wèn) 鏈 訪 問(wèn) 鏈 param c m b f 非局部名字的訪問(wèn) program param(input, output)。 var m: integer。 b(f) end {c}。 var m: integer。 } | } 非局部名字的訪問(wèn) 本節(jié)介紹 ? 無(wú)過(guò)程嵌套的靜態(tài)作用域 （ C語(yǔ)言 ） ? 有過(guò)程嵌套的靜態(tài)作用域 （ Pascal語(yǔ)言 ） ? 動(dòng)態(tài)作用域 （ Lisp語(yǔ)言 ） 非局部名字的訪問(wèn) 無(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)返回 非局部名字的訪問(wèn) 有過(guò)程嵌套的靜態(tài)作用域 sort readarray exchange quicksort partition 非局部名字的訪問(wèn) 有過(guò)程嵌套的靜態(tài)作用域 ? 過(guò)程 嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 ? 變量的嵌套深度：它的聲明所在過(guò)程的嵌套 深度作為該名字的嵌套深度 ? 訪問(wèn)鏈 – 用來(lái)尋找非局部 名字的存儲(chǔ)單元 s a, x q (1, 9) k, v 訪問(wèn)鏈 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 s a, x q (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)鏈 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 p (1, 3) i, j 訪問(wèn)鏈 非局部名字的訪問(wèn) 非局部名字的訪問(wèn) ? 訪問(wèn)非局部名字的存儲(chǔ)單元 假定過(guò)程 p的嵌套深度為 np， 它引用嵌套深度為 na 的變量 a， na ? np， 如何訪問(wèn) a的存儲(chǔ)單元 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 非局部名字的訪問(wèn) ? 訪問(wèn)非局部名字的存儲(chǔ)單元 假定過(guò)程 p的嵌套深度為 np， 它引用嵌套深度為 na 的變量 a， na ? np， 如何訪問(wèn) a的存儲(chǔ)單元 – 從棧頂?shù)幕顒?dòng)記錄開始 ， 追蹤訪問(wèn)鏈 np ? na次 – 到達(dá) a的聲明所在過(guò)程的活動(dòng)記錄 – 訪問(wèn)鏈的追蹤用間接操作就可完成 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 ? 訪問(wèn)非局部名字的存儲(chǔ)單元 sort readarray exchange quicksort partition s a, x q (1, 9) k, v 訪問(wèn)鏈 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 s a, x q (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)鏈 s a, x q (1, 3) k, v 訪問(wèn)鏈 q (1, 9) k, v 訪問(wèn)鏈 p (1, 3) i, j 訪問(wèn)鏈 非局部名字的訪問(wèn) 非局部名字的訪問(wèn) ? 過(guò)程 p對(duì)變量 a訪問(wèn)時(shí) ， a的地址由下面的二元組表示： （ np ? na， a在活動(dòng)記錄中的偏移 ） 非局部名字的訪問(wèn) ? 建立訪問(wèn)鏈 – 假定嵌套深度為 np的過(guò)程 p調(diào)用嵌套深度為 nx的過(guò)程 x