Linux çekirdeği süreç yönetiminde içsel bağlantılı listeleri kullanıyor

Linux işletim sistemi çekirdeği, süreçlerin ve bellek bloklarının takibinde yaygın olarak içsel bağlantılı liste (intrusive linked list) adı verilen veri yapılarını tercih ediyor. Klasik bağlantılı listelerin aksine bu yöntemde liste düğümü harici bir veri işaretçisi tutmak yerine doğrudan nesnenin kendi veri yapısının içine gömülüyor. Bu yaklaşım, her yeni eleman için fazladan bellek tahsisi yapma zorunluluğunu ortadan kaldırıyor ve önbellek kaçırma oranlarını düşürerek performans avantajı sağlıyor.

Linux çekirdeği genelinde bu yapı struct list_head tanımıyla çift yönlü dairesel bağlantılı liste şeklinde uygulanıyor. Çekirdek içindeki nesneler, bu liste düğümünün adresinden yola çıkarak container_of ve offsetof makroları aracılığıyla ana veri yapısının başlangıç adresini hesaplıyor. İstatistiksel analizlere göre çekirdekteki liste işlemlerinin yalnızca yüzde 6'sı gezinme amacıyla yürütülüyor ve bu gezinmelerin de yüzde 28'i ya boş listelerde ya da tek düğümlü yapılarda gerçekleşiyor. Bu nedenle içsel listeler, gezinme sıklığı düşük durumlar için ideal bir çözüm sunuyor.

Çekirdekte görev (task) olarak adlandırılan süreçler task_struct yapısı üzerinden bu listelere ekleniyor ve sistem init_task kök sürecinden başlayarak tüm süreci denetliyor. Yeni bir süreç çatallandığında bu liste RCU mekanizmasıyla güncelleniyor ve hazırda bekletme veya tüm süreçlere sinyal gönderme gibi genel işlemlerde liste taranıyor. Tekil süreçlere hızlı erişim gerektiğinde ise çekirdek, liste yerine sabit zamanlı arama sağlayan IDR sözlük yapılarını devreye sokuyor.