第3章存儲管理3.13.23.3本章講述內容：3.4存儲管理綜述；

固定分區存儲管理；可變分區存儲管理；分頁式存儲管理;3.5分段式存儲管理;3.6虛擬存儲與請求頁式存儲管理。問題1：下列存儲設備可以被CPU直接訪問的訪問的是（）。A.內存儲器B.高速緩沖存儲器C.硬盤

D.光盤

E.寄存器F.磁盤G.磁帶問題2：不能被CPU直接訪問的設備上的數據，怎么才能被CPU處理？在操作系統中，把負責管理內存儲器的那部分程序，稱為存儲管理?；靖拍顑却鎯ζ鳎ê喎Q內存、主存、物理存儲器）處理機能直接訪問的存儲器。用來存放系統和用戶的程序和數據，其特點是存取速度快，存儲方式是以新換舊，斷電信息丟失。外存儲器（簡稱外存、輔助存儲器）處理機不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內存而言要慢得多，但它可用來長期保存用戶信息。在文件系統中介紹。存儲器分類指導思想：利用輔存（如磁盤、磁帶等）提供的大容量存儲空間，存放準備運行的程序和數據，當需要時或主存空間允許時，隨時將它們讀入主存儲器。信息的二級存儲

3.1存儲管理綜述3.1.1存儲器的層次結構

目前，計算機采用的都是以存儲器為中心的體系結構。存儲器負責存放整個系統的程序與數據，是重要的系統資源。.磁帶磁盤主存儲器高速緩存寄存器快慢存取速度小大容量昂貴便宜價格.

在考慮計算機存儲器的設計時，必須顧及“價格”、“容量”、“訪問時間”這三個重要特性。各種實現技術間往往有以下的關系：存取時間越快，每“位”的價格就越高；容量越大，每“位”的價格就越低；容量越大，存取速度就越慢。.

只能在“價格”、“容量”、“訪問時間”三者間尋求折中，采用存儲器的層次結構。這時，從上往下就有：每“位”的價格遞減；存儲容量遞增；存取時間遞增。.

這種層次結構中，容量較大、價格便宜的慢速存儲器（如磁盤），可作為容量較小、價格較貴的快速存儲器的后備。這正是存儲管理中虛擬存儲技術的實現基礎。

這種層次結構中，CPU可直接到寄存器、高速緩沖存儲器、內存儲器這三層上訪問數據，不能直接到磁盤和磁帶上訪問數據，那里的數據只有轉移到內存儲器后，才能接受CPU的處理。.3.1.2高速緩沖存儲器的工作原理高速緩沖存儲器CPU主存儲器字傳送塊傳送

相對于內存，高速緩存容量小、存取速度快。在它里面只存放內存中的一小部分數據內容。.

在CPU與內存間，可安排“高速緩沖存儲器”，簡稱為“高速緩存”。..

當CPU試圖訪問內存中的某一個字時，就總是先檢查該字是否在高速緩存中。如果在，就直接將它從高速緩存傳送給CPU；如果不在，則先把內存中包含此字在內的一塊數據讀入高速緩存，然后再把所需的字從高速緩存傳送給CPU。槽號標簽012C-10123塊塊（K個字）2n-1塊（K個字）地址高速緩沖存儲器主存儲器

內存和高速緩存間是以“塊”為單位傳遞數據的，高速緩存與CPU之間則是以“字”為單位傳遞數據的。..

當CPU需存取內存中某塊里的某字，而那塊不在存儲槽中，就把那塊傳到一槽里。高速緩存中的槽都有標簽，用來標識這個存儲槽在當前存放的是內存中的哪一塊。3.1.3存儲管理的功能

存儲擴充的含義是通過技術手段，給用戶造成有一個非常大的內存的虛幻感覺，但其實并沒有擴大實際內存的容量。存儲管理若能做到這種意義下的存儲擴充，那么就能使用戶程序的規模不受內存實際容量的限制。存儲擴充無疑是一件非常好的事情。這是虛擬存儲要討論的話題。1.

這是存儲管理必須承擔的任務，它應該隨時記錄內存的使用情況；根據用戶程序的需要分配存儲區；在用戶程序運行完后，及時收回存儲區，以提高內存的使用效率。內存的分配與回收2.存儲保護和共享

存儲共享是指允許多個進程訪問內存中的同一部分，這是提高存儲利用率的一種措施。.

存儲保護涉及兩個問題，一是確保用戶進程的程序不侵犯操作系統；二是確保兩個用戶程序之間不相互干擾。.3.地址定位

為適應多道程序設計環境，為使內存中的程序能夠移動，存儲管理必須對用戶程序邏輯地址空間中的地址實施重新定位，以保證進程程序的正確運行。4.存儲擴充

把用戶程序指令中的相對地址變換成為所在絕對地址空間中的絕對地址的過程，稱為“地址重定位”。

3.2固定分區存儲管理3.2.1地址重定位幾個概念1.地址重定位的定義2.01001KB2KB30003KBXXXXXXcall100用戶程序A的相對地址空間XXXXXXcall100內存儲器020KB20KB+10021KB22KB20KB+300023KB操作系統XXXXXXXcall20580內存儲器020KB20KB+10021KB22KB20KB+300023KB操作系統XXXXXXcall22628內存儲器022KB22KB+10023KB24KB22KB+300025KB操作系統20KB.絕對地址(或物理地址).絕對地址空間(或物理地址空間).相對地址(或邏輯地址).相對地址空間(或邏輯地址空間)單元地址：內存儲器由一個個存儲單元組成。一個存儲單元存放若干個二進制的位（bit），8個二進制的位被稱做一個字節（Byte）。內存中的存儲單元按一定的順序號進行編號，每個單元對應的編號，稱為該單元的單元地址。物理地址：在操作系統中，把單元地址稱為內存儲器的物理地址，也叫做絕對地址。物理地址空間：從任何一個絕對地址開始的一段連續的內存空間，被稱為物理地址空間，也稱為絕對地址空間。邏輯地址空間：用戶程序產生出一個相對于“0”編址的地址空間，這個地址空間被稱為是用戶程序的邏輯地址空間也稱為相對地址空間。邏輯地址：在邏輯地址空間中的地址被稱為邏輯地址也叫做相對地址。

要求編程人員熟悉內存使用情況，程序設計時要極小心地對待指令中的地址，不能夠出現任何差錯，否則后果不堪設想；3.2.2

地址定位方式和靜態重定位1.絕對定位方式

即在程序裝入內存之前，程序指令中的地址就已經是絕對地址，已經正確地反映了它將要進入的存儲區位置。..

優點：程序中的邏輯地址與實際內存中的物理地址完全相同。因此在程序執行前不需對程序指令中的地址再進行任何調整和修改，裝入到指定內存位置就可運行。.不適用于多道程序設計環境。缺點：(1)(2)(3)(4)程序進入內存后，不能做任何移動，只能固定在這個存儲區內；對程序做任何微小修改，都可能會牽扯到程序整體的變動，費工耗時；2.靜態重定位方式.

