第四章存儲管理

操作系統(tǒng)原理第四章存儲管理1整理課件簡介

操作系統(tǒng)中的存儲管理主要是指對主存的管理。

主存即內(nèi)存，是指處理機可以直接存取指令和數(shù)據(jù)的存儲器。主存是現(xiàn)代操作系統(tǒng)進行操作的中心，是計算機系統(tǒng)中的一種重要資源。作為系統(tǒng)資源管理程序的操作系統(tǒng)，必須對主存施以有效、精心的管理。

多道程序設(shè)計技術(shù)出現(xiàn)后，對存儲管理提出了更高要求。一方面，要使主存得到充分、有效的利用；另一方面要為用戶提供方便的使用環(huán)境。2整理課件4.1存儲器管理的根本概念4.1.1存儲管理研究的課題計算機的存儲設(shè)備可以分為三個層次：高速昂貴而易變〔斷電后信息喪失〕的高速緩存和存放器，數(shù)量很少；速度快，價格高且易變的主存儲器(RAM)；速度較低，價格低廉，但不易變的輔存如軟、硬磁盤、光盤等。3整理課件4.1存儲器管理的根本概念目前關(guān)于存儲管理的主要研究課題歸納為四個方面存儲分配問題：重點是研究存儲共享和各種分配算法；記住主存各個位置的狀態(tài)，哪些空間已分配，哪些空間設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄分配。按一定的策略為用戶作業(yè)分配內(nèi)存。實施分配，當用戶作業(yè)申請時，按需分配，修改相應(yīng)的表格。回收內(nèi)存，作業(yè)完成，退出主存，修改相應(yīng)的分配表格。地址再定位問題：研究各種地址變換機構(gòu)，以及靜態(tài)和動態(tài)再定位方法。地址重定位、地址映射。4整理課件4.1存儲器管理的根本概念存儲保護問題：研究保護各類程序、數(shù)據(jù)區(qū)的方法。為多個程序共享內(nèi)存提供保障，使在內(nèi)存中的各道程序，只能訪問它自己的區(qū)域，防止各道程序間相互干擾，特別是當一道程序發(fā)生錯誤時，不致于影響其他程序的運行。通常由硬件完成保護功能，由軟件輔助實現(xiàn)。存儲擴充問題：主要研究虛擬存儲器問題及其各種調(diào)度算法。一方面需要提高主存利用率，共享主存；另一方面為用戶提供一個遠遠大于主存的地址空間。5整理課件4.1存儲器管理的根本概念4.1.2地址再定位1.地址空間和存儲空間地址空間〔邏輯空間〕：一個目標程序所限定的地址范圍，成為該作業(yè)的地址空間。是虛的概念。相對地址〔邏輯地址〕：地址空間的地址都是相對于起始地址0為基準量的，稱為相對地址。絕對地址〔物理地址〕：指存儲控制部件能識別存儲單元的號。存儲空間〔物理空間〕：所有內(nèi)存中實際的物理存儲單元的集合。存儲空間是一個“實〞的物體。6整理課件4.1存儲器管理的根本概念名空間符號指令數(shù)據(jù)說明I/O說明地址空間目標程序（裝配模塊）存儲空間0x01MB74.1存儲器管理的根本概念2.地址的再定位

