Gömülü sistemlerde Circular/Ring Buffer kullanımı ve tasarımı
Gömülü sistemlerde yaygın olarak kullanılan veri yapılarından birtanesi Circular (Ring) buffer’dir. Circular Buffer parçalı olmayan (contiguous), sabit boyutlu, dolaşımlı (circular) ve FIFO (First In First Out) karakteristiğine sahip bir veri yapısıdır. Genellikle sabit uzunluklu bir kuyruk (queue) olarak kullanılır. Sabit uzunluklu bir kuyruk yerine daha sonradan ihtiyaç halinde kapasitesi yükseltilebilir bir kuyruk tasarımı da yapmamız mümkündür ancak gerçek zamanlı gömülü sistemler özelinde dinamik bellek yönetimi ile cihazın çalışma zamanı kararlılığını etkilememek amacı ile genellikle sadece ilklendirme sırasında tercih edilmektedir. Çalışma zamanında esnek bir yapı kurgulanmak isteniyor ise de nesne ve buffer bellekleri dinamik bellek yönetimi yerine bellek havuzu (memory pool) üzerinden statik bellek dağıtıcısı (static memory allocator) ile yönetilmektedir. Şu ana kadar bahsettiğim yapılar emniyet kritik uygulamalar için zaten standartlaştırılmaktadır ancak gömülü linux projelerinde (linux kernel de dahil) veri yapılarının birçoğunun dinamik bellek yönetimi ile kullanıldığı da görülmektedir. Bu yüzden gömülü yazılımlarda kullanılan veri yapılarında sadece statik bellek yönetimi kullanılır gibi bir genelleme yapmak tamamen yanlıştır.
Circular Buffer gömülü sistemlerde farklı dinamikler ile çalışan tüketici görevin (consumer task) üretici görev (producer task) tarafından sağlanan verileri güncel ve tamponlanmış bir şekilde alabilmesinde yardımcı olmaktadır. Burada task dediğimiz zaman sadece işletim sistemi düşünmemek gerekiyor. Bu bir bare-metal sistem de olabilir. Üretici taskı bir ISR (Interrupt Service Routine), tüketici taskı da super loop içerisinde yer alan bir işlev olabilir. Örnek bir senaryo söylersek ISR içerisinde ADC’den her veri okunduğunda verilerin circular buffer’a atılırken bir tüketici taskı tarafından da bu verilerin buffer’dan alınarak tüketilmesi yani bu verilerin kullanılarak bir RMS, FFT… gibi sinyal işleme süreçlerinin gerçekleştirilmesini söyleyebiliriz. En düşük öncelikli donanım kesmesi en yüksek öncelikli yazılım görevinden bile daha önce ele alınacağı için gömülü sistemlerde veriyi işleyebilmek için bu tarz tamponlama ihtiyaçları birçok uygulamada ortaya çıkmaktadır.
Circular buffer tasarımında tipik olarak head ve tail dediğimiz iki işaretçi bulunur. Tail işaretçisi veri eklendiğinde yani yazma işlemi yapıldığında hareket eder. Head işaretçisi ise veri okunduğunda hareket eder. Böylelikle bu iki işaretçi sayesinde circular buffer’in dolu ya da boş olup olmadığını ve aynı zamanda da circular buffer içerisinde ne kadarlık boş alan kaldığı gibi bilgileri elde edebilmemiz mümkün olmaktadır. Animasyon 1'i referans aldığımızda yeşil ok tail işaretçisini kırmızı ok da head işaretçisini belirtmektedir.
Circular buffer tasarımında bir t zamanında buffer’in dolu ya da boş olup olmadığını bilmek önemlidir. Eğer head ve tail işaretçileri birbirine eşit ise buffer’ın boş olduğunu söyleyebiliriz. Bu koşulu zaten buffer’i ilklendirdiğimizde iki işaretçiyi de 0'a eşitleyerek sağlamış oluyoruz ancak daha sonrasında veri yazma ve okuma yaptığımızda bu koşulu sağlamak için animasyonda da dikkat edeceğiniz üzere dizinin bir elemanı boş bırakılmaktadır. Bunun nedeni ise buffer tamamen dolu olduğunda yine head ve tail aynı noktaya geleceği için o an buffer’in dolu mu yoksa boş mu olduğunu ayırt etmemizin mümkün olmamasıdır. Mümkün olmasını sağlamak için de daha komplike bir tasarım yapmamız gerekecektir. Bu yüzdendir ki birçok circular buffer tasarımında array içerisinde bir eleman boş bırakılır ve buraya veri yazılmaz. Eğer tail işaretçisi bir sonraki hareketinde head ile aynı noktaya geliyor ise circular buffer tamamen dolmuş demektir. Özetle circular buffer’in dolu ya da boş olduğu aşağıdaki iki koşul ile kontrol edilmektedir.
- Head işaretçisi tail işaretçisine eşit ise circular buffer boştur.
- Tail işaretçisinin bir sonraki adımı head işaretçisine eşitse circular buffer doludur.
Circular buffer’ın dolu ya da boş olup olmadığı bizim için daha yolun başında neden bu kadar önemli oldu peki Şerafettin Hocam?
Çünkü circular buffer’a ekleme yapacaksak öncelikle bu buffer’ın dolu olup olmadığını kontrol etmek zorundayız. Eğer dolu ise tasarıma göre eski verinin üstüne yazılabilecek veya kullanıcıya bir şekilde bunu belirtecek aksiyonlar alınması gerekebilir. Aynı şekilde eğer buffer boş ise de okuma yapıldığı zaman buffer’da veri olmadığının belirtilmesi gerekebilir.
API Tasarımı
Tipik bir circular buffer uygulamasında ihtiyaç duyacağımız API’lar aşağıdaki gibidir.
Bir uygulama yazarken öncelikle arayüzü (interface) oluşturmak uygulamaya en baştan geniş çerçeveden bakmamıza yardımcı olmaktadır. API’lerde kullanılan veri yapısını benim yukarıda yaptığım gibi opaque olarak tanımlarsak herhangi bir kaynak kodu yazmasanız ve ilgili veri yapısını henüz oluşturmasanız bile kodunuz sadece başlık dosyası ile derlenecektir.
Kaynak kodunda da görüldüğü üzere circular buffer fonksiyonları generic bir şekilde kullanabilmek amacı ile verilerini almak için void işaretçiler tercih edilmiştir. Bunun nedeni ise uygulamaya göre circular buffer içerisinde char, float, işaretli/işaretsiz int verilerini tür bağımsız bir şekilde tutabilmektir. Hatta bu tasarım ile sadece primitive tipleri değil kullanıcı tanımlı veri tiplerini de bu buffer içerisinde tutabilmemiz mümkündür. C’de bu tarz yapıları generic olarak yazmanın yolu benim de bu tasarımda yaptığım gibi void işaretçiler kullanarak yapmaktır.
Yukarıdaki tasarımda sadece ilklendirme aşamasında dinamik bellek yönetimi tercih edilmiştir. Çalışma zamanında (runtime) herhangi bir dinamik bellek yönetimi yapılmamaktadır. Dinamik bellek yönetimi hiç kullanılmak istenmiyor ise maksimum bir nesne sayısı ve circular buffer havuzu oluşturularak bu tasarım sadece statik bellek yönetimi yapılacak şekilde güncellenebilir. Bunun için de circularBuffer veri yapısını ve init/destroy fonksiyonlarını aşağıdaki gibi güncellememiz gerekmektedir.
Bazı tasarımlarda circular buffer dolduğunda eski verinin üzerine yeni verinin yazılması veya kapasitenin reallocation yapılarak daha büyük yeni bir kapasiteye getirilmesi gibi aksiyonlar alınabilmektedir. Yukarıdaki iki farklı tasarımda da circular buffer dolduğu zaman buffer’dan veri okunarak yeni gelen verilere yer açılması kullanıcı sorumluluğundadır.
Bu tasarımları gerçek gömülü sistemlerde üretici görevden tüketici göreve tamponlamış veri pompalamız gereken her senaryoda kullanabiliriz. Gerçek zamanlı işletim sistemlerinde bu tarz amaçlar için geliştirilmiş hazır araçlar bulunmaktadır. Örneğin FreeRTOS içerisinde Stream Buffer, Message Buffer ve Queue araçları bu amaç için kullanılmaktadır.
Bu yazıda bahsi geçen tasarımlara aşağıdaki Github reposu üzerinden ulaşabilirsiniz.
https://github.com/serbayozkan/GenericCircularBuffer_C
Diğer yazılarımda görüşmek üzere…
Referanslar ve Faydalı Kaynaklar