在多道程序設計環境下，用戶事先無法、也不愿意知道自己的程序會被裝入到內存的什么位置，他們只是向系統提供相對于“0”編址的程序。.

操作系統要有一個“重定位裝入程序”，功能是：一根據當前內存使用情況，為欲裝入的二進制目標程序分配所需的存儲區；二根據所分配的存儲區，對程序中的指令地址進行重新計算和修改；三將重定位后的二進制目標程序裝入到指定的存儲區中。靜態重定位由軟件（重定位裝入程序）實現，無須硬件提供支持；靜態重定位的特點靜態重定位是在程序運行之前完成地址重定位工作的；地址重定位的工作是在程序裝入時被一次集中完成的；

物理地址空間里的目標程序與原邏輯地址空間里的目標程序面目已不相同，前者是后者進行地址調整后的結果；

實施靜態重定位后，位于物理地址空間里的用戶程序不能在內存中移動，除非再重新進行地址定位；.

采用這種重定位方式，用戶向裝入程序提供相對于“0”編址的二進制目標程序，無需關注程序具體的裝入位置。通過重定位裝入程序的加工，目標程序進入分配給它的物理地址空間，程序指令中的地址也都被修改為正確反映該空間的情形。因為這種地址重定位是在程序執行前完成的，因此稱為地址的“靜態重定位”。.(1)(2)(3)(4)(5)(6)適用于多道程序設計環境。3.動態重定位方式

對用戶程序實行地址的靜態重定位后，定位后的程序就被“釘死”在了它的物理地址空間里，不能做任何移動。..

將地址定位的時間推遲到程序執行時再進行，這就是地址“動態重定位”方式。在對程序實行動態重定位時需要硬件的支持。

為阻止用戶程序指令中的地址闖入操作系統所占用的區域，在CPU里設置一個用于存儲保護的專用寄存器：“界限寄存器”。.

內存用戶區又被分為“使用區”和“空閑區”兩部分，分配給了用戶、但又未使用的區域稱為“內部碎片”。內部碎片的存在是對內存資源的一種浪費。3.2.3單一連續分區存儲管理1.2.單一連續分區存儲管理的基本思想單一連續區存儲管理的特點

總體上把內存儲器分為兩個分區：一個分區固定分配給操作系統使用；另一個分配給用戶使用，稱為“用戶區”。.....作業3作業2作業1操作系統用戶區內存0ab操作系統使用區內存0ab空閑區用戶區c操作系統使用區內存0ab空閑區ca界限寄存器系統總是把整個用戶區分配給一個用戶使用。這種系統只適用于單用戶（或單道）的情況。進入內存作業獨享系統中的所有資源，包括內存的整個用戶區。采用這種存儲分配策略時，將對用戶程序實行靜態重定位。.

作業比用戶區小時，就會形成碎片，造成內存儲器資源的浪費。3.單一連續分區管理的缺點..4.覆蓋技術

每次只能一個作業進入內存，故不適宜多道程序設計，系統的工作效率不高，資源利用率低下。若用戶作業的相對地址空間比用戶區大，該作業就無法運行?！案采w”是早期為程序設計人員提供的擴充內存的技術，中心思想是允許作業的若干個程序段使用同一個存儲區域，共用的存儲區被稱為“覆蓋區”。MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)MAIN(10KB)A(50KB)B(30KB)C(30KB)D(20KB)E(40KB)0180KB連接裝配10KB50KB40KB內存MAINA或BC或D或E5.對換技術作業1作業2作業3輔助存儲器內存儲器操作系統用戶區換出換入

基本思想：將作業都存放在輔存。每次只讓其中的一個進入內存投入運行。當運行中提出輸入輸出請求或分配給的時間片用完時，就把這個程序從內存“換出”到輔存，把輔存里的另一個作業“換入”運行，產生出“多道”的效果。3.2.4固定分區存儲管理1.基本思想

所謂“固定分區”存儲管理，是指預先把內存的用戶區劃分成若干個連續的分區，它們的尺寸可以相同，也可以不同。劃分后，內存中分區的個數以及每個分區的尺寸保持不變。每個分區里只允許裝入一個作業運行。2.對作業的組織操作系統第1分區(8KB)第2分區(32KB)第3分區(64KB)第4分區(132KB)0256KB20KBABCDEF操作系統第1分區(8KB)第2分區(32KB)第3分區(64KB)第4分區(132KB)0256KB20KBABCDEF.每個分區設置一個后備作業隊列.多個分區只設置一個后備作業隊列

一個作業到達時，總是進入到“能容納該作業的最小分區”的那個后備作業隊列里去排隊。

當某個分區空閑時，統一都到這一個隊列里去挑選作業，裝入運行。缺點：可能會產生有的分區隊列忙碌、有的分區隊列閑置的情形。作業尺寸比任何一個分區的長度都大時，就無法運行。..3.分區的分配與釋放.

分區空閑時，若它的隊列非空，就把該分區分配給隊列的第一個作業使用；作業運行完畢，收回該分區，進行下一次分配。每個分區設置一個后備作業隊列多個分區只設置一個后備作業隊列在任何一個分區釋放時，就根據分配方案從該隊列里挑選一個作業裝入運行。4.地址重定位與存儲保護在固定分區存儲管理中，實行靜態重定位。.

在固定分區存儲管理中，要防止用戶程序對操作系統的侵擾，也要防止用戶程序間的侵擾。因此設置一對專用寄存器：“低界限寄存器”和“高界限寄存器”，用于存儲保護。地址重定位存儲保護0abcdab作業1作業2作業3第1分區第2分區第3分區操作系統低界限寄存器高界限寄存器CPU5.固定分區存儲管理的特點與缺點.是最簡單的、具有“多道”色彩的存儲管理方案。.作業程序一次性全部裝入分配給它的連續分區。.實行的是靜態重定位。..會產生內部碎片，引起內存資源的浪費。

外部碎片：存儲管理中，把那些無法分配出去滿足作業存儲請求的空閑區稱為“外部碎片”。3.3.1可變分區存儲管理的基本思想3.3可變分區存儲管理1.基本思想2.

內、外部碎片

在作業要求裝入內存時，若當時內存中有足夠的存儲空間滿足該作業的需求，那就劃分出一個與作業相對地址空間同樣大小的分區分配給它使用。操作系統空閑區作業A(15KB)作業B(20KB)作業C(10KB)內存操作系統空閑區作業A(15KB)作業B(20KB)內存操作系統空閑區作業A(15KB)內存操作系統空閑區作業A(15KB)內存作業B(20KB)作業C(10KB)..

內部碎片：存儲管理中，把分配給了用戶而用戶未用的存儲區稱為“內部碎片”。3.實施可變分區存儲管理要解決的三個問題

