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

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

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

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

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

5、變量分配存儲單元。在目的程序運(yùn)轉(zhuǎn)時進(jìn)展分配 編譯時為運(yùn)轉(zhuǎn)階段設(shè)計(jì)好存儲組織方式，即為每個數(shù)據(jù)項(xiàng)安排好它在數(shù)據(jù)區(qū)中的相對位置108.3 棧式動態(tài)存儲分配 棧式分配適用于允許遞歸調(diào)用的程序設(shè)計(jì)言語;引入一運(yùn)轉(zhuǎn)棧,每調(diào)用一次過程,就把該過程的相應(yīng)調(diào)用記錄壓入棧,過程執(zhí)行終了后再將其彈出棧;進(jìn)入時：在棧頂為其分配一個數(shù)據(jù)區(qū)退出時：吊銷過程數(shù)據(jù)區(qū)動作： 1)懇求 2)釋放 3)嵌套調(diào)用11下面我們經(jīng)過一段C程序的運(yùn)轉(zhuǎn)來闡明運(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)用語句的下一條可執(zhí)行語句的地址。 指向前一個活動記錄起始位置的指針：該基地址指針存放該模塊的主調(diào)模塊的活動記錄的基地址，用于確保控制前往主調(diào)過程時，能使運(yùn)轉(zhuǎn)環(huán)境恢復(fù)到調(diào)

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

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

9、同樣也沒有形參，第2個參數(shù)Abp3表示在運(yùn)轉(zhuǎn)棧中，前一個活動記錄是開場地址為Abp3的m2活動記錄。部分?jǐn)?shù)據(jù)區(qū)：f和test。 abp2os無前記錄 xd1abp0 x d1return2abp1indxd1return3jd1d2abp3ftest 塊4活動記錄abp4 m2活動記錄abp3 m1活動記錄abp2 main活動記錄abp1abp015遞歸過程的處置 下面程序的運(yùn)轉(zhuǎn)結(jié)果是什么？假設(shè)把第6行的(i+1)*fact( )改成fact( )*(i+1)的話，那么程序的運(yùn)轉(zhuǎn)結(jié)果是有什么變化？試分析為什么會有這兩種不同的結(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 堆式動態(tài)存儲分配 當(dāng)程序文語允許在運(yùn)轉(zhuǎn)時為變量動態(tài)懇求和釋放存儲空間，采用堆式分配是最有效的處理方案。堆式分配的根本思想是，為正運(yùn)轉(zhuǎn)的程序劃出適當(dāng)大的空間(稱為堆Heap)，每當(dāng)需求時可從堆的空閑區(qū)中分得一塊，用完之后再退還給堆。如C言語中的malloc和free函數(shù)。如C+言語中的new和delete函數(shù)。178.4.1 堆分配方式 當(dāng)運(yùn)轉(zhuǎn)程序懇求一塊體積為N的空間時，應(yīng)該如何分配呢？常采用的方法如下

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

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

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

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