操作系統(tǒng)原理-方敏-存儲管理

第五章存儲管理操作系統(tǒng)課程組內(nèi)容回顧死鎖的檢測永久性資源的死鎖檢測資源分配圖死鎖定理臨時資源的死鎖檢測死鎖的解除重新啟動撤銷進(jìn)程剝奪資源進(jìn)程回退2一、概述計算機(jī)的存儲體系結(jié)構(gòu)計算機(jī)為什么要使用存儲器？

——馮?諾依曼原理為什么要進(jìn)行存儲管理？存儲器一直以來都是較為珍貴的系統(tǒng)資源，需要合理使用。程序的邏輯空間和實際的物理空間不甚相同，需要進(jìn)行映射。3一、概述存儲結(jié)構(gòu)層次訪問速度頻度成本容量4一、概述存儲管理的目的使得用戶和用戶程序不涉及內(nèi)存物理的細(xì)節(jié)。自動完成用戶程序的裝入。提高內(nèi)存的利用率。解決內(nèi)存速度與CPU速度不匹配的問題。實現(xiàn)內(nèi)存共享。方便使用者，有效利用存儲資源，提高系統(tǒng)工作效率。5一、概述存儲管理的任務(wù)在現(xiàn)代操作系統(tǒng)中，存儲管理的主要任務(wù)有以下幾個方面：地址變換(地址再定位)存儲資源的分配和回收存儲共享和保護(hù)存儲器擴(kuò)充覆蓋技術(shù)交換技術(shù)6二、地址重定位基本概念程序符號地址/名地址編譯0101010010110101010101101010目標(biāo)文件邏輯地址/相對地址虛擬地址/程序地址加載內(nèi)存物理地址/絕對地址定義：當(dāng)程序被裝入內(nèi)存時，程序的邏輯地址被轉(zhuǎn)換成內(nèi)存的物理地址，這一過程稱為地址重定位(由內(nèi)存管理單元(MMU)完成)。7二、地址重定位常見的地址重定位技術(shù)絕對裝入(Absoluteloading)/固定地址再定位程序的地址再定位是在程序執(zhí)行之前被確定的，也就是在編譯連接時直接生成實際存儲器地址(物理地址)。在此，程序地址空間和內(nèi)存地址空間是一一對應(yīng)的。優(yōu)點：裝入過程簡單。缺點：與硬件的結(jié)構(gòu)過于密切，缺乏靈活性。0101010010110101010101101010目標(biāo)文件加載內(nèi)存邏輯地址物理地址一一對應(yīng)例如：單片機(jī)，MS-DOS中.com格式程序。8二、地址重定位可重定位裝入(RelocatableLoading)即指程序裝入內(nèi)存時，由于程序的邏輯地址和物理地址不一致，由邏輯地址到物理地址的映射過程。分類靜態(tài)再定位：指地址定位時修改程序的邏輯地址值，完成定位后，在程序的執(zhí)行期間地址將不再發(fā)生變化。特點：在程序執(zhí)行之前進(jìn)行地址再定位。優(yōu)點：無需硬件支持，容易實現(xiàn)。早期的操作系統(tǒng)中大多數(shù)都采用這種方法。缺點：必須分配連續(xù)的存儲區(qū)域；執(zhí)行期間不能擴(kuò)充存儲空間，也不能在內(nèi)存中移動，內(nèi)存利用率低，不便于共享。9二、地址重定位動態(tài)再定位：程序在裝入內(nèi)存時，不修改程序的邏輯地址值，程序在訪問物理內(nèi)存之前，再實時地將邏輯地址轉(zhuǎn)換成物理地址。BR:基址寄存器，存放程序的起始地址VR:變址寄存器，存放需要變換的邏輯地址10二、地址重定位優(yōu)點：程序在執(zhí)行期間可以換入和換出內(nèi)存，可以解決內(nèi)存緊張狀態(tài)；可以在內(nèi)存中移動——把內(nèi)存中的碎片集中起來，可以充分利用空間；不必給程序分配連續(xù)的內(nèi)存空間，可以較好的利用較小的內(nèi)存塊；若干用戶可以共享同一程序，實現(xiàn)共享。缺點：需要附加的硬件支持，實現(xiàn)存儲管理的軟件算法比較復(fù)雜。11三、分區(qū)存儲管理方案存儲管理方案分類從操作系統(tǒng)的發(fā)展歷史來看，存儲管理主要有以下幾種方案：分區(qū)存儲管理方案。要求連續(xù)分配存儲空間，且程序要一次性全部裝入內(nèi)存。簡單，但是有比較嚴(yán)重的內(nèi)碎塊和外碎塊。段式存儲管理方案。不要求連續(xù)分配存儲空間，段和段之間可以不連續(xù)，但程序需要一次性全部裝入內(nèi)存。有比較嚴(yán)重的外碎塊。頁式存儲管理方案。是一種不連續(xù)存儲管理方案，也需要一次性全部裝入內(nèi)存。在邏輯地址空間和物理地址空間都采用分頁的思想。缺點是每一個作業(yè)的最后一頁有內(nèi)碎塊。12三、分區(qū)存儲管理方案段頁式存儲管理方案。是一種不連續(xù)存儲方案，段式存儲管理和頁式存儲管理的結(jié)合?？朔思兎猪摵图兎侄未鎯芾硭枷氲娜秉c。交換技術(shù)和覆蓋技術(shù)。虛擬存儲管理方案。13三、分區(qū)存儲管理方案分區(qū)存儲管理：是一種連續(xù)分配存儲空間的管理方式。曾被廣泛地應(yīng)用于1960～1970年代的操作系統(tǒng)中。思想：把內(nèi)存分為一些大小相等或不等的分區(qū)(Partition)，裝入時每個應(yīng)用程序占用一個或幾個分區(qū)，操作系統(tǒng)占用其中一個分區(qū)。適用于多道程序系統(tǒng)和分時系統(tǒng)，支持多個程序并發(fā)執(zhí)行。分類單一連續(xù)分區(qū)存儲管理固定分區(qū)管理可變分區(qū)管理14三、分區(qū)存儲管理方案單一連續(xù)分區(qū)存儲管理特點：一次只能裝入一個程序，程序獨占整個用戶區(qū)，如果程序小于用戶區(qū)，則剩余的空間浪費，如果大于，則無法裝入。優(yōu)點：簡單，適用于單用戶、單任務(wù)的操作系統(tǒng)，不需要復(fù)雜的硬件支持。缺點：一個作業(yè)運行時要占用整個內(nèi)存地址空間，對內(nèi)存造成了很大的浪費，不支持大作業(yè)。15三、分區(qū)存儲管理方案固定分區(qū)管理支持多道程序技術(shù)實現(xiàn)方法：初始化內(nèi)存空間分區(qū)狀態(tài)表程序A(30K)程序A已分配內(nèi)碎片：指占用分區(qū)之內(nèi)未被利用的空間。16三、分區(qū)存儲管理方案特點：內(nèi)存中同時可以容納多道程序；程序必須連續(xù)存放，且要一次全部裝入。優(yōu)點：比單一連續(xù)分配方法，內(nèi)存的利用率提高了；可以支持多道程序；實現(xiàn)簡單，開銷小。缺點：作業(yè)必須預(yù)先能夠估計自己要占用多大的內(nèi)存空間，有時候這是難以做到的；存在內(nèi)碎片，造成存儲空間的浪費；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。17三、分區(qū)存儲管理方案可變分區(qū)(DynamicPartitioning)思想：預(yù)先不劃分內(nèi)存，當(dāng)作業(yè)需要時向系統(tǒng)申請，系統(tǒng)從其中挖出一塊給該作業(yè)，其大小等于作業(yè)所需內(nèi)存的大小，然后將剩下的部分再作為空表塊，給下一次分配使用。OSJob1Job2Job4Job3Q:如何管理這些空閑區(qū)？m_sizem_addrm_sizem_addrm_sizem_addrm_sizem_addr0…線性表格法m_sizem_addrm_sizem_addr鏈接法Job518三、分區(qū)存儲管理方案分區(qū)分配算法最先適應(yīng)算法(first-fit)分配方法：將所有的空閑分區(qū)按照地址遞增的順序排列，按照分區(qū)的先后次序，從頭開始查找，符合要求的第一個分區(qū)就是要找的分區(qū)。OSJob2Job4Job5m_sizem_addrm_sizem_addrm_sizem_addr0…19三、分區(qū)存儲管理方案釋放方法OSJob2Job4Job5規(guī)則：相鄰合并，否則插入20三、分區(qū)存儲管理方案優(yōu)點：分配策略簡單。盡可能利用存儲區(qū)低地址的空閑區(qū)，而在高地址部分保存較大的空閑區(qū)，容易滿足大作業(yè)。在釋放內(nèi)存分區(qū)時，如果有相鄰的空白區(qū)就進(jìn)行合并，使其成為一個較大的空白區(qū)。缺點：查找總是從表首開始，因此前面的空閑區(qū)往往被分割得很小時，查找次數(shù)增大。會產(chǎn)生外碎片(指占用的分區(qū)之間難以利用的空閑分區(qū))，這些碎片散布在存儲器的各處，不能集中使用，因而降低了存儲器的利用率。21三、分區(qū)存儲管理方案下次適應(yīng)算法(next-fit，循環(huán)最先適應(yīng)算法)分配方法：按分區(qū)的先后次序，從上次分配的分區(qū)起查找，到最后分區(qū)時再回到開頭，符合要求的第一個分區(qū)就是找到的分區(qū)。釋放方法：同于最先適應(yīng)算法。優(yōu)點：使空閑分區(qū)分布得更均勻，提高了分配查找的速度。缺點：較大的空閑分區(qū)不易保留。22三、分區(qū)存儲管理方案最佳適應(yīng)算法(best-fit)分配方法：將所有的空閑分區(qū)按照其容量遞增的順序排列，當(dāng)要求分配一個空白分區(qū)時，由小到大進(jìn)行查找，找到最合適的分配。釋放方法：在整個鏈表上搜索地址相鄰的空閑區(qū)，合并后，再插入到合適的位置。優(yōu)點：分配后所剩余的空白塊會最小，較大的空閑分區(qū)會被保留。平均，只要查找一半的表格便能找到最佳適應(yīng)的空白區(qū)；如果有一個空白區(qū)的容量正好滿足要求，則它必被選中。缺點：空白區(qū)一般不可能恰好滿足要求，在分配之后的剩余部分通常非常小，以致小到無法使用，會形成較多外碎片。23三、分區(qū)存儲管理方案最壞適應(yīng)算法(worst-fit)分配方法：與最佳適應(yīng)算法相反，將所有的空白分區(qū)按容量遞減的的順序排列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。釋放方法：同于最佳適應(yīng)算法(best-fit)優(yōu)點：分配的時候，只需查找一次，就可以成功，分配的算法很快。缺點：最后剩余的分區(qū)會越來越小，不會保留較大的空閑分區(qū)，無法運行大程序。24三、分區(qū)存儲管理方案可再定位式分區(qū)又稱浮動分區(qū)分配，是解決碎片問題的簡單而有效的辦法?；舅枷耄阂苿铀斜环峙涞姆謪^(qū)，使之成為一個連續(xù)區(qū)域，而留下一個較大的空白區(qū)?！翱繑n”或“緊湊”Q:程序地址的再定位？25提出原因四、頁式存儲管理分區(qū)存儲管理方案要求作業(yè)存儲時必須連續(xù)存放OSJob1Job3Job2Job4Job5頁式存儲管理方案解決作業(yè)不連續(xù)存放的問題26邏輯地址空間01K2K3K4K四、頁式存儲管理基本原理物理地址空間0100K101K102K103K104K105K106K107K108K109KOS012345678實頁/主頁0123虛頁：大小相同，常為2的整數(shù)冪。2031Q:如何記錄和管理這種映射關(guān)系？27四、頁式存儲管理頁面變換表(Pagemanagementtable)是一種特殊的數(shù)據(jù)結(jié)構(gòu)用途：記錄每一個作業(yè)的虛頁號到物理內(nèi)存中頁號之間的映射關(guān)系。每一個作業(yè)都擁有一個自己的頁面變換表。結(jié)構(gòu)：0虛頁號3實頁號162135…………Job1Job2總頁表…………起始地址長度…作業(yè)ID…SL頁表控制寄存器起始地址長度28四、頁式存儲管理物理地址空間OS012345678邏輯地址空間0123203101K2K3K4K0100K101K102K103K104K105K106K107K108K109K虛頁號實頁號03162135LOADA邏輯地址…………3頁號頁內(nèi)偏移量1001345…………3K310029四、頁式存儲管理地址變換過程Q:為了取出一個數(shù)據(jù)，系統(tǒng)需要訪問內(nèi)存幾次？30四、頁式存儲管理快表由一組聯(lián)想寄存器(TLB,TranslationLookasideBuffer)組成。聯(lián)想寄存器：一種按內(nèi)容進(jìn)行并行查找的快速寄存器，訪問速度比主存快得多。原理：31四、頁式存儲管理經(jīng)常要訪問的頁表表項。32四、頁式存儲管理空閑內(nèi)存頁的管理位示圖bitbyteQ:內(nèi)存大小：256M，每頁4K，位示圖有多大？33四、頁式存儲管理優(yōu)點沒有外碎片，每個內(nèi)碎片不超過頁大小。程序不必連續(xù)存放。主要缺點：程序要一次全部裝入內(nèi)存才能執(zhí)行。采用動態(tài)地址變換機(jī)構(gòu)會增加計算機(jī)的成本和降低處理機(jī)的速度。各種數(shù)據(jù)結(jié)構(gòu)(頁表，空閑頁表)要占用一定的內(nèi)存空間，而且系統(tǒng)要花費一定的時間來建立和管理這些表格。依然存在內(nèi)碎片。34五、段式存儲管理基本思想邏輯單位內(nèi)存管理采用可變分區(qū)動態(tài)分配法。段表總段表/系統(tǒng)段表…………起始地址長度…作業(yè)ID…35五、段式存儲管理地址變換過程段表控制寄存器36五、段式存儲管理優(yōu)點沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。便于實現(xiàn)共享，即允許若干個進(jìn)程共享一個或者多個段。37分頁式管理和分段式管理的比較五、段式存儲管理內(nèi)容頁式存儲管理段式存儲管理劃分依據(jù)系統(tǒng)管理需要用戶應(yīng)用需要頁/段大小各頁面大小相同段的大小不固定邏輯地址只有一個邏輯地址空間每個段一個獨立的邏輯地址空間頁表/段表頁面較多，頁表較長，查找費時段較少，段表較短，查找速度快碎片存在內(nèi)碎片存在外碎片內(nèi)存共享不支持支持存儲擴(kuò)充不支持不支持38六、段頁式存儲管理思想：邏輯地址空間物理地址空間...03K...0...5K03K邏輯地址格式?39六、段頁式存儲管理40六、段頁式存儲管理地址變換過程Q：為了獲得一條指令或者數(shù)據(jù)，需要訪問內(nèi)存幾次？41七、內(nèi)存擴(kuò)充技術(shù)提出原因在基本的存儲管理系統(tǒng)中，當(dāng)一個作業(yè)的程序地址空間大于內(nèi)存可以使用的空間時，該作業(yè)就不能裝入運行，并發(fā)運行進(jìn)程數(shù)受到了內(nèi)存空間的限制。內(nèi)存擴(kuò)充技術(shù)就是借助大容量的輔存在邏輯上實現(xiàn)內(nèi)存的擴(kuò)充，來解決內(nèi)存容量不足的問題。42程序(190K)七、內(nèi)存擴(kuò)充技術(shù)覆蓋技術(shù)(Overlay)目標(biāo)：在較小的可用內(nèi)存中運行較大的程序。原理A(20K)B(50K)C(30K)D(20K)E(40K)F(30K)覆蓋段43七、內(nèi)存擴(kuò)充技術(shù)覆蓋技術(shù)的優(yōu)缺點優(yōu)點有效利用內(nèi)存空間，提高系統(tǒng)的并發(fā)性。缺點覆蓋結(jié)構(gòu)需要程序員在程序編寫的時候精心安排，并用覆蓋描述語言描述，增加編程復(fù)雜度；從外存裝入覆蓋文件，是以時間延長來換取空間節(jié)省的；覆蓋區(qū)仍然存在著碎片。44內(nèi)存七、內(nèi)存擴(kuò)充技術(shù)交換技術(shù)(swapping)最早應(yīng)用于MIT開發(fā)的CTSS中。原理外存Job2Job3Job1Job445七、內(nèi)存擴(kuò)充技術(shù)交換技術(shù)的優(yōu)缺點優(yōu)點：增加并發(fā)運行的程序數(shù)目可以提供優(yōu)先級服務(wù)缺點：對換入和換出的控制增加處理機(jī)開銷；程序換入時的重定位問題。交換技術(shù)和覆蓋技術(shù)的區(qū)別內(nèi)容覆蓋技術(shù)交換技術(shù)適用情況作業(yè)內(nèi)部作業(yè)之間對程序結(jié)構(gòu)的影響有無46八、虛擬存儲技術(shù)虛擬存儲技術(shù)也是一種存儲擴(kuò)充技術(shù)?；A(chǔ)程序中不是每一條指令都會在程序的一次運行過程中執(zhí)行到。錯誤處理子程序條件語句(if...else...)程序中有的指令可能只執(zhí)行一次程序的初始化部分程序執(zhí)行的局部性原理：在一段時間內(nèi)，作業(yè)一般不會執(zhí)行到所有程序的指令，也不會存取絕大部分?jǐn)?shù)據(jù)，執(zhí)行的代碼和要存取的數(shù)據(jù)往往集中在某些區(qū)域中(例如一個循環(huán)、一個數(shù)組)。47八、虛擬存儲技術(shù)原理：在程序裝入時，不必一次將其全部讀入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的某些區(qū)域讀入到內(nèi)存，然后程序開始執(zhí)行。在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)據(jù)尚未在內(nèi)存，則由處理器通知操作系統(tǒng)將相應(yīng)的區(qū)域調(diào)入內(nèi)存，然后繼續(xù)執(zhí)行。帶來的好處程序的大小可以突破內(nèi)存容量限制，使得用戶感覺到系統(tǒng)好像提供了一個容量極大的“主存”。內(nèi)存中容納更多程序并發(fā)執(zhí)行。48八、虛擬存儲技術(shù)虛擬存儲技術(shù)分類虛擬頁式存儲管理純頁式管理＋請求調(diào)頁虛擬段式存儲管理純段式管理＋請求調(diào)段虛擬段頁式存儲管理虛擬頁式管理＋虛擬段式管理49邏輯地址空間物理地址空間九、虛擬頁式存儲技術(shù)工作原理012345678...…012CPUOS缺頁中斷缺頁中斷處理子程序3頁表Q：當(dāng)內(nèi)存中沒有空閑頁面時，如果還要調(diào)入一個新頁，如何處理？50九、虛擬頁式存儲技術(shù)頁面淘汰算法頁面置換算法決定在需要調(diào)入頁面時，選擇內(nèi)存中哪個物理頁面被置換。出發(fā)點：希望把未來不再使用的或者短時期內(nèi)較少使用的頁面調(diào)出。常見的頁面淘汰算法51九、虛擬頁式存儲技術(shù)最佳算法(OPT)思想：選擇從當(dāng)前時刻開始以后不在使用的頁面淘汰，如果沒有這類頁，則選擇離當(dāng)前頁最遠(yuǎn)位置上出現(xiàn)的頁面淘汰。優(yōu)點：使得頁面調(diào)入調(diào)出的次數(shù)達(dá)到最小，這是一種理想情況。缺點：實際上無法實現(xiàn)，因為系統(tǒng)無法預(yù)知未來頁面的訪問情況。因此只能用作理論上性能評價的標(biāo)準(zhǔn)。52九、虛擬頁式存儲技術(shù)先進(jìn)先出頁面淘汰算法(FIFO)思想：選擇最早調(diào)入內(nèi)存的頁面淘汰。出發(fā)點：近期調(diào)入的頁面被再次訪問的概率要大于早期調(diào)入的頁面。問題：事實上并非所有的時候都這樣。此時FIFO算法的性能較差。舉例：53九、虛擬頁式存儲技術(shù)設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，采用FIFO進(jìn)行頁面淘汰。缺頁中斷次數(shù)F=9，而缺頁率f=9/12=75%54九、虛擬頁式存儲技術(shù)Belady現(xiàn)象：可用頁面增大，缺頁率反而升高的現(xiàn)象。原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。主存容量M=4缺頁中斷次數(shù)F=10，而缺頁率f=9/12=83%55九、虛擬頁式存儲技術(shù)最近最少使用頁面淘汰算法(LRU,LeastRecentlyUsed)思想：每次選擇內(nèi)存中離當(dāng)前時刻最久未使用過的頁面淘汰。根據(jù)：局部性原理。實現(xiàn)方法硬件方法：一個特殊的棧：把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。每個頁面設(shè)立移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補(bǔ)0，于是寄存器數(shù)值最小的是最久未使用頁面。56九、虛擬頁式存儲技術(shù)軟件方法增加系統(tǒng)開銷57九、虛擬頁式存儲技術(shù)算法舉例 設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，采用LRU算法進(jìn)行頁面淘汰。缺頁中斷次數(shù)F=10，缺頁率f=10／12=83％58九、虛擬頁式存儲技術(shù)主存容量M=4缺頁中斷次數(shù)F=8，缺頁率f=8/12=67％結(jié)論：LRU算法不會出現(xiàn)Belady現(xiàn)象。59九、虛擬頁式存儲技術(shù)LRU算法的優(yōu)缺點優(yōu)點不會出現(xiàn)Belady現(xiàn)象性能較好，接近OPT算法缺點算法效率不高需要對整個頁表頻繁進(jìn)行維護(hù)。比較是算法的基本操作，當(dāng)頁面較多時會消耗大量時間。60九、虛擬頁式存儲技術(shù)最近未使用頁面淘汰算法(NRU,NotRecentlyUsed)第二次機(jī)會淘汰算法(SCR)頁面緩沖算法(PageBuffering)61九、虛擬頁式存儲技