操作系統(tǒng)四版課件3

第3章存儲管理3.13.23.3本章講述內(nèi)容：3.4存儲管理綜述；

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

D.光盤

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

3.1存儲管理綜述3.1.1存儲器的層次結(jié)構(gòu)

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

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

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

這種層次結(jié)構(gòu)中，容量較大、價格便宜的慢速存儲器（如磁盤），可作為容量較小、價格較貴的快速存儲器的后備。這正是存儲管理中虛擬存儲技術(shù)的實現(xiàn)基礎(chǔ)。

這種層次結(jié)構(gòu)中，CPU可直接到寄存器、高速緩沖存儲器、內(nèi)存儲器這三層上訪問數(shù)據(jù)，不能直接到磁盤和磁帶上訪問數(shù)據(jù)，那里的數(shù)據(jù)只有轉(zhuǎn)移到內(nèi)存儲器后，才能接受CPU的處理。.3.1.2高速緩沖存儲器的工作原理高速緩沖存儲器CPU主存儲器字傳送塊傳送

相對于內(nèi)存，高速緩存容量小、存取速度快。在它里面只存放內(nèi)存中的一小部分?jǐn)?shù)據(jù)內(nèi)容。.

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

當(dāng)CPU試圖訪問內(nèi)存中的某一個字時，就總是先檢查該字是否在高速緩存中。如果在，就直接將它從高速緩存?zhèn)魉徒oCPU；如果不在，則先把內(nèi)存中包含此字在內(nèi)的一塊數(shù)據(jù)讀入高速緩存，然后再把所需的字從高速緩存?zhèn)魉徒oCPU。槽號標(biāo)簽012C-10123塊塊（K個字）2n-1塊（K個字）地址高速緩沖存儲器主存儲器

內(nèi)存和高速緩存間是以“塊”為單位傳遞數(shù)據(jù)的，高速緩存與CPU之間則是以“字”為單位傳遞數(shù)據(jù)的。..

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

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

這是存儲管理必須承擔(dān)的任務(wù)，它應(yīng)該隨時記錄內(nèi)存的使用情況；根據(jù)用戶程序的需要分配存儲區(qū)；在用戶程序運行完后，及時收回存儲區(qū)，以提高內(nèi)存的使用效率。內(nèi)存的分配與回收2.存儲保護和共享

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

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

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

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

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

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

地址定位方式和靜態(tài)重定位1.絕對定位方式

即在程序裝入內(nèi)存之前，程序指令中的地址就已經(jīng)是絕對地址，已經(jīng)正確地反映了它將要進入的存儲區(qū)位置。..

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

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

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

物理地址空間里的目標(biāo)程序與原邏輯地址空間里的目標(biāo)程序面目已不相同，前者是后者進行地址調(diào)整后的結(jié)果；

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

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

對用戶程序?qū)嵭械刂返撵o態(tài)重定位后，定位后的程序就被“釘死”在了它的物理地址空間里，不能做任何移動。..

將地址定位的時間推遲到程序執(zhí)行時再進行，這就是地址“動態(tài)重定位”方式。在對程序?qū)嵭袆討B(tài)重定位時需要硬件的支持。

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

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

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

作業(yè)比用戶區(qū)小時，就會形成碎片，造成內(nèi)存儲器資源的浪費。3.單一連續(xù)分區(qū)管理的缺點..4.覆蓋技術(shù)

每次只能一個作業(yè)進入內(nèi)存，故不適宜多道程序設(shè)計，系統(tǒng)的工作效率不高，資源利用率低下。若用戶作業(yè)的相對地址空間比用戶區(qū)大，該作業(yè)就無法運行?！案采w”是早期為程序設(shè)計人員提供的擴充內(nèi)存的技術(shù)，中心思想是允許作業(yè)的若干個程序段使用同一個存儲區(qū)域，共用的存儲區(qū)被稱為“覆蓋區(qū)”。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內(nèi)存MAINA或BC或D或E5.對換技術(shù)作業(yè)1作業(yè)2作業(yè)3輔助存儲器內(nèi)存儲器操作系統(tǒng)用戶區(qū)換出換入

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

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

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

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

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

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

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

內(nèi)、外部碎片

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

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

.采用地址動態(tài)重定位技術(shù)，使程序能在內(nèi)存中移動，為空閑區(qū)合并提供保證；.

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

靜態(tài)重定位是在程序運行之前完成地址轉(zhuǎn)換的；動態(tài)重定位卻是將地址轉(zhuǎn)換的時刻推遲到指令執(zhí)行時進行。

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

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

靜態(tài)重定位是由軟件完成地址轉(zhuǎn)換工作的；動態(tài)重定位則由一套硬件提供的地址轉(zhuǎn)換機構(gòu)來完成。1.基本思想2.靜態(tài)和動態(tài)重定位的比較3.3.2地址的動態(tài)重定位

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

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

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

釋放區(qū)的前鄰接分區(qū)是已分配區(qū)，后鄰接分區(qū)是空閑區(qū)。因此，釋放分區(qū)應(yīng)該和后鄰接的空閑區(qū)合并成一個新的空閑區(qū)。

釋放分區(qū)的前鄰接分區(qū)是空閑區(qū)，后鄰接分區(qū)是已分配區(qū)。釋放區(qū)應(yīng)該和前鄰接的空閑區(qū)合并成一個新的空閑區(qū)。

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

若有作業(yè)運行結(jié)束，則根據(jù)作業(yè)名到已分配表里找到它的表目項，將該項的“狀態(tài)”改為“空”，隨之在空閑區(qū)表里尋找一個狀態(tài)為“空”的表目項，把釋放分區(qū)的信息填入，并將表目項狀態(tài)改為“空閑”。

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

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

例3-1在圖3-11的基礎(chǔ)上，現(xiàn)在到達(dá)一個作業(yè)E，存儲請求是30KB。試給出這時內(nèi)存分區(qū)的劃分情形以及已分配表和空閑區(qū)表的變化。

把內(nèi)存中每個空閑分區(qū)視為一個整體，在它里面開辟出兩個單元，一個存放該分區(qū)的長度（size），一個存放它下一個空閑分區(qū)的起址（next），操作系統(tǒng)開辟一個單元，存放第1個空閑分區(qū)的起址，這個單元稱為“鏈?zhǔn)字羔槨?。最后一個空閑分區(qū)的next里存放標(biāo)志“NULL”。這樣一來，系統(tǒng)里所有空閑分區(qū)被next連接成一個鏈表。從鏈?zhǔn)字羔槼霭l(fā)，順著各個空閑分區(qū)的next往下走，就能到達(dá)每一個空閑分區(qū)。20KB8KB60KB2.單鏈表法.sizenext空閑區(qū)長度下一個空閑區(qū)起址空閑區(qū)8KB212KB32KBNULL300KB20KB60KB空閑區(qū)(8KB)32KB212KB空閑區(qū)(32KB)300KBNULL空閑區(qū)(300KB)作業(yè)B(32KB)作業(yè)D(120KB)020KB28KB60KB92KB212KB512KB內(nèi)存操作系統(tǒng)鏈?zhǔn)字羔樻準(zhǔn)字羔?基本思想

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

在每個空閑分區(qū)里，即存放下一個空閑區(qū)起址next，也存放它的上一個空閑區(qū)起址（prior）的信息。這樣，通過雙向鏈表，就可以方便地由next找到一個空閑區(qū)的下一個空閑區(qū)，也可以由prior找到一個空閑區(qū)的上一個空閑區(qū)?？臻e區(qū)(300KB)sizenext.3.雙鏈表法基本思想20KB空閑區(qū)長度下一個空閑區(qū)起址空閑區(qū)300KBNULL作業(yè)B(32KB)作業(yè)D(120KB)020KB28KB60KB92KB212KB512KB內(nèi)存操作系統(tǒng)鏈?zhǔn)字羔榩rior上一個空閑區(qū)起址空閑區(qū)(32KB)32KB212KB60KB20KB空閑區(qū)(8KB)8KB60KBNULL.存儲合并

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

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

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

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

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

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

只要作業(yè)的存儲需求大于系統(tǒng)提供的整個用戶區(qū)，該作業(yè)就無法投入運行。.

有可能出現(xiàn)極小的分區(qū)暫時分配不出去的情形，產(chǎn)生外部碎片。

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

地址法

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

2L表示分配的最小分區(qū)的尺寸；2U表示分配的最大分區(qū)的尺寸。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內(nèi)存，采用伙伴系統(tǒng)管理存儲空間的分配和回收。例：固定分區(qū)：限制可運行程序的道數(shù)，產(chǎn)生碎片，利用率低可變分區(qū)：按需求量劃分，能消除內(nèi)部碎片，維護復(fù)雜。

用戶作業(yè)仍然相對于“0”進行編址，形成一個連續(xù)的相對地址空間。操作系統(tǒng)按照內(nèi)存塊的尺寸對該空間進行劃分，每一個分區(qū)被稱為“頁”，編號從0開始。