一個邏輯地址空間的程序裝入到物理地址空間的時候，由于兩個空間不一致，需要進行地址變換，或稱地址映射，即地址的再定位。地址再定位有靜態(tài)再定位和動態(tài)再定位兩種。靜態(tài)再定位是在程序執(zhí)行之前進行地址再定位。通常由裝配程序完成。8整理課件4.1存儲器管理的根本概念例現(xiàn)有一個作業(yè)A，它需要20K空間，兩次運行分別被裝入主存中的不同地址。A作業(yè)的地址空間0K20K操作系統(tǒng)操作系統(tǒng)主存100K120KA作業(yè)的地址空間0K20K主存120K140K94.1存儲器管理的根本概念優(yōu)點：容易實現(xiàn)，無需硬件支持，只要求程序本身時可再定位的。缺點：程序經(jīng)地址再定位后就不能再移動了，因而不能重新分配內(nèi)存，不利于內(nèi)存的有效利用；程序在存儲空間中只能連續(xù)分配，不能分布在內(nèi)存的不同區(qū)域；假設(shè)干用戶很難共享內(nèi)存中的同一程序，如假設(shè)共享同一程序，那么各用戶必須使用自己的副本。10整理課件4.1存儲器管理的根本概念動態(tài)再定位是在程序執(zhí)行期間，在每次存儲訪問之前進行的。作業(yè)在存儲空間中的位置是裝入時確定的，但在運行時允許“搬家〞和附加存儲空間。11整理課件4.1存儲器管理的根本概念優(yōu)點：在執(zhí)行過程中，用戶程序在內(nèi)存中可以移動，這有利于內(nèi)存的充分利用；程序不必連續(xù)存放在內(nèi)存中，可以分散在內(nèi)存的假設(shè)干個不同區(qū)域，這只需增加幾對基址－限長存放器，每對存放器對應(yīng)一個區(qū)域；假設(shè)干用戶可以共享同一程序。缺點：需要附加的硬件支持，實現(xiàn)存儲管理的軟件算法比較復(fù)雜。12整理課件4.1存儲器管理的根本概念4.1.3虛擬存儲器概念的引入虛擬存儲器的提出VirtualStore〔VS〕1.解決小內(nèi)存運行大作業(yè)問題連續(xù)區(qū)，分區(qū)的管理，分頁式管理中，如作業(yè)長大于內(nèi)存的用戶區(qū)長，將無法運行該作業(yè)，因為作業(yè)一次全裝入主存。在多道環(huán)境下，要求內(nèi)存放入多個作業(yè)，問題更為突出。2.用戶擴大內(nèi)存的要求，以便有效地支持多道系統(tǒng)和大型程序的需要由于內(nèi)存硬件價格貴，因此利用VS，可以從邏輯上擴充主存。13整理課件4.1存儲器管理的根本概念3.程序的訪問局部性時間的局部性：剛剛訪問的局部，可能馬上還要訪問。例如程序中有大量的循環(huán)語句?？臻g的局部性：被訪問局部的鄰近區(qū)域，可能馬上就要被訪問〔程序的順序性〕。程序段的互斥性：不是每個程序段在執(zhí)行時同時都運行到。14整理課件4.1存儲器管理的根本概念虛擬存儲器的定義讓用戶編程使用的地址范圍決定的虛存空間，遠遠大于實際的內(nèi)存空間。對用戶而言，它是一個比主存大得多的地址空間，可以按它來編程，而不必考慮主存的缺乏。對OS而言，是用各種表格機構(gòu)構(gòu)造的一個虛擬存儲器。15整理課件4.1存儲器管理的根本概念VS的根本實現(xiàn)原理利用表格為用戶構(gòu)造一個虛擬空間，作為實現(xiàn)VS的機構(gòu)。利用大容量的外存，存放進入VS中的信息,是VS的硬件根底。主存作為VS中的程序和數(shù)據(jù)得以運行的緩沖區(qū)。在內(nèi)、外存之間信息調(diào)度。硬件提供動態(tài)地址轉(zhuǎn)換機構(gòu)。注VS的容量由虛擬地址結(jié)構(gòu)決定，也受外存容量的限制。16整理課件4.2早期的存儲管理4.2.1單一連續(xù)分配每個進程所需的空間分配到主存一塊連續(xù)區(qū)。早期的單道成批處理或個人微機OS或?qū)Ｓ肙S多用。目的：解決成批作業(yè)自動接續(xù)問題，不提供共享主存功能。分配方法將主存分為二塊連續(xù)區(qū)：系統(tǒng)區(qū)——存放OS和用戶區(qū)— —存放用戶程序；系統(tǒng)設(shè)置一個界限存放器〔Fenceregister〕指出OS區(qū)和用戶區(qū)的界限，當用戶程序地址小于邊界地址時，產(chǎn) 生越界中斷；由裝入程序每次裝入一個作業(yè)到用戶區(qū)，剩余的用戶區(qū)空間浪費掉；采用靜態(tài)重定位。17整理課件4.2早期的存儲管理特點單道運行，獨占資源，浪費了內(nèi)存碎片，資源利用率低。簡單，OS可以小到1KB〔一般幾十KB〕，不需復(fù)雜的硬、軟件支持。缺少靈活性，大作業(yè)不能在小內(nèi)存運行。操作系統(tǒng)32KB作業(yè)64KB未用160KB分配給用戶作業(yè)的空間18整理課件4.2早期的存儲管理4.2.2分區(qū)分配分區(qū)分配是能滿足多道程序設(shè)計需要的一種最簡單的存儲管理技術(shù)，分區(qū)管理法也稱界地址存儲管理法。通常，按照分區(qū)的劃分方式，又可分為固定式分區(qū)、可變式分區(qū)、可再定位式分區(qū)和多重分區(qū)。1.固定式分區(qū)法思想：預(yù)先將主存用戶區(qū)劃成大小不等假設(shè)干分區(qū)；分區(qū)的個數(shù)和長度保持固定，每個分區(qū)只裝入一個作業(yè)。分區(qū)的個數(shù)等于作業(yè)的道數(shù)。固定分區(qū)是實現(xiàn)多道程序設(shè)計最簡單的一種技術(shù)。19整理課件4.2早期的存儲管理分區(qū)的分配和釋放作業(yè)都必須規(guī)定最大的存儲量；OS設(shè)立一張分區(qū)說明表，指明塊號、位置、長度和狀態(tài)；裝入一個作業(yè)時，由再定位裝入程序按作業(yè)的內(nèi)存需求量在表中找一個夠大的未分配分區(qū)，用靜態(tài)再定位方式裝入作業(yè)，修改狀態(tài)標志；回收時，將分區(qū)狀態(tài)置0，即釋放。20整理課件4.2早期的存儲管理分區(qū)號容量位置狀態(tài)18KB312KB在使用232KB320KB在使用332KB352KB未用4120KB384KB未用5520KB504KB在使用操作系統(tǒng)312KB8KB32KB32KB120KB520KB0312KB320KB352KB384KB504KB21整理課件4.2早期的存儲管理存儲保護設(shè)立上界存放器和下界存放器分別存放當前運行作業(yè)的分區(qū)最小絕對地址和最大絕對地址；當訪問的地址小于上界或下界時產(chǎn)生越界中斷。優(yōu)點可以共享主存，提高主存利用率。程序一次性裝入主存。由于靜態(tài)再定位，程序不能移動。22整理課件4.2早期的存儲管理缺點分區(qū)內(nèi)部碎片大，浪費內(nèi)存。 例現(xiàn)有四個作業(yè)，其作業(yè)長度分別為1K，9K，23K，33K，總計長度為66K，為它們分配分區(qū)長分別為4K，12K，28K，44K，共占88K，浪費了22K。作業(yè)長度大于分區(qū)最大長度，無法分配。這種方式適于能掌握作業(yè)大小、數(shù)量的系統(tǒng)及中型機以上的OS，如IBMOS/MFT〔任務(wù)數(shù)固定的多道程序設(shè)計系統(tǒng)〕。23整理課件4.2早期的存儲管理2.可變式分區(qū)法

