1、第七章運轉時辰環境湖南大學計算機與通訊學院軟件學院編譯器的一些問題變量的存儲位置如何分配？名字的作用域如何實現？過程調用如何實現？參數傳送如何實現？這些問題需求依托運轉時環境來輔助處理。運轉時辰環境運轉時辰環境為數據分配安排存儲位置確定訪問變量時運用的機制過程之間的銜接參數傳送和操作系統、輸入輸出設備相關的其它接口主題存儲管理：棧分配、堆管理、渣滓回收對變量、數據的訪問存儲分配的典型方式目的程序的代碼放置在代碼區，通常位于存儲的低端靜態區、堆區、棧區分別放置不同類型生命期的數據值,實際中棧向較低地址方向增長堆向較高方向增長。圖7-1編譯的結果全局/靜態變量共享*從如今開場要留意，為使我們能在一

2、切的例子中方便地運用正的偏移量,棧向較高地址方向增長，即頂是在最下端。0X00H0XFFFFH.靜態和動態存儲分配靜態分配編譯器在編譯時辰就可以做出存儲分配決議，不需求思索程序運轉時辰的情形，如：靜態變量言語中static變量全局變量動態分配棧式存儲：過程的部分名字采用棧式存儲和過程的調用/前往同步進展分配和回收，值的生命期和過程生命期一樣堆heap存儲：有些數據生命期比相應過程調用的生命期更長，常分配在一個可重用存儲的“堆中。堆和渣滓回收堆是虛擬內存的一個區域，它允許對象或其他數據元素在被創建時獲得存儲空間，并在數據變得無效時釋放該存儲空間渣滓回收：檢測出堆中無用的數據元素，釋放它們的空間手

3、工進展回收程序員渣滓回收機制，如：棧式分配內容：活動樹活動記錄調用(代碼)序列棧中的變長數據活動樹過程調用過程活動在時間上總是嵌套的：后調用的先前往(LIFO)因此可以用棧式分配來處置過程活動所需求的內存空間。程序運轉的一切過程活動可以用樹表示每個結點對應于一個過程活動根結點對應于main過程的活動過程p的某次活動對應的結點的子結點對應于此次活動調用的各個過程活動從左向右，表示調用的先后順序活動樹的例子快速排序1活動樹的例子快速排序程序：P260，圖7-2過程調用前往序列和活動樹的前序后序遍歷對應假定當前活動對應結點N，那么一切尚未終了的結點對應于N及其祖先結點。活動記錄過程調用和前往由控制棧

4、進展管理過程活動記錄：當調用過程或函數時，為其部分數據動態分配的存儲區活動記錄按照活動的開場時間，從棧底到棧頂陳列圖活動記錄框架計算中間結果部分變量活動記錄控制鏈：指向調用者的活動記錄固定長度部分訪問鏈：活動記錄中指向上一級活動記錄(包含嵌套的環境定義的活動記錄)的指針保管的機器形狀：此次調用前的機器形狀信息，如：前往地址及一些存放器的值運轉時辰棧的例子例：快速排序a11為全局變量main沒有部分變量r有部分變量iq的部分變量i，和參數m,n。Main的活動記錄調用序列調用序列(calling sequence)為活動記錄分配空間，填寫記錄中的信息；前往序列(return sequence)恢

5、復機器形狀，使調用者繼續運轉。調用序列會分割到調用者和被調用者中。根據源言語、目的機器、操作系統的限制，可以有不同的分割方案把代碼盡能夠放在被調用者中。調用/前往序列的要求數據方面可以把參數正確地傳送給被調用者可以把前往值傳送給調用者控制方面可以正確轉到被調用者的代碼的開場位置可以正確轉回調用者的調用位置的下一條指令調用序列和活動記錄的規劃相關活動記錄的規劃原那么調用者和被調用者之間傳送的值放在被調用者記錄的開場位置固定長度的項放在中間位置控制鏈、訪問鏈、機器形狀字段早期不知道大小的項在活動記錄尾部干脆將固定長度的部分變量也放入該段棧頂指針通常指向固定長度字段的末端top_sp調用代碼序列的例

6、子Calling sequence調用序列調用者計算真實參數的值將前往地址和原top_sp控制鏈存放到被調用者的活動記錄中。調用者添加top_sp的值越過了調用者的部分數據、暫時變量、被調用者的參數、機器形狀字段被調用者保管存放器值和其他形狀字段被調用者初始化部分數據、開場運轉。Return sequence 前往序列被調用者將前往值放到和參數相鄰的位置恢復top_sp和存放器，跳轉到前往地址。棧中的變長數據假設數據對象的生命期局限于過程活動的生命期，就可以分配在運轉時辰棧中。top指向實踐的棧頂top_sp用于尋覓頂層記錄的定長字段框架指針例 利用Euclid算法的簡單遞歸算法，計算兩個非負

7、整數的最大公約數。程序清單 C代碼#include int x, y;int gcd(int u, int v) if (v=0) return u; else return gcd(v, u%v);main() scanf(“%d%d, &x, &y); printf(“%dn, gcd(x,y); return 0; 假設輸入為，試畫出運轉的活動樹試畫出運轉時棧變化過程main()gcd(15,10)gcd(10,5)gcd(5,0)第3個調用時的環境如圖7-2所示。x:15y:10u:15v:10控制鏈前往地址部分變量u:10v:5控制鏈前往地址部分變量u:5v:0控制鏈前往地址部分變量

8、自在空間Top_sptop全局靜態區域main的活動記錄第一次調用gcd時的活動記錄第二次調用gcd時的活動記錄第三次調用gcd時的活動記錄棧的生長方向基于棧的環境main()gcd(15,10)gcd(10,5)gcd(5,0)前往值為基于棧的運轉時環境留意：同一個過程的不同活動對應的活動記錄的大小完全一樣；新的活動記錄總是在棧頂參與；其控制鏈總是指向先前的活動記錄的控制鏈；top_sp指向當前活動記錄的控制鏈；調用前往時，將按順序從棧中刪去每個活動記錄；當在main中執行printf語句時，環境中只保管了main的活動記錄和全局/靜態區域。7.3 棧中非部分數據的訪問7.3.1無嵌套過程時

9、的數據訪問無嵌套過程時的數據訪問例：言語不允許嵌套過程聲明，變量要么在函數內定義，要么全局地定義C言語中函數對變量的訪問部分變量：在當前活動記錄內，可經過top_sp指針加上相對地址來訪問全局/靜態變量：在靜態區，地址在編譯時可知C言語允許函數參數參數中只需求包括函數代碼的起始地址。在函數中訪問變量的方式很簡單，不需求思索過程是如何激活的。C言語中活動記錄中無需訪問鏈7.3 基于棧的運轉時環境1) 對稱號的訪問在基于棧的環境中，要訪問參數和部分變量，可用當前框架指針(top_sp)的偏移量實現。在大多數的言語中，每個部分聲明的偏移量可由編譯程序靜態地計算出來。由于過程的聲明在編譯時是固定的，而

10、且為每個聲明分配的存儲器大小也根據其數據類型而固定。例 思索C過程void f(int x, char c) int a10; double y; . . . 對f調用的活動記錄ya9a1a0前往地址控制鏈cxx偏移量top_spc偏移量a偏移量y偏移量*此處在前往地址下省略了被保管的形狀等信息整型4個字節、地址4個字節、字符1個字節、雙精度浮點數8個字節，那么偏移量為：稱號偏移量 x-9 c-8 a+0 y+40 ai的地址為：0+4*i+ top_sp。在基于棧的環境中，非部分的和靜態的名字的地址都是固定的靜態地址，可以直接訪問。*留意在本章內，棧是往下面大端生長的。非部分數據的訪問嵌套過

11、程PASCAL言語允許過程嵌套定義，且遵照靜態作用域規那么代碼運轉時，對變量的訪問應指向運轉棧中最上層的同名變量。問題：變量不一定在當前活動記錄中，如何確定其位置？思索：符號表中存儲了變量的偏移量，因此只需求確定的活動記錄。子問題：用嵌套層次可以完全處理這個問題嗎？非部分數據的訪問嵌套過程問題：用調用層次可以完全處理這個問題嗎？void A()intx,y;voidB()int b;x = b+y;voidC()B(); C();B的活動記錄C的活動記錄A的活動記錄當A調用C，C又調用B時:不能！A,B的層次差是，但B的控制鏈并沒有直接指向A處理方法：引入訪問鏈指向過程的定義環境7.3.3 一

12、個支持嵌套過程聲明的言語最新的支持嵌套過程的典型言語之一：MLML是一種函數式言語，變量一旦聲明并初始化就不會再改動有少數例外，如：數組元素可經過特殊的函數調用改動變量定義并初始化為不可更改的值的語句方式： =函數定義的語法：Fun ()=函數體(body)定義的語法：Let in end嵌套深度嵌套深度是正文概念，可根據源程序靜態地確定不內嵌于任何其他過程中的過程，嵌套深度為1嵌套在深度為i的過程中的過程，深度為i+1.深度為1sort深度為2readArray，exchange，quicksort深度為3partition圖7-10 一個運用嵌套函數聲明的ML風格的quicksort訪問鏈

13、顯式表顯式表訪問鏈引入訪問鏈的目的：訪問非部分數據假設過程p在聲明時嵌套在過程q的聲明中，那么p的活動記錄中的訪問鏈指向最上層最新的q的活動記錄。從棧頂活動記錄開場，訪問鏈構成了一個鏈路，嵌套深度逐一遞減。設深度為np的過程p訪問變量x，而變量x在深度為nq的過程中聲明，那么從當前活動記錄出發，沿訪問鏈前進np-nq次找到活動記錄其中的x就是要找的變量位置x相對于該活動記錄的偏移量在編譯時辰知np和-nq在編譯時辰知；訪問鏈的例子P270圖7-11 用來查找非部分數據的訪問鏈sort活動記錄訪問鏈的處置明確調用過程與聲明嵌套深度的關系當過程q調用過程p時，P訪問鏈如何設置？把p的聲明嵌套深度n

14、p與nq的關系分為大于，等于，小于三種情況思索p的聲明嵌套深度大于q，p必然在q中直接定義，否那么不滿足作用域規那么，那么p的訪問鏈指向當前活動記錄(即父親直接調用孩子)遞歸調用：p=q 。p的活動記錄的訪問鏈等于q當前記錄的訪問鏈(即本身等于本身)p的聲明嵌套深度小于q的深度：此時必然有過程r，p直接在r中定義，而q嵌套在r中。此時應讓p的訪問鏈指向r的活動記錄。(即q是p的侄子系的，r是p的父親)rpq.7.3.6 過程型參數的訪問鏈有些言語允許過程作為參數，如：言語例：tiny編譯器中語義分析程序analyze.c的transverse函數聲明如下：static void travers

15、e( TreeNode * t, void (* preProc) (TreeNode *), void (* postProc) (TreeNode *) )構建符號表前序遍歷語法樹traverse(syntaxTree,insertNode,nullProc);類型檢查時后序遍歷語法樹traverse(syntaxTree,nullProc,checkNode);7.3.6 過程型參數的訪問鏈當一個過程作為參數傳送給另一個過程，并且隨后調用了這個參數，有能夠并不知道在程序中出現的上下文后果：不知道如何設置的訪問鏈處理方法： 在傳送過程指針參數時，過程型參數中不僅包含過程的代碼指針(IP)，

16、還包括正確的訪問鏈AL)。7.3.6 過程型參數的訪問鏈圖-12 運用函數參數的ML程序的概要f是一個函數參數對的援用d被用作函數參數7.3.6 過程型參數的訪問鏈由于d在c中定義7.3.8 顯示表display)用訪問鏈訪問數據時，假設嵌套深度大，那么訪問的效率差。顯示表：運用數組d為每個嵌套深度保管一個指針指針di指向棧中最高的對應于嵌套深度為i的的活動記錄。假設程序p中訪問嵌套深度為i的過程q中變量x，那么di直接指向相應的q活動記錄；顯示表的維護調用過程p時，在p的活動記錄中保管原dnp的值，并將dnp設置為p的該次活動記錄。從p前往時，恢復dnp的值。顯示表舉例q(1,9)調用q(1

17、,3)時，q的深度為2例： ML風格的quicksort顯示表舉例q(1,3)調用p，p的深度為3q調用e，e的深度為2例： ML風格的quicksort嵌套層次構造分析偽代碼Display(1)main-(2)P-(3)Q-(4)R主程序的活動記錄 d1display棧頂1主程序的活動記錄P 的活動記錄 d1d2display棧頂2棧棧主程序-P-Q-R主程序的活動記錄P 的活動記錄 Q 的活動記錄R 的活動記錄主程序的活動記錄 P 的活動記錄Q 的活動記錄 displayd1d2d3 d1d2d3 display34棧頂棧棧棧頂堆管理堆空間用于存放生命周期不確定、或者生存到被顯式刪除為止的

