操作系統(tǒng)-內存置換算法(共8頁)

1、精選優(yōu)質文檔-傾情為你奉上存儲管理的頁面置換算法存儲管理的頁面置換算法在考試中常常會考到，操作系統(tǒng)教材中主要介紹了3種常用的頁面置換算法，分別是：先進先出法（FIFO）、最佳置換法（OPT）和最近最少使用置換法（LRU）。大家要理解3種置換算法的含義，然后能熟練地運用在具體的練習中就可以了。為什么要進行頁面置換在請求分頁存儲管理系統(tǒng)中，由于使用了虛擬存儲管理技術，使得所有的進程頁面不是一次性地全部調入內存，而是部分頁面裝入。這就有可能出現(xiàn)下面的情況：要訪問的頁面不在內存，這時系統(tǒng)產生缺頁中斷。操作系統(tǒng)在處理缺頁中斷時，要把所需頁面從外存調入到內存中。如果這時內存中有空閑塊，就可以直接調入該頁面

2、；如果這時內存中沒有空閑塊，就必須先淘汰一個已經在內存中的頁面，騰出空間，再把所需的頁面裝入，即進行頁面置換。有助于理解的關鍵詞有：請求分頁、虛擬存儲、缺頁中斷、頁面置換。先進先出法（FIFO）算法描述：由于認為最早調入內存的頁不再被使用的可能性要大于剛調入內存的頁，因此，先進先出法總是淘汰在內存中停留時間最長的一頁，即先進入內存的頁，先被換出。先進先出法把一個進程所有在內存中的頁按進入內存的次序排隊，淘汰頁面總是在隊首進行。如果一個頁面剛被放入內存，就把它插在隊尾。【例1】教材第4章課后習題?？紤]下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當

3、內存塊數(shù)量分別為3，5時，試問先進先出置換算法（FIFO）的缺頁次數(shù)是多少？（注意，所有內存塊最初都是空的，凡第一次用到的頁面都產生一次缺頁。）解：當內存塊數(shù)量分別為3時，F(xiàn)IFO算法的執(zhí)行過程如下圖所示。打叉的表示發(fā)生了缺頁，共缺頁16次。提示：當FIFO算法執(zhí)行到藍色的4號頁面時，這時內存中有三個頁面，分別是1，2，3。按照FIFO算法，在內存中停留時間最長的頁面被淘汰。三個頁面在內存中的停留時間用綠色區(qū)域標記出來了，可見，1號頁面是停留時間最長的，因此要淘汰1號頁面。當內存塊數(shù)量分別為5時，共缺頁10次。FIFO算法的執(zhí)行過程如下。優(yōu)缺點：先進先出法（FIFO）簡單易于實現(xiàn)，但是性能不好

4、，存在Belady現(xiàn)象。例如對于以下頁面：1，2，3，4，1，2，5，1，2，3，4，5，當內存塊為3時，出現(xiàn)9次缺頁中斷；當內存塊為4時，出現(xiàn)10次缺頁中斷。缺頁率隨著內存塊增加而增加的現(xiàn)象，稱為Belady現(xiàn)象。有興趣的同學可以試一試，看看是不是這樣的。代碼:#include "iostream"using namespace std;#include<vector>#include <deque>/ram 模擬系統(tǒng)為進程分配的3個內存塊deque<int> ram(3);int length=0;/檢測是否在內存中int isCon

5、tain(int findNum)int i;for (i=0;i<ram.size();i+)if (findNum=rami) break;return i;/缺頁中斷 將缺少的頁調入內存 同時將最早進來的頁調出int intServer(int page)if(length!=ram.size() ramlength=page; length+;else ram.pop_front(); ram.push_back(page);return 0;/顯示3個內存塊中存放的頁面號void display() int i;cout<<"內存塊中存放的頁面號:&quo

6、t;for (i=0;i<ram.size();i+)printf("%2d ",rami);cout<<endl;int main()/int i=0;for (i=0;i<ram.size();i+ )rami=0;/該模擬進程總共有20條指令 instructesi 為i條指令所在頁int instructes21=0;srand();/隨機產生指令所在的頁for(int i=1;i<=20;i+) /該模擬進程指令或數(shù)據(jù)分布在6個頁面中 /分別為第 1,2,3,4,5,6 頁 instructesi=rand()%6+1; /cout&

7、lt;<"第"<<i<<"條指令所在頁"<<instructesi<<endl; printf("第%2d指令所在頁%d n",i,instructesi);int count=0;for ( i=1;i<=20;i+)printf("當前待執(zhí)行指令所在頁:%2d:n",instructesi);display();int pos=isContain(instructesi);if (pos=ram.size()printf("第%2d頁不在內存中 -> 缺頁中斷n",instructesi);intServer(instructesi);count+;cout<<endl;cout<<"總共執(zhí)行20條指令n"<<"缺頁次數(shù):"<<count<<endl;cout<<"缺頁率:"<<(float)cou