操作系統(tǒng)學位復習

第8章實存儲器管理技術2023/2/51物理主存主存為操作系統(tǒng)、各種系統(tǒng)程序和用戶程序所共享，任何程序的執(zhí)行最終都要從主存中存取指令和數(shù)據(jù)，都必須和主存打交道；現(xiàn)代操作系統(tǒng)可區(qū)分兩類主存：物理主存和邏輯主存；共享的基礎是物理主存；物理主存由0~(m-1)個物理地址組成；物理地址是計算機主存單元的真實地址，又稱為絕對地址或實地址，處理器依據(jù)絕對地址可以隨機存取存放在其內的信息；物理地址的集合所對應的空間組成了主存空間；而主存中的一個區(qū)域是物理地址集合的一個遞增整數(shù)序列子集（如n,n+1,…,n+m）所對應的主存空間。2023/2/52邏輯主存如果直接以物理地址提交給用戶使用，對用戶來說是十分困難的事情；采用了多道程序設計技術之后，多個用戶程序共享主存，由用戶自行分配主存更是不可能的事；因此，為支持多道程序運行，方便用戶，系統(tǒng)必須為每個用戶提供0~(n-1)的一組邏輯地址，即提供一個虛擬地址空間；用戶的程序地址（指令地址或操作數(shù)地址）均為邏輯地址，或稱為相對地址；根據(jù)邏輯地址不能直接到主存中去存取信息；邏輯地址與物理地址之間有一定的映射關系，程序執(zhí)行時，必須將邏輯地址正確地轉換為物理地址，這就叫做地址映射。2023/2/53主存儲器的物理組織主存的結構組織和實現(xiàn)方法，很大程度上決定了計算機系統(tǒng)的功能；主存的功能：存放內核和用戶程序的指令和數(shù)據(jù)；每一項信息都存放在主存的特定位置上；信息在主存是按“位”存放的；編址；目前多數(shù)計算機以字節(jié)為單位進行編址。2023/2/54計算機系統(tǒng)存儲器層次寄存器高速緩存主存儲器磁盤緩存固定磁盤可移動存儲介質2023/2/55主存儲器管理功能（1）主存分配可以使多個程序同時駐留在主存中，以提高CPU利用率；保證系統(tǒng)的高性能，提高存儲利用率和提高主存的分配和釋放（回收）速度，以加快任務的執(zhí)行；地址轉換和重定位程序不必事先約定存放地址，可在執(zhí)行過程中移動；可以運行只裝入了一部分的程序，縮短程序的啟動時間；研究和使用各種有效的地址轉換技術以及相應的地址轉換機構；2023/2/56主存儲器管理功能（2）存儲保護和主存共享研究如何保護各存儲區(qū)中信息不被破壞和偷竊；由于許多不同的任務可能要執(zhí)行同一個程序，進程中多個合作進程要訪問相同的數(shù)據(jù)結構，所以存儲保護機制要提供進程對某些主存區(qū)共享的靈活性；存儲擴充使用有效的存儲管理技術來實現(xiàn)邏輯上的擴充—即虛擬存儲技術；運行的程序應不受主存大小的限制，理想情況下應能運行任意大小的程序。2023/2/57主存映射什么是地址映射？首先，在多用戶共享主存時，需要由系統(tǒng)分配主存；一般情況下，一個作業(yè)程序分配到的存儲空間和它的地址空間是不一致的；因此作業(yè)的相應進程在處理器上運行時，所要訪問的指令和數(shù)據(jù)的實際地址和地址空間中的地址是不同的；所以，處理器在執(zhí)行指令時，必須把邏輯地址轉換為絕對地址后，方能訪問信息。地址映射方式編程或編譯時確定地址映射關系如果虛—實地址間的對應關系是在程序編寫或者程序編譯時實現(xiàn)的，則結果為一個不能浮動的程序模塊，它必須被放在主存某一確定的地址中，而且永不會改變，因為它所包含的全部地址都是主存地址，在這種情況下，把這樣一個程序裝入主存，就必須在申請主存時，具體地提出申請的主存容量和主存地址，因此主存分配程序在分配時將沒有什么活動余地。靜態(tài)地址映射動態(tài)地址映射2023/2/58程序的邏輯組織傳統(tǒng)計算機的主存儲器是一個一維的存儲空間，它的地址從零開始到主存上界順序編號，這是存儲器的組織方式；程序一般有兩種組織方式程序的地址空間是一維線性的所有的程序和數(shù)據(jù)經編譯、連接后成為一個連續(xù)的地址空間；程序的地址空間是二維段式結構將程序分成若干模塊或過程，并把可修改的數(shù)據(jù)和不可修改的數(shù)據(jù)分開，一個程序可由代碼段、數(shù)據(jù)段、棧段、特別分段等組成，編譯時就明確加以區(qū)分，經編譯、連接后成為可執(zhí)行代碼，系統(tǒng)有指向各分段的指針，在程序執(zhí)行時可方便地實現(xiàn)地址變換。把地址空間邏輯上劃分成對應的程序段和數(shù)據(jù)段的優(yōu)點：首先，它符合人們的習慣；其次，只要增加少量開銷就能對不同的段賦予不同的保護級別；另外，還可實現(xiàn)動態(tài)連接，即對分段單獨進行編譯，只有當某一段要調用另一分段時，才由系統(tǒng)在運行時動態(tài)連接。2023/2/59固定分區(qū)存儲管理（1）把主存分成若干個固定大小的存儲區(qū)（又稱存儲塊），每個存儲區(qū)分給某一個作業(yè)使用，直到該作業(yè)完成后才把該存儲區(qū)歸還系統(tǒng)；分單道作業(yè)和多道作業(yè)兩種情況；單用戶、單道作業(yè)情況（教材圖8.2）多道作業(yè)情況（教材圖8.3）操作系統(tǒng)區(qū)、用戶使用的分區(qū)主存中分區(qū)的區(qū)數(shù)是固定不變的，每區(qū)的大小也是固定不變的分給每個作業(yè)一塊大于或等于作業(yè)大小的主存分區(qū)，不允許兩個作業(yè)同時放于同一個分區(qū)中；問題：分區(qū)中常有未用的、剩下的空閑部分，即存儲碎片，降低了主存的利用率；存儲分塊表：主存分區(qū)情況說明信息，存儲區(qū)的使用狀況信息，包括大小、位置和狀態(tài)三項信息。2023/2/510固定分區(qū)存儲管理（2）操作系統(tǒng)區(qū)作業(yè)i的程序、數(shù)據(jù)等界限地址柵欄寄存器作業(yè)2作業(yè)1界限地址+邏輯地址裝入程序采用靜態(tài)重定位的單用戶連續(xù)存儲管理操作系統(tǒng)區(qū)用戶區(qū)界限地址定位寄存器邏輯地址CPU絕對地址采用動態(tài)重定位的單用戶連續(xù)存儲管理2023/2/511固定分區(qū)存儲管理（3）存儲分塊表大?。褐赋鲈摯鎯K的大小，以字節(jié)為單位；位置：指出該存儲塊在主存中的起始地址；狀態(tài)：表明該存儲塊是否已被使用。存儲保護功能一對“界地址寄存器”，如果處理器要訪問主存某單元時，系統(tǒng)硬件自動將該單元地址與界限寄存器的內容進行比較，以判斷此次訪問是否合法；優(yōu)點：簡單，要求的硬件支持只是一對界地址寄存器，軟件算法簡單；缺點：主存利用率不高。2023/2/512固定分區(qū)存儲管理的地址轉換（1）固定分區(qū)存儲管理的地址轉換可以采用靜態(tài)定位方式，裝入程序在進行地址轉換時檢查其絕對地址是否在指定的分區(qū)中，若是，則可把程序裝入，否則不能裝入，且應歸還所分得的存儲區(qū)域；固定分區(qū)方式的主存去配很簡單，只需將主存分配表中相應分區(qū)的占用標志位置成“0”即可。2023/2/513固定分區(qū)存儲管理的地址轉換（2）固定分區(qū)存儲管理的地址轉換也可以采用動態(tài)定位方式，如下圖示；系統(tǒng)專門設置一對地址寄存器—上限/下限寄存器；當一個進程占有CPU執(zhí)行時，操作系統(tǒng)就從主存分配表中取出相應的地址占有上限/下限寄存器；硬件的地址轉換機構根據(jù)下限寄存器中保存的基地址B與邏輯地址得到絕對地址；硬件的地址轉換機構同時把絕對地址和上限/下限寄存器中保存的相應地址進行比較，而實現(xiàn)存儲保護。B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器<B+L2越界中斷用戶分區(qū)1用戶分區(qū)2用戶分區(qū)32023/2/514可變分區(qū)存儲管理概念所謂可變分區(qū)，是指主存事先并未劃分成一塊塊分區(qū)，而是在作業(yè)進入主存時，按該作業(yè)的大小建立分區(qū)，分給作業(yè)使用；特點：分區(qū)個數(shù)是可變的，每個分區(qū)的大小也是不固定的；主存中分布著個數(shù)和大小都是變化的空閑分區(qū)或碎片，這些空閑分區(qū)有些可能相當大，而有些則相當小。2023/2/515數(shù)據(jù)基的組織方法（1）存儲分塊表（教材圖8.5）這種存儲分塊表存在兩個缺點：由于分區(qū)個數(shù)是變化的，所以表長不好確定，造成表格管理上的困難，若給該表留的空間不足，又無法登記各分區(qū)的情況，若留的空間過大，造成浪費；分配主存時，為查找一塊合適的空閑分區(qū)所需掃描的表目增加了，查找速度變慢了；分開設置兩個存儲管理表（教材圖8.6）用已使用分區(qū)表（UBT）和空閑分區(qū)表（FBT）分別登記和管理系統(tǒng)中的已分分區(qū)和空閑分區(qū)；減少存儲分配和釋放時查找表格的長度，提高查找速度；2023/2/516數(shù)據(jù)基的組織方法（2）空閑存儲塊鏈（教材圖8.7）使用鏈指針把所有的空閑分區(qū)鏈結在一起，構成一條空閑存儲塊鏈；實現(xiàn)方法：把每個空閑存儲塊的起始若干個字節(jié)分成兩部分，前一部分作為鏈指針，指向下一空閑存儲塊的起始地址，后一部分指出本空閑存儲塊的大小，用一固定單元作為空閑存儲鏈的頭指針用以指出該鏈中的第一塊空閑存儲塊的起始地址，最后一塊空閑存儲塊的鏈指針中放著鏈尾標志；這種方法使得數(shù)據(jù)基的管理和維護比較簡單。2023/2/517存儲分配算法最佳適應法從所有未分配的分區(qū)中挑選一個最接近作業(yè)尺寸且大于或等于作業(yè)大小的分區(qū)分給要求的作業(yè)；從而使分區(qū)內未用部分即碎片最少；最先適應法按分區(qū)序號從存儲分塊表的第一個表目起查找該表，把最先找到的且大于或等于作業(yè)大小的未分配分區(qū)分給要求的作業(yè)；可以縮短查找時間；最壞適應法從所有未分配的分區(qū)中挑選最大的且大于或等于作業(yè)大小的分區(qū)分給要求的作業(yè)；可用于可變分區(qū)分配技術中。2023/2/518三種放置策略的說明作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存作業(yè)A18KBOS30KB在使用20KB在使用5KB在使用46KB020KB100KB160KB210KB256KB-1主存(a)最先適應法(b)最佳適應法(c)最壞適應法2023/2/519各種存儲分配算法的分析與比較最佳適應法：盡量多保留大的分區(qū)，使被選中分區(qū)剩下盡可能小的未用碎片；使系統(tǒng)中產生了許多小得無法再用的碎片；最先適應法：盡可能地縮短了存儲分配時間；對空閑塊的管理采取不同的辦法：表格法、空閑存儲塊鏈法、位圖法；最壞適應法：保證分配后剩下的分區(qū)足夠大，以便滿足后續(xù)要求。2023/2/520碎片問題和存儲器的緊縮由于各作業(yè)請求和釋放主存塊的結果，產生很多小的碎片，碎片的存在降低了多道的程度，造成了主存空間的大量浪費；解決碎片問題：把程序分成幾部分裝入不同的分區(qū)中去，改變一直把程序作為一個連續(xù)的整體在主存中存放的要求；改善了碎片問題，但卻增加了程度管理和執(zhí)行的復雜性；把小碎片集中起來使之成為一個大分區(qū)；移動各用戶分區(qū)中的程序，使它們集中于主存的一端，使碎片集中于另一端，從而連成一個完整的大分區(qū)，即存儲器的“緊縮”或“澄清”。2023/2/521動態(tài)重定位動態(tài)重定位：是指程序的重定位時機不是在程序執(zhí)行前進行，而是在程序執(zhí)行過程中才進行地址轉換，更確切地說是在每次訪問主存單元前才進行地址轉換（教材圖8.9）；重定位過程：首先將用戶按相對地址編址的目標程序原封不動地裝入主存中分給該用戶使用的分區(qū)中；當該用戶程序被調度到處理器上執(zhí)行時，操作系統(tǒng)自動將該用戶作業(yè)的起址由作業(yè)表中取出，并將分區(qū)起始地址減去用戶目標程序的相對基地址，然后將其減得值裝入定位寄存器中；當處理器要訪問主存時，地址轉換硬件自動將程序中的相對地址與定位寄存器中的內容相加，并按相加的和作為主存絕對地址去訪問數(shù)據(jù)。采用動態(tài)重定位后，由于目標程序裝入主存后不需要修改地址指針及所有與地址有關的項，因而程序可在主存中隨意浮動而不影響其正確執(zhí)行，從而可以方便地進行存儲器緊縮，較好地解決了碎片問題。2023/2/522動態(tài)重定位的硬件支持及軟件算法硬件支持：定位寄存器、加法器進行存儲器緊縮的兩種時機：在某個分區(qū)被釋放后立即進行緊縮，此時系統(tǒng)中總是只有一個連續(xù)的空閑分區(qū)為無碎片；當“請求分配模塊”找不到足夠大的空閑分區(qū)給用戶時再進行緊縮，這樣緊縮的次數(shù)要少些，但表格管理復雜了（教材圖8.10）。動態(tài)重定位技術的優(yōu)點：可以消除碎片，能有效利用主存空間，提高多道程序系統(tǒng)的多道程度，從而也提高了對處理器和外設的利用率；缺點：首先，需要動態(tài)重定位硬件機構支持，提高了計算機成本，減低了速度，其次，緊縮工作要花費一定的機時。2023/2/523多重分區(qū)/多對界地址管理單對界地址管理技術：每個用戶只占據(jù)主存的一個分區(qū)，存儲保護只需使用一對界地址寄存器；弊?。菏紫?，解決碎片問題時，移動程序進行存儲器緊縮時需要硬件支持；其次，不便于在進程之間共享數(shù)據(jù)。多對界地址管理技術：系統(tǒng)中設置多對界地址寄存器，并且在為每個作業(yè)或進程分配主存時，可按界地址寄存器對的個數(shù)為其分配多個不相鄰接的空閑分區(qū)；該技術既可以改善碎片情況，又便于共享；但是，在實存管理技術中，多重分區(qū)的多重程度不宜過多，否則會增加管理的復雜性。2023/2/524簡單分頁（1）前述固定分區(qū)和可變分區(qū)存儲技術存在著一定的缺點；分頁技術思想的由來；分頁存儲管理技術中的基本作法；等分主存；（頁架）用戶邏輯地址空間的分頁；（頁）邏輯地址的表示。（數(shù)對（p,d））主存分配原則；分頁情況下，系統(tǒng)以頁架為單位把主存分給進程，分給一個進程的各頁架不一定是相鄰和連續(xù)的；頁表—指出每個進程的各頁放在主存的哪些頁架中；分頁系統(tǒng)中的地址結構—分為兩部分；頁面尺寸應是2的冪—可以省去除法運算，拆分地址場中的數(shù)即可。（如p159例）2023/2/525簡單分頁（2）地址轉換過程：首先將邏輯地址左邊表示頁號部分的頁號抽取出來；以頁號作為索引查找該進程頁表，找出該頁存放的主存頁架號；用此頁架號（二進制形式）取代邏輯地址的左邊部分，并與右邊的頁內地址合并成相應的物理地址去訪問主存。簡單分頁方法的優(yōu)點：它基本沒有頁內碎片，只是在每個進程的最后一頁中，會有頁內碎片；也不會有小到不可再用的頁外碎片，主存的利用率高；不管采用哪種數(shù)據(jù)結構（空閑頁架表、位圖、空閑頁架鏈表等），分配和釋放存儲都很快；管理簡單（類似于固定分區(qū)的情況）。2023/2/526頁式存儲管理的地址轉換和存儲保護頁表始址頁表長度作業(yè)名…A頁表始址…xxxxxx頁表長度…3作業(yè)表塊號比較頁號頁內地址塊號頁內地址頁表頁表控制寄存器絕對地址邏輯地址地址越界2023/2/527程序的分段結構子程序段X數(shù)組段A┇call[X]∣<E<(調用X段的入口E)┇call[Y]∣<F<(調用Y段的入口F)┇load1,[A]∣<G<(調用數(shù)組段A[G])┇主程序段┇E：┅┅┅┅┅┅┇┇F：┅┅┅┅┅┅┇子程序段Y┇G：┅┅┅┅┅┅┇┇┇┇工作區(qū)段2023/2/528簡單分段（1）為什么需要按段分配主存？事先將用戶邏輯地址空間連接成一維線性地址空間，既費時又不便于作業(yè)的執(zhí)行，尤其不便于共享；因此，人們希望按照程序模塊來劃分段，并按這些段來分配主存；段，就是一組邏輯信息的集合，如子程序、數(shù)組和數(shù)據(jù)區(qū)等。分段存儲管理的基本概念進程的邏輯地址空間（二維的，用段名和段內地址兩個成分來描述）程序的地址結構主存分配段表（每個進程一個段表，用來指出進程的某段放在主存中的何處，以及該段的長度等信息）段的地址轉換（把邏輯地址左邊段號部分提取出來，作為索引，查找進程的段表，將段內地址與段的長度比較，如果大于段的長度，則引起非法訪問中斷，即越界訪問，如果訪問合法，就將段的起始地址與段內地址相加，就得到所要訪問的物理地址。）2023/2/529分段式存儲管理的地址轉換和存儲保護段控制寄存器段表始址段表長度段號s位移d段長基址物理地址越界?段表2023/2/530簡單分段（2）簡單分段的優(yōu)點是沒有段內碎片，只有外部碎片；簡單分段也是基于多重分區(qū)技術的進一步發(fā)展而來的；簡單分段對用戶是可見的，而且分段需要用戶提供支持，用戶也需要知道系統(tǒng)的最大段長度限制；當進程被交換出主存時，它的頁表或段表也需隨進程一起撤出主存。2023/2/531分段和分頁的比較分段是信息的邏輯單位，由源程序的邏輯結構所決定，用戶可見，段長可根據(jù)用戶需要來規(guī)定，段起始地址可以從任何主存地址開始；在分段方式中，源程序(段號，段內位移)經連結裝配后仍保持二維結構。分頁是信息的物理單位，與源程序的邏輯結構無關，用戶不可見，頁長由系統(tǒng)確定，頁面只能以頁大小的整倍數(shù)地址開始。在分頁方式中，源程序(頁號，頁內位移)經連結裝配后變成了一維結構。2023/2/532單項選擇題1.設內存的分配情況如下圖所示，若要申請一塊40K字節(jié)的內存空間，若采用最佳適應算法，則所得到的分區(qū)首址為（c）。A.100KB.190KC.330KD.410K占用占用占用占用0100K180K190K280K330K390K410K512K—12023/2/5332.在可變式分區(qū)存儲管理中的拼接技術可以（a）。A.集中空閑區(qū)B.增加主存容量C.縮短訪問周期D.加速地址轉換3.分區(qū)管理中采用“最佳適應”分配算法時，宜把空閑區(qū)按（a）次序登記在空閑區(qū)表中。A.長度遞增B.長度遞減C.地址遞增D.地址遞減4.在固定分區(qū)分配中，每個分區(qū)的大小是（c）A.相同B.隨作業(yè)長度變化C.可以不同但預先固定D.可以不同但根據(jù)作業(yè)長度固定5.把作業(yè)地址空間中使用的邏輯地址變成內存中物理地址的過程稱為（a）A.重定位B.物理化C.邏輯化D.加載6.在分頁系統(tǒng)環(huán)境下，程序員編制的程序，其地址空間是連續(xù)的，分頁是由（d）完成的。A.程序員B.編譯地址C.用戶D.系統(tǒng)7.如果一個程序為多個進程所共享，那么該程序的代碼在執(zhí)行的過程中不能被修改，即程序應該是（b）。A.可執(zhí)行碼B.可重入碼C.可改變碼D.可再現(xiàn)碼2023/2/534第9章虛擬存儲管理2023/2/535虛擬存儲系統(tǒng)的基本概念實存管理技術特點在作業(yè)運行時，整個作業(yè)的邏輯地址空間必須全部裝入主存；當作業(yè)尺寸大于主存可用空間時，該作業(yè)就無法運行。虛擬存儲器：一種實際上并不以物理形式存在的虛假的存儲器；把被運行進程訪問的地址同主存的物理地址區(qū)別開來；一個程序被編譯連接后產生目標程序，該目標程序所限定的地址的集合稱為邏輯地址空間，目標程序中指令和數(shù)據(jù)放置的位置稱相對地址或邏輯地址；而CPU能直接訪問的主存稱為物理地址空間或實存地址空間；虛擬地址：運行進程訪問的地址；實地址：處理器可直接訪問的主存地址；虛擬地址空間：運行進程可以訪問的虛地址的集合；實地址空間：計算機的主存；由動態(tài)地址映象機構來完成虛地址到實地址的轉換；虛實地址的區(qū)分，為使進程的虛擬地址空間大于主存實地址空間創(chuàng)造了條件，也為作業(yè)大小可大于主存空間創(chuàng)造了條件。2023/2/536虛存管理技術在虛擬存儲系統(tǒng)中，用戶認為機器具有無窮大的存儲空間，并且只有這一個用戶在使用機器；用戶只使用了物理主存的很少部分；原因：操作系統(tǒng)內核只把進程當前要用的部分放在主存中，不僅能減少進程啟動和滾進滾出的開銷，而且主存中也可以同時容納大量的進程，提高了系統(tǒng)多道程度和并行性；代價：主存管理要為地址轉換表和其他一些數(shù)據(jù)結構付出額外的主存開銷；地址轉換增加了每條指令的執(zhí)行時間。常用虛存管理技術分頁技術（paging）分段技術（segmentation）分段加分頁技術（segmentationwithpaging）2023/2/537分頁系統(tǒng)中的地址映象技術（1）分頁系統(tǒng)主要目的：讓程序能在它的虛擬地址空間中運行并實現(xiàn)由虛擬地址到主存物理地址的轉換；幾種地址轉換方法直接映象的頁地址轉換多級頁表的地址轉換反向頁表的地址轉換快表的地址轉換2023/2/538分頁系統(tǒng)中的地址映象技術（2）

