第08章 程序運(yùn)行時(shí)的存儲(chǔ)組織及管理

1、1S.PO.P語義分析、生成中間代碼語義分析、生成中間代碼生成目標(biāo)程序生成目標(biāo)程序代碼優(yōu)化代碼優(yōu)化語法分析程序語法分析程序詞法分析程序詞法分析程序錯(cuò)錯(cuò)誤誤處處理理符符號(hào)號(hào)表表管管理理編譯程序在編譯階段要為源程序中出現(xiàn)的變量、常量等組編譯程序在編譯階段要為源程序中出現(xiàn)的變量、常量等組織好在織好在運(yùn)行階段的存儲(chǔ)空間運(yùn)行階段的存儲(chǔ)空間將這種組織形式通過生成的將這種組織形式通過生成的目標(biāo)代碼目標(biāo)代碼體現(xiàn)出來體現(xiàn)出來為運(yùn)行階段實(shí)現(xiàn)存儲(chǔ)為運(yùn)行階段實(shí)現(xiàn)存儲(chǔ)奠定基礎(chǔ)奠定基礎(chǔ)2教學(xué)目標(biāo)教學(xué)目標(biāo)1.1.要求明確靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配的要求明確靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配的含義含義2.2.了解棧式動(dòng)態(tài)存儲(chǔ)分配和活

2、動(dòng)記錄的含義了解棧式動(dòng)態(tài)存儲(chǔ)分配和活動(dòng)記錄的含義及組成及組成3.3.了解堆式動(dòng)態(tài)存儲(chǔ)分配的分配方式和管理了解堆式動(dòng)態(tài)存儲(chǔ)分配的分配方式和管理技術(shù)技術(shù)38.1 8.1 程序運(yùn)行時(shí)的存儲(chǔ)組織程序運(yùn)行時(shí)的存儲(chǔ)組織8.2 8.2 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配8.3 8.3 棧式動(dòng)態(tài)存儲(chǔ)分配棧式動(dòng)態(tài)存儲(chǔ)分配8.4 8.4 堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配教學(xué)內(nèi)容教學(xué)內(nèi)容4運(yùn)行時(shí)存儲(chǔ)空間的劃分運(yùn)行時(shí)存儲(chǔ)空間的劃分代碼空間代碼空間數(shù)據(jù)空間數(shù)據(jù)空間目標(biāo)代碼區(qū)目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū)運(yùn)行棧區(qū)運(yùn)行棧區(qū) 運(yùn)行堆區(qū)運(yùn)行堆區(qū)56 臨時(shí)變量臨時(shí)變量 內(nèi)情向量內(nèi)情向量 形式單元形式單元 動(dòng)態(tài)鏈動(dòng)態(tài)鏈 返回地址返回地址 靜

3、態(tài)鏈靜態(tài)鏈 局部變量局部變量 連接連接數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 局部局部數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) SP TOP781) 1) 隱式參數(shù)隱式參數(shù)主要用于和主調(diào)模塊的通訊，在主要用于和主調(diào)模塊的通訊，在一般情況下這個(gè)參數(shù)可以是主調(diào)過程的返回一般情況下這個(gè)參數(shù)可以是主調(diào)過程的返回地址，或在不能利用寄存器返回函數(shù)值時(shí)傳地址，或在不能利用寄存器返回函數(shù)值時(shí)傳回函數(shù)返回值。這些信息不會(huì)在程序中明顯回函數(shù)返回值。這些信息不會(huì)在程序中明顯地出現(xiàn)，所以稱為隱式參數(shù)。地出現(xiàn)，所以稱為隱式參數(shù)。2) 2) 形式參數(shù)形式參數(shù)部分存放相應(yīng)實(shí)在參數(shù)的地址或部分存放相應(yīng)實(shí)在參數(shù)的地址或值。值。3) 3) 程序變量部分程序變量部分將作為簡單變量、數(shù)

4、組、記將作為簡單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的臨時(shí)變量的存儲(chǔ)空錄以及編譯程序所產(chǎn)生的臨時(shí)變量的存儲(chǔ)空間。間。91011下面我們通過一段下面我們通過一段C C程序的運(yùn)行來說明運(yùn)行棧的變化情況。設(shè)有程序的運(yùn)行來說明運(yùn)行棧的變化情況。設(shè)有C C程序如下：程序如下：real x; 塊塊1int m1(int ind) 塊塊2 int x; x=m2(ind+1);int m2(int j) 塊塊3 int f10; 塊塊4 bool test1; main()塊塊5 int x; x=2; printf(%dn,m1(x/5); (a) (b) (c) (d) (e)121 1、 參數(shù)區(qū)參數(shù)區(qū)

5、參數(shù)區(qū)保存的內(nèi)容包括：1) 隱式參數(shù)隱式參數(shù)：隱式參數(shù)常包含下列幾項(xiàng)： 返回地址：主調(diào)程序中調(diào)用語句的下一條可執(zhí)行語句的地址。 指向前一個(gè)活動(dòng)記錄起始位置的指針：該基地址指針存放該模塊的主調(diào)模塊的活動(dòng)記錄的基地址，用于確?？刂品祷刂髡{(diào)過程時(shí)，能使運(yùn)行環(huán)境恢復(fù)到調(diào)用前的格局。 函數(shù)返回值：有的隱式參數(shù)區(qū)包含此項(xiàng)，有的不包括，還有更好的處理返回值的方法 。2) 顯式參數(shù)顯式參數(shù)：顯式參數(shù)區(qū)是形式參數(shù)的通訊區(qū)。 形式參數(shù)的傳遞有傳值、傳地址、傳名等方法。有些語言如PASCAL語言即可傳值、也可傳地址。C語言采用的是傳值的方式，這種參數(shù)傳遞方法，實(shí)在參數(shù)的值將賦給形式參數(shù)。當(dāng)程序運(yùn)行進(jìn)入一個(gè)程序塊時(shí)，

6、就要在運(yùn)行棧中為當(dāng)程序運(yùn)行進(jìn)入一個(gè)程序塊時(shí)，就要在運(yùn)行棧中為此程序塊添加一個(gè)活動(dòng)記錄?；顒?dòng)記錄中除了存儲(chǔ)此程序塊添加一個(gè)活動(dòng)記錄?；顒?dòng)記錄中除了存儲(chǔ)局部變量外，還包括一個(gè)參數(shù)區(qū)和一個(gè)局部變量外，還包括一個(gè)參數(shù)區(qū)和一個(gè)displaydisplay區(qū)。區(qū)。圖圖8.38.3表示了一個(gè)典型的活動(dòng)記錄的概貌。表示了一個(gè)典型的活動(dòng)記錄的概貌。 13210例如，令過程例如，令過程R R的外層為的外層為Q Q，Q Q的外層為的外層為P P，則過程，則過程R R運(yùn)行運(yùn)行時(shí)時(shí)displaydisplay表的內(nèi)容應(yīng)為：表的內(nèi)容應(yīng)為：14圖圖8.48.4給出了圖給出了圖8.2(e)8.2(e)的運(yùn)行的運(yùn)行棧中各活動(dòng)記

7、錄的內(nèi)容。棧中各活動(dòng)記錄的內(nèi)容。塊塊4 4的活動(dòng)記錄如下：的活動(dòng)記錄如下：DISPLAYDISPLAY區(qū)：區(qū)：指針指針d1d1和和d2d2，分分別指向全局變量區(qū)的地址別指向全局變量區(qū)的地址Abp0Abp0和和Abp3Abp3。隱式參數(shù)區(qū)：隱式參數(shù)區(qū)：有兩個(gè)參數(shù)，第有兩個(gè)參數(shù)，第一個(gè)是返回地址，因塊一個(gè)是返回地址，因塊4 4不是不是一個(gè)獨(dú)立的函數(shù)，是一嵌套的一個(gè)獨(dú)立的函數(shù)，是一嵌套的塊程序，所以，沒有返回地址，塊程序，所以，沒有返回地址，同樣也沒有形參，第同樣也沒有形參，第2 2個(gè)參數(shù)個(gè)參數(shù)Abp3Abp3表示在運(yùn)行棧中，前一個(gè)表示在運(yùn)行棧中，前一個(gè)活動(dòng)記錄是開始地址為活動(dòng)記錄是開始地址為Abp

8、3Abp3的的m2m2活動(dòng)記錄。活動(dòng)記錄。局部數(shù)據(jù)區(qū)：局部數(shù)據(jù)區(qū)：f f和和testtest。 塊塊4活動(dòng)記錄活動(dòng)記錄abp4abp4 m2活動(dòng)記錄活動(dòng)記錄abp3 m1活動(dòng)記錄活動(dòng)記錄abp2 main活動(dòng)記錄活動(dòng)記錄abp1abp015intint fact() fact() staticstatic intint i=5; i=5; if(i=0) return 1; if(i=0) return 1; else else i-; i-; return( return( (i+1)(i+1)* *fact()fact() ); ); /第第6 6行行 main()main() print

9、f(factorprintf(factor of 5!=%dn,fact(); of 5!=%dn,fact(); 161718(a)程序運(yùn)行初期：程序運(yùn)行初期： (b)運(yùn)行一段時(shí)間后：運(yùn)行一段時(shí)間后：當(dāng)有新請(qǐng)求分配內(nèi)存時(shí)，有兩種當(dāng)有新請(qǐng)求分配內(nèi)存時(shí)，有兩種策略分配策略分配空間：空間：1) 系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進(jìn)行(即剩余的空閑塊即剩余的空閑塊不能滿足分配的請(qǐng)求不能滿足分配的請(qǐng)求)時(shí)，系統(tǒng)才去回收所有用戶不再使用的空時(shí)，系統(tǒng)才去回收所有用戶不再使用的空閑塊。閑塊。2) 用戶使用一旦結(jié)束，便將所占內(nèi)存區(qū)釋放成空閑塊。同時(shí)，用戶使用一旦結(jié)束，便將所占內(nèi)存區(qū)釋放成空閑塊。同時(shí)，每當(dāng)新的用戶請(qǐng)求分配內(nèi)存時(shí)，系統(tǒng)需要巡視整個(gè)內(nèi)存中所有每當(dāng)新的用戶請(qǐng)求分配內(nèi)存時(shí)，系統(tǒng)需要巡視整個(gè)內(nèi)存中所有空閑塊，并從中找出一個(gè)空閑塊，并從中找出一個(gè)“合適合適”的空閑塊加以