目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織概論(ppt54頁(yè))-wenkub
2023-03-12 13:07:58 本頁(yè)面
【正文】 B2:begin real d, e。 例：見(jiàn) P238239 分程序結(jié)構(gòu) Procedure A(m,n)。 圖 運(yùn)行棧 靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址， 動(dòng)態(tài)鏈 ，指向 調(diào)用 該過(guò)程前正在運(yùn)行過(guò)程的數(shù)據(jù)段基地址。 圖 嵌套定義過(guò)程的活動(dòng)記錄和存儲(chǔ)棧 (a) 局部變量 ┆ 存取鏈 控制鏈 TOP SP ┆ ┆ 存取鏈 控制鏈 (老 SP) ┆ ┆ TOP SP (b) quicksort的 AR sort的 AR 再回到圖 。 2. 用 DISPLAY表。 (19) begin?end{quicksort}。 (13) function partition(y,z:integer):integer。 a[j]∶=x。 (6) begin?a?end{readarray}。 //sort的過(guò)程頭 (2) var a: array [0..10] of integer。這里把控制鏈也稱作老 SP，即調(diào)用該過(guò)程的那個(gè)過(guò)程的最新活動(dòng)記錄的起點(diǎn)。 指向調(diào)用該過(guò)程的那個(gè)過(guò)程的最新活動(dòng)記錄的起始地址 用以存取非局部變量，這些變量存放于其他過(guò)程的活動(dòng)記錄中。 例如圖 ，若主程序調(diào)用了過(guò)程Q， Q又調(diào)用了 R，在 R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖（ a）所示。 簡(jiǎn)單的棧式分配的實(shí)現(xiàn) 程序結(jié)構(gòu)特點(diǎn) :過(guò)程定義不嵌套，過(guò)程可遞歸調(diào)用，含可變數(shù)組；例： program main 全局變量的說(shuō)明 proc R …… end R。當(dāng)然在實(shí)際編譯程序中，也常常使用機(jī)器寄存器傳遞實(shí)參。 ④ 存取鏈 ：用以存取非局部變量，這些變量存放于其它過(guò)程的活動(dòng)記錄中。過(guò)程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的動(dòng)態(tài)信息，這些信息可以如圖 。 ? 最差滿足法（時(shí)間優(yōu)先）。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊能和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。歸還時(shí)，把所歸還的塊插入鏈表。 但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？ 要使用廢品回收技術(shù)，除了在語(yǔ)言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不能實(shí)現(xiàn)。 解決辦法似乎很簡(jiǎn)單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空間。但這種做法較麻煩。 此時(shí) ,空間的使用未必服從“先申請(qǐng)后釋放，后申請(qǐng)先釋放”的原則，那么棧式的動(dòng)態(tài)分配方案就不適用了。 過(guò)程所需的數(shù)據(jù)空間包括兩部分： ① 生存期在本過(guò)程這次活動(dòng)中的數(shù)據(jù)對(duì)象； ② 用以管理過(guò)程活動(dòng)的記錄信息 。 因?yàn)閷?duì)于這種程序在編譯時(shí)無(wú)法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。 ?源語(yǔ)言的結(jié)構(gòu)特點(diǎn)、源語(yǔ)言的數(shù)據(jù)類(lèi)型、源語(yǔ)言中決定名字作用域的規(guī)則等因素影響存儲(chǔ)空間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分配的基本策略。 因此運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖 。 數(shù)據(jù)空間 應(yīng)包括： ? 用戶定義的各種類(lèi)型的數(shù)據(jù)對(duì)象（變量和常數(shù)）所 需的存儲(chǔ)空間； ? 作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元； ? 調(diào)用過(guò)程時(shí)所需的連接單元； ? 組織輸入 /輸出所需的緩沖區(qū)。 目標(biāo)代碼所占用空間 的大小在編譯時(shí)能確定。 目標(biāo)代碼區(qū) code 靜態(tài)數(shù)據(jù)區(qū) static 棧 Stack 堆 heap 圖 目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分 數(shù)據(jù)空間 ?所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個(gè)名字與一個(gè)存儲(chǔ)位置關(guān)聯(lián)起來(lái)，該存儲(chǔ)位置用以保存名字的值。 數(shù)據(jù)空間的三種不同使用方法和管理方法 數(shù)據(jù)空間的使用和管理方法 : 簡(jiǎn)單的棧式分配方案 嵌套過(guò)程的棧式分配方案 分程序結(jié)構(gòu)的存儲(chǔ)分配方案 靜態(tài)存儲(chǔ)分配、 動(dòng)態(tài)存儲(chǔ)分配 —— 棧式 堆式 靜態(tài)存儲(chǔ)分配 如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部的數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。 若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱為可變（動(dòng)態(tài)）數(shù)組。 棧式動(dòng)態(tài)存儲(chǔ)分配策略適用于 PASCAL， C，ALGOL之類(lèi)具有遞歸結(jié)構(gòu)的語(yǔ)言的實(shí)現(xiàn)。通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配方案。 因此，常常仍采用“先碰上哪塊比 N大就從其中分出 N個(gè)單元”的原則。 這里主要問(wèn)題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的全部引用點(diǎn)。 堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑： 1）定長(zhǎng)塊管理 堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長(zhǎng)塊進(jìn)行?？紤]插入方便，可以把所歸還的塊插在 available所指的塊之前，然后 available指向新歸還的塊。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。 上述三種分配策略各有所長(zhǎng)。 圖 過(guò)程的活動(dòng)記錄 返回地址 實(shí)參 控制鏈 存取鏈 機(jī)器狀態(tài)信息 局部變量 臨時(shí)工作單元 ① 臨時(shí)工作單元 ：比如計(jì)算表達(dá)式過(guò)程中需存放中間結(jié)果用的臨時(shí)值單元。并不是所有語(yǔ)言需要該信息。 ⑦ 返回地址 ：保存該被調(diào)過(guò)程返回后的地址。 proc Q …… end Q。 若主程序調(diào)用了過(guò)程 Q， Q遞歸調(diào)用自己，在 Q過(guò)程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖 （ b）所示。 TOP? 臨時(shí)工作單元 局部簡(jiǎn)單變量 局部數(shù)組的內(nèi)情
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1