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

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

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

D.光盤

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總體上把內(nèi)存儲(chǔ)器分為兩個(gè)分區(qū)：一個(gè)分區(qū)固定分配給操作系統(tǒng)使用；另一個(gè)分配給用戶使用，稱為“用戶區(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)總是把整個(gè)用戶區(qū)分配給一個(gè)用戶使用。這種系統(tǒng)只適用于單用戶（或單道）的情況。進(jìn)入內(nèi)存作業(yè)獨(dú)享系統(tǒng)中的所有資源，包括內(nèi)存的整個(gè)用戶區(qū)。采用這種存儲(chǔ)分配策略時(shí)，將對(duì)用戶程序?qū)嵭徐o態(tài)重定位。.

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

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

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

所謂“固定分區(qū)”存儲(chǔ)管理，是指預(yù)先把內(nèi)存的用戶區(qū)劃分成若干個(gè)連續(xù)的分區(qū)，它們的尺寸可以相同，也可以不同。劃分后，內(nèi)存中分區(qū)的個(gè)數(shù)以及每個(gè)分區(qū)的尺寸保持不變。每個(gè)分區(qū)里只允許裝入一個(gè)作業(yè)運(yùn)行。2.對(duì)作業(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.每個(gè)分區(qū)設(shè)置一個(gè)后備作業(yè)隊(duì)列.多個(gè)分區(qū)只設(shè)置一個(gè)后備作業(yè)隊(duì)列

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

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

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

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

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

內(nèi)、外部碎片

在作業(yè)要求裝入內(nèi)存時(shí)，若當(dāng)時(shí)內(nèi)存中有足夠的存儲(chǔ)空間滿足該作業(yè)的需求，那就劃分出一個(gè)與作業(yè)相對(duì)地址空間同樣大小的分區(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)部碎片：存儲(chǔ)管理中，把分配給了用戶而用戶未用的存儲(chǔ)區(qū)稱為“內(nèi)部碎片”。3.實(shí)施可變分區(qū)存儲(chǔ)管理要解決的三個(gè)問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

地址法

尺寸法最佳適應(yīng)算法分配結(jié)果，找滿足需要，最小的空閑區(qū)最壞適應(yīng)算法分配結(jié)果，找滿足需要，最大的空閑區(qū)例3-3B請(qǐng)求240KB：3.3.6伙伴系統(tǒng).伙伴系統(tǒng)是基于固定分區(qū)和可變分區(qū)提出的一種折中存儲(chǔ)管理方案。.在伙伴系統(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請(qǐng)求100KB：C請(qǐng)求64KB：D請(qǐng)求256KB：B釋放256KB：A釋放128KB：E請(qǐng)求128KB：C釋放64KB：E釋放128KB：D釋放256KB：有一個(gè)1MB內(nèi)存，采用伙伴系統(tǒng)管理存儲(chǔ)空間的分配和回收。例：固定分區(qū)：限制可運(yùn)行程序的道數(shù)，產(chǎn)生碎片，利用率低可變分區(qū)：按需求量劃分，能消除內(nèi)部碎片，維護(hù)復(fù)雜。

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

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

把整個(gè)內(nèi)存儲(chǔ)器劃分成大小相等的許多分區(qū)，每個(gè)分區(qū)稱為“塊”。比如把內(nèi)存儲(chǔ)器劃分成n個(gè)分區(qū)，編號(hào)為0,1,2,…,n-1。塊是存儲(chǔ)分配的單位。3.4分頁式存儲(chǔ)管理3.4.1分頁式存儲(chǔ)管理的基本思想操作系統(tǒng)內(nèi)存儲(chǔ)器作業(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的相對(duì)地址空間1.內(nèi)存的劃分2.3.相對(duì)地址的映射用戶相對(duì)地址空間中的每一個(gè)相對(duì)地址，都可以用數(shù)對(duì)“頁號(hào)，頁內(nèi)位移”來表示。頁號(hào)：用戶程序相對(duì)地址空間中的n+1頁，按照0、1…n編號(hào)。塊號(hào)：內(nèi)存絕對(duì)地址空間中的m+1塊，按照0、1…m編號(hào)。頁內(nèi)位移：相對(duì)地址與所在頁的起始位置的之間的位移。塊內(nèi)位移：絕對(duì)地址與所在頁的起始位置的之間的位移。（頁號(hào)，頁內(nèi)位移）：用戶相對(duì)地址空間中的每一個(gè)相對(duì)地址，都可以用數(shù)對(duì)（頁號(hào)，頁內(nèi)位移）來表示。（塊號(hào)，塊內(nèi)位移）：內(nèi)存絕對(duì)地址空間中的每一個(gè)絕對(duì)地址，都可以用數(shù)對(duì)（塊號(hào)，塊內(nèi)位移）來表示。

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

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

記錄作業(yè)A的頁、塊對(duì)應(yīng)關(guān)系4.分頁式存儲(chǔ)管理的地址重定位用戶作業(yè)A的相對(duì)地址空間XXXXXXcall300001001KB2KB30003KB952第0頁第1頁第2頁內(nèi)存儲(chǔ)器操作系統(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的頁、塊對(duì)應(yīng)關(guān)系頁號(hào)塊號(hào)0124977K+952=8120...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

每個(gè)程序段是一個(gè)獨(dú)立的地址空間，它們可獨(dú)自增長(zhǎng)或減小而不用顧及別的程序段，不會(huì)影響到其他程序段的地址空間。

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

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

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

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

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

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

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

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

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

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

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

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

06002191142300210090358013274961954解：

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

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

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

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

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

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

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

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

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

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

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

(3)

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

.

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

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

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

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

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

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

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

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

2173.6.3缺頁中斷的處理1.頁表表項(xiàng)中的“缺頁中斷位”頁號(hào)塊號(hào)缺頁中斷位輔存地址

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

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

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

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

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

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

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

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

缺頁中斷處理完成后，仍返回到原指令去重新執(zhí)行，因?yàn)槟菞l指令并未執(zhí)行。而一般中斷則是返回到下一條指令去執(zhí)行，因?yàn)檫@條指令已經(jīng)執(zhí)行完畢了。

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

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

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

=

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

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

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

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

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

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

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

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

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

比如，作業(yè)的頁面走向?yàn)椋?/p>

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

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

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

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

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

對(duì)于所給的頁面走向，它涉及到的頁面總數(shù)為12，通過缺頁中斷調(diào)入頁面的次數(shù)是9（因?yàn)椤叭表撚?jì)數(shù)”欄中有9個(gè)勾），因此它的缺頁中斷率f是：

f

=

9/12

=

75%.

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

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

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

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

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

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

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

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

=

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

=

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

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

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

它有分頁式存儲(chǔ)管理的所有特點(diǎn)。.

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

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