
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.
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:
- İ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.
- 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:
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
vruntimedeğ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
vruntimedeğ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
vruntimedeğ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_leftmostiş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
vruntimedeğeri güncellenir ve ağaca yeniden eklenir ($O(\log N)$ karmaşıklık). - Yeni
rb_leftmostbelirlenir 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:
- 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ı).
- 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:
cat /proc/$$/sched | grep -E "se.vruntime|se.exec_start|nr_switches"
Çıktı:
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:
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 tepkiFikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.
Ali Purtaş
@alipurtas • Hey, This is Ali!
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
copy_file_range ile Blok Katmanında Reflink Tabanlı Dosya Klonlama
copy_file_range sistem çağrısı, Btrfs ve XFS reflink mekanizması, blok seviyesinde anlık dosya klonlama ve gigabaytlarca veriyi kopyalamadan çoğaltma rehberi.
Linux sendfile ve splice Çağrılarıyla Çekirdek İçi Veri Aktarımı
Geleneksel G/Ç kopyalama maliyetleri, sendfile ve splice sistem çağrıları, boru tamponları üzerinden kullanıcı alanına inmeden sokete veri aktarma mimarisi.
Bellek Bariyerleri: x86 TSO ile ARM Zayıf Bellek Düzeni Farkları
x86 TSO modeli ile ARM gevşek bellek mimarisi karşılaştırması, hafıza bariyeri komutları ve lock-free kodların Graviton işlemcilerde çökme nedenleri analizi.
Tartışma & Yorumlar
0Tartışmaya katılmak ve soru sormak için oturum açmalısınız.
Giriş Yap