CPU scheduling nasıl çalışır ve yaygın algoritmalar nelerdir?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling**, kernel'in *hangi* hazır thread'in CPU'yu *sonra* alacağına ve *ne kadar süreyle* alacağına dair kararıdır. Genellikle çekirdek sayısından daha çok çalışabilir thread olduğundan, **scheduler** bunları çoğullar (multiplex); birbiriyle çekişen hedefleri — **throughput**, **düşük latency / yanıt süresi** ve **adillik** — dengelemeyi amaçlarken **starvation**'dan (açlık) kaçınır.

## Yaygın algoritmalar

```text
FCFS (first-come, first-served) → simple, but one long job blocks everyone (convoy effect)
SJF  (shortest job first)       → optimal avg wait, but needs to know job length; can starve long jobs
Round-robin (RR)                → each job a fixed TIME SLICE (quantum), cycle through → fair, good latency
Priority                        → highest priority first → can STARVE low priority (fix: aging)
MLFQ (multi-level feedback)     → several priority queues; jobs that use a full quantum sink,
                                  interactive jobs that yield stay high → approximates SJF without knowing lengths
```

**Round-robin**, temel ayar düğmesini gösterir — **quantum**:

```text
quantum too SMALL → fair & responsive, but lots of context-switch overhead
quantum too LARGE → less overhead, but degrades toward FCFS (poor responsiveness)
```

## Gerçek scheduler'lar

Linux'un uzun süredir varsayılanı **CFS (Completely Fair Scheduler)** idi: sabit dilimler yerine her task'ın **virtual runtime (vruntime)** değerini izler ve **nice** değerine göre ağırlıklandırarak o ana dek en az CPU almış thread'i çalıştırır — "herkes adil bir pay alır" yaklaşımına yakınsar. Bir red-black tree'yi vruntime'a göre anahtarlar, dolayısıyla sıradaki task'ı seçmek O(log n)'dir. (Daha yeni kernel'ler, aynı adillik hedefine ek olarak daha sıkı latency sınırları sunan bir iyileştirme olan EEVDF'yi kullanır.)

**Preemptive vs cooperative:** modern OS'ler **preemptive**'tir — bir timer interrupt, scheduler'ın CPU'yu zorla geri almasını sağlar, böylece bir thread bir çekirdeği tekeline alamaz.

## Neden önemli

Scheduling, kullanıcıların hissettiği latency ve throughput'u doğrudan şekillendirir. Mülakatçılar, ödünleşimleri anlayıp anlamadığınızı görmek için bunu yoklar — etkileşimli bir iş yükünün neden kısa quantum ya da bir priority artışı istediğini, priority scheduling'in starvation'ı önlemek için neden **aging**'e ihtiyaç duyduğunu ve MLFQ/CFS'nin iş uzunluklarını önceden bilmeden nasıl iyi etkileşimli davranış elde ettiğini. Bu aynı zamanda `nice` ayarlamanın, real-time priority'lerin ve aç kalmış ya da takılan bir servisi teşhis etmenin arkasındaki zihinsel modeldir.

Yaygın algoritmalar

Gerçek scheduler'lar

Neden önemli

İlgili sorular