——直接映象的頁地址轉換實現(xiàn)過程（教材圖9.1）當進程被調度到處理器上運行時，操作系統(tǒng)自動將該進程的頁表起始地址裝入頁表地址寄存器中；當該進程要訪問某個虛地址時，分頁的地址映象硬件自動按頁面大小將地址場從某位起截成頁號和頁內地址兩部分；以頁號為索引查找頁表（查找工作由硬件自動進行），得到頁架號，進而得到實際主存的絕對地址。該映象技術對系統(tǒng)效能的影響影響了處理器執(zhí)行指令的速度，使速度降低為原來的一半；原因：CPU至少要訪問兩次主存才能存取到所要數(shù)據(jù)，第一次查頁表以找出對應的頁架號，第二次真正訪問所需數(shù)據(jù)。2023/2/539分頁系統(tǒng)中的地址映象技術（3）

——多級頁表的地址轉換因為大頁表不能全放在主存中，所以對頁表本身也采取分頁措施，把頁表本身按固定大小分成一個個頁面；教材圖9.2；通過二級頁表的地址映射訪問主存存取數(shù)據(jù)需要三次訪問主存，所需時間是原來的三倍；一次頁目錄一次頁表數(shù)據(jù)所在的物理地址2023/2/540分頁系統(tǒng)中的地址映象技術（4）

——反向頁表的地址轉換教材圖9.3；實現(xiàn)過程當給出進程的虛地址后，存儲管理單元通過一個哈希定位表數(shù)據(jù)結構，把虛頁號經哈希函數(shù)轉換為一個哈希值；以該哈希值為索引，它指向反向頁表中的一個表目；由這個表目中的虛頁號得到相應的頁架號，再與偏移量拼接成物理地址，訪問主存。2023/2/541分頁系統(tǒng)中的地址映象技術（5）

——快表的地址轉換（1）把一部分常用頁表表目放入高速緩沖中，通過快表進行地址映射，快表中只包含一些最近使用的頁表的表目；快表的訪問速度比主存的訪問速度高一個數(shù)量級；快表的表目中包含：虛頁號以及該虛地址屬于哪個進程、物理頁架號、頁面保護權限等。2023/2/542分頁系統(tǒng)中的地址映象技術（5）

——快表的地址轉換（2）教材圖9.4；當運行進程要訪問虛地址v，于是硬件將地址v截成頁號p和頁內地址d；地址轉換機構首先以頁號p和快表中各表目同時進行比較，以便確定該頁是否在快表中；若在其中，則快表即送出相應的頁架號與頁內地址一起拼接成絕對地址，并按此地址訪問主存；若該頁不在快表中，則使用直接映象方法查找進程的頁表，找出其頁架號p’與頁內地址拼接成絕對地址，并訪問主存；同時將該頁的頁號及對應的頁架號一起送入快表的空閑表目中去；若無空表目，通常把最先裝入的那個頁的有關信息淘汰掉，騰出表目位置。實際上，直接映象和快表同時進行，當快表成功，就自動停止直接映象工作。2023/2/543缺頁中斷處理流程查快表有登記無登記查頁表登記入快表發(fā)缺頁中斷在主存在輔存形成絕對地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復現(xiàn)場調整頁表和主存分配表裝入所需頁面主存有空閑塊保護現(xiàn)場有選擇調出頁面該頁是否修改未修改已修改把該頁寫回輔存相應位置操作系統(tǒng)硬件邏輯地址無2023/2/544分段概述虛擬分段的優(yōu)點分段技術簡化了對可以任意增長和收縮的數(shù)據(jù)段的管理；分別編譯的段的連接十分簡單；如果一個段的過程被修改并重新編譯，不會引起其他段修改，因為這些修改只涉及該段自己的地址空間；分段機制便于在進程間共享過程和數(shù)據(jù)，只要把這些過程和數(shù)據(jù)，如同共享庫一樣，放在分別的段中，通過段表映射進行共享；段是程序員可見的邏輯上的實體，如過程，數(shù)組和堆棧等，對不同段，程序員可以安排不同的保護類型。虛擬分段的缺點段大小不一致，段外碎片使存儲利用率下降。2023/2/545分段的實現(xiàn)每個虛擬地址由一個數(shù)對（段號，段內偏移量）兩部分組成，每個進程一個段表；每個段表的表目：段的起始地址段長有效位修改位保護和共享信息實現(xiàn)過程（教材圖9.5）：當進程訪問某虛擬地址（s,w）時，內核將段表地址寄存器中內容b與段號同段表表目長的乘積相加后，得到該段的表目入口地址；由此表目中查得段s在主存中的起始地址s’；再將s’與段內地址w相加，而得到欲訪問單元的主存物理地址，并進行訪問。2023/2/546段頁式存儲管理的基本概念等分主存把整個主存分成大小相等的存儲塊，即頁架；進程的地址空間采用分段的方式按程序的自然邏輯關系把進程的地址空間分成若干段，每一段有自己的外部段名和內部段號；進程的每一段又采用分頁方法按主存頁架大小把每一段劃分成若干頁，每段從零開始為自己段的各頁依次編頁號；邏輯地址結構一個邏輯地址用三個參數(shù)表示，段號s，頁號p，頁內地址偏移量d，記為v=(s,p,d)；主存分配主存以頁架為單位分配給每個進程；段表、頁表、段表地址寄存器2023/2/547段頁式存儲管理中的地址轉換若運行進程訪問虛地址v=(s,p,d)的地址轉換過程（教材圖9.6）：地址轉換硬件將段表地址寄存器內容與指令地址場中的段號s相加，得到欲訪問段s在該進程的段表中表目入口地址；從該表的表目中得到該段的頁表起始地址，并將其與地址場中的頁號p相加后得到欲訪問頁p在該段的頁表中的表目入口地址；從該頁表表目中取出其對應的頁架號與指令地址場中的頁內地址d拼接成主存物理地址。2023/2/548段頁式存儲管理算法教材圖9.8；s<=段表長嗎？由硬件自動將段號s與段表地址寄存器中的段表長進行比較；段在主存嗎？根據(jù)段表中狀態(tài)位值由硬件判別；p<=頁表長嗎？根據(jù)段表的表目中的頁表長度與p進行比較，在有快表的情況下將p與快表中的該表目的“該段的頁表長”進行比較；訪問類型合法嗎？將本次訪問的類型與快表中的存取控制信息進行比較；頁在主存嗎？根據(jù)該段的頁表中的相應頁的狀態(tài)位判定；缺頁中斷處理2023/2/549段頁式存儲管理的優(yōu)缺點優(yōu)點提供了虛擬存儲器的功能；因為以頁架為單位分配主存，所以無緊縮問題，也沒有頁外的碎片存在；便于處理變化的數(shù)據(jù)結構，段可動態(tài)增長；便于共享，只要欲共享作業(yè)的段表中有相應表目指向該共享段在主存中的頁表地址；便于控制存取訪問。缺點增加了硬件成本，因為需要更多的硬件支持；增加了軟件復雜性和管理開銷；同分頁系統(tǒng)一樣仍然存在頁內碎片。2023/2/550頁面置換算法的引出當系統(tǒng)中沒有空閑頁時，就要進行頁面置換，即挑選一個頁面淘汰出去，并把此頁架分給進程使用；問題挑選什么樣的頁面來淘汰？從該進程已有頁面集中還是在全體頁面集中選擇淘汰頁，即局部置換還是全局置換？2023/2/551頁面置換算法（1）最佳置換算法淘汰在將來再也不被訪問，或者是在最遠的將來才被訪問的頁；最近未使用置換算法不但希望淘汰的頁是最近未使用的頁，而且還希望被挑選的頁在主存駐留其間，其頁面內的數(shù)據(jù)未被修改過；先進先出置換算法選擇最早進入主存的頁面淘汰，理由是其不再使用的可能性比最近調入的頁面要大；但只是在按線性順序訪問地址空間時，才是理想的，否則效率不高；隨著分給的頁架數(shù)增加，缺頁頻率也增加；2023/2/552頁面置換算法（2）二次機會置換算法把先進先出算法與使用頁表中的訪問位結合起來；首先檢查先進先出鏈上的最前面（最早進入）的頁，如果它的訪問位為0，則選擇該頁淘汰；如果它的訪問位為1，則把該頁移到FIFO的鏈尾，即把它作為新調入的頁；繼續(xù)查找鏈上的下一個頁并檢查它們的訪問頁，直到遇到訪問位為0的那些較先進入的頁，把它選擇為被淘汰的頁。時鐘頁面置換算法把進程所訪問的頁構成一個象時鐘那樣的環(huán)形鏈表；產生缺頁