io_uring için kilitsiz MPSC FIFO kuyrukları geliyor

Linux çekirdeğinin io_uring alt sistemi, bekleyen iş öğelerini takip etmek için kullandığı genel kilitsiz tek yönlü bağlı liste (llist) yapısını, 7.2 çekirdek sürümüyle birlikte özel bir kilitsiz çok-üretici/tek-tüketici (MPSC) kuyruğuna taşıyor. Jens Axboe tarafından gönderilen ve Dmitry Vyukov'a ait bir algoritmaya dayanan bu değişiklik, eski yaklaşımın yapısal verimsizliklerini ortadan kaldırıyor.

llist yalnızca baştan ekleme desteklediği için io_uring bunu fiilen bir yığın gibi kullanıyordu; bu da işlem öncesi FIFO sırasını geri yüklemek için ekstra bir ters çevirme geçişi ve bir toplu işlem kesildiğinde ters çevrilmiş ama işlenmemiş öğeleri tutmak için ikinci bir liste gerektiriyordu. Öğe eklemek de karşılaştır-ve-değiştir tekrar döngülerine dayanıyordu; bu da yoğun çok-üretici yükü altında cache-line çekişmesine yol açıyordu.

Yeni mpscq yapısı, üreticilerin tek bir atomik xchg() işlemiyle, hiçbir tekrar döngüsü olmadan kuyruğun sonuna ekleme yapmasını sağlıyor; boş liste durumunu ise bir "stub" nöbetçi düğüm yönetiyor. Tüketici tarafı, üreticilerle yanlış paylaşımı en aza indirmek için kendi cache line'ında ayrı bir baş işaretçisi tutuyor ve öğeleri herhangi bir yeniden sıralama adımına gerek kalmadan gerçek geliş sırasına göre işliyor.

Mühendisler için bu, hedeflenmiş kilitsiz veri yapılarının yüksek verimli, yüksek eşzamanlılıklı G/Ç yollarında genel çekirdek ilkellerinden nasıl daha iyi performans gösterebileceğine dair somut bir örnek ve Vyukov MPSC kuyruğu algoritmasının üretim çekirdek kodundaki okunabilir bir vaka çalışması niteliğinde.