操作系統(tǒng)原理第3章-存儲管理

第三章存儲管理1計算機存儲器分類外存UserOS內(nèi)存計算機系統(tǒng)工作中心2本章要點存儲管理任務(wù)：分配、映射、保護、共享內(nèi)存劃分與分配技術(shù)：靜態(tài)、動態(tài)程序裝入技術(shù)簡單存儲管理技術(shù)虛擬存儲管理技術(shù)33.1存儲管理的任務(wù)存儲分配地址映射存儲保護（MemoryProtection）存儲共享（MemorySharing）4存儲分配基本任務(wù)：管理內(nèi)存空間的分配與回收（1）分配基本內(nèi)存空間（2）增加新的內(nèi)存空間--動態(tài)申請或釋放內(nèi)存空間（3）回收內(nèi)存空間5用于內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)如：位視圖、空閑頁框表等。記載哪些內(nèi)存被分配給那個進程，哪些內(nèi)存空間是空閑的信息。若系統(tǒng)采用虛擬存儲管理技術(shù)，還需要登記進程的程序和數(shù)據(jù)中，哪些部分還在內(nèi)存，哪些部分尚在外存等信息。這些數(shù)據(jù)結(jié)構(gòu)自身需要占用一定的內(nèi)存空間，也需要系統(tǒng)花費額外的時間進行維護。6存儲分配步驟首先，根據(jù)系統(tǒng)的內(nèi)存分配算法，在空閑的內(nèi)存分區(qū)中尋找到一塊滿足進程需要的內(nèi)存空間，將其分配給進程。然后，更新進程的資源分配清單、內(nèi)存分配情況清單等數(shù)據(jù)結(jié)構(gòu)。7內(nèi)存的回收更新相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，將回收的內(nèi)存空間標識為“空閑可用”。？該內(nèi)存空間是否可以被回收？被其他進程共享？屬于相應(yīng)的進程？與相鄰的空閑空間進行合并8地址映射邏輯地址，或相對地址：一般從0開始編址物理地址，或絕對地址：標識內(nèi)存中的每個存儲單元。進程控制塊程序數(shù)據(jù)棧進程控制信息程序入口點地址值增加進程映像分支指令訪問數(shù)據(jù)當前棧頂圖3.1進程執(zhí)行時的尋址9？邏輯地址高級語言或匯編語言使用符號地址：變量名或標號源程序經(jīng)過編譯、鏈接以后，其中的符號地址就會變成數(shù)字式的邏輯地址。編譯/鏈接程序會自動計算每一個變量或標號所對應(yīng)的邏輯地址是多少。10靜態(tài)映射：靜態(tài)重定位地址映射：程序裝入內(nèi)存以后，由操作系統(tǒng)將邏輯地址邏輯地址+起始地址，得到實際的物理地址。重定位（Relocation）：對目標程序中的指令和數(shù)據(jù)地址進行修改的過程。靜態(tài)映射實現(xiàn)簡單。地址變換只在程序裝入是一次完成，程序運行時不再改變。但不適合多道程序系統(tǒng)：不允許系統(tǒng)執(zhí)行內(nèi)存的碎片整理；無法實現(xiàn)虛擬存儲。11動態(tài)映射：動態(tài)重定位定義：操作系統(tǒng)將程序裝入內(nèi)存以后，并不立即把目標程序中的邏輯地址轉(zhuǎn)換為物理地址，而是在處理機執(zhí)行每一條指令時進行地址轉(zhuǎn)換。復(fù)雜、費時為了系統(tǒng)效率，處理機中設(shè)置了專門的高速硬件，自動完成地址轉(zhuǎn)換，這樣的硬件被稱作地址管理部件，如下圖。12CPU中的地址管理部件CPU地址管理部件程序指令邏輯地址物理地址地址總線圖3.2CPU中的地址管理部件工作示意圖13存儲保護防止地址越界，防止操作越權(quán)。地址越界：進程訪問不屬于自己的地址空間，或進程在運行時所產(chǎn)生的物理地址超越其自身的地址空間范圍。--可能侵犯其他用戶進程空間，也可能侵犯操作系統(tǒng)的存儲空間操作越權(quán)：進程對共享存儲區(qū)的操作違反了系統(tǒng)規(guī)定的權(quán)限14存儲保護的實現(xiàn)存儲保護只能在進程執(zhí)行過程中動態(tài)地進行，不能在運行前一次性靜態(tài)完成。若采用動態(tài)映射動態(tài)計算物理地址，可能計算出錯誤地址；若采用靜態(tài)映射，進程執(zhí)行過程中也可能出錯，從而導(dǎo)致地址越界或操作越權(quán)。為提高系統(tǒng)效率，存儲保護的主要工作必須由高速的專用硬件完成：在地址管理部件中。15存儲共享為了進程通信和節(jié)約內(nèi)存空間，兩個或多個進程共用內(nèi)存中相同的分區(qū)，即他們的物理空間有相交的部分。可以共享進程的代碼，也可以共享進程數(shù)據(jù)。一般地，進程之間共享代碼的目的主要是為了節(jié)約存儲空間，共享數(shù)據(jù)的目的主要是為了實現(xiàn)進程間相互通信。16存儲共享示意圖PCB3數(shù)據(jù)代碼PCB2代碼數(shù)據(jù)PCB1數(shù)據(jù)代碼進程1進程2進程3圖3.3進程之間共享代碼和數(shù)據(jù)17存儲共享實現(xiàn)通信的模式通過存儲共享完成通信的過程：一個進程將數(shù)據(jù)寫入共享存儲區(qū)，另一個進程從共享存儲區(qū)中讀出數(shù)據(jù)。18共享代碼程序可重入：設(shè)計程序時，邏輯上將程序代碼區(qū)和數(shù)據(jù)區(qū)分開。代碼區(qū)不包含運行程序時需要改變的數(shù)據(jù)，被處理的數(shù)據(jù)都放在獨立的數(shù)據(jù)區(qū)。這樣，進程執(zhí)行過程中就不會改變代碼部分的任何內(nèi)容。數(shù)據(jù)區(qū)是單獨的一個段、堆棧式動態(tài)申請的分區(qū)，或通過參數(shù)傳遞。19共享代碼—實現(xiàn)過程創(chuàng)建新進程時，不需要為該進程的代碼部分另外申請內(nèi)存空間，只需將該進程PCB中的進程代碼空間的地址指向已有的代碼空間地址。進程的數(shù)據(jù)區(qū)，要么等到操作系統(tǒng)為其分配相應(yīng)存儲空間以后，將數(shù)據(jù)區(qū)地址填寫在PCB中；要么由進程運行時向操作系統(tǒng)動態(tài)申請。20共享代碼—實質(zhì)可以將進程的代碼視為處理數(shù)據(jù)的一組規(guī)則或公式，這一組規(guī)則或公式存儲在內(nèi)存中的某個分區(qū)。進程的執(zhí)行：利用這一組規(guī)則或公式來完成數(shù)據(jù)的運算。多個進程共享代碼：多個進程需要使用同一組規(guī)則或公式處理不同的數(shù)據(jù)。PCB：告訴進程其所需的規(guī)則或公式以及需要處理的數(shù)據(jù)存儲在哪里，進程的進度等信息。21共享代碼—高級語言程序編程對于高級程序的設(shè)計而言，只要相應(yīng)的編譯程序支持可重入的程序設(shè)計，那么，設(shè)計程序時就不需要考慮程序的可重入問題，不需要將程序代碼和數(shù)據(jù)嚴格分開。編譯程序在編譯時，會自動將欲處理的數(shù)據(jù)與程序代碼分開存儲，以保證代碼部分是純的、可重入的。22存儲擴充內(nèi)存：速度快、容量小、價格貴。外存：容量大、速度慢、價格便宜。目的：在多道程序系統(tǒng)中能運行更多、更大的程序，降低系統(tǒng)的造價，提高系統(tǒng)的性價比。存儲擴充：采用軟件手段，在硬件的配合下，將部分外存空間虛擬為內(nèi)存空間，并將內(nèi)存和外存有機地結(jié)合起來，得到一個容量相當于外存、速度接近于內(nèi)存、價格十分便宜的虛擬存儲系統(tǒng)。23存儲擴充—虛擬存儲實現(xiàn)過程虛擬存儲系統(tǒng)在邏輯上對外是一個整體，用戶感覺到系統(tǒng)提供了一個非常大的“內(nèi)存”空間。操作系統(tǒng)負責完成內(nèi)存與外存之間的透明切換：進程運行時將需要的數(shù)據(jù)或代碼從外存裝入內(nèi)存，并將內(nèi)存中暫時不用的部分交換到外存。243.2內(nèi)存劃分與分配技術(shù)25內(nèi)存劃分靜態(tài)劃分：劃分預(yù)先進行，創(chuàng)建新進程時，在內(nèi)存中找到一個合適的分區(qū)分配給它。動態(tài)劃分：系統(tǒng)初始化時，可以將整個內(nèi)存的用戶區(qū)看作一個分區(qū)。創(chuàng)建新進程時，根據(jù)進程申請的空間大小，在這個分區(qū)中動態(tài)地為之劃分一部分空間。26靜態(tài)劃分必須事先進行，一旦劃分完畢，分區(qū)的大小和數(shù)目將不再改變。可以劃分：大小相同/不同的分區(qū)，如固定分區(qū)和分頁。固定分區(qū)：根據(jù)系統(tǒng)管理員的經(jīng)驗和一些統(tǒng)計規(guī)律，事先將內(nèi)存空間劃分為若干個固定大小的分區(qū)，稱為分區(qū)(Partitioning)。當進程申請存儲空間時，系統(tǒng)為之分配一個大小合適的空閑分區(qū)。27靜態(tài)劃分（續(xù)）分頁：特殊的靜態(tài)分區(qū)，需要事先將內(nèi)存空間劃分為若干個大小相同的分區(qū)，稱為頁框，或幀（frame）。當進程申請存儲空間時，系統(tǒng)可以為之分配多個空閑頁框。28固定分區(qū)劃分：等長8MB8MB8MB8MB8MB操作系統(tǒng)8MB(a)等長分區(qū)圖3.4固定分區(qū)劃分29固定分區(qū)：等長—總結(jié)所有分區(qū)的長度相同。優(yōu)點：分配簡單，只要進程大小不超過分區(qū)大小，就可以裝到任何一個分區(qū)中運行。浪費存儲空間。若進程申請的存儲空間很小，卻需要占用整個分區(qū)，分區(qū)內(nèi)存在不可用的浪費空間，稱為內(nèi)零頭—碎片（internalfragmentation）。無法運行超過分區(qū)大小的程序。無法精確確定分區(qū)的大小。30固定分區(qū)劃分：異長圖3.4固定分區(qū)劃分操作系統(tǒng)8MB2MB8MB4MB12MB20MB(b)異長分區(qū)31固定分區(qū)：異長將內(nèi)存空間劃分為若干個長度不同的分區(qū)，以適合于不同大小的進程需要既提高存儲空間的利用率、減少浪費，又使長進程能裝入運行。但是，確定每個分區(qū)的大小也是一件十分困難的事情。32固定分區(qū)特點管理簡單，只需要建立一張分區(qū)使用表，登記分區(qū)的使用情況。（等長分區(qū)只需要標明分區(qū)狀態(tài)是已分配/空閑）分區(qū)號(可省略)大小起始地址狀態(tài)12040未分配25060已分配350110未分配4100160已分配5200260已分配33固定分區(qū)：分配首先，檢索分區(qū)使用表，從中找出一個尚未分配的、能滿足大小且內(nèi)零頭最小的分區(qū)。若分區(qū)使用表中的分區(qū)按從小到大的順序排列，則分配時，從表中的第一個表項開始查找，找到的第一個尚未分配并滿足大小的分區(qū)即是最佳的分區(qū)。將分區(qū)使用表中該分區(qū)的狀態(tài)修改為已分配。若找不到大小足夠的分區(qū)，則系統(tǒng)將拒絕運行該進程，或采用其它技術(shù)進行處理，如覆蓋技術(shù)等。34固定分區(qū)總結(jié)固定分區(qū)存在內(nèi)零頭，浪費存儲空間：異長分區(qū)較等長分區(qū)可以一定程度上提高系統(tǒng)的性能，但并不能徹底解決問題。35分頁式劃分（Paging）為了提高內(nèi)存資源的利用率，可以考慮將分區(qū)長度縮小，減少內(nèi)零頭浪費的空間。但是，這樣做必須有一個前提，即進程可以分配若干不連續(xù)的存儲空間。否則，小分區(qū)可能使更多的進程無法裝入內(nèi)存。分頁劃分：系統(tǒng)預(yù)先將內(nèi)存空間劃分為若干較小的、固定大小的頁框。36分頁式劃分示意圖150213內(nèi)存頁框號圖3.5分頁式劃分37分頁式劃分特點頁框較小，有效地減少了內(nèi)零頭的浪費每個進程平均浪費0.5頁框大小。頁框大小固定，簡化了存儲分配。需要記錄內(nèi)存頁框的分配和使用情況：位示圖、空閑頁框表或空閑頁框鏈表等。38分頁：數(shù)據(jù)結(jié)構(gòu)—位示圖位示圖：是一個由0、1構(gòu)成的向量，其中每一位(bit)表示一個頁框的使用狀態(tài)。一般規(guī)定，0表示頁框空閑，1表示頁框已被分配。假定存儲空間被劃分為n個頁框，所有頁框依次編號為0,1,2,…,n-1，則記錄所有頁框的使用狀態(tài)的位示圖形如：000001110111111111110001111…00111139分頁：數(shù)據(jù)結(jié)構(gòu)—空閑頁框表空閑頁框表：以表格形式記載內(nèi)存頁框的使用情況。顯然，為每一個空閑頁框設(shè)置一個表項是不合理的，這將導(dǎo)致頁框表太大?？梢詾橐唤M連續(xù)的空閑頁框設(shè)置一個表項，其中主要包括：首頁框號和頁框個數(shù)，如表3.2所示。40空閑頁框表首頁框號頁框個數(shù)501002203030080450210表3.2空閑頁框表41分頁：數(shù)據(jù)結(jié)構(gòu)—總結(jié)位示圖和空閑頁框表都需要占用專門的存儲空間空閑頁框鏈表：是將內(nèi)存中所有的空閑頁框通過其內(nèi)的鏈接指針連成一個鏈表，系統(tǒng)只需要記錄鏈表頭的位置。為進程分配存儲空間時，從鏈表頭開始取所需的頁框，同時更新鏈表頭?；厥者M程釋放的存儲空間時，將新產(chǎn)生的空閑頁框鏈接到空閑頁框鏈表中。42動態(tài)劃分與分配算法靜態(tài)劃分未考慮進程的實際需要。無論是固定分區(qū)，還是分頁，都存在不同程度的內(nèi)零頭。動態(tài)劃分：根據(jù)進程的實際需要，動態(tài)地劃分內(nèi)存空間，并分配給進程，徹底解決了內(nèi)零頭問題。系統(tǒng)初始化時，內(nèi)存用戶區(qū)就是一個大分區(qū)。隨著進程的創(chuàng)建和撤消，內(nèi)存被動態(tài)劃分成若干較小的分區(qū)。43動態(tài)劃分（續(xù)）例如，如圖3.6有一個128MB的內(nèi)存，其中操作系統(tǒng)自身占用8MB，剩下的120MB空間供用戶進程使用。依次裝入進程P1、P2、P3、P4、P5、P6，剩下一個10MB的空閑分區(qū)。一段時間之后，進程P1、P3、P5執(zhí)行結(jié)束，釋放出3個空閑分區(qū)。內(nèi)存中共有4個空閑分區(qū)，44圖3.6動態(tài)劃分內(nèi)存空間的過程(a)分配之前OS8MB120MB(b)分配之后OS8MBP210MBP140MBP410MBP320MBP620MBP510MB10MB(c)P1、P3、P5結(jié)束OS8MBP210MBP410MBP620MB40MB20MB10MB10MB例：動態(tài)劃分45動態(tài)劃分—空閑分區(qū)表可見，動態(tài)分區(qū)的分區(qū)長度和數(shù)目都是可變的。為了實施存儲分配，系統(tǒng)必須維護一張空閑分區(qū)表，登記內(nèi)存中的各個空閑分區(qū)?？臻e分區(qū)首址空閑分區(qū)長度80120270404009051020046外零頭—獨立小分區(qū)：緊湊動態(tài)劃分技術(shù)解決了靜態(tài)劃分技術(shù)的內(nèi)零頭?？赡墚a(chǎn)生很多較小的分區(qū)：外零頭(ExternalFragment)。緊湊(Compaction)：把內(nèi)存中的所有空閑分區(qū)拼接成一個較大的空閑分區(qū)。即把內(nèi)存中的所有進程移到內(nèi)存的某一端；所有空閑分區(qū)移到另一端例如，將如圖3.7(a)所示的內(nèi)存空間進行緊湊以后的效果見圖3.8所示。47圖3.8利用緊湊技術(shù)消除外零頭(a)緊湊之前24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB(b)緊湊以后64MBOS8MBP716MBP210MBP410MBP610MB緊湊技術(shù)示意圖48動態(tài)劃分—分配算法采用動態(tài)劃分技術(shù)，為進程分配存儲空間的過程較復(fù)雜。當系統(tǒng)中有多個滿足進程大小的空閑分區(qū)時，如何為進程選擇一個分區(qū)合適的分區(qū)呢？目前幾種較典型的分區(qū)分配方案：49首次適應(yīng)算法

