電子發(fā)燒友App
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ī)制中最簡(jiǎn)單的，每個(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)文重新排序。簡(jiǎn)化了這些實(shí)現(xiàn)其實(shí)也就提高了對(duì)報(bào)文時(shí)延的保證。
FIFO關(guān)心的就是隊(duì)列長(zhǎng)度問題，隊(duì)列長(zhǎng)度會(huì)影響到時(shí)延、抖動(dòng)、丟包率。因?yàn)殛?duì)列長(zhǎng)度是有限的，有可能被填滿，這就涉及到該機(jī)制的丟棄原則。常見的一個(gè)丟棄原則叫做Tail Drop機(jī)制。簡(jiǎn)單地說就是該隊(duì)列如果已經(jīng)滿了，那么后續(xù)進(jìn)入的報(bào)文被丟棄，而沒有什么機(jī)制來保證后續(xù)的報(bào)文可以擠掉已經(jīng)在隊(duì)列內(nèi)的報(bào)文。在這種機(jī)制中，如果定義了較長(zhǎng)的隊(duì)列長(zhǎng)度，那么隊(duì)列不容易填滿，被丟棄的報(bào)文也就少了，但是隊(duì)列長(zhǎng)度太長(zhǎng)了會(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)簡(jiǎ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）置換算法模擬源代碼
［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（）;
}
}
}
工商網(wǎng)監(jiān)
評(píng)論