第五章存儲管理

第5章存儲管理

存儲管理是指計算機(jī)的主存管理。主存是計算機(jī)硬件中除CPU之外的又一個寶貴的資源。存儲管理要具備下列功能（見1.2.2節(jié)P6）內(nèi)存分配

地址映射：把程序中的邏輯地址映射為物理地址

內(nèi)存保護(hù)：使多道程序間互不干擾內(nèi)存擴(kuò)充：用輔存擴(kuò)充主存，實(shí)現(xiàn)“虛擬存貯器”

本章內(nèi)容提要5.1引言5.2分區(qū)法5.3分頁技術(shù)5.4分段技術(shù)5.5段頁式技術(shù)5.6虛擬存儲器5.7請求分頁技術(shù)5.8頁面置換算法5.9內(nèi)存塊的分配和抖動問題5.10請求分段技術(shù)5.11Linux系統(tǒng)的存儲管理內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）處理機(jī)能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟失。外存儲器（簡稱外存、輔助存儲器）處理機(jī)不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內(nèi)存而言要慢得多，但它可用來長期保存用戶信息。在文件系統(tǒng)中介紹。復(fù)習(xí)：存儲器管理的相關(guān)概念5.1引言內(nèi)存（MainMemory或PrimaryMemory或RealMemory）也稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲器。圖5-1內(nèi)存在計算機(jī)系統(tǒng)中的地位用戶程序的主要處理階段 （見下頁圖）

1．編輯階段4．裝入階段

2．編譯階段5．運(yùn)行階段

3．連接階段

連接就是將編譯或匯編后得到的一組目標(biāo)模塊及它們所需的庫函數(shù)裝配成一個完整的裝入模塊的過程。

5.1.1用戶程序的地址空間4．裝入階段用戶程序經(jīng)編譯之后的每個目標(biāo)模塊都以0為基地址順序編址，這種地址稱為相對地址或邏輯地址；內(nèi)存中各物理存儲單元的地址是從統(tǒng)一的基地址開始順序編址的，這種地址稱為絕對地址或物理地址。程序裝入內(nèi)存的方式有以下三種：①絕對裝入方式②可重定位裝入方式③動態(tài)運(yùn)行時裝入方式5．運(yùn)行階段

建立進(jìn)程并執(zhí)行，得到運(yùn)行結(jié)果5.1.2重定位由程序中邏輯地址組成的地址范圍叫做邏輯地址空間，或簡稱為地址空間；由內(nèi)存中一系列存儲單元所限定的地址范圍稱做內(nèi)存空間，也稱物理空間或絕對空間。程序和數(shù)據(jù)裝入內(nèi)存時，需對目標(biāo)程序中的地址進(jìn)行修改。這種把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程稱做重定位

按重定位的時機(jī)，重定位技術(shù)可分為靜態(tài)重定位和動態(tài)重定位。1．靜態(tài)重定位靜態(tài)重定位是在目標(biāo)程序裝入內(nèi)存時，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的地址進(jìn)行修改，即把程序的邏輯地址都改成實(shí)際的內(nèi)存地址。圖5-4靜態(tài)重定位示意圖2．動態(tài)重定位：