(FFA：FirstFitAlgorithm)基本思想：總是從內(nèi)存的某一端（一般從低地址端）開始查找，選擇一個超過進程申請大小的空閑分區(qū)。為此，可以將空閑分區(qū)表中登記的空閑分區(qū)按照其起始地址由小到大的次序依次排列。系統(tǒng)查找空閑分區(qū)時，從表頭開始查找，取第一個滿足要求的分區(qū)分配給進程。50首次適應(yīng)算法（續(xù)）

(FFA：FirstFitAlgorithm)若找到的空閑分區(qū)恰好與進程申請的存儲空間大小相等，或分配給該進程以后，僅剩下一個非常小的空間（小于系統(tǒng)設(shè)置的閾值），則將該分區(qū)全部分配給申請進程。否則，系統(tǒng)將該分區(qū)劃分為兩個分區(qū)，一個分區(qū)的長度等于進程申請的空間大小，并將其分配給申請進程。然后，將另一個子分區(qū)鏈接到空閑分區(qū)鏈表中。51首次適應(yīng)算法—總結(jié)

(FFA：FirstFitAlgorithm)優(yōu)點：盡量使用低地址空間，因而在高地址的空間可能會保留較大的空閑分區(qū)。所以，大進程申請的存儲空間大都能在高地址端得到滿足。缺點：由于每次只簡單地使用找到的第一個分區(qū)，結(jié)果可能導(dǎo)致將較大的空閑分區(qū)不斷地分割為較小的空閑分區(qū)。52下次適應(yīng)算法