.采用地址動態重定位技術，使程序能在內存中移動，為空閑區合并提供保證；.

記住各分區的使用情況，當一個分區被釋放時，要能判定它的前、后分區是否為空閑區。若是空閑區，就進行合并，形成一個大的空閑區。.給出分區分配算法，在有多個空閑區都滿足作業的存儲請求時，決定分配哪一個。.

靜態重定位是在程序運行之前完成地址轉換的；動態重定位卻是將地址轉換的時刻推遲到指令執行時進行。

實行靜態重定位，原來的指令地址部分被修改了；實行動態重定位，只是按照所形成的地址去執行這條指令，并不對指令本身做任何修改。

靜態重定位是在裝入時一次集中地把程序指令中所有要轉換的地址全部加以轉換；而動態重定位則是每執行一條指令時，對其地址加以轉換。

靜態重定位是由軟件完成地址轉換工作的；動態重定位則由一套硬件提供的地址轉換機構來完成。1.基本思想2.靜態和動態重定位的比較3.3.2地址的動態重定位

把相對地址空間中的用戶作業程序“原封不動”地裝入到分配給它的絕對地址空間中去。執行某條指令時，才根據當前程序所在區域，對指令中的地址進行重定位。即指令中地址的轉換是在程序執行時動態完成的，故稱為地址的“動態重定位”。0用戶作業A的相對地址空間XXXXXX1001KB2KB3000call1003KB0XXXXXX22KB+10023KB24KB22KB+3000call10025KB20KB22KB22KB定位寄存器2262822528操作系統內存...由地址變換線路取出

一是調度到某作業時，若系統的每個空閑區尺寸都小于它的需要，但空閑區總存儲量大于它的存儲請求，于是進行空閑區合并，得到一個大的空閑區，滿足該作業的需要；一是只要有作業運行完歸還所占用的存儲區，系統就進行空閑區的合并。

釋放區的前、后鄰接分區都是空閑區。因此，釋放區應該和前、后兩個鄰接的空閑區合并成一個新的空閑區。

釋放區的前鄰接分區是已分配區，后鄰接分區是空閑區。因此，釋放分區應該和后鄰接的空閑區合并成一個新的空閑區。

釋放分區的前鄰接分區是空閑區，后鄰接分區是已分配區。釋放區應該和前鄰接的空閑區合并成一個新的空閑區。

釋放分區的前、后鄰接分區都是已分配區，沒有合并的問題存在。3.3.3空閑區的合并1.前后相鄰接分區的四種關系2.空閑分區合并的時機已分配區空閑區釋放分區空閑區已分配區釋放分區空閑區空閑區釋放分區已分配區已分配區釋放分區....

若有作業運行結束，則根據作業名到已分配表里找到它的表目項，將該項的“狀態”改為“空”，隨之在空閑區表里尋找一個狀態為“空”的表目項，把釋放分區的信息填入，并將表目項狀態改為“空閑”。

作業提出存儲需求時，查空閑區表里狀態為“空閑”的表目項。若該項的尺寸能滿足所求，就將它一分為二：分配出去的那部分在已分配表里找一個狀態為“空”的表目項進行登記，剩下的部分仍在空閑區表里占據一個表目項。3.3.4分區的管理與組織方式1.表格法

設置兩張表：“已分配表”和“空閑區表”。其中“序號”是表目項的順序號，“起始地址”、“尺寸”、“狀態”都是該分區的相應屬性。由于系統中分區的數目是變化的，因此每張表格中的表目項數要足夠的多，暫時不用的表目項的狀態被設為“空”。內存操作系統空閑區(8KB)作業B(32KB)空閑區(32KB)作業D(120KB)空閑區(300KB)序號起始地址尺寸狀態12345020KB28KB60KB92KB212KB512KB28KB32KB作業B空空空92KB120KB作業D——————序號起始地址尺寸狀態1234560KB32KB作業B空閑空空——作業D20KB8KB212KB300KB——已分配表空閑區表...

例3-1在圖3-11的基礎上，現在到達一個作業E，存儲請求是30KB。試給出這時內存分區的劃分情形以及已分配表和空閑區表的變化。

把內存中每個空閑分區視為一個整體，在它里面開辟出兩個單元，一個存放該分區的長度（size），一個存放它下一個空閑分區的起址（next），操作系統開辟一個單元，存放第1個空閑分區的起址，這個單元稱為“鏈首指針”。最后一個空閑分區的next里存放標志“NULL”。這樣一來，系統里所有空閑分區被next連接成一個鏈表。從鏈首指針出發，順著各個空閑分區的next往下走，就能到達每一個空閑分區。20KB8KB60KB2.單鏈表法.sizenext空閑區長度下一個空閑區起址空閑區8KB212KB32KBNULL300KB20KB60KB空閑區(8KB)32KB212KB空閑區(32KB)300KBNULL空閑區(300KB)作業B(32KB)作業D(120KB)020KB28KB60KB92KB212KB512KB內存操作系統鏈首指針鏈首指針.基本思想

對提出的任何一個存儲請求，從空閑區鏈表首指針開始查看一個個空閑區。若有滿足要求的，按尺寸分配，調整next指針；若到達NULL未見滿足要求，則分配失敗。存儲分配.存儲釋放作業完成任務后，將占用的存儲區釋放，鏈入空閑區鏈表（要調整指針和空閑區合并）。

在每個空閑分區里，即存放下一個空閑區起址next，也存放它的上一個空閑區起址（prior）的信息。這樣，通過雙向鏈表，就可以方便地由next找到一個空閑區的下一個空閑區，也可以由prior找到一個空閑區的上一個空閑區。空閑區(300KB)sizenext.3.雙鏈表法基本思想20KB空閑區長度下一個空閑區起址空閑區300KBNULL作業B(32KB)作業D(120KB)020KB28KB60KB92KB212KB512KB內存操作系統鏈首指針prior上一個空閑區起址空閑區(32KB)32KB212KB60KB20KB空閑區(8KB)8KB60KBNULL.存儲合并

把釋放區鏈入空閑區雙向鏈表時，若通過它的prior發現該釋放區的前面一個空閑區的起址加上長度，等于釋放區的起址，那么說明它前面的空閑區與它直接鄰接，應該把這個釋放區與原先的空閑區合并。若釋放區起址加上長度正好等于next所指的下一個空閑區的起址，那么說明它與后面的空閑區直接鄰接，應該把這個釋放區與原先的空閑區合并。.空閑區的兩種組織形式

若將每個空閑分區按其起址由小到大排列在鏈表里，則把這種組織稱為“地址法”；若按每個空閑分區的長度由小到大排列在鏈表里，則把這種組織稱為“尺寸法”。

最先適應算法：總是把最先找到的、滿足存儲需求的那個空閑分區作為分配的對象。出發點盡量減少查找時間，有可能把大的空閑區分割許多小的分區，對大作業不利。3.3.5空閑分區的分配算法1.三種分配算法2.可變分區存儲管理的特點