為了解決固定分區(qū)的內(nèi)部碎片問題，在固定分區(qū)管理技術(shù)上設(shè)計了可變分區(qū)管理，適用于多道系統(tǒng)?？勺兪椒謪^(qū)法也就是動態(tài)劃分存儲器的分區(qū)方法，它是在作業(yè)裝入和處理過程中建立的分區(qū)，并且要使分區(qū)的容量能正好適應(yīng)作業(yè)大小。在作業(yè)進入系統(tǒng)前，根據(jù)作業(yè)的大小來申請所需存儲容量，然后由系統(tǒng)實施分配。系統(tǒng)為了管理主存分區(qū)分配情況，需建立兩張表，分別登記已分配區(qū)和未分配區(qū)的分區(qū)容量、位置和狀態(tài)信息。24整理課件4.2早期的存儲管理可變分區(qū)的分配思想新作業(yè)裝入主存時，找一個足夠大的空閑區(qū)，按作業(yè)長度劃分，剩余仍為一個小空閑區(qū)；釋放時，與相鄰的空閑區(qū)合并。OS作業(yè)1（8KB）作業(yè)2（32KB）作業(yè)4（24KB）作業(yè)3（120KB）作業(yè)5（128KB）作業(yè)6（256KB）0312KB320KB352KB376KB384KB504KB632KB888KB1024KBOS作業(yè)1（8KB）作業(yè)2（32KB）作業(yè)3（120KB）0312KB320KB352KB384KB504KB1024KBOS作業(yè)1（8KB）作業(yè)4（24KB）作業(yè)5（128KB）作業(yè)6（256KB）0312KB320KB352KB376KB504KB632KB888KB1024KB25整理課件4.2早期的存儲管理可變分區(qū)管理的數(shù)據(jù)結(jié)構(gòu)線性表結(jié)構(gòu)OS設(shè)立二張表，已分配區(qū)表和空閑區(qū)表〔未分配區(qū)表〕。已分配區(qū)說明表未分配區(qū)說明表序號首址大小狀態(tài)序號首址大小狀態(tài)120K8K已分（1）156K30K可用（1）228K28K已分（1）228K28K空白（0）3142K100K空白（0）386K22K可用（1）4108K34K已分（1）4142K100K可用（1）…………………………………………可變式分區(qū)狀態(tài)表26整理課件4.2早期的存儲管理鏈表結(jié)構(gòu)：一種利用存儲分塊自身存放信息即分區(qū)附加數(shù)據(jù)集，并由鏈指針按照一定算法鏈接起來。FPBPFPBPFPBPFPBPFB空閑區(qū)鏈結(jié)構(gòu)狀態(tài)大小前向指針1N+2含有N個字的作業(yè)1N+2狀態(tài)大小后向指針已分配區(qū)狀態(tài)大小前向指針1M+2FP含有M個字的空閑區(qū)1M+2BP狀態(tài)大小后向指針空閑區(qū)274.2早期的存儲管理可變分區(qū)的管理——分配與回收分配的步驟按作業(yè)長度找一個夠大的空閑區(qū)，劃出作業(yè)長度，多余仍為空閑區(qū)；修改空閑區(qū)表，填寫已分配區(qū)表。釋放的步驟查看已分配區(qū)表，根據(jù)釋放的地址、長度，得對應(yīng)表項；該項狀態(tài)置0，空白項；將釋放區(qū)記入未分配表中空項，狀態(tài)置為可用空間；與相鄰區(qū)合并。28整理課件4.2早期的存儲管理合并鄰接空閑區(qū)有四種情況合并上鄰接區(qū)；合并下鄰接區(qū)；上下兩鄰接區(qū)均可合并；上下兩鄰接區(qū)均不可合并。作業(yè)B回收區(qū)P上鄰接區(qū)f1作業(yè)B上鄰接區(qū)f1下鄰接區(qū)f2回收區(qū)P回收區(qū)P回收區(qū)P作業(yè)A下鄰接區(qū)f2作業(yè)A29整理課件4.2早期的存儲管理可變分區(qū)的分配算法最先適應(yīng)法〔firstfit〕FF：找能滿足需求的第一個空閑區(qū)，即可分配，剩余局部仍留在空閑區(qū)表中?？砂芽臻e區(qū)表按地址大小由小到大排列。優(yōu)點釋放時，假設(shè)有相鄰區(qū)，易于合并；先分配低地址空間，保存高地址較大的的空間，以備大作業(yè)分配。30整理課件4.2早期的存儲管理最正確適應(yīng)法〔BFBestfit〕找能滿足作業(yè)需要的最小分區(qū)分配。將空閑區(qū)按長度由小到大排列，即X1≤X2≤X3≤……≤Xn，其中Xi為第i分空閑區(qū)長度。S為作業(yè)的需要量，那么從X1順序比，直到S≤Xi，從Xi中分配，假設(shè)Xn不能分，那么失敗。如Xi>S，剩余的插入適宜位置。31整理課件4.2早期的存儲管理優(yōu)點平均查到一半時，即可以找到最正確空閑區(qū)，假設(shè)有Xi=S，必被選中。保存與S相差大的空閑區(qū)，每次分相差小的空閑區(qū)。缺點碎片太小，無法利用；分配、回收查找費時；合并不易，要對各空閑區(qū)計算最高地址，然后比較，找鄰接區(qū)，費時。合并后，要插入適宜位置也費時。32整理課件4.2早期的存儲管理最壞適應(yīng)法〔worstfit〕：每次總是選最大的空閑區(qū)分配。將空閑區(qū)按長度由大到小排列：X1≥X2≥X3≥……≥Xn，假設(shè)X1≥S，從X1中分X1-S≠0，剩余的插入適宜位置，X1不夠大，失?。?yōu)點分配速度快，只比較X1長度，即可確定分配；X1分配后，剩余仍較大，可滿足以后的需求。缺點各區(qū)都均等地減小，不能滿足大作業(yè)需要。33整理課件4.2早期的存儲管理操作系統(tǒng)作業(yè)A2n130K作業(yè)D1n214K作業(yè)C3N310K作業(yè)A1n470K（a）存儲器示意圖序號首址大小狀態(tài)1n2+13K1K12n310K13n130K14n470K15m160K06m220K0（c）分配后的最佳適應(yīng)算法空閑區(qū)表序號首址大小狀態(tài)1n4+13K57K12n130K13n214K14n310K15m160K06m220K0（d）分配后的最差適應(yīng)算法空閑區(qū)表序號首址大小狀態(tài)1n1+13K17K12n214K13n310K14n470K15m160K06m220K0（b）分配后的首次適應(yīng)算法空閑區(qū)表344.2早期的存儲管理3.可再定位式分區(qū)分配碎片：內(nèi)存中無法被利用的小的空閑分區(qū)?？稍俣ㄎ皇椒謪^(qū)分配即浮動分區(qū)分配，是解決碎片問題的簡單而有效的方法。其根本思想是移動所有被分配了的分區(qū)，使之稱為一個連續(xù)區(qū)域，而留下一個較大的空白區(qū)。由于程序涉及到基址存放器、訪問內(nèi)存指令、訪問參數(shù)表或數(shù)據(jù)結(jié)構(gòu)，所以一個作業(yè)移動位置后，通常無法保證程序在新位置上能夠正確運行，為此，應(yīng)解決程序的可再定位〔浮動〕問題。35整理課件4.2早期的存儲管理操作系統(tǒng)操作系統(tǒng)用戶程序A用戶程序A10K用戶程序B用戶程序B用戶程序C50K用戶程序D用戶程序C105K45K用戶程序（a）緊湊前（b）緊湊后緊湊內(nèi)存示意圖36整理課件4.2早期的存儲管理解決程序的可再定位〔浮動〕問題的方法：使用模塊裝入程序，將程序的裝配模塊重新裝入到指定位置，并從頭開始執(zhí)行。缺點花費較多的處理機時間；如果程序已經(jīng)執(zhí)行了一段時間，必須從頭開始，否那么將引起混亂。動態(tài)再定位技術(shù)。當一個作業(yè)裝入與其地址空間不一致的存儲空間時，可在訪問指令或數(shù)據(jù)時，通過再定位存放器〔或稱浮動存放器〕來自動修改訪問存儲器的地址。因此，一個作業(yè)再主存中移動后，只需要改變再定位存放器的內(nèi)容即可。37整理課件4.2早期的存儲管理可再定位分區(qū)分配算法和固定式〔或可變式〕分區(qū)分配算法根本相同。問題是何時進行靠攏，一般有兩種時機的選擇當某個分區(qū)內(nèi)的作業(yè)一完成，就立即靠攏。這樣的靠攏操作是比較頻繁的，由于實施程序的移動要花費較多的處理機時間，因此應(yīng)盡可能減少靠攏操作的次數(shù)；在為某一作業(yè)請求一個分區(qū)時，當時內(nèi)存沒有足夠大的空白區(qū)，但各空白區(qū)之和可以滿足該作業(yè)存儲要求，此時須進行靠攏操作。這樣的靠攏次數(shù)要少得多，從而可以節(jié)省處理機時間。38整理課件4.2早期的存儲管理分配算法流程圖請求分配一個大小為xKB的分區(qū)有大于xKB的空白區(qū)嗎？空白區(qū)的總和≥xKB執(zhí)行靠攏操作并修改狀態(tài)表此時無法分配返回一個分區(qū)號分配一個分區(qū)并修改狀態(tài)表NNYY39整理課件4.2早期的存儲管理4.多重分區(qū)分配通常一個作業(yè)由一些相對獨立的程序段和數(shù)據(jù)段組成，如主程序、子程序、數(shù)據(jù)組等。這些程序段中的每一個在邏輯上必須是連續(xù)的，但是相應(yīng)的各分區(qū)不要求是連續(xù)的。采用多重分區(qū)分配方案，作業(yè)可以在其執(zhí)行期間申請附加的分區(qū)。優(yōu)點：可使存儲空間的利用率提高。缺點：作業(yè)分段越多，分區(qū)越小，存儲器過碎，造成沒有較大的空白區(qū)；實現(xiàn)多重分區(qū)要求更多的硬件支持，管理也比較復(fù)雜。40整理課件4.2早期的存儲管理5.分區(qū)的保護措施存儲保護是為了防止一個作業(yè)有意或無意的破壞操作系統(tǒng)或其他作業(yè)。通常采用界限存放器或者存儲保護鍵兩種方法。界限存放器定位存放器和界限存放器：利用定位存放器的值〔=存儲空間首址減去地址空間首址的值)，和界限存放器的值進行存儲訪問檢查(界限存放器的值存放作業(yè)地址空 間的大小〕。上下限存放器。每次訪主存時,其地址值與上限存放器值(物理地址的最高地址)和下限存放器值(最低物理地址)比較：假設(shè)大于上限或小于下限時那么中斷訪問主存。41整理課件4.2早期的存儲管理下界寄存器60KB基址寄存器60KB限長寄存器64KB上界寄存器124KB060KB作業(yè)2的分區(qū)124KB256KB060KB作業(yè)2的分區(qū)124KB256KB上下界存放器進行存儲保護基址存放器進行存儲保護424.2早期的存儲管理存儲保護鍵將主存靜態(tài)分成假設(shè)干塊，一般是等分為1k~2k大小分塊；每塊都指定一個單獨的保護鍵，保護鍵由保護字和保護方式組成：保護方式分為寫保護、讀寫保護兩種，而保護字由一組代碼組成；每個作業(yè)賦于一個不同代碼并存入該作業(yè)的程序狀態(tài)字中，訪問主存時用此代碼(鑰匙)與保護鍵進行匹配檢查；先進行保護方式檢查，假設(shè)是寫保護，那么對一切讀指令都不進行匹配檢查允許訪問主存，但對寫指令必須進行匹配檢查；假設(shè)是讀寫保護，那么對任何指令都進行匹配檢查。匹配檢查是用作業(yè)代碼鑰匙與主存的代碼鎖相比較，假設(shè)相同那么允許訪問主存，否那么作為訪問主存出錯被中斷；一般系統(tǒng)都將操作系統(tǒng)的程序狀態(tài)字(PSW)鑰匙置為0，它具有萬能鑰匙之成效——可訪問任一主存塊。43整理課件4.2早期的存儲管理44整理課件4.2早期的存儲管理6.分區(qū)分配方案的評價優(yōu)點對多道程序設(shè)計，實現(xiàn)了存儲的共享，更有效地使用了處理機和I/O設(shè)備，從而使系統(tǒng)的吞吐量和作業(yè)周轉(zhuǎn)時間得到了相應(yīng)的改善；高了主存利用率，可變式分區(qū)高于固定式分區(qū)，可定位式分區(qū)更高；實現(xiàn)存儲保護的措施比較簡單；多重分區(qū)分配方案能實現(xiàn)對子數(shù)據(jù)、程序段的共享。45整理課件4.2早期的存儲管理缺點：主存仍不能充分利用，存在嚴重碎片問題(可重定位分區(qū)分配除外)；不能實現(xiàn)對主存的擴充，作業(yè)大小受到主存可用空間的限制；和單一連續(xù)分配一樣，要求一個作業(yè)在執(zhí)行之間必須全部裝入內(nèi)存，因此在主存中可能包含從未使用過的信息。采用靠攏方法，雖然能解決碎片問題，但有時需移動大量信息，從而損失了處理機時間。除多重分區(qū)外，幾個共行作業(yè)之間不能共享存入主存的單一信息副本。46整理課件4.3分頁存儲管理可再定位〔即浮動〕式分區(qū)分配技術(shù)，使用這種分配技術(shù)可以消除碎片，使一些零散的空白區(qū)集合成較大的連續(xù)的空白區(qū)，提高主存的利用率。但是，各作業(yè)分區(qū)的靠攏花費了較多的處理機時間，并不可取。這是由于我們提出了每個作業(yè)占有的存儲空間必須是連續(xù)的。避開這一要求，就引進了分頁存儲管理技術(shù)。47整理課件4.3分頁存儲管理4.3.1分頁原理用戶作業(yè)地址空間起點與分區(qū)的物理位置無關(guān)，所以作業(yè)的地址空間通常從0開始。分頁存儲管理就是從邏輯地址空間到物理地址空間的一種變換，即f：L→S，其中，L、S分別表示邏輯地址空間和物理地址空間。頁框〔物理塊〕：將主存按2n劃成位置固定，長度相等的塊，稱為頁框〔pageframe〕或物理頁。如1KB，PC機為4KB一頁。對頁框進行統(tǒng)一編號0，1，2，……，n-1，稱為塊號〔頁框號﹑頁架號﹑物理頁號﹑絕對頁號〕；頁框是分配內(nèi)存的根本單位。48整理課件4.3分頁存儲管理頁面(頁)：作業(yè)的虛擬地址空間也按同樣長度分成頁面(虛頁，虛擬頁面)，對其統(tǒng)一編號0，1，2…，m-1，稱為頁面號(虛頁號﹑邏輯頁號﹑相對頁號)。一個作業(yè)的邏輯地址空間的所有頁面是鄰接的，而變換到物理存儲空間的各塊可以不鄰接。邏輯地址空間和物理地址 空間的對應(yīng)關(guān)系由稱為頁 面變換表的PMT指出，

PMT也簡稱為頁表。虛頁號頁框號0317218…………頁表（PAGETABLE）49整理課件4.3分頁存儲管理在分頁存儲管理方式中，系統(tǒng)以頁框為單位把主存分給進程，并且每個進程分給的各頁框不一定相鄰和連續(xù)。頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。每一個進程對應(yīng)一張頁表，一個頁表表項的數(shù)目等于其所記錄的進程邏輯地址空間的頁面數(shù)。CPU中設(shè)立一個頁表地址存放器。例作業(yè)A的地址空間為11KB，按4KB分頁，分為0，1，2頁。50整理課件4.3分頁存儲管理作業(yè)101KB2KB作業(yè)201KB2KB3KB作業(yè)301KB操作系統(tǒng)作業(yè)2（0頁）作業(yè)2（1頁）作業(yè)1（0頁）作業(yè)1（1頁）作業(yè)2（2頁）作業(yè)3（0頁）物理地址空間頁號塊號051601KB2KB3KB4KB5KB6KB7KB8KB9KB10KB02142708頁面變換表邏輯地址空間514.3分頁存儲管理L1，2KB＋6001557100作業(yè)2的地址空間05181KB2KB2KB＋60L1，2KB＋6001557100存儲空間2KB3KB4KB5KB6KB7KB7KB＋608KB021427頁面變換表頁面變換表保證了作業(yè)的正確執(zhí)行524.3分頁存儲管理4.3.2地址變換機構(gòu)1.動態(tài)地址變換機構(gòu)DAT考察計算機系統(tǒng)指令LR1，D2〔X2，B2〕，其中，X2、B2、D2為第二操作數(shù)域使用的變址存放器、基址存放器和位移量，R1是第一操作數(shù)域的通用存放器。指令格式為圖LR1X2B2D20781112151619203153整理課件4.3分頁存儲管理指令的第二操作數(shù)的有效地址為E2＝〔X2〕＋〔B2〕＋D2，該指令的有效地址占24位。因此，邏輯地址空間最大可達224＝16MB。假定頁面大小為4KB，于是邏輯地址空間可達4096個頁面，每個頁面4096個字節(jié)。24位有效地址自然地被劃分為兩局部，前12位為頁號，后12位為頁內(nèi)地址。頁號頁內(nèi)地址07819203154整理課件4.3分頁存儲管理動態(tài)地址變換機構(gòu)自動地將所有地址劃分為頁號和頁內(nèi)地址兩局部。利用PMT表將頁號代之以塊號，得到要使用的物理存儲地址。LR1，D2（X2，B2）LR1X2B2D2（7）000000000111（144）000010010000有效地址（2）000000000000（144）000010010000頁號頁內(nèi)地址頁號塊號011427……255頁面變換表554.3分頁存儲管理每個作業(yè)都有一個頁面變換表，通常各作業(yè)的頁面變換表放在操作系統(tǒng)的一個工作區(qū)中，由頁面變換地址存放器〔PMTAR〕指出作業(yè)的頁面變換表的起始地址。當處理機執(zhí)行一個新作業(yè)或恢復(fù)一個舊作業(yè)時，只要修改PMTAR的內(nèi)容，使之指向要執(zhí)行作業(yè)的PMT起始地址即可。56整理課件4.3分頁存儲管理PMTAR34160長度PMT起始地址0KB4KB8KB12KB0頁1頁2頁作業(yè)2的地址空間4字節(jié)247作業(yè)2（0頁）作業(yè)2（1頁）作業(yè)2（2頁）操作系統(tǒng)用04KB塊2塊4塊74160PMTAR、PMT、頁面和塊之間的關(guān)系57整理課件4.3分頁存儲管理2.高速頁面變換存放器為了實現(xiàn)從作業(yè)地址空間到物理地址空間變換，可采用硬件的高速存放器來實現(xiàn)。3.聯(lián)想存儲器頁面變換表存放在主存，由操作系統(tǒng)實施管理，在作業(yè)執(zhí)行時，每條指令的執(zhí)行都必須進行地址變換。每條指令必須兩次訪問存儲器：一次把頁號變成物理塊號，一次進行實際存取所要的數(shù)據(jù)或指令，增加了指令執(zhí)行的機器時間，影響了計算機的速度。采用高速存放器方法，如果作業(yè)地址空間較大，所需存儲器較多，花費較高。58整理課件4.3分頁存儲管理因此采用一種折衷方法來解決這一矛盾，即把高速存放器作為DAT的輔助機構(gòu)來實行地址變換。這些存放器連同管理它們的硬件構(gòu)成了一個容量較小的存儲器，稱之為聯(lián)想存儲器，也稱快表。在聯(lián)想存儲器中，存放正運行作業(yè)當前最常用的頁號和相應(yīng)塊號，具有并行查詢能力。59整理課件4.3分頁存儲管理有效地址PW頁號P塊號B…BW物理地址輸入存放器輸出存放器60整理課件4.3分頁存儲管理在采用聯(lián)想存儲器的系統(tǒng)中，通常采用“雙管齊下〞的方針，既按給出的頁號檢索聯(lián)想存儲器中的相應(yīng)塊號，同時按PMT表進行查找塊號，同時進行。如果在聯(lián)想存儲器中，檢索到所要塊號，立即停止PMT表的查找，利用聯(lián)想存儲器給出的塊號訪問主存。如果聯(lián)想存儲器檢索不到需要的塊號，將PMT表查找到的頁號以及所對應(yīng)的塊號填入聯(lián)想存放器內(nèi)的空白單元中，如沒有空白單元，根據(jù)某種規(guī)那么淘汰一個單元內(nèi)容后填入。61整理課件4.3分頁存儲管理例設(shè)CPU訪問內(nèi)存要200ns，訪問快表一次要40ns，命中率為90%，求一次訪問內(nèi)存的平均時間是多少？比慢表訪問下降了多少？解訪問內(nèi)存的平均時間為：〔40+200)*0.9+(200+200)*0.1=216+40=256〔ns〕不用快表，每取一指令或數(shù)據(jù)要用400ns，那么〔400-256〕/400=36%62整理課件4.3分頁存儲管理例CPU訪問慢表為100ns，訪問快表為20ns，希望把進行一次訪問內(nèi)存存取指令的或數(shù)據(jù)的時間控制在140ns，求此時快表的命中率。解設(shè)命中率為X，列方程：〔100+20〕*X+〔100+100〕*〔1-X〕=14080X=60X=75%所以，命中率至少要75%。63整理課件4.3分頁存儲管理4.3.3分頁存儲管理算法為實現(xiàn)分頁儲存管理，在軟件方面應(yīng)建立如下表格，并由操作系統(tǒng)實施管理。作業(yè)表〔JT〕。整個系統(tǒng)一張表。每個作業(yè)在作業(yè)表中對應(yīng)一個表目，包括該作業(yè)的頁表地址、頁表長度和狀態(tài)信息。當作業(yè)調(diào)度程序調(diào)度到某個作業(yè)時，如果存儲要求可以得到滿足，就在此表上進行登記。當作業(yè)輪到處理時，就從此表把頁表始址和頁表長度送到控制存放器中。64整理課件4.3分頁存儲管理存儲分塊表〔MBT〕。整個系統(tǒng)一張表。該表中每一表目對應(yīng)一個存儲塊，記錄了該塊的狀態(tài)：已分配或空閑。頁面變換表〔PMT〕。每個作業(yè)一張表。頁面變換表，用于該作業(yè)的地址變換，該作業(yè)有多少頁面就有多少表目，表目內(nèi)記錄對應(yīng)的存儲塊號。65整理課件4.3分頁存儲管理作業(yè)表作業(yè)號頁表長度PMT始址狀態(tài)123600已分配234160已分配313820已分配4－－空項塊號563600作業(yè)1的PMT塊號2474160作業(yè)2的PMT塊號83820作業(yè)3的PMT塊號狀態(tài)0OS1OS2作業(yè)23可用4作業(yè)25作業(yè)16作業(yè)17作業(yè)28作業(yè)39可用存儲分塊表MBT66整理課件4.3分頁存儲管理請求分配xKB的地址空間計算所需塊數(shù)NN＝[xKB/4KB]有N個可用的塊？本次無法分配在作業(yè)表中找空表目置頁表長度＝N，狀態(tài)＝已分配分配該作業(yè)的PMT表，并在作業(yè)表中登記該PMT的始址檢查內(nèi)存分塊表，分配N個可用存儲塊，在每塊的狀態(tài)欄內(nèi)填入作業(yè)序號，再將存儲塊號填入PMT表返回分頁存儲分配算法流程圖67整理課件4.3分頁存儲管理4.3.4分頁存儲管理方案的評價分頁存儲管理方案不必像浮動分區(qū)法那樣執(zhí)行費時的靠攏操作，消除了碎片，便于多道程序設(shè)計，提高了處理機和主存的利用率。缺點：采用動態(tài)地址變換會增加計算機本錢和降低處理機的速度；各種表格要占用一定容量的主存空間，而且還要花費一局部處理機時間用來建立和管理這些表格；碎片雖然消除，但每個作業(yè)的最后一頁一般不能充分利用。存儲擴充問題仍然沒有解決。68整理課件4.4請求分頁存儲管理4.4.1請求分頁原理根本原理將作業(yè)的地址空間按同等大小劃分成頁面〔虛頁〕，將主存空間劃分成同樣大小的頁框〔實頁〕；將頁面不是全部裝入主存，而是裝入一局部。作業(yè)運行時，至少裝入一個頁面；每次訪問的頁面如果不在主存中，就從輔存中調(diào)入主存。69整理課件4.4請求分頁存儲管理請求分頁存儲中，必須解決幾個問題：1.如果一個作業(yè)不把它的整個地址空間同時全部裝入主存，那么該作業(yè)是否能開始運行并運行一段時間？2.在作業(yè)運行一段時間后，必然要訪問到?jīng)]有裝入的頁面，也就是說，要訪問的虛頁不在實存。那么，這個問題系統(tǒng)是怎樣發(fā)現(xiàn)的？3.如果系統(tǒng)已經(jīng)發(fā)現(xiàn)某虛頁不在實存，就應(yīng)將其裝入實存。問題是從何處裝入，裝入到何處，如果實存空間已滿怎么辦？70整理課件4.4請求分頁存儲管理1.一個作業(yè)的地址空間不同時全部裝入主存時，這個作業(yè)可以開始運行不能運行一段時間，因為作業(yè)在運行期間的各個階段，多數(shù)作業(yè)只使用全部地址空間的一局部；程序的局部性：順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)〔如數(shù)組〕，它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被訪問后，那么它附近的位置很快也會被訪問。作業(yè)被調(diào)度投入運行前，通常只裝入其虛頁0到實存，作業(yè)所需其它各頁，根據(jù)請求而被裝入，這就保證了一個作業(yè)在運行前可以不必裝入該作業(yè)的全部地址空間。71整理課件4.4請求分頁存儲管理2.在PMT中增加一個狀態(tài)位，規(guī)定該位為0表示該頁已裝入主存，該位為1表示該頁不在主存，當?shù)刂纷儞Q機構(gòu)檢測到虛頁的狀態(tài)位為1時，表示該頁不在主存，規(guī)定由硬件產(chǎn)生缺頁中斷，轉(zhuǎn)入中斷處理程序，雖然這不是用戶程序的錯誤，但它是屬于程序中斷。72整理課件4.4請求分頁存儲管理作業(yè)101KB作業(yè)201KB2KB作業(yè)300塊1塊2塊L1，1KB＋αA1，2KB＋β3塊4塊5塊6塊7塊8塊006802009塊存儲空間塊號狀態(tài)506001KB2KB3KB4KB5KB6KB7KB8KB9KB204070803090－1－1頁面變換表地址空間L1，1KB＋αA1，2KB＋β0068020000615100作業(yè)401001041KB1KB＋α2KB2KB＋β3KB734.4請求分頁存儲管理3.當發(fā)現(xiàn)虛頁不在實存時，引起缺頁中斷，利用中斷處理程序完成該頁的裝入。中斷處理程序把所需頁面裝入實存后，修改PMT的狀態(tài)位，然后重新執(zhí)行該指令。將某一頁從實存移到輔存稱為“出頁〞，從輔存調(diào)入實存稱為“入頁〞，入頁和出頁的操作稱為“分頁〞操作。在請求分頁系統(tǒng)中，從實存中剛剛移走某個頁面后，根據(jù)請求馬上又調(diào)入該頁，這種反復(fù)進行入頁和出頁的現(xiàn)象稱為“抖動〞，也叫做系統(tǒng)顛簸。它浪費了大量的處理機時間，所以應(yīng)盡可能防止“抖動〞的發(fā)生。74整理課件4.4請求分頁存儲管理執(zhí)行一條指令形成有效地址計算頁號該頁在實存嗎？取數(shù)據(jù)完成該指令取下一條指令缺頁中斷入口有空閑的實頁嗎？取出保存的頁號找出磁盤地址入頁修改PMTMBT表重新執(zhí)行被中斷的指令出頁修改PMTMBTC=1?復(fù)制到輔存硬件軟件YYYNNN75整理課件4.4請求分頁存儲管理4.4.2頁面置換算法通常一個置換算法的效能與作業(yè)運行過程中訪問地址空間的變化規(guī)律密切相關(guān)，而這個規(guī)律難以預(yù)測。因此，人們對不同類型的作業(yè)，從不同角度，提出了許多不同的置換算法。1.先進先出算法〔First-inFirst-out，F(xiàn)IFO〕先進先出算法的根本思想是：總是淘汰那些駐留在主存時間最長的頁面，即先到主存的頁面先被淘汰。理由是：最早調(diào)入主存的頁面，其不再被訪問的可能性最大，這種算法實現(xiàn)起來比較簡單。該算法只是在按線性順序訪問地址空間的情況下才是理想的，否那么效率不高。76整理課件4.4請求分頁存儲管理塊號頁號指針01246342∧56577142替換指針〔指向最老的頁〕塊號頁號指針0126∧342256577146替換指針〔指向最老的頁〕77整理課件4.4請求分頁存儲管理2.最近最久未用置換算法〔LRU〕根本思想：如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很久沒有被訪問，那么最近也不再會被訪問。這種思想來源于程序設(shè)計的局部化程度。實質(zhì)是，當需要置換一頁時，選擇在最近一段時間最久未用的也予以淘汰。實現(xiàn)這種技術(shù)，是通過周期性地對“引用位〞進行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時間t，淘汰時選擇t最大的頁。最近最久未用置換算法簡稱LRU〔LeastRecentlyUsed〕算法，它能夠比較普遍地適用于各類類型的程序，但是實現(xiàn)起來比較困難。78整理課件4.4請求分頁存儲管理3.LRU近似算法需要在存儲分塊表MBT〔或頁表PMT〕中設(shè)一“引用位〞，當存儲分塊表中的頁被訪問時，該位由硬件自動置“1〞，而由頁面管理軟件周期地〔設(shè)周期為T〕把所有應(yīng)用位置“0〞。這種算法比較簡單，易于實現(xiàn)。缺點是：周期T的大小不易確定。另外，如果缺頁中斷剛好發(fā)生在系統(tǒng)對所有引用位重置“0〞之后，那么幾乎所有塊的引用位為“0〞，因此也有可能把常用的頁淘汰出去。79整理課件4.4請求分頁存儲管理入口替換指針前進一步指向下一存儲塊其引用位＝0？選擇該頁淘汰返回置引用位＝0LRU近似算法的流程80整理課件4.4請求分頁存儲管理塊號頁號引用位指針0124034215650711替換指針塊號頁號引用位指針01240342056517116替換指針LRU近似算法例81整理課件4.4請求分頁存儲管理4.第二次時機頁面替換算法思想：為了防止FIFO可能會把經(jīng)常使用的頁替換出去的問題，我們可以對它做一個簡單的修改，對最老頁面的R位進行檢查。如果R位是0,那么這個頁既老又沒用，應(yīng)該被立刻替換掉；如果是1,就去除這個位，把這個頁放到頁鏈表的尾端，修改它的裝入時間讓它就像剛裝入的一樣，然后繼續(xù)搜索。82整理課件4.4請求分頁存儲管理A0B3C7D8E12F14G15H18第一個裝入的頁最近裝入的頁〔a〕頁面按先進先出的順序排列A0BC7D8E12F14G15H18A被像新裝入的頁面一樣對待〔b〕在時間20發(fā)生頁面故障并且A的R位已經(jīng)設(shè)置時的頁面鏈20第二次時機頁面替換算法83整理課件4.4請求分頁存儲管理5.時鐘頁面替換算法〔CLC算法〕把所有的頁面保存在一個類似鐘表外表的環(huán)形鏈表中，有一個表針指向最老的頁面。在發(fā)生缺頁中斷時，該算法首先檢查表針指向的頁面，如果它的R位是0就淘汰掉這個頁， 并把新頁插入這個位置， 然后把表針前移一個位置； 如果R位是1就去除R位并把 表針前移一個位置，重復(fù)這 個過程直到找到一個R位為 0的頁為止。ABCDEFGHIJKL時鐘頁面替換算法84整理課件4.4請求分頁存儲管理4.4.3性能分析請求分頁存儲管理方案消除了對主存實際容量的限制，能使更多的作業(yè)按多道同時執(zhí)行，從而提高了系統(tǒng)效率。由于頁面的調(diào)入、調(diào)出要增加I/O的負擔，而且影響系統(tǒng)的效率。早期的計算機系統(tǒng)中，為擴充主存的容量，采用請求分頁存儲管理方案實現(xiàn)虛擬存儲系統(tǒng)，盡管要增加系統(tǒng)開銷，也是必要的。但是，在今天硬件本錢急劇下降，存儲技術(shù)不斷進步的形勢下，是否仍采用請求分頁存儲管理是一個值得討論的問題。85整理課件4.4請求分頁存儲管理為盡可能地減少缺頁中斷的次數(shù)，應(yīng)從程序設(shè)計的質(zhì)量，頁面的大小，主存的容量以及頁面置換算法等幾方面考慮。程序設(shè)計的質(zhì)量主要指程序局部化程度。包括時間局部化和空間局部化。時間局部化是指一旦某個位置〔數(shù)據(jù)或指令〕被訪問了，它常常很快又要再次被訪問?？赏ㄟ^循環(huán)、經(jīng)常用到的變量和子程序等程序結(jié)構(gòu)來實現(xiàn)。空間局部化是指一旦某個位置被訪問到，那么它附近的位置很快也要用到?？赏ㄟ^盡量采用順序的指令列、線性的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。設(shè)計請求分頁存儲系統(tǒng)，頁面大小也是重要參數(shù)。86整理課件4.4請求分頁存儲管理提供虛擬存儲系統(tǒng)之后，每個作業(yè)只要分到一塊主存空間就可以執(zhí)行了。從外表上看，這增加了可同時運行的作業(yè)數(shù)，但實際上是低效的。一個作業(yè)的執(zhí)行所產(chǎn)生的缺頁中斷的次數(shù)是存放頁面的實際存儲容量的函數(shù)。當主存容量增加時，缺頁中斷次數(shù)減少，到一定程度后，中斷減少次數(shù)不明顯。試驗分析說明：對所有程序來說，要使其有效地工作，它在主存中的頁面數(shù)應(yīng)不低于它的總頁面數(shù)的一半。 P121圖4.26存儲容量與缺頁中斷次數(shù)的關(guān)系87整理課件4.4請求分頁存儲管理現(xiàn)在討論運行的程序和頁面置換算法的關(guān)系。例設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，置換算法采用FIFO。P行表示頁面走向，M行表示主存頁面號，標“＋〞表示新調(diào)入頁面，加圓圈表示下一時刻被淘汰，F(xiàn)行表示是否引起缺頁中斷。缺頁次數(shù)F=9，缺頁率f=9/12=75%。時刻123456789101112P432143543215M4＋3＋2＋1＋4＋3＋5＋552＋1＋143214333522④③②①44④③55F＋＋＋＋＋＋＋＋＋88整理課件4.4請求分頁存儲管理例設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=4，置換算法采用FIFO。P行表示頁面走向，M行表示主存頁面號，標“＋〞表示新調(diào)入頁面，加圓圈表示下一時刻被淘汰，F(xiàn)行表示是否引起缺頁中斷。缺頁次數(shù)F=10，缺頁率f=10/12=83%。時刻123456789101112P432143543215M4＋3＋2＋1＋1＋15＋4＋3＋2＋1＋5＋43222154321433321543244④③②①⑤④3F＋＋＋＋＋＋＋＋＋＋89整理課件4.4請求分頁存儲管理例設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=3，置換算法采用LRU。P行表示頁面走向，M行表示主存頁面號，標“＋〞表示新調(diào)入頁面，加圓圈表示下一時刻被淘汰，F(xiàn)行表示是否引起缺頁中斷。缺頁次數(shù)F=10，缺頁率f=10/12=83%。時刻123456789101112P432143543215M4＋3＋2＋1＋4＋3＋5＋432＋1＋5＋43214354321④③②①43⑤④③2F＋＋＋＋＋＋＋＋＋＋90整理課件4.4請求分頁存儲管理例設(shè)頁面走向為P=4，3，2，1，4，3，5，4，3，2，1，5，主存容量M=4，置換算法采用LRU。P行表示頁面走向，M行表示主存頁面號，標“＋〞表示新調(diào)入頁面，加圓圈表示下一時刻被淘汰，F(xiàn)行表示是否引起缺頁中斷。缺頁次數(shù)F=8，缺頁率f=8/12=67%。時刻123456789101112P432143543215M4＋3＋2＋1＋435＋432＋1＋5＋43214354321432143543243②11①⑤④3F＋＋＋＋＋＋＋＋91整理課件4.4請求分頁存儲管理4.4.4請求分頁存儲管理方案的評價請求分頁存儲管理保存了分頁存儲管理的全部優(yōu)點，特別是它解決了消除碎片的問題。優(yōu)點提供了大容量的多個虛擬存儲器，作業(yè)地址空間不再受實存容量的限制；更有效地利用了主存，一個作業(yè)的地址空間不必全部同時都裝入主存，只裝入其必要局部，其它局部根據(jù)請求裝入，或者根本就不裝入〔錯誤處理程序等〕；更加有利于多道程序的設(shè)計，從而提高了系統(tǒng)效率。方便了用戶，特別是大作業(yè)用戶。92整理課件4.4請求分頁存儲管理缺點：為處理缺頁中斷，增加了處理機時間的開銷，即請求分頁系統(tǒng)是用時間的代價換取了空間的擴大；可能因作業(yè)地址空間過大或多道程序道數(shù)過多以及其它原因而造成系統(tǒng)抖動；為防止系統(tǒng)抖動所采取的各種措施會增加系統(tǒng)的復(fù)雜性。93整理課件4.5分段存儲管理