(NFA:Next-FitAlgorithm)首次適應(yīng)算法每次都從低地址端開始查找空閑分區(qū)，總是頻繁使用內(nèi)存的某一端，某些大進程申請的大分區(qū)需要很長時間才能在內(nèi)存的另一端找到。能否均衡使用整個內(nèi)存空間，加快大分區(qū)的查找速度呢？下次適應(yīng)算法能記住上次分配分區(qū)的位置，下一次實施分配時，從上一次的分配位置之后開始查找，選擇一個大小足夠的空閑分區(qū)。

53下次適應(yīng)算法—總結(jié)

(NFA:Next-FitAlgorithm)該算法常常會導(dǎo)致內(nèi)存中缺乏大分區(qū)，因為它會均衡地利用空閑分區(qū)，包括分割較大的空閑分區(qū)。從而使得大進程無法裝入內(nèi)存運行。下次適應(yīng)算法可能會導(dǎo)致大量的外零頭，需要較頻繁地實施緊湊操作。54最佳適應(yīng)算法

(BFA：BestFitAlgorithm)總是選擇滿足申請要求且長度最小的空閑分區(qū)。為了提高查找效率，可以將所有的空閑分區(qū)按照長度由小到大的次序依次排列在空閑分區(qū)表中。為進程分配存儲空間時，從表頭開始查找，第一個滿足進程申請存儲空間大小的分區(qū)就是最適合的分區(qū)。55最佳適應(yīng)算法—總結(jié)

(BFA：BestFitAlgorithm)優(yōu)點：盡量不分割大的空閑分區(qū)缺點：可能會形成大量較小的、難以再分配的分區(qū)——大量的外零頭。最佳適應(yīng)算法并非是最好的算法。56最差適應(yīng)算法

(WFA：WorstFitAlgorithm)選擇滿足申請要求且長度最大的空閑分區(qū)，使分割出來的剩余空閑分區(qū)較大。為了提高系統(tǒng)效率，可將系統(tǒng)中所有的空閑分區(qū)按照長度由大到小的次序依次排列在空閑分區(qū)表中。為進程分配存儲空間時，從表頭開始查找，選擇第一個滿足進程需要的分區(qū)。如果第一個空閑分區(qū)小于進程申請空間的大小，則不能立即為進程分配存儲空間。57最差適應(yīng)算法—總結(jié)

(WFA：WorstFitAlgorithm)優(yōu)點：可以避免形成大量較小外零頭，但它總是分割大的空閑分區(qū)。當遇到大進程申請大空間時，無法找到一個足夠大的空閑分區(qū)。注意：在大進程面前，內(nèi)存中所謂的較大空閑分區(qū)也是外零頭了。58例如當系統(tǒng)進行到如圖3.6(c)所示的情形時，若有一個進程P7申請大小為16MB的存儲空間。分別采用上述4種算法進行分配，如圖所示，分析結(jié)果。59圖3.7動態(tài)劃分的4種分配算法(a)FFA或WFA24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB(b)NFA24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB此次分配位置上次分配位置(c)BFA10MBOS8MBP210MBP716MBP410MBP610MB10MB40MB4MB例：動態(tài)劃分四種算法對比60伙伴系統(tǒng)(BuddySystem)靜態(tài)劃分方案限制了系統(tǒng)中活躍進程的數(shù)目。并且，只能運行不超過分區(qū)大小的進程，如果進程遠遠小于分區(qū)大小，則內(nèi)存空間的利用率非常低。動態(tài)劃分方案使存儲管理復(fù)雜化，并且需要系統(tǒng)付出緊湊外零頭的額外開銷。伙伴系統(tǒng)：綜合靜態(tài)劃分技術(shù)和動態(tài)劃分技術(shù)的優(yōu)點61伙伴系統(tǒng)內(nèi)存的用戶可用空間為2u。系統(tǒng)總是為進程分配大小為2i的一個空閑分區(qū)。其中m≤i≤U，2m是系統(tǒng)允許的最小分區(qū)尺寸。如果進程申請的存儲空間大小為k，且2i-1＜k≤2i,則將整個2i大小的分區(qū)分配給它。否則，該分區(qū)被分割成大小相等（2i-1）的兩個分區(qū)。再判斷k是否滿足條件：2i-2<k≤2i-1,若滿足條件，則將兩個伙伴中的任何一個分配給進程；否則，將其中一個伙伴又平均分成兩個分區(qū)。此過程一直繼續(xù)進行，直到產(chǎn)生的分區(qū)大于或等于k，將其分配給進程。

伙伴系統(tǒng)—設(shè)計思想62

伙伴系統(tǒng)—存儲分配進程申請大小為k的空間，系統(tǒng)為之分配一個2i的空閑分區(qū)，其中，2i-1＜k≤2i若k＞2u，即進程>內(nèi)存空間，失??；若當前無尺寸為2i的空閑分區(qū)，則：(1)將i變?yōu)閕+1，查找一個尺寸為2i+1的空閑分區(qū)。若存在，轉(zhuǎn)(2)執(zhí)行;否則，繼續(xù)執(zhí)行(1)；⑵等分2i+1空閑分區(qū):產(chǎn)生兩個2i的伙伴分區(qū)；⑶把其中一個2i的伙伴分區(qū)作為空閑分區(qū)；(4)另一個2i空閑分區(qū)分配給進程，結(jié)束。63伙伴系統(tǒng)—空間回收

當進程執(zhí)行完畢，釋放一個尺寸為2i的分區(qū)時，系統(tǒng)用下面的算法回收該分區(qū)：如果被回收分區(qū)的伙伴分區(qū)非空閑，那么保留該分區(qū)為一個獨立的空閑分區(qū)，否則[1]合并回收分區(qū)及其伙伴分區(qū)，從而得到一個尺寸為2i+1的空閑分區(qū)；[2]系統(tǒng)再次調(diào)用本算法回收上一步得到的尺寸為2i+1的空閑分區(qū)。64例如—伙伴系統(tǒng)有進程P1、P2、P3、P4、P5相繼申請、釋放空間。系統(tǒng)分配、回收（合并）伙伴分區(qū)的過程如圖所示：65P1申請100KBP2申請200KBP3申請120KBP4申請300KB系統(tǒng)初始狀態(tài)P2、P3結(jié)束P5申請160KBP1執(zhí)行結(jié)束P5執(zhí)行結(jié)束P4執(zhí)行結(jié)束1MBP1128KB256KB512KBP1128KBP2512KBP1P3P2512KBP1P3P2P4P1128KB256KBP4P1128KBP5P4256KBP5P4512KBP41MB圖3.9一個伙伴系統(tǒng)的內(nèi)存分配與回收過程663.3程序裝入技術(shù)67可執(zhí)行程序的生成步驟圖3.10高級程序處理過程源程序目標模塊編譯庫函數(shù)裝入模塊鏈接編輯執(zhí)行目標模塊內(nèi)存68可執(zhí)行程序的裝入？如何裝入待執(zhí)行的程序及其所需的數(shù)據(jù)？何時將程序的邏輯地址轉(zhuǎn)換為物理地址3種裝入方式：絕對裝入、重定位裝入和運行時動態(tài)裝入。

69絕對裝入程序運行之前，按照程序的邏輯地址，將程序和數(shù)據(jù)裝入內(nèi)存指定的地方。優(yōu)點：實現(xiàn)簡單，無須進行邏輯地址到物理地址的變換。70絕對裝入（續(xù)）缺點：程序每次必須裝入同一內(nèi)存區(qū)；程序員必須事先了解內(nèi)存的使用情況，根據(jù)內(nèi)存情況確定程序的邏輯地址；程序的修改（增加或刪除指令）將引起整個程序中指令地址的變動；程序中的所有存儲引用，例如函數(shù)調(diào)用或過程調(diào)用等，在裝入之前都必須轉(zhuǎn)換為物理地址，這不利于存儲共享。71重定位裝入允許將程序裝入與邏輯地址不同的物理內(nèi)存空間。即程序可以裝入到內(nèi)存的任何位置，其邏輯地址與裝入內(nèi)存后的物理地址無直接關(guān)系。但是，必須進行地址映射，將邏輯地址轉(zhuǎn)換為物理地址。靜態(tài)重定位技術(shù)：地址映射在程序裝入時進行，以后不再更改程序地址。72重定位裝入（續(xù)）有利于程序代碼和數(shù)據(jù)的共享。因為裝入程序時，可以將其中的某些存儲引用的邏輯地址映射為內(nèi)存中已有的共享區(qū)的物理地址。但是，靜態(tài)重定位不允許程序在內(nèi)存中移動。這不便于進程交換和緊湊拼接操作，也很難實現(xiàn)多道程序環(huán)境下，多個程序同時裝入內(nèi)存的要求。所以，重定位裝入方式只適合于單道程序環(huán)境。73運行時動態(tài)裝入定義：程序的地址轉(zhuǎn)換不是在裝入時進行，而是在程序運行時動態(tài)進行。運行時動態(tài)裝入需要硬件支持，即重定位寄存器，用于保存程序在內(nèi)存中的起始地址。程序被執(zhí)行時，通過重定位寄存器內(nèi)的起始物理地址和指令或數(shù)據(jù)的邏輯地址計算其物理地址。運行時動態(tài)裝入有利于多道程序環(huán)境下，進程的換進/換出及實現(xiàn)緊湊技術(shù)。

74可執(zhí)行程序的鏈接形成？目標模塊如何鏈接成裝入模塊呢靜態(tài)鏈接動態(tài)鏈接：裝入時動態(tài)鏈接和運行時動態(tài)鏈接75靜態(tài)鏈接定義：程序被裝入內(nèi)存之前，必須完全鏈接成一個裝入模塊，將其中的存儲引用全部轉(zhuǎn)換為相對地址跳轉(zhuǎn)語句。并將多個目標模塊鏈接成為一個模塊，使裝入模塊中的每一條指令具有相對于整個模塊的第一條語句的邏輯地址。靜態(tài)鏈接生成的裝入模塊可以采用重定位裝入或運行時動態(tài)裝入方式。靜態(tài)鏈接需要花費大量的處理機時間。而其中的很多模塊將不會運行，浪費存儲空間和處理機時間。

76鏈接圖3.11目標模塊鏈接成裝入模塊模塊1…ifx>1thencallmm1elsecallmm2…模塊mm1模塊mm2(a)目標模塊模塊1…ifx>1thenelse…模塊mm1模塊mm2(b)裝入模塊？執(zhí)行？執(zhí)行77動態(tài)鏈接定義：不用事先鏈接所有目標模塊形成一個完備的裝入模塊，而是生成一個含有未被鏈接的外部模塊引用的裝入模塊，這些外部模塊可以在裝入時鏈接，或運行時鏈接。78裝入時動態(tài)鏈接定義：當系統(tǒng)裝入含有未鏈接的外部模塊引用的裝入模塊時，每當遇到一個外部模塊引用，則查找相應(yīng)的目標模塊。將其裝入內(nèi)存，并將模塊內(nèi)的指令地址轉(zhuǎn)換為相對于整個裝入模塊起始地址的相對地址。優(yōu)點：有利于目標模塊的更新與升級；有利于代碼共享；有利于擴充軟件的功能--可以將擴充部分作為動態(tài)鏈接模塊。但是，可能鏈接一些不會執(zhí)行的模塊，浪費存儲空間和處理機時間。79運行時動態(tài)鏈接定義：外部模塊引用直至程序執(zhí)行時才裝入內(nèi)存，并鏈接到裝入模塊中，進行地址轉(zhuǎn)換?？梢越鉀Q靜態(tài)鏈接和裝入時動態(tài)鏈接都面臨的存儲空間和處理機時間浪費問題，不需要執(zhí)行的模塊就不會裝入內(nèi)存。廣泛用于事務(wù)處理系統(tǒng)，如航空售票系統(tǒng)、銀行管理系統(tǒng)等。另外，操作系統(tǒng)自身的一些特殊處理例程，如錯誤處理例程，也無需事先全部裝入內(nèi)存。803.4簡單存儲管理技術(shù)

81簡單存儲相對于虛擬存儲而言，指為了實現(xiàn)簡單，執(zhí)行之前，操作系統(tǒng)必須將待執(zhí)行的程序全部裝入內(nèi)存。然而，現(xiàn)代操作系統(tǒng)大都支持虛擬存儲功能，允許進程裝入部分程序即可開始執(zhí)行，其余部分保留在外存。當執(zhí)行所需的部分不在內(nèi)存時，中斷進程執(zhí)行，使之阻塞等待，直到相應(yīng)部分裝入內(nèi)存。82？程序在內(nèi)存中如何組織連續(xù)存儲:需要內(nèi)存中的一塊連續(xù)的、足夠大的分區(qū)。如果內(nèi)存中沒有足夠大的連續(xù)空閑分區(qū)，但存在總量足夠的獨立小分區(qū)，即外零頭。系統(tǒng)要么拒絕分配空間，要么采用緊湊技術(shù)拼接外零頭或采用交換技術(shù)。83？程序在內(nèi)存中的組織（續(xù)）非連續(xù)存儲：允許進程的程序和數(shù)據(jù)分別裝在內(nèi)存的不同分區(qū)中。但，必須登記一個進程分到的所有分區(qū)的位置、大小、使用情況（如是否共享等）等信息。常用的非連續(xù)存儲技術(shù)：分頁存儲技術(shù)、分段存儲技術(shù)及其結(jié)合—段頁式技術(shù)。84圖3.12內(nèi)存的連續(xù)存儲與非連續(xù)存儲…OS進程P…基地址(a)連續(xù)存儲進程P（2）…OS…進程P（1）…進程P（n）…進程的組成基地址長度…P(1)2604200…P(2)1240300……………P(n)6500300…(b)非連續(xù)存儲85連續(xù)存儲管理最簡單的存儲管理技術(shù)要求系統(tǒng)配置專門的硬件實現(xiàn)快速地址轉(zhuǎn)換和存儲保護。處理機硬件基址寄存器(Baseregister)界限寄存器(Boundsregister)86連續(xù)存儲管理（續(xù)）

基址寄存器：存放當前執(zhí)行進程所在分區(qū)的物理存儲單元的起始地址。界限寄存器：存放當前執(zhí)行進程所在分區(qū)最后一個物理存儲單元的地址，限定進程的執(zhí)行范圍，保護其他進程不被非法訪問。基址寄存器和界限寄存器被多個進程共享，只有當前執(zhí)行進程才使用它們。87裝入時，進程分區(qū)的基地址值和分區(qū)的最后一個物理存儲單元的地址值，分別填入該進程PCB的相應(yīng)字段中。當進程被調(diào)度執(zhí)行時，將PCB中對應(yīng)的進程基地址值寫入基址寄存器中，并將進程獲得的內(nèi)存分區(qū)最大地址值，填入界限寄存器中。當進程被交換出/換入內(nèi)存時，上述兩個地址值也會發(fā)生改變。

連續(xù)存儲管理（續(xù)2）

88地址映射與存儲保護邏輯地址轉(zhuǎn)換成物理地址—取基址寄存器中的值，加上邏輯地址值，生成一個物理地址。地址越界檢查—取界限寄存器中的值，與第一步計算的結(jié)果進行比較。如果生成的物理地址超出了界限范圍，產(chǎn)生一個中斷，報告地址越界。否則，繼續(xù)該指令的執(zhí)行。89程序部分數(shù)據(jù)部分內(nèi)存基址寄存器加法器邏輯地址界限寄存器比較器越界中斷物理地址圖3.13連續(xù)存儲管理的地址轉(zhuǎn)換和越界檢查90簡單分頁存儲管理–非連續(xù)連續(xù)存儲：存在外零頭，浪費存儲空間?！熬o湊”需要系統(tǒng)額外開銷。非連續(xù)存儲：允許將一個進程的程序和數(shù)據(jù)離散存儲在多個獨立的分區(qū)中，消除了外零頭。

91分頁式存儲--基本原理

分頁存儲管理技術(shù)是一種特殊的固定分區(qū)方法。系統(tǒng)事先將物理內(nèi)存劃分成許多尺寸相等的頁框(PageFrame)，并將進程分割成許多大小相同的頁面(Page)，頁面與頁框大小相同。92分區(qū)：進程的邏輯地址空間是連續(xù)的、一維的、線性地址，進程的每一條指令和數(shù)據(jù)的地址相對于第一條語句的地址而定。分頁：進程被分割成許多頁面。每個頁面內(nèi)的指令和數(shù)據(jù)是連續(xù)的，它們的地址相對于其所屬頁的第一條語句的地址，稱為頁內(nèi)偏移量。（分頁）邏輯地址被分為兩部分：頁號和頁內(nèi)偏移量

頁號頁內(nèi)偏移量151090圖3.14分頁管理的邏輯地址表示93程序裝入過程當一個進程被裝入物理內(nèi)存時，系統(tǒng)將為該進程的每個頁面分配一個獨立的頁框。同一個進程的多個頁面不必存放在連續(xù)的多個頁框中，并利用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)將所分配到的每個頁框信息登記下來。94例如—分頁系統(tǒng)假設(shè)內(nèi)存能提供16個空閑頁框，進程P1被分割成4個頁面，裝入內(nèi)存中的0號至3號頁框。進程P2被分割成3個頁面，裝入4號至6號頁框。進程P3被裝入7號至12號頁框，如圖3.15(a)所示。此時，進程P4請求分配5個頁框大小的存儲空間，但內(nèi)存只有3個空閑頁框。于是，將暫時不運行的P2交換出內(nèi)存，如圖3.15(b)所示。然后，再將P4裝入4、5、6、13、14號頁框，如圖3.15(c)所示。

95圖3.15進程裝入到離散的頁框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5頁框號內(nèi)存(a)依次裝入P1、P2、P3P1P2P3空閑0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5頁框號內(nèi)存(b)換出P2P1空閑P3空閑0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4頁框號內(nèi)存(c)裝入P4P1P4P3空閑P496分頁系統(tǒng)數(shù)據(jù)結(jié)構(gòu)：頁表頁表：系統(tǒng)為每個進程建立一張頁面映射表。用于記載進程的各頁面到物理內(nèi)存中頁框的映射信息。進程的每個頁面依次對應(yīng)頁表中的一個表項，其中包含相應(yīng)頁在內(nèi)存中對應(yīng)的物理頁框號和頁面存取控制權(quán)限等字段。97頁號頁框號00112233進程P1頁表頁號頁框號0-1-2-進程P2頁表頁號頁框號071829310411512進程P3頁表頁號頁框號041526313414進程P4頁表圖3.16進程P1、P2、P3、P4的頁表示意圖例如：頁表98數(shù)據(jù)結(jié)構(gòu)：頁框表空閑頁框表：登記系統(tǒng)中剩下的空閑頁框情況圖3.17Fig3-15a的空閑頁框表示意圖15141399地址變換硬件--實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換分頁系統(tǒng)中的地址變換過程如下：（1）

