IAli
Tüm Yazılar
Linux CFS: vruntime Metriği ve Kırmızı-Siyah Ağaç Mimarisi Analizi

Linux CFS: vruntime Metriği ve Kırmızı-Siyah Ağaç Mimarisi Analizi

Completely Fair Scheduler vruntime hesabı, nice öncelik ağırlık tablosu, kırmızı-siyah ağaç kuyruk yönetimi ve çekirdek seviyesinde adil CPU paylaştırma.

İşletim sistemi çekirdeğinin en temel ve büyüleyici görevi, sınırlı sayıdaki fiziksel CPU çekirdeğini aynı anda çalışmak isteyen yüzlerce hatta binlerce süreç arasında paylaştırmaktır. Linux 2.6.23 sürümünden Linux 6.5 sürümüne kadar bu devasa görevin omurgasını Ingo Molnar tarafından tasarlanan Tamamen Adil Zamanlayıcı (Completely Fair Scheduler - CFS) oluşturmuştur.

Geleneksel zamanlayıcılar sabit zaman dilimleri (time slices) tahsis ederken, CFS ideal bir çoklu görev bilgisayarını (Ideal Multi-tasking Hardware) simüle etmeye çalışır. Bu rehberde CFS mimarisinin kalbini oluşturan sanal çalışma süresi (vruntime) metriğini, sched_prio_to_weight ağırlık dizisini, kırmızı-siyah ağaç (red-black tree) algoritmasını ve Cgroups v2 ve CFS Kotası ile olan doğrudan bağını inceliyoruz.

TEXT
CFS Kırmızı-Siyah Ağaç Mimarisi ve rb_leftmost Seçimi:

                   cfs_rq (Çalışma Kuyruğu)
                             │
                             ▼
                    [ Düğüm: vruntime = 140 ms ]
                           /            \
                          /              \
           [ Düğüm: vruntime = 90 ms ]    [ Düğüm: vruntime = 190 ms ]
                 /            \
                /              \
       [ Düğüm: 40 ms ]   [ Düğüm: 110 ms ]
            ▲
            │ (rb_leftmost)
    EN KÜÇÜK VRUNTIME
    (CPU'YA İLK SEÇİLECEK SÜREÇ)

1. O(1) Zamanlayıcıdan CFS'e Neden Geçildi?

Linux 2.6'nın ilk yıllarında kullanılan Ingo Molnar'ın O(1) zamanlayıcısı, süreçleri 140 öncelik seviyesine göre ayrılmış iki ayrı dizi (active ve expired) içinde tutuyordu. Sürecin zaman dilimi bittiğinde expired dizisine taşınıyor, active dizisi boşaldığında dizilerin işaretçileri takas ediliyordu.

O(1) zamanlayıcı matematiksel olarak sabit zamanda çalışsa da iki temel soruna sahipti:

  1. İnteraktif Süreç Sezgisi (Heuristics): Bir sürecin fare/klavye gibi etkileşimli mi yoksa arka plan hesaplaması mı olduğunu anlamak için karmaşık uyku süresi formülleri kullanılıyordu. Bu sezgiler multimedya, ses ve 3D oyunlarda takılmalara yol açıyordu.
  2. Sabit Zaman Dilimi Adaletsizliği: Nice değerine göre atanan sabit milisaniyeler (örneğin 100 ms veya 5 ms), süreç sayısı arttıkça genel sistem gecikmesini öngörülemez hale getiriyordu.

CFS bu karmaşık sezgileri çöpe attı. Prensip basitleştirildi: Her sürece eşit CPU hakkı ver. En az CPU kullanan süreci bir sonraki adımda çalıştır.

2. vruntime (Virtual Runtime) Metriği ve Matematiksel Formülü

CFS'te her görevin çalışma geçmişi vruntime (sanal çalışma süresi) adı verilen 64 bitlik bir tamsayı ile nanasaniye cinsinden tutulur.

Bir süreç CPU üzerinde $\Delta\text{exec}$ süresi kadar fiziksel olarak çalıştığında, sanal çalışma süresi şu formülle güncellenir:

$$\text{vruntime}{\text{yeni}} = \text{vruntime}{\text{eski}} + \Delta\text{exec} \times \left( \frac{\text{NICE_0_LOAD}}{\text{weight}} \right)$$

Burada:

  • $\Delta\text{exec}$: Sürecin CPU üzerinde gerçekten geçirdiği fiziksel nanasaniye süresi.
  • $\text{NICE_0_LOAD}$: Nice değeri 0 olan standart bir sürecin taban ağırlığı (sabit değer: 1024).
  • $\text{weight}$: Sürecin nice önceliğine karşılık gelen çekirdek ağırlık değeri.

sched_prio_to_weight Ağırlık Tablosu

Linux çekirdek kaynak kodunda (kernel/sched/core.c) nice değerleri -20 ile +19 arasında değişir. Bu değerler çekirdekte şu statik dizi ile temsil edilir:

C
const int sched_prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* -15 */ 29154, 23254, 18705, 14949, 11916,
    /* -10 */  9548,  7620,  6100,  4904,  3906,
    /*  -5 */  3121,  2501,  1991,  1586,  1277,
    /*   0 */  1024,   820,   655,   526,   423,
    /*   5 */   335,   272,   215,   172,   137,
    /*  10 */   110,    87,    70,    56,    45,
    /*  15 */    36,    29,    23,    18,    15,
};

