運行時的存儲組織.ppt

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