目標程序運行時的存儲組織概論(ppt 54頁)-預覽頁
【正文】 棧式動態(tài)存儲分配 這種分配策略是將整個程序的數(shù)據(jù)空間設計為一個棧。 . 堆式動態(tài)存儲分配 如果一個程序語言提供用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間的機制，或者不僅有過程而且有進程的程序結構，一般用堆式的動態(tài)存儲分配方案。 這種分配方式的存儲管理技術甚為復雜，我們這里舉出這種分配方法必須考慮的幾個問題。但不論采用什么原則，整個大存區(qū)在一定時間之后必然會變成零碎不堪。 堆式的動態(tài)存儲分配策略 : 另外，如果運行程序要求一塊體積為 N的空間，但所有空閑塊的總和也不夠 N，那又應怎么辦呢？ 有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對付這種局面。初始化時，將堆存儲空間分成長度相等的若干塊，每塊中指定一個鏈域，按照鄰塊的順序把所有塊鏈成一個 鏈表 ，用指針 available指向鏈表中的第一塊。 占用 占用 占用 空閑 空閑 空閑 available (a) 占用 占用 空閑 空閑 空閑 (b) 空閑 available 圖 定長塊管理 2）變長塊管理 除了按定長塊進行分配之外，還可以根據(jù)需要分配長度不同的存儲塊，可以隨要求而變。若空閑塊表中有若干個滿足需要的空閑塊時，該分配哪一塊呢 ? 通常有三種不同的分配策略： 變長塊管理通常有三種不同的分配策略： ? 首次滿足法（時間優(yōu)先） 。 棧式存儲分配的實現(xiàn) 前面提到，使用棧式存儲分配策略意味著，運行時每當進入一個過程，就在棧頂為該過程的臨時工作單元，局部變量，機器狀態(tài)及返回地址等信息分配所需的數(shù)據(jù)空間，當一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間也即釋放。 ② 局部變量 ：一個過程的局部變量。 ⑤ 控制鏈 ：指向調(diào)用該過程的那個過程的活動記錄。 圖 過程的活動記錄 返回地址 實參 控制鏈 存取鏈 機器狀態(tài)信息 局部變量 臨時工作單元 靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址， 即指向 定義 本過程的 直接外層過程 （或主程序）運行時最新 活動記錄的基地址 。 主程序執(zhí)行語句 end main 圖 過程定義不嵌套的程序結構 這種情況下，采用棧式動態(tài)分配策略，即，運行時，每當進入一個過程，則為該過程分配一段存儲區(qū)，當一個過程工作完畢返回時，它所占用的存儲區(qū)可釋放。 TOP? 臨時工作單元 局部簡單變量 局部數(shù)組的內(nèi)情向量 保存運 行過程前的狀態(tài) （返回地址，寄存器值 … ） 實參 （形式單元）和參數(shù)個數(shù) SP? 存取鏈（ 靜態(tài)鏈 ） 控制鏈 （ 動態(tài)鏈， 老 SP） 圖 過程的活動記錄 Main? Q? R TOP? R的活動記錄 SP? 主程序全局 數(shù)據(jù)區(qū) Q的活動記錄 Main?Q?Q Q的活動記錄 主程序全局 數(shù)據(jù)區(qū) Q的活動記錄 圖 棧式存儲分配 靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址， 即指向 定義 本過程的 直接外層過程 （或主程序）運行時 最新 活動記錄的基地址 。 SP總是指向現(xiàn)行過程活動記錄的起點， TOP則始終指向已占用的棧頂單元。 ? （實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。 (4) procedure readarray。 //sort內(nèi)嵌套定義的 exchange的過程頭 (8) begin (9) x∶=a[i]。 (11) procedure quicksort(m,n: integer)。 (15) begin ?a? //partition 的函數(shù)體 (16) ?v? (17) ? exchange(i,j)。 設法跟蹤每個外層過程的最新活動記錄 AR的位置。過程活動記錄的內(nèi)容如圖 （ a）所示。 圖 exchange之后運行棧的示意，我們僅把存取鏈和控制鏈的值標明。 Display表 嵌套層次顯示表 ，即每進入一個過程后，在建立它的活動記錄的同時建立一張 Display表。 B1:begin real z。 B4:begin array C[1:m]。 L8:end。 一則，每逢進入 一個分程序，就照樣建立連接數(shù)據(jù)和 DISPLAY表 ,這是不必要的。但這種辦法是很浪費時間的。第二，不把分程序看作“無參過程”，每個分程序享用包圍它的那個最近過程的 DISPLAY。 這樣，每個過程的活動記錄所含的內(nèi)容有： TOP值，它指向過程活動記錄的棧頂位置。 對于每個分程序來說，它們包括： （ 1)分程序的 TOP值。 (3) begin。 帶有非局部變量和形參的 PASCAL過程 非局變量 a[i]和 a[j]的 值進行交換， i,j為形參（在這里是傳值） (1)program reference(input,output)。 (5) begin (6) temp:=x。 b:=2。 例如：過程 swap(x,y:integer)。 （ 3）被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。 x:=y； y:=temp end； 調(diào)用 swap(a,b) 過程將不會影響 a和 b的值。 var temp:integer。 (3){ int temp。 (5)} (6)main( ) (7){ int a=1,b=2。 過程參數(shù) 一個嵌套過程（函數(shù)）可以作為參數(shù)傳遞。 ? (3) begin writeln(h(2)) end。 ? (7) begin f:=m+n end{
教學課件相關推薦
鄂ICP備17016276號-1