Bu tablodaki geometrik oran yaklaşık yüzde 1.25'tir (her 1 nice adımı yaklaşık yüzde 10 daha fazla CPU zamanına karşılık gelir).

Örnek Hesap:

  • Süreç A (Nice 0, Ağırlık 1024): 10 ms çalıştığında formül gereği vruntime değeri tam 10 ms artar: $$\Delta\text{vruntime} = 10 \times (1024 / 1024) = 10,\text{ms}$$
  • Süreç B (Nice -5, Yüksek Öncelik, Ağırlık 3121): 10 ms çalıştığında vruntime değeri yalnızca 3.28 ms artar: $$\Delta\text{vruntime} = 10 \times (1024 / 3121) \approx 3.28,\text{ms}$$

Süreç B fiziksel olarak aynı süre çalışmasına rağmen sanal süresi çok daha yavaş ilerler. Dolayısıyla kuyrukta geride kalır ve CPU'ya çok daha sık seçilir.

3. Kırmızı-Siyah Ağaç (Red-Black Tree) Kuyruk Mimarisi

Çalışmaya hazır (runnable) süreçler, çekirdeğin çalışma kuyruğunda (cfs_rq) bir kırmızı-siyah ağaç (struct rb_root_cached tasks_timeline) üzerinde tutulur.

Ağacın sıralama anahtarı (key) süreçlerin vruntime değeridir:

  • En küçük vruntime değerine sahip süreç ağacın en solundaki yaprak düğümdür (leftmost node).
  • Çekirdek bir sonraki çalıştırılacak süreci seçerken ağacı baştan aşağı aramaz. rb_leftmost işaretçisini doğrudan okur ($O(1)$ karmaşıklık).
  • Seçilen süreç CPU üzerinde bir süre çalışır. Fiziksel süresi dolduğunda vruntime değeri güncellenir ve ağaca yeniden eklenir ($O(\log N)$ karmaşıklık).
  • Yeni rb_leftmost belirlenir ve döngü kesintisiz devam eder.

Eğer bir süreç I/O beklemek için uykuya dalarsa (örneğin disk okuması yaparken) ağaçtan çıkarılır. Uyandığında haksız bir avantaj elde edip tüm CPU'yu tekeline almasın diye vruntime değeri kuyruğun o anki taban sanal zamanı (cfs_rq->min_vruntime) seviyesine eşitlenir.

4. Zamanlama Gecikmesi ve Granülerlik Parametreleri

CFS'in davranışını yöneten iki temel çekirdek parametresi vardır:

  1. sysctl_sched_latency (Hedef Gecikme): Çalışmaya hazır tüm süreçlerin en az bir kez CPU yüzü görmesi gereken hedef zaman penceresidir (varsayılan: 6 ms ile 24 ms arası).
  2. sysctl_sched_min_granularity (Minimum Dilim): Bir sürecin CPU'dan zorla indirilmeden önce kesintisiz çalışmasına izin verilen en küçük süredir (varsayılan: 0.75 ms ile 3 ms arası). Bu sınır aşırı bağlam değişimini (context switch trashing) engeller.

Süreç sayısı $N$ arttığında, eğer $N \times \text{min_granularity} > \text{sched_latency}$ haline gelirse, hedef gecikme doğrusal olarak esnetilir.

5. Üretim Ortamında CFS İzleme ve Analiz

Sisteminizdeki süreçlerin vruntime ve zamanlama istatistiklerini canlı olarak incelemek için /proc/[pid]/sched dosyasını okuyabilirsiniz:

Bash
cat /proc/$$/sched | grep -E "se.vruntime|se.exec_start|nr_switches"

Çıktı:

TEXT
se.vruntime                                  :       1428901.819204
se.nr_migrations                             :                   12
nr_switches                                  :                  481
nr_voluntary_switches                        :                  420
nr_involuntary_switches                      :                   61

Tüm CPU çekirdeklerinin zamanlayıcı durumunu görmek için:

Bash
cat /proc/sched_debug | grep -E "cfs_rq\[|min_vruntime" | head -n 12

CFS, saf adalet ilkesiyle genel sunucu iş yüklerinde büyük başarı sağlasa da, gecikme (latency) ile verim (throughput) ayrımını tek bir vruntime metriğine sıkıştırması nedeniyle Linux 6.6 ile yerini Linux 6.6 EEVDF Zamanlayıcısı mimarisine devretmiştir.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...