1、1第第8章章 運行時的運行時的存儲管理存儲管理2開設本章的目的開設本章的目的n一個用高級語言編寫的程序要投入運行，一個用高級語言編寫的程序要投入運行， 一組可運行的代一組可運行的代碼，這組代碼應與高碼，這組代碼應與高級語言的程序等價；級語言的程序等價；程序語言的編譯系統程序語言的編譯系統涉及涉及 一個運行環境，一個運行環境，對程序中的變量做存對程序中的變量做存儲分配，提供各種運儲分配，提供各種運行信息。行信息。 變量以及變量的變量以及變量的存儲分配和存儲管理存儲分配和存儲管理的問題。的問題。涉及涉及3 8.1 存儲組織存儲組織4運行時內存的劃分運行時內存的劃分v編譯程序從操作系統中得到一塊存儲

2、區以編譯程序從操作系統中得到一塊存儲區以使目標程序在其上運行，該存儲區需容納使目標程序在其上運行，該存儲區需容納1. 生成的目標生成的目標代碼空間代碼空間；2. 目標代碼運行時的目標代碼運行時的數據空間數據空間。5代碼空間代碼空間 這是經翻譯后的目標代碼的存儲區域，這是經翻譯后的目標代碼的存儲區域，線性存放著目標指令序列。這是線性存放著目標指令序列。這是固定長度固定長度的，即在編譯時能確定的。的，即在編譯時能確定的。6數據空間數據空間 每個程序都定義一定數量的各種類型每個程序都定義一定數量的各種類型的變量和常量，必須為之分配相應的存儲的變量和常量，必須為之分配相應的存儲空間。空間。l 用戶定義

3、的各種類型的數據對象；用戶定義的各種類型的數據對象；l 保留中間結果和傳遞參數的臨時工作單元；保留中間結果和傳遞參數的臨時工作單元；l 調用過程時所需的連接單元；調用過程時所需的連接單元；l 組織輸入、輸出所需的緩沖區。組織輸入、輸出所需的緩沖區。7 有些數據對象所有些數據對象所占用的空間，在編譯占用的空間，在編譯時能確定，其地址可時能確定，其地址可以編譯進目標代碼；以編譯進目標代碼；有些數據對象具有可有些數據對象具有可變體積和待編譯性質，變體積和待編譯性質，無法再編譯時確定存無法再編譯時確定存儲空間的位置。儲空間的位置。靜態存儲分配靜態存儲分配動態存儲分配動態存儲分配8 對數據空間來說，對數

4、據空間來說，程序實體的屬程序實體的屬性性(變量類型決定存儲長度，作用域決變量類型決定存儲長度，作用域決定了變量在存儲區的空間范圍等定了變量在存儲區的空間范圍等)和和語語言的運行特性言的運行特性都決定了數據空間的分配都決定了數據空間的分配和管理應采用的方法和策略。和管理應采用的方法和策略。數據空間的分配數據空間的分配名字名字 存儲位置存儲位置 值值9 靜態數據區靜態數據區用以用以存放編譯時能確定所占存放編譯時能確定所占用空間的數據。用空間的數據。 堆棧區堆棧區用于存放用于存放可變數據以及管理過程可變數據以及管理過程活動的控制信息。活動的控制信息。代代代代碼碼碼碼段段段段靜靜靜靜態態態態數數數數據

5、據據據段段段段運運運運行行行行棧棧棧棧 堆堆堆堆10 v靜態存儲分配靜態存儲分配v動態存儲分配動態存儲分配 1. 棧式動態存儲分配棧式動態存儲分配 2. 堆式動態存儲分配堆式動態存儲分配11過程活動記錄過程活動記錄(AR)(AR) 源程序由一組過程按某種規則組成。源程序由一組過程按某種規則組成。過程的一次執行稱作一次活動。一個過程過程的一次執行稱作一次活動。一個過程的一次執行所需要的信息使用一個連續的的一次執行所需要的信息使用一個連續的存儲區來管理，這個區叫做一個活動記錄。存儲區來管理，這個區叫做一個活動記錄。12 臨時值，如計算表達式時的中間工作單元。臨時值，如計算表達式時的中間工作單元。

6、局部變量局部變量 （數據）（數據） 保存運行過程前的狀態保存運行過程前的狀態 存取鏈存取鏈（可選可選） 對于非局部量的引用。對于非局部量的引用。 控制鏈控制鏈（可選可選） 指向調用者的活動記錄，釋放棧。指向調用者的活動記錄，釋放棧。 實參實參 （形式單元）（形式單元）返回值返回值 （對函數）（對函數）（有時可使用寄存器存放返回值）（有時可使用寄存器存放返回值）13 8.2 靜態靜態存儲分配存儲分配14靜態存儲分配靜態存儲分配v對于某些變量，在編譯時刻就可以由編譯對于某些變量，在編譯時刻就可以由編譯程序為它們分配存儲區。在運行時刻，這程序為它們分配存儲區。在運行時刻，這些變量和存儲區的結合（些變