現(xiàn)在的計算機(jī)系統(tǒng)都采用動態(tài)重定位方法動態(tài)重定位是在程序執(zhí)行期間，每次訪問內(nèi)存之前進(jìn)行重定位。這種變換是靠硬件地址轉(zhuǎn)換機(jī)構(gòu)實(shí)現(xiàn)的。圖5-5動態(tài)重定位示意圖5.1.3對換技術(shù)對換的定義把內(nèi)存中暫時不能運(yùn)行的進(jìn)程或暫時不用的程序和數(shù)據(jù)，換出到外存上，以便騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存。若對換是以整個進(jìn)程為單位，稱為整體對換（進(jìn)程對換），用于分時系統(tǒng)中；對換以“頁”或“段”為單位，稱為頁面對換（分段對換，部分對換），用于虛擬存儲系統(tǒng)。圖5-6對換兩個進(jìn)程示意圖圖5-7多道程序?qū)Q技術(shù)示例5.2分區(qū)法分區(qū)分配是為支持多道程序運(yùn)行而設(shè)計的一種最簡單的存儲管理方式。按照分區(qū)的劃分方式，可分為：固定分區(qū)法可變分區(qū)法5.2.1固定分區(qū)法固定分區(qū)就是內(nèi)存中分區(qū)的個數(shù)固定不變，各個分區(qū)的大小也固定不變，每個分區(qū)只可裝入一個進(jìn)程。1．分區(qū)的大小劃分分區(qū)大小有兩種方式：各分區(qū)大小相同——等分方式不同分區(qū)大小不同——差分方式固定分區(qū)(大小相同)固定分區(qū)(多種大小)2．內(nèi)存分配為便于內(nèi)存分配，系統(tǒng)建立一張分區(qū)說明表。內(nèi)存的申請和釋放都根據(jù)分區(qū)說明表進(jìn)行。最簡單的多道程序存儲管理方式分區(qū)大小和個數(shù)在系統(tǒng)生成時確定內(nèi)存利用率不高，已很少使用，主要應(yīng)用于控制系統(tǒng)中5.2.2動態(tài)分區(qū)法即可變分區(qū)分配1．分區(qū)的分配各分區(qū)在進(jìn)程進(jìn)入內(nèi)存時建立，使其大小適應(yīng)進(jìn)程的大小。這種技術(shù)稱為動態(tài)分區(qū)法。如IBM的OS/360MVT內(nèi)存分配與回收圖5-7表示MVT的內(nèi)存分配和進(jìn)程調(diào)度示例圖5-10MVT的內(nèi)存分配和進(jìn)程調(diào)度情況2．?dāng)?shù)據(jù)結(jié)構(gòu)為實(shí)現(xiàn)分區(qū)分配，系統(tǒng)要設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄內(nèi)存的使用情況，常用的數(shù)據(jù)結(jié)構(gòu)有：（1）空閑分區(qū)表為內(nèi)存中每個空閑分區(qū)設(shè)置一個表項(xiàng)，包含分區(qū)序號、分區(qū)始址、分區(qū)大小、狀態(tài)等數(shù)據(jù)項(xiàng)。（2）空閑分區(qū)鏈利用前、后指針將所有分區(qū)鏈成一個雙向鏈，在每個分區(qū)尾部重復(fù)設(shè)置狀態(tài)位、分區(qū)大小表目。3．分配算法（1）最先適應(yīng)算法（First-fit）空閑分區(qū)以地址遞增的次序排列特點(diǎn)：（1）優(yōu)先利用低址區(qū)，保留了高址部分的大空閑區(qū)。（2）低址部分不斷被劃分，留下許多難以利用的小空閑區(qū)（3）因每次都從低址部分查起，故查詢開銷大?？臻e區(qū)按地址遞增的次序鏈接（2）最佳適應(yīng)算法（Best-fit）空閑表是以空閑塊的大小為序、按增量形式排列的，即小塊在前，大塊在后。特點(diǎn)：（1）避免“大材小用”（2）分配后切割下的剩余部分難以再次利用以容量大小遞增的次序鏈接（3）循環(huán)適應(yīng)算法（Next-fit）最先適應(yīng)算法的變種。它不從空閑表的開頭查找，而從上次找到的可用分區(qū)的下一個空閑分區(qū)開始查找，從中選擇滿足大小要求的第一個空閑分區(qū)。特點(diǎn)：（1）為循環(huán)查找方法設(shè)置一起始查找指針。（2）使空閑分區(qū)分布得更均勻。（3）缺乏大的空閑分區(qū)。分配16KB內(nèi)存塊之前和之后的內(nèi)存配置內(nèi)存中這種容量太小、無法利用的小分區(qū)稱做“碎片”或“零頭”。在一個分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費(fèi)的空間）稱做內(nèi)部碎片，如固定分區(qū)法會產(chǎn)生內(nèi)部碎片。在所有分區(qū)之外新增的碎片稱做外部碎片.—依據(jù)碎片出現(xiàn)的位置4.碎片問題5.2.3可重定位分區(qū)分配1、緊縮解決碎片問題移動某些已分配區(qū)的內(nèi)容，使所有進(jìn)程的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端。這種技術(shù)稱為緊縮（或拼湊）。小空閑分區(qū)拼接成大分區(qū)的方法緊湊后程序、數(shù)據(jù)須進(jìn)行重定位（采用動態(tài)重定位技術(shù)）。采用緊縮法消除碎片，要花費(fèi)大量CPU時間圖5-13可重定位分區(qū)的緊縮什么時候進(jìn)行緊縮呢？有兩種不同的方案。第1種方案是當(dāng)進(jìn)程結(jié)束、釋放所占用的分區(qū)時如果它不與空閑區(qū)鄰接，就立即執(zhí)行緊縮。第2種方案是在分配進(jìn)程的分區(qū)時進(jìn)行，各個空閑分區(qū)都不能滿足該進(jìn)程的需要時進(jìn)行緊縮。2.動態(tài)重定位的實(shí)現(xiàn)過程動態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)。硬件支持

基址寄存器：存放用戶程序在內(nèi)存中的起始地址限長寄存器：存放用戶程序邏輯地址的最大范圍動態(tài)重定位的實(shí)現(xiàn)過程如圖5-11所示動態(tài)重定位的實(shí)現(xiàn)過程3.可重定位分區(qū)法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)是可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)計，提高內(nèi)存的利用率。它的缺點(diǎn)是：緊縮花費(fèi)了大量CPU時間；當(dāng)進(jìn)程大于整個空閑區(qū)時，仍要浪費(fèi)一定的內(nèi)存；進(jìn)程的存儲區(qū)內(nèi)可能放有從未使用的信息；進(jìn)程之間無法對信息共享。5.3分頁技術(shù)連續(xù)分配方式會形成許多“碎片”，“緊湊”操作的開銷又較大。采用離散分配方式可以將一個進(jìn)程直接分散地裝入到許多不相鄰接的分區(qū)中而不必再進(jìn)行“緊湊”，解決碎片問題，提高了內(nèi)存利用率。根據(jù)離散分配時所用基本單位的不同，可將其分為以下三種：

１、分頁存儲管理

用戶的地址空間被劃分為若干個固定大小

的區(qū)域，稱為“頁”。將內(nèi)存空間分成若干個物理塊，頁和塊的

大小相等?？蓪⒂脩舫绦虻娜我豁摲旁趦?nèi)存的任一塊中，實(shí)現(xiàn)了離散分配，每個用戶程序在內(nèi)存中的碎片大小不會超過一頁2、分段存儲管理

把用戶程序的地址空間分成若干個大小不等的段，每段定義一組相對完整的邏輯信息，進(jìn)行存儲分配時，以段為單位，這些段在內(nèi)存中可以不鄰接3、段頁式存儲管理

