運(yùn)行時(shí)的存儲(chǔ)組織.ppt

第9章 運(yùn)行時(shí)的存儲(chǔ)組織,School of Computer Science & Technology Harbin Institute of Technology,重點(diǎn)：符號(hào)表的內(nèi)容、組織，過程調(diào)用實(shí)現(xiàn)， 靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配的基本方法。 難點(diǎn)：參數(shù)傳遞，過程說明語句代碼結(jié)構(gòu)， 過程調(diào)用語句的代碼結(jié)構(gòu)， 過程調(diào)用語句的語法制導(dǎo)定義， 棧式存儲(chǔ)分配。,2019/7/2,2,第9章 運(yùn)行時(shí)的存儲(chǔ)組織,9.1 與存儲(chǔ)組織有關(guān)的源語言概念與特征 9.2 存儲(chǔ)組織 9.3 靜態(tài)存儲(chǔ)分配 9.4 棧式存儲(chǔ)分配 9.5 棧中非局部數(shù)據(jù)的訪問 9.6 堆管理 9.7 本章小結(jié),2019/7/2,3,9.1 與存儲(chǔ)組織有關(guān)的源語言概念與特征,編譯程序必須準(zhǔn)確地實(shí)現(xiàn)包含在源程序中的各種抽象概念，如名字、作用域、數(shù)據(jù)類型、操作符、過程、參數(shù)和控制流結(jié)構(gòu)等，這些概念反映了源語言所具有的一些特征，對(duì)它們的支持往往會(huì)影響運(yùn)行時(shí)的存儲(chǔ)組織和分配策略 給定一個(gè)源程序，編譯程序必須根據(jù)源語言的特征(規(guī)定)為源程序中的許多問題做出決策，包括何時(shí)、怎樣為名字分配內(nèi)存地址。 靜態(tài)策略：在編譯時(shí)即可做出決定的策略 動(dòng)態(tài)策略：直到程序執(zhí)行時(shí)才能做出決定的策略,2019/7/2,4,9.1.1 名字及其綁定,“名字”、“變量”和“標(biāo)識(shí)符” 的區(qū)別與聯(lián)系 名字和變量分別表示編譯時(shí)的名字和運(yùn)行時(shí)該名字所代表的內(nèi)存位置。 標(biāo)識(shí)符則是一個(gè)字符串，用于指示數(shù)據(jù)對(duì)象、過程、類或?qū)ο蟮娜肟凇?所有標(biāo)識(shí)符都是名字，但并不是所有的名字都是標(biāo)識(shí)符，名字還可以是表達(dá)式。例如，名字x.y可能表示x所代表結(jié)構(gòu)的域y。 同一標(biāo)識(shí)符可以被聲明多次，但每個(gè)聲明都引入一個(gè)新的變量。即使每個(gè)標(biāo)識(shí)符只被聲明一次，局部于某個(gè)遞歸過程的標(biāo)識(shí)符在不同的運(yùn)行時(shí)刻也將指向不同的內(nèi)存位置。,2019/7/2,5,名字的綁定,從名字到值的兩步映射 環(huán)境把名字映射到左值，而狀態(tài)把左值映射到右值 賦值改變狀態(tài)，但不改變環(huán)境。 如果環(huán)境將名字x映射到存儲(chǔ)單元s，我們就說x被綁定到s,名字,內(nèi)存位置 (變量),狀態(tài),值,環(huán)境,2019/7/2,6,9.1.2 聲明的作用域,x的聲明的作用域是程序中的這樣一段區(qū)域，在該區(qū)域中，x的引用均指向x的這一聲明。對(duì)于某種程序設(shè)計(jì)語言，如果只通過考察其程序就可以確定某個(gè)聲明的作用域，則稱該語言使用靜態(tài)作用域；否則稱該語言使用動(dòng)態(tài)作用域。 C+、Java和C#等還提供了對(duì)作用域的顯式控制，其方法是使用public、private和protected這樣的關(guān)鍵字。 聲明的作用域是通過符號(hào)表進(jìn)行管理的，詳見8.4節(jié)的討論。,2019/7/2,7,1. 靜態(tài)作用域,在具有程序塊結(jié)構(gòu)的語言中，變量聲明的靜態(tài)作用域規(guī)則如下 ： 如果名字x的聲明D屬于程序塊B，則D的作用域是B的所有語句，只有滿足如下條件的程序塊B除外：B嵌套在B中(可以是任意的嵌套深度)，且B中具有同一名字x的一個(gè)新的聲明。 令B1, B2, , Bk是包圍x的本次引用的所有程序塊，Bk-1是Bk的直接外層程序塊，Bk-2是Bk-1的直接外層程序塊，如此類推。找到使x的某個(gè)聲明屬于Bi的最大i，則x的本次引用指向Bi中的這個(gè)聲明。換句話說，x的本次引用處在Bi中的這個(gè)聲明的作用域中。,2019/7/2,8,1. 靜態(tài)作用域,表9.1 圖8.10所示程序中聲明的作用域,2019/7/2,9,2. 顯式訪問控制,類和結(jié)構(gòu)為其成員引入了一種新的作用域 如果p是某個(gè)帶有域(成員)x的類的對(duì)象，則p.x中x的引用將指向該類定義中的域x。與程序塊結(jié)構(gòu)類似的是，類D中成員x的聲明的作用域?qū)?huì)擴(kuò)展到D的任何子類D，除非D中具有同一名字x的一個(gè)局部聲明。,2019/7/2,10,2. 顯式訪問控制,通過使用像public、private和protected這樣的關(guān)鍵字，C+或Java類的面向?qū)ο笳Z言提供了一種對(duì)超類中成員名字的顯式訪問控制。這些關(guān)鍵字通過限制訪問來支持封裝。因此，私有名的作用域只包含與該類及其友類相關(guān)聯(lián)的方法聲明和定義，保護(hù)名只對(duì)其子類是可訪問的，而公用名從類的外部也是可以訪問的。,2019/7/2,11,3. 動(dòng)態(tài)作用域,動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間而靜態(tài)作用域規(guī)則相對(duì)于空間 靜態(tài)作用域規(guī)則要求我們找出某個(gè)引用所指向的聲明，條件是該聲明處在包圍該引用的“空間上最近的”單元(程序塊)中。 動(dòng)態(tài)作用域也是要求我們找出某個(gè)引用所指向的聲明，但條件是該聲明處在包圍該引用的“時(shí)間上最近的”單元(過程活動(dòng))中。,2019/7/2,12,3. 動(dòng)態(tài)作用域,“動(dòng)態(tài)作用域”通常是指下面的策略 名字x的引用指向帶有x聲明的最近被調(diào)用的過程中x的這個(gè)聲明。 例如，過程被當(dāng)做參數(shù)進(jìn)行傳遞時(shí),2019/7/2,13,9.1.3 過程及其活動(dòng),將“過程、函數(shù)和方法”統(tǒng)稱為“過程” 過程定義是一個(gè)聲明，它的最簡(jiǎn)單形式是把一個(gè)標(biāo)識(shí)符和一個(gè)語句聯(lián)系起來。該標(biāo)識(shí)符是過程名，而這個(gè)語句是過程體。 當(dāng)過程名出現(xiàn)在可執(zhí)行語句中時(shí)，稱相應(yīng)的過程在該點(diǎn)被調(diào)用。過程調(diào)用就是執(zhí)行被調(diào)用過程的過程體。注意，過程調(diào)用也可以出現(xiàn)在表達(dá)式中。,2019/7/2,14,9.1.3 過程及其活動(dòng),出現(xiàn)在過程定義中的某些標(biāo)識(shí)符具有特殊的意義，稱為該過程的形式參數(shù)，簡(jiǎn)稱為形參。調(diào)用過程時(shí)，表達(dá)式作為實(shí)在參數(shù)(或?qū)崊?傳遞給被調(diào)用的過程，以替換出現(xiàn)在過程體中的對(duì)應(yīng)形式參數(shù)。9.1.4節(jié)將討論實(shí)參和形參的結(jié)合方法。 過程體的每次執(zhí)行叫做該過程的一個(gè)活動(dòng)。過程p的一個(gè)活動(dòng)的生存期是從過程體執(zhí)行的第一步到最后一步，包括執(zhí)行被p調(diào)用的過程的時(shí)間，以及再由這樣的過程調(diào)用其它過程所花的時(shí)間，等等。,2019/7/2,15,9.1.3 過程及其活動(dòng),如果a和b是過程的活動(dòng)，那么它們的生存期或者不交迭，或者嵌套。也就是說，如果在a結(jié)束之前b就開始了，那么b必須在a結(jié)束之前結(jié)束。 如果同一個(gè)過程的一次新的活動(dòng)可以在前一次活動(dòng)結(jié)束前開始，則稱這樣的過程是遞歸的。遞歸過程p也可以間接地調(diào)用自己。 如果某個(gè)過程是遞歸的，則在某一時(shí)刻可能有它的幾個(gè)活動(dòng)同時(shí)活躍，這時(shí)必須合理組織這些同時(shí)活躍著的活動(dòng)的內(nèi)存空間。,2019/7/2,16,9.1.4 參數(shù)傳遞方式,當(dāng)一個(gè)過程調(diào)用另一個(gè)過程時(shí)，它們之間交換信息的方法通常是通過非局部名字和被調(diào)用過程的參數(shù)來實(shí)現(xiàn)的。 傳值 傳地址 傳值結(jié)果 傳名 其主要區(qū)別在于實(shí)參所代表的究竟是左值、右值還是實(shí)參的正文本身,2019/7/2,17,1. 傳值,計(jì)算實(shí)參并將其右值傳遞給被調(diào)用過程 傳值方式可以如下實(shí)現(xiàn)： 被調(diào)用過程為每個(gè)形參開辟一個(gè)稱為形式單元的存儲(chǔ)單元，用于存放相應(yīng)實(shí)參的值。 調(diào)用過程計(jì)算實(shí)參，并把右值放入相應(yīng)的形式單元中。,調(diào)用者,被調(diào)用者直接使用,A,實(shí)際參數(shù)A,形式參數(shù)X,A的值,單向傳值,2019/7/2,18,2. 傳地址,調(diào)用過程將實(shí)參的地址傳遞給被調(diào)用過程 傳地址方式可以如下實(shí)現(xiàn)： 如果實(shí)參是一個(gè)具有左值的名字或表達(dá)式，則傳遞該左值本身 如果實(shí)參是a+b或2這樣的沒有左值的表達(dá)式，則調(diào)用過程首先計(jì)算實(shí)參的值并將其存入一個(gè)新的存儲(chǔ)單元，然后將這個(gè)新單元的地址傳遞給被調(diào)用過程,調(diào)用者,被調(diào)用者間址訪問,A,實(shí)際參數(shù)A,形式參數(shù)X,A的地址,傳地址,2019/7/2,19,3. 傳值結(jié)果,傳值結(jié)果就是將傳值和傳地址這兩種方式結(jié)合起來 傳值結(jié)果方式可以如下實(shí)現(xiàn)： 實(shí)參的右值和左值同時(shí)傳給被調(diào)用過程。 在被調(diào)用過程中，像傳值方式那樣使用實(shí)參的右值。 當(dāng)控制返回調(diào)用過程時(shí)，根據(jù)傳遞來的實(shí)參的左值，將形參當(dāng)前的值復(fù)制到實(shí)參存儲(chǔ)單元。,調(diào)用者,被調(diào)用者,A,實(shí)際參數(shù)A,形式參數(shù)X,A的值,傳值/傳地址,A的地址,2019/7/2,20,4. 傳名,用實(shí)參表達(dá)式對(duì)形參進(jìn)行文字替換。 傳名方式可以如下實(shí)現(xiàn)： 在調(diào)用過程中設(shè)置計(jì)算實(shí)參左值或右值的形實(shí)轉(zhuǎn)換子程序。 被調(diào)用過程為每個(gè)形參開辟一個(gè)存儲(chǔ)單元，用于存放該實(shí)參的形實(shí)轉(zhuǎn)換子程序的入口地址。被調(diào)過程執(zhí)行時(shí)，每當(dāng)要向形參賦值或取該形參的值時(shí)，就調(diào)用相應(yīng)于該形參的形實(shí)轉(zhuǎn)換子程序，以獲得相應(yīng)的實(shí)參地址或值。注意，形實(shí)轉(zhuǎn)換子程序的運(yùn)行環(huán)境是調(diào)用程序。形實(shí)轉(zhuǎn)換子程序又稱為換名子程序thunk。,2019/7/2,21,例,procedure swap(var x, y: integer); var temp: integer; begin 調(diào)用swap(i, ai) temp := x; temp := i; x := y; i := ai; y := temp ai := temp end,2019/7/2,22,子程序 P(X,Y,Z); Y:=Y+1; Z:=Z+X,傳值： 2,傳地址： X=T=5,Y=Z=A=2 A:=A+1=2+1 A:=A+T=3+5 8,傳名 A:=A+1=3 A:=A+A+B=3+3+3 9,主程序 A:=2; B:=3; P(A+B, A, A); print A,臨時(shí)單元: T:A+B=5,2019/7/2,23,編譯程序組織存儲(chǔ)空間時(shí)必須考慮的問題,過程能否遞歸？ 當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要保留？ 過程能否訪問非局部變量？ 過程調(diào)用的參數(shù)傳遞方式？ 過程能否作為參數(shù)被傳遞？ 過程能否作為結(jié)果值傳遞？ 存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配？ 存儲(chǔ)塊是否必須顯式地釋放？,2019/7/2,24,9.2 存儲(chǔ)組織,9.2.1 運(yùn)行時(shí)內(nèi)存的劃分 9.2.2 活動(dòng)記錄 9.2.3 局部數(shù)據(jù)的組織 9.2.4 全局存儲(chǔ)分配策略,2019/7/2,25,9.2.1 運(yùn)行時(shí)內(nèi)存的劃分,目標(biāo)代碼,靜態(tài)數(shù)據(jù),棧,堆,空閑 空間,2019/7/2,26,過程的每個(gè)活動(dòng)所需要的信息用一塊連續(xù)的存儲(chǔ)區(qū)來管理，這塊存儲(chǔ)區(qū)叫做活動(dòng)記錄 假定語言的特點(diǎn)為:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，過程定義允許/不允許嵌套。 采用棧式存儲(chǔ)分配機(jī)制 活動(dòng)記錄：運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過程就有一個(gè)相應(yīng)的活動(dòng)記錄壓入棧頂。活動(dòng)記錄一般含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。,9.2.2 活動(dòng)記錄,2019/7/2,27,對(duì)任何局部變量X的引用可表示為變址訪問: dxSP dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)變量,數(shù)組內(nèi)情向量,簡(jiǎn)單變量,SP 0,1,2,舊SP,TOP,每個(gè)過程的活動(dòng)記錄內(nèi)容 非嵌套語言(如C),2019/7/2,28,連接數(shù)據(jù) 返回地址 動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記錄地址的指針。 靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來訪問非局部數(shù)據(jù)。,靜態(tài)鏈,動(dòng)態(tài)鏈,形式單元,臨時(shí)變量,數(shù)組內(nèi)情向量,局部變量,SP0,1,2,返回地址,TOP,每個(gè)過程的活動(dòng)記錄內(nèi)容 嵌套語言(如Pascal),2019/7/2,29,形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。 局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元(如存放對(duì)表達(dá)式求值的結(jié)果)。,靜態(tài)鏈,動(dòng)態(tài)鏈,形式單元,臨時(shí)變量,數(shù)組內(nèi)情向量,局部變量,SP 0,1,2,返回地址,TOP,每個(gè)過程的活動(dòng)記錄內(nèi)容,2019/7/2,30,9.2.3 局部數(shù)據(jù)的組織,字節(jié)是可編址內(nèi)存的最小單位。 變量所需的存儲(chǔ)空間可以根據(jù)其類型而靜態(tài)確定。 一個(gè)過程所聲明的局部變量，按這些變量聲明時(shí)出現(xiàn)的次序，在局部數(shù)據(jù)域中依次分配空間。 局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置的地址來表示。 數(shù)據(jù)對(duì)象的存儲(chǔ)安排還有對(duì)齊的問題。 整數(shù)必須放在內(nèi)存中特定的位置，如被2、4、8整除 的地址,2019/7/2,31,9.2.3 局部數(shù)據(jù)的組織,在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的size分別是24和16，為什么不一樣？ typedef struct _a typedef struct _b char c1; char c1; long i; char c2; char c2; long i; double f; double f; a; b;,2019/7/2,32,9.2.3 局部數(shù)據(jù)的組織,在SPARC/Solaris工作站上下面兩個(gè)結(jié)構(gòu)的size分別是24和16，為什么不一樣？ typedef struct _a typedef struct _b char c1; 0 char c1; 0 long i; 4 char c2; 1 char c2; 8 long i; 4 double f; 16 double f;8 a; b;,2019/7/2,33,9.2.3 局部數(shù)據(jù)的組織,在X86/Linux機(jī)器的結(jié)果和SPARC/Solaris工作站不一樣，是20和16。 typedef struct _a typedef struct _b char c1; 0 char c1; 0 long i; 4 char c2; 1 char c2; 8 long i; 4 double f; 12 double f;8 a; b;,2019/7/2,34,靜態(tài)存儲(chǔ)分配策略(FORTRAN) 如果在編譯時(shí)能確定數(shù)據(jù)空間的大小，則可采用靜態(tài)分配方法：在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲(chǔ)空間中的位置。 動(dòng)態(tài)存儲(chǔ)分配策略(PASCAL) 如果在編譯時(shí)不能確定運(yùn)行時(shí)數(shù)據(jù)空間的大小，則必須采用動(dòng)態(tài)分配方法。允許遞歸過程及動(dòng)態(tài)申請(qǐng)、釋放內(nèi)存。 棧式動(dòng)態(tài)存儲(chǔ)分配 堆式動(dòng)態(tài)存儲(chǔ)分配,9.2.4 全局存儲(chǔ)分配策略,2019/7/2,35,9.3 靜態(tài)存儲(chǔ)分配策略,如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址，存儲(chǔ)空間的這種分配方法稱為靜態(tài)存儲(chǔ)分配。必須滿足如下條件： 數(shù)據(jù)對(duì)象的長(zhǎng)度和它在內(nèi)存中的位置在編譯時(shí)必須是已知的； 不允許過程的遞歸調(diào)用，因?yàn)橐粋€(gè)過程的所有活動(dòng)都是用同樣的局部名字綁定的； 數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立，因?yàn)闆]有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。,2019/7/2,36,某分段式程序運(yùn)行時(shí)的內(nèi)存劃分,2019/7/2,37,每個(gè)數(shù)據(jù)區(qū)有一個(gè)編號(hào)，地址分配時(shí)，在符號(hào)表中，對(duì)每個(gè)數(shù)據(jù)名登記其所屬數(shù)據(jù)區(qū)編號(hào)及在該區(qū)中的相對(duì)位置。 考慮子程序段： SUBROUTINE SWAP(A,B) T=A A=B B=T RETURN END,寄存器保護(hù)區(qū),返回地址,A,T,B,0,1,a,2019/7/2,38,靜態(tài)存儲(chǔ)分配策略,順序分配算法（基于調(diào)用圖） 按照程序段出現(xiàn)的先后順序逐段分配,程序段 區(qū)域 021 2236 3754 5571 7294 95104 共需要105個(gè)存儲(chǔ)單元,程序段號(hào)/所需數(shù)據(jù)空間,能用更少的空間么？,2019/7/2,39,分層分配算法,允許程序段之間的覆蓋（覆蓋可能性分析）,程序段 區(qū)域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63個(gè)存儲(chǔ)單元,思考：如何設(shè)計(jì)分配算法？,7/80,2019/7/2,40,9.4 棧式存儲(chǔ)分配策略,如果過程允許遞歸 某一時(shí)刻過程A可能已被自己調(diào)用了若干次，但只有最近一次處于執(zhí)行狀態(tài)。其余各次等待返回被中斷的那次調(diào)用 必須保存每次調(diào)用相應(yīng)的數(shù)據(jù)區(qū)內(nèi)容（活動(dòng)記錄） 引入一個(gè)運(yùn)行棧 讓過程的每次執(zhí)行和過程的活動(dòng)記錄相對(duì)應(yīng)。 每調(diào)用一次過程，就把該過程的活動(dòng)記錄壓入棧中，返回時(shí)彈出。 假設(shè)寄存器top標(biāo)記棧頂，局部名字x的相對(duì)地址為dx，則x的地址為top+dx 或 dxtop,2019/7/2,41,9.4.1 調(diào)用序列和返回序列,過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等 過程調(diào)用和返回是通過在目標(biāo)代碼中生成調(diào)用序列和返回序列來實(shí)現(xiàn)的 調(diào)用序列負(fù)責(zé)分配活動(dòng)記錄，并將相關(guān)信息填入活動(dòng)記錄中 返回序列負(fù)責(zé)恢復(fù)機(jī)器狀態(tài)，使調(diào)用過程能夠繼續(xù)執(zhí)行 調(diào)用序列和返回序列常常都分成兩部分，分處于調(diào)用過程和被調(diào)用過程中,2019/7/2,42,9.4.1 調(diào)用序列和返回序列,即使是同一種語言，過程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異 設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則： 以活動(dòng)記錄中間的某個(gè)位置作為基地址； 長(zhǎng)度能較早確定的域放在活動(dòng)記錄的中間； 一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面，以便其長(zhǎng)度的改變不會(huì)影響數(shù)據(jù)對(duì)象相對(duì)于中間那些域的位置； 用同樣的代碼來執(zhí)行各個(gè)活動(dòng)的狀態(tài)保存和恢復(fù)； 把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)記錄的地方。,2019/7/2,43,9.4.1 調(diào)用序列和返回序列,調(diào)用者和被調(diào)用者之間的任務(wù)劃分,2019/7/2,44,9.4.1 調(diào)用序列和返回序列,一種可能的調(diào)用序列： 調(diào)用者計(jì)算實(shí)參 調(diào)用者把返回地址和sp的舊值存入被調(diào)用者的活動(dòng)記錄中，然后將sp移過調(diào)用者的局部數(shù)據(jù)域和臨時(shí)變量域，以及被調(diào)用者的參數(shù)域和狀態(tài)域 被調(diào)用者保存寄存器值和其它機(jī)器狀態(tài)信息 被調(diào)用者初始化其局部數(shù)據(jù)，并開始執(zhí)行。,2019/7/2,45,9.4.1 調(diào)用序列和返回序列,一種可能的返回序列： 被調(diào)用者將返回值放入臨近調(diào)用者的活動(dòng)記錄的地方。 利用狀態(tài)域中的信息，被調(diào)用者恢復(fù)sp和其它寄存器，并且按調(diào)用者代碼中的返回地址返回。 盡管sp的值減小了，調(diào)用者仍然可以將返回值復(fù)制到自己的活動(dòng)記錄中，并用它來計(jì)算一個(gè)表達(dá)式。,2019/7/2,46,9.4.1 調(diào)用序列和返回序列,過程的參數(shù)個(gè)數(shù)可變的情況 函數(shù)返回值改成用寄存器傳遞 編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼 被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置 被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等 如C語言的printf,2019/7/2,47,過程調(diào)用的三地址碼: param x1 param x2 param xn call p，n,9.4.2 C語言的過程調(diào)用和返回,2019/7/2,48,1) 每個(gè)param xi(i=1,2,n)可直接翻譯成如下指令: (i+3)top:= xi (傳值) (i+3)top:=addr(xi) (傳地址) 2) call p，n 被翻譯成如下指令: 1top:=sp (保護(hù)現(xiàn)行sp) 3top:=n (傳遞參數(shù)個(gè)數(shù)) JSR p (轉(zhuǎn)子指令),參數(shù)個(gè)數(shù),返回地址,內(nèi)情向量,局部變量,老sp,臨時(shí)單元,對(duì)于par和call產(chǎn)生的目標(biāo)代碼,top sp ,調(diào)用過程的活動(dòng)記錄,老sp,參數(shù)個(gè)數(shù),形式單元,形式單元,2019/7/2,49,3) 進(jìn)入過程p后，首先應(yīng)執(zhí)行下述指令: sp:=top+1 (定義新的sp) 1sp:=返回地址 (保護(hù)返回地址) top:=top+L (新top) L：過程P的活動(dòng)記錄所需單元數(shù)， 在編譯時(shí)可確定。,TOP,調(diào)用過程的活動(dòng)記錄,返回地址,top,sp,2019/7/2,50,4) 過程返回時(shí)，應(yīng)執(zhí)行下列指令: top:=sp-1 (恢復(fù)調(diào)用前top) sp:=0sp (恢復(fù)調(diào)用前SP) X:=2top (把返回地址取到X中) UJ 0X (按X返回) UJ為無條件轉(zhuǎn)移指令， 即按X中的返回地址實(shí)行變址轉(zhuǎn)移,調(diào)用過程的活動(dòng)記錄,top,sp,sp,top,2019/7/2,51,9.4.3 棧中的可變長(zhǎng)數(shù)據(jù),活動(dòng)記錄的長(zhǎng)度在編譯時(shí)不能確定的情況 局部數(shù)組的大小要等到過程激活時(shí)才能確定 在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元 運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間,2019/7/2,52,9.4.3 棧中的可變長(zhǎng)數(shù)據(jù),圖9.13 訪問動(dòng)態(tài)分配的數(shù)組,2019/7/2,53,棧式存儲(chǔ)分配策略的局限,棧式分配策略在下列情況下行不通： 過程活動(dòng)停止后，局部名字的值還必須維持 被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期更長(zhǎng)，此時(shí)活動(dòng)樹不能正確描繪程序的控制流 不遵守棧式規(guī)則的有Pascal語言和C語言的動(dòng)態(tài)變量 Java禁止程序員自己釋放空間,2019/7/2,54,9.5 棧中非局部數(shù)據(jù)的訪問,本節(jié)內(nèi)容 無嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（C語言） 包含嵌套過程的靜態(tài)作用域的實(shí)現(xiàn)（Pascal語言） 動(dòng)態(tài)作用域的實(shí)現(xiàn)（Lisp語言）,2019/7/2,55,9.5.1 無過程嵌套的靜態(tài)作用域,假定:允許過程遞歸調(diào)用、允許過程含有可變數(shù)組，但過程定義不允許嵌套，如C語言。 過程體中的非局部引用可以直接使用靜態(tài)確定的地址 局部變量在棧頂?shù)幕顒?dòng)記錄中，可以通過sp指針來訪問 無須深入棧中取數(shù)據(jù)，無須訪問鏈 過程可以作為參數(shù)來傳遞，也可以作為結(jié)果來返回,C語言的函數(shù)聲明不能嵌套，函數(shù)不論在什么情況下激活，要訪問的數(shù)據(jù)分成兩種情況: 非靜態(tài)局部變量（包括形式參數(shù)），它們分配在活動(dòng)記錄棧頂?shù)哪莻€(gè)活動(dòng)記錄中 外部變量（包括定義在其它源文件中的外部變量）和靜態(tài)的局部變量，它們都分配在靜態(tài)數(shù)據(jù)區(qū),9.5.1 無過程嵌套的靜態(tài)作用域,2019/7/2,56,2019/7/2,57,全局?jǐn)?shù)據(jù)說明 main( ) main中的數(shù)據(jù)說明 void R( ) R中的數(shù)據(jù)說明 void Q( ) Q中的數(shù)據(jù)說明 ,主程序過程Q 過程R,Q的活動(dòng)記錄,主程序活動(dòng)記錄,TOP,R的活動(dòng)記錄,SP,參數(shù)個(gè)數(shù),返回地址,形式單元,內(nèi)情向量,局部變量,老SP,臨時(shí)單元,全局?jǐn)?shù)據(jù)區(qū),2019/7/2,58,9.5.2 有過程嵌套的靜態(tài)作用域,假定語言不僅允許過程的遞歸調(diào)用(和可變數(shù)組)，而且允許過程定義的嵌套，如PASCAL，PL語言。 sort readarray exchange quicksort partition,2019/7/2,59,(1) program sort(input, output); (2) var a :array010 of integer; (3) x :integer; (4) procedure readarray; (5) var i :integer; (6) begin a end readarray; (7) procedure exchange(i,j:integer); (8) begin (9) x:= ai; ai:=aj; aj:= x; (10) end exchange ;,program sort procedure readarray procedure exchange procedure quicksort function partition,2019/7/2,60,(11) procedure quicksort(m,n:integer); (12) var k,v:integer; (13) function partition(y,z:integer): integer; (14) var i,j:integer; (15) begin a (16) v (17) exchange(i,j); (18) end partition; (19) begin end quicksort; (20) begin end sort.,program sort procedure readarray procedure exchange procedure quicksort function partition,2019/7/2,61,9.5.2 有過程嵌套的靜態(tài)作用域,引入概念：過程嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度,2019/7/2,62,9.5.2 有過程嵌套的靜態(tài)作用域,1. 訪問鏈,2019/7/2,63,9.5.2 有過程嵌套的靜態(tài)作用域,假定過程p的嵌套深度為np，它引用嵌套深度為na的變量a，na np。如何訪問a的存儲(chǔ)單元？ 從棧頂?shù)幕顒?dòng)記錄開始, 追蹤訪問鏈np-na次。 到達(dá)a的聲明所在過程的活動(dòng)記錄。 訪問鏈的追蹤用間接操作就可完成。,2019/7/2,64,9.5.2 有過程嵌套的靜態(tài)作用域,過程p對(duì)變量a訪問時(shí)，a的地址由下面的二元組表示： （np na，a在活動(dòng)記錄中的偏移）,2019/7/2,65,9.5.2 有過程嵌套的靜態(tài)作用域,如何建立訪問鏈 假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的 過程x np nx的情況 x必須在p中進(jìn)行定義，否則它對(duì)于p來說就是不可訪問的 被調(diào)用過程的訪問鏈必須指向調(diào)用過程的活動(dòng)記錄的訪問鏈,2019/7/2,66,9.5.2 有過程嵌套的靜態(tài)作用域,如何建立訪問鏈 假定嵌套深度為np的過程p調(diào)用嵌套深度為nx的過程x np nx的情況 p和x的嵌套深度分別為1，2，nx 1的外圍過程肯定相同 追蹤訪問鏈np nx + 1次，到達(dá)了靜態(tài)包圍x和p的且離它們最近的那個(gè)過程的最新活動(dòng)記錄 所到達(dá)的訪問鏈就是x的活動(dòng)記錄中的訪問鏈應(yīng)該指向的那個(gè)訪問鏈,2019/7/2,67,9.5.2 有過程嵌套的靜態(tài)作用域,2.過程型參數(shù)的訪問鏈 program param(input, output); procedure b(function h(n: integer): integer); begin writeln(h(2) end b; procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end f; begin m := 0; b(f) end c; begin c end.,過程作為參數(shù)傳遞時(shí)，怎樣在該過程被激活時(shí)建立它的訪問鏈 從b的訪問鏈難以建立f的訪問鏈,激活f,c傳遞參數(shù)f時(shí)，像調(diào)用f一樣為f建立一個(gè)訪問鏈，該訪問鏈同f一起傳遞給b。f被激活時(shí)用這個(gè)訪問鏈建立f的活動(dòng)記錄的訪問鏈,2019/7/2,68,9.5.2 有過程嵌套的靜態(tài)作用域,program param(input, output);（過程作為參數(shù)） procedure b(function h( begin writeln(h(2) end ; procedure c; var m: integer; function f(n: integer) begin f := m+n end f; begin m := 0; b(f) end c; begin c end.,2019/7/2,69,9.5.2 有過程嵌套的靜態(tài)作用域,program ret (input, output);（過程作為返回值） var f: function (integer): integer; function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln ( g(2) end; begin f := a; b(f) end.,ret,a,b,addm,被調(diào)過程addm活動(dòng)的生存期超出了調(diào)用過程a活動(dòng)的生存期,棧式存儲(chǔ)分配策略失效！,活動(dòng)樹,2019/7/2,70,3. Display表 Display表是一個(gè)指針數(shù)組d，在運(yùn)行過程中，若當(dāng)前活動(dòng)的過程的嵌套深度為i，則di中存放當(dāng)前的活動(dòng)記錄地址，di-1,di-2, ,d1 中依次存放著當(dāng)前活動(dòng)的過程的直接外層， , 直至最外層（主程序）等每一層過程的最新活動(dòng)地址。 這樣，嵌套深度為j的變量a存放在由dj所指出的活動(dòng)記錄中。 在運(yùn)行過程中維持一個(gè)Display表實(shí)現(xiàn)非局部訪問比存取鏈效率要高。,9.5.2 有過程嵌套的靜態(tài)作用域,2019/7/2,71,Display表的維護(hù)（過程不作為參數(shù)傳遞） 當(dāng)嵌套深度為i的過程的活動(dòng)記錄壓在棧頂時(shí)： (1)在新的活動(dòng)記錄中保存di的值； (2)置di指向新的活動(dòng)記錄。 在一個(gè)活動(dòng)結(jié)束前， di置成保存的舊值。 用Display表如何訪問非局部量？ 1. Display表是一個(gè)數(shù)組，開始地址用通用 寄存器指出； 2. Display表由一組寄存器實(shí)現(xiàn)。,9.5.2 有過程嵌套的靜態(tài)作用域,2019/7/2,72,一個(gè)例子,program P; var a, x : integer; procedure Q(b: integer); var i: integer; procedure R(u: integer; var v: integer); var c, d: integer; begin if u=1 then R(u+1, v) v:=(a+c)*(b-d); end R begin R(1,x); end Q,procedure S; var c, i:integer; begin a:=1; Q(c); end S begin a:=0; S; end. P,主程序P 過程 S 過程 Q 過程 R 過程 R,2019/7/2,73,一、通過靜態(tài)鏈訪問非局部數(shù)據(jù) 靜態(tài)鏈：指向本過程的直接外層過程的活動(dòng)記錄的起始地址，也稱訪問鏈。 動(dòng)態(tài)鏈：指向本過程的調(diào)用過程的活動(dòng)記錄的起始地址，也稱控制鏈。,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,SP0,1,2,動(dòng)態(tài)鏈(老SP),TOP,靜態(tài)鏈,2019/7/2,74,SP ,TOP,主程序P,2019/7/2,75,2,a,3,SP ,TOP,動(dòng)態(tài)鏈,靜態(tài)鏈,主程序P過程 S,問：第N層過程調(diào)用第 N+1層過程，如何確定被調(diào)用過程(第 N+1層) 的靜態(tài)鏈？,答：調(diào)用過程(第N層過程)的最新活動(dòng)記錄的起始地址.,0,2019/7/2,76,6,SP ,TOP,動(dòng)態(tài)鏈,靜態(tài)鏈,主程序P 過程 S 過程 Q,問：第N層過程調(diào)用第 N層過程，如何確定被調(diào)用過程(第 N層) 的靜態(tài)鏈？,答：調(diào)用過程(第N層過程)的靜態(tài)鏈的值。,返回地址,2019/7/2,77,1,0,2,6,動(dòng)態(tài)鏈,靜態(tài)鏈,主程序P 過程 S 過程 Q 過程 R,12,SP ,TOP,返回地址,返回地址,返回地址,2019/7/2,78,1,a,3,6,動(dòng)態(tài)鏈,靜態(tài)鏈,主程序P 過程 S 過程 Q 過程 R 過程 R,12,返回地址,18,TOP,SP ,返回地址,返回地址,返回地址,2019/7/2,79,返回地址,1,返回地址,6,動(dòng)態(tài)鏈,靜態(tài)鏈,主程序P 過程 S 過程 Q 過程 R 過程 Q,返回地址,12,返回地址,18,TOP,SP ,問：第N層過程調(diào)用第 N-x層過程，如何確定被調(diào)用過程(第 N-x層)過程的靜態(tài)鏈？,答:沿著調(diào)用過程(第N層過程)的靜態(tài)鏈向前走x步到達(dá)的活動(dòng)記錄的靜態(tài)鏈的值。,2019/7/2,80,二、通過Display表 訪問非局部數(shù)據(jù),SPn為第n層過程數(shù)據(jù)區(qū)首址,9.5.2 有過程嵌套的靜態(tài)作用域,SPn SPn-1 SP1 SP0,SP,2019/7/2,81,令過程R的外層為Q，Q的外層為主程序P，則過程R運(yùn)行時(shí)的DISPLAY表內(nèi)容為：,2019/7/2,82,問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？,2019/7/2,83,問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？,l2: P1的最新活動(dòng)記 錄的起始地址,P0的最新活動(dòng)記 錄的起始地址,P1的display表,P0的最新活動(dòng)記錄 的起始地址,l2: P2的最新活動(dòng)記 錄的起始地址,P2的display表,從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。,2019/7/2,84,問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？,l2-1: P1的最新活動(dòng) 記錄的起始地址,P0的最新活動(dòng)記錄 的起始地址,P1的display表,P0的最新活動(dòng)記錄 的起始地址,P1的最新活動(dòng)記錄 的起始地址,P2的display表,從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。,l2: P2的最新活動(dòng)記 錄的起始地址,2019/7/2,85,問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？,P1的最新活動(dòng)記錄 的起始地址,P0的最新活動(dòng)記錄 的起始地址,P1的display表,P0的最新活動(dòng)記錄 的起始地址,P2的display表,從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。,l2: P2的最新活動(dòng) 記錄的起始地址,l2: P2的最新活動(dòng) 記錄的起始地址,2019/7/2,86,問題：當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display表？,答案：從P1的display表中自底而上地取過l2個(gè)單元（l2為P2的層數(shù)）再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display表。 把P1的display表地址作為連接數(shù)據(jù)之一(稱為全局display地址)傳送給P2就能夠建立P2的display表。,2019/7/2,87,diaplay表在活動(dòng)記錄中的相對(duì)地址d在編譯時(shí)能完全確定。 假定在現(xiàn)行過程中引用了某層過程(令其層次為k)的X變量，那么，可用下面兩條指令獲得X的地址: LD R1 (d+k)SP LD R2 dxR1,嵌套過程語言活動(dòng)記錄,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,SP 0,1,2,老SP,TOP,Display 表,全局Display,3,d,2019/7/2,88,一個(gè)例子,program P; var a, x : integer; procedure Q(b: integer); var i: integer; procedure R(u: integer; var v: integer); var c, d: integer; begin if u=1 then R(u+1, v) v:=(a+c)*(b-d); end R begin R(1,x); end Q,procedure S; var c, i:integer; begin a:=1; Q(c); end S begin a:=0; S; end. P,主程序P 過程 S 過程 Q 過程 R 過程 R,2019/7/2,89,主程序過程 S,TOP,SP ,動(dòng)態(tài)鏈,2019/7/2,90,返回地址,1,返回地址,6,主程序P過程 S 過程 Q,動(dòng)態(tài)鏈,TOP,SP ,2019/7/2,91,返回地址,1,返回地址,6,主程序P過程 S 過程 Q 過程 R,動(dòng)態(tài)鏈,返回地址,14,TOP,SP ,2019/7/2,92,返回地址,1,返回地址,6,主程序P 過程 S 過程 Q 過程 R 過程 R,動(dòng)態(tài)鏈,返回地址,14,返回地址,22,TOP,SP ,2019/7/2,93,過程調(diào)用、過程進(jìn)入、過程返回,每個(gè)par Ti(i=1,2,n)可直接 翻譯成如下指令: (i+4)TOP:= Ti (傳值) (i+4)TOP:=addr(Ti ) (傳地址),參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,老SP,Display 表,全局Display,TOP,SP ,調(diào)用過程的 活動(dòng)記錄,形式單元,2019/7/2,94,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,老SP,Display 表,全局Display,2. call P，n 被翻譯成: 1TOP:=SP (保護(hù)現(xiàn)行SP) 3TOP:=SP+d (傳送現(xiàn)行display地址) 4TOP:=n (傳遞參數(shù)個(gè)數(shù)) JSR (轉(zhuǎn)子指令),過程調(diào)用、過程進(jìn)入、過程返回,TOP,SP ,調(diào)用過程的 活動(dòng)記錄,老SP,全局Display,參數(shù)個(gè)數(shù),2019/7/2,95,3. 轉(zhuǎn)進(jìn)過程P后，首先定義新的SP和TOP，保存返回地址。 4. 根據(jù)“全局display“建立現(xiàn)行過程的display：從全局display表中自底向上地取l個(gè)單元，在添上進(jìn)入P后新建立的SP值就構(gòu)成了P的display。,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,老SP,Display 表,全局Display,TOP,SP ,調(diào)用過程的 活動(dòng)記錄,返回地址,Display 表,過程調(diào)用、過程進(jìn)入、過程返回,2019/7/2,96,5. 過程返回時(shí)，執(zhí)行下述指令: TOP:=SP-1 SP:=0SP X:=2TOP UJ 0X,參數(shù)個(gè)數(shù),返回地址,形式單元,臨時(shí)單元,內(nèi)情向量,局部變量,老SP,Display 表,全局Display,TOP,SP ,調(diào)用過程的 活動(dòng)記錄,TOP,SP ,過程調(diào)用、過程進(jìn)入、過程返回,2019/7/2,97,9.5.3 動(dòng)態(tài)作用域的實(shí)現(xiàn),從技術(shù)上講，如果作用域策略需要基于程序運(yùn)行時(shí)才能知道的因素，則任何作用域策略都將是動(dòng)態(tài)的。但“動(dòng)態(tài)作用域”這個(gè)術(shù)語通常是指下面的策略：名字x的引用指向帶有x聲明的最近被調(diào)用的過程中x的這個(gè)聲明。 在某種意義上說，動(dòng)態(tài)作用域規(guī)則相對(duì)于時(shí)間，而靜態(tài)作用域規(guī)則相對(duì)于空間。,2019/7/2,98,9.5.3 動(dòng)態(tài)作用域,程序運(yùn)行時(shí)，一個(gè)名字a實(shí)施其影響，直到含a的聲明的一個(gè)過程開始執(zhí)行時(shí)暫停，此過程停止時(shí)，該影響恢復(fù)。 設(shè)有下面的的調(diào)用序列： A B C P 過程P中有對(duì)x的非局部引用，沿動(dòng)態(tài)鏈（紅鏈）查找，最先找到的便是。,2019/7/2,99,9.5.3 動(dòng)態(tài)作用域,program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin 靜態(tài)作用域 r := 0.25; 0.250 0.250 show; small; writeln; 0.250 0.250 show; small; writeln end.,2019/7/2,100,9.5.3 動(dòng)態(tài)作用域,program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; var r: real; begin r := 0.125; show end; begin 動(dòng)態(tài)作用域 r := 0.25; 0.250 0.125 show; small; writeln; 0.250 0.125 show; small; writeln end.,2019/7/2,101,9.5.3 動(dòng)態(tài)作用域,實(shí)現(xiàn)動(dòng)態(tài)作用域的方法 深訪問(訪問非局部名字時(shí)的開銷大,易于實(shí)現(xiàn)過程類參數(shù)) 用控制鏈搜索運(yùn)行棧，尋找包含該非局部名字的第一個(gè)活動(dòng)記錄 淺訪問(活動(dòng)開始和結(jié)束時(shí)的開銷大) 將每個(gè)名字的當(dāng)前值保存在靜態(tài)分配的內(nèi)存空間中 當(dāng)過程p開始一個(gè)新的活動(dòng)時(shí)，p的局部名字n使用在靜態(tài)數(shù)據(jù)區(qū)分配給n的內(nèi)存單元。n的先前值必須保存在p的活動(dòng)記錄中，當(dāng)p的活動(dòng)結(jié)束時(shí)再恢復(fù),2019/7/2,102,9.6 堆管理,對(duì)于允許程序?yàn)樽兞吭谶\(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)和釋放存儲(chǔ)空間的語言, 采用堆式分配是最有效的解決方案. 活動(dòng)結(jié)束時(shí)必須保持局部名字的值。 被調(diào)用者的活動(dòng)比調(diào)用者的活動(dòng)的生存期長(zhǎng)。 堆式分配的基本思想是, 為運(yùn)行的程序劃出適當(dāng)大的空間(稱為堆Heap), 每當(dāng)程序申請(qǐng)空間時(shí), 就從堆的空閑區(qū)找出一塊空間分配給程序, 每當(dāng)釋放時(shí)則回收之. 內(nèi)存管理器 分配和回收堆區(qū)空間的子系統(tǒng) 是應(yīng)用程序和操作系統(tǒng)之間的一個(gè)接口,2019/7/2,103,9.6.1 內(nèi)存管理器,內(nèi)存管理器的基本任務(wù) 空間分配。每當(dāng)程序?yàn)槟硞€(gè)變量或?qū)ο笊暾?qǐng)一塊內(nèi)存空間時(shí)，內(nèi)存管理器就產(chǎn)生一塊連續(xù)的具有被請(qǐng)求大小的堆空間。 空間回收。內(nèi)存管理器把回收的空間返還到空閑空間的緩沖池中，用于滿足其它的分配請(qǐng)求。,2019/7/2,104,9.6.1 內(nèi)存管理器,如果下面兩個(gè)條件成立的話，內(nèi)存管理將會(huì)變得相對(duì)簡(jiǎn)單一些 所有的分配請(qǐng)求都要求相同大小的塊； 存儲(chǔ)空間按照某種可以預(yù)見的方式來釋放，如先分配者先釋放。,2019/7/2,105,9.6.1 內(nèi)存管理器,內(nèi)存管理器的設(shè)計(jì)目標(biāo) 空間效率。內(nèi)存管理器應(yīng)該使程序所需堆區(qū)空間的總量達(dá)到最小，以便在某個(gè)固定大小的虛擬地址空間中運(yùn)行更大的程序。方法：減少內(nèi)存碎片的數(shù)量。 程序效率。內(nèi)存管理器應(yīng)該充分利用內(nèi)存子系統(tǒng)，以便使程序運(yùn)行得更快。方法：利用程序的“局部性”，即程序在訪問內(nèi)存時(shí)具有非隨機(jī)性聚集的特性。 低開銷。由于存儲(chǔ)分配和回收在很多程序中都是常用的操作，所以內(nèi)存管理器應(yīng)該盡可能地提高這些操作的執(zhí)行效率，也就是說要盡可能地降低它們的開銷。,2019/7/2,106,9.6.2 內(nèi)存體系,要想做好內(nèi)存管理和編譯器優(yōu)化，首先要充分了解內(nèi)存的工作機(jī)理。 內(nèi)存訪問時(shí)間的巨大差異來源于硬件技術(shù)的局限。,圖9.21 典型的內(nèi)存體系,2019/7/2,107,9.6.3 程序中的局部性,程序的局部性 程序中的大部分運(yùn)行時(shí)間都花費(fèi)在較少的一部分代碼中，而且只是涉及到一小部分?jǐn)?shù)據(jù)。 時(shí)間局部性：如果某個(gè)程序訪問的內(nèi)存位置有可能在很短的時(shí)間內(nèi)被再次訪問 空間局部性：如果被訪問過的內(nèi)存位置的鄰近位置有可能在很短的時(shí)間內(nèi)被再次訪問,2019/7/2,108,9.6.3 程序中的局部性,程序的局部性使得我們可以充分利用圖9.21所示的內(nèi)存層次結(jié)構(gòu)，即將最常用的指令和數(shù)據(jù)放在快而小的內(nèi)存中，而將其余部分放在慢而大的內(nèi)存中，這將顯著降低程序的平均內(nèi)存訪問時(shí)間 很多程序在對(duì)指令和數(shù)據(jù)的訪問方式上既表現(xiàn)出時(shí)間局部性，又表現(xiàn)出空間局部性,2019/7/2,109,9.6.