FIFO (bilgi işlem ve elektronik) - FIFO (computing and electronics)

Bir FIFO kuyruğunun temsili

Hesaplamada ve sistem teorisinde , FIFO ( ilk giren ilk çıkar için bir kısaltma ), en eski (ilk) girişin veya "baş" ın bulunduğu bir veri yapısının (genellikle, özellikle bir veri tamponunun ) sıra , önce işlenir.

Böyle işleme bir insanları hizmet benzerdir kuyruk alanı bir üzerinde ilk gelene ilk hizmet onlar sıranın kuyruk varmak ettiği aynı sırada, yani (FCFS) bazında.

FCFS aynı zamanda FIFO işletim sistemi çizelgeleme algoritması için bir jargon terimidir ve her işlem merkezi işlem birimi (CPU) zamanını talep edildiği sırada verir. FIFO'nun tam tersi, en genç girişin veya "yığının tepesinin" ilk önce işlendiği, son giren ilk çıkar olan LIFO'dur. Bir öncelik kuyruğu ne FIFO ne de LIFO'dur, ancak geçici olarak veya varsayılan olarak benzer davranışları benimseyebilir. Kuyruk teorisi , veri yapılarının işlenmesine yönelik bu yöntemleri ve katı FIFO kuyrukları arasındaki etkileşimleri kapsar.

Bilgisayar Bilimi

Kuyruklama ve kuyruktan çıkarma işlemleriyle bir FIFO kuyruğunun temsili.

Uygulamaya bağlı olarak, bir FIFO bir donanım kaydırma yazmacı olarak veya farklı bellek yapıları, tipik olarak dairesel bir tampon veya bir tür liste kullanarak uygulanabilir . Soyut veri yapısı hakkında bilgi için bkz. Kuyruk (veri yapısı) . Bir FIFO kuyruğunun çoğu yazılım uygulaması iş parçacığı için güvenli değildir ve veri yapısı zincirinin bir seferde yalnızca bir iş parçacığı tarafından değiştirildiğini doğrulamak için bir kilitleme mekanizması gerektirir.

Aşağıdaki kod, bağlantılı bir liste FIFO C ++ dil uygulamasını gösterir. Pratikte, popüler Unix sistemleri C sys / queue.h makroları veya C ++ standart kitaplık std :: list şablonu dahil olmak üzere , veri yapısını sıfırdan uygulama ihtiyacını ortadan kaldıran bir dizi liste uygulaması mevcuttur . 

#include <memory>
#include <stdexcept>

using namespace std;

template <typename T>
class FIFO {
    struct Node {
        T value;
        shared_ptr<Node> next = nullptr;

        Node(T _value): value(_value) {}
    };

    shared_ptr<Node> front = nullptr;
    shared_ptr<Node> back  = nullptr;

public:
    void enqueue(T _value) {
        if (front == nullptr) {
            front = make_shared<Node>(_value);
            back = front;
        } else {
            back->next = make_shared<Node>(_value);
            back = back->next;
        }
    }

    T dequeue() {
        if (front == nullptr)
            throw underflow_error("Nothing to dequeue");

        T value = front->value;
        front = move(front->next);
        
        return value;
    }
};

İşlemler arası iletişim için borular ve filtreler modelini destekleyen bilgi işlem ortamlarında , bir FIFO, adlandırılmış bir kanal için başka bir addır .

Disk denetleyicileri, FIFO'yu disk G / Ç isteklerine hizmet verilecek sırayı belirlemek için bir disk zamanlama algoritması olarak kullanabilir; burada, daha önce bahsedilen CPU zamanlamasında olduğu gibi aynı FCFS başlatması ile de bilinir.

Bilgisayar ağlarında kullanılan iletişim ağı köprüleri , anahtarları ve yönlendiricileri , veri paketlerini bir sonraki hedeflerine doğru yolda tutmak için FIFO'ları kullanır. Tipik olarak ağ bağlantısı başına en az bir FIFO yapısı kullanılır. Bazı cihazlarda, farklı bilgi türlerini eşzamanlı ve bağımsız olarak sıraya koymak için birden çok FIFO bulunur.

Elektronik

Bir FIFO programı

FIFO'lar genellikle elektronik devrelerde donanım ve yazılım arasında tamponlama ve akış kontrolü için kullanılır . Donanım biçiminde, bir FIFO öncelikle bir dizi okuma ve yazma işaretçisi , depolama ve kontrol mantığından oluşur. Depolama, statik rasgele erişimli bellek (SRAM), parmak arası terlikler , mandallar veya başka herhangi bir uygun depolama biçimi olabilir. Önemsiz boyuttaki FIFO'lar için, genellikle bir bağlantı noktasının yazmaya, diğerinin okumaya ayrıldığı bir çift bağlantı noktalı SRAM kullanılır.

Elektronikte uygulanan ilk bilinen FIFO, 1969'da Fairchild Semiconductor'da Peter Alfke tarafından yapıldı . Alfke de sonradan müdürlük yaptı Xlinix .

Eşzamanlılık

Senkronize FIFO, aynı saatin hem okuma hem de yazma için kullanıldığı bir FIFO'dur. Eşzamansız bir FIFO, okuma ve yazma için farklı saatler kullanır ve metastabilite sorunları ortaya çıkarabilir . Eşzamansız bir FIFO'nun ortak bir uygulaması, güvenilir bayrak oluşturmayı sağlamak için okuma ve yazma işaretçileri için bir Gray kodu (veya herhangi bir birim mesafe kodu) kullanır. Bayrak üretimi ile ilgili bir başka not, eşzamansız FIFO uygulamaları için işaretler oluşturmak için zorunlu olarak işaretçi aritmetiğinin kullanılması gerektiğidir. Tersine, senkronize FIFO uygulamalarında bayraklar oluşturmak için ya sızdıran bir kova yaklaşımı ya da işaretçi aritmetiği kullanılabilir.

Senkronizasyon amacıyla bir donanım FIFO kullanılır. Genellikle dairesel bir kuyruk olarak uygulanır ve bu nedenle iki işaretçisi vardır :

  • İşaretçiyi oku / adres kaydını oku
  • İşaretçi yaz / adres kaydını yaz

Durum bayrakları

FIFO durum bayraklarının örnekleri şunları içerir: dolu, boş, neredeyse dolu ve neredeyse boş. Okunan adres kaydı yazma adresi yazmacına ulaştığında bir FIFO boştur . Yazma adresi yazmacı, okunan adres yazmacına ulaştığında bir FIFO doludur. Okuma ve yazma adresleri başlangıçta hem ilk bellek konumunda hem de FIFO kuyruğu boştur .

Her iki durumda da okuma ve yazma adresleri eşit olur. İki durumu birbirinden ayırmak için basit ve sağlam bir çözüm, her okuma ve yazma adresi için adres her kaydırıldığında tersine çevrilen fazladan bir bit eklemektir . Bu kurulumla, netleştirme koşulları şunlardır:

  • Okunan adres kaydı yazma adresi yazmacına eşit olduğunda, FIFO boştur.
  • Okuma adresi en az anlamlı biti (LSB) yazma adresi LSB'lerine eşit olduğunda ve ekstra en anlamlı bit farklı olduğunda, FIFO doludur.

Ayrıca bakınız

Referanslar

Dış bağlantılar