როგორ მუშაობს CPU scheduling და რომელია გავრცელებული ალგორითმები?

Question

IT Interview Practice · Accepted Answer

**CPU scheduling** არის kernel-ის გადაწყვეტილება, თუ *რომელი* მზა thread იღებს CPU-ს *შემდეგ* და *რამდენ ხანს*. რადგან ჩვეულებრივ core-ებზე მეტი გამშვები thread არსებობს, **scheduler** ამრავალხაზოვნებს (multiplex) მათ, მიზნად ისახავს კონკურენტული მიზნების დაბალანსებას — **throughput**, **დაბალი latency / response time**, და **სამართლიანობა** — და ამავდროულად თავს არიდებს **starvation-ს**.

## გავრცელებული ალგორითმები

```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** ასახავს ძირითად სახელურს — **quantum-ს**:

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

## რეალური scheduler-ები

Linux-ის დიდი ხნის ნაგულისხმევი იყო **CFS (Completely Fair Scheduler)**: ფიქსირებული ნაჭრების ნაცვლად ის თვალს ადევნებს თითოეული task-ის **virtual runtime-ს (vruntime)** და ყოველთვის უშვებს thread-ს, რომელმაც აქამდე ყველაზე ცოტა CPU მიიღო, აწონილს მისი **nice** მნიშვნელობით — რაც აახლოებს „ყველა სამართლიან წილს იღებს"-თან. ის red-black tree-ს vruntime-ით ინდექსავს, ასე რომ შემდეგი task-ის არჩევა O(log n)-ია. (უფრო ახალი kernel-ები იყენებენ EEVDF-ს, დახვეწას იმავე სამართლიანობის მიზნით და უფრო მკაცრი latency-ის ზღვრებით.)

**Preemptive vs cooperative:** თანამედროვე OS-ები **preemptive-ია** — timer interrupt scheduler-ს საშუალებას აძლევს იძულებით დაიბრუნოს CPU, ასე რომ ერთ thread-ს არ შეუძლია core-ის მონოპოლიზება.

## რატომ არის ეს მნიშვნელოვანი

Scheduling პირდაპირ აყალიბებს latency-სა და throughput-ს, რომელსაც მომხმარებლები გრძნობენ. ინტერვიუერები ამ თემას ჩხრეკენ, რომ ნახონ, გესმით თუ არა ტრეიდ-ოფები — რატომ სურს ინტერაქტიულ workload-ს მოკლე quantum ან priority boost, რატომ სჭირდება priority scheduling-ს **aging**, რომ თავიდან აიცილოს starvation, და როგორ აღწევენ MLFQ/CFS კარგ ინტერაქტიულ ქცევას job-ების სიგრძის წინასწარ ცოდნის გარეშე. ეს ასევე გონებრივი მოდელია `nice`-ის, real-time priority-ების გამართვისა და მშიერი ან შემანელებელი service-ის დიაგნოსტიკის უკან.

გავრცელებული ალგორითმები

რეალური scheduler-ები

რატომ არის ეს მნიშვნელოვანი

დაკავშირებული კითხვები