第九章 運(yùn)行時(shí)存儲空間的組織

第九章運(yùn)行時(shí)存儲空間的組織本章內(nèi)容討論一個(gè)活動記錄中的數(shù)據(jù)安排程序執(zhí)行過程中，所有活動記錄的組織方式存儲器的組織與存儲分配的策略

名字存儲單元狀態(tài)值環(huán)境9.1目標(biāo)程序運(yùn)行時(shí)的活動9.1.1過程的活動活動

過程的一次執(zhí)行稱為過程的一次活動?；顒佑涗?過程的活動需要可執(zhí)行代碼和存放所需信息的存儲空間,后者稱為活動記錄?；顒拥纳嫫谶^程P一個(gè)活動的生存期，指的是從執(zhí)行該過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行P時(shí)調(diào)用其它過程花費(fèi)的時(shí)間。9.1目標(biāo)程序運(yùn)行時(shí)的活動9.1.2參數(shù)傳遞傳地址（callbyreference）把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。傳值（callbyvalue）把實(shí)在參數(shù)的值計(jì)算出來并存放在一個(gè)被調(diào)用段可以拿得到的地方。被調(diào)用段開始工作時(shí)，首先把這些值抄進(jìn)自己的形式單元中，然后就好像使用局部名一樣使用這些形式單元。9.1目標(biāo)程序運(yùn)行時(shí)的活動傳名（callbyname）：也稱為“換名”過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的位置，把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)在參數(shù)（文字替換）。9.2運(yùn)行時(shí)存儲器的劃分9.2.1運(yùn)行時(shí)存儲器的劃分編譯程序?yàn)榱耸顾幾g后得到的目標(biāo)程序能夠運(yùn)行，要從操作系統(tǒng)中獲得一塊存儲空間。對這塊提供運(yùn)行的空間應(yīng)該進(jìn)行劃分以便存放，其中包括生成的目標(biāo)代碼、數(shù)據(jù)對象和跟蹤過程活動的控制棧。目標(biāo)代碼的大小在編譯時(shí)可以確定，所以編譯程序可以把它放在一個(gè)靜態(tài)確定的區(qū)域。

運(yùn)行時(shí)存儲器的劃分：目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆9.2.2活動記錄（ActivationRecord）為了管理過程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲塊，這樣的一個(gè)連續(xù)存儲塊稱為活動記錄?；顒佑涗浺话惆缦聝?nèi)容：臨時(shí)單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址9.2.3存儲分配策略1靜態(tài)分配靜態(tài)分配策略在編譯時(shí)對所有數(shù)據(jù)對象分配固定的存儲單元，且在運(yùn)行時(shí)始終保持不變。2動態(tài)分配棧式動態(tài)分配策略在運(yùn)行時(shí)把存儲器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過程，它所需要的存儲空間就動態(tài)地分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動態(tài)分配策略在運(yùn)行時(shí)把存儲器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲空間的申請與歸還（回收），凡申請者從堆中分給一塊，凡釋放者退回給堆。9.2運(yùn)行時(shí)存儲器的劃分

影響存儲分配策略的語言特征

過程能否遞歸9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲塊能否在程序控制下動態(tài)地分配9.2運(yùn)行時(shí)存儲器的劃分影響存儲分配策略的語言特征

過程能否遞歸當(dāng)控制從過程的活動返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲塊能否在程序控制下動態(tài)地分配存儲塊是否必須顯式地釋放9.3靜態(tài)存儲分配靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲單元，不需要運(yùn)行時(shí)的任何支持。9.3靜態(tài)存儲分配靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲單元，不需要運(yùn)行時(shí)的任何支持。綁定的生存期是程序的整個(gè)運(yùn)行時(shí)間。9.3靜態(tài)存儲分配靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲單元，不需要運(yùn)行時(shí)的任何支持。綁定的生存期是程序的整個(gè)運(yùn)行時(shí)間。控制再次進(jìn)入該過程時(shí)，局部變量的值和控制上一次離開時(shí)的一樣。9.3靜態(tài)存儲分配靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲單元，不需要運(yùn)行時(shí)的任何支持。綁定的生存期是程序的整個(gè)運(yùn)行時(shí)間。控制再次進(jìn)入該過程時(shí)，局部變量的值和控制上一次離開時(shí)的一樣。每個(gè)活動記錄的大小是固定的。9.3靜態(tài)存儲分配靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲單元，不需要運(yùn)行時(shí)的任何支持。綁定的生存期是程序的整個(gè)運(yùn)行時(shí)間?？刂圃俅芜M(jìn)入該過程時(shí)，局部變量的值和控制上一次離開時(shí)的一樣。每個(gè)活動記錄的大小是固定的。過程調(diào)用時(shí)保存信息的地址在編譯時(shí)也是已知的。9.3靜態(tài)存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許9.3靜態(tài)存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時(shí)可以知道的9.3靜態(tài)存儲分配靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制，必須是在編譯時(shí)可以知道的數(shù)據(jù)結(jié)構(gòu)不能動態(tài)建立9.3靜態(tài)存儲分配