最佳適應算法：總是從當前所有空閑區中找出一個能夠滿足存儲需求的、最小的空閑分區作為分配的對象。盡可能不把大的空閑區分割許多小的分區，保證大作業需要。

最壞適應算法：總是從當前所有空閑區中找出一個能夠滿足存儲需求的、最大的空閑分區作為分配的對象。出發點是照顧中、小作業的需求。...3.可變分區存儲管理的缺點..作業一次性地全部裝入到一個連續的存儲分區中。.

分區是按照作業對存儲的需求劃分的，因此不會出現內部碎片這樣的存儲浪費。.為確保作業能夠在內存中移動，要由硬件支持實行指令地址的動態重定位。.

只要作業的存儲需求大于系統提供的整個用戶區，該作業就無法投入運行。.

有可能出現極小的分區暫時分配不出去的情形，產生外部碎片。

由于是通過移動程序來達到分區合并的目的，勢必增加系統在這方面的時間投入與開銷?？勺兎謪^存儲管理特點：作業一次性地全部裝入到一個連續的存儲分區中。（缺點：無法解決大作業和小內存問題）避免了內部碎片。（缺點：導致外部碎片）采用動態地址重定位技術，可以使作業在內存中移動。（缺點：程序的移動增加了系統開銷）例3-2：如圖3-19（a）所示，現有兩個空閑分區。作業D到達，提出存儲需求20KB。試問：如果系統實行最先適應算法，應該把哪一個空閑分區分配給它？分配后的內存情形用圖示出。

地址法

尺寸法最佳適應算法分配結果，找滿足需要，最小的空閑區最壞適應算法分配結果，找滿足需要，最大的空閑區例3-3B請求240KB：3.3.6伙伴系統.伙伴系統是基于固定分區和可變分區提出的一種折中存儲管理方案。.在伙伴系統中，可用內存分區的大小為2K，L≤K≤U，其中：

2L表示分配的最小分區的尺寸；2U表示分配的最大分區的尺寸。C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初啟：A請求100KB：C請求64KB：D請求256KB：B釋放256KB：A釋放128KB：E請求128KB：C釋放64KB：E釋放128KB：D釋放256KB：有一個1MB內存，采用伙伴系統管理存儲空間的分配和回收。例：固定分區：限制可運行程序的道數，產生碎片，利用率低可變分區：按需求量劃分，能消除內部碎片，維護復雜。

用戶作業仍然相對于“0”進行編址，形成一個連續的相對地址空間。操作系統按照內存塊的尺寸對該空間進行劃分，每一個分區被稱為“頁”，編號從0開始。

用戶作業相對地址空間的劃分

把整個內存儲器劃分成大小相等的許多分區，每個分區稱為“塊”。比如把內存儲器劃分成n個分區，編號為0,1,2,…,n-1。塊是存儲分配的單位。3.4分頁式存儲管理3.4.1分頁式存儲管理的基本思想操作系統內存儲器作業A(第2頁)作業A(第0頁)作業A(第1頁)020KB24KB28KB32KB36KB40KB44KB48KB256KB(0~4塊)第5塊第6塊第7塊第8塊第9塊第10塊第11塊04KB8KB11KB12KB第0頁第1頁第2頁10921008(1,1092)(2,1008)51889200用戶作業A的相對地址空間1.內存的劃分2.3.相對地址的映射用戶相對地址空間中的每一個相對地址，都可以用數對“頁號，頁內位移”來表示。頁號：用戶程序相對地址空間中的n+1頁，按照0、1…n編號。塊號：內存絕對地址空間中的m+1塊，按照0、1…m編號。頁內位移：相對地址與所在頁的起始位置的之間的位移。塊內位移：絕對地址與所在頁的起始位置的之間的位移。（頁號，頁內位移）：用戶相對地址空間中的每一個相對地址，都可以用數對（頁號，頁內位移）來表示。（塊號，塊內位移）：內存絕對地址空間中的每一個絕對地址，都可以用數對（塊號，塊內位移）來表示。

用數對里的“頁號”2去查作業A的頁、塊對應關系表。

把內存第7塊的起始地址與頁內位移相加，就得到了相對地址3000現在的絕對地址，即7K+952=8120。

記錄作業A的頁、塊對應關系4.分頁式存儲管理的地址重定位用戶作業A的相對地址空間XXXXXXcall300001001KB2KB30003KB952第0頁第1頁第2頁內存儲器操作系統call3000作業A(第0頁)XXXXXX952作業A(第2頁)作業A(第1頁)04KB4KB+1005KB6KB7KB7KB+9528KB9KB10KB(0~3塊)第4塊第5塊第6塊第7塊第8塊第9塊(2,952)用戶作業A的頁、塊對應關系頁號塊號0124977K+952=8120...

運行到指令“call3000”時，把相對地址3000轉換成：(2，952)。計算公式是：頁號=相對地址/塊尺寸頁內位移=相對地址%塊尺寸..系統就去做指令“call8120”，從而得到了正確地執行。例題：一個實行分頁式存儲管理的系統，內存塊尺寸為2KB/塊?，F有一個用戶，其相對地址空間為0～5129字節。若將此作業裝入內存，計算系統產生多大的內存碎片，并判斷碎片的性質。分析步驟：第一步：用戶的相對地址空間的大??；5130第二步：求用戶的相對地址空間需要內存塊的個數；3x2048=6144第三步：內存塊中那塊產生了碎片，用塊大小減去產生碎片的頁的大小。6144-5130=1014

利用內存記錄作業頁、塊對應關系的表，就是“頁表”。每個作業都有自己的頁表。作業相對地址空間有多少頁，頁表就有多少個表項。為了地址轉換，硬件設置一個專用寄存器：“頁表控制寄存器”。進程調度時，把調度到作業的頁表起址和長度放入寄存器中，達到映射不同作業地址的目的。3.4.2分頁式存儲管理的地址轉換1.數對(頁號，頁內位移)的形成

把塊(或頁)的尺寸限定只能是2的方冪，那么利用計算機系統設定的地址結構，很容易得到相對地址所對應的數對(頁號，頁內位移)。015014013012111010191817061514130201000150140130121110101918170615141302010001501401301211101019181706151413020100頁號(2)頁內位移(952)頁號(11)頁內位移(184)2.頁表與快表.利用內存構成頁表操作系統內存儲器塊號頁內位移絕對地址頁表起始地址長度頁表控制寄存器頁號頁內位移相對地址CPU(1)地址3000的二進制表示地址轉換過程(2)

頁表存放在內存，增加了系統在存儲上的花銷，還降低了CPU的訪問速度。因為每次對某一地址的訪問，先要訪問內存中的頁表，形成絕對地址后，才能進行所需的真正訪問。因此，以前只須一次訪問就能實現的操作，現在要兩次訪問內存才能實現。

實現頁表的另一方法是用一組快速硬件寄存器構成公用頁表。調度到誰就把誰的頁表裝入該組寄存器中。這樣硬件把頁號與寄存器組中所有表項同時并行比較，立即輸出與頁號匹配的塊號。這時無須訪問內存，并且通過并行匹配直接完成地址變換，因此速度很快。.操作系統內存儲器塊號頁內位移絕對地址快速寄存器組頁號頁內位移相對地址CPU快速寄存器組(1)(2)快速寄存器價格昂貴，完全由它來組成頁表的方案是不可取的。.頁表/快表

考慮到大多數程序在一次運行時，傾向于在少數頁面中進行頻繁訪問（即程序的“局部性”原理），因此在實際系統中采用內存頁表與快速寄存器組結合的解決方案，且只用極少幾個快速寄存器來構成寄存器組，起名為：“相聯寄存器”，或簡稱“快表”。(1)

快表中只存部分頁表。把一個相對地址劃分出數對：（頁號，頁內位移）后，系統先通過頁號與快表中的所有表項進行并行比較。若發現了匹配的頁，則將塊號直接取出，不再通過頁表。用該塊號與頁內位移拼接，形成所需要的絕對地址。(2)

作業長度不可能是頁面尺寸的整數倍，平均說，分給作業的最后內存塊會浪費掉一半。若內存中有n個作業，頁面尺寸為p個字節，那么內存中就有n*p/2個字節被浪費掉。所以，頁面尺寸要小。

當快表中沒有匹配的頁號時，地址轉換機構按普通訪問頁表的方式工作，獲得所需的絕對地址；再把這個頁號與塊號的對應關系送入快表保存，以便下一次進行地址轉換時能夠命中。若快表里沒有空表項，則要先刪除快表中的一個表項，然后將新的頁表表項替換進去。頁表控制寄存器操作系統內存儲器塊號頁內位移絕對地址快表頁號頁內位移相對地址長度起始地址頁表(3).命中率

直接查快表就能實現內存訪問的成功率為“命中率”。命中率越高，性能就越好。表中給出了平均命中率與相聯寄存器個數的關系。從表中可以看出，設置快表，確實能夠達到提高地址轉換速度的目的。相聯寄存器個數平均命中率8121685%93%97%.3.關于頁面尺寸的討論.

頁面尺寸小，用戶作業相對地址空間的頁面數就增加，頁表就會加大。因此，從減少頁表所需內存開銷看，頁面尺寸應該大一些為好。選擇最佳頁面尺寸，可能需在幾個相互矛盾的因素間折中求得。3.4.3內存塊的分配與回收1.對內存塊的管理..存儲分塊表單鏈表操作系統作業C第2頁作業B第0頁作業A第0頁空閑塊作業A第2頁空閑塊空閑塊作業B第1頁空閑塊空閑塊作業A第1頁作業C第3頁作業C第0頁作業C第1頁空閑塊內存儲器064K空閑塊鏈表起址塊號狀態0已分配1已分配2已分配3已分配4空閑5已分配6空閑7空閑8已分配9空閑10空閑11已分配12已分配13已分配14已分配15空閑空閑塊總數：6

系統維持一張表格，表格表項與內存中的一塊相對應，記錄該的塊使用情況。只要表格中“空閑塊總數”記錄的數目大于請求的存儲量，就可進行分配，并把分配出去的塊的狀態改為“已分配”。作業完成后歸還存儲塊時，就把表中相應塊的狀態改為“空閑”。單鏈表存儲分塊表

把空閑塊鏈接成一個單鏈表加以管理，系統必須設置一個空閑塊鏈表的起始地址指針，以便進行存儲分配時能夠找到空閑的內存塊。無論是進行空閑塊的分配還是作業完成后歸還存儲塊，都要調整空閑塊間的鏈表指針。.

假定當前的內存儲器使用情況，如圖所示。.

作業雖然不占據連續的存儲區，但每次仍要求一次全部進入內存。因此，如果作業很大，其存儲需求大于內存，那么還是存在小內存不能運行大作業的問題。

用戶作業的相對地址空間按照塊的尺寸劃分成頁。這種劃分是在系統內部進行的，用戶感覺不到，即對用戶是“透明”的。2.分頁式存儲管理的特點..內存存儲器事先被劃分成相等尺寸的塊，它是進行存儲分配的單位。..

相對地址空間中的頁可以進入內存中的任何一個空閑塊，并且分頁式存儲管理實行的是動態重定位，因此它打破了一個作業必須占據連續存儲空間的限制，作業在不連續的存儲區里，也能夠得到正確的運行。3.分頁式存儲管理的缺點平均每一個作業要浪費半頁大小的存儲塊。.位圖

用二進制位與內存塊的使用建立起關系，為“0”，表示對應塊空閑；為“1”，表示對應塊已分配。1111010010011110空閑塊總數：60123456701字節號位號位圖

獨立的地址空間有助于實施對過程和數據的共享，不必在每一個用戶作業的地址空間里都必須有相關的備份。

每個程序段是一個獨立的邏輯實體（比如一個過程、一個數組或一個堆棧），因此可以對它們進行不同類型的存儲保護。

每個程序段是一個獨立的地址空間，它們可獨自增長或減小而不用顧及別的程序段，不會影響到其他程序段的地址空間。

所謂“分段式”存儲管理，即要求用戶將自己的作業程序以多個相互獨立的稱為“段”的地址空間提交給系統，每個段都是一個從“0”開始的一維地址空間，長度不一。操作系統按照段長為作業分配內存空間。

改變某程序段尺寸，就會影響其他無關程序段的起址；對某個程序段進行修改，會影響到其他相關部分，就可能要對所有的程序重新進行鏈接編輯。3.5分段式存儲管理3.5.1分段及二維邏輯地址空間1.一維地址空間組織方式的缺點.不利于按照程序段的性質，實施存儲保護和共享。..2.分段式存儲管理的含義3.分段式組織方式的優點..

在編譯過程中會建立很多表，其中主要有：供打印程序清單的源程序文檔；由變量名及其屬性組成的符號表；由程序中所有的整型、實型常量組成的常量表；包含程序語法分析結果的語法分析樹；內部過程調用時使用的堆棧。

通過編譯程序在編譯過程中建立的各種表，說明頁式及段式存儲管理中，作業程序地址空間組織形式的不同。例：解：..在分頁式管理時，這5個表必須限定在一個一維的地址空間里，如圖(a)所示。使用使用使用使用使用空閑空閑空閑空閑堆棧語法分析樹常量表源程序文檔符號表(a)0KB4KB8KB12KB16KB20KB0KB4KB8KB12KB符號表段00KB源程序文檔常量表段1段3段40KB4KB8KB12KB16KB語法分析樹0KB4KB8KB12KB堆棧段2(b).

在分段管理時，是把這些表視為一個個相互獨立的地址空間，比如：段0、段1等，它們組成了整個用戶的地址空間，如圖(b)所示。

系統為每個用戶作業設置一個段表，用于記錄各段在內存中的存放信息。邏輯空間中有多少段，段表里就有多少個表項。每個表項通常包括的信息有段號、段長、該段在內存的基址（即起始地址）等。

如果段號s大于段表長度，表示該地址越界出錯；否則以此段號為索引查段表，得到該段在內存的基址。

硬件要提供一個段表基址寄存器。每當重新調度時，就把調度到的作業的段表起址及段表長度（即段表中表項的個數）放入寄存器中，從而達到映射不同作業的目的。.

在分段式存儲管理時，要指示存儲空間里的一個地址，必須提供兩部分內容：段號和段內位移。即邏輯地址應該是二維的：[段號，段內位移]。.

在圖(a)所示的32位地址結構中，各用16個二進制位表示段號s和段內位移d，因此表示用戶的邏輯地址空間最多可以有216個段，每段最大長度是64KB。3116150sd段號段內位移ds段號段內位移0312322(a)(b).

圖(b)所示的32位的地址結構中，由于用9個二進制位表示段號s，用23個二進制位表示段內位移d，因此表示允許用戶的邏輯地址空間中最多可以有29個段，每段的最大長度是223=8192KB。..分段式存儲管理時的地址轉換步驟如下：.(1)從相對地址數對：[段號s，段內位移d]中提取出段號s，用來進行地址轉換。(2)(3)由段的基址和段內位移d拼裝出所需的物理地址，實現對內存的訪問。3.5.2段表及地址變換過程段號(s)段內位移(d)相對地址段表段表基址寄存器段號長度基址基址段內位移物理地址段sd內存程序分段地址轉換機制.分段地址轉換機制圖示例：

在分段式存儲管理中，某作業的段表如下。有該作業的六個邏輯地址為：[0，430]、[3，400]；[1，10]、[2，2500]、[4，42]、[1，11]。求對應的物理地址。段號段長基址

06002191142300210090358013274961954解：

對不同邏輯地址中的段號，有結果如下：（1）[0，430]的物理地址是219+430=649；（2）[3，400]的物理地址是1327+400=1727；（3）[1，10]的物理地址是2300+10=2310；（4）由邏輯地址知，是要訪問第2段位于2500處的元素。但第2段的段長是100，表明所要訪問的段內位移越界出錯；（5）[4，42]的物理地址是1954+42=1996；（6）[1，11]的物理地址是2300+11=2311。3.5.3存儲保護與共享

在分頁式環境下，存儲保護只能以頁面為單位。在頁表的每一個表項里，設置一個所謂的“保護位”，該位的不同取值表示對應的頁幀是可讀、可寫或只可讀等。分頁式存儲管理中的存儲保護與共享.1..

被共享的程序文本部分不一定正好劃分在一個或幾個完整的頁面中，有可能一個頁面中既有允許共享的內容，又有不能共享的私有數據。因此，在分頁式環境下實現頁面的共享比較困難，但也不是不可能。進程A的邏輯地址空間進程B的邏輯地址空間進程C的邏輯地址空間ed10ed21ed32dataA3ed10ed21ed32dataB3ed10ed21ed32dataC3進程A的頁表031426320314263203142632頁號幀號進程B的頁表頁號幀號進程C的頁表頁號幀號操作系統0123456789101112dataAed1ed2ed3dataBdataC內存.

假定分頁式存儲管理的頁幀尺寸為50KB，那么文本編輯程序被劃分成3頁，用戶進程的數據段被劃分成一頁，合起來每個用戶進程的邏輯地址空間為4頁。.

三個進程的邏輯地址空間和相應的頁表，0~2頁都劃歸文本編輯程序（即ed1，ed2，ed3），頁表中的0~2表項都對應于頁幀號3、4和6；進程的數據頁（即dataA、dataB、dataC）都位于自己空間的第3頁，分別存放在內存的2、8和11頁幀。81111文本編輯程序段0程序段段1數據段段2進程A的邏輯地址空間文本編輯程序段0程序段段1數據段段2進程B的邏輯地址空間堆棧段段30252861基址243062操作系統內存進程A的段表段號段長0252861基址243062進程B的段表段號段長3A的數據段文本編輯程序B的數據段A的程序段B的堆棧段43062B的程序段分段式存儲管理中的存儲保護與共享2..

在分段式環境下，段是有完整意義的邏輯信息單位，因此對段中的所有內容可以采用相同的方式使用。.

為實行存儲保護，在段表表項里增加權限位，指出每段是可讀、可寫或只執行等信息。每次進行地址映射時，都將這次訪問的類型與權限位比較，若不符合就產生出錯中斷。.

在分段式存儲管理中很容易實現段的共享，只需在有關作業的段表中增加一個表項，讓其基址指向共享段在內存中的起始地址即可。.

進程A和B要共享文本編輯程序，就可把文本編輯程序作為它們地址空間中的段0。假定文本編輯程序存放在內存43062起始的連續分區里，那么在所對應的各段表中，段號為0的表項的基址都是43062，從而達到共享該文本編輯程序的目的。(1)

頁是信息的物理單位，段是信息的邏輯單位：系統根據內存塊的尺寸劃分頁，不考慮頁中的信息是否完整。因此，一頁對應的是信息的一個物理單位；段是基于用戶程序結構提出的存儲管理模式，用戶知道自己的程序分多少段，每段在邏輯上都是相對完整的一組信息。所以，段是信息的邏輯單位。(2)

頁的尺寸由系統確定，段的尺寸因段而異：實行分頁式存儲管理的系統，頁的尺寸是由系統確定的，它與內存頁幀的大小相同。段的長度取決于用戶編寫的程序，不同的段有不同的長度。

(3)

頁式地址空間是一維的，段式地址空間是二維的：在分頁式存儲管理時，用戶必須通過鏈接編輯程序，把各程序段鏈接成一個相對于0編址的一維線性空間，用戶向系統提供的是一個一維的邏輯地址空間；在分段式存儲管理時，用戶不把各程序段連接成一個相對于0編址的一維線性空間，各程序段之間是通過[段號，段內位移]進行訪問的。因此，用戶向系統提供的是一個二維的邏輯地址空間。3.5.4分段與分頁的區別

.

形式上看，分段式與分頁式存儲管理有很多相似之處。比如，一個為（頁號，頁內位移），一個為[段號，段內位移]；一個有頁表，一個有段表；如此等等。不過它們卻是兩個完全不同的概念。.分段與分頁的主要區別3.6虛擬存儲與請求頁式存儲管理3.6.1虛擬存儲的概念1.作業程序不必全部在內存

由于程序執行具有“局部性”，因此實際運行時，沒有必要把全部信息都放在內存里。只要合理組織，調度恰當，在發現所需訪問的信息不在內存時，能夠找到它，能夠把它調入內存，那么不僅可以保證作業的正確執行，而且還提高了系統的資源利用率，使得系統具有更高的運行效率。2.虛擬存儲的概念

