页式存储管理
頁式存儲(chǔ)管理為操作系統(tǒng)中的內(nèi)容，但是在計(jì)算機(jī)組成原理中的虛擬存儲(chǔ)器部分也用到了這一方式。
分區(qū)式存儲(chǔ)管理最大的缺點(diǎn)是碎片問題嚴(yán)重，內(nèi)存利用率低。究其原因，主要在于連續(xù)分配的限制，即它要求每個(gè)作用在內(nèi)存中必須占一個(gè)連續(xù)的分區(qū)。
如果允許將一個(gè)進(jìn)程分散地裝入到許多不相鄰的分區(qū)中，便可充分地利用內(nèi)存，而無需再進(jìn)行“緊湊”。
基于這一思想，產(chǎn)生了“非連續(xù)分配方式”，或者稱為“離散分配方式”。
?
連續(xù)分配：為用戶進(jìn)程分配的必須是一個(gè)連續(xù)的內(nèi)存空間。
非連續(xù)分配：為用戶進(jìn)程分配的可以是一些分散的內(nèi)存空間。
分頁存儲(chǔ)管理的思想：把內(nèi)存分為一個(gè)個(gè)相等的小分區(qū)，再按照分區(qū)大小把進(jìn)程拆分成一個(gè)個(gè)小部分。
分頁存儲(chǔ)管理分為：實(shí)分頁存儲(chǔ)管理和虛分頁存儲(chǔ)管理
?
一、實(shí)分頁式存儲(chǔ)管理
實(shí)分頁式存儲(chǔ)最大的優(yōu)點(diǎn)是內(nèi)存利用率高，與目前流行的虛分頁存儲(chǔ)管理相比，具有實(shí)現(xiàn)簡(jiǎn)單，程序運(yùn)行快的優(yōu)點(diǎn)。目前，飛速發(fā)展的硬件制造技術(shù)使得物理內(nèi)存越來越大，因此我們認(rèn)為，實(shí)分頁式存儲(chǔ)管理將是一種最有發(fā)展前途的存儲(chǔ)管理方式。
1、基本原理
假設(shè)一個(gè)大型飯店，所有的客房都是標(biāo)準(zhǔn)的雙人間，部分客房已經(jīng)住進(jìn)客人，現(xiàn)在又有一個(gè)旅游團(tuán)要求入住。接待員統(tǒng)計(jì)了一下，對(duì)旅游團(tuán)領(lǐng)隊(duì)說：“貴團(tuán)全體成員都能住下，兩人一個(gè)房間，但是不能住在同一樓層了，因?yàn)槊繉涌罩目头坎粔?#xff0c;更沒有幾個(gè)挨著的。請(qǐng)?jiān)?#xff01;”。對(duì)于這樣的安排，一般人不會(huì)感到奇怪。因?yàn)槁糜螆F(tuán)本來就是由一位位個(gè)人或夫妻等組成的，而飯店的客房本來也是兩人一間的，兩人一組正好可住在一個(gè)客房里；另外，飯店幾乎每天都有入住的和退房的客人，想在同一樓層找?guī)组g挨著的客房實(shí)在不容易。
①將整個(gè)系統(tǒng)的內(nèi)存空間劃分成一系列大小相等的塊，每一塊稱為一個(gè)物理塊、物理頁或實(shí)頁，頁架或頁幀（frame），可簡(jiǎn)稱為塊（block）。所有的塊按物理地址遞增順序連續(xù)編號(hào)為0、1、2、……。
????????這里的塊相當(dāng)于飯店的客房，系統(tǒng)對(duì)內(nèi)存分塊相當(dāng)于飯店把大樓所有的客房都設(shè)計(jì)成標(biāo)準(zhǔn)的雙人間。
②每個(gè)作業(yè)的地址空間也劃分成一系列與內(nèi)存塊一樣大小的塊，每一塊稱為一個(gè)邏輯頁或虛頁，也有人叫頁面，可簡(jiǎn)稱為頁（page）。所有的頁按照邏輯地址遞增順序連續(xù)編號(hào)為0、1、2、……。
???????????這里，對(duì)作業(yè)地址空間分頁就相當(dāng)于把旅游團(tuán)成員分成兩人一組。
?
③一個(gè)作業(yè)，只要它的總頁數(shù)不大于內(nèi)存中的可用塊數(shù)，系統(tǒng)就可以對(duì)它實(shí)施分配。系統(tǒng)裝入作業(yè)時(shí)，以頁為單位分配內(nèi)存，一頁分配一個(gè)塊，作業(yè)所有的頁所占的塊可以不連續(xù)。系統(tǒng)同時(shí)為這個(gè)作業(yè)建立一個(gè)頁號(hào)與塊號(hào)的對(duì)照表，稱為頁表。
??????? 這就像飯店有個(gè)記錄客戶入住情況的客戶登記表一樣。另外，飯店安排客戶入住是要查看全部客房的使用情況一覽表，相應(yīng)地系統(tǒng)給作業(yè)分配內(nèi)存時(shí)要查看主存分配表或者內(nèi)存塊說明表。‘
④每個(gè)塊的大小是固定的，一般是個(gè)1/2KB～4KB之間的數(shù)值（請(qǐng)讀者思考：塊尺寸為什么太大或太小都不好），而且必須是個(gè)2的冪次。
???????? 對(duì)塊尺寸這樣規(guī)定相當(dāng)于飯店規(guī)定客房是雙人間。可以設(shè)想一下，如果上例中飯店所有的客房都是十人間的話，效益肯定不如全是雙人間的好
?
實(shí)模式下分頁存儲(chǔ)管理的基本原理：
操作系統(tǒng)以頁框?yàn)閱挝粸楦鱾€(gè)進(jìn)程分配內(nèi)存空間。系統(tǒng)自動(dòng)地將作業(yè)的地址空間分頁，將系統(tǒng)的主存空間分塊，頁與塊等大小，在作業(yè)運(yùn)行時(shí)，一次性把作業(yè)的全部頁面裝入內(nèi)存，各個(gè)頁所占的內(nèi)存塊可以不連續(xù)，也不必按先后順序，可以放到不相鄰的各個(gè)頁框中。
這實(shí)際是個(gè)把作業(yè)從地址空間映射到存儲(chǔ)空間的過程
2、頁表
頁面的劃分完全是一種系統(tǒng)硬件的行為，一個(gè)邏輯地址放到這種地址結(jié)構(gòu)中，自然就分成了頁號(hào)和頁內(nèi)單元號(hào)兩部分。
?
頁面大小為：4KB
在分頁系統(tǒng)中，允許將作業(yè)（進(jìn)程）的任一頁裝入到內(nèi)存中的任一可用的物理塊中，但進(jìn)程的地址空間本來是連續(xù)的，若把他分頁后裝入到不相鄰的物理塊中，要保證系統(tǒng)仍能正確運(yùn)行，就要實(shí)現(xiàn)從進(jìn)程的邏輯地址變換為內(nèi)存的物理地址。
所以，系統(tǒng)為每個(gè)進(jìn)程建立一張頁面映射表，簡(jiǎn)稱頁表。
?
3、地址映射
在系統(tǒng)中設(shè)置地址變換機(jī)構(gòu)，能將用戶進(jìn)程地址空間中的邏輯地址變?yōu)閮?nèi)存空間中的物理地址。
由于頁面和物理塊的大小相等，頁內(nèi)偏移地址和塊內(nèi)偏移地址是相同的。無須進(jìn)行從頁內(nèi)地址到塊內(nèi)地址的轉(zhuǎn)換。
地址變換機(jī)構(gòu)的任務(wù)，關(guān)鍵是將邏輯地址中的頁號(hào)轉(zhuǎn)換為內(nèi)存中的物理塊號(hào)。物理塊號(hào)內(nèi)的偏移地址就是頁內(nèi)偏移地址。
頁表的作用就是從頁號(hào)到物理塊號(hào)的轉(zhuǎn)換，所以地址變換的任務(wù)借助于頁表來完成的。
?
如果題目中是用十進(jìn)制數(shù)表示邏輯地址，則：
例題1：有一系統(tǒng)采用頁式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。
?
虛地址 3412
?? ?P＝3412 ％ 2048＝1
??? W＝3412 mod 2048＝1364
?? ?MA=9*2048+1364=19796
?? ?虛地址3412的內(nèi)存地址是19796
?? ?
虛地址 7145
?? ?P＝7145 ％ 2048 ＝3
?? ?W＝7145 mod 2048 ＝1001
?? ?MA=5*2048+1001=11241
?? ?虛地址7145的內(nèi)存地址是：11241
4、快表
因?yàn)轫摫硎谴娣旁趦?nèi)存中的，CPU要存取一個(gè)數(shù)據(jù)，需訪問主存兩次。
第一次：訪內(nèi)存中的頁表，找到該頁的的物理塊號(hào)，將此塊號(hào)與頁內(nèi)地址拼結(jié)形成物理地址；
第二次：真正訪問該物理地址，存取其中的內(nèi)容。
這樣就把程序的執(zhí)行速度降低一倍。
為了提高存取速度，在地址變換機(jī)構(gòu)中增設(shè)一組寄存器，用來存放訪問的那些頁表。
快表是一種訪存速度比內(nèi)存快很多的高速緩沖器。
把存放在高速緩沖寄存器中的頁表叫快表，這個(gè)高速緩沖寄存器又叫聯(lián)想存貯器（TLB）。與此對(duì)應(yīng)，內(nèi)存中的頁表稱為慢表。
當(dāng)進(jìn)程訪問一頁時(shí)，系統(tǒng)將頁號(hào)與快表中的所有項(xiàng)進(jìn)行并行比較。若訪問的頁在快表中，即可立即進(jìn)行地址轉(zhuǎn)換。
當(dāng)被訪問的頁不在快表中時(shí)，去內(nèi)存中查詢頁表，同時(shí)將頁表找到的內(nèi)存塊號(hào)與虛頁號(hào)填入快表中
例題2：
快表命中率98%，訪問時(shí)間是10ns，內(nèi)存訪問時(shí)間是100ns，平均訪問時(shí)間？
平均訪問時(shí)間=98%*(10+100)+（1-98%）*（10+100+100）
若快表命中
聯(lián)想寄存器檢索時(shí)間：10ns
訪問內(nèi)存1次取數(shù)據(jù)時(shí)間：100ns
取數(shù)據(jù)總時(shí)間：110ns
若快表中未命中
聯(lián)想寄存器檢索時(shí)間：10ns
訪問內(nèi)存1次檢索頁表時(shí)間：100ns
訪問內(nèi)存1次取數(shù)據(jù)時(shí)間：100ns
取數(shù)據(jù)總時(shí)間：210ns
?
4、兩級(jí)和多級(jí)頁表
現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。可采用兩個(gè)方法來解決這一問題：
① 采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：
② 只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。
?
?
二級(jí)頁表如何實(shí)現(xiàn)地址變換？
?
?
5、頁的分配與回收
用一張“位示圖”構(gòu)成主存分配表。位示圖的每一位與一個(gè)主存塊對(duì)應(yīng)，其值為0，表示對(duì)應(yīng)的主存塊空閑，其值為1，表示對(duì)應(yīng)的主存塊已分配。
位示圖優(yōu)點(diǎn)是占用內(nèi)存空間小，可常駐內(nèi)存，加快分配進(jìn)程，但缺點(diǎn)是不夠直觀。
?
內(nèi)存分配過程：
計(jì)算一個(gè)作業(yè)所需要的總塊數(shù)N
查位示圖，看看是否還有N個(gè)空閑塊
如果有足夠的空閑塊，則頁表長(zhǎng)度設(shè)為N，可填入PCB中；申請(qǐng)頁表區(qū)，把頁表始址填入PCB
依次分配N個(gè)空閑塊，將塊號(hào)和頁號(hào)填入頁表
修改位示圖
6、存在的問題
為每個(gè)進(jìn)程配置一張頁表，進(jìn)程邏輯空間非常大，帶來的問題？
可以引入Inverted page tables(反置頁表)
反置頁表 – 按物理塊號(hào)排序
?IBM RT; HP Spectrum…
反置頁表很大，使用Hash表加快檢索
所有在內(nèi)存中的并發(fā)進(jìn)程只有一張頁表
除了Hash表，聯(lián)想寄存器也被用來存放最近使用過的頁表項(xiàng)
?
7、分頁存儲(chǔ)管理方案的評(píng)價(jià)
優(yōu)點(diǎn)：
??? 較好地解決了碎片問題
??? 打破了存儲(chǔ)分配的連續(xù)性要求
??? 提高了主存的利用率
缺點(diǎn)：
頁內(nèi)碎片
動(dòng)態(tài)地址變換、方案實(shí)施需耗用額外的系統(tǒng)資源
存儲(chǔ)擴(kuò)充問題沒有解決——作業(yè)大小受到限制，可用塊數(shù)小于作業(yè)需求時(shí)需等待
二、虛擬存儲(chǔ)器(Virtual Memory)
1、局部性原理(principle of locality)
指程序在執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。還可以表現(xiàn)為：
時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較短時(shí)期內(nèi)；
空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。
局部性原理的具體體現(xiàn)：
程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令。
過程調(diào)用的嵌套深度一般不超過5，因此執(zhí)行的范圍不超過這組嵌套的過程。
程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。
程序中存在相當(dāng)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。
2、引入虛擬存儲(chǔ)技術(shù)的好處
大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；
大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory)
并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；
易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時(shí)的程序結(jié)構(gòu)
3、虛擬存儲(chǔ)技術(shù)的特征
不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動(dòng)態(tài)鏈接庫占用的空間）
部分交換：與交換技術(shù)相比較，虛擬存儲(chǔ)的調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行的；
大空間：通過物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間
4、虛擬存儲(chǔ)技術(shù)的種類
虛擬頁式
虛擬段式
虛擬段頁式
三、虛擬頁式(virtual paging)存儲(chǔ)管理
1、基本原理
系統(tǒng)自動(dòng)地將作業(yè)的地址空間分頁，將系統(tǒng)的主存空間分塊，頁與塊等大小，在作業(yè)運(yùn)行前，只把初始需要的一部分頁面裝入內(nèi)存塊里，運(yùn)行中需要訪問自己地址空間中的但當(dāng)前不在內(nèi)存的頁面時(shí)產(chǎn)生缺頁中斷，由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存，若此時(shí)內(nèi)存中沒有空閑物理塊安置請(qǐng)求調(diào)入的新頁面，則系統(tǒng)按預(yù)定的置換策略自動(dòng)選擇一個(gè)或一些在內(nèi)存的頁面，把它們換出到外存。
虛擬頁式存儲(chǔ)管理實(shí)際是實(shí)分頁技術(shù)與虛擬存儲(chǔ)技術(shù)相結(jié)合的產(chǎn)物，其分頁思想與實(shí)分頁是一樣的。
這里的請(qǐng)求調(diào)入和置換功能都是比實(shí)分頁存儲(chǔ)管理增加的內(nèi)容，是實(shí)現(xiàn)虛擬存儲(chǔ)的主要功能。
為實(shí)現(xiàn)虛擬頁式存儲(chǔ)管理:
需要置換技術(shù)、請(qǐng)求裝入技術(shù)和大硬盤支持，另外：
頁表表目需要增加外存塊號(hào)、狀態(tài)位、訪問位或訪問字段、修改位、存取控制字段等。
外存塊號(hào)指出該頁在外存的地址，供調(diào)入該頁時(shí)用；
狀態(tài)位指示該頁是否在內(nèi)存；
訪問位或訪問字段則是該頁被訪問過的標(biāo)志或被訪問過的次數(shù)；
修改位表示該頁是否被修改過；
存取控制字段則是用來限制頁面被安全共享的。
作業(yè)1在請(qǐng)求分頁系統(tǒng)中的存儲(chǔ)映像
?
當(dāng)執(zhí)行 “mov r1，[2120］”時(shí)
CPU產(chǎn)生的虛地址為2120
分頁機(jī)構(gòu)得 p=2，w=72（每頁1K）
查頁表。該頁中斷位i=1，發(fā)生缺頁中斷?
?
如主存中有空白塊，直接調(diào)入
如主存中無空白塊，則需淘汰該作業(yè)在主存中的一頁
?
2、主存頁面分配策略
在虛擬頁式存儲(chǔ)管理中，內(nèi)存分配似實(shí)分頁方式，但還必須考慮解決下面兩個(gè)問題：
（1）是否對(duì)各進(jìn)程采用平均分配策略？
（2）發(fā)生缺頁中斷時(shí)，如何為所缺的頁面分配內(nèi)存？
對(duì)問題(2)有一下幾種做法：
a、平均分配。
b、按進(jìn)程長(zhǎng)度比例分配。
c、按進(jìn)程優(yōu)先級(jí)分配。
d、按進(jìn)程長(zhǎng)度和優(yōu)先級(jí)別分配。
對(duì)問題(2)主要有一下兩種做法：
a、固定分配局部置換。
b、可變分配全局置換。
3、頁面調(diào)入策略
（1）請(qǐng)求調(diào)入
當(dāng)發(fā)生頁面故障時(shí)進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問不在內(nèi)存的頁面引發(fā)缺頁中斷時(shí)，由系統(tǒng)根據(jù)這種訪問請(qǐng)求把所缺頁面裝入內(nèi)存。
優(yōu)點(diǎn)：由請(qǐng)求調(diào)入策略裝入的頁一定會(huì)被訪問，再加之比較容易實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多采用此策略。
缺點(diǎn)：每次僅調(diào)入一頁，增加了磁盤I/O的啟動(dòng)頻率。
（ 2）預(yù)調(diào)入
=>也稱先行調(diào)度，即一頁面被訪問前就已經(jīng)預(yù)先置入內(nèi)存，以減少今后的缺頁率。
=>主要適于進(jìn)程的許多頁存放在外存的連續(xù)區(qū)域中的情況。有的系統(tǒng)結(jié)合請(qǐng)求調(diào)入使用，即每次缺頁時(shí)裝入多個(gè)頁面。
優(yōu)點(diǎn)：提高調(diào)頁的I/O效率。
缺點(diǎn)：基于預(yù)測(cè)，若調(diào)入的頁在以后很少被訪問，則效率低。常用于程序裝入時(shí)的調(diào)頁。
?
調(diào)入頁面的來源：
通常對(duì)外存交換區(qū)的I/O效率比文件區(qū)的高。
進(jìn)程裝入時(shí)，將其全部頁面復(fù)制到交換區(qū)，以后總是從交換區(qū)調(diào)入。執(zhí)行時(shí)調(diào)入速度快，要求交換區(qū)空間較大。
凡是未被修改的頁面，都直接從文件區(qū)讀入，而被置換時(shí)不需調(diào)出；已被修改的頁面，被置換時(shí)需調(diào)出到交換區(qū)，以后從交換區(qū)調(diào)入。
存儲(chǔ)分配的安全性考慮:
把一個(gè)頁面分配給進(jìn)程之前，先要清除頁面中的數(shù)據(jù)（如全部填充為0），以免該進(jìn)程讀取前一進(jìn)程遺留在頁面中的數(shù)據(jù)；
?
4、頁面調(diào)度算法
由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存，若此時(shí)內(nèi)存中沒有空閑物理塊安置請(qǐng)求調(diào)入的新頁面，則系統(tǒng)按預(yù)定的策略自動(dòng)選擇一個(gè)（請(qǐng)求調(diào)入策略）或一些（預(yù)調(diào)入策略）在內(nèi)存的頁面，把它們換出到外存。
a、什么是淘汰策略（置換策略）？
?用來選擇淘汰哪一頁的規(guī)則就叫做置換策略，或稱淘汰算法。如何決定淘汰哪一頁？根據(jù)頁面在系統(tǒng)中的表現(xiàn)（如：使用的頻繁程度、進(jìn)入系統(tǒng)時(shí)間的長(zhǎng)短）
b、顛簸
顛簸(thrashing)，又稱為“抖動(dòng)”。
簡(jiǎn)單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的頻繁頁面置換現(xiàn)像稱為“抖動(dòng)”。
現(xiàn)象？淘汰的頁面恰好是不久又要訪問的頁面。
?
（1）最佳淘汰算法——OPT(Optimal)
這是Belady貝萊迪于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過最長(zhǎng)的時(shí)間后才會(huì)被訪問的頁面。
顯然，采用這種算法會(huì)保證最低的缺頁率，但它是無法實(shí)現(xiàn)的，因?yàn)樗仨氈理撁妗皩怼钡脑L問情況。不過，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個(gè)標(biāo)準(zhǔn)。
假定系統(tǒng)為某個(gè)進(jìn)程分配了三個(gè)物理塊，進(jìn)程的訪問順序?yàn)?，0，1，2，0，3，0，4，2，3，0，3，2，1，2
采用OPT淘汰算法：
?
（2）先進(jìn)先出淘汰算法——FIFO
這是最早出現(xiàn)的淘汰算法。
總是淘汰最先進(jìn)入內(nèi)存的頁面。它實(shí)現(xiàn)簡(jiǎn)單，只需把進(jìn)程中已調(diào)入內(nèi)存的頁面，按先后次序鏈成一個(gè)隊(duì)列，并設(shè)置一個(gè)所謂的替換指針，使它總是指向內(nèi)存中最老的頁面。
缺點(diǎn)：效率不高，因?yàn)樗c進(jìn)程實(shí)際的運(yùn)行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁面或者循環(huán)體所在頁面都可能被它選為淘汰對(duì)象。出現(xiàn)bleady現(xiàn)象。
頁面進(jìn)入主存的先后次序：
2->4->5->1
?
當(dāng)要調(diào)入第6頁時(shí)：
置換第2頁
將第2頁改為6
替換指針指向第4頁4->5->1->6
Belady現(xiàn)象：采用FIFO算法時(shí)，如果對(duì)一個(gè)進(jìn)程未分配它所要求的全部頁面，有時(shí)就會(huì)出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異常現(xiàn)象。
Belady現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問M個(gè)頁，OS分配N個(gè)內(nèi)存頁面給進(jìn)程P；對(duì)一個(gè)訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S, N)時(shí)而增大，時(shí)而減小。
Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特征是非常不一致的，即被置換的頁面通常并不是進(jìn)程不會(huì)訪問的。
采用FIFO淘汰算法：
?
?
（3） 最近最久未使用算法(LRU, Least Recently Used）
根據(jù)頁面調(diào)入內(nèi)存后的使用情況，選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。
OPT算法使用頁面將要被訪問的時(shí)間，LRU算法使用頁面最后一次被訪問的時(shí)間。二者唯一的差別是：OPT是向前看的，而LRU是向后看的。
下面給出LRU的實(shí)現(xiàn)算法：
a、計(jì)時(shí)法：對(duì)于每一頁面增設(shè)一個(gè)訪問時(shí)間計(jì)時(shí)器，每當(dāng)一個(gè)頁面被訪問時(shí)，當(dāng)時(shí)的絕對(duì)時(shí)鐘內(nèi)容被拷貝到對(duì)應(yīng)的訪問時(shí)間計(jì)時(shí)器中，這樣系統(tǒng)記錄了內(nèi)存中所有頁面最后一次被訪問的時(shí)間。淘汰時(shí)，選取訪問時(shí)間計(jì)時(shí)器的值最小的頁面。
b、堆棧法：每當(dāng)進(jìn)程訪問某頁面時(shí)，便將該頁面的頁號(hào)從棧中移出，將它壓入棧頂。棧頂始終是最新被訪問的頁面的編號(hào)。棧底則是最近最久未被使用的頁面的頁面號(hào)。
c、多位寄存器法
為每頁設(shè)置一個(gè)R位的寄存器
每次訪問一頁時(shí)，將該頁所對(duì)應(yīng)的寄存器最左位置1
每隔時(shí)間間隔T，所有寄存器右移一位。
選擇R值最小的頁淘汰。
例如，r寄存器共有四位，頁面P0、P1、P2在T1、T2、T3時(shí)刻的r寄存器內(nèi)容如下：
???? 頁面????????????????????????????? 時(shí)刻
???????????????????????????? T1??????????? T2?????????? T3???? ?
???? P0???????????????? 1000??????? 0100?? ???? 1010
???? P1???????????????? 1000??????? 1100??????? 0110
???? P2???????????????? 0000?????? 1000???????? 0100
給某作業(yè)分配了三塊主存，該作業(yè)依次訪問的頁號(hào)為：4，3，0，4，1，1，2，3，2。當(dāng)訪問這些頁時(shí)，頁面淘汰序列變化情況如下
?
LRU的開銷是很大的，必須有硬件的支持，完全由軟件實(shí)現(xiàn)其速度至少會(huì)減少10倍，因此LRU近似算法更實(shí)用些
（4）二次機(jī)會(huì)淘汰算法——SC(Second Chance)淘汰算法
這是一種LRU的近似算法，是通過對(duì)FIFO算法進(jìn)行簡(jiǎn)單改造，結(jié)合頁表中的訪問位而得來一種淘汰算法。
該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻?#xff0c;如果它的訪問位為0，則選擇該頁淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過程，直至遇到新鏈?zhǔn)醉撌且粋€(gè)訪問位為0的較早進(jìn)入內(nèi)存的頁為止，把它選為被淘汰的頁。
為每一個(gè)存儲(chǔ)塊（存儲(chǔ)分塊表）或頁面（頁表）設(shè)立一個(gè)引用位。
當(dāng)訪問某頁時(shí)，就將該頁引用位置1
頁面管理軟件周期性地（設(shè)周期為T）將所有引用位重新置0
在T內(nèi)，被訪問過的頁面引用位為1，否則為0
選擇引用位為0的頁面淘汰。
（5）時(shí)鐘(Clock)淘汰算法
二次機(jī)會(huì)淘汰算法缺點(diǎn)：就是需要把訪問位為1的處于鏈?zhǔn)椎捻撘浦伶溛?#xff0c;這需要一定的開銷。
改進(jìn)的方法：就是把進(jìn)程所訪問的頁面鏈成一個(gè)環(huán)形鏈表，再設(shè)一個(gè)指針指向最老的頁面，于是形成了一種簡(jiǎn)單實(shí)用的LRU近似算法——時(shí)鐘淘汰算法。
該算法首先檢測(cè)指針?biāo)傅捻撁?#xff0c;如果它的訪問位為0，則淘汰該頁，新裝入的頁插入到此位置，然后指針前進(jìn)一個(gè)位置；如果它的訪問位為1，則清除為0，并將指針前進(jìn)一個(gè)位置，繼續(xù)檢查訪問位。重復(fù)此過程，直到找到訪問位為0的頁面為止。
訪問頁號(hào)727
引發(fā)缺頁
?
?
?
?
?
（6）最近未用淘汰算法——NRU(Not Used Recently)淘汰算法
它把FIFO算法的思想與頁面的訪問位和修改位結(jié)合起來確定一個(gè)接近LRU算法的淘汰對(duì)象。
該算法每次都盡量選擇最近最久未被寫過的頁面淘汰，這種干凈的頁面可以不被寫回到磁盤。在實(shí)現(xiàn)時(shí)，為每一個(gè)頁面設(shè)置初始值0的訪問位和修改位。當(dāng)對(duì)某頁面執(zhí)行寫操作時(shí)，其修改位和訪問位均由硬件置成1；當(dāng)對(duì)某頁面執(zhí)行讀操作時(shí)，只有其訪問位被硬件置成1。系統(tǒng)每隔固定時(shí)間將所有訪問位都清0。
按照下列次序選擇被淘汰的頁面：
①訪問位＝０，修改位＝０；直接淘汰；
②訪問位＝０，修改位＝１；寫回外存后淘汰；
③訪問位＝１，修改位＝０；直接淘汰；
④訪問位＝１，修改位＝１；寫回外存后淘汰；
頁面請(qǐng)求序列為：2，3，2，1，5，2，4，5，3，2，5，2
內(nèi)存分配3塊
用OPT、LRU、FIFO、Clock算法寫出頁面置換過程
時(shí)鐘clock算法中的箭頭是當(dāng)前指針的位置！
5、影響缺頁中斷率的因素 ?
（1）頁面調(diào)度算法不合理
抖動(dòng)又叫顛簸，是指一段時(shí)間里，頁面在內(nèi)存與外存之間頻繁地調(diào)度或換入換出，以至于系統(tǒng)用于調(diào)度頁面所需要的時(shí)間比進(jìn)程實(shí)際運(yùn)行所占用的時(shí)間還要多。
顯然，抖動(dòng)是由于缺頁中斷率很高而引起的一種壞現(xiàn)象，它將嚴(yán)重影響系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰。
（2）分配給作業(yè)的內(nèi)存塊數(shù)太少
作業(yè)的缺頁中斷率與作業(yè)所占內(nèi)存塊數(shù)成反比。分配給作業(yè)的內(nèi)存塊數(shù)太少是導(dǎo)致抖動(dòng)現(xiàn)象發(fā)生的最主要的原因，實(shí)驗(yàn)分析表明：對(duì)所有的程序來說，要使其有效地工作，它在內(nèi)存中的頁面數(shù)不應(yīng)少于它的總頁面數(shù)的一半。
（3）頁面大小的選擇不合理
雖然缺頁中斷率與頁面尺寸成反比，但頁面尺寸卻不能一味地求大，它一般在0.5KB~4KB之間，是個(gè)實(shí)驗(yàn)統(tǒng)計(jì)值。因?yàn)轫撁娲髸r(shí)，頁表較小，占空間少，查表速度快，缺頁中斷次數(shù)少，但頁面調(diào)度時(shí)間長(zhǎng)，頁內(nèi)碎片較大。頁面小時(shí)，恰恰相反。
（4）用戶程序編制的方法不合適
作業(yè)的缺頁中斷率與程序的局部化（包括時(shí)間局部化和空間局部化）程度成反比。用戶程序編制的方法不合適可能導(dǎo)致程序運(yùn)行的時(shí)空復(fù)雜度高，缺頁次數(shù)多。
總結(jié)
- 上一篇： 教你搞定补码不恢复余数除法中够减和商的关
- 下一篇： 利用邻接表完成图的BFS和DFS