Ⅰ 操作系統題：頁面置換演算法 OPT FIFO LRU
fifo就是先進先出，可以想像成隊列
lru是最久未使用，當或廳需要替換頁面的時候，向前面看，最久衫老隱沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最含清遲出現的。
不懂再問。。
Ⅱ 試說明改進形clock頁面置換演算法的基本原理
這很簡單啊，要打字太多了。不過網上這類演算法舉例很少，就看你怎麼理解了。
改良後的Clock演算法
考慮到如果某一調入內存的頁沒有被修改過，則不必將它拷回到磁碟。於是在改進的Clock增加了弊漏旅一個M位， M=0 表示該頁未被修改過。這樣我們選擇頁面換出時，既要最近未訪問過的頁面，又要未被修改過的頁面。其執行過程分一下三步：
第一步：從開始位置循環掃描隊列，尋找A=0、M=O的第一類面，找到立搜廳即置換。另外，第一次掃描期租凳間不改變訪問位A。
第二步：如果第一步失敗，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，找到後立即置換，並將所有掃描過的A都置0。
第三步：如果第二步也失敗，則返回指針開始位置，然後重復第一步，必要時再重復第二步，此時必能找到淘汰頁。
Ⅲ 內存擴充之虛擬存儲技術
傳統存儲管理
特徵
時間局部性：如果執行了程序中的某條指令，那麼不久後這條指令很有可能再次執行；如果某個數據被訪問過，不久之後該數據很可能再次被訪問（因為程序中存在大量循環）
空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元很有可能被訪問（因為很多數據在內存中是連續存放的，並且程序的指令也是順序地在內存中存放的
寄存器
高速緩存
內存
外存（如磁碟、磁帶等）
越往上容量越小，訪問速度越快，成本越高
越往下容量越大，訪問速度越慢，成本越低
高速緩存技術的思想：將近期會頻繁訪問到的數據放到更高速的存儲器中，暫時用不到的數據放在更低速存儲器中
快表機構就是將近期常訪問的頁表項副本放到更高速的cache中
基於局部性原理，在程序裝入時，可以將程序中很快就會用到的部分裝入內存，暫時用不到的部分留在外存，就可以讓程序開始執行
在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然後繼續執行程序
若內存空間不夠，由操作系統將內存中暫時用不到的信息換出到外存
因此，在操作系統的管理下，在用戶看來似乎有一個比實際內存大得多的內存，這就是虛擬內存
操作系統虛擬性的一個體現，實際的物理內存大小沒有變，只是在邏輯上進行了擴充
虛擬內存的最大容量是由計算機的地址結構（CPU定址范圍）確定的
虛擬內存的實際容量 = min(內存外存容量之和，CPU定址范圍)
虛擬內存有以下三個主要特徵
虛擬內存技術，允許一個作業多次調入內存。如果採用連續分配方式，會不方便實現。因此，虛擬內存的實現需要建立在離散分配的內存管理方式基礎上
傳統的非連續分配存儲管理
基本分頁存儲管理
基本分段存儲管理
基本段頁式存儲管理
虛擬內存的實現
請求分頁存儲管理
請求分段存儲管理
請求段頁式存儲管理
主要區別：在程序執行過程中，當所訪問的信息不在內存時，由操作系統負責將所需信息從外存調入內存，然後繼續執行程序。若內存空間不夠，由操作系統負責將內存中暫時用不到的信息換出到外存
操作系統要提供請求調頁/段功能、頁面/段置換功能
請求分頁存儲管理和基本分頁存儲管理的主要區別
頁表機制
頁表項：內存塊號、狀態位、訪問欄位、修改位、外存地址，頁號時隱含的
內存塊號是頁面在內存中對應的頁框號，如果狀態位為0，則內存塊號為無
狀態位表示是否已被調入內存
訪問欄位記錄最近被訪問過幾次，或者上次訪問時間，由此操作系統能夠提供置換演算法
修改位記錄頁面被調入內存後是否被修改過，如果沒有，就不需要浪費時間寫回外存
外存地址是頁面在外存中的存放位置
缺頁中斷機構
在請求分頁系統中，每當要訪問的頁面不在內存時，便會產生一個缺頁中斷，然後由操作系統的缺頁中斷處理程序處理中斷（內中斷）
此時缺頁的進程阻塞，放入阻塞隊列，調頁完成後再將其喚醒，放回就緒隊列
如果內存中有空閑塊，則為進程分配一個空閑塊，將所缺頁面裝入該塊，並修改頁表中相應的頁表項
如果內存中沒有空閑塊，則由頁面置換演算法選擇一個頁面淘汰，若該頁面在內存期間被修改過，則要將其寫回外存，為修改過的頁面不用寫回外存
一條指令再執行期間可能產生多次缺頁中斷（ A to B）
新增的步驟
頁面的換入、換出需要磁碟IO，會有較大的開銷，因此好的頁面置換演算法應該追求更少的缺頁率
缺頁中斷≠頁面置換
發生缺頁中斷會發生調頁，只有內存塊滿了才發生頁面置換
最佳置換演算法OPT：每次淘汰以後永不使用或最長時間內不再被訪問的頁面
理想化的演算法，很難實現
先進先出演算法FIFO：每次淘汰最先進入內存的頁面
實現：把調入內存的頁面根據調入的先後順序排成隊列，頁面置換時換出隊頭頁面，新調入的頁面排到隊尾
優點：實現簡單
缺點1：belady異常，為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象。只有FIFO會產生belady異常。
缺點2：演算法與進程實際運行時的規律不適應，因為先調入的頁面有可能最經常被訪問，因此演算法性能差
最近最久未使用置換演算法LRU：淘汰最近最久未使用的頁面
實現方法：賦予每個頁面對應的頁表項中，用訪問欄位記錄該頁面自上次被訪問以來所經歷的時間t
優點：性能最接近OPT
缺點：實現困難、開銷大
時鍾置換演算法CLOCK/NRU
簡單NRU：為每一個頁表項設置一個訪問位，再將內存中的頁面都通過連接指針連成一個循環隊列，當某頁被訪問時，訪問位為1，只需檢查頁的訪問位。如果為0，就將該頁換出，否則將其改為0，暫不換出，繼續向後掃描，若第一輪掃描都是1，將這也頁面的訪問位改為0後，進行第二輪掃描，第二輪掃描中一定會有訪問位為0的頁面，將其換出。因此最多經過兩輪掃描
改進NRU：如果淘汰的頁面沒有被修改過，就不需要執行IO操作，只有淘汰的頁面被修改過時，才需要寫回外存。因此，同時考慮最近有無訪問和有無修改，在其他條件相同時，優先淘汰沒有修改過的頁面，避免IO操作
第一輪：找到第一個訪問位和修改位都為0的頁面進行替換，如果沒有找到進行下一輪掃描
第二輪：查找第一個訪問位為0，修改位為1的頁面進行替換，本輪將所有被掃描過的訪問位設置為0，如果沒有進行下一輪掃描
第三輪：查找0，0替換否則下一輪
第四輪：查找0，1替換
最多會進行四輪掃描
駐留集：請求分頁管理中給進程分配的物理塊的集合
在採用了虛擬存儲技術的系統中，駐留集大小一般小於進程的總大小
駐留集太小，導致缺頁頻繁，系統要花大量時間處理缺頁，實際用於進程推進的時間很少
駐留集太大，會導致多道程序並發度下降，資源利用率降低
固定分配：操作系統為每個進程分配一組固定數目的物理塊，在進程運行期間不再改變
可變分配：先為每個進程分配一定數目的物理塊，在進程運行期間，可根據情況作適當的增加或減少
局部置換：發生缺頁時只能選進程自己的物理地址塊進行置換
全局置換：可以將操作系統保留的空閑物理塊分配給缺頁進程，也可以將別的進程持有的物理塊置換到外存，再分配給缺頁進程
不存在固定分配全局置換的策略，因為全局置換意味著一個進程擁有的物理塊數量必然改變
其他三種組合存在
固定分配局部置換：系統為每個進程分配一定數量的物理塊，在整個運行期間都不改變。若進程在運行中發生缺頁，並且需要進行頁面置換，則只能從該進程在內存中的頁面中選出一頁換出，然後再調入需要的頁面
缺點：很難在剛開始就確定應為每個進程分配多少個物理地址塊才算合理（採用這種策略的系統可以根據進程大小、優先順序、或是根據程序員給出的參數來確定為一個進程分配的內存塊數
可變分配全局置換：剛開始會為進程分配一定數量的物理塊。操作系統會保持一個空閑物理塊隊列，當某進程發生缺頁時，從空閑物理塊中取出一塊分給該進程；若無空閑物理塊，則選擇一個未鎖定的頁面換出到外存，再將該物理塊分配給缺頁的進程。採用這種策略時，只要某進程發生缺頁，都將獲得新的物理塊，僅當空閑物理塊用完時，系統才選擇一個未鎖定的頁面調出。被選擇調出的頁面可能是系統中任何一個進程的頁面，因此這個被選中的進程擁有的物理塊會減少，缺頁率會增加
只要缺頁就給該進程分配新的物理塊
可變分配局部置換：剛開始會為每個進程分配一定數量的物理塊，當某進程發生缺頁時，只允許從該進程自己的物理塊中選出一個進行頁面置換。如果進程在運行過程中頻繁缺頁，系統會為該進程多分配幾個物理塊，直至該進程缺頁率趨於適當程度；反之，如果缺頁率太低，就是當減少分配給該進程的內存塊數
要根據發生缺頁的頻率來動態增加或減少進程的物理塊
何時調入頁面
從何處調入頁面
對換區：讀寫速度更快，採用連續分配方式
文件區：讀寫速度更慢，採用離散分配方式
抖動/顛簸現象：剛剛換出的頁面馬上要換入內存，剛剛換入的頁面馬上要換出外存，這種頻繁的頁面調度行為稱為抖動/顛簸
主要原因是進程頻繁訪問的頁面數目高於可用的物理塊數（分配給進程的物理塊不夠）
為進程分配物理塊太少會使進程發生抖動現象，為進程分配的物理塊太多會降低系統的並發度降低某些資源的利用率。因此提出了「工作集」的概念
工作集：在某段時間間隔里，進程實際訪問頁面的集合
駐留集：請求分頁存儲管理中給進程分配的內存塊的集合
駐留集不能小於工作集，否則進程運行過程中將頻繁缺頁
Ⅳ 頁面置換演算法的常見的置換演算法
最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。理由是：最早調入內存的頁，其不再被使用的可能性比剛調入內存的可能性大。建立一個FIFO隊列，收容所有在內存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內存時，就把它插在隊尾上。
這種演算法只是在按線性順序訪問地址空間 時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。
FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。
FIFO演算法和OPT演算法之間的主要差別是，FIFO演算法利用頁面進入內存後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間里最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。
LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間里最久未被使用的頁面。
LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。LRU演算法需要實際硬體的支持。其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法：
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位，並給CPU增加一個邏輯時鍾或計數器。每次存儲訪問，該時鍾都加1。每當訪問一個頁面時，時鍾寄存器的內容就被復制到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要 維護這個頁表中的時間，還要考慮到時鍾值溢出的問題。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。
因實現LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似演算法。
一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。
4）Clock置換演算法（LRU演算法的近似實現）
5）最少使用（LFU）置換演算法
在採用最少使用置換演算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪 問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。
LFU置換演算法的頁面訪問圖與LRU置換演算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。
6）工作集演算法
7）工作集時鍾演算法
8）老化演算法（非常類似LRU的有效演算法）
9）NRU(最近未使用）演算法
10）第二次機會演算法
第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是 0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。
第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。
Ⅳ 簡單時鍾置換演算法（NLU）當不發生頁面置換也就是命中時，循環隊列中的掃描指針跟著命中的頁移動不
在地址映射過程中，若在頁面中發現所要訪問的頁面不在內存中，則產生缺頁中斷。當發生缺頁中斷時，如果操作系統內存中沒有空閑頁面，則操作系統必須在內存選擇一模旦個頁面將其移出內存，以便為即將調入的頁面讓出空間。而用來選鉛碼氏擇淘汰哪一頁的規則叫做頁面置換演算法。槐散
Ⅵ C++編程，clock置換演算法
#include<iostream>
#include<stdlib.h>
#include<time.h>
#define N 20 //虛擬內存尺寸
using namespace std;
int P;
int const blockCount=3 ;//內存中的物理塊數
int count = 0;
int block[blockCount];
int const PageCount=15;//總的頁面數
int Page[PageCount];
int state[blockCount];//clock置換演算法中，內存中的每個頁面號對應的狀態
int state2[blockCount][2];// 二維數組，第一行第一列為訪問位，第一行的第二列為修改位
double lost= 0.0;
void generate_list(int *list,int e,int m,int t)
{
int i,j=0,q=P,r;
srand((unsigned)time(NULL));
while(j<e)
{
for(i=j;i<j+m;i++)
{
if(i==e)
break;
list[i]=(q+rand()%e)%N; //保證在虛擬內存的頁號內
}
j=i;
r=rand()%100;
if(r<t)
q=rand()%N;
else
q=(q+1)%N;
}
}
//隨機生產是否被修改的情況，prop(0……100),prop/100的概率為被修改
void generate_modify(int *mo,int e,int prop)
{
int i,t;
for(i=0;i<e;i++)
{
t=rand()%100;
if(t>prop)
mo[i]=0;
else
mo[i]=1;
}
}
//檢測頁號是否在內存中
bool inblock(int num)
{
for(int i=0; i<blockCount;i++)
{
if(block[i] == Page[num])
{
state[i] = 1;
return true;
}
}
return false;
}
//判斷頁面是否已經被修改
bool change()
{
if((rand()%2+1) == 1 )
{
printf("該頁並余蠢面被修改!\n");
return true;
}
else
return false;
}
//用於改進型clock置換演算法，檢測頁號是否在內存中並把訪問位和修改位置毀耐1
bool inblock2(int num)
{
for(int i=0;i<blockCount;i++){
if(block[i] == Page[num]){
if(change()){
state2[i][0] = 1;
state2[i][1] = 1;
}
else{
state2[i][0] = 1;
}
return true;
}
}
return false;
}
//用於改進型clock置換演算法，判斷內存中第幾個需要被置換
int whichpage(){
int j;
for(j=0;j<blockCount;j++)
{
if(state2[j][0] == 0&&state2[j][1] == 0)
{
return j;
}
}
for(j=0;j<blockCount;j++ )
{
if(state2[j][0] == 0&&state2[j][1] == 1)
{
return j;
}
state2[j][0] = 0 ;
}
for(j=0;j<blockCount;j++ )
{
state2[j][0] =0 ;
}
return whichpage();
}
//簡單Clock置換演算法
void CLOCK(int num)
{
int j;
if(inblock(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\絕陪n",i,block [i]);
}
else
if(count == blockCount)
{
//lost++;
for(j=0;j<blockCount; )
{
if(state[j] == 0)
{
break;
}
else{
state[j] = 0;
}
j++;
j = j%3;
}
block[j] = Page[num];
state[j] = 1;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
}
//改進型clock置換演算法
void LCLOCK(int num)
{
int j;
if(inblock2(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else
if(count == blockCount)
{
//lost++;
j = whichpage();
block[j] = Page[num];
state2[j][0] = 1;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理塊%d#中內容:%d\n",i,block[i]);
}
}
int main()
{
int a[N];
int mo[N];
int A=10;
int e,m,prop,t,j;
printf("頁面走向為：");
generate_list(a, e,m,t);
generate_modify(mo,e,prop);
for(int i = 0;i<PageCount;i++)
{
Page[i] =rand()%9 + 1;
printf("%d ",Page[i]);
}
char ch ;
printf("\n");
printf("\t\t1 Clock置換演算法\n");
printf("\t\t2 改進型Clock置換演算法\n");
printf("\t\t3 退出!\n\n");
printf("請輸入演算法序號:\t\n");
while(1){
scanf("%c",&ch);
switch(ch){
case '1':{
lost=0;
count=0;
for(int m=0;m<blockCount;m++)
{
state[m] = 0;
}
for(int j=0;j<blockCount;j++)
{
block[j]=0;
}
for(int i=0;i<PageCount;i++)
{
printf("讀入Page[%d]\n",i);
CLOCK(i);
}
printf("頁面訪問次數: %d\n缺頁次數: %0.lf\n",PageCount,PageCount-lost);
printf("缺頁率為:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n請輸入演算法序號:\t");
}break;
case '2':{
lost = 0;
count = 0;
for(int m = 0; m < blockCount; m++)
{
for(int n = 0; n < 2;n++)
state2[m][n] = 0;
}
for(int j = 0; j < blockCount; j++)
{
block[j] = 0;
}
for(int i = 0; i < PageCount; i++)
{
printf("讀入Page[%d]\n",i);
LCLOCK(i);
}
printf("頁面訪問次數: %d\n缺頁次數: %0.lf\n",PageCount,PageCount-lost);
printf("缺頁率為:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n請輸入演算法序號:\t");
}break;
case '3':{
exit(0);
}
}
}
return 0;
}
Ⅶ 操作系統CLOCK置換演算法的題目，急求解！！
因為一個目錄文件最多可以由4個磁碟塊組成，讀目錄和下級目錄的時候，在最好的情況下，總能在第一個磁碟塊上就能找到所需的下級目錄信息，所以ADKQ四個目錄讀四次就可以了，此後差頌是讀文件，理想情況下所需頁面可以通過前10個索引直接找到，此時只需再讀一次就虛核鄭能讀到所需頁了，結果最少共用5次
最壞情況下，每個目錄都存放在4個磁碟塊的最後一個上，因此每個目錄都得讀四次，一共4*4=16次，而找到文件後，所需頁面又得通過2級索引去找，這樣一來2級索引表讀一次，1級索引表又讀一次，氏配頁面本身內容再讀一次，又需2+1=3次，所以最壞情況就是16+3=19次
Ⅷ 頁面置換演算法
上文說到，請求分頁管理方式中，當需要調入頁面到內存中，但此時內存已滿，就需要從內存中按照一定的置換演算法決定將哪個頁面取出將內存給調入的頁面。本文將介紹幾種頁面置換算方法。
本文內容
演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此演算法依次執行，最後的結果如下
結果圖
註：缺頁時未必發生頁面置換，若還有可用的空閑內存空間就不用進行頁面置換。
最佳置換演算法可以保證最低的缺頁率，但是實際上，只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此， 最佳置換演算法是無法實現的 。
演算法思想：每次選擇 淘汰的頁面是最早進入內存的頁面。
該演算法很簡單，每次淘汰最在內存中待時間最久的各個，下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
分配三個內存塊的情況：
分配四個內存塊的情況：
當為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象稱為 貝萊迪（Belay）異常 。
只有FIFO演算法會產生Belay異常。 另外，FIFO演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應。因為先進入的頁面也有可能最經常被訪問。因此， 演算法性能差。
演算法思想： 每次淘汰的頁面是最近最久未使用的頁面。
實現方法：賦予每個頁面對應的頁表項中，用 訪問欄位記錄該頁面純虧自上次被訪問以來所經歷的時間t。 當需要淘汰一個頁面時，選擇現有頁面中t最大的頁面，即最近最久未使用。
舉例說明，加入某系統為某進程分配了四個內存塊，並考慮到有以下頁面號引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
這里先直接給出答案
結果圖
最佳置換演算法那性能最好，但無法實現。先進先出置換演算法實現簡單，但是演算法性能差。最近最久未使用置換演算法性能好，是最接近OPT演算法性能的，但是實現起來需要專門的硬體支持，演算法開銷大。 時鍾置換演算法 是一種 性能和開銷均春褲配平衡 的演算法。又稱 CLOCK演算法 ，或 最近未用演算法 （ NRU ，Not Recently Used）
簡單CLOCK演算法 演算法思想：為每個頁面設置一個 訪問位 ，再將內存中的頁面都通過 鏈接指針鏈接成一個循環隊列 。當某個頁被訪問時，其訪問位置1.當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，暫不換出，將訪問位改為0，繼續檢查下一個頁面，若第一輪掃描中所有的頁面都是1，則將這些頁面的訪問位一次置為0後，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK演算法選擇一個扒指淘汰頁面最多會經過 兩輪掃描 ）。
這個演算法指針在掃描的過程就像時鍾一樣轉圈，才被稱為時鍾置換演算法。
簡單的時鍾置換演算法僅考慮到了一個頁面最近是否被訪問過。事實上，如果淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。 只有淘汰的頁面被修改過時，才需要寫回外存。
因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統還需要考慮頁面有沒有被修改過。
改進型時鍾置換演算法的 演算法思想 ： 在其他在條件相同時，應該優先淘汰沒有被修改過的頁面， 從而來避免I/O操作。
為了方便討論，用（訪問位，修改位）的形式表示各頁面的狀態。如（1,1）表示一個頁面近期被訪問過，且被修改過。
演算法規則 ：將所有可能被置換的頁面排成一個循環隊列
由於第二輪已將所有的頁的訪問位都設為0，因此第三輪、第四輪掃描一定會選中一個頁，因此 改進型CLOCK置換演算法最多會進行四輪掃描。
假設系統為進程分配了5個內存塊，某時刻，各個頁的狀態如下圖
如果此時有新的頁要進入內存，開始第一輪掃描就找到了要替換的頁，即最下面的狀態為（0,0）的頁。
某一時刻頁面狀態如下
如果此時有新的頁要進入內存，開始第一輪掃描就發現沒有狀態為（0，0）的頁，第一輪掃描後不修改任何標志位。所以各個頁狀態和上圖一樣。
然後開始第二輪掃描，嘗試找到狀態為（0,1）的頁，並將掃描過後的頁的訪問位設為0，第二輪掃描找到了要替換的頁。
某一時刻頁面狀態如下
第一輪掃描沒有找到狀態為（0,0）的頁，且第一輪掃描不修改任何標志位，所以第一輪掃描後狀態和上圖一致。
然後開始第二輪掃描，嘗試找狀態為（0,1）的頁，也沒有找到，第二輪掃描需要將訪問位設為1，第二輪掃描後，狀態為下圖
某一時刻頁面狀態如下
具體的掃描過程和上面相同，這里只給出最後的結果，如下圖
所以，改進型的CLOCK置換演算法最多需要四輪掃描確定要置換的頁。從上面的分析可以看出，改進型的CLOCK置換演算法
(1) 第一優先順序淘汰的是 最近沒有訪問且沒有修改 的頁面。
(2) 第二優先順序淘汰的是 最近沒有訪問但修改 的頁面。
(3) 第三優先順序淘汰的是 最近訪問但沒有修改 的頁面。
(4) 第四優先順序淘汰的是 最近訪問且修改 的頁面。
Ⅸ 12、存儲模型2（操作系統筆記）
我們將虛擬存儲技術和頁式存儲管理方案結合起來得到了虛擬頁式存儲管理系統。具體有兩種方式，一是請求調頁，二是預先調頁。以 cpu 時間和磁碟換取昂貴內存空間，這是操作系統中的資源轉換技術。
通常，頁表項是硬體設計的。
為什麼要鎖定頁面？
又稱頁面淘汰演算法。最佳演算法-->先進先出-->第二次機會-->時鍾演算法-->最近未使用-->最近最少使用-->最不經常使用-->老化演算法-->工作集-->工作集時鍾
在先進先出演算法的基礎上進行該機而來的，此演算法按照先進先出演算法選擇某一頁面，檢查其訪問位 R ，如果為 0 ，則置換該頁；如果為 1 ，則給第二次機會，並將訪問位置零，並將其從鏈頭取下放到鏈尾。
在第二次機會演算法中當給某個頁面第二次機會的時候，將其訪問位置零，然後將其掛到鏈尾，這都是需要開銷的，於是我們改進為時鍾演算法。
選擇最後一次訪問時間距離當前時間最長的一頁並置換，即置換未使用時間最長的一頁。
即 Not frequently Used ，選擇訪問次數最少的頁面置換
例子：
要求：
計算應用 FIFO、LRU、OPT 演算法時的缺頁次數
應用 FIFO、LRU 頁面置換演算法
應用OPT頁面置換演算法
例子：系統給某進程分配 m 個頁框，初始為空頁面訪問順序為
1 2 3 4 1 2 5 1 2 3 4 5 ，採用 FIFO 演算法，計算當 m=3 和 m=4 時的缺頁中斷次數。
結論： m=3 時，缺頁中斷九次； m=4 時，缺頁中斷十次。注意： FIFO 頁面置換演算法會產生異常現象（ Belady 現象），即：當分配給進程的物理頁面數增加時，缺頁次數反而增加。
缺頁越多，系統的性能越差，這稱為顛簸（抖動）：虛存中，頁面在內存與磁碟之間頻繁調度，使得調度頁面所需的時間比進程實際運行的時間還多，這樣導致系統效率急劇下降，這種現象稱為顛簸或抖動。
例子：
分配了一個頁框，頁面大小為 128 個整數，矩陣 A(128 x 128) 按行存放。
如果能為進程提供與活躍頁面數相等的物理頁面數，則可減少缺頁中斷次數，這是由 Denning 提出的。