對于模塊化程序和變化的數(shù)據(jù)結(jié)構(gòu)的處理，以及不同作業(yè)之間對某些公共子程序或數(shù)據(jù)塊的共享等問題的解決，都存在著較大的困難。程序人員一般都希望把信息按內(nèi)容和邏輯關(guān)系分成段，每個段都有自己的名字，且可以根據(jù)名字來訪問相應(yīng)的程序段或數(shù)據(jù)段。94整理課件4.5分段存儲管理4.5.1分段原理

[MAIN]=0L1，[A]|6ST，[B]|<C>[X]=3[A]=5[B]=6C:虛存空間0160034001000600160E04000123340E0346045100R03800660R/W1－SMT容量存取權(quán)限狀態(tài)始址OS[X][A][MAIN]實存空間34603800400095整理課件4.5分段存儲管理

在分段存儲管理系統(tǒng)中，可以用類似于分頁管理用過的地址變換機構(gòu)，實現(xiàn)分段管理的地址變換。使用的是段變換表SMT，它把作業(yè)地址空間變換為物理存儲空間，作業(yè)地址空間的段與主存中的段大小相等。地址變換是在作業(yè)執(zhí)行過程中由硬件自動完成的。96整理課件4.5分段存儲管理段號段內(nèi)地址SB請求訪問S段中的B單元段S在實存嗎？B≤S段容量在訪問權(quán)限之內(nèi)？置訪問位為1。假設(shè)為寫訪問，那么置改變位為1求段的始址L，加上段內(nèi)地址B，便得實存地址A＝L＋B返回訪問地址保護中斷越界中斷缺段中斷由處理機產(chǎn)生由分段管理機構(gòu)實現(xiàn)97整理課件4.5分段存儲管理4.5.2段變換表作業(yè)的地址空間被劃分成假設(shè)干段，每個段定義一個完整邏輯信息，從0開始編址；分頁的作業(yè)是單一線性地址空間，分段作業(yè)的地址空間就是二維的，由“段名，段內(nèi)地址〞兩個部份組成；“頁〞是信息的物理單位；“段〞是信息的邏輯單位。從形狀來說，頁面大小固定，段的長度卻不定；98整理課件4.5分段存儲管理從透明度上看，頁面對于用戶是不可知的，它僅僅用于對主存的管理，分段那么對用戶是可見的，分段可在編程或編譯時即已確定和劃分；分頁管理實現(xiàn)單段式虛擬存儲系統(tǒng)，而分段存儲管理實現(xiàn)多段式虛擬存儲系統(tǒng)。指令和數(shù)據(jù)的單元地址均由兩局部構(gòu)成；一是表示段名的段號S，一是段內(nèi)位移量W，即段內(nèi)地址。段與段之間不再連續(xù)。段號S段內(nèi)地址W07815163199整理課件4.5分段存儲管理地址轉(zhuǎn)換過程由控制存放器找出正在運行作業(yè)的段表首址；利用有效地址中段號2作為進入段表的索引，得到該段在主存中的首址6K；根據(jù)段內(nèi)位移W與段長比較結(jié)果，判斷是否有越界，假設(shè)有產(chǎn)生越界中斷；取段保護方式檢查指令是否符合存取方式,假設(shè)不符合產(chǎn)生保護中斷；將段內(nèi)位移量W=100與段首址6K相加得出主存的物理地址6244；按物理地址6244訪問。100整理課件4.5分段存儲管理地址轉(zhuǎn)換過程如下圖：101整理課件4.5分段存儲管理4.5.3分段存儲管理方案的評價優(yōu)點消除了碎片。通過靠攏可移動任何段的位置〔修改SMT表的起始地址〕，從而可將零散的空白區(qū)合并成一個較大的空白區(qū)，用于裝入某一較大的段；提供了大容量的虛存。允許動態(tài)增加段的長度，容易處理變化的數(shù)據(jù)結(jié)構(gòu)便于動態(tài)裝入和鏈接。當兩個或兩個以上的作業(yè)要使用同一子程序時，在實存上就要有兩個或兩個以上的程序副本，造成浪費。通過分段管理和動態(tài)連接，可以做到幾個作業(yè)共享一個程序。便于實現(xiàn)存儲保護。102整理課件4.5分段存儲管理[MAIN1][DATA1][SQRT]作業(yè)1[MAIN2]

