目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織教材(已修改)
2025-03-01 02:26 本頁(yè)面
【正文】 第八章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織 ?第一節(jié) 數(shù)據(jù)空間的三種不同使用方法和管理方法 ?第二節(jié) 棧式存儲(chǔ)分配的實(shí)現(xiàn) ?第三節(jié) 參數(shù)傳遞 ?第四節(jié) 過(guò)程調(diào)用、過(guò)程進(jìn)入和過(guò)程返回 167。 數(shù)據(jù)空間的三種不同使用方法和管理方法 ?從邏輯上看，代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序 運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配 ?數(shù)據(jù)空間包括：用戶(hù)定義的各種類(lèi)型的數(shù)據(jù)對(duì)象（變量 和常量）所需的存儲(chǔ)空間，作為保留中間結(jié)果和傳遞參 數(shù)的臨時(shí)工作單元，調(diào)用過(guò)程時(shí)所需的連接單元，組織 輸入輸出所需的緩沖區(qū) ?運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧 區(qū)、堆區(qū) ?圖 ： ?代碼區(qū)用以存放目標(biāo)代碼，這是固定長(zhǎng)度的，即編譯時(shí) 能確定的 ?靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時(shí)能確定所占用空間的數(shù)據(jù) ?堆棧區(qū)用于可變數(shù)據(jù)以及管理過(guò)程活動(dòng)的控制信息 ?編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是 程序語(yǔ)言設(shè)計(jì)時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦 法的規(guī)定 ?在程序設(shè)計(jì)語(yǔ)言語(yǔ)義學(xué)中，使用 environment表示將一個(gè) 名字映射到一個(gè)存儲(chǔ)位置的函數(shù)， state表示存儲(chǔ)位置到 值的映射，如圖 ： ?數(shù)據(jù)空間的使用和管理方法分成三種： ?靜態(tài)存儲(chǔ)分配 ?棧式動(dòng)態(tài)存儲(chǔ)分配 ?堆式動(dòng)態(tài)存儲(chǔ)分配 一 .靜態(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ǔ)位置 ?如像 FORTRAN程序是段結(jié)構(gòu)的，如圖 ： ?圖 FORTRAN77的程序例子： 圖 ?圖 ： 二 .動(dòng)態(tài)存儲(chǔ)分配 ?如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許遞歸過(guò)程、可變數(shù)組或允許 用戶(hù)自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ) 管理技術(shù) 三 .棧式動(dòng)態(tài)存儲(chǔ)分配 ?這種分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧 四 .堆式動(dòng)態(tài)存儲(chǔ)分配 ?假設(shè)程序運(yùn)行時(shí)有一個(gè)大的存儲(chǔ)空間，每當(dāng)需要時(shí)就從 這片空間中借用一塊，不用時(shí)再退還，由于借還的時(shí)間 先后不一，經(jīng)一段運(yùn)行之后，程序運(yùn)行空間將被劃分成 許多塊，有些占用，有些空閑。那么當(dāng)運(yùn)行程序要求一 塊體積為 N的空間時(shí)，需要決定應(yīng)該從哪個(gè)空閑塊得到這 個(gè)空間 ?理論上講 ,應(yīng)該從比 N稍大一些的空閑塊中取出 N個(gè)單元， 以便使大的空閑塊派更大的用場(chǎng)，但實(shí)現(xiàn)難度很大 ?實(shí)際中常常采用的辦法：先遇到哪塊比 N大就從其中取出 N個(gè)單元 ?即使這樣，也會(huì)發(fā)生找不到一塊比 N大的空閑塊，但所有 空閑塊總和比 N大得多，這時(shí)，有的分配管理系統(tǒng)采用廢 品回收的辦法來(lái)應(yīng)付 167。 棧式存儲(chǔ)分配的實(shí)現(xiàn) ?過(guò)程的活動(dòng)記錄 AR(Activation Record)：是一段連續(xù)的存 儲(chǔ)區(qū)，用以存放過(guò)程的一次執(zhí)行所需要的信息，這些信 息如圖 ： ?臨時(shí)工作單元：如計(jì)算表達(dá)式過(guò)程存放的中間結(jié)果 ?局部變量：一個(gè)過(guò)程的局部變量 ?機(jī)器狀態(tài)信息：如程序計(jì)數(shù)器、寄存器的值 ?存取鏈：用以存取非局部變量 ?控制鏈：指向調(diào)用該過(guò)程的那個(gè)過(guò)程的活動(dòng)記錄 ?實(shí)參：由調(diào)用過(guò)程向該被調(diào)過(guò)程提供實(shí)參的值 (或地址 ) ?返回地址：保存該被調(diào)過(guò)程返回后的地址 一 .簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn) ?最簡(jiǎn)單的程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)如圖 ： ?例如，圖 ，若主程序調(diào)用了過(guò)程 Q， Q 又調(diào)用了 R,在 R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖 (a)所示： ?若主程序調(diào)用了過(guò)程 Q， Q遞歸調(diào)用自己，在 Q過(guò)程第 2次 進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖 (b)所示： ?若主程序先調(diào)用過(guò)程 Q，然后主程序接著調(diào)用 R，且 Q過(guò) 程沒(méi)有調(diào)用 Q和 R，這時(shí) Q和 R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)分 別如圖 (c)和 (d)所示： ?常常使用兩個(gè)指針指示棧最頂端的數(shù)據(jù)區(qū)： ?SP：總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn) ?TOP：始終指向已占用的棧頂單元 ?這種語(yǔ)言若含有可變數(shù)組，則其過(guò)程活動(dòng)記錄的內(nèi)容如 圖 ： ?圖 ，可以與圖 （ a）對(duì)照： 二 .嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn) ?Pascal語(yǔ)言程序結(jié)構(gòu)的特點(diǎn)是允許過(guò)程嵌套定義，如圖 ： ?圖 Pascal程序中過(guò)程定義的嵌套情況如下： ?sort ? readarray ? exchange ? quicksort ? partition ?假如過(guò)程 sort激活（調(diào)用）了過(guò)程 quicksort，這時(shí)存儲(chǔ)棧 中的情形如圖 ，其中在 quicksort過(guò)程活動(dòng)記錄 中有一存儲(chǔ)單元（用斜線描繪）用以記錄過(guò)程 quicksort 可以引用 sort中定義的變量 a和 x。也就是說(shuō)，為了解決對(duì) 非局部變量的存取問(wèn)題，必須設(shè)法跟蹤每個(gè)外層過(guò)程的 最新活動(dòng)記錄的位置 ?一種跟蹤方法是：在過(guò)程活動(dòng)記錄中增設(shè)存取鏈 ,指向包 含該過(guò)程的直接外層過(guò)程的最新活動(dòng)記錄的起始位置。 過(guò)程活動(dòng)記錄的內(nèi)容如圖 （ a）所示。圖 到的情況可用圖 （ b）所示： ?因?yàn)?PL/O的過(guò)程是無(wú)參過(guò)程， PL/O也無(wú)動(dòng)態(tài)數(shù)組，所以 它的過(guò)程活動(dòng)記錄的內(nèi)容如圖 ： ?再回到圖 ，如果該程序的某次執(zhí)行順序?yàn)椋? ?sort quicksort quicksort partition exchange? ?圖 exchange之后運(yùn)行棧的示意，僅 標(biāo)明存取鏈和控制鏈的值 ?另一種跟蹤方法是：每進(jìn)入一個(gè)過(guò)程后，在建立它的活 動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表 display ?嵌套層次：指過(guò)程定義的層數(shù)，始終假定主程序的層數(shù) 為 0，因此主程序稱(chēng)為 0層過(guò)程 ?計(jì)數(shù)過(guò)程的層數(shù)用一個(gè)計(jì)數(shù)器 Level，初值為 0，每遇到過(guò) 程說(shuō)明則增 1，過(guò)程說(shuō)明結(jié)束則減 1 ?display是一個(gè)指針數(shù)組 d，也可看做是一個(gè)小棧，自頂向 下每個(gè)單元依次存放著現(xiàn)行層，直接外層， ?? 直至
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1