【正文】 業(yè)大學(xué) 理學(xué)院 鹿文鵬17Static Linkingn 在在 程序運行之前把各目標(biāo)模塊及庫函數(shù)鏈接程序運行之前把各目標(biāo)模塊及庫函數(shù)鏈接成一個完整的裝入模塊，以后不再拆開成一個完整的裝入模塊，以后不再拆開 。變換外部符號。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬19Loadtime Dynamic Linkingn 編譯的目標(biāo)模塊在編譯的目標(biāo)模塊在 裝入內(nèi)存時，邊裝入邊鏈裝入內(nèi)存時，邊裝入邊鏈接接 。靜。靜態(tài)鏈接。把對某些模塊的鏈接推遲到執(zhí)行時進行?？杉印€連續(xù)的內(nèi)存空間。劃分分區(qū)劃分分區(qū)內(nèi)存分配內(nèi)存分配齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬26n 1. 分區(qū)大小相等分區(qū)大小相等使所有的內(nèi)存分區(qū)大小相等。缺乏靈活性。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬27n 把分區(qū)按大小排隊，并建立一個把分區(qū)按大小排隊，并建立一個 分區(qū)使用表分區(qū)使用表。n 分配內(nèi)存時，檢索分區(qū)表分配內(nèi)存時，檢索分區(qū)表 ，如果存在大小合，如果存在大小合適且未分配的分區(qū)，就把其分配給相應(yīng)的程適且未分配的分區(qū)，就把其分配給相應(yīng)的程序，然后置序，然后置 “已分配已分配 ”標(biāo)志；若未找到大小足標(biāo)志；若未找到大小足夠的分區(qū)，則拒絕為之分配內(nèi)存。作業(yè) 2： 30K作業(yè) 1： 112K齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬29 動態(tài)分區(qū)分配動態(tài)分區(qū)分配n 動態(tài)分區(qū)分配是動態(tài)分區(qū)分配是 根據(jù)進程的實際需要，動態(tài)根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間地為之分配內(nèi)存空間 。記錄內(nèi)存的使用情況，為分配提供依據(jù)。的大小等數(shù)據(jù)項。向鏈。的次序鏈接。缺點：低址不斷被劃分，會產(chǎn)生大量的碎片；每次缺點：低址不斷被劃分，會產(chǎn)生大量的碎片；每次從低址開始查找，會增加查找可用空間的開銷。與請求的大小相等的內(nèi)存空間分配給作業(yè)。找到第一個空閑分區(qū)，比較其大小是否滿足要求。區(qū)的開銷，但會導(dǎo)致缺乏大的空閑分區(qū)。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。每次分配后所切割下來的剩余部分總是最小的，在存儲器中會留下許多這樣難以利用的小空閑區(qū)。最后，將分配區(qū)的首址返回給將分配區(qū)的首址返回給調(diào)用者。n 回收情況：回收情況：– A. 只有前鄰空閑區(qū)只有前鄰空閑區(qū)– B. 只有后鄰空閑區(qū)只有后鄰空閑區(qū)– C. 既有前鄰空閑區(qū)又有后鄰空閑區(qū)既有前鄰空閑區(qū)又有后鄰空閑區(qū)– D. 沒有鄰接空閑區(qū)沒有鄰接空閑區(qū)根據(jù)不同情況，根據(jù)不同情況， A、 B、 C有不同的合并策略。 n 經(jīng)過緊湊后的某些用戶經(jīng)過緊湊后的某些用戶程序在內(nèi)存中的位置發(fā)程序在內(nèi)存中的位置發(fā)生了變化生了變化 ，此時需對程，此時需對程序和數(shù)據(jù)的地址加以修序和數(shù)據(jù)的地址加以修改（變換），即改（變換），即 需要進需要進行重定位行重定位 。程序在執(zhí)行時，始地址。即可。消除內(nèi)存碎片，提高內(nèi)存利用率。不再轉(zhuǎn)換。動態(tài)重定位分區(qū)分配動態(tài)重定位分區(qū)分配 VS動態(tài)分區(qū)分配動態(tài)分區(qū)分配相對而言，前者具有緊湊功能，需要重定位相對而言，前者具有緊湊功能，需要重定位寄存器支持寄存器支持齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬50 對換對換 (Swapping)n n 把內(nèi)存中暫時不能運行的進程或暫時不用的程序和把內(nèi)存中暫時不能運行的進程或暫時不用的程序和數(shù)據(jù)，換出到外存，而把已具備運行條件的進程或數(shù)據(jù)，換出到外存，而把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，換入內(nèi)存，使其投入運進程所需要的程序和數(shù)據(jù)，換入內(nèi)存，使其投入運行行 (從而提高內(nèi)存利用率從而提高內(nèi)存利用率 )。目的是為了支持虛擬存儲系統(tǒng)。功能：對換空間的管理、進程的換出及換入。與內(nèi)存在動態(tài)分區(qū)分配方式中所使用情況。其分配算式中的內(nèi)存分配與回收方法雷同。作相應(yīng)修改。但須為此付出較大開銷。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬56 基本分頁存儲管理方式基本分頁存儲管理方式n 分段存儲管理方式分段存儲管理方式 基本單位是段基本單位是段n 分頁存儲管理方式分頁存儲管理方式 基本單位是頁基本單位是頁n 基本的分頁存儲管理方式基本的分頁存儲管理方式 ，要求把每個作業(yè)，要求把每個作業(yè)全部裝入內(nèi)存后方能運行。l 頁面太小，減少了內(nèi)存碎片，有利于提高內(nèi)頁面太小，減少了內(nèi)存碎片，有利于提高內(nèi)存利用率；但也會導(dǎo)致頁面過多，頁表過長存利用率；但也會導(dǎo)致頁面過多，頁表過長l 頁面太大，則會導(dǎo)致內(nèi)存碎片較多頁面太大，則會導(dǎo)致內(nèi)存碎片較多齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬59n 兩部分，兩部分， 前一部分為頁號前一部分為頁號 P (220)。n 系統(tǒng)為每個進程建立一張頁面映射表，簡稱系統(tǒng)為每個進程建立一張頁面映射表，簡稱頁表。n 頁表的作用是實現(xiàn)從頁號到物理塊號的地址頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射映射 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬62頁表的作用頁表的作用實現(xiàn)從頁號到物理塊號的地址映射實現(xiàn)從頁號到物理塊號的地址映射作業(yè)每頁 1K 內(nèi)存每塊 1K齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬63 地址變換機構(gòu)地址變換機構(gòu)n 功能：功能： 完成從邏輯地址（頁號完成從邏輯地址（頁號 +頁內(nèi)地址）頁內(nèi)地址）到物理地址的轉(zhuǎn)換。 借助于頁表完成借助于頁表完成。進程未執(zhí)行時，這兩個數(shù)據(jù)存于進程的程的 PCB中；執(zhí)行時，才將它們裝入中；執(zhí)行時，才將它們裝入 PTR。將之裝入物理地址的物理塊號部分。n 第一次是訪問內(nèi)存中的頁表，從中找到該頁的物理第一次是訪問內(nèi)存中的頁表，從中找到該頁的物理塊號，將此塊號與頁內(nèi)偏移量塊號，將此塊號與頁內(nèi)偏移量 W拼接以形成物理地拼接以形成物理地址；第二次訪問內(nèi)存時，才是從第一步所得地址中址；第二次訪問內(nèi)存時，才是從第一步所得地址中獲得所需數(shù)據(jù)獲得所需數(shù)據(jù) (或向此地址中寫入數(shù)據(jù)或向此地址中寫入數(shù)據(jù) )。（意味著這些頁表項不在存放在內(nèi)存中）內(nèi)存中）齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬702. 具有快表的地址變換機構(gòu)具有快表的地址變換機構(gòu)n 地址變換過程：地址變換過程：l 在在 CPU給出有效地址后，由地址變換機構(gòu)自動地將給出有效地址后，由地址變換機構(gòu)自動地將頁號頁號 P送入高速緩沖存儲器（快表），將此頁號與送入高速緩沖存儲器（快表），將此頁號與其中的頁號進行比較其中的頁號進行比較l 若有相匹配的頁號（在快表中），直接讀出其所對若有相匹配的頁號（在快表中），直接讀出其所對應(yīng)的物理塊號，并送物理地址寄存器中。找到后，把對應(yīng)的物理塊號送地址寄存器；也將此頁表項存把對應(yīng)的物理塊號送地址寄存器；也將此頁表項存入快表中。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬712. 具有快表的地址變換機構(gòu)具有快表的地址變換機構(gòu)齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬722. 具有快表的地址變換機構(gòu)具有快表的地址變換機構(gòu)n 由于成本，快表不可能做的很大，一般只存由于成本，快表不可能做的很大，一般只存放放 16~512個頁表項。從快表中能找到所需頁表項的機率，可達可達 90%以上。第二次才根據(jù)該地址存取頁面數(shù)據(jù)。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面對應(yīng)的物理塊號如下表：已調(diào)入內(nèi)存的頁面對應(yīng)的物理塊號如下表：頁號頁號 物理塊號物理塊號0 51 102 43 7則邏輯地址 0A5C（ H）所對應(yīng)的物理地址為 ： 125C齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬76練習(xí)練習(xí)v 0A5C＝＝ 0000,1010,0101,1100v 頁號為頁號為 2，對應(yīng)塊號為，對應(yīng)塊號為 4，有：，有：v 物理地址：物理地址： 0001， 0010,0101,1100v 即：即： 125C齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬77 兩級和多級頁表兩級和多級頁表n 引入：引入：計算機支持的邏輯地址空間非常大計算機支持的邏輯地址空間非常大 (232~264)，每個進程的每個進程的 頁表項也非常龐大，需占據(jù)大量的頁表項也非常龐大，需占據(jù)大量的連續(xù)內(nèi)存空間連續(xù)內(nèi)存空間 ，這顯然不現(xiàn)實。址。需要陸續(xù)調(diào)入其它的。應(yīng)的頁表分頁是否已調(diào)入內(nèi)存。顯然無法接受。存的利用率。用戶通常將作業(yè)按邏輯關(guān)系劃分為若干段。為實現(xiàn)段的共享，希望存儲管理能與用戶。在需調(diào)用某些段時才將其程序段裝入內(nèi)存。地址空間。邏輯地址由段號和段內(nèi)地址組成。 每個段在每個段在表中占有一個表項，記錄了該段在內(nèi)存中的表中占有一個表項，記錄了該段在內(nèi)存中的始址和段的長度始址和段的長度 。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬94n 與分頁系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時，每與分頁系統(tǒng)一樣，當(dāng)段表放在內(nèi)存中時，每訪問一個數(shù)據(jù)，都須訪問兩次內(nèi)存。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬95n 分頁是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用分頁是出于系統(tǒng)管理的需要，分段是出于用戶應(yīng)用的需要的需要– 一條指令或一個操作數(shù)可能會跨越兩個頁的分界處，而一條指令或一個操作數(shù)可能會跨越兩個頁的分界處，而不會跨越兩個段的分界處。n 邏輯地址表示：邏輯地址表示：– 分頁是一維地址空間，各個模塊在鏈接時組織成同一個分頁是一維地址空間，各個模塊在鏈接時組織成同一個地址空間；只利用一個標(biāo)記符即可表示一個地址。n 通常段比頁大，因而段表比頁表短，可以縮短查找通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。216。行修改。如果個用戶。 每個每個用戶進程的頁表中均需建立相應(yīng)的頁表項用戶進程的頁表中均需建立相應(yīng)的頁表項 。如：call 2148— 〉〉 call 2|100n 段式地址是二維的，兩個數(shù)字。如：call ac1|100 進程進程 1：： ac1=2；進程；進程 2：： ac1=4齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬102 段頁式存儲管理方式段頁式存儲管理方式n 分頁系統(tǒng)能有效地提高內(nèi)存利用率，而分段分頁系統(tǒng)能有效地提高內(nèi)存利用率，而分段系統(tǒng)則能很好地滿足用戶需要。n 段頁式系統(tǒng)中，地址結(jié)構(gòu)由段號、段內(nèi)頁號段頁式系統(tǒng)中，地址結(jié)構(gòu)由段號、段內(nèi)頁號及頁內(nèi)地址三部分組成。再將其與頁內(nèi)地址組合齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬105 d0和段號 s來求出該段所對應(yīng)的段表項在段表中的位置，從中得到該段的頁表始址 d1； d1和段內(nèi)頁號 P獲得對應(yīng)頁的頁表項位置，從中讀出該頁所在的物理塊號 P’； P’和頁內(nèi)地址 d來構(gòu)成物理地址。第一次訪問內(nèi)存中的段表，取得頁表始址；第第一次訪問內(nèi)存中的段表，取得頁表始址；第二次訪問內(nèi)存的頁表，取得該頁的物理塊號，二次訪問內(nèi)存的頁表，取得該頁的物理塊號，并與頁內(nèi)地址一起組成實際的物理地址；第三并與頁內(nèi)地址一起組成實際的物理地址；第三次從物理地址中取出指令或數(shù)據(jù)。齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬108 基本分段存儲管理方式基本分段存儲管理方式 小結(jié)小結(jié)n 分段存儲管理方式的引入分段存儲管理方式的引入 方便用戶方便用戶n 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理187。 段表始址段表始址 +段號段號 頁表始址頁表始址 與與 頁號頁號 結(jié)合結(jié)合 頁面對應(yīng)的物頁面對應(yīng)的物理塊號理塊號 與與 頁內(nèi)地址頁內(nèi)地址 結(jié)合結(jié)合 物理地址物理地址齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬109 虛擬存儲器的基本概念虛擬存儲器的基本概念n 連續(xù)分配方式、基本分頁、基本分段存儲管連續(xù)分配方式、基本分頁、基本分段存儲管理方式均需將一個作業(yè)全部裝入內(nèi)存后方能理方式均需將一個作業(yè)全部裝入內(nèi)存后方能運行，這將導(dǎo)致大作業(yè)無法運行。 并非全部程序和數(shù)據(jù)都需用到，一次裝入，浪費內(nèi)存并非全部程序和數(shù)據(jù)都需用到，一次裝入，浪費內(nèi)存– 駐留性：一旦裝入便一直駐留內(nèi)存直至作業(yè)結(jié)束駐留性：一旦裝入便一直駐留內(nèi)存直至作業(yè)結(jié)束187。程序在一段時間內(nèi)都。一段時間內(nèi)所訪問的地址可能集中空間局限性。某條指令或數(shù)據(jù)可能被再次執(zhí)行或時間局限性。一次性全部裝入，也沒必要長期駐留內(nèi)存。調(diào)入內(nèi)存。也可使內(nèi)存中同時裝入更多的進程并發(fā)執(zhí)行。實質(zhì)：以時間換空間，但時間犧牲不大。的。 只裝入部分頁面即可運行，可通過調(diào)只裝入部分頁面即可運行，可通過調(diào)頁和頁面置換功能，調(diào)入需要的頁面，同時將暫不頁和頁面置換功能，調(diào)入需要的頁面，同時將暫不需要的換出。只裝入部分段即可運行，可通過調(diào)段和段置換功能，調(diào)入需要的段，同時將暫不需要的調(diào)出。n 最本質(zhì)的特征是離散性最本質(zhì)的特征是離散性 ，在此基礎(chǔ)上又形成了多次，在此基礎(chǔ)上又形成了多次性和對換性，所表現(xiàn)出來的最重要的特征是性和對換性，所表現(xiàn)出來的最重要的特征是虛擬性虛擬性 . 齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬120 虛擬存儲器虛擬存儲器 小結(jié)小結(jié)n 虛擬存儲器的引入虛擬存儲器的引入– 大作業(yè)小內(nèi)存運行大作業(yè)小內(nèi)存運行 局部性原理局部性原理 – 具有請求調(diào)入功能和置換功能，能從邏輯上擴充內(nèi)存具有請求調(diào)入功能和置換功能，能從邏輯上擴充內(nèi)存n 虛擬存儲器的實現(xiàn)方法虛擬存儲器的實現(xiàn)方法– 分頁請求系統(tǒng)分頁請求系統(tǒng) 請求分段系統(tǒng)請求分段系統(tǒng)n 虛擬存儲器的特征虛擬存儲器的特征– 離散性離散性 多次性多次性 對換性對換性 虛擬性虛擬性齊魯工業(yè)大學(xué) 理學(xué)院 鹿文鵬121 請求分頁存儲管理方式請求分頁存儲管理方式n 建立在基本分頁基礎(chǔ)上，為了支持虛擬存儲建立在基本分頁基礎(chǔ)上，為了支持虛擬存儲器功能，而增加了請求調(diào)頁功能和頁面置換器功能，而增加了請求調(diào)頁功能和頁面置換功能。供程序（數(shù)據(jù)）換進換出時參考。 在在 指令執(zhí)行期間指令執(zhí)行期間 產(chǎn)生和處理中斷。187。如找到，修改其訪問位；對于頁。– 2)利用頁表項中的物理塊號和頁內(nèi)地址，形成物理地址，利用頁表項中的物理塊號和頁內(nèi)地址，形成物理地址，結(jié)束。如果在，則將該頁寫入快表（若快表已滿，則應(yīng)該先調(diào)出某個或某些頁表