First Input First Output的縮寫，先入先出隊列，這是一種傳統的按序執行方法，先進入的指令先完成并引退，跟著才執行第二條指令。

　　FIFO（First Input First Output），即先進先出隊列。在超市購物之后會提著我們滿滿的購物車來到收銀臺排在結賬隊伍的最后，眼睜睜地看著前面的客戶一個個離開。這就是一種先進先出機制，先排隊的客戶先行結賬離開。

　　fifo算法原理

　　在計算機中，先入先出隊列是一種傳統的按序執行方法，先進入的指令先完成并引退，跟著才執行第二條指令（指令就是計算機在響應用戶操作的程序代碼，對用戶而言是透明的）。如圖1所示，當CPU在某一時段來不及響應所有的指令時，指令就會被安排在FIFO隊列中，比如0號指令先進入隊列，接著是1號指令、2號指令……當CPU完成當前指令以后就會從隊列中取出0號指令先行執行，此時1號指令就會接替0號指令的位置，同樣，2號指令、3號指令……都會向前挪一個位置，這樣解釋大家清楚了吧？

　　圖1 先進先出隊列

　　FIFO是隊列機制中最簡單的，每個接口上都存在FIFO隊列，表面上看FIFO隊列并沒有提供什么QoS（Quality of Service，服務質量）保證，甚至很多人認為FIFO嚴格意義上不算做一種隊列技術，實則不然，FIFO是其它隊列的基礎，FIFO也會影響到衡量QoS的關鍵指標：報文的丟棄、延時、抖動。既然只有一個隊列，自然不需要考慮如何對報文進行復雜的流量分類，也不用考慮下一個報文怎么拿、拿多少的問題，而且因為按順序取報文，FIFO無需對報文重新排序。簡化了這些實現其實也就提高了對報文時延的保證。

　　FIFO關心的就是隊列長度問題，隊列長度會影響到時延、抖動、丟包率。因為隊列長度是有限的，有可能被填滿，這就涉及到該機制的丟棄原則。常見的一個丟棄原則叫做Tail Drop機制。簡單地說就是該隊列如果已經滿了，那么后續進入的報文被丟棄，而沒有什么機制來保證后續的報文可以擠掉已經在隊列內的報文。在這種機制中，如果定義了較長的隊列長度，那么隊列不容易填滿，被丟棄的報文也就少了，但是隊列長度太長了會出現時延的問題，一般情況下時延的增加會導致抖動也增加。如果定義了較短的隊列，時延的問題可以得到解決，但是發生Tail Drop的報文就變多了。

　　先進先出（FIFO）置換算法

　　這是最早出現的置換算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現簡單，只需把一個進程已調入內存的頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進程實際運行的規律不相適應，因為在進程中，有些頁面經常被訪問，比如，含有全局變量、常用函數、例程等的頁面，FIFO 算法并不能保證這些頁面不被淘汰。

　　這里，我們只需要設置一個先進先出隊列就可以。最先進入內存的頁面最早被轉換出去。

　　例如：假定系統為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：

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

　　結果為：

　　7

　　7 0

　　7 0 1

　　0 1 2

　　1 2 0

　　2 0 3

　　2 3 0

　　3 0 4

　　0 4 2

　　4 2 3

　　2 3 0

　　2 0 3

　　0 3 2

　　3 2 1

　　3 1 2

　　1 2 0

　　2 0 1

　　0 1 7

　　1 7 0

　　7 0 1

　　先進先出（FIFO）置換算法模擬源代碼

　　［java］ view plain copy/**

　　* 先進先出轉換算法

　　* @author Administrator

　　*

　　*/

　　public class FIFO {

　　/**

　　* 內存塊的個數

　　*/

　　public static final int N = 3;

　　/**

　　* 內存塊數組

　　*/

　　Object［］ array = new Object［N］;

　　private int size;

　　/**

　　* 內存是非空為否

　　* @return

　　*/

　　public boolean isEmpty（） {

　　if（0 == size）

　　return true;

　　else

　　return false;

　　}

　　public/**

　　* 內存是非空滿

　　* @return

　　*/ boolean isFulled（） {

　　if（size 》= N）

　　return true;

　　else

　　return false;

　　}

　　/**

　　* 元素（頁框）的個數

　　* @return

　　*/

　　public int size（） {

　　return size;

　　}

　　/**

　　* 查找元素o在數組中的位置

　　* @param o

　　* @return

　　*/

　　public int indexOfElement（Object o） {

　　for（int i=0; i《N; i++） {

　　if（o == array［i］） {

　　return i;

　　}

　　}

　　return -1;

　　}

　　/*public void push（Object o） {

　　Node p = new Node（o）;

　　//Node p2 = head;

　　p.next = head;

　　head = p;

　　}*/

　　/**

　　* 頁面轉換

　　* @param obj

　　*/

　　public Object trans（Object obj）{

　　Object e = null;

　　int t = 0;

　　if（indexOfElement（obj） ！= -1） {

　　t = indexOfElement（obj）;

　　for（int i=t; i《size-1; i++） {

　　array［i］ = array［i+1］;

　　}

　　array［size-1］ = obj;

　　} else {

　　if（！isFulled（））{

　　array［size］ = obj;

　　size ++;

　　} else {

　　for（int i=0; i《size-1; i++） {

　　array［i］ = array［i+1］;

　　}

　　array［size-1］ = obj;

　　}

　　}

　　if（ -1 == t） {

　　return null;

　　} else {

　　return array［t］;

　　}

　　}

　　/**

　　* 輸出內存區中的各數據

　　*/

　　public void showMemoryBlock（） {

　　for（int i=0; i《size; i++） {

　　System.out.print（array［i］ + “ ”）;

　　}

　　}

　　/**

　　* 清空隊列（頁框）

　　*/

　　public void clear（）{

　　}

　　/**

　　* @param args

　　*/

　　public static void main（String［］ args） {

　　Integer iter［］ = {7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1};

　　FIFO fifo = new FIFO（）;

　　for（int i=0; i《iter.length; i++） {

　　fifo.trans（iter［i］）;

　　fifo.showMemoryBlock（）;

　　System.out.println（）;

　　}

　　}

　　}