作業提交給系統時，先進入輔存。運行時，只將部分信息裝入內存，大部分仍保存在輔存中。運行過程中需要用到不在內存的信息時，再把它們調入，以保證程序的正常運行。這樣一個被用戶認為有的、但實際上不存在的“大”存儲器，就被稱為“虛擬存儲器”。..

虛擬存儲器是一種擴大內存容量的設計技術，它把輔存作為計算機內存的后援。在虛擬存儲意義下，用戶作業的相對地址空間，就是系統提供給他的虛擬存儲器。在多道程序設計環境下，每個用戶都有自己的虛擬存儲器。在提供虛擬存儲管理的系統里，把用戶作業的相對地址空間稱為“虛擬地址空間”，里面的地址稱為“虛擬地址”。

把內存劃分成尺寸相同、位置固定的塊。然后按照內存塊的大小，把作業的虛擬地址空間（即以前的相對地址空間）劃分成頁。由于頁的尺寸與塊一樣，因此虛擬地址空間中的一頁，可以裝入到內存中的任何一塊中。3.6.2

請求分頁式存儲管理的基本思想最多可有2048頁每頁1KB第0頁第1頁第2頁虛擬存儲器第2045頁第2046頁第2047頁第0塊第1塊第2塊第29塊第30塊第31塊內存儲器1.與分頁式相同處2.與分頁式不同處

作業全部進入輔存。運行時，只裝入要用的若干頁，其他頁仍在輔存。運行過程中，虛擬地址被轉換成數對：(頁號，頁內位移)。由頁號查頁表，若該頁在內存，運行就進行下去；若該頁不在內存，表明“缺頁”，運行無法繼續。這時，就根據頁號把該頁從輔存調入內存。所謂“請求分頁式”，即是當運行中需要某頁時，再把它從輔存調入內存使用的意思。

中斷處理程序查存儲分塊表，找空閑塊；根據頁在輔存的位置，啟動磁盤讀信息。

2173.6.3缺頁中斷的處理1.頁表表項中的“缺頁中斷位”頁號塊號缺頁中斷位輔存地址

在請求分頁式存儲管理中，是由頁表表目項的“缺頁中斷位”來判斷所需頁是否在內存的。該位為“1”，表示此頁在內存；為“0”，表示不在內存，并發出“缺頁”中斷信號，以求得系統的處理。2.缺頁中斷處理過程作業2虛擬地址空間05184KB8KB830012KBcall8300第0頁第1頁第2頁XXXXXX205114012操作系統第7塊作業2的頁表內存儲器作業2第2頁

根據執行指令中的虛擬地址，（頁號，頁內位移）。用頁號去查頁表，判斷該頁是否在內存。

若該頁缺頁中斷位為“0”，產生缺頁中斷，進行中斷處理。

把從磁盤上讀出的信息裝入到分配的內存塊中。

修改頁表中相應的表目內容，修改存儲分塊表里相應表目的狀態。

在完成所需頁面的裝入后，返回原指令重新執行。①②③④⑤⑥(1)(2)(3)(4)(5)(6)

假定一個作業運行的頁面走向中涉及的頁面總數為A，其中有F次缺頁，必須通過缺頁中斷把它們調入內存。定義：

f=F/A稱f為“缺頁中斷率”。顯然，缺頁中斷率與缺頁中斷的次數有密切的關系。

缺頁中斷處理完成后，仍返回到原指令去重新執行，因為那條指令并未執行。而一般中斷則是返回到下一條指令去執行，因為這條指令已經執行完畢了。

缺頁中斷是在執行一條指令時產生的中斷，并立即轉去處理;一般中斷則是在一條指令執行完后，發現有中斷請求時才去響應和處理。3.缺頁中斷與一般中斷的區別..4.頁面走向和缺頁中斷率

作業運行時，虛擬地址在隨時發生變化，它是程序的執行軌跡，是程序的一種動態特征。由于每個虛擬地址都與一個數對：（頁號，頁內位移）相對應，因此這種動態特征可以用程序執行時頁號的變化來描述。通常，稱一個程序執行過程中頁號的變化序列為“頁面走向”。所給程序的頁面走向是：0、1、0、2、0、1，涉及的頁面總數是6.。..用戶作業程序100LOAD1#,1120104ADD1#,2410108STORE1#,1124虛擬地址100112010424101081124數對：(頁號,頁內位移)(0,100)(1,96)(0,104)(2,362)(0,108)(1,100)頁面走向010201

程序1按行對a的元素初始化，缺頁中斷進一頁，就能完成對a一行元素的初始化。a共128行，需128次缺頁中斷將它們調入，完成對a的初始化。程序2按列對a的元素初始化。通過缺頁中斷進來一頁，只能對a的一行的一個列元素初始化。于是，每列元素的初始化，須128次缺頁中斷才完成。程序2需128×128

=

16384次缺頁中斷，才能完成a的初始化工作。

要把128×128的數組元素初始化為“0”。數組中的每個元素占一個字。若頁面尺寸為128字，規定數組按行存放，系統只給該作業2個內存塊：一個存程序，另一個用于數組初始化。開始時，程序已在內存塊，數據未進入。試問下面給出的兩個程序在運行時各會發生多少次缺頁中斷？

頁面尺寸：頁面尺寸是與塊尺寸相同的，因此塊大頁也就大。頁面增大了，在每個內存塊里的信息相應增加，缺頁的可能性下降。反之，頁面尺寸減少，每塊里的信息減少，缺頁的可能性上升。

分配給作業的內存塊數：由于分配給作業的內存塊數多，同時能夠裝入內存的作業頁面就多，缺頁的可能性下降，發生缺頁中斷的可能性也就下降。影響缺頁中斷次數的因素.(1)程序的實現：作業程序的編寫方法，對缺頁中斷產生的次數也會有影響。(2)(3)例：程序1： 程序2：main() main(){ {inta[128][128]; inta[128][128];inti,j; inti,j;for(i=0;i<128;i++) for(j=0;j<128;j++)for(j=0;j<128;j++) for(i=0;i<128;i++)a[i][j]=0; a[i][j]=0;} }解：

改變位：該位為“0”時，表示此頁面在內存時數據未被修改過；為“1”時，表示被修改過。當其為淘汰對象時，根據此位的取值來確定是否要進行磁盤回寫操作。

引用位：在系統規定的時間間隔內，該頁是否被引用過的標志（該位在頁面淘汰算法中將會用到）。3.6.4頁面淘汰算法1.幾個問題.

頁面淘汰：缺頁時，要從輔存把所需頁面調入內存。若當時內存有空閑塊，那么不會有什么問題；若當時內存中已沒有空閑塊，那就必須在內存中選擇一頁，把它調出內存，以便為即將調入的頁面讓出塊空間。這就是所謂的“頁面淘汰”。.