根據(jù)邏輯地址,計算出頁號和頁內(nèi)偏移量；（2）

用頁號檢索頁表，查找指定頁面對應(yīng)的頁框號；（3）

根據(jù)頁框號和頁內(nèi)偏移量，計算出物理地址。100頁表寄存器頁表寄存器：實現(xiàn)快速地址映射，存儲執(zhí)行進程的頁表起始地址。頁表寄存器設(shè)置在處理機硬件中。當進程被創(chuàng)建時，其頁表起始地址記載于進程PCB中。當進程被調(diào)度執(zhí)行時，頁表的起始地址將從該進程的PCB中取出，并填入頁表寄存器中。進行地址變換時，處理機從頁表寄存器中查找頁表的地址。101頁號偏移量邏輯地址物理地址頁框號偏移量頁表寄存器頁表起始地址內(nèi)存頁框號頁表地址轉(zhuǎn)換程序+偏移量圖3.18分頁系統(tǒng)的地址變換過程頁框102大頁表大邏輯地址空間，頁表非常大，需要占用相當大的內(nèi)存空間。比如，32位邏輯地址空間，假設(shè)頁面大小為4KB（212），則4GB（232）的邏輯地址空間將被劃分成220個頁面。103大頁表（續(xù)）若采用一級頁表，則其內(nèi)將包含1兆（220）個頁表項。若按字節(jié)尋址，一個頁表項占4B，則一級頁表需要占用4MB（222）內(nèi)存空間。不可能將4MB的頁表保存在一個連續(xù)區(qū)中。那么，如何處理大頁表的存儲與檢索呢？104二級頁表將一個大頁表全部保存在內(nèi)存中。首先，將其分割，并離散地存儲在內(nèi)存的多個頁框中。為之建立二級頁表，記錄被分割的各個頁面存儲在哪些頁框中，也稱為外層頁表（OuterPageTable）。對于4GB的進程，若采用二級頁表，則對應(yīng)的二級頁表結(jié)構(gòu)如圖：105……4GB的用戶進程4MB的一級頁表4KB的二級頁表圖3.194GB進程的二級頁表結(jié)構(gòu)106多級頁表對于某些機器，二級頁表也可能非常大?？梢圆捎枚嗉夗摫恚瑢ν鈱禹摫碓龠M行分頁，將各個頁面離散地存儲到不相鄰接的物理頁框中雖然，對大頁表而言，多級頁表方法消除了對較大的連續(xù)內(nèi)存空間的需要，但并未解決大頁表占用較大的內(nèi)存空間的問題，建立多及頁表反而會增加額外的存儲空間。107大頁表—解決方案最好的解決辦法是采用虛擬存儲技術(shù)，內(nèi)存中僅裝入頁表的一部分。即只將當前需要的部分頁表項裝入內(nèi)存，其余頁表項駐留在磁盤上，需要時再將它們裝入內(nèi)存。若采用多級頁表，對于正在運行的進程，必須將其外層頁表調(diào)入內(nèi)存（全部），而內(nèi)層頁表只需調(diào)入幾頁就可以了（部分）。108反置頁表--(InvertedPageTable)一般情況下，系統(tǒng)從進程的角度為每個進程建立一張頁表，頁表的表項按頁號排序。這種方法可能導(dǎo)致一個大進程的頁表太大，占據(jù)大量的內(nèi)存空間。反置頁表：從內(nèi)存的角度建立頁表，整個系統(tǒng)只有一張頁表。頁表的表項基于內(nèi)存中的每一個物理頁框設(shè)置，頁表項按頁框號的順序排序。其中還必須包含頁框?qū)?yīng)的頁號及其隸屬進程的標識符等信息。109反置頁表（續(xù)）通常，反置頁表需要包含成千上萬個表項，利用進程ID和頁號檢索其中某一個表項的速度很慢。可以根據(jù)進程ID和頁號構(gòu)建Hash表。Hash表的每一項指向反置頁表中的某一項。但是，可能會出現(xiàn)多個邏輯地址被映射到一個Hash表項的情況。需要通過鏈接指針將多個沖突的映射鏈接起來。一般，沖突的表項一般只有一項，或兩項。

110反置頁表--地址變換首先，以進程ID和頁號為參數(shù)，代入Hash函數(shù)進行計算。然后，根據(jù)計算結(jié)果，檢索反置頁表。若檢索完整個反置頁表都未找到與之匹配的表項，表明此頁尚未裝入內(nèi)存。若系統(tǒng)支持虛擬存儲技術(shù)，則產(chǎn)生中斷--請求調(diào)頁。若系統(tǒng)不支持虛擬存儲技術(shù)，則表示地址出錯。當檢索到反置頁表中的對應(yīng)表項時，將其中的頁框號與邏輯地址中的偏移量相加，構(gòu)成物理地址。

111圖3.20利用反置頁表進行地址變換

物理地址偏移量頁框號邏輯地址偏移量頁號HashHash表頁號進程ID指針頁框號反置頁表112快表分頁系統(tǒng)：處理機每次存取指令或數(shù)據(jù)至少需要訪問兩次物理內(nèi)存—第一次訪問頁表，第二次存取指令或數(shù)據(jù)，大頁表可能訪問次數(shù)更多。為了提高地址變換速度，為進程頁表設(shè)置一個專用的高速緩沖存儲器，稱為快表、TLB(TranslationLookasideBuffer)，或聯(lián)想存儲器（AssociativeMemory）

113快表的工作原理快表的工作原理類似于系統(tǒng)中的數(shù)據(jù)高速緩存(cache)，其中專門保存當前進程最近訪問過的一組頁表項。根據(jù)局部性原理，在一個很短的時間段內(nèi)，程序的執(zhí)行總是局部于某一個范圍。即，進程最近訪問過的頁面在不久的將來還可能被訪問。114分頁系統(tǒng)地址轉(zhuǎn)換首先，通過根據(jù)邏輯地址中的頁號，查找快表中是否存在對應(yīng)的頁表項。若快表中存在該表項，稱為命中（hit），取出其中的頁框號，加上頁內(nèi)偏移量，計算出物理地址。若快表中不存在該頁表項，稱為命中失敗，則再查找頁表，找到邏輯地址中指定頁號對應(yīng)的頁框號，并計算物理地址。同時，更新快表，將該表項插入快表中—快表已滿？？？。115圖3.21具有快表的分頁系統(tǒng)地址變換過程頁號偏移量邏輯地址物理地址頁框號偏移量偏移量內(nèi)存快表頁框號頁表頁框TLB命中命中失敗116頁面與頁框大小分頁系統(tǒng)中，頁面=頁框。頁框的大小由計算機的硬件邏輯定義。通常，頁框的大小是2的冪次個字節(jié)，且常在512B（29）～4KB（212）之間，典型的頁框大小為1KB。將頁框大小設(shè)置為2的冪次，可以簡化處理機中地址變換硬件邏輯的設(shè)計與實現(xiàn)—邏輯地址<->頁號、偏移量，頁框號、偏移量<->物理地址。117頁面與頁框大?。ɡm(xù)）影響頁面與頁框大小的主要因素：頁內(nèi)零頭、地址轉(zhuǎn)換速度和頁面交換效率。較小的頁面有利于減少內(nèi)零頭，從而有利于提高內(nèi)存的利用率。然而，較小的頁面也將導(dǎo)致頁表過大，從而降低處理機訪問頁表時的命中率(HitRate)。塊（內(nèi)外存數(shù)據(jù)交換單位）越大，內(nèi)/外存之間的數(shù)據(jù)交換效率越高。因此，對于支持交換技術(shù)的系統(tǒng)，較大的頁面有利于提高頁面換進/換出內(nèi)存的效率。118分頁存儲管理—總結(jié)徹底消除了外零頭,僅存在很少的內(nèi)零頭,提高了內(nèi)存利用率。分頁操作由系統(tǒng)自動進行,一個頁面不能實現(xiàn)某種邏輯功能。用戶看到的邏輯地址是一維的，無法調(diào)試執(zhí)行其中的某個子程序或子函數(shù)。采用分頁技術(shù)不易于實現(xiàn)存儲共享，也不便于程序的動態(tài)鏈接。119簡單分段存儲管理基于模塊化程序設(shè)計時，常常需要將一個大任務(wù)劃分成若干相對獨立的子任務(wù)，對應(yīng)于子任務(wù)編寫子程序，稱為段(Segment)。每個子程序可以獨立地編輯、編譯、鏈接和執(zhí)行。各個子程序由實現(xiàn)的功能決定，長度各不相同。執(zhí)行時，根據(jù)實際需要，將若干子程序鏈接成一個大程序。120基本原理—分段管理程序由若干邏輯段組成，每個段有自己的名字和長度。程序的邏輯地址是由段名（段號）和段內(nèi)偏移量決定。每個段的邏輯地址從0開始編址。段號段內(nèi)偏移量151090圖3.22分段管理的邏輯地址表示121基本原理（續(xù)）系統(tǒng)采用動態(tài)劃分技術(shù)，將物理內(nèi)存動態(tài)地劃分成許多尺寸不相等的分區(qū)（Partition）。當一個進程被裝入物理內(nèi)存時，系統(tǒng)將為該進程的每一段獨立地分配一個分區(qū)。同一進程的多個段不必存放在連續(xù)的多個（?。┓謪^(qū)中。122分段系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)段表:每個進程建立一個，用于描述進程的分段情況，記載進程的各個段到物理內(nèi)存中分區(qū)的映射情況。其中包含段號、段長、段基址以及對本段的存取控制權(quán)限（共享）等信息?？臻e分區(qū)表:用于記載物理內(nèi)存中的空閑分區(qū)情況注意：由于分段基于分區(qū)，因此分區(qū)管理中的空閑分區(qū)管理數(shù)據(jù)結(jié)構(gòu)同樣適用于分段管理的空閑分區(qū)管理。123圖3.23分段存儲示例…P2.1P1.0P1.2P1.1…P2.0(a)分段存儲0500100執(zhí)行存取控制段基址段長段號1200800只讀22001000執(zhí)行(b)進程P1的段表01001200執(zhí)行存取控制段基址段長段號1200600執(zhí)行(c)進程P2的段表124地址變換和存儲保護—步驟

