| Fifo |
Articles about Fifo |
Information AboutFifo |
| CATEGORIES ABOUT FIFO | |
| scheduling algorithms | |
| inter-process communication | |
|
FIFO is an time in the order they come. A Priority Queue is a variation on the queue which does not qualify for the name FIFO, because it is not accurately descriptive of that Data Structure 's behavior. Queueing Theory encompasses the more general concept of queue, as well as interactions between strict-FIFO queues. The expression FIFO can be used in different contexts. PEOPLE
COMPUTER SCIENCE Data structure In Computer Science this term refers to the way data stored in a queue is processed. Each item in the queue is stored in a queue (''simpliciter'') data structure. The first data to be added to the queue will be the first data to be removed, then processing proceeds sequentially in the same order. This is typical behavior for a queue, but see also the LIFO and Stack algorithms. A typical data structure will look like struct fifo_node {
value_type value; }; class fifo {
{
front = front->next; return tmp; } queue(value) {
tempNode->value = value; tempNode->next = back; back = tempNode; } } (For information on the abstract data structure, see Queue . For details of a common implementation, see Circular Buffer .) Popular UNIX systems include a sys/queue.h C/C++ header file which provides macros usable by applications which need to create FIFO queues. Head or tail first Authors and users of FIFO queue software should consider carefully the use of the terms "head" and "tail" to refer to the two ends of the queue. To many people, items should enter a queue at the tail, remain in the queue until they reach the head and leave the queue from there. This point of view is justified by analogy with queues of people waiting for some kind of service and parallels the use of "front" and "back" in the above example. Other people, however, believe that you enter a queue at the head and leave at the tail, in the manner of food passing through a snake. Queues written in that way appear in places that might be considered authoritiative, such as the GNU/Linux operating system, making the point of view hard to dismiss however repugnant you find the idea of getting your data from a snake's rear-end. Pipes In computing environments that support the Pipes And Filters model for Interprocess Communication , a FIFO is another name for a Named Pipe . ELECTRONICS FIFOs are used commonly in Electronic circuits for buffering and flow control. In hardware form a FIFO primarily consists of a set of read and write pointers, storage and control logic. Storage may be SRAM, flip-flops, latches or any other suitable form of storage. For FIFOs of non-trivial size a dual-port SRAM is usually used where one port is used for writing and the other is used for reading. A synchronous FIFO is a FIFO where the same clock is used for both reading and writing. An asynchronous FIFO uses different clocks for reading and writing. Asynchronous FIFOs introduce Metastability issues. A common implementation of an asychronous FIFO uses a Gray Code (or any unit distance code) for the read and write pointers to ensure reliable flag generation. One further note concerning flag generation is that one must necessarily use pointer arithmetic to generate flags for asynchronous FIFO implementations. Conversely, one may use either a " Leaky Bucket " approach or pointer arithmetic to generate flags in synchronous FIFO implementations. Examples of FIFO status flags include: full, empty, almost full, or almost empty. The first known FIFO implemented in electronics is done by Peter Alfke in 1969 at Fairchild Semiconductors. Peter Alfke is now a Director at Xilinx . FIFO FULL/EMPTY In hardware FIFO is used for synchronization purposes. It is often implemented as a Circular Queue , and thus has two pointers: 1. Read Pointer/Read Address Register 2. Write Pointer/Write Address Register Read and write addresses are initially both at the first memory location and the FIFO queue is Empty. FIFO Empty: When read address register reaches to write address register, the FIFO triggers the Empty signal. FIFO FULL: When write address register reaches to read address register, the FIFO triggers the FULL signal. SEE ALSO
REFERENCES |
|
|