分頁、分段兩種管理方式的結(jié)合，同時具備兩者的優(yōu)點(diǎn)。既提高了存儲器的利用率，又滿足用戶要求，是目前使用較多的存儲管理方式。5.3.1分頁存儲管理的基本概念（1）邏輯空間分頁將一個進(jìn)程的邏輯地址空間分成若干大小相等的部分，每個部分稱作頁面或頁。編號從0開始（2）內(nèi)存空間分塊將內(nèi)存空間分成與頁相同大小的若干個存儲塊，稱為內(nèi)存塊或頁框頁面（或塊）的大小是由硬件（系統(tǒng)）確定。（3）邏輯地址表示由頁號和頁內(nèi)地址組成頁號p頁內(nèi)地址d0111231其中:0～11位為頁內(nèi)地址，表示每頁的大小為212，即4KB；12～31位為頁號，表示地址空間中最多可容納220=1M個頁面。地址計算已知邏輯地址A，計算頁號p和頁內(nèi)地址dp=INT(A/L),d=AMODL，L為頁面大小

若邏輯地址Ａ＝2170Ｂ頁面大小Ｌ＝１KB

則p＝INT［Ａ／Ｌ］＝２

d＝［Ａ］MODL＝122（4）內(nèi)存分配原則系統(tǒng)以塊為單位把內(nèi)存分給各個進(jìn)程進(jìn)程的每個頁面對應(yīng)一個內(nèi)存塊，并且一個進(jìn)程的若干頁可以分別裝入物理上不連續(xù)的內(nèi)存塊中。離散分配系統(tǒng)為每個進(jìn)程建立一張頁面映射表，簡稱頁表。A、在進(jìn)程地址空間內(nèi)的所有頁（0~N），依次在頁表中有一頁表項(xiàng)，記錄了相應(yīng)頁在內(nèi)存中對應(yīng)的物理塊號。B、進(jìn)程執(zhí)行時，通過查找頁表，可找到每頁在內(nèi)存中的物理塊號，實(shí)現(xiàn)了從頁號到物理塊號的地址映射。頁表的作用（5）頁表（6）內(nèi)存塊表整個系統(tǒng)有一個內(nèi)存塊表。每個內(nèi)存塊在內(nèi)存塊表中占一項(xiàng)，表明該塊當(dāng)前空閑還是已分出去了。如果已分出去，是分給哪個進(jìn)程的哪個頁面了。進(jìn)程訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址變換機(jī)構(gòu)自動地將邏輯地址分為頁號和頁內(nèi)地址（p,d）。借助于頁表，將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號物理塊號和頁內(nèi)地址送入物理地址寄存器中，拼接成實(shí)際內(nèi)存地址5.3.2分頁系統(tǒng)中的地址映射圖5-17分頁系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)分頁技術(shù)不存在外部碎片，只存在內(nèi)部碎片每個進(jìn)程平均有半個頁面的內(nèi)部碎片

頁面的大小由機(jī)器的地址結(jié)構(gòu)決定。選擇頁面較小：內(nèi)存碎片小，減少碎片的總空間，提高了內(nèi)存的利用率。每個進(jìn)程要求的頁面多，導(dǎo)致頁表過長，占用內(nèi)存多，降低頁面對換的效率。選擇頁面較大：減少頁表長度，提高對換效率，頁內(nèi)碎片增大。頁面的大小是2的冪，常在29~212之間，即在512字節(jié)~4KB之間。5.3.3頁面尺寸頁表功能的實(shí)現(xiàn)：2種方法①使用一組專門的寄存器：一個頁表項(xiàng)用一個寄存器，可通過高速寄存器提高地址變換的速度。寄存器成本較高，適于較小系統(tǒng)中②將頁表駐留在內(nèi)存：由一個頁表基址寄存器PTBR指向該頁表。整個系統(tǒng)只有一個PTBR。進(jìn)程未執(zhí)行時，指向頁表的指針存放在本進(jìn)程的PCB中，進(jìn)程執(zhí)行時將其裝入到PTBR中。5.3.4硬件支持內(nèi)存中放置頁表帶來存取速度下降的矛盾。利用頁表存取數(shù)據(jù)時要兩次訪問內(nèi)存：第一次：訪問頁表，完成地址轉(zhuǎn)換。第二次：利用地址獲取數(shù)據(jù)。這樣，使計算機(jī)的處理速度降低1/2?？毂恚ɑ騎ranslationLookasideBuffer,TLB）?？毂砻宽?xiàng)包括鍵號和值兩部分，鍵號是當(dāng)前進(jìn)程正在使用的某個頁面號，值是該頁面所對應(yīng)的物理塊號。圖5-18利用快表實(shí)現(xiàn)地址轉(zhuǎn)換示例轉(zhuǎn)換過程：在CPU給出有效地址后，由地址變換機(jī)構(gòu)自動地將頁號p送入高速緩沖寄存器，并將此頁號與高速緩沖存儲器中的所有頁號進(jìn)行比較，若其中有與此相匹配的頁號，則表示要訪問的頁表項(xiàng)在快表中。這樣，可直接讀出該頁所對應(yīng)的物理塊號，并送到物理地址寄存器中。若在快表中未找到對應(yīng)的頁表項(xiàng)，還需再訪問內(nèi)存中的頁表，找到后，把從頁表項(xiàng)中讀出的物理塊號送地址寄存器；同時，還將此頁表項(xiàng)存入快表中的一個寄存器單元中，即重新修改快表。若快表存已滿，則OS淘汰最老且已被認(rèn)為不再需要的頁表項(xiàng)。

