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

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

2、和活動(dòng)記錄的含義了解棧式動(dòng)態(tài)存儲(chǔ)分配和活動(dòng)記錄的含義及組成及組成 了解堆式動(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ū)5p目標(biāo)代碼的長(zhǎng)度在編譯時(shí)就可確定目標(biāo)代碼的長(zhǎng)度在編譯時(shí)就可確定,可放在可放在內(nèi)內(nèi);p對(duì)于在編譯

3、時(shí)已知大小的數(shù)據(jù)對(duì)象對(duì)于在編譯時(shí)已知大小的數(shù)據(jù)對(duì)象(如如等等等等), 也可放在也可放在內(nèi)內(nèi);p為提高運(yùn)行效率為提高運(yùn)行效率,應(yīng)盡可能多地分配應(yīng)盡可能多地分配。的分配一般可全部放在的分配一般可全部放在內(nèi)內(nèi).p像像這類語(yǔ)言的實(shí)現(xiàn)這類語(yǔ)言的實(shí)現(xiàn),由于子程序允許由于子程序允許地調(diào)用地調(diào)用,因此應(yīng)用一因此應(yīng)用一來(lái)動(dòng)態(tài)地管理內(nèi)存分配來(lái)動(dòng)態(tài)地管理內(nèi)存分配.p另外另外和和 還允許還允許的內(nèi)存的內(nèi)存,這種數(shù)這種數(shù)據(jù)的空間可由據(jù)的空間可由實(shí)現(xiàn)實(shí)現(xiàn).6 臨時(shí)變量臨時(shí)變量 內(nèi)情向量?jī)?nèi)情向量 形式單元形式單元 動(dòng)態(tài)鏈動(dòng)態(tài)鏈 返回地址返回地址 靜態(tài)鏈靜態(tài)鏈 局部變量局部變量 連接連接數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 局部局部數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) S

4、P TOP7p若在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)若在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)體的存儲(chǔ)空間大小，則可以采用較簡(jiǎn)單的體的存儲(chǔ)空間大小，則可以采用較簡(jiǎn)單的p采用靜態(tài)存儲(chǔ)分配的語(yǔ)言必須滿足下列條件：采用靜態(tài)存儲(chǔ)分配的語(yǔ)言必須滿足下列條件：1 1） 不允許過(guò)程有遞歸調(diào)用。不允許過(guò)程有遞歸調(diào)用。2 2） 不允許有可變大小的數(shù)據(jù)項(xiàng)，如可變數(shù)組或可不允許有可變大小的數(shù)據(jù)項(xiàng)，如可變數(shù)組或可變字符串。變字符串。3 3） 不允許用戶動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。不允許用戶動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。滿足上述條件的語(yǔ)言有滿足上述條件的語(yǔ)言有FORTRANFORTRAN、BASICBASIC等。等。81) 1) 隱式參數(shù)隱式參

5、數(shù)主要用于和主調(diào)模塊的通訊，在主要用于和主調(diào)模塊的通訊，在一般情況下這個(gè)參數(shù)可以是主調(diào)過(guò)程的返回一般情況下這個(gè)參數(shù)可以是主調(diào)過(guò)程的返回地址，或在不能利用寄存器返回函數(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) 程序變量部分程序變量部分將作為簡(jiǎn)單變量、數(shù)組、記將作為簡(jiǎn)單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的臨時(shí)變量的存儲(chǔ)空錄以及編譯程序所產(chǎn)生的臨時(shí)變量的存儲(chǔ)空間。間。9

6、在在編譯階段編譯階段由由編譯程序編譯程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的管理，為源實(shí)現(xiàn)對(duì)存儲(chǔ)空間的管理，為源程序中的變量分配存儲(chǔ)單元。程序中的變量分配存儲(chǔ)單元。在編譯時(shí)能夠確定變量在運(yùn)行時(shí)的數(shù)據(jù)空間大小在編譯時(shí)能夠確定變量在運(yùn)行時(shí)的數(shù)據(jù)空間大小運(yùn)行時(shí)不改變運(yùn)行時(shí)不改變?cè)谀繕?biāo)程序在目標(biāo)程序運(yùn)行階段運(yùn)行階段由由目標(biāo)程序目標(biāo)程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的組實(shí)現(xiàn)對(duì)存儲(chǔ)空間的組織與管理，為源程序中的變量分配存儲(chǔ)單元。織與管理，為源程序中的變量分配存儲(chǔ)單元。在目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配在目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配 編譯時(shí)為運(yùn)行階段設(shè)計(jì)好存儲(chǔ)組織形式，即為每編譯時(shí)為運(yùn)行階段設(shè)計(jì)好存儲(chǔ)組織形式，即為每個(gè)數(shù)據(jù)項(xiàng)安排好它在數(shù)據(jù)區(qū)中的相對(duì)位置個(gè)數(shù)據(jù)

7、項(xiàng)安排好它在數(shù)據(jù)區(qū)中的相對(duì)位置1011下面我們通過(guò)一段下面我們通過(guò)一段C C程序的運(yùn)行來(lái)說(shuō)明運(yùn)行棧的變化情況。設(shè)有程序的運(yùn)行來(lái)說(shuō)明運(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ū) 參數(shù)區(qū)保存的內(nèi)容包括：1) 隱式參數(shù)隱式參數(shù)：隱式參數(shù)常包含下列幾項(xiàng)： 返回地址：主調(diào)

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

9、活動(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)記錄的概貌。 132 2、DisplayDisplay（嵌套層次顯示表）區(qū)（嵌套層次顯示表）區(qū)displaydisplay區(qū)用于保存對(duì)當(dāng)前正在執(zhí)行的模區(qū)用于保存對(duì)當(dāng)前正在執(zhí)行的模塊來(lái)說(shuō)是全局的程序變量區(qū)的信息，它由塊來(lái)說(shuō)是全局的程序變量區(qū)的信息，它由一系列地址指針?biāo)M成，每一個(gè)指針指向一系列地址指針?biāo)M成，每一個(gè)指針指向一個(gè)程序塊的活動(dòng)記錄的開(kāi)始位置，而這一個(gè)程序

10、塊的活動(dòng)記錄的開(kāi)始位置，而這個(gè)程序塊對(duì)于當(dāng)前正在執(zhí)行的程序塊來(lái)說(shuō)個(gè)程序塊對(duì)于當(dāng)前正在執(zhí)行的程序塊來(lái)說(shuō)是全局的。是全局的。210例如，令過(guò)程例如，令過(guò)程R R的外層為的外層為Q Q，Q Q的外層為的外層為P P，則過(guò)程，則過(guò)程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)記錄的內(nèi)容。棧中各活動(dòng)記錄的內(nèi)容。塊塊4 4的活動(dòng)記錄如下：的活動(dòng)記錄如下：DISPLAYDISPLAY區(qū)：區(qū)：指針指針d1d1和和d2d2，分，分別指向全局變量區(qū)的地址別指向全局變量區(qū)的地址Abp0Abp0和和Abp3

11、Abp3。隱式參數(shù)區(qū)：隱式參數(shù)區(qū)：有兩個(gè)參數(shù)，第有兩個(gè)參數(shù)，第一個(gè)是返回地址，因塊一個(gè)是返回地址，因塊4 4不是不是一個(gè)獨(dú)立的函數(shù)，是一嵌套的一個(gè)獨(dú)立的函數(shù)，是一嵌套的塊程序，所以，沒(méi)有返回地址，塊程序，所以，沒(méi)有返回地址，同樣也沒(méi)有形參，第同樣也沒(méi)有形參，第2 2個(gè)參數(shù)個(gè)參數(shù)Abp3Abp3表示在運(yùn)行棧中，前一個(gè)表示在運(yùn)行棧中，前一個(gè)活動(dòng)記錄是開(kāi)始地址為活動(dòng)記錄是開(kāi)始地址為Abp3Abp3的的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)

12、記錄abp1abp015下面程序的運(yùn)行結(jié)果是什么？如果把第下面程序的運(yùn)行結(jié)果是什么？如果把第6行的行的(i+1)*fact( )改成改成fact( )*(i+1)的話，則程序的運(yùn)行結(jié)果的話，則程序的運(yùn)行結(jié)果是有什么變化？試分析為什么會(huì)有這兩種不同的結(jié)果。是有什么變化？試分析為什么會(huì)有這兩種不同的結(jié)果。int fact()int fact() staticstatic int i=5; int i=5; if(i=0) return 1; if(i=0) return 1; else else i-; i-; return( return( (i+1)(i+1)* *fact()fact() )

13、; ); /第第6 6行行 main()main() printf(factor of 5!=%dn,fact(); printf(factor of 5!=%dn,fact(); 16p當(dāng)程序語(yǔ)言允許在運(yùn)行時(shí)為變量當(dāng)程序語(yǔ)言允許在運(yùn)行時(shí)為變量，采用，采用是最有效的解決方案。是最有效的解決方案。，為正運(yùn)行的程序劃出適，為正運(yùn)行的程序劃出適當(dāng)大的空間當(dāng)大的空間( (稱為稱為) )，每當(dāng)需要時(shí)可從堆的，每當(dāng)需要時(shí)可從堆的中分得一塊，用完之后再退還給堆。中分得一塊，用完之后再退還給堆。p如如C C語(yǔ)言中的語(yǔ)言中的mallocmalloc和和freefree函數(shù)。函數(shù)。p如如C+C+語(yǔ)言中的語(yǔ)言中的n

14、ewnew和和deletedelete函數(shù)。函數(shù)。1718(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í)，有兩種策略分配策略分配空間：空間： 系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)行分配，而不查看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無(wú)法進(jìn)行用戶的內(nèi)存區(qū)是否已空閑，直到分配無(wú)法進(jìn)行(即剩余的空閑塊即剩余的空閑塊不能滿足分配的請(qǐng)求不能滿足分配的請(qǐng)求)時(shí)，系統(tǒng)才去回收所有用戶不再使用的空時(shí)，系統(tǒng)才去回收所有用戶不再使用的空閑塊。閑塊。1) 用戶使用一旦結(jié)束，便將所占內(nèi)存區(qū)釋放成空

15、閑塊。同時(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è)“合適合適”的空閑塊加以分配。的空閑塊加以分配。190 10000 20000 30000(a)內(nèi)存狀態(tài) (b)可利用空間目錄 10000HEAD 10000 20000 30000(c)可利用空間鏈表圖8.7堆式存儲(chǔ)管理的可利用空間表 20200000300000#010000HEAD 10000 20000 30000212223p最優(yōu)滿足法：最優(yōu)滿足法：產(chǎn)生內(nèi)存碎片，保留了大內(nèi)存塊，產(chǎn)生內(nèi)存碎片，保留了大內(nèi)存塊