用戶作業(yè)相對地址空間的劃分

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

用數(shù)對里的“頁號”2去查作業(yè)A的頁、塊對應(yīng)關(guān)系表。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

假定當(dāng)前的內(nèi)存儲器使用情況，如圖所示。.

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

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

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

用二進制位與內(nèi)存塊的使用建立起關(guān)系，為“0”，表示對應(yīng)塊空閑；為“1”，表示對應(yīng)塊已分配。1111010010011110空閑塊總數(shù)：60123456701字節(jié)號位號位圖

獨立的地址空間有助于實施對過程和數(shù)據(jù)的共享，不必在每一個用戶作業(yè)的地址空間里都必須有相關(guān)的備份。

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

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

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

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

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

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

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

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

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

硬件要提供一個段表基址寄存器。每當(dāng)重新調(diào)度時，就把調(diào)度到的作業(yè)的段表起址及段表長度（即段表中表項的個數(shù)）放入寄存器中，從而達(dá)到映射不同作業(yè)的目的。.

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

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

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

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

06002191142300210090358013274961954解：

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

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

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

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

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

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

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

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

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

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

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

(3)

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

.

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

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

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

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

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

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

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

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

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

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

根據(jù)執(zhí)行指令中的虛擬地址，（頁號，頁內(nèi)位移）。用頁號去查頁表，判斷該頁是否在內(nèi)存。

若該頁缺頁中斷位為“0”，產(chǎn)生缺頁中斷，進行中斷處理。

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

修改頁表中相應(yīng)的表目內(nèi)容，修改存儲分塊表里相應(yīng)表目的狀態(tài)。

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

假定一個作業(yè)運行的頁面走向中涉及的頁面總數(shù)為A，其中有F次缺頁，必須通過缺頁中斷把它們調(diào)入內(nèi)存。定義：

f=F/A稱f為“缺頁中斷率”。顯然，缺頁中斷率與缺頁中斷的次數(shù)有密切的關(guān)系。

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

缺頁中斷是在執(zhí)行一條指令時產(chǎn)生的中斷，并立即轉(zhuǎn)去處理;一般中斷則是在一條指令執(zhí)行完后，發(fā)現(xiàn)有中斷請求時才去響應(yīng)和處理。3.缺頁中斷與一般中斷的區(qū)別..4.頁面走向和缺頁中斷率

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

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

=

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

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

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

分配給作業(yè)的內(nèi)存塊數(shù)：由于分配給作業(yè)的內(nèi)存塊數(shù)多，同時能夠裝入內(nèi)存的作業(yè)頁面就多，缺頁的可能性下降，發(fā)生缺頁中斷的可能性也就下降。影響缺頁中斷次數(shù)的因素.(1)程序的實現(xiàn)：作業(yè)程序的編寫方法，對缺頁中斷產(chǎn)生的次數(shù)也會有影響。(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”時，表示此頁面在內(nèi)存時數(shù)據(jù)未被修改過；為“1”時，表示被修改過。當(dāng)其為淘汰對象時，根據(jù)此位的取值來確定是否要進行磁盤回寫操作。

引用位：在系統(tǒng)規(guī)定的時間間隔內(nèi)，該頁是否被引用過的標(biāo)志（該位在頁面淘汰算法中將會用到）。3.6.4頁面淘汰算法1.幾個問題.

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

缺頁中斷與頁面淘汰的關(guān)系：頁面淘汰是由缺頁中斷引起的，但缺頁中斷不一定引起頁面淘汰。只有當(dāng)內(nèi)存中沒有空閑塊時，缺頁中斷才會引起頁面淘汰。.

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

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

比如，作業(yè)的頁面走向為：

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

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

由于3個內(nèi)存塊中沒有第4頁，因此要通過缺頁中斷將其調(diào)入。但供該作業(yè)使用的3個內(nèi)存塊全部分配，必須進行頁面淘汰才能讓所需的第4頁進來?？梢钥闯觯懊?個缺頁中斷沒有引起頁面淘汰，現(xiàn)在這個缺頁中斷引起了頁面淘汰。.

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

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

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

f

=

9/12

=

75%.

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

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

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

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

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

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

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

內(nèi)存塊為3時缺頁中斷率f

=

9/12；內(nèi)存塊為4時缺頁中斷率f

=

10/12。也就是說，對于這個頁面走向，F(xiàn)IFO頁面淘汰算法會出現(xiàn)異?，F(xiàn)象。

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

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

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

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

某作業(yè)頁面走向是4、3