缺頁中斷與頁面淘汰的關系：頁面淘汰是由缺頁中斷引起的，但缺頁中斷不一定引起頁面淘汰。只有當內存中沒有空閑塊時，缺頁中斷才會引起頁面淘汰。.

抖動：若一個剛被淘汰出去的頁，時隔不久因要訪問它，又從輔存調入。調入后不久又被淘汰，再訪問，再調入。如此頻繁地反復進行，使得整個系統一直陷于頁面的調入、調出，大部分CPU時間都用于處理缺頁中斷和頁面淘汰上，很少顧及到用戶作業的實際計算。這種現象被稱為“抖動”或稱為“顛簸”。.

頁表表目的變動：選中了一個淘汰的頁面，若該頁面在內存時未被修改過，就可直接用調入的頁面將其覆蓋；若該頁面在內存時被修改過，就必須把它回寫到磁盤，以更新該頁在輔存上的副本。一個頁面在內存時是否被修改過，可通過頁表表目反映。頁號塊號缺頁中斷位輔存地址引用位改變位(1)(2)

比如，作業的頁面走向為：

1、2、3、4、1、2、5、1、2、3、4、5即作業運行時，先用到第1頁，再用到第2頁、第3頁和第4頁等。頁面走向中涉及的頁面總數為12。

先進先出(FIFO)頁面淘汰算法的基本思想是：當要進行頁面淘汰時，總是把最早進入內存的頁面作為淘汰對象。2.先進先出頁面淘汰算法123412555344123412225331234111255√√√123412512345√√√√√√頁面走向3個內存塊缺頁計數：缺頁中斷率：f=9/12=75%..

由于3個內存塊中沒有第4頁，因此要通過缺頁中斷將其調入。但供該作業使用的3個內存塊全部分配，必須進行頁面淘汰才能讓所需的第4頁進來。可以看出，前面3個缺頁中斷沒有引起頁面淘汰，現在這個缺頁中斷引起了頁面淘汰。.

假定只分給該作業3個內存塊使用。開始時作業程序全部在輔存，3個內存塊都為空。運行后，通過3次缺頁中斷，把第1、第2、第3三個頁面分別從輔存調入內存塊中。當頁面走向到達4時，用到第4頁。.

根據FIFO的淘汰原則，應該把第一個進來的第1頁淘汰出去。緊接著用到第1頁，它不在內存的三個塊中，于是要把第2頁淘汰出去，讓第1頁進來，等等。..

對于所給的頁面走向，它涉及到的頁面總數為12，通過缺頁中斷調入頁面的次數是9（因為“缺頁計數”欄中有9個勾），因此它的缺頁中斷率f是：

f

=

9/12

=

75%.

這種算法把進入內存的頁面按進入先后次序組成鏈表。選擇淘汰對象時，考查鏈表的第1個頁面，檢查它的“引用位（R）”。若R位為“0”，表示上一次頁面淘汰以來，它沒有被引用過，因此可以把它立即淘汰；若R位為“1”，表示上一次頁面淘汰以來，它被引用過，因此暫時不淘汰它，而是將R位修改為“0”，然后排到鏈表的最后，繼續在鏈表上搜索符合條件的淘汰對象。FIFO的著眼點是，認為在內存中存放時間最長的頁面，被訪問的可能性最小。在實際中，就可能把經常要訪問的頁面淘汰出去。為盡量避免出現這種情形，提出了對它的改進：“第二次機會頁面淘汰算法”。.ABCDEFGH鏈表首指針鏈表尾指針R=1ABCDEFGH鏈表首指針鏈表尾指針R=0(a)(b)插入到隊列最后AGJDBCLKHIFE指針移動方向頁面失效時，考察指針所指頁面，根據R位采取動作：R=0時替換該頁；R=1時清零，往下考察

第二次機會頁面淘汰算法把在內存中的頁面組織成一個鏈表來管理，頁面要在鏈表中經常移動，從而影響系統的效率。..

可把頁面組織成循環鏈表的形式，類似于時鐘，用一個指針指向當前最先進入內存的頁面。發生缺頁中斷并要求頁面淘汰時，先檢查指針指向的頁面的R位。它實際上是第二次機會頁面淘汰算法的變形，有時稱為“時鐘頁面淘汰算法”。

最近最少用（LFU）頁面淘汰算法的著眼點是考慮內存塊里頁面的使用頻率，認為在一段時間里使用得最多的頁面，將來用到的可能性就大。因此，進行頁面淘汰時，總是把當前使用得最少的頁面淘汰出去。為此，為每個在內存中的頁面設置一個計數器。產生缺頁中斷時，把計數器取值最小的那個頁面淘汰出去。3.最近最久未用頁面淘汰算法

最近最久未用(LRU)頁面淘汰算法的著眼點是在頁面淘汰時，檢查可淘汰對象的被訪問時間，總是把最長時間未被訪問過的頁面淘汰出去。即該算法認為若一個頁面剛被訪問過，那么不久的將來被訪問的可能性就大；否則被訪問的可能性就小。123412512345123412512341234125123√√√123412512345√√√√√√頁面走向3個內存塊缺頁計數：√缺頁中斷率：f=10/12=83%4.最近最少用頁面淘汰算法5.最優頁面淘汰算法

已知一個作業的頁面走向，那么在進行頁面淘汰時，把以后不再使用的或在最長時間內不會用到的頁面淘汰出去，這樣所引起的缺頁中斷次數肯定最小。這就是所謂的“最優（OPT）頁面淘汰算法”。

遺憾的是，OPT的前提是要已知作業運行時的頁面走向，這根本不可能做到，所以OPT頁面淘汰算法沒有實用價值，它只能用來作為一個標桿（或尺度），與別的淘汰算法進行比較。..

內存塊為3時缺頁中斷率f

=

9/12；內存塊為4時缺頁中斷率f

=

10/12。也就是說，對于這個頁面走向，FIFO頁面淘汰算法會出現異常現象。

它不僅打破了占據連續存儲區的禁錮，而且也打破了要求作業全部進入內存的禁錮。由于它能夠向用戶作業提供虛擬存儲器，從而解決了小內存大作業的矛盾。6.異?，F象7.請求頁式存儲管理的特點

對FIFO頁面淘汰算法，有時增加分配給作業的可用內存塊數，它的缺頁次數反而上升。通常把這稱為“異?，F象”。8.請求頁式存儲管理的缺點432143555211432143335224321444355√√√432143543215√√√√√√頁面走向3個內存塊缺頁計數：√缺頁中斷率：f=9/12=75%4321115432154322215432144321543√√√432143543215√√√√√√頁面走向4個內存塊缺頁計數：缺頁中斷率：f=10/12=83%44333215432.

它有分頁式存儲管理的所有特點。.

平均每個作業要浪費半頁大小的存儲塊。也就是說，請求分頁式存儲管理會產生內部碎片。

某作業頁面走向是4、3