（1）根據(jù)邏輯地址中的段號檢索進程段表，獲得指定段對應(yīng)的段表項；（2）判斷是否地址越界。比較邏輯地址中的段內(nèi)偏移量與段表項中的段長，若超過段的長度，則產(chǎn)生存儲保護中斷（該中斷將由操作系統(tǒng)進行處理）；否則，轉(zhuǎn)（3）；（3）把邏輯地址中的段內(nèi)偏移量與段表表項中的段基址相加，從而得到物理地址。125段表寄存器段表同樣被保存在物理內(nèi)存中。段表寄存器：實現(xiàn)快速地址變換，用來存放當前執(zhí)行進程的段表在物理內(nèi)存中的起始地址。當創(chuàng)建進程，將進程的程序和數(shù)據(jù)裝入內(nèi)存時，系統(tǒng)為之建立段表，并將段表的起始地址填入進程的PCB中。當進程被調(diào)度執(zhí)行時，取出其PCB中的段表首地址，填入段表寄存器中。126圖3.24分段系統(tǒng)的地址變換過程內(nèi)存物理地址段基址+偏移量偏移量段號偏移量邏輯地址段表寄存器段表起始地址+段表段長段基址+越界判斷中斷越界正常段段127分段系統(tǒng)的快表在分段系統(tǒng)中，為了訪問內(nèi)存中的一條指令或數(shù)據(jù)，需要兩次訪問內(nèi)存：—第一次，訪問內(nèi)存中的段表，獲得對應(yīng)段的起始地址。根據(jù)段的起始地址和段內(nèi)偏移量，計算出物理地址?！诙?，根據(jù)物理地址，訪問對應(yīng)存儲單元的指令或數(shù)據(jù)。為了提高處理機的效率，類似分頁系統(tǒng)的快表，可以為分段系統(tǒng)增加一個快表，用于保存最近使用過的段表項。

128分段系統(tǒng)—總結(jié)

有效消除了內(nèi)零頭，提高了存儲利用率。允許子程序獨立編譯和修改，而不需要重新編譯或鏈接其它相關(guān)子程序。容易實現(xiàn)存儲共享。具有較高的安全保障。很容易滿足程序段的動態(tài)增長需要。129分頁與分段技術(shù)的比較都采用非連續(xù)存儲，由地址映射實現(xiàn)地址變換。不同主要表現(xiàn)在：（1）

頁是信息的物理單位，大小固定。段是信息的邏輯單位，各段的長度不固定。每一段都具有一定邏輯含義。（2）

分頁的地址空間是一維的，邏輯地址的劃分由機器硬件實現(xiàn)，用戶不清楚具體分頁情況。分段的地址空間是二維或多維的，程序員知道段名和段內(nèi)偏移量。（3）分頁活動源于系統(tǒng)管理物理內(nèi)存的需要，在系統(tǒng)內(nèi)部進行，由系統(tǒng)實施，用戶看不見。分段活動源于用戶進行模塊化程序設(shè)計的需要，在系統(tǒng)外部進行，由用戶實施，用戶是知道的。

130簡單段頁式存儲管理基本思想：采用分段方法組織用戶程序，采用分頁方法分配和管理內(nèi)存。即，用戶程序可以用模塊化思想進行設(shè)計，一個用戶序由若干段構(gòu)成。系統(tǒng)將內(nèi)存劃分成固定大小的頁框，并將程序的每一段分割成若干頁以后裝入內(nèi)存執(zhí)行。131邏輯地址在段頁式系統(tǒng)中，進程的每一段被進一步分割成頁面，段內(nèi)代碼和數(shù)據(jù)地址不再連續(xù)。邏輯地址由3部分組成：段號、段內(nèi)頁號、頁內(nèi)偏移量，如圖段號段內(nèi)頁號頁內(nèi)偏移量圖3.25段頁式系統(tǒng)的邏輯地址結(jié)構(gòu)132數(shù)據(jù)結(jié)構(gòu)用于管理的數(shù)據(jù)結(jié)構(gòu)：段表、頁表，如圖圖3.26段頁式系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)段0段1段2用戶程序段表03頁表首址頁表長度段號12內(nèi)存

OS

0頁號頁框號12頁號頁框號頁表133段表寄存器—段頁式管理段表寄存器：加速地址變換，用于存放執(zhí)行進程段表的起始地址。134地址變換—過程首先，從段表寄存器從獲得進程段表的起始地址，根據(jù)該地址，查找進程的段表。然后，根據(jù)邏輯地址指定的段號檢索段表，找到對應(yīng)段的頁表起始地址。再根據(jù)邏輯地址中指定的頁號檢索該頁表，找到對應(yīng)頁所在的頁框號。最后，用頁框號加上邏輯地址中指定的頁內(nèi)偏移量，形成物理地址。135圖3.27段頁式系統(tǒng)的地址變換過程段表頁表首址段號頁內(nèi)偏移量邏輯地址段內(nèi)頁號++物理地址頁框號+頁內(nèi)偏移量頁表頁框號+偏移量內(nèi)存頁框頁框頁框段表寄存器段表起始地址136快表—段頁式管理第一次，訪問段表，從中獲得該段的頁表首址；第二次，訪問頁表，從中取出邏輯地址指定的頁面所在的頁框號，并將該頁框號和頁內(nèi)偏移量相加，形成指令或數(shù)據(jù)的物理地址；第三次訪問內(nèi)存，根據(jù)前面計算的物理地址，取出對應(yīng)存儲單元的指令或數(shù)據(jù)。可以在地址變換機構(gòu)中增設(shè)一個高速緩沖寄存器，其中保存最近使用過的頁號及其所屬的段號—頁框號？？？。137段頁式有快表的地址轉(zhuǎn)換—過程首先，利用段號和頁號檢索該高速緩沖寄存器。若找到匹配的表項，則可以從中獲得相應(yīng)頁面的頁框號，加上頁內(nèi)偏移量，形成物理地址。若該高速緩沖寄存器中未包含對應(yīng)表項，則需要訪問段表及頁表，計算出物理地址以后，從相應(yīng)存儲單元獲取指令或數(shù)據(jù)。138段頁式存儲管理—總結(jié)綜合了分段和分頁技術(shù)的優(yōu)點，既能有效地利用存儲空間，又能方便用戶進行程序設(shè)計。但是，實現(xiàn)段頁式存儲管理系統(tǒng)需要增加硬件成本，系統(tǒng)的復(fù)雜度和管理開銷也大大增加。因此，段頁式存儲管理技術(shù)適合于大、中型計算機系統(tǒng)，不太適合小型、微型計算機系統(tǒng)。1393.5虛擬存儲管理技術(shù)

140簡單存儲：要求將一個進程所需的程序和數(shù)據(jù)全部裝入內(nèi)存方可執(zhí)行。這樣的系統(tǒng)存在兩個很嚴重的問題?！湟唬瑢τ诖筮M程，如果其所需內(nèi)存空間超過了內(nèi)存的最大容量，則無法運行?！涠?，對于多道程序系統(tǒng)，由于每一個進程需要全部裝入內(nèi)存，使同時駐留內(nèi)存的進程數(shù)量受到限制。雖然也可以通過提高內(nèi)存容量來解決，但是代價太高。將一部分價格較低的外存空間當作內(nèi)存使用，從邏輯上擴充內(nèi)存容量，將獲得更高的性價比。141虛擬存儲技術(shù)的理論依據(jù)程序執(zhí)行的局部性原理：程序的執(zhí)行總是呈現(xiàn)局部性。即，在一個較短的時間段內(nèi)，程序的執(zhí)行僅限于某個部分；相應(yīng)的，它所訪問的存儲空間也局限于某個區(qū)域。因此，只要保證進程執(zhí)行所需的部分程序和數(shù)據(jù)駐留在內(nèi)存，一段時間內(nèi)進程都能順利執(zhí)行。142實現(xiàn)虛擬存儲的一般過程