如果在編譯時(shí)就能夠確定一個(gè)程序在運(yùn)行時(shí)所需的存儲空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。存儲空間的這種分配方法叫做靜態(tài)分配。FORTRAN程序的特點(diǎn)是：不允許過程的遞歸性；每個(gè)數(shù)據(jù)名所需的存儲空間大小都是常量（即不許含可變體積的數(shù)據(jù)，如可變數(shù)組）；并且所有數(shù)據(jù)名的性質(zhì)是完全確定的（不允許那種需在運(yùn)行時(shí)動態(tài)確定其性質(zhì)的名字）。9.4簡單的棧式存儲分配

這種語言沒有分程序結(jié)構(gòu)，過程定義不許嵌套，但允許過程的遞歸調(diào)用。C就是這樣的一種語言。9.4.1C的活動記錄C的活動記錄有以下四個(gè)項(xiàng)目?！みB接數(shù)據(jù)，有兩個(gè)：（1）老SP值，即前一活動記錄的地址；（2）返回地址?！?shù)個(gè)數(shù)?！ば问絾卧ù娣艑?shí)在參數(shù)的值或地址）?！み^程的局部變量、數(shù)組內(nèi)情向量和臨時(shí)工作單元。9.4.2C的過程調(diào)用、過程進(jìn)入、數(shù)組空間分配和過程返回9.5嵌套過程語言的棧式實(shí)現(xiàn)嵌套層次：如過程Q是在層數(shù)為i的過程P內(nèi)定義，并且P是包圍Q的最小過程，那么Q的層數(shù)就為i＋1。sort readarray exchange quicksort partition 9.5嵌套過程語言的棧式實(shí)現(xiàn)過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 39.5嵌套過程語言的棧式實(shí)現(xiàn)過程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 3變量的嵌套深度：它的聲明所在過程的嵌套深度作為該名字的嵌套深度9.5嵌套過程語言的棧式實(shí)現(xiàn)棧式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持9.5嵌套過程語言的棧式實(shí)現(xiàn)棧式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動活得更長，此時(shí)活動樹不能正確描繪程序的控制流9.5嵌套過程語言的棧式實(shí)現(xiàn)棧式分配棧式分配策略在下列情況下行不通：過程活動停止后，局部名字的值還必須維持被調(diào)用者的活動比調(diào)用者的活動活得更長，此時(shí)活動樹不能正確描繪程序的控制流不遵守棧式規(guī)則的有Pascal語言和C語言的動態(tài)變量Java禁止程序員自己釋放空間9.6堆式動態(tài)存儲分配堆式的動態(tài)存儲如果一個(gè)程序語言允許用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過程而且有進(jìn)程（process）的程序結(jié)構(gòu)，那么，由于空間的使用未必服從“先請后還，后請先還”的原則，因此，棧式的動態(tài)分配方案就不適用了。在這種情況下通常使用一種稱之為堆式的動態(tài)存儲分配方案。9.6堆式動態(tài)存儲分配9.6.1堆式動態(tài)存儲分配的實(shí)現(xiàn)1.定長塊管理堆式存儲分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表9.6堆式動態(tài)存儲分配2.變長塊管理（1）首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊，就進(jìn)行分配。（2）最優(yōu)滿足法：將空閑塊鏈表中一個(gè)不小于申請塊且最接近于申請塊的空閑塊分配給用戶，則系統(tǒng)在分配前首先要對空閑塊鏈表從頭至尾掃描一遍，然后從中找出一塊不小于申請塊且最接近于申請塊的空閑塊分配。（3）最差滿足法：將空閑塊表中不小于申請塊且是最大的空閑的一部分分配給用戶。9.6堆式動態(tài)存儲分配9.6.2隱式存儲回收隱式存儲回收要求用戶程序和支持運(yùn)行的回收子程序并行工作，因?yàn)榛厥兆映绦蛐枰婪峙浣o用戶程序的存儲塊何時(shí)不再使用。例題1一個(gè)C語言程序及其在X86/Linux操作系統(tǒng)上的編譯結(jié)果如下。根據(jù)所生成的匯編程序來解釋程序中四個(gè)變量的存儲分配、作用域、生存期和置初值方式等方面的區(qū)別。staticlongaa=10;shortbb=20;func(){ staticlongcc=30;shortdd=40;}例題1.data | .align4.align4 | .type cc.2,@object .typeaa,@object | .size cc.2,4 .sizeaa,4 |cc.2:aa: | .long30 .long10 |.text.globlbb | .align4 .align2 |.globlfunc

.typebb,@object |func: .sizebb,2 | ...bb: | movw$40,-2(%ebp) .value20 | ...例題2main(){ char*cp1,*cp2;

cp1="12345"; cp2="abcdefghij"; strcpy(cp1,cp2); printf("cp1=%s\ncp2=%s\n",cp1,cp2);}運(yùn)行結(jié)果是： cp1=abcdefghij cp2=ghij為什么cp2所指的串被修改了？例題2因?yàn)槌Ａ看?2345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前： 12345\0abcdefghij\0

cp1 cp2例題2因?yàn)槌Ａ看?2345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前： 12345\0abcdefghij\0

cp1 cp2執(zhí)行后：

abcdefghij\0fghij\0

cp1 cp2例題2因?yàn)槌Ａ看?2345”和“abcdefghij”連續(xù)分配在常數(shù)區(qū)執(zhí)行前： 12345\0abcdefghij\0

cp1 cp2執(zhí)行后：

abcdefghij\0fghij\0

cp1 cp2現(xiàn)在的編譯器大都把程序中的串常量單獨(dú)存放在一個(gè)只讀的數(shù)據(jù)段中。例題3 下面的程序運(yùn)行時(shí)輸出3個(gè)整數(shù)。試從運(yùn)行環(huán)境和printf的實(shí)現(xiàn)來分析，為什么此程序會有3個(gè)整數(shù)輸出？

main(){

printf(“%d,%d,%d\n”);}例題4func(i,j,f,e)shorti,j;floatf,e;{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main(){shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八進(jìn)制數(shù)）Addressofi1,j1,f1,e1=…26,…24,…20,…14

例題4func(i,j,f,e) Sizesofshort,int,long,float,

shorti,j;floatf,e; double=2,4,4,4,8

{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main(){ shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八進(jìn)制數(shù)）Addressofi1,j1,f1,e1=…26,…24,…20,…14例題4func(i,j,f,e) Sizesofshort,int,long,float,

shorti,j;floatf,e; double=2,4,4,4,8

{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main() 為什么4個(gè)形式參數(shù)i,j,f,e的地址{ 間隔和它們類型的大小不一致

shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八進(jìn)制數(shù)）Addressofi1,j1,f1,e1=…26,…24,…20,…14例題4C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。

例題4C語言編譯是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。

但是對于形式參數(shù)和實(shí)在參數(shù)是不同的整型，或者是不同的實(shí)型，編譯器則試圖保證目標(biāo)代碼運(yùn)行時(shí)能得到正確的結(jié)果，條件是，當(dāng)需要把高級別類型數(shù)據(jù)向低級別類型數(shù)據(jù)轉(zhuǎn)換時(shí)，不出現(xiàn)溢出。

例題4C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。

但是對于形式參數(shù)和實(shí)在參數(shù)是不同的整型，或者是不同的實(shí)型，編譯器則試圖保證目標(biāo)代碼運(yùn)行時(shí)能得到正確的結(jié)果，條件是，當(dāng)需要把高級別類型數(shù)據(jù)向低級別類型數(shù)據(jù)轉(zhuǎn)換時(shí)，不出現(xiàn)溢出。

當(dāng)整型或?qū)嵭蛿?shù)據(jù)作為實(shí)在參數(shù)時(shí)，將它們分別提升到long和double類型的數(shù)據(jù)再傳遞到被調(diào)用函數(shù)例題4C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。

但是對于形式參數(shù)和實(shí)在參數(shù)是不同的整型，或者是不同的實(shí)型，編譯器則試圖保證目標(biāo)代碼運(yùn)行時(shí)能得到正確的結(jié)果，條件是，當(dāng)需要把高級別類型數(shù)據(jù)向低級別類型數(shù)據(jù)轉(zhuǎn)換時(shí)，不出現(xiàn)溢出。

當(dāng)整型或?qū)嵭蛿?shù)據(jù)作為實(shí)在參數(shù)時(shí)，將它們分別提升到long和double類型的數(shù)據(jù)再傳遞到被調(diào)用函數(shù)被調(diào)用函數(shù)根據(jù)形式參數(shù)所聲明的類型，決定是否要將實(shí)在參數(shù)向低級別類型轉(zhuǎn)換。例題4低地址放高位高地址放低位shortlong長整型和短整型floatdoublee雙精度型和浮點(diǎn)型例題4e，8個(gè)字節(jié)在main函數(shù)中參數(shù)壓棧時(shí)的觀點(diǎn)在fun