--- title: 'Çizelgeleme Algoritmaları' source: 'https://academia.sh/tr/kurslar/isletim-sistemi-kavramlari/cizelgeleme-algoritmalari' course: 'İşletim Sistemi Kavramları' language: tr updated: '2026-08-17T18:08:22+00:00' license: 'CC BY-SA 4.0' --- # Çizelgeleme Algoritmaları Dört çizelgeleyici, aynı iş yükü: önalımsız sıra 194, dilimli 197, öncelikli 195, adil paylaşımlı 192 zaman birimi veriyor; dilim 4'ten 1'e indiğinde süre 206'ya, bağlam değiştirme 36'ya çıkıyor, ikinci iş yükünde sıralama değişiyor ve iki iş yükünde de en iyi olan hiçbir yordam bulunmuyor. Önceki dört ders yürütme birimlerinin nasıl kurulduğunu ölçtü: kaç adres uzayı, kaç kopyalanan sayfa, kaç etkilenen birim. Kurulum bittiğinde geriye her zaman biriminde yeniden sorulan tek bir soru kalır — hazır birimlerden hangisi koşacak. Bu kararı veren bileşen **çizelgeleyicidir (scheduler)** ve kararın nasıl verildiği ölçülebilir bir farktır. Bu ders aynı beş süreçlik iş yükünü dört ayrı yordamla koşturur, sonra aynı karşılaştırmayı ikinci bir iş yükünde yineler. Dersin sonucu tek bir yordamın seçilmesi değildir; **hiçbir yordamın her iş yükünde en iyi olmadığının** gösterilmesidir. - **SR31.** Çizelgeleyici her zaman biriminde hazır birimlerden birini seçer. Hazır olmayan birim, bekleme adımındadır ve seçilemez. - **SR32.** **Önalımsız sıra**, bir süreci bitene ya da bir bekleme adımına girene kadar bırakmaz; hazır olanlar arasında **en erken hazır olanı** seçer. - **SR33.** **Dilimli** yordam **önalımlıdır**: bir süreç en çok **4 zaman birimi** koşar, sonra çekirdeği bırakır. Bu süreye **zaman dilimi**, kısaca **dilim** denir. - **SR34.** **Öncelikli** yordam en yüksek öncelikli hazır süreci seçer; öncelikler iş yükünün parçasıdır ve ikinci iş yükünde farklıdır. - **SR35.** **Adil paylaşımlı** yordam, o ana kadar **en az çekirdek kullanmış** hazır süreci seçer. - **SR36.** Ölçülen büyüklükler: **süre** (bütün işin bitmesine kadar geçen zaman birimi), **bağlam değiştirme sayısı**, **boş çekirdek adımı**, **ortalama tamamlanma süresi** (varıştan bitişe) ve **ortalama bekleme** (hazır ama koşamadığı zaman birimi). - **SR37.** İkinci iş yükü tohumu **20260219**'dur. Aynı beş süreç yapısı, farklı adım bileşimi ve farklı öncelikler verir. - **SR38.** Çözünürlük **2 zaman birimidir**. İki yordam arasındaki 1 birimlik fark **ölçülmemiş sayılır** ve sıralamaya girmez. ## İki İş Yükü İki tohum aynı yapıyı üretir ama farklı bir bileşim verir. Fark, hesap adımı ile bekleme adımı arasındaki dağılımdadır ve çizelgeleyicilerin davranışını belirleyen şey tam olarak budur. ```python # Bu makine bir BENZETICIDIR. Hicbir gercek cizelgeleyici cagrilmaz; butun # sureler modeldeki zaman birimidir. TOHUM = 20260218 IKINCI_TOHUM = 20260219 SUREC_SAYISI = 5 ADIM_SAYISI = 12 BEKLEME_SURESI = 30 BAGLAM_BEDELI = 2 SANAL_SAYFA = 16 def uretec(tohum): """Belirlenimci sozde-rastgele uretec. Ayni tohum ayni diziyi verir.""" d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def is_yuku(tohum=TOHUM): """Bir adim ya ("HESAP", sanal_sayfa) ya da ("BEKLE", sure).""" r = uretec(tohum) isler = [] for i in range(SUREC_SAYISI): adimlar = [] for _ in range(ADIM_SAYISI): if r(10) < 3: adimlar.append(("BEKLE", BEKLEME_SURESI)) else: taban = (i * 3) % SANAL_SAYFA adimlar.append(("HESAP", (taban + r(4)) % SANAL_SAYFA)) isler.append({"ad": f"S{i+1}", "adim": adimlar, "oncelik": 1 + r(3), "varis": i * 4}) return isler ISLER = is_yuku() print("is yuku hesap adimi bekleme adimi oncelikler") for tohum in (TOHUM, IKINCI_TOHUM): y = is_yuku(tohum) h = sum(1 for i in y for t, _ in i["adim"] if t == "HESAP") print(f"{tohum} {h:10d} {SUREC_SAYISI * ADIM_SAYISI - h:13d}" f" {[i['oncelik'] for i in y]}") ``` ``` is yuku hesap adimi bekleme adimi oncelikler 20260218 39 21 [3, 2, 1, 3, 2] 20260219 46 14 [1, 2, 3, 1, 1] ``` İkinci iş yükü **daha hesap ağırlıklıdır**: 60 adımın 46'sı çekirdeği tutar, ilkinde bu sayı 39'du. Bu, çizelgeleyici için daha zor bir iştir, çünkü çekirdek için çekişen süreç sayısı artmıştır. Öncelikler de değişmiştir ve tek bir sürecin önceliği 3'tür. ## Dört Yordam, Aynı İş Yükü Aşağıdaki gerçeklenim dört yordamı tek gövdede toplar. Aralarındaki tek fark iki satırdır: hazır kümesinden hangisinin seçildiği ve bir sürecin dilimini doldurup doldurmadığına bakılıp bakılmadığı. ```python # Ilk blogun uzerine: ISLER ve BAGLAM_BEDELI oradan gelir. SONSUZ = 10**9 def cizelgele(isler, yordam="sirayla", dilim=4, cekirdek=1, baglam_bedeli=BAGLAM_BEDELI): """yordam: sirayla (onalimsiz) | dilimli | oncelikli | adil Her zaman biriminde her cekirdek en cok bir adim yurutur.""" durum = [{"ad": i["ad"], "adim": list(i["adim"]), "yer": 0, "varis": i["varis"], "hazir": i["varis"], "kullanim": 0, "bitis": None, "oncelik": i["oncelik"]} for i in isler] pay_siniri = SONSUZ if yordam == "sirayla" else dilim cekirdekler = [{"surec": None, "onceki": None, "pay": 0, "engel": 0} for _ in range(cekirdek)] t, baglam, bos_adim = 0, 0, 0 def bitmedi(d): return d["yer"] < len(d["adim"]) while any(bitmedi(d) for d in durum) or any(d["bitis"] is None or d["bitis"] > t for d in durum): for c in cekirdekler: # birakma d = c["surec"] if d is not None and (not bitmedi(d) or d["hazir"] > t or c["pay"] >= pay_siniri): c["surec"] = None for c in cekirdekler: # atama if c["engel"] or c["surec"] is not None: continue tutulan = [x["surec"] for x in cekirdekler if x["surec"] is not None] hazir = [d for d in durum if bitmedi(d) and d["hazir"] <= t and d not in tutulan] if not hazir: continue if yordam == "oncelikli": sec = min(hazir, key=lambda d: (-d["oncelik"], d["hazir"], d["ad"])) elif yordam == "adil": sec = min(hazir, key=lambda d: (d["kullanim"], d["hazir"], d["ad"])) else: sec = min(hazir, key=lambda d: (d["hazir"], d["ad"])) if c["onceki"] is not None and c["onceki"] is not sec: baglam += 1 c["engel"] = baglam_bedeli c["surec"] = sec c["onceki"] = sec c["pay"] = 0 for c in cekirdekler: # yurutme if c["engel"]: c["engel"] -= 1 continue d = c["surec"] if d is None: bos_adim += 1 continue tur, deger = d["adim"][d["yer"]] if tur == "BEKLE": d["yer"] += 1 d["hazir"] = t + deger c["surec"] = None bos_adim += 1 if not bitmedi(d): # son adim beklemeyse is o zaman biter d["bitis"] = t + deger else: d["yer"] += 1 d["kullanim"] += 1 d["hazir"] = t + 1 c["pay"] += 1 if not bitmedi(d): d["bitis"] = t + 1 c["surec"] = None t += 1 for d, i in zip(durum, isler): gc = sum(v for tur, v in i["adim"] if tur == "BEKLE") d["bekleme"] = d["bitis"] - d["varis"] - d["kullanim"] - gc return {"sure": t, "baglam": baglam, "bos_cekirdek_adimi": bos_adim, "toplam_is": sum(d["kullanim"] for d in durum), "ortalama_tamamlanma": round(sum(d["bitis"] - d["varis"] for d in durum) / len(durum), 2), "ortalama_bekleme": round(sum(d["bekleme"] for d in durum) / len(durum), 2), "bitis": {d["ad"]: d["bitis"] for d in durum}} YORDAM = ("sirayla", "dilimli", "oncelikli", "adil") print("cizelgeleyici sure baglam bos.cek ort.tamamlanma ort.bekleme") for y in YORDAM: s = cizelgele(ISLER, y) print(f" {y:12s} {s['sure']:4d} {s['baglam']:5d} {s['bos_cekirdek_adimi']:6d}" f" {s['ortalama_tamamlanma']:13.2f} {s['ortalama_bekleme']:10.2f}") print() print("dilim supurmesi (dilimli)") print("dilim sure baglam ort.bekleme") for d in (1, 2, 4, 8, 16): s = cizelgele(ISLER, "dilimli", dilim=d) print(f"{d:5d} {s['sure']:4d} {s['baglam']:5d} {s['ortalama_bekleme']:11.2f}") ``` ``` cizelgeleyici sure baglam bos.cek ort.tamamlanma ort.bekleme sirayla 194 22 111 148.40 14.60 dilimli 197 25 108 153.80 20.00 oncelikli 195 21 114 149.00 15.20 adil 192 25 103 153.00 19.20 dilim supurmesi (dilimli) dilim sure baglam ort.bekleme 1 206 36 33.00 2 202 29 26.60 4 197 25 20.00 8 194 22 14.60 16 194 22 14.60 ``` Dört yordamın süreleri 192 ile 197 arasındadır; aralarındaki en büyük fark **5 zaman birimidir**, yani toplam sürenin yüzde 2,6'sı. Bu, önemli bir okumadır: **çizelgeleyici seçimi bu iş yükünde büyük bir kaldıraç değildir.** Asıl belirleyici, iş yükünün kendi bekleme adımlarıdır ve onlar 630 zaman birimi tutar. Önalımlı yordam, önalımsız sıradan **3 zaman birimi** daha uzun sürer ve 3 bağlam değiştirme fazla yapar. Ortalama bekleme 14,60'tan 20,00'a çıkar. Dilimlemenin sağladığı şey — hiçbir sürecin çekirdeği uzun süre tutamaması — süreyle ödenir. ## Dilim Küçüldükçe Kötüleşir Süpürme bu ödemenin doğrudan ölçüsüdür. Dilim 4'ten 1'e indiğinde süre 197'den **206**'ya, bağlam değiştirme 25'ten **36**'ya, ortalama bekleme 20,00'dan **33,00**'a çıkar. Her adımda çekirdeği bırakmak, adımların kendisinden çok bağlam değiştirmeye zaman harcamak demektir: 36 geçiş 72 zaman birimi tutar ve iş yükünün toplam hesap adımı 39'dur. Öteki uçta süpürme durur. Dilim 8 ile dilim 16 **tıpatıp aynı** sonucu verir: 194, 22, 14,60. Bunun nedeni açıktır — bu iş yükünde hiçbir süreç art arda sekizden fazla hesap adımı yürütmez, dolayısıyla dilim 8'in üstünde önalım hiç tetiklenmez. **Bu iş yükünün çözünürlüğü dilim 8'de tükenir**; daha büyük dilimlerle yapılan bir karşılaştırma yeni bilgi vermez. Dilim 8'deki 194 ve 22, önalımsız sıranın sayılarının tıpatıp aynısıdır ve olması gereken de budur: önalımın hiç tetiklenmediği bir dilimli yordam, önalımsız yordamdır. ## Toplam Süre Neyi Gizler Toplam süre tek başına bakıldığında dört yordam birbirine yakın durur. Yordamların birbirinden ayrıldığı yer toplam değil, **dağılımdır**: aynı 192 ile 197 arasındaki süre, süreçler arasında çok farklı biçimlerde bölüşülebilir. ```python # Onceki bloklarin uzerine: ISLER, cizelgele ve YORDAM. print("cizelgeleyici S1 S2 S3 S4 S5 en genis fark") for y in YORDAM: s = cizelgele(ISLER, y) t = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER] print(f" {y:12s} " + " ".join(f"{x:4d}" for x in t) + f" {max(t) - min(t):13d}") print() print("oncelik 3 olan surecler:", [i["ad"] for i in ISLER if i["oncelik"] == 3]) print("oncelik 1 olan surecler:", [i["ad"] for i in ISLER if i["oncelik"] == 1]) for y in ("sirayla", "oncelikli"): s = cizelgele(ISLER, y) yuksek = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER if i["oncelik"] == 3] dusuk = [s["bitis"][i["ad"]] - i["varis"] for i in ISLER if i["oncelik"] == 1] print(f"{y:10s} yuksek oncelik ort. {sum(yuksek) / len(yuksek):6.2f}" f" | dusuk oncelik ort. {sum(dusuk) / len(dusuk):6.2f}") ``` ``` cizelgeleyici S1 S2 S3 S4 S5 en genis fark sirayla 103 112 176 173 178 75 dilimli 111 120 175 185 178 74 oncelikli 103 112 187 169 174 84 adil 127 115 170 180 173 65 oncelik 3 olan surecler: ['S1', 'S4'] oncelik 1 olan surecler: ['S3'] sirayla yuksek oncelik ort. 138.00 | dusuk oncelik ort. 176.00 oncelikli yuksek oncelik ort. 136.00 | dusuk oncelik ort. 187.00 ``` Son sütun adil paylaşımlı yordamın ne yaptığını gösterir: en hızlı ve en yavaş sürecin tamamlanma süreleri arasındaki fark 65 zaman birimidir, dört yordamın en darı. Öncelikli yordamda aynı fark **84**'tür, en genişi. Adaletin ölçüsü toplam süre değil bu farktır ve adil paylaşımlı yordam onu 19 birim daraltır. Öncelikli yordamın kime ne kazandırdığı ayrıca sayılabilir. Önceliği 3 olan iki süreç, önalımsız sırada ortalama 138,00 zaman biriminde biterken öncelikli yordamda 136,00'da biter: **2 zaman birimi**, yani çözünürlüğün tam sınırında bir kazanç. Önceliği 1 olan süreç ise 176,00'dan 187,00'a geriler — **11 zaman birimi** kayıp. Öncelik vermek, kayırılanlara ölçülemeyecek kadar az kazandırıp kayırılmayana ölçülebilir bir bedel ödetir. ## Sıralama İkinci İş Yükünde Ayakta Kalıyor mu Tek bir iş yükünde ölçülmüş bir sıralama, o iş yüküne ait bir olgudur. Sonucun bir kural olabilmesi için ikinci bir iş yükünde de sınanması gerekir. ```python # Onceki bloklarin uzerine: is_yuku, cizelgele, YORDAM ve IKINCI_TOHUM. SONUC = {y: [cizelgele(is_yuku(t), y)["sure"] for t in (TOHUM, IKINCI_TOHUM)] for y in YORDAM} EN_IYI = [min(SONUC[y][k] for y in YORDAM) for k in (0, 1)] print("cizelgeleyici 20260218 fark 20260219 fark") for y in YORDAM: a, b = SONUC[y] print(f" {y:12s} {a:8d} {a - EN_IYI[0]:5d} {b:9d} {b - EN_IYI[1]:5d}") print() for k, tohum in enumerate((TOHUM, IKINCI_TOHUM)): en_iyi = [y for y in YORDAM if SONUC[y][k] == EN_IYI[k]] en_kotu = [y for y in YORDAM if SONUC[y][k] == max(SONUC[z][k] for z in YORDAM)] print(f"{tohum}: en iyi {en_iyi} | en kotu {en_kotu}") print("iki is yukunde de en iyi olan:", [y for y in YORDAM if SONUC[y][0] == EN_IYI[0] and SONUC[y][1] == EN_IYI[1]]) print("cozunurluk altinda kalan cift (fark < 2):", [(y, z, k) for k in (0, 1) for i, y in enumerate(YORDAM) for z in YORDAM[i + 1:] if abs(SONUC[y][k] - SONUC[z][k]) < 2]) ``` ``` cizelgeleyici 20260218 fark 20260219 fark sirayla 194 2 189 0 dilimli 197 5 202 13 oncelikli 195 3 196 7 adil 192 0 195 6 20260218: en iyi ['adil'] | en kotu ['dilimli'] 20260219: en iyi ['sirayla'] | en kotu ['dilimli'] iki is yukunde de en iyi olan: [] cozunurluk altinda kalan cift (fark < 2): [('sirayla', 'oncelikli', 0), ('oncelikli', 'adil', 1)] ``` ## Hangi Sonuç Ayakta Kalır Çıktının son dört satırı bu dersin bütün iddialarını sınırlar. **Ayakta kalan sonuç: dilimleme adaleti süreyle ödetir.** Dilimli yordam **iki iş yükünde de en kötüdür** — ilkinde en iyiden 5, ikincisinde 13 zaman birimi geride. İkinci iş yükünde fark üç katına çıkar, çünkü hesap ağırlıklı bir iş yükünde önalım daha sık tetiklenir. Bu sonuç iki ölçümde de aynı yönde durur ve yazılabilir. **Ayakta kalmayan sonuç: adil paylaşımın üstünlüğü.** Adil paylaşımlı yordam ilk iş yükünde en iyidir, ikincisinde en iyiden 6 zaman birimi geridedir. Aynı yordam bir iş yükünde birinci, ötekinde değildir; dolayısıyla **"adil paylaşım en iyisidir" cümlesi ölçülmemiş bir iddiadır ve kurulamaz.** **İki iş yükünde de en iyi olan yordam listesi boştur.** Bu, dersin ana sonucudur: bir çizelgeleyicinin üstünlüğü kendisinin değil, **iş yükünün bileşiminin** özelliğidir. Önalımsız sıra hesap ağırlıklı ikinci iş yükünde birinciye çıkar, çünkü orada süreçlerin bekleme adımı azdır ve bölmeden koşturmak toplamı kısaltır. Son satır çözünürlüğün nasıl çalıştığını gösterir. İlk iş yükünde önalımsız sıra (194) ile öncelikli (195) arasındaki 1 birim, ikinci iş yükünde öncelikli (196) ile adil paylaşımlı (195) arasındaki 1 birim çözünürlüğün altındadır. Bu çiftler **ayrılmaz**; aralarında bir sıralama yazmak, ölçülmemiş bir farkı ölçülmüş gibi sunmak olur. ## Özet - Çizelgeleyici, her zaman biriminde hazır birimlerden hangisinin koşacağına karar verir; dört yordam bu kararı önalım ve seçim ölçütü bakımından farklı verir. - Aynı iş yükünde dört yordamın süresi 192 ile 197 arasındadır; en büyük fark 5 zaman birimi, yani yüzde 2,6'dır. Çizelgeleyici seçimi bu iş yükünde büyük bir kaldıraç değildir. - Dilim küçüldükçe kötüleşir: dilim 1'de süre 206, bağlam değiştirme 36, ortalama bekleme 33,00 olur. Dilim 8 ile 16 aynı sonucu verir; bu iş yükünün çözünürlüğü dilim 8'de tükenir. - Dilimli yordam **iki iş yükünde de en kötüdür** (197 ve 202); dilimleme adaleti süreyle ödetir ve bu sonuç iki ölçümde de ayaktadır. - İki iş yükünde de en iyi olan yordam **yoktur**: adil paylaşımlı ilkinde birinci, önalımsız sıra ikincisinde birincidir. Üstünlük yordamın değil, iş yükünün bileşiminin özelliğidir. - Çözünürlük altındaki 1 birimlik farklar ölçülmemiş sayılır; iki çift bu nedenle ayrılmaz kalır ve aralarına sıralama yazılmaz. ## Sonraki Adım Bu konu boyunca birimler birbirinden ayrı sayıldı: her biri kendi adımlarını yürütüyor, çizelgeleyici aralarında gidip geliyordu. Bir varsayım hiç sınanmadı — bir birimin adımı bölündüğünde sonucun değişmeyeceği varsayımı. Kursun sonraki konusu bu varsayımı bozar ve tek bir cümleyi kanıtlar: aynı programın iki birimi aynı veriye dokunduğunda **doğru çıktı doğru program demek değildir.**