fifo頁面淘汰演算法

『壹』 最佳頁面淘汰演算法是怎樣計算的

1;
50%指令順序執行
2;25%指令均勻散步在前地址部分
3;25%指令均勻散步在後地址部分
題目中選用:命中率=1-頁面失敗次數(只選用2的冪次)/葉地址流長度
演算法:opt
fifo
rlu(定義)(至少用兩個演算法)程序流程圖開始:產生給定長度符合假定的指令地址流->為每一個指令地址的成對應的訪問頁號->置初算size=1~8(1,2,4,8)(頁面大上)實存
=4~32(4,8,16,32)->輸入淘汰演算法->A->ALG=FIFO(OR)(LRU)->FIFO->用FIFO計算命中率->用LRU計算命中率->輸出結果->結束演算法定義:理想淘汰演算法--最佳頁面演算法(OPT)
淘汰以後不再需要的或最遠的將來才會用到的頁面
先進先出頁面淘汰演算法(FIFO)
選擇在內存中駐留時間最長的頁並淘汰之
最近最少使用頁面淘汰演算法(LRU)
選擇最後一次訪問時間距離當前時間最長的一頁並淘汰之即淘汰沒有使用的時間最長的頁.

『貳』 最佳頁面淘汰演算法是怎樣計算的

<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%

『叄』 關於先進先出（FIFO）頁面淘汰演算法

輸入：1，2，3，4，1，2，5，1，2，3，4，5

先進先出，就是保存最近3個訪問的記錄在內存中
, , <—1 中斷1次
, ,1<—2 中斷1次
, 1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—1 中斷1次
3,4 ,1<—2 中斷1次
4,1,2<—5 中斷1次
1,2,5<—1 命中，不中斷
2,5,1 <—2 命中，不中斷
5,1,2<—3 中斷1次
1,2,3 <—4 中斷1次
2,3,4 <—5 中斷1次
3,4,5

累計中斷12次

『肆』 fifo演算法是什麼

FIFO（First Input First Output），即先進先出隊列。

FIFO是隊列機制中最簡單的，每個介面上都存在FIFO隊列，FIFO演算法維護一個先進先出隊列，隊列長度為分配給這個進程的頁面數M。開始時隊列是空的，裝入進程的第一頁即可啟動運行，當訪問到某個不在內存的頁面時，把它從輔存調入，加入FIFO隊列的尾部。

fifo演算法的特點

FIFO演算法的優點是簡單，一個很嚴重的缺點是在有的情況下，給進程的頁面數M增加時，同樣的頁面序列P，缺頁率反而增加，這稱為FIFO異常。有興趣的話，不妨自己構造這種例子。當某個頁面剛被淘汰又要調入時容易產生這種現象。可以構造出無限多個例子。

『伍』 操作系統課程設計，用C#實現內存頁面的置換。實現演算法間比較

頁面置換演算法

一．題目要求：

通過實現頁面置換演算法的FIFO和LRU兩種演算法，理解進程運行時系統是怎樣選擇換出頁面的，對於兩種不同的演算法各自的優缺點是哪些。

要求設計主界面以靈活選擇某演算法，且以下演算法都要實現 1) 最佳置換演算法(OPT)：將以後永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。

2) 先進先出演算法(FIFO)：淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

3) 最近最久未使用演算法(LRU)：淘汰最近最久未被使用的頁面。 4) 最不經常使用演算法(LFU) 二．實驗目的：

1、用C語言編寫OPT、FIFO、LRU，LFU四種置換演算法。 2、熟悉內存分頁管理策略。 3、了解頁面置換的演算法。 4、掌握一般常用的調度演算法。 5、根據方案使演算法得以模擬實現。 6、鍛煉知識的運用能力和實踐能力。 三、設計要求

1、編寫演算法，實現頁面置換演算法FIFO、LRU；

2、針對內存地址引用串，運行頁面置換演算法進行頁面置換； 3、演算法所需的各種參數由輸入產生（手工輸入或者隨機數產生）； 4、輸出內存駐留的頁面集合，頁錯誤次數以及頁錯誤率；

四．相關知識：

1．虛擬存儲器的引入：

局部性原理：程序在執行時在一較短時間內僅限於某個部分；相應的，它所訪問的存儲空間也局限於某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。

2．虛擬存儲器的定義：

虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。

3．虛擬存儲器的實現方式：

分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。

請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能後，所形成的段式虛擬存儲系統。

4．頁面分配：

平均分配演算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配演算法，根據進程的大小按比例分配物理塊。

考慮優先的分配演算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額後，分配給各進程。

5．頁面置換演算法：

常用的頁面置換演算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、設計說明

1、採用數組頁面的頁號

2、FIFO演算法，選擇在內存中駐留時間最久的頁面予以淘汰；

分配n個物理塊給進程，運行時先把前n個不同頁面一起裝入內存，然後再從後面逐一比較，輸出頁面及頁錯誤數和頁錯誤率。

3、LRU演算法，根據頁面調入內存後的使用情況進行決策；

同樣分配n個物理塊給進程，前n個不同頁面一起裝入內存，後面步驟與前一演算法類似。

選擇置換演算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換： 六．設計思想：

OPT基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組next[mSIZE]記錄物理塊中對應頁面的最後訪問時間。每當發生缺頁時，就從物理塊中找出最後訪問時間最大的頁面，調出該頁，換入所缺的頁面。

FIFO基本思想：

是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該演算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者藉助輔助數組time[mSIZE]記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。

LRU基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組flag[10]標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。 七．流程圖：

如下頁所示

六．運行結果： 1. 按任意鍵進行初始化：

2. 載入數據：

3. 進入置換演算法選擇界面：

4.運算中延遲操作：

5.三種演算法演示結果：

『陸』 在請求分頁存儲管理中，若採用FIFO頁面淘汰演算法，則當可供分配的頁楨樹增加時，缺頁中斷次數怎樣麻

理論上是減少的，但如果是FIFO演算法

在分頁式虛擬存儲器管理中，發生缺頁時的置換演算法採用FIFO（先進先出）演算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多但缺頁率反而提高的異常現象。稱為belady現象。
答案是可能增加也可能減少

『柒』 頁面置換演算法FIFO 、LRU求缺頁中斷次數

(1)FIFO
123412512345
----------------------------------------
123412555344
12341222533該行是怎麼算出來的？
1234111255該行是怎麼算出來的？
----------------------------------------
缺頁中斷次數=9
FIFO是這樣的：3個內存塊構成一個隊列，前3個頁面依次入隊（3個缺頁），內存中為3-2-1；
接著要訪問4號頁面，內存中沒有（1個缺頁），按FIFO，1號頁面淘汰，內存中為4-3-2；
接著要訪問1號頁面，內存中沒有（1個缺頁），按FIFO，2號頁面淘汰，內存中為1-4-3；
接著要訪問2號頁面，內存中沒有（1個缺頁），按FIFO，3號頁面淘汰，內存中為2-1-4；
接著要訪問5號頁面，內存中沒有（1個缺頁），按FIFO，4號頁面淘汰，內存中為5-2-1；
接著要訪問1號頁面，內存中有（命中），內存中為5-2-1；
接著要訪問2號頁面，內存中有（命中），內存中為5-2-1；
接著要訪問3號頁面，內存中沒有（1個缺頁），按FIFO，1號頁面淘汰，內存中為3-5-2；
接著要訪問4號頁面，內存中沒有（1個缺頁），按FIFO，2號頁面淘汰，內存中為4-3-5；
接著要訪問5號頁面，內存中有（命中），內存中為4-3-5；
缺頁中斷次數=9（12次訪問，只有三次命中）
LRU不同於FIFO的地方是，FIFO是先進先出，LRU是最近最少用，如果1個頁面使用了，要調整內存中頁面的順序，如上面的FIFO中：
接著要訪問1號頁面，內存中有（命中），內存中為5-2-1；
在LRU中，則為
接著要訪問1號頁面，內存中有（命中），內存中為1-5-2；

『捌』 操作系統原理與應用之 頁面調度演算法問題

FIFO：即先進先出演算法，就是先進去的頁在位置不夠時先淘汰。所以具體如下：
主存開始為空
訪問1，1不在主存中，產生缺頁中斷，添加，主存里現在是：1
訪問2，2不在主存中，產生缺頁中斷，添加，主存里現在是：1,2
以此類推，
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
訪問4，4不在主存中，缺頁中斷，主存滿了，最早的1淘汰，主存里現在是：2,3,6,4
然後3,6,4,7（缺頁中斷，2淘汰）
然後3，3在主存中，不產生中斷
然後6,4,7,2（缺頁中斷，3淘汰）
4,7,2,1（缺頁中斷，6淘汰）
4在主存中，不中斷
7在主存中，不中斷
7,2,1,5（缺頁中斷，4淘汰）
2,1,5,6（缺頁中斷，7淘汰）
5在主存中，不中斷
2在主存中，不中斷
1在主存中，不中斷
整個FIFO過程就是這樣。

LRU是最近最久未使用的先淘汰，具體如下：
1（缺頁中斷）
1,2（缺頁中斷）
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
2,3,6,4（缺頁中斷，1最久沒用過，淘汰）
3,6,4,7（缺頁中斷，2最久沒用過，淘汰）
3在主存中，不中斷，3最近使用過，主存中順序調整為6,4,7,3
4,7,3,2（缺頁中斷，6最久沒用過，淘汰）
7,3,2,1（缺頁中斷，4最久沒用過，淘汰）
3,2,1,4（缺頁中斷，7最久沒用過，淘汰）
2,1,4,7（缺頁中斷，3最久沒用過，淘汰）
1,4,7,5（缺頁中斷，2最久沒用過，淘汰）
4,7,5,6（缺頁中斷，1最久沒用過，淘汰）
5在主存中，調整順序為4,7,6,5
7,6,5,2（缺頁中斷，4最久沒用過，淘汰）
6,5,2,1（缺頁中斷，7最久沒用過，淘汰）
整個LRU過程就是這樣。

全手打求採納謝謝~！如有問題請追問~