7、量和存儲區的結合（綁定綁定）不變。）不變。v局部名字的值在過程活動停止后仍保留下局部名字的值在過程活動停止后仍保留下來。來。 v不能不能處理的情況：處理的情況：在編譯時刻不能確定大小的變量。在編譯時刻不能確定大小的變量。要支持遞歸過程實現。要支持遞歸過程實現。動態建立的數據結構。動態建立的數據結構。15動態存儲分配動態存儲分配v凡不滿足靜態分配條件的語言，自然歸入凡不滿足靜態分配條件的語言，自然歸入了動態分配類。了動態分配類。v如果一個程序語言允許遞歸過程、可變數如果一個程序語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間，那么組或允許用戶自由申請和釋放空間，那么就采用動態存儲分配管理技

8、術。就采用動態存儲分配管理技術。v有兩種動態存儲分配方式：有兩種動態存儲分配方式： 1. 棧式棧式(stack)動態存儲分配動態存儲分配 2. 堆式堆式(heap)動態存儲分配動態存儲分配16 8.3 棧式棧式存儲分配存儲分配17v基于控制棧的原理：基于控制棧的原理： 存儲空間被組織成棧，存儲空間被組織成棧，活動記錄的推入和彈出分別對應于活動的活動記錄的推入和彈出分別對應于活動的開始和結束。開始和結束。v 與靜態分配不同的是，在每次活動中把局與靜態分配不同的是，在每次活動中把局部名字和新的存儲單元綁定，在活動結束部名字和新的存儲單元綁定，在活動結束時，活動記錄從棧中彈出，因而局部名字時，活動記

9、錄從棧中彈出，因而局部名字的存儲空間也隨之消失。的存儲空間也隨之消失。 18簡單的棧式存儲分配簡單的棧式存儲分配v程序結構特點程序結構特點：沒有分程序結構，過程定沒有分程序結構，過程定義不嵌套，過程可遞歸調用，含可變數組；義不嵌套，過程可遞歸調用，含可變數組； v采用棧式動態分配策略，運行時，每當進采用棧式動態分配策略，運行時，每當進入一個過程，則為該過程分配一段存儲區，入一個過程，則為該過程分配一段存儲區，當一個過程工作完畢返回時，它所占用的當一個過程工作完畢返回時，它所占用的存儲區則可釋放。存儲區則可釋放。19 main 全局變量的說明或數組的說明；全局變量的說明或數組的說明； proc

10、R end R; proc Q end Q; 主程序執行語句主程序執行語句 end mainMain-Q-TOP- R 的活動記錄的活動記錄 SP-的活動記錄的活動記錄主程序全局主程序全局數據區數據區RQSP指向現行過程活動記錄的起點指向現行過程活動記錄的起點TOP始終指向已占用的棧頂單元始終指向已占用的棧頂單元20 嵌套過程語言的棧式分配嵌套過程語言的棧式分配v（語言）一個過程可以引用包圍它的任（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，一外層過程所定義的標識符（如變量，數組或過程等）。數組或過程等）。v（實現）一個過程可以引用它的任一外（實現）一個過程可以引用它的任

11、一外層過程的最新活動記錄中的某些數據。層過程的最新活動記錄中的某些數據。21帶有嵌套過程的一個帶有嵌套過程的一個Pascal程序程序 sort readarray exchange quicksort partition22 v關鍵技術：解決對非局部量的引用（存關鍵技術：解決對非局部量的引用（存取）。取）。v設法跟蹤每個外層過程的最新活動記錄設法跟蹤每個外層過程的最新活動記錄AR的位置。的位置。v跟蹤辦法：跟蹤辦法： 1. 用存取鏈。用存取鏈。 2. 用用DISPLAY表。表。23存取鏈存取鏈 棧中的活動記錄應反映源程序中過程棧中的活動記錄應反映源程序中過程之間的嵌套關系。之間的嵌套關系。 為

12、每一個活動記錄增設一個稱為存取為每一個活動記錄增設一個稱為存取鏈的指針，如果在源程序中過程鏈的指針，如果在源程序中過程p直接嵌入直接嵌入在過程在過程q中，那么中，那么p的一個活動記錄中的存的一個活動記錄中的存取鏈指向取鏈指向q的最近的活動記錄中的存取鏈。的最近的活動記錄中的存取鏈。從當前活動記錄開始，沿著這條鏈，能找從當前活動記錄開始，沿著這條鏈，能找到訪問的非局部名字。到訪問的非局部名字。 程序運行過程中應維持這條鏈。程序運行過程中應維持這條鏈。24嵌套層次顯示表嵌套層次顯示表displayv“嵌套層次嵌套層次”是指過程定義的層數。主程是指過程定義的層數。主程序的層數為序的層數為0。向外逐層加。向外逐層加1。v每進入一個過程后，在建立它的活動記錄每進入一個過程后，在建立它的活動記錄的同時建立一張的同時建立一張display表。表。v當前激活過程的層次為當前激活過程的層次為K，它的，它的Display表表含有含有K+1個單元，個單元，自頂向下自頂向下依次存放著現依次存放著現行層，直接外層行層，直接外層直至最外層的每一過程直至最外層的每一過程的最新活動記錄的地址。的最新活動記錄的地址。25 8.4 堆式堆式存儲分配存儲分配26堆式存儲分配堆式存儲分配v堆式分配的適合范圍：堆式分配的適合范