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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)進(jìn)程執(zhí)行完畢，釋放一個(gè)尺寸為2i的分區(qū)時(shí)，系統(tǒng)用下面的算法回收該分區(qū)：如果被回收分區(qū)的伙伴分區(qū)非空閑，那么保留該分區(qū)為一個(gè)獨(dú)立的空閑分區(qū)，否則[1]合并回收分區(qū)及其伙伴分區(qū)，從而得到一個(gè)尺寸為2i+1的空閑分區(qū)；[2]系統(tǒng)再次調(diào)用本算法回收上一步得到的尺寸為2i+1的空閑分區(qū)。64例如—伙伴系統(tǒng)有進(jìn)程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一個(gè)伙伴系統(tǒng)的內(nèi)存分配與回收過程663.3程序裝入技術(shù)67可執(zhí)行程序的生成步驟圖3.10高級(jí)程序處理過程源程序目標(biāo)模塊編譯庫函數(shù)裝入模塊鏈接編輯執(zhí)行目標(biāo)模塊內(nèi)存68可執(zhí)行程序的裝入？如何裝入待執(zhí)行的程序及其所需的數(shù)據(jù)？何時(shí)將程序的邏輯地址轉(zhuǎn)換為物理地址3種裝入方式：絕對(duì)裝入、重定位裝入和運(yùn)行時(shí)動(dòng)態(tài)裝入。

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

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

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

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

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

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

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

91分頁式存儲(chǔ)--基本原理

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

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

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

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

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

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

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

111圖3.20利用反置頁表進(jìn)行地址變換

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

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

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

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

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

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

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

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

OS

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(OptimalAlgorithm，OPT)基本思想：被置換的頁面是將來不再訪問，或在最遠(yuǎn)的將來才被訪問的頁面。若采用固定分配策略，最佳置換算法可以保證系統(tǒng)的缺頁率最低。但是，無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干頁面中，哪一個(gè)頁面是將來不再訪問的，甚至最長時(shí)間內(nèi)將不再被訪問的，因而該算法是無法實(shí)現(xiàn)的。該算法可以用于評(píng)價(jià)其它置換算法的性能。181OPT置換算法示例假設(shè)系統(tǒng)分配給某進(jìn)程3個(gè)頁框，且進(jìn)程開始運(yùn)行時(shí)，這3個(gè)頁框是空的—采用請求調(diào)頁和局部置換策略。考慮下列頁面號(hà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算法的實(shí)現(xiàn)方案據(jù)局部性原理，如果一個(gè)頁面最近被訪問過，那么，它將在不久的將來再次被訪問。如果一個(gè)頁面已經(jīng)很長時(shí)間未被訪問過，則在很久的將來，它將不會(huì)被訪問。因此，可以根據(jù)頁面的使用歷史，判斷其將來的行為。184最近最少使用置換算法

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

22323231251251254254354352352352頁面引用序列232152453252FFFF

F

F

F

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

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