18、數據對象，例：new生成的對象可以生存到被delete為止Malloc懇求的空間生存到被free為止存儲管理器分配/回收堆區空間的子系統根據言語而定C、C+需求手動回收空間Java可以自動回收空間渣滓搜集存儲管理器的根本功能分配：為每個內存懇求分配一段延續的、適當大小的堆空間。首先從空閑堆空間分配；假設沒有可分配的堆空間，那么從操作系統中獲得延續的虛擬內存來添加堆空間；如空間已用完，那么將空間耗盡的音訊反響給運用程序回收：把被回收的空間前往空閑空間緩沖池，以滿足以后的分配懇求。期望的存儲管理器特性空間效率使程序所需堆空間最小實現手段：最小化存儲碎片程序效率充分利用存儲子系統，提高程序運轉效率在

19、存儲子系統中，不同的層次訪問速度不一樣盡能夠多的利用高訪問速度的存儲器件，可大幅度提高效率低開銷最小化分配/收回內存的開銷即破費在分配和回收上的執行時間在總運轉時間中所占的比例注：分配的開銷由小型懇求決議，管理大型對象的開銷相對不重要 一次內存訪問中，機器首先在最低層的存儲中尋覓數據，假設數據不在那里那么到上一層中尋覓。程序的部分性大部分程序呈現高度的部分性即程序的大部分運轉時間破費在相對較小的一部分代碼時間部分性假設一個程序訪問的存儲位置很能夠將在一個很短的時間段內被再次訪問，稱其具有時間部分性空間部分性假設被訪問的存儲位置的臨近位置很能夠將在一個很短的時間段內被再次訪問，稱其具有空間部分性

20、程序的部分性程序把90的時間用于執行10的代碼，緣由如下：程序常包含許多從不被執行的指令如：運用組件和庫構建的程序只運用了它們提供的一小部分功能隨需求變化和程序演化，遺留系統中經常包含許多不再被運用的指令有大量容錯和調試代碼在正常運轉時不執行執行最內層循環和最緊湊遞歸環破費了程序執行的大部分時間堆空間的碎片問題程序運轉前，堆是一個延續的自在空間隨著程序分配/回收內存，堆區逐漸被分割成空閑存儲塊窗口，hole和已用存儲塊分配內存時，通常是把一個窗口的一部分分配出去，其他部分成為更小的塊。回收時，被釋放的存儲塊被放回緩沖池。通常會把延續的窗口接合成為更大的窗口。堆空間分配方法Best-Fit最正確

21、順應優先在滿足懇求的最小窗口中分配內存優點：可將大窗口保管下來以應對更大的懇求First-Fit最先順應優先在第一個滿足懇求的窗口中分配內存優點：快，常具有較好數據部分性同一段時間內的對象分配延續空間缺陷：總體性能較差運用容器的管理方法設定不同大小的空閑塊，并將同樣大小的塊放在容器中。較小的較常用的尺寸設置較多的容器。比如GNU的C編譯器gcc運用存儲管理器lea將一切存儲塊對齊到8字節邊境?？臻e塊的尺寸大?。?6,24,32,40,512相鄰間相差8大于512的按照對數值劃分(每個容器的最小尺寸是前一個容器的最小尺寸的兩倍。)荒野塊：可以擴展的內存塊分配方法：對于小尺寸的懇求，直接在相應容器中找。大尺寸的懇求，在適當的容器中尋覓適當的空閑塊。能夠需求分割內存塊。能夠需求從荒野塊中分割更多的塊。管理和接合空閑空間當回收一個塊時，能夠可以把這個塊和相鄰的塊接合起來，構成更大的塊。有些管理方法，比如說Lea中，不一定需求進展接合。(小于512的)支持相鄰塊接合的數據構造需求如下兩點邊境標志：在每一塊存儲塊的兩端，分別設置一個free/used位(兼當邊境)；相鄰的位置上存放字節總數。雙重鏈接的、嵌入式的空閑塊列表：列表的指針存放在空閑塊中、用雙向指針的方式記錄了有哪些空閑塊。例子相鄰的存儲塊A、B、C當回收B時