[DATA2][SQRT]作業(yè)20123作業(yè)1的SMT01234作業(yè)2的SMTOS[MAIN1][DATA1][SQRT][MAIN2][DATA2]實存兩個作業(yè)對SQRT的共享103整理課件4.5分段存儲管理缺點進行地址變換和實現(xiàn)靠攏操作要花費處理機時間，為管理各分段，要設(shè)立假設(shè)干表格，提供附加的存儲空間；在輔存上管理可變長度的段比較困難；段的最大長度受到實存容量的限制；會出現(xiàn)系統(tǒng)抖動現(xiàn)象。104整理課件4.6段頁式存儲管理用分段方法來分配和管理虛存：用分頁方法來分配和管理實存。在段頁管理系統(tǒng)中，每一段不再占有連續(xù)的實存空間，而被劃分為假設(shè)干個頁面。段頁存儲管理實際上是對頁面進行分配和管理的，因此有關(guān)段的靠攏、輔存管理以及段長限制等問題都得到很好的解決。而分段的優(yōu)點，如允許動態(tài)擴大段長，分段的動態(tài)鏈接，段的共享，段的保護措施等卻被保存下來。這一存儲管理技術(shù)在大、中型計算機中已獲得了廣泛的應(yīng)用。105整理課件4.6段頁式存儲管理4.6.1段頁式存儲管理的實現(xiàn)一、實現(xiàn)原理1.一個作業(yè)的地址空間被分成假設(shè)干段，每段又被分成假設(shè)干固定大小的頁面；2.段末局部未占滿一頁的也算一頁，如下圖，這就解決了外零頭問題；106整理課件4.6段頁式存儲管理3.段頁式地址結(jié)構(gòu)是由段號S、頁號P、頁內(nèi)地址W三局部組成。這種地址結(jié)構(gòu)如以下圖所示；4.段號長度ns,確定了作業(yè)的最大段數(shù)2ns；頁號P的占位數(shù)np確定了每個分段的最大頁數(shù)為2np，而段內(nèi)位移W的占位數(shù)nw確定了每頁的最大容量2nw；例IBM370系統(tǒng)中，最多有256段〔ns=8〕，每個分段最多16頁〔np=4〕,每頁最大4K〔nW=12〕。段號S頁號P頁內(nèi)地址W0781516192031107整理課件4.6段頁式存儲管理5.系統(tǒng)為每一個作業(yè)建立了一張段表，并為每個段建立了一張頁表，段表的地址局部指向相應(yīng)頁表的首址?？刂萍拇嫫鞫伪黹L度段表地址段號狀態(tài)頁表長度頁表地址00L011·21·30L3段表頁號狀態(tài)實存頁號00102030L000102030L3頁表…OS實存108整理課件4.6段頁式存儲管理二、段頁式的地址轉(zhuǎn)換過程1.由控制存放器中查出段表起始址；2.根據(jù)段表首址及虛地址中段號S查段表,并根據(jù)段描述符知相應(yīng)段信息；3.假設(shè)段不在主存產(chǎn)生缺段中斷；4.假設(shè)操作不符存取方式