反映快表使用效果的概念——命中率。命中率：反映了在快表中的進(jìn)程頁表占該進(jìn)程總頁表數(shù)的百分比。對于大型作業(yè)而言，不可能把全部頁表放入快表中例：檢索快表的時間為20ns，訪問內(nèi)存的時間為100ns。①若能在快表中找到CPU給出的頁號，則存 取一個數(shù)據(jù)所需時間：t1=100+20=120ns

②若不能在快表中找到該頁號，則存取一個數(shù)據(jù)所 需時間：t2=100+20+100=220ns5.3.5保護(hù)方式分頁系統(tǒng)提供的存儲保護(hù)方式有三種：（1）利用頁表本身進(jìn)行保護(hù)頁表基址信息放在進(jìn)程PCB中頁表長度寄存器PTLR（2）設(shè)置存取控制位R、RW、RX（3）設(shè)置合法標(biāo)志在頁表的每項(xiàng)中設(shè)置合法/非法位。5.3.6頁表的構(gòu)造多級頁表散列頁表倒置頁表1．多級頁表問題提出：一個具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB，則每個進(jìn)程頁表項(xiàng)可達(dá)1M個，且每個頁表項(xiàng)占用4個字節(jié)。因此每個進(jìn)程僅頁表就要占4MB的內(nèi)存空間，而且還要求是連續(xù)的。解決方法：（1）對頁表所需內(nèi)存空間采用離散分配方式，來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題。（2）只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)放在磁盤上，需要時再調(diào)入內(nèi)存。頁號p頁內(nèi)地址d0111231圖5-19兩級頁表地址結(jié)構(gòu)示意圖

采用頁表分頁的方法，使每個頁面的大小與內(nèi)存物理塊的大小相同，并為它們編號，這樣可離散地將各個頁面分別存放在不同的物理塊中；同樣為離散分配的頁表再建立一張頁表（稱外層頁表—

OuterPageTable），在每個頁表項(xiàng)中記錄了頁表頁面的物理塊號。圖5-20兩級頁表結(jié)構(gòu)示意圖圖5-21兩級頁表結(jié)構(gòu)的地址轉(zhuǎn)換圖5-22三級頁表地址結(jié)構(gòu)示意圖32位的機(jī)器：兩級頁表結(jié)構(gòu)

64位的機(jī)器：四級頁表2．散列頁表處理32位地址空間的通用方式是使用散列頁表HashedPageTable，以頁號作為參數(shù)形成散列值。散列表中每一項(xiàng)有一個鏈表，它把有相同散列值的元素鏈接起來。每個鏈表元素由三部分組成：①頁號；②對應(yīng)的內(nèi)存塊號；③指向鏈表中下一個元素的指針。

圖5-23散列頁表構(gòu)成及地址轉(zhuǎn)換過程它是按內(nèi)存塊號排序的，每個內(nèi)存塊占有一個表項(xiàng)。每個表項(xiàng)包括存放在該內(nèi)存塊中頁面的頁號和擁有該頁面的進(jìn)程標(biāo)識符。倒置頁表減少頁表占用的內(nèi)存，增加了檢索頁表時消耗的時間3．倒置頁表圖5-24倒置頁表構(gòu)成及地址轉(zhuǎn)換過程共享頁面，有效節(jié)省內(nèi)存空間。(見下頁圖)相關(guān)進(jìn)程的邏輯空間中的頁指向相同的內(nèi)存塊(該塊中放有共享程序或數(shù)據(jù))要求可共享的代碼必須是可再入代碼（或純碼，在其執(zhí)行過程中本身不做任何修改的代碼，通常由指令和常數(shù)組成）。數(shù)據(jù)頁面往往不能共享。5.3.7頁面共享圖5-25頁面共享示例分頁系統(tǒng)中實(shí)現(xiàn)頁的共享比較困難，因?yàn)榉猪撓到y(tǒng)中把作業(yè)或進(jìn)程的地址空間劃分成頁面的做法對用戶是屏蔽的。（用戶不知道作業(yè)分了多少頁和每頁的界限）引入原因：為了滿足用戶（程序員）在編程和使用上的多種要求,有些要求是其它幾種存儲管理方式難以滿足的。用戶在編程和使用上的五種要求方便編程信息共享信息保護(hù)動態(tài)鏈接動態(tài)增長5.4分段技術(shù)5.4.1分段存儲管理的基本概念1．分段用戶的邏輯地址空間劃分為若干段，每個段定義了一組邏輯信息，每個段都有自己的名字——段名（通常用一個段號代替），段的長度由相應(yīng)的邏輯信息組的長度決定。每個段都從0開始編址，并采用一段連續(xù)的地址空間。圖5-26分段地址空間示例作業(yè)的邏輯地址空間：分段情況下要求每個作業(yè)的地址空間按照程序的自然邏輯關(guān)系分成若干段，每個段有自己的段名。2．程序的地址結(jié)構(gòu)邏輯地址要用兩個成分來表示：段號s和段內(nèi)地址d。在分段存儲情況下，進(jìn)程的邏輯地址空間是二維的。以上結(jié)構(gòu)允許一個作業(yè)最多有216(64K)個段，每段最大長度為216=64KB。3．內(nèi)存分配內(nèi)存以段為單位進(jìn)行分配，每段單獨(dú)占用一塊連續(xù)的內(nèi)存分區(qū)。各分區(qū)的大小由對應(yīng)段的大小決定。各段是離散分配于不同的區(qū)域4．段表和段表地址寄存器系統(tǒng)為每個進(jìn)程建立一個段映射表，簡稱“段表”。每個段在段表中占有一項(xiàng)，段表項(xiàng)中包含段號、段長和段起始地址（又稱“基址”）等段表實(shí)現(xiàn)了邏輯段到物理內(nèi)存區(qū)的映射系統(tǒng)還要建立一個段表地址寄存器，它有兩部分：一部分指出該段表在內(nèi)存的起始地址；另一部分指出該段表的長度。5．分頁和分段的主要區(qū)別相同之處：都采用離散分配方式；都要通過地址映射機(jī)構(gòu)來實(shí)現(xiàn)地址變換。

不同之處：①頁是信息的物理單位，段是信息的邏輯單位。②頁的大小是由系統(tǒng)確定的，段的長度因段而異，由用戶決定③分頁的進(jìn)程地址空間是一維的，分段的進(jìn)程地址空間是二維的。④分頁系統(tǒng)很難實(shí)現(xiàn)過程和數(shù)據(jù)的分離，分段系統(tǒng)卻可以很容易實(shí)現(xiàn)這些功能。5.4.2地址轉(zhuǎn)換圖5-28分段地址轉(zhuǎn)換過程與分頁系統(tǒng)一樣，通過段表訪問一個數(shù)據(jù)需兩次訪問內(nèi)存為提高訪問速度，亦可增設(shè)一個快表，用于保存最近常用的段表項(xiàng)5.4.3段的共享和保護(hù)1．段的共享分段管理的一個優(yōu)點(diǎn)是提供對代碼或數(shù)據(jù)的有效共享。共享是在段一級實(shí)現(xiàn)的，任何共享信息可以單獨(dú)成為一段。也可以只共享部分程序。圖5-29分段系統(tǒng)中段的共享2．段的保護(hù)：分段管理的另一個優(yōu)點(diǎn)段的保護(hù)措施包括以下三種：①存取控制在段表表項(xiàng)中設(shè)置存取控制字②段表本身可起保護(hù)作用。表項(xiàng)中設(shè)置該段的長度限制－段長段表地址寄存器中有段表長度的信息。③保護(hù)環(huán)（一種較完善的存取控制機(jī)制）低編號的環(huán)具有高優(yōu)先權(quán)（１）一個程序可以訪問駐留在相同或較低特權(quán)環(huán)中的數(shù)據(jù)。（２）一個程序可以調(diào)用駐留在相同或較高特權(quán)環(huán)中的服務(wù)。

程序間的控制傳輸數(shù)據(jù)訪問程序調(diào)用和數(shù)據(jù)訪問的關(guān)系：

5.5段頁式技術(shù)

集中了分頁、分段系統(tǒng)的優(yōu)點(diǎn)。既有分段系統(tǒng)便于實(shí)現(xiàn)、分段可共享、易于保護(hù)、可動態(tài)鏈接等優(yōu)點(diǎn)，又能象分頁系統(tǒng)可很好地解決內(nèi)存碎片問題，并可為各段離散地分配內(nèi)存。5.5.1段頁式存儲管理的基本原理將用戶程序先分段，每段賦予一個段名，再將每個段分頁內(nèi)存分成大小相等的塊邏輯地址由段號s、頁號p和頁內(nèi)地址d組成。為實(shí)現(xiàn)地址變換，系統(tǒng)為每個進(jìn)程設(shè)置段表和頁表。段表的內(nèi)容為：頁表始址和頁表長度段表地址寄存器：指出進(jìn)程的段表長度和段表始址5.5.2地址轉(zhuǎn)換過程圖5-31段頁式系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)段頁式系統(tǒng)中，為了獲得一條指令或數(shù)據(jù)，需三次訪問內(nèi)存：1）訪問內(nèi)存中的段表，取得頁表始址；2）訪問內(nèi)存中的頁表，取得該頁所在的物理塊號，并將該塊號與頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址；3）從第二次訪問所得地址中，取出指令或數(shù)據(jù)。為了提高速度，可在地址變換機(jī)構(gòu)中設(shè)置一高速緩沖寄存器（快表）前面講的各種存儲管理方式，都要求將一個作業(yè)全部裝入內(nèi)存方能運(yùn)行，因此可能出現(xiàn)這樣的情況:第一、有的作業(yè)很大，不能一次性全部裝入內(nèi)存；第二、大量作業(yè)需運(yùn)行，不能同時裝入內(nèi)存，只能將少數(shù)作業(yè)先裝入，多數(shù)作業(yè)留在外存上。如何解決？5.6虛擬存儲器進(jìn)程在執(zhí)行之前要全部裝入內(nèi)存，這種限制不合理：①程序中往往含有不會被執(zhí)行的代碼。②分配的內(nèi)存空間會大于它們的實(shí)際需要。③一個程序的某些選項(xiàng)和特性可能很少使用。程序的執(zhí)行過程也顯示出局部性。分別調(diào)入內(nèi)存。至少會帶來如下兩點(diǎn)好處： ①用戶編制程序時不必考慮內(nèi)存容量的限制 ②在一定容量的內(nèi)存中就可同時裝入更多的進(jìn)程5.6.1虛擬存儲器的概念VirtualMemory是用戶能作為可編址內(nèi)存對待的虛擬存儲空間，它使用戶邏輯存儲器與物理存儲器分離，是操作系統(tǒng)給用戶提供的一個比真實(shí)內(nèi)存空間大得多的地址空間。物質(zhì)基礎(chǔ)是二級存儲器結(jié)構(gòu)和動態(tài)地址轉(zhuǎn)換機(jī)構(gòu)（DAT）。虛擬存儲器實(shí)質(zhì)上是把用戶地址空間和實(shí)際的存儲空間區(qū)分開來。虛擬存儲器的容量主要受到兩方面的限制：①指令中表示地址的字長。②外存的容量。１、請求分頁系統(tǒng)：在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)

置換時以頁面為單位。虛擬存儲器的實(shí)現(xiàn)方法

——均建立在離散分配的基礎(chǔ)上2、請求分段系統(tǒng)：在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段及分段置換功能后形成的段式虛擬存儲系統(tǒng)。置換是以段為單位進(jìn)行的。

5.6.2虛擬存儲器的特征①虛擬擴(kuò)充：從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量②部分裝入：進(jìn)程執(zhí)行時，只需將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存，以后運(yùn)行到其它部分時再從外存調(diào)入。③離散分配：在內(nèi)存分配時采用離散分配方式④多次對換：即在進(jìn)程運(yùn)行期間，允許將那些暫不使用的程序和數(shù)據(jù)，從內(nèi)存調(diào)至外存的對換區(qū)，待以后需要時再將它們從外存調(diào)至內(nèi)存，也允許將暫不運(yùn)行的進(jìn)程調(diào)至外存，待它們重新具有運(yùn)行條件時再調(diào)入內(nèi)存。有效地提高了內(nèi)存的利用率。虛擬存儲：以CPU時間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。5.7請求分頁技術(shù)5.7.1請求分頁存儲管理的基本思想請求分頁存儲管理技術(shù)是在單純分頁技術(shù)基礎(chǔ)上發(fā)展起來的，二者的根本區(qū)別在于請求分頁提供虛擬存儲器。它的基本思想是：當(dāng)一個進(jìn)程的部分頁面在內(nèi)存時就可調(diào)度它運(yùn)行；在運(yùn)行過程中若用到的頁面尚未在內(nèi)存，則把它們動態(tài)換入內(nèi)存。為了標(biāo)示進(jìn)程的頁面是否已在內(nèi)存，在每個頁表項(xiàng)中增加一個標(biāo)志位。

5.7.2硬件支持及缺頁處理1．頁表機(jī)制頁表項(xiàng)通常包含下列5種信息：①內(nèi)存塊號。②標(biāo)志位。這一位用來標(biāo)示對應(yīng)的頁面是否已裝入內(nèi)存。如果該位是1，表示該表項(xiàng)是有效的，可以使用，即該頁在內(nèi)存中；如果該位是0，則表示該表項(xiàng)對應(yīng)的頁面目前不在內(nèi)存中，訪問該頁會引起缺頁中斷。③保護(hù)位：規(guī)定該頁的訪問權(quán)限。④修改位和引用位。這兩位用來記錄該頁的使用狀況。⑤禁止緩存位：禁止該頁被緩存。2．缺頁中斷機(jī)構(gòu)圖：指令執(zhí)行步驟與缺頁中斷處理過程5.7.3請求分頁技術(shù)的性能以有效存取時間說明令p表示缺頁中斷的概率（0≤p≤1），簡稱缺頁率，它等于缺頁次數(shù)與全部訪問內(nèi)存次數(shù)之比。有效存取時間可表示為：

(1-p)×ma+p×缺頁處理時間

ma為內(nèi)存存取時間，一般為10～200ns為了算出有效存取時間，必須知道處理缺頁中斷所需的時間。缺頁導(dǎo)致以下一系列動作（設(shè)當(dāng)前進(jìn)程為A）：(1)捕俘進(jìn)入操作系統(tǒng)。(2)保存進(jìn)程A的各個寄存器和進(jìn)程狀態(tài)信息。(3)確定該中斷是缺頁引起的。(4)檢查對該頁的訪問是合法的，并確定該頁在磁盤上的地址。(5)把該頁從盤上讀到空閑內(nèi)存塊中。(6)在等待盤I/O完成時，把CPU分給其他進(jìn)程（如進(jìn)程B）。(7)盤I/O完成，發(fā)出盤中斷。(8)保存進(jìn)程B的用戶寄存器和進(jìn)程狀態(tài)。(9)確定該中斷來自磁盤。(10)調(diào)整頁表和其他表格，標(biāo)明所需頁已放入內(nèi)存。(11)進(jìn)程A就緒，等待分配CPU。(12)調(diào)度到進(jìn)程A，則恢復(fù)它的各寄存器、進(jìn)程狀態(tài)和新的頁表，然后重新執(zhí)行前面被中斷的指令。并不是在任何情況下都要執(zhí)行以上各步。在任何情況下，缺頁中斷處理所花費(fèi)的時間主要有：①處理缺頁中斷的時間。②調(diào)入該頁的時間。③重新啟動該進(jìn)程的時間。②項(xiàng)是將頁面從盤上讀到內(nèi)存，花費(fèi)的時間包括三部分：磁盤尋道時間（即磁頭從當(dāng)前磁道移至指定磁道所用的時間）旋轉(zhuǎn)延遲時間（磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時間）數(shù)據(jù)傳輸時間典型磁盤的旋轉(zhuǎn)延遲時間約為8ms，尋道時間約為15ms，傳輸時間是1ms。全部換頁時間將近25ms。

如果把平均缺頁服務(wù)時間取為25ms，內(nèi)存存取時間取為100ns，那么有效存取時間

=(1-p)×100+p×25000000=100+24999900×p有效存取時間正比于缺頁率，如果期望計算機(jī)性能下降率不超過10％，則有：

110＞100+25000000×p10＞25000000×pp＜0.0000004即缺頁率不能超過千萬分之四在請求分頁系統(tǒng)中使缺頁率保持在很低水平非常重要虛存管理的核心把選擇換出頁面的算法稱為頁面置換算法。一個進(jìn)程在運(yùn)行過程中，頻繁地更換頁面，將系統(tǒng)大部分時間花費(fèi)在頁面置換上，則稱該進(jìn)程發(fā)生了“抖動”（顛簸）不適當(dāng)?shù)乃惴赡軙?dǎo)致進(jìn)程發(fā)生“抖動”。一個好的頁面算法應(yīng)避免“抖動”發(fā)生，即具有較低的頁面更換頻率。

5.8頁面置換算法參見圖：指令執(zhí)行步驟與缺頁中斷處理過程5.8.1頁面置換1．頁面置換過程2．頁面走向存儲訪問序列也叫頁面走向。為減少算法計算量，進(jìn)行如下簡化：①對于給定的頁面大小，僅考慮其頁號，不關(guān)心完整的地址。②如果當(dāng)前對頁面p進(jìn)行了訪問，那么，馬上又對該頁訪問就不會缺頁。這樣連續(xù)出現(xiàn)的同一頁號就簡化為一個頁號。

0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105若每頁100個字節(jié)，則頁面走向簡化為：

1，4，1，6，1，6，1，6，1，6，1對特定的訪問序列來說，為確定缺頁數(shù)量和頁面置換算法，還要知道可用的內(nèi)存塊數(shù)一般來說，隨著可用塊數(shù)的增加，缺頁數(shù)將減少。圖5-35缺頁量與內(nèi)存塊數(shù)關(guān)系圖為了說明下面的頁面置換算法，統(tǒng)一采用下述頁面走向：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

并且假定每個作業(yè)只有三個內(nèi)存塊可供使用。5.8.2先進(jìn)先出法（FIFO）出現(xiàn)最早的算法總是淘汰在內(nèi)存中停留時間最長（年齡最老）的一頁，即先進(jìn)入內(nèi)存的頁，先被換出。圖5-36FIFO頁面置換序列共發(fā)生12次頁面置換（15次缺頁中斷）FIFO頁面置換算法的優(yōu)點(diǎn)是容易理解且方便程序設(shè)計。然而，它的性能并不很好。FIFO頁面置換算法的另一個缺點(diǎn)是存在Belady異?，F(xiàn)象，即缺頁率隨內(nèi)存塊增加而增加。圖5-37關(guān)于一個頁面走向的FIFO淘汰算法的缺頁曲線5.8.3最佳置換法（OPT）最佳置換算法（OptimalReplacement,OPT）其實(shí)質(zhì)是：為調(diào)入新頁面而必須預(yù)先淘汰某個老頁面時，所選擇的老頁面應(yīng)在將來不被使用，或者是在最遠(yuǎn)的將來才被訪問。因以上限定的頁面無法預(yù)知，故算法無法實(shí)現(xiàn)。但可作為標(biāo)準(zhǔn)去評價其他算法圖5-38最佳頁面置換產(chǎn)生第一次頁面置換：因0將于第5次訪問，1將于第14次訪問，而7在第18次才需訪問，故將7換出，調(diào)入2。共發(fā)生6次頁面置換，9次缺頁中斷。

OPT算法示例：FIFO算法的依據(jù)是各個頁面調(diào)入內(nèi)存的時間，故性能較差。OPT算法依據(jù)今后使用頁面的時間，性能最好，難于實(shí)現(xiàn)。LRU算法以“最近的過去”作為“不久將來”的近似實(shí)質(zhì)是：當(dāng)需要置換一頁時，選擇在最近一段時間里最久沒有使用過的頁面予以淘汰。5.8.4最近最少使用置換法（LRU）LRU算法示例

共發(fā)生9次頁面置換，12次缺頁中斷。最佳置換算法：向后看，依據(jù)以后各頁的使用情況。最近最久未用算法：向前看，依據(jù)以前各頁的使用情況頁面的過去與未來的走向之間并無必然的聯(lián)系，故兩種算法并無實(shí)質(zhì)性的關(guān)聯(lián)。

LRU算法需要實(shí)際硬件的支持。實(shí)現(xiàn)時的問題是：怎樣確定最后訪問以來所經(jīng)歷時間的順序。有以下兩種可行的辦法：①計數(shù)器每個頁表項(xiàng)對應(yīng)一個使用時間字段，并給CPU增加一個邏輯時鐘或計數(shù)器，每進(jìn)行一次訪問，該時鐘加1。每當(dāng)訪問一個頁面時，時鐘寄存器的內(nèi)容被復(fù)制到相應(yīng)頁表項(xiàng)的使用字段中。選擇時間值最小的頁面為淘汰頁。②棧：保存當(dāng)前使用的各頁面的頁面號。

A、

系統(tǒng)為每個進(jìn)程配置一個頁面使用棧。

B、當(dāng)進(jìn)程訪問某頁時，將該頁面的頁面號從棧中移出，壓入棧頂。這樣棧頂始終是最新被訪問頁面的編號，而棧底所存的頁號即是最近最久未使用的。圖5-40利用棧記錄目前訪問最多的頁面示例5.8.5第二次機(jī)會置換法（SCR）第二次機(jī)會置換法（SecondChancePageReplacement,SCR）是對FIFO算法的改進(jìn)——

避免把經(jīng)常使用的頁面置換出去。當(dāng)選擇某一頁面置換時，就檢查最老頁面的引用位：如果是0，就立即淘汰該頁；如果該引用位是1，就給它第二次機(jī)會，將引用位清0，并放入頁面鏈表末尾，并把它的裝入時間重置為當(dāng)前時間，然后選擇下一個FIFO頁面。圖5-41第二次機(jī)會法示例如果所有的頁面先前都被訪問過，即它們的引用位都為1，那么，該算法就降為FIFO算法。5.8.6時鐘置換法（Clock）1．簡單時鐘置換法將所有頁面都鏈成一個環(huán)狀鏈表，用一個指針指向最老的頁面。當(dāng)缺頁時，檢查指針指向的頁面，若引用位是0則淘汰該頁，若為1，則清0，把指針前移一個位置。圖5-42時鐘置換法示意圖該算法又稱最近未使用置換法（NotRecentlyUsed,NRU）2．改進(jìn)的時鐘置換法首選淘汰頁的條件

未使用過的頁面未被修改過的頁面四種類型的頁面（由頁表中頁面引用位、修改位）

00：最近既未被訪問，也未被修改，是最佳淘汰頁；01：最近未被訪問，已修改，并不是很好的淘汰頁；10：最近訪問過，未修改，有可能再被訪問的頁；11：最近訪問過，已修改，有可能再被訪問的頁。改進(jìn)型Clock算法的執(zhí)行過程從指針?biāo)甘镜漠?dāng)前位置開始，掃描循環(huán)隊(duì)列，尋找00的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。注意：第一次掃描期間不改變引用位。

若第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找01的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。注意：在第二輪掃描期間將所有經(jīng)過的頁面的引用位置為0。若第二步也失敗，即未找到第二類頁面，則將指針返回到開始位置，并將所有的訪問位置0。然后，重復(fù)第一步，若仍然失敗，必要時再重復(fù)第二步，此時必能找到被淘汰的頁。5.8.7最少使用置換法（LFU）

LeastFrequentlyUsed，LFU為每個頁面設(shè)置一個軟件計數(shù)器，用于記載該頁被訪問的次數(shù)，初值為0。發(fā)生缺頁時，淘汰其計數(shù)值最小的頁。LRU：時間LFU：次數(shù)5.8.8頁面緩沖算法（PageBuffering）

基本思想：

按照FIFO算法選擇需要淘汰的頁面，該被淘汰的頁面將放入兩個鏈表中的一個：若頁面未被修改過，則將它放入空閑頁鏈表，否則放入修改頁鏈表。當(dāng)修改頁鏈表中被修改頁面達(dá)一定數(shù)量時，再將它們一起（即成簇）寫回到磁盤，以減少磁盤的I/O的操作次數(shù)，從而減少磁盤訪問時間。自由頁表和修改頁表相當(dāng)于頁的Cache。被替換的頁仍然保留在主存中。淘汰頁不是在主存中發(fā)生物理移動，而只是將頁表中的表項(xiàng)移動到空閑頁鏈表和修改頁鏈表。5.9內(nèi)存塊的分配和抖動問題5.9.1內(nèi)存塊的分配1．最少內(nèi)存塊數(shù)分給每個進(jìn)程的最少內(nèi)存塊數(shù)是指保證進(jìn)程正常運(yùn)行所需的最少內(nèi)存塊數(shù)，它是由指令集結(jié)構(gòu)決定的。2．內(nèi)存塊的分配①固定分配策略分配給進(jìn)程的內(nèi)存塊數(shù)是固定的，且在最初裝入時（即進(jìn)程創(chuàng)建時）確定塊數(shù)。②可變分配策略允許分給進(jìn)程的內(nèi)存塊數(shù)隨進(jìn)程的活動而改變。頁面置換范圍全局置換允許一個進(jìn)程從全體存儲塊的集合中選取淘汰塊，盡管該塊當(dāng)前分配給其他進(jìn)程，還是能強(qiáng)行占用。局部置換是每個進(jìn)程只能從分給它的一組內(nèi)存塊中選擇淘汰塊。

可組合出以下三種適用的策略：

A、固定分配、局部置換

分配：為每個進(jìn)程分配一固定數(shù)目的物理塊，整個運(yùn)行期間不再改變。置換：從該進(jìn)程在內(nèi)存的幾個頁面中選出一頁換出。為每個進(jìn)程分配多少個頁面的內(nèi)存難以確定：

太少：缺頁中斷增多，系統(tǒng)吞吐量小。

太多：駐留內(nèi)存的進(jìn)程數(shù)目減少，資源利用率低，對換時花費(fèi)時間較多。

B、可變分配、局部置換

分配：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物理塊。置換：缺頁時，從該進(jìn)程內(nèi)存頁面中換出一頁。若進(jìn)程運(yùn)行中頻繁發(fā)生缺頁中斷，系統(tǒng)再為其增加若干附加的物理塊，直至其缺頁率減少到適當(dāng)程度為止；若進(jìn)程在運(yùn)行過程中缺頁率特別低，系統(tǒng)會適當(dāng)減少分配給其的物理塊，但不應(yīng)引起其缺頁率的明顯增加。

C、可變分配、全局置換分配：系統(tǒng)為每個進(jìn)程分配一定數(shù)目的物理塊，OS