Gömülü Sistemlerde Kuyruk(Queue) Yapısı

Queue Nedir ?

Gömülü sistemlerde çok sık kullanılan bir veri yapısı olan kuyruk yapısından bahsedeceğim. Öncelikle kuyruk (queue) nedir ne değildir ile başlayıp, çeşitli kullanım alanlarından bahsedip, son olarakta bir kütüphane ile bunu realize edeceğiz.

Anlatıma geçmeden birkaç görsel ile hayal gücünüzde bu veri yapısının neye benzediği ile başlayalım.

Queue_Header

Queue yapısı temelinde bir ilk giren ilk çıkar (First in First Out (FIFO)) temelinde bir yapıdır. Bu verinin boyutunun ne olduğundan ziyade verinin tampon bellekte (buffer) yerleştirildiği yeri belirlemek ve doğru bir şekilde ilgili yer indislerini yönetmek önünüze çıkan yegâne zorluk olacaktır.

Nerelerde Kullanılır ?

Kullanım alanı kullanıcın isteği doğrultusunda sınırsız olabileceği gibi gömülü sistemlerde en çok kullanıldığı yerler şunlardır;

  • İşlemcinin ana işlemleri arasında birden çok veri giriş/çıkışının (Input/Output (I/O)) yönetildiği ve gelen verilerin anlık parlamalar(burst) ile gelip uzunca süre işlenmesi için size boşluk kaldığında,
  • İşlemcinizin hızlı ama çevreselin I/O hızının yavaş olduğu durumlarda,
    • UART,
    • SPI,
    • I2C gibi  I/O modüllerinde sıkça kullanılır.
  • Temelinde bir veri I/O modeli olduğu için çoklu işlem yapılı (multi-threaded) uygulamalarda threadler arasında veri paylaşımı için sıkça kullanılır.

                                         

Nasıl Yönetilir ?

Yazının başında bahsettiğim gibi queue yapısı aslında bir FIFO fakat yazılım tabanlı bir kopyası sadece… Tek farkı donanım üstünden kullanıldığında ilgili yazmaça (registera) yazmak (push, enqueue vs.) ilgili donanımın veri miktarını 1 arttırırken, okumak 1 azaltıyor ve de bize hafıza ile ilgili herhangi bir indis tutma, yönetme, buffer büyüklüğü aşıldı mı sorgusunu gerçekleştirme ihtiyacı kalmıyor. Lakin bu yazının amacı bu modülü yazılım ile yapmak olduğu için hafızayı yönetmek, ilgili queue bufferının sonuna gelip gelmediğimizi kontrol etmek,  queuenun yazmaya ve/veya okumaya müsait olup/olmadığını kontrol etmek bizlere düşüyor.

Bu noktada neredeyse milyonlarca implementasyonla karşılaşabilirsiniz. Linux’ün Kernel kodlarında yapılan yaklaşım şu şekildedir.

  • Yazıcı indisi(head): Verinin son yazıldığı yeri gösterir ve okuyucu indise yazma yoluyla eşit olmaması gerekir.
  • Okuyucu indisi(tail): Verinin okunacağı indisi kontrol eder ve heade ulaşmışsa ilgili queueda okunacak bir şey olmadığını gösterir.
  • Linux Kernel’i sanat eseri sayılabilecek (State-of-Art) bir kod olduğu için queuenun sonunu bulmak için birçok implementasyondan farklı olarak modulo (%) işlemi yerine çok daha efektif olan lojik ve (and, &) işlemini kullanır. Bunu kullanmak  içinse queue için ayırdığımız bufferın boyutunun 2’nin üssü olması gerekir. (1, 2, 4, 8, 16, 32 ……256…..1024…)

Bu implementasyonda ki kayıp ilgili queueda bir elemanı asla dolduramamaktır. Örneğin üst üste yazma yapıldığında head taili ezemeyeceği için ilgili 1 alandan feragat etmeniz gerekir.

Kendi implementasyonumuzu daha da reelize etmek için konuyu derinleştirmek gerekir. Queue yapısında basitçe veri yazdığımızda 1 artan bir indisi, okuduğumuzda da 1 artan bir başka indisi bulunmakta ve de boyutunu okuyabildiğimiz bir başka indisimiz bulunmalıdır. Linux’ten gördüğümüz üzere eğer queuemuzun boyutu 2’nin üssü olursa % işlemi yerine & işlemi kullanabilmekteyiz. Eğer 2’nin üssü kullanmaz isek % işlemi gibi yaygın hiçbir işlemcide donanımsal implemente edilmeyen bir matematiksel işlem kullandığımızdan çalışma zamanında (run-time) kayba uğrarız.

Uygulama

İmplementasyon aşamasında ilgili queueya yaptığımız girdilerin bir fonksiyon çağırmada topluca atılabilmesi için variadic macro denilen değişken sayıda parametre alabilen fonksiyon tipi kullanılmıştır.
Böylelikle put_to_queue fonksiyonu 3. argüman olan variable data length (değişken veri uzunluğu) her zaman gerek duymaz hale getirmiş bulunduk. 3. parametre olan ve uint32_t tipinde 4 byte uzunluğunda olan fonksiyona geçilen değişken var olup olmadığı ise queue_s içerisinde bulunan  q_inout_fixed_size değişkeninin 0xFFFF olup olmaması yardımı ile belirlenmektedir. Böylelikle okuma yönünde get_from_queue fonksiyonu da bu çok yönlülüğe uyumlu çalışmaktadır.

Kütüphanede başarılı olan her put ve get fonksiyonu 1 döndürmekte iken başarısızlar 0 döndürmektedir.

example.c (Edit 11/04/2020)

 

byte_queue.h dosyamızın içeriği

byte_queue.c dosyasımızın içeriği

 

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir