目標程序運行時的存儲組織概論(ppt 54頁)-文庫吧
2025-02-11 13:07 本頁面
【正文】 所指的塊之前，然后 available指向新歸還的塊。 占用 占用 占用 空閑 空閑 空閑 available (a) 占用 占用 空閑 空閑 空閑 (b) 空閑 available 圖 定長塊管理 2）變長塊管理 除了按定長塊進行分配之外，還可以根據(jù)需要分配長度不同的存儲塊，可以隨要求而變。按這種方法，初始化時存儲空間是一個整塊。按照用戶的需要，分配時先是從一個整塊里分割出滿足需要的一小塊，以后，歸還時，如果新歸還的塊能和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個鏈表。再進行分配時，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個滿足需要的空閑塊時，該分配哪一塊呢 ? 通常有三種不同的分配策略： 變長塊管理通常有三種不同的分配策略： ? 首次滿足法（時間優(yōu)先） 。 ? 最優(yōu)滿足法（空間優(yōu)先） 。 ? 最差滿足法（時間優(yōu)先）。 上述三種分配策略各有所長。 棧式存儲分配的實現(xiàn) 前面提到，使用棧式存儲分配策略意味著，運行時每當進入一個過程，就在棧頂為該過程的臨時工作單元，局部變量，機器狀態(tài)及返回地址等信息分配所需的數(shù)據(jù)空間，當一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間也即釋放。 為討論方便，首先引入一個術(shù)語 過程的活動記錄AR(Activation Record)。過程的活動記錄是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的動態(tài)信息，這些信息可以如圖 。 圖 過程的活動記錄 返回地址 實參 控制鏈 存取鏈 機器狀態(tài)信息 局部變量 臨時工作單元 ① 臨時工作單元 ：比如計算表達式過程中需存放中間結(jié)果用的臨時值單元。 ② 局部變量 ：一個過程的局部變量。 ③ 機器狀態(tài)信息： 保存該過程執(zhí)行前關(guān)于機器狀態(tài)的信息，諸如程序計數(shù)器、寄存器的值，這些值都需要在控制從該過程返回時給予恢復(fù)。 ④ 存取鏈 ：用以存取非局部變量，這些變量存放于其它過程的活動記錄中。并不是所有語言需要該信息。 ⑤ 控制鏈 ：指向調(diào)用該過程的那個過程的活動記錄。 ⑥ 實參 ：也稱形式單元，由調(diào)用過程向該被調(diào)過程提供實參的值（或地址）。當然在實際編譯程序中，也常常使用機器寄存器傳遞實參。 ⑦ 返回地址 ：保存該被調(diào)過程返回后的地址。 圖 過程的活動記錄 返回地址 實參 控制鏈 存取鏈 機器狀態(tài)信息 局部變量 臨時工作單元 靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址， 即指向 定義 本過程的 直接外層過程 （或主程序）運行時最新 活動記錄的基地址 。 動態(tài)鏈 ，指向 調(diào)用 該過程前正在運行過程的數(shù)據(jù)段基地址。 簡單的棧式分配的實現(xiàn) 程序結(jié)構(gòu)特點 :過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組；例： program main 全局變量的說明 proc R …… end R。 proc Q …… end Q。 主程序執(zhí)行語句 end main 圖 過程定義不嵌套的程序結(jié)構(gòu) 這種情況下，采用棧式動態(tài)分配策略，即，運行時，每當進入一個過程，則為該過程分配一段存儲區(qū)，當一個過程工作完畢返回時，它所占用的存儲區(qū)可釋放。程序運行時的存儲空間 (棧 )中在某一時刻可能會包含某個過程的幾個活動記錄（某個過程遞歸調(diào)用的情況）；另外，同樣的一個存儲位置，在不同運行時刻可能分配給不同的數(shù)據(jù)對象。 例如圖 ，若主程序調(diào)用了過程Q， Q又調(diào)用了 R，在 R進入運行后的存儲結(jié)構(gòu)如圖（ a）所示。 若主程序調(diào)用了過程 Q， Q遞歸調(diào)用自己，在 Q過程第二次進入運行后的存儲結(jié)構(gòu)如圖 （ b）所示。 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)直接外層最新活動記錄的起始地址， 即指向 定義 本過程的 直接外層過程 （或主程序）運行時 最新 活動記錄的基地址 。 動態(tài)鏈 ，指向 調(diào)用 該過程前正在運行過程的數(shù)據(jù)段基地址。 指向調(diào)用該過程的那個過程的最新活動記錄的起始地址 用以存取非局部變量，這些變量存放于其他過程的活動記錄中。 TOP? 臨時工作單元 局部簡單變量 局部數(shù)組的內(nèi)情向量 返回地址 實參 （形式單元） SP? 參數(shù)個數(shù) 控制鏈 （老 SP） 圖 無嵌套定義 的過程活動記錄內(nèi)容 常常使用兩個指針指示棧最頂端的數(shù)據(jù)區(qū)，一個稱為 SP，一個稱為 TOP。 SP總是指向現(xiàn)行過程活動記錄的起點， TOP則始終指向已占用的棧頂單元。 這種語言若含有可變數(shù)組，則其過程活動記錄的內(nèi)容可如圖 。這里把控制鏈也稱作老 SP，即調(diào)用該過程的那個過程的最新活動記錄的起點。 嵌套過程語言的棧式實現(xiàn) 主要特點： ? （語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，數(shù)組或過程等）。 ? （實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。 (1) program sort(input, output)。 //sort的過程頭 (2) var a: array [0..10] of integer。 (3) x: integer。 (4) procedure readarray。 //sort內(nèi)嵌套定義的 readar
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1