目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織概論(ppt54頁)(已修改)
2025-03-01 13:07 本頁面
【正文】 第 10章 目標(biāo)程序 運(yùn)行時(shí)的存儲(chǔ)組織 數(shù)據(jù)空間的三種不同使用方法和管理方法 棧式存儲(chǔ)分配的實(shí)現(xiàn) 參數(shù)傳遞 從邏輯上看，在代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的配置和數(shù)據(jù)空間的分配。 數(shù)據(jù)空間 應(yīng)包括： ? 用戶定義的各種類型的數(shù)據(jù)對(duì)象（變量和常數(shù)）所 需的存儲(chǔ)空間； ? 作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元； ? 調(diào)用過程時(shí)所需的連接單元； ? 組織輸入 /輸出所需的緩沖區(qū)。 目標(biāo)代碼所占用空間 的大小在編譯時(shí)能確定。有些數(shù)據(jù)對(duì)象所占用的空間也能在編譯時(shí)確定，其地址可以編譯進(jìn)目標(biāo)代碼中。而有些數(shù)據(jù)對(duì)象具有可變體積和待分配性質(zhì)，無法在編譯時(shí)確定存儲(chǔ)空間的位置。 因此運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖 。 目標(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)起來，該存儲(chǔ)位置用以保存名字的值。 ?編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是程序語言設(shè)計(jì)時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。 ?決定存儲(chǔ)管理復(fù)雜程度的因素 源語言本身，比如源語言允許的數(shù)據(jù)類型有多少？語言中允許的數(shù)據(jù)項(xiàng)是靜態(tài)確定還是動(dòng)態(tài)確定？程序結(jié)構(gòu)有什么特點(diǎn)，是段結(jié)構(gòu)還是分程序結(jié)構(gòu)？過程定義是否允許嵌套？等等。 ?源語言的結(jié)構(gòu)特點(diǎn)、源語言的數(shù)據(jù)類型、源語言中決定名字作用域的規(guī)則等因素影響存儲(chǔ)空間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分配的基本策略。 數(shù)據(jù)空間的三種不同使用方法和管理方法 數(shù)據(jù)空間的使用和管理方法 : 簡(jiǎn)單的棧式分配方案 嵌套過程的棧式分配方案 分程序結(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ǔ)分配。 如 C中的靜態(tài)變量，外部變量等。 動(dòng)態(tài)存儲(chǔ)分配 如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、允許動(dòng)態(tài)的申請(qǐng)建立和撤消存儲(chǔ)空間、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。 因?yàn)閷?duì)于這種程序在編譯時(shí)無法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。 若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱為可變（動(dòng)態(tài)）數(shù)組。 棧式動(dòng)態(tài)存儲(chǔ)分配 這種分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。 在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。 過程所需的數(shù)據(jù)空間包括兩部分： ① 生存期在本過程這次活動(dòng)中的數(shù)據(jù)對(duì)象； ② 用以管理過程活動(dòng)的記錄信息 。 棧式動(dòng)態(tài)存儲(chǔ)分配策略適用于 PASCAL， C，ALGOL之類具有遞歸結(jié)構(gòu)的語言的實(shí)現(xiàn)。 . 堆式動(dòng)態(tài)存儲(chǔ)分配 如果一個(gè)程序語言提供用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制，或者不僅有過程而且有進(jìn)程的程序結(jié)構(gòu)，一般用堆式的動(dòng)態(tài)存儲(chǔ)分配方案。如Ｃ ++中的 new， delete， PASCAL的 new，等機(jī)制 。 此時(shí) ,空間的使用未必服從“先申請(qǐng)后釋放，后申請(qǐng)先釋放”的原則，那么棧式的動(dòng)態(tài)分配方案就不適用了。通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配方案。 這種分配方式的存儲(chǔ)管理技術(shù)甚為復(fù)雜，我們這里舉出這種分配方法必須考慮的幾個(gè)問題。 堆式的動(dòng)態(tài)存儲(chǔ)分配策略 : 當(dāng)運(yùn)行程序要求一塊體積為 N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？ 理論上說，應(yīng)從比 N稍大一點(diǎn)的一個(gè)空閑塊中取出 N個(gè)單元，以便使大的空閑塊派更大的用場(chǎng)。但這種做法較麻煩。 因此，常常仍采用“先碰上哪塊比 N大就從其中分出 N個(gè)單元”的原則。但不論采用什么原則，整個(gè)大存區(qū)在一定時(shí)間之后必然會(huì)變成零碎不堪。 總有一個(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體積為 N的空間，但發(fā)現(xiàn)沒有比 N大的空閑塊了，然而所有空閑塊的總和卻要比 N大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是一個(gè)比前面的問題難得多的問題。 解決辦法似乎很簡(jiǎn)單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空間。 這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的全部引用點(diǎn)。 堆式的動(dòng)態(tài)存儲(chǔ)分配策略 : 另外，如果運(yùn)行程序要求一塊體積為 N的空間，但所有空閑塊的總和也不夠 N，那又應(yīng)怎么辦呢？ 有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放在占用塊，或者那些行程序目前很少使用的占用塊，把這此占用塊收回來，重新分配。 但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？ 要使用廢品回收技術(shù)，除了在語言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不能實(shí)現(xiàn)。 堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑： 1）定長塊管理 堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè) 鏈表 ，用指針 available指向鏈表中的第一塊。 分配時(shí)每次都分配指針 available所指的塊，然后 available指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表?？紤]插入方便，可以把所歸還的塊插在 available
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1