先進先出（FIFO，first-in, first-out）是處理從佇列或堆疊發出的程式工作要求的一種方法，它使最早的要求被最先處理。
基本介紹
- 中文名：先進先出
- 外文名：first-in, first-out
- 簡稱：FIFO
- 定義：處理從佇列或堆疊發出的一種方法
- 組成：存儲體、寫計數器等
- 學科：通信技術
概述,功能塊,先進先出存儲器電路原理,
概述
在計算機編程中，先進先出（FIFO，first-in, first-out）是處理從佇列或堆疊發出的程式工作要求的一種方法，它使最早的要求被最先處理。後進先出（LIFO，last-in, first-out）是另一種方法，它使最新的要求被最先處理，而最早的要求要等到佇列（或堆疊）中只有這一個要求時才會被處理。儘管後進先出似乎不公平，但是它卻更有效率。一個用後進先出處理的堆疊有時被稱為下推或下推彈出式堆疊（或列表）。
功能塊
FIFO由6個功能塊組成，它們是存儲體、寫計數器（WP）、讀計數器（RP）、滿邏輯IN_FULL、空邏輯IN_EMPTY和選擇邏輯SELECT。這是一個同步的FIFO。在時鐘脈衝的上升沿作用下，當WR=0且FULL=0時，DIN的數據將壓入FIFO堆疊。在通常情況下，RP所指出的單元內容總是放於DOUT的輸出數據線上，只是在RD=0且EMPTY=0時，RP的內容才改變而指向FIFO的下一個單元，下一個單元的內容替換當前內容並從DOUT輸出。應注意，在任何時候DOUT上都有一個數據輸出，而不像RAM那樣，只有在讀有效時才有數據輸出，平時為三態輸出。
先進先出存儲器電路原理
FIFO（First In First Out）是一種先進先出的數據快取器，它與普通存儲器的區別是沒有外部讀寫地址線，這樣使用起來非常簡單。但缺點是只能順序寫入數據，順序的讀出數據，其數據地址由內部讀寫指針自動加l完成，不能像普通存儲器那樣可以由地址線決定讀取或寫入某個指定的地址。
FIFO依據工作時鐘域，可分為同步FIFO和異步FIFO。同步FIFO是指讀時鐘和寫時鐘為同一個時鐘，在時鐘上升沿或下降沿發生讀寫操作。異步FIFO是指讀寫時鐘不一致，讀寫時鐘是互相獨立的。FIFO一般用於不同時鐘域之間的數據傳輸，如FIFO的一端是AD數據採集，另一端是計算機的PCI匯流排，假設其AD採集的速率為16位100KSPS，那么每秒的數據量為100K×16bit=1.6Mb/s，而PCI匯流排的速度為33MHz，匯流排寬度32bit，其最大傳輸速率為1056Mb/s，在兩個不同的時鐘域間就可以採用FIFO來作為數據緩衝。另外對於不同寬度的數據接口也可以用FIFO，例如，單片機位8位數據輸出，而DSP可能是16位數據輸入，在單片機與DSP連線時就可以使用FIFO來達到數據匹配的目的。
FIFO設計的難點在於如何判斷FIFO的空/滿狀態。為了保證數據正確地寫入或讀出，而不發生溢出或讀空的狀態出現，必須保證FIFO在滿的情況下，不能進行寫操作。在空的狀態下不能進行讀操作。怎樣判斷FIFO的滿/空就成了FIFO設計的核心問題。
FIFO的工作原理和佇列的原理一樣，都是先進來的數據先出去，所以可以使用佇列的思想去設計FIFO存儲器。佇列分順序佇列和循環佇列2種。順序佇列會隨著數據的入隊和出隊不斷地增長，最後可能溢出。只在數據不是很大時使用。通常採用更合理的循環佇列。
我們的按鍵值數據全部都存在一個暫存器數組裡面。這裡假設數組大小為8。頭指針指向最先入隊的數據，即將要出隊的數據。count存儲整個佇列裡面有多少個非空數據。當新的按鍵按下時，要存儲在head模8所對應的數組單元里。當要讀取鍵值時，只需把head指針所對應的那個元素輸出即可。每次執行人隊操作時，count都要加1。同理，每次執行出隊操作時，count都要減1。當count=0時，此時佇列為空，不能執行湊取操作，當count=8時，佇列為滿，不能執行存儲操作。使用循環佇列，不用擔心溢出問題。