進程運行之前，僅需要將一部分頁面或段裝入內(nèi)存，便可啟動運行，其余部分暫時保留在磁盤上。進程運行時，如果它所需要訪問的頁面（段）已經(jīng)裝入內(nèi)存，則可以繼續(xù)執(zhí)行下去；如果其所需要訪問的頁面（段）尚未裝入內(nèi)存，則發(fā)生缺頁（段）中斷，進程阻塞。此時，系統(tǒng)將啟動請求調(diào)頁（段）功能，將進程所需的頁（段）裝入內(nèi)存。143實現(xiàn)虛擬存儲的一般過程（續(xù)）

如果當前內(nèi)存已滿，無法裝入新的頁（段），則還需要利用頁（段）置換功能，將內(nèi)存中暫時不用的頁（段）交換到磁盤上，以騰出足夠的內(nèi)存空間。再將進程所需的頁（段）裝入內(nèi)存，喚醒阻塞的進程，使之重新參與調(diào)度執(zhí)行。144從外存裝入頁/段更新頁/段表交換頁/段內(nèi)存滿？是否缺頁/段中斷頁/段在內(nèi)存是否進程執(zhí)行圖3.28實現(xiàn)虛擬存儲的典型過程145虛擬存儲定義通過系統(tǒng)提供的缺頁/段中斷功能和交換技術(shù)，動態(tài)裝入進程的程序代碼和數(shù)據(jù)，使得一個大的用戶程序能在一個相對較小的內(nèi)存空間中運行，也使得有限的內(nèi)存能同時容納更多的進程。習慣上，人們把這種用戶感覺上的、由實際內(nèi)存和部分外存共同構(gòu)成的存儲空間稱為虛擬存儲器146虛擬存儲技術(shù)的技術(shù)支持

首先，必須有相應(yīng)的硬件支持，用以實現(xiàn)虛擬分頁或虛擬分段存儲管理。其次，操作系統(tǒng)必須提供相應(yīng)的軟件支持，管理頁或段在內(nèi)存和外存之間的移動。147虛擬存儲的基本數(shù)據(jù)結(jié)構(gòu)

由于虛擬存儲系統(tǒng)中，進程的程序代碼和數(shù)據(jù)只有一部分在內(nèi)存，另一部分保存在外存。在頁/段表項中增加一個“存在”字段，其值為0或1。增加一個“修改”字段，表明對應(yīng)頁/段自進入內(nèi)存以來是否被修改過。只有被修改過的頁/段才需要保存到外存，若需要將未修改過的頁/段換出內(nèi)存，只需要將新裝入的頁/段直接覆蓋其存儲區(qū)域，而不必將其內(nèi)容保存到外存。

148圖3.29虛擬分頁、分段及段頁式存儲系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)頁號頁框號存在修改其他控制(a)虛擬存儲頁表項段號段長存在修改其他控制(b)虛擬存儲段表項段基址長(c)虛擬存儲段頁式系統(tǒng)的段表項和頁表項段號其他控制頁表長度頁表基址段表項頁號頁框號存在修改其他控制頁表項虛擬存儲數(shù)據(jù)結(jié)構(gòu)對比圖

149虛擬存儲的優(yōu)點第一，可以運行大程序，包括超過內(nèi)存實際容量的大程序。第二，可以在有限的物理內(nèi)存中運行更多的程序。多道程序系統(tǒng)的度（作業(yè)個數(shù)）不再受到物理內(nèi)存空間的限制。150虛擬存儲的典型問題

--抖動（thrashing）當進程要求裝入新的頁面或程序段時，如果當前沒有足夠的空閑空間，需要交換一些頁面或段到外存。如果被交換出去的頁面或段很快將被進程使用，則又需要將其換入內(nèi)存。如果系統(tǒng)花費大量的時間把程序和數(shù)據(jù)頻繁地裝入和移出內(nèi)存而不是執(zhí)行用戶指令，那么，稱系統(tǒng)出現(xiàn)了抖動。出現(xiàn)抖動現(xiàn)象時，系統(tǒng)顯得非常繁忙，但是吞吐量很低，甚至產(chǎn)出為零。根本原因：選擇的頁面或段不恰當。151虛擬存儲分頁技術(shù)

建立在簡單分頁存儲管理系統(tǒng)之上，是目前常用的一種虛擬存儲管理技術(shù)。常用：虛擬分頁式、虛擬段頁式。152地址變換過程基于簡單存儲分頁系統(tǒng)增加了某些功能，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出頁面等。進程執(zhí)行時，首先通過根據(jù)邏輯地址中的頁號，查找快表中是否存在對應(yīng)的頁表項。若快表中不存在該頁表項，則再查找頁表。檢查對應(yīng)的頁面是否在內(nèi)存中存在。若該頁面不在內(nèi)存，啟動缺頁中斷處理例程，裝入需要的頁面，并更新頁表和快表。若該頁面已經(jīng)在內(nèi)存中，將對應(yīng)的頁表項插入快表中，更新快表。若快表中存在該表項，則直接取出其中的頁框號，加上頁內(nèi)偏移量，計算出物理地址。153訪問頁表圖3.30虛擬存儲分頁系統(tǒng)地址變換過程物理地址頁框號偏移量更新快表頁號偏移量邏輯地址檢索快表是否是否換出頁面處理機處理中斷是否處理機從外存取該頁將該頁裝入內(nèi)存更新頁表缺頁中斷處理？命中？內(nèi)存滿？頁在內(nèi)存154缺頁中斷處理過程（1）操作系統(tǒng)接收到進程產(chǎn)生的缺頁中斷信號，啟動中斷處理例程，保留處理機現(xiàn)場；（2）操作系統(tǒng)通知處理機從外存讀取指定的頁面；（3）處理機激活I(lǐng)/O設(shè)備；（4）檢查內(nèi)存有無足夠的空閑空間裝入該頁面？若有，轉(zhuǎn)（6），否則，執(zhí)行（5）；（5）利用頁面置換算法，選擇內(nèi)存中的某個頁面，換出內(nèi)存；（6）將指定頁面從外存裝入內(nèi)存；（7）更新該進程的頁表；（8）更新快表；（9）計算物理地址。155虛擬存儲分段技術(shù)

建立在簡單存儲分段系統(tǒng)基礎(chǔ)上，利用動態(tài)分區(qū)技術(shù)分配存儲空間，并以段作為交換的單位。進程執(zhí)行之前，系統(tǒng)為之分配幾個必要的內(nèi)存分區(qū)，每一個分區(qū)中裝入一段。當進程執(zhí)行過程中，出現(xiàn)缺段中斷時，操作系統(tǒng)將為進程裝入需要的程序段。156虛擬存儲分段：數(shù)據(jù)結(jié)構(gòu)

需要修改段表，增加“存在”字段和“修改”字段，分別標明對應(yīng)段是否存在于內(nèi)存，以及內(nèi)存中的段自裝入以來是否被修改過。157地址變換與存儲保護在簡單分段系統(tǒng)的地址變換機構(gòu)基礎(chǔ)上形成的。越界檢查：可能產(chǎn)生一個地址越界中斷，進入相應(yīng)的中斷處理例程執(zhí)行。一般地，當?shù)刂吩浇缰袛嗵幚硗戤?，該進程將異常結(jié)束。操作合法性檢查：如果屬于非法操作，產(chǎn)生非法訪問中斷，這時也會讓進程異常終止。缺段處理：執(zhí)行進程被阻塞。并產(chǎn)生一個中斷信號，處理機執(zhí)行缺段中斷處理例程。158圖3.31虛擬存儲分段系統(tǒng)地址變換過程物理地址段基址偏移量更新快表否非法訪問中斷是是否是越界中斷處理訪問段表段號偏移量邏輯地址檢索快表否是缺段中斷處理否更新段表？命中？段在內(nèi)存？地址越界？合法訪問159圖3.31虛擬存儲分段系統(tǒng)中的缺段中斷的處理過程換出一個或幾個段形成一個合適空閑區(qū)返回修改段表、空閑分區(qū)表從外存讀入段s喚醒進程是拼接外零頭，形成一個合適的空閑區(qū)是段s不在內(nèi)存阻塞執(zhí)行進程內(nèi)存中有合適的空閑區(qū)嗎？否空閑區(qū)容量總和能否滿足？否160虛擬存儲段頁式技術(shù)

虛擬存儲段頁式系統(tǒng)中，程序和數(shù)據(jù)通常以頁面為單位被系統(tǒng)裝入和移出內(nèi)存。因此，一般不需要在段表項中增加“存在”字段和“修改”字段，而將它們放在頁表中。段表中需要保留基于段的保護與存儲共享等目的的存取控制信息，頁表中設(shè)置基于頁的控制信息。

161地址變換首先，通過根據(jù)段號和頁號，查找快表中是否存在對應(yīng)的頁表項。若快表中不存在該頁表項，則再查找段表。然后，檢索段號對應(yīng)的段表項，找到對應(yīng)段的頁表起始地址。再根據(jù)頁號檢索該頁表，檢查對應(yīng)頁面是否在內(nèi)存。若該頁面不在內(nèi)存，啟動缺頁中斷處理例程，裝入需要的頁面，并更新頁表和快表。若該頁面已經(jīng)在內(nèi)存中，將對應(yīng)的頁表項插入快表中，更新快表。若快表中存在該表項，則直接取出其中的頁框號，加上頁內(nèi)偏移量，計算出物理地址。162圖3.32虛擬存儲段頁式系統(tǒng)地址變換過程更新頁表缺頁中斷處理物理地址頁框號偏移量更新快表是否訪問段表訪問頁表檢索快表段號頁內(nèi)偏移量邏輯地址段內(nèi)頁號否是？命中？頁在內(nèi)存163虛擬存儲系統(tǒng)的軟件策略現(xiàn)代操作系統(tǒng)幾乎都采用虛擬存儲管理系統(tǒng)一些特殊的操作系統(tǒng)和一些較老的操作系統(tǒng)沒有采用虛擬存儲技術(shù)。例如，MSDOS、早期的UNIX和一些嵌入式（專用）操作系統(tǒng)等。大多采用分段與分頁相結(jié)合的段頁式管理系統(tǒng)。下面以分頁存儲管理為例，介紹虛擬存儲系統(tǒng)采用的軟件策略。164虛擬存儲系統(tǒng)的軟件策略（續(xù)）駐留集管理(ResidentSetManagement)放置策略(PlacementPolicy)獲取策略(FetchPolicy)置換策略(ReplacementPolicy)清除策略(CleaningPolicy)負載控制(LoadControl)165駐留集管理駐留集：虛擬存儲系統(tǒng)中，每個進程駐留在內(nèi)存的頁面集合，或進程分到的物理頁框集合。駐留集管理主要解決的問題是，系統(tǒng)應(yīng)當為每個活躍進程分配多少個頁框。166影響頁框分配的主要因素

分配給每個活躍進程的頁框數(shù)越少，同時駐留內(nèi)存的活躍進程數(shù)就越多，進程調(diào)度程序能調(diào)度就緒進程的概率就越大。然而，這將導(dǎo)致進程發(fā)生缺頁中斷的概率較大；為進程分配過多的頁框，并不能顯著地降低其缺頁中斷率。

167基本的駐留集管理策略固定分配策略(Fixed-AllocationPolicy)可變分配策略(Variable-AllocationPolicy)168固定分配策略為每個進程分配固定數(shù)量的頁框。即，每個活躍進程的駐留集尺寸在運行期間固定不變。為進程分配多少個頁框是合理的呢？—可以由系統(tǒng)根據(jù)進程的類型確定，也可以由編程人員或系統(tǒng)管理員指定。169可變分配策略為每個活躍進程分配的頁框數(shù)在進程的生命周期內(nèi)是可變的。即，系統(tǒng)可以首先給進程分配一定數(shù)量的頁框。進程運行期間，可以增加或減少頁框。系統(tǒng)可以根據(jù)進程的缺頁率調(diào)整進程的駐留集?！斶M程的缺頁率很高時，駐留集太小，需要增加頁框；—當缺頁率一段時間內(nèi)都保持很低時，可以在不會明顯增加進程缺頁率的前提下，回收其一部分頁框，減小進程的駐留集。170可變分配vs.固定分配可變分配策略比固定分配策略更靈活，既可以提高系統(tǒng)的吞吐量，又能保證內(nèi)存的有效利用?？勺兎峙湟蠼y(tǒng)計進程的缺頁率，增加系統(tǒng)額外開銷。而準確判斷進程缺頁率的高低，確定缺頁率的閾值是非常困難的?？勺兎峙洳呗圆粌H需要操作系統(tǒng)軟件專門的支持，而且，還需要處理機平臺提供的硬件支持171頁面放置策略解決的問題：系統(tǒng)應(yīng)當在內(nèi)存的什么位置為活躍進程分配頁框？一般地，對于一個分頁系統(tǒng)或段頁式系統(tǒng)，將進程的一個頁面裝入哪一個頁框無關(guān)緊要。對于分段系統(tǒng)，需要考慮將一個程序段裝入哪一個合適的分區(qū)中，可采用的分配算法包括首次適應(yīng)法、下次適應(yīng)法、最佳適應(yīng)法或最差適應(yīng)法等。172頁面獲取策略解決的問題：系統(tǒng)應(yīng)當在何時把一個頁面裝入內(nèi)存？請求調(diào)頁(DemandPaging)預(yù)調(diào)頁(Prepaging)173請求調(diào)頁僅當進程執(zhí)行過程中，通過檢查頁表發(fā)現(xiàn)相應(yīng)頁面不在內(nèi)存時，才裝入該頁面。當進程剛開始執(zhí)行時，由于預(yù)先未裝入進程的頁面，故需要頻繁地申請裝入頁面。執(zhí)行一段時間以后，進程的缺頁率將下降。采用請求調(diào)頁方式，一次裝入請求的一個頁面，磁盤I/O的啟動頻率較高，系統(tǒng)的開銷較大。174預(yù)調(diào)頁方式當進程創(chuàng)建時，預(yù)先為進程裝入多個頁面。缺頁中斷時，系統(tǒng)為進程裝入指定的頁面以及與之相臨的多個頁面。若局部性很差，預(yù)先裝入的很多頁面不會很快被引用，并會占用大量的內(nèi)存空間，反而降低系統(tǒng)的效率175頁面置換策略當發(fā)生缺頁中斷且無足夠的內(nèi)存空間時，需要置換已有的某些（個）頁面。應(yīng)該解決的基本問題：—當系統(tǒng)欲把一個頁面裝入內(nèi)存時，應(yīng)當在什么范圍內(nèi)判斷已經(jīng)沒有空閑頁框供分配？—當指定的范圍內(nèi)沒有空閑頁框時，應(yīng)當從指定的范圍內(nèi)選擇哪個頁面移出內(nèi)存？176局部置換策略—范圍可以采用局部置換或全局置換策略。局部置換：系統(tǒng)在進程自身的駐留集中判斷當前是否存在空閑頁框，并在其中進行置換。177全局置換策略在整個內(nèi)存空間內(nèi)判斷有無空閑頁框，并允許從其它進程的駐留集中選擇一個頁面換出內(nèi)存。178分配模式vs.置換模式固定分配策略局部置換策略全局置換策略可變分配策略可變分配策略+局部置換策略—即可增加或減少分配給每個活躍進程的頁框數(shù)；當進程的頁框全部用完，而需要裝入一個新的頁面時，系統(tǒng)將在該進程的當前駐留集中選擇一個頁面換出內(nèi)存。

179頁面置換策略—頁面選擇頁面置換算法：在指定的置換范圍內(nèi)，決定將哪一個頁面換出內(nèi)存。置換算法的好壞將直接影響系統(tǒng)的性能，不適當?shù)闹脫Q算法可能導(dǎo)致系統(tǒng)出現(xiàn)“抖動”現(xiàn)象。常用的頁面置換算法：最佳置換算法、最近最少使用算法、先進先出算法和時鐘算法等180最佳置換算法

(OptimalAlgorithm，OPT)基本思想：被置換的頁面是將來不再訪問，或在最遠的將來才被訪問的頁面。若采用固定分配策略，最佳置換算法可以保證系統(tǒng)的缺頁率最低。但是，無法預(yù)知一個進程在內(nèi)存的若干頁面中，哪一個頁面是將來不再訪問的，甚至最長時間內(nèi)將不再被訪問的，因而該算法是無法實現(xiàn)的。該算法可以用于評價其它置換算法的性能。181OPT置換算法示例假設(shè)系統(tǒng)分配給某進程3個頁框，且進程開始運行時，這3個頁框是空的—采用請求調(diào)頁和局部置換策略?？紤]下列頁面號引用序列：2、3、2、1、5、2、4、5、3、2、5、218222323231235235435435435235235235頁面引用序列232152453252FFFF

F

F

12次頁面引用6次缺頁中斷（F和F）3次頁面置換（F）圖3.33采用OPT置換算法的缺頁中斷（請求調(diào)頁）與（局部）頁面置換過程183OPT算法的實現(xiàn)方案據(jù)局部性原理，如果一個頁面最近被訪問過，那么，它將在不久的將來再次被訪問。如果一個頁面已經(jīng)很長時間未被訪問過，則在很久的將來，它將不會被訪問。因此，可以根據(jù)頁面的使用歷史，判斷其將來的行為。184最近最少使用置換算法

(LeastRecentlyUsedAlgorithm，LRU)LRU定義：根據(jù)頁面裝入內(nèi)存以后的使用情況，選擇淘汰最近最久未被使用的一個頁面。該算法的性能接近OPT算法，但實現(xiàn)較困難。一種方法：為每一個頁面增加一個訪問字段，用以標注該頁最后一次被訪問的時間。需要選擇淘汰頁面時，比較置換范圍內(nèi)的所有頁面的最后訪問時間，選擇訪問時間最遠的哪個頁面。實現(xiàn)該方法的開銷非常大，不易實現(xiàn)。185LRU置換算法的實現(xiàn)（續(xù)）另一種方法：將訪問頁面組織在一個堆棧中，最近訪問的頁面位于棧頂，棧底的頁面即是最久未被訪問的。?！筮M先出實踐證明，該方法的實現(xiàn)仍然很困難，系統(tǒng)付出的代價也非常大。186LRU置換算法示例

22323231251251254254354352352352頁面引用序列232152453252FFFF

F

F

F

12次頁面引用7次缺頁中斷（F和F）4次頁面置換（F）圖3.34采用LRU置換算法的缺頁中斷與頁面置換過程187先進先出置換算法

(First-inFirst-outAlgorithm，F(xiàn)IFO)淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。實現(xiàn)時，只需把一個進程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個隊列，并設(shè)置一個指針，使它總是指向最老的頁面。18822323231531521524524324324354352頁面引用序列232152