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

1、1S.PO.P語(yǔ)義分析、生成中間代碼生成目的程序代碼優(yōu)化語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理編譯程序在編譯階段要為源程序中出現(xiàn)的變量、常量等組織好在運(yùn)轉(zhuǎn)階段的存儲(chǔ)空間將這種組織方式經(jīng)過(guò)生成的目的代碼表達(dá)出來(lái)為運(yùn)轉(zhuǎn)階段實(shí)現(xiàn)存儲(chǔ)奠定根底2第八章 程序運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織及管理 教學(xué)目的要求明確靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配的含義了解棧式動(dòng)態(tài)存儲(chǔ)分配和活動(dòng)記錄的含義及組成了解堆式動(dòng)態(tài)存儲(chǔ)分配的分配方式和管理技術(shù)38.1 程序運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織8.2 靜態(tài)存儲(chǔ)分配8.3 棧式動(dòng)態(tài)存儲(chǔ)分配8.4 堆式動(dòng)態(tài)存儲(chǔ)分配教學(xué)內(nèi)容48.1 程序運(yùn)轉(zhuǎn)時(shí)的存儲(chǔ)組織 運(yùn)轉(zhuǎn)時(shí)存儲(chǔ)空間的劃分代碼空間數(shù)據(jù)空間目的代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)

2、運(yùn)轉(zhuǎn)棧區(qū) 運(yùn)轉(zhuǎn)堆區(qū)5存儲(chǔ)分配戰(zhàn)略目的代碼的長(zhǎng)度在編譯時(shí)就可確定,可放在靜態(tài)區(qū)內(nèi);對(duì)于在編譯時(shí)知大小的數(shù)據(jù)對(duì)象(如常量,全局變量,靜態(tài)變量等等), 也可放在靜態(tài)區(qū)內(nèi);為提高運(yùn)轉(zhuǎn)效率,應(yīng)盡能夠多地分配靜態(tài)數(shù)據(jù)空間。FORTRAN,BASIC的分配普通可全部放在靜態(tài)區(qū)內(nèi).像PASCAL,C這類(lèi)言語(yǔ)的實(shí)現(xiàn),由于子程序允許遞歸地調(diào)用,因此運(yùn)用一數(shù)據(jù)棧來(lái)動(dòng)態(tài)地管理內(nèi)存分配.另外PASCAL和C還允許動(dòng)態(tài)地懇求的內(nèi)存,這種數(shù)據(jù)的空間可由堆式分配實(shí)現(xiàn).6活動(dòng)記錄active record執(zhí)行過(guò)程時(shí)所需進(jìn)展的信息管理，是經(jīng)過(guò)活動(dòng)記錄實(shí)現(xiàn)的，活動(dòng)記錄延續(xù)存儲(chǔ)在塊中，其內(nèi)容見(jiàn)右圖。以過(guò)程為單位的動(dòng)態(tài)存儲(chǔ)分配方案：當(dāng)

3、一過(guò)程被調(diào)用時(shí)，就把其活動(dòng)記錄壓入運(yùn)轉(zhuǎn)時(shí)存儲(chǔ)棧頂，前往時(shí)彈出之。 暫時(shí)變量 內(nèi)情向量 方式單元 動(dòng)態(tài)鏈 前往地址 靜態(tài)鏈 部分變量 銜接數(shù)據(jù)區(qū) 部分?jǐn)?shù)據(jù)區(qū) SP TOP78.2 靜態(tài)存儲(chǔ)分配 假設(shè)在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)體的存儲(chǔ)空間大小，那么可以采用較簡(jiǎn)單的靜態(tài)存儲(chǔ)管理。采用靜態(tài)存儲(chǔ)分配的言語(yǔ)必需滿(mǎn)足以下條件：1 不允許過(guò)程有遞歸調(diào)用。2 不允許有可變大小的數(shù)據(jù)項(xiàng)，如可變數(shù)組或可變字符串。3 不允許用戶(hù)動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。滿(mǎn)足上述條件的言語(yǔ)有FORTRAN、BASIC等。88.2 靜態(tài)存儲(chǔ)分配右以下圖是一個(gè)FORTRAN程序模塊在采用靜態(tài)存儲(chǔ)分配戰(zhàn)略時(shí)的典型數(shù)據(jù)區(qū)格局。隱式參數(shù)前往地

4、址、存放器內(nèi)容等方式參數(shù)簡(jiǎn)單變量數(shù)組暫時(shí)變量1) 隱式參數(shù)主要用于和主調(diào)模塊的通訊，在普通情況下這個(gè)參數(shù)可以是主調(diào)過(guò)程的前往地址，或在不能利用存放器前往函數(shù)值時(shí)傳回函數(shù)前往值。這些信息不會(huì)在程序中明顯地出現(xiàn)，所以稱(chēng)為隱式參數(shù)。2) 方式參數(shù)部分存放相應(yīng)真實(shí)參數(shù)的地址或值。3) 程序變量部分將作為簡(jiǎn)單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的暫時(shí)變量的存儲(chǔ)空間。9靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配在編譯階段由編譯程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的管理，為源程序中的變量分配存儲(chǔ)單元。在編譯時(shí)可以確定變量在運(yùn)轉(zhuǎn)時(shí)的數(shù)據(jù)空間大小運(yùn)轉(zhuǎn)時(shí)不改動(dòng)動(dòng)態(tài)存儲(chǔ)分配在目的程序運(yùn)轉(zhuǎn)階段由目的程序?qū)崿F(xiàn)對(duì)存儲(chǔ)空間的組織與管理，為源程序中的

5、變量分配存儲(chǔ)單元。在目的程序運(yùn)轉(zhuǎn)時(shí)進(jìn)展分配 編譯時(shí)為運(yùn)轉(zhuǎn)階段設(shè)計(jì)好存儲(chǔ)組織方式，即為每個(gè)數(shù)據(jù)項(xiàng)安排好它在數(shù)據(jù)區(qū)中的相對(duì)位置108.3 棧式動(dòng)態(tài)存儲(chǔ)分配 棧式分配適用于允許遞歸調(diào)用的程序設(shè)計(jì)言語(yǔ);引入一運(yùn)轉(zhuǎn)棧,每調(diào)用一次過(guò)程,就把該過(guò)程的相應(yīng)調(diào)用記錄壓入棧,過(guò)程執(zhí)行終了后再將其彈出棧;進(jìn)入時(shí)：在棧頂為其分配一個(gè)數(shù)據(jù)區(qū)退出時(shí)：吊銷(xiāo)過(guò)程數(shù)據(jù)區(qū)動(dòng)作： 1)懇求 2)釋放 3)嵌套調(diào)用11下面我們經(jīng)過(guò)一段C程序的運(yùn)轉(zhuǎn)來(lái)闡明運(yùn)轉(zhuǎn)棧的變化情況。設(shè)有C程序如下：real x; 塊1int m1(int ind) 塊2 int x; x=m2(ind+1);int m2(int j) 塊3 int f10; 塊

6、4 bool test1; main()塊5 int x; x=2; printf(%dn,m1(x/5); 塊4數(shù)據(jù)區(qū) 塊3數(shù)據(jù)區(qū) 塊2數(shù)據(jù)區(qū) 塊5數(shù)據(jù)區(qū) 塊1數(shù)據(jù)區(qū) 塊3數(shù)據(jù)區(qū) 塊2數(shù)據(jù)區(qū) 塊5數(shù)據(jù)區(qū) 塊1數(shù)據(jù)區(qū) 塊2數(shù)據(jù)區(qū) 塊5數(shù)據(jù)區(qū) 塊1數(shù)據(jù)區(qū) 塊5數(shù)據(jù)區(qū) 塊1數(shù)據(jù)區(qū) 塊1數(shù)據(jù)區(qū) (a) (b) (c) (d) (e)121、 參數(shù)區(qū) 參數(shù)區(qū)保管的內(nèi)容包括：1) 隱式參數(shù)：隱式參數(shù)常包含以下幾項(xiàng)： 前往地址：主調(diào)程序中調(diào)用語(yǔ)句的下一條可執(zhí)行語(yǔ)句的地址。 指向前一個(gè)活動(dòng)記錄起始位置的指針：該基地址指針存放該模塊的主調(diào)模塊的活動(dòng)記錄的基地址，用于確?？刂魄巴髡{(diào)過(guò)程時(shí)，能使運(yùn)轉(zhuǎn)環(huán)境恢復(fù)到調(diào)

7、用前的格局。 函數(shù)前往值：有的隱式參數(shù)區(qū)包含此項(xiàng)，有的不包括，還有更好的處置前往值的方法 。2) 顯式參數(shù)：顯式參數(shù)區(qū)是方式參數(shù)的通訊區(qū)。 方式參數(shù)的傳送有傳值、傳地址、傳名等方法。有些言語(yǔ)如PASCAL言語(yǔ)即可傳值、也可傳地址。C言語(yǔ)采用的是傳值的方式，這種參數(shù)傳送方法，真實(shí)參數(shù)的值將賦給方式參數(shù)。當(dāng)程序運(yùn)轉(zhuǎn)進(jìn)入一個(gè)程序塊時(shí)，就要在運(yùn)轉(zhuǎn)棧中為此程序塊添加一個(gè)活動(dòng)記錄?；顒?dòng)記錄中除了存儲(chǔ)部分變量外，還包括一個(gè)參數(shù)區(qū)和一個(gè)display區(qū)。圖8.3表示了一個(gè)典型的活動(dòng)記錄的概貌。 參數(shù)區(qū) 局部數(shù)據(jù) DISPLAY 132、Display嵌套層次顯示表區(qū)display區(qū)用于保管對(duì)當(dāng)前正在執(zhí)行的模塊

8、來(lái)說(shuō)是全局的程序變量區(qū)的信息，它由一系列地址指針?biāo)M成，每一個(gè)指針指向一個(gè)程序塊的活動(dòng)記錄的開(kāi)場(chǎng)位置，而這個(gè)程序塊對(duì)于當(dāng)前正在執(zhí)行的程序塊來(lái)說(shuō)是全局的。參數(shù)區(qū) 局部數(shù)據(jù) DISPLAY P的活動(dòng)紀(jì)錄的地址Q(chēng)的最新活動(dòng)紀(jì)錄的地址R的現(xiàn)行活動(dòng)紀(jì)錄地址210例如，令過(guò)程R的外層為Q，Q的外層為P，那么過(guò)程R運(yùn)轉(zhuǎn)時(shí)display表的內(nèi)容應(yīng)為：14圖8.4給出了圖8.2(e)的運(yùn)轉(zhuǎn)棧中各活動(dòng)記錄的內(nèi)容。塊4的活動(dòng)記錄如下：DISPLAY區(qū)：指針d1和d2，分別指向全局變量區(qū)的地址Abp0和Abp3。隱式參數(shù)區(qū)：有兩個(gè)參數(shù)，第一個(gè)是前往地址，因塊4不是一個(gè)獨(dú)立的函數(shù)，是一嵌套的塊程序，所以，沒(méi)有前往地址，

9、同樣也沒(méi)有形參，第2個(gè)參數(shù)Abp3表示在運(yùn)轉(zhuǎn)棧中，前一個(gè)活動(dòng)記錄是開(kāi)場(chǎng)地址為Abp3的m2活動(dòng)記錄。部分?jǐn)?shù)據(jù)區(qū)：f和test。 abp2os無(wú)前記錄 xd1abp0 x d1return2abp1indxd1return3jd1d2abp3ftest 塊4活動(dòng)記錄abp4 m2活動(dòng)記錄abp3 m1活動(dòng)記錄abp2 main活動(dòng)記錄abp1abp015遞歸過(guò)程的處置 下面程序的運(yùn)轉(zhuǎn)結(jié)果是什么？假設(shè)把第6行的(i+1)*fact( )改成fact( )*(i+1)的話(huà)，那么程序的運(yùn)轉(zhuǎn)結(jié)果是有什么變化？試分析為什么會(huì)有這兩種不同的結(jié)果。int fact() static int i=5; if(i

10、=0) return 1; else i-; return( (i+1)*fact() ); /第6行 main() printf(factor of 5!=%dn,fact(); 168.4 堆式動(dòng)態(tài)存儲(chǔ)分配 當(dāng)程序文語(yǔ)允許在運(yùn)轉(zhuǎn)時(shí)為變量動(dòng)態(tài)懇求和釋放存儲(chǔ)空間，采用堆式分配是最有效的處理方案。堆式分配的根本思想是，為正運(yùn)轉(zhuǎn)的程序劃出適當(dāng)大的空間(稱(chēng)為堆Heap)，每當(dāng)需求時(shí)可從堆的空閑區(qū)中分得一塊，用完之后再退還給堆。如C言語(yǔ)中的malloc和free函數(shù)。如C+言語(yǔ)中的new和delete函數(shù)。178.4.1 堆分配方式 當(dāng)運(yùn)轉(zhuǎn)程序懇求一塊體積為N的空間時(shí)，應(yīng)該如何分配呢？常采用的方法如下

11、：1 先遇到哪個(gè)大于N的空閑塊就從中取出N個(gè)單元進(jìn)展分配。2 假設(shè)在堆中找不到大于N的空閑塊，但一切空閑塊的總和比N大，就需求將空閑塊銜接在一同，從而構(gòu)成大于N的空閑塊。假設(shè)一切空閑塊的總和都小于N，那么需求采用更復(fù)雜的方法。如廢品回收技術(shù)，將那些運(yùn)轉(zhuǎn)程序曾經(jīng)不運(yùn)用但還沒(méi)有釋放的塊、或運(yùn)轉(zhuǎn)程序目前很少運(yùn)用的塊回收，再重新分配。 188.4.2 堆式存儲(chǔ)管理技術(shù) u1u2u3u4u5u6u7u8u1u3u4u7u8(a)程序運(yùn)轉(zhuǎn)初期： (b)運(yùn)轉(zhuǎn)一段時(shí)間后：當(dāng)有新懇求分配內(nèi)存時(shí)，有兩種戰(zhàn)略分配空間： 系統(tǒng)繼續(xù)從高地址的空閑塊中進(jìn)展分配，而不查看已分配給用戶(hù)的內(nèi)存區(qū)能否已空閑，直到分配無(wú)法進(jìn)展(即

12、剩余的空閑塊不能滿(mǎn)足分配的懇求)時(shí)，系統(tǒng)才去回收一切用戶(hù)不再運(yùn)用的空閑塊。 用戶(hù)運(yùn)用一旦終了，便將所占內(nèi)存區(qū)釋放成空閑塊。同時(shí)，每當(dāng)新的用戶(hù)懇求分配內(nèi)存時(shí)，系統(tǒng)需求巡視整個(gè)內(nèi)存中一切空閑塊，并從中找出一個(gè)“適宜的空閑塊加以分配。190 10000 20000 30000(a)內(nèi)存形狀 起始地址內(nèi)存大小 使用情況 100005000空閑200003000空閑300008000空閑(b)可利用空間目錄 050002000003000300000800#10000HEAD 10000 20000 30000(c)可利用空間鏈表圖8.7堆式存儲(chǔ)管理的可利用空間表 201、定長(zhǎng)塊的管理將總的可被利用的堆

13、存儲(chǔ)區(qū)劃分成大小適當(dāng)?shù)囊幌盗袎K。這些塊經(jīng)過(guò)每塊中的LINK域銜接起來(lái)構(gòu)成單向線(xiàn)性鏈表，即可利用空間表，如以下圖所示。200000300000#010000HEAD 10000 20000 30000212、變長(zhǎng)塊的管理變長(zhǎng)塊的管理是常用的堆式存儲(chǔ)管理方法。系統(tǒng)在運(yùn)轉(zhuǎn)期間分配給用戶(hù)的內(nèi)存塊的大小不固定，可以隨懇求而變。因此，“可利用空間表中的結(jié)點(diǎn)，即空閑塊的大小也是隨意的。結(jié)點(diǎn)的數(shù)據(jù)構(gòu)造如下TAG：標(biāo)志，0表示空閑，1表示占用。SIZE：記錄結(jié)點(diǎn)大小，指示空閑塊的存儲(chǔ)量。LINK：指向下一個(gè)結(jié)點(diǎn)。 SPACE：地址延續(xù)的內(nèi)存空間。 TAGSIZELINKSPACE22變長(zhǎng)塊內(nèi)存的分配假設(shè)用戶(hù)懇求

14、一個(gè)大小為n的存儲(chǔ)塊，而“可利用空間表中僅有一塊大小為mn的空閑塊，那么分配時(shí)只需將大小為n的部分分配給懇求的用戶(hù)，同時(shí)將剩余的m-n部分作為一個(gè)結(jié)點(diǎn)留在鏈表中即可。假設(shè)可利用空間表中有假設(shè)干個(gè)大于n的空閑塊時(shí)，可采用以下方法分配： 1、初次滿(mǎn)足法 2、最優(yōu)滿(mǎn)足法 3、最差滿(mǎn)足法238.4.2 堆式存儲(chǔ)管理技術(shù)三種分配方式各有所長(zhǎng)最優(yōu)滿(mǎn)足法：產(chǎn)生內(nèi)存碎片，保管了大內(nèi)存塊，以備呼應(yīng)后面能夠發(fā)生的對(duì)大存儲(chǔ)空間的懇求。最差滿(mǎn)足法：使鏈表中的結(jié)點(diǎn)空間大小趨于均勻，因此，它適用于懇求分配的內(nèi)存大小范圍較窄的系統(tǒng)。初次滿(mǎn)足法：分配隨機(jī)，適用于事先對(duì)系統(tǒng)運(yùn)轉(zhuǎn)期間能夠出現(xiàn)的內(nèi)存分配和釋放情況不能準(zhǔn)確把握的場(chǎng)所。248.4.2 堆式存儲(chǔ)管理技術(shù)從時(shí)間上對(duì)三種分配法進(jìn)展比較查詢(xún)“可