First Input First Output的縮寫，先入先出隊(duì)列，這是一種傳統(tǒng)的按序執(zhí)行方法，先進(jìn)入的指令先完成并引退，跟著才執(zhí)行第二條指令。

　　FIFO（First Input First Output），即先進(jìn)先出隊(duì)列。在超市購物之后會(huì)提著我們滿滿的購物車來到收銀臺(tái)排在結(jié)賬隊(duì)伍的最后，眼睜睜地看著前面的客戶一個(gè)個(gè)離開。這就是一種先進(jìn)先出機(jī)制，先排隊(duì)的客戶先行結(jié)賬離開。

　　fifo算法原理

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

　　圖1 先進(jìn)先出隊(duì)列

　　FIFO是隊(duì)列機(jī)制中最簡單的，每個(gè)接口上都存在FIFO隊(duì)列，表面上看FIFO隊(duì)列并沒有提供什么QoS（Quality of Service，服務(wù)質(zhì)量）保證，甚至很多人認(rèn)為FIFO嚴(yán)格意義上不算做一種隊(duì)列技術(shù)，實(shí)則不然，F(xiàn)IFO是其它隊(duì)列的基礎(chǔ)，F(xiàn)IFO也會(huì)影響到衡量QoS的關(guān)鍵指標(biāo)：報(bào)文的丟棄、延時(shí)、抖動(dòng)。既然只有一個(gè)隊(duì)列，自然不需要考慮如何對(duì)報(bào)文進(jìn)行復(fù)雜的流量分類，也不用考慮下一個(gè)報(bào)文怎么拿、拿多少的問題，而且因?yàn)榘错樞蛉?bào)文，F(xiàn)IFO無需對(duì)報(bào)文重新排序。簡化了這些實(shí)現(xiàn)其實(shí)也就提高了對(duì)報(bào)文時(shí)延的保證。

　　FIFO關(guān)心的就是隊(duì)列長度問題，隊(duì)列長度會(huì)影響到時(shí)延、抖動(dòng)、丟包率。因?yàn)殛?duì)列長度是有限的，有可能被填滿，這就涉及到該機(jī)制的丟棄原則。常見的一個(gè)丟棄原則叫做Tail Drop機(jī)制。簡單地說就是該隊(duì)列如果已經(jīng)滿了，那么后續(xù)進(jìn)入的報(bào)文被丟棄，而沒有什么機(jī)制來保證后續(xù)的報(bào)文可以擠掉已經(jīng)在隊(duì)列內(nèi)的報(bào)文。在這種機(jī)制中，如果定義了較長的隊(duì)列長度，那么隊(duì)列不容易填滿，被丟棄的報(bào)文也就少了，但是隊(duì)列長度太長了會(huì)出現(xiàn)時(shí)延的問題，一般情況下時(shí)延的增加會(huì)導(dǎo)致抖動(dòng)也增加。如果定義了較短的隊(duì)列，時(shí)延的問題可以得到解決，但是發(fā)生Tail Drop的報(bào)文就變多了。

　　先進(jìn)先出（FIFO）置換算法

　　這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)簡單，只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行的規(guī)律不相適應(yīng)，因?yàn)樵谶M(jìn)程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO 算法并不能保證這些頁面不被淘汰。

　　這里，我們只需要設(shè)置一個(gè)先進(jìn)先出隊(duì)列就可以。最先進(jìn)入內(nèi)存的頁面最早被轉(zhuǎn)換出去。

　　例如：假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下的頁面號(hào)引用串：

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

　　結(jié)果為：

　　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

　　先進(jìn)先出（FIFO）置換算法模擬源代碼

　?。?a href="http://www.delux-kingway.cn/v/tag/852/" target="_blank">java］ view plain copy/**

　　* 先進(jìn)先出轉(zhuǎn)換算法

　　* @author Administrator

　　*

　　*/

　　public class FIFO {

　　/**

　　* 內(nèi)存塊的個(gè)數(shù)

　　*/

　　public static final int N = 3;

　　/**

　　* 內(nèi)存塊數(shù)組

　　*/

　　Object［］ array = new Object［N］;

　　private int size;

　　/**

　　* 內(nèi)存是非空為否

　　* @return

　　*/

　　public boolean isEmpty（） {

　　if（0 == size）

　　return true;

　　else

　　return false;

　　}

　　public/**

　　* 內(nèi)存是非空滿

　　* @return

　　*/ boolean isFulled（） {

　　if（size 》= N）

　　return true;

　　else

　　return false;

　　}

　　/**

　　* 元素（頁框）的個(gè)數(shù)

　　* @return

　　*/

　　public int size（） {

　　return size;

　　}

　　/**

　　* 查找元素o在數(shù)組中的位置

　　* @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;

　　}*/

　　/**

　　* 頁面轉(zhuǎn)換

　　* @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］;

　　}

　　}

　　/**

　　* 輸出內(nèi)存區(qū)中的各數(shù)據(jù)

　　*/

　　public void showMemoryBlock（） {

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

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

　　}

　　}

　　/**

　　* 清空隊(duì)列（頁框）

　　*/

　　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（）;

　　}

　　}

　　}