--- title: 'Kilitlenme ve Açlık' source: 'https://academia.sh/tr/kurslar/isletim-sistemi-kavramlari/kilitlenme-ve-aclik' course: 'İşletim Sistemi Kavramları' language: tr updated: '2026-08-17T18:08:18+00:00' license: 'CC BY-SA 4.0' --- # Kilitlenme ve Açlık Kilitlenmenin dört koşulu, bekleme çizgesinde döngü tespitiyle saptanması, sıralı edinimin yapısal önlemesi ve bunun bekleme adımı olarak bedeli. Önceki ders tek bir kilidin bedelini ölçtü ve sonucu tek bir eksende topladı: bekleme adımı. O eksende kötü bir sayı, yavaş bir programdır. Bu derste ikinci bir arıza türü çıkıyor ve o eksende **hiç** sayı üretmiyor: kilitlenen bir iş parçacığı yavaşlamaz, **durur**. İki kilit yetiyor. Bir iş parçacığı birinci kilidi tutup ikincisini isterken, başka bir iş parçacığı ikinciyi tutup birinciyi isterse ikisi de bir daha ilerlemez. Bu derste bu durumun ne zaman oluştuğu **sayılacak**, önlemenin yapısal biçimi kurulacak ve önlemenin bedeli ölçülecek. ## Dört Koşul **Kilitlenme (deadlock)** rastgele oluşmaz. Dört koşul **aynı anda** sağlandığında oluşur ve herhangi birinin kırılması onu imkânsız kılar. **Karşılıklı dışlama.** Kaynak paylaşılamıyor; bir anda tek iş parçacığı tutabiliyor. Bu koşul kaldırılırsa önceki dersin doğruluk güvencesi de gider. **Tut ve bekle.** Bir iş parçacığı elindekini bırakmadan yenisini istiyor. **Önalımsızlık.** Kilit zorla geri alınamıyor; ancak tutan bırakabiliyor. **Dairesel bekleme.** Bekleme ilişkisi bir halka oluşturuyor. **EZ14.** Bekleme çizgesinin düğümleri iş parçacıkları, kenarları "tutulan bir kilidi bekleme" ilişkisidir. **EZ15.** Bir kilidi aynı anda tek iş parçacığı tutar; istenen kilit boştaysa kenar yoktur. **EZ16.** Her iş parçacığı bir kilit tutar ve başka bir kilit ister; kilit bırakma zorlanamaz, tespit sonrası kurtarma modellenmez. İlk üç koşul çoğu programda tasarım gereği vardır. Kalan tek hedef **dairesel beklemedir** ve bu, çizge diliyle tam olarak **döngüdür**. ## Döngü Tespiti Yeni Bir Yordam Değildir Veri Yapıları kursunun derine arama dersi yönlü çizgede döngü tespitini kurdu ve oradaki ayrım burada aynen geçerlidir: "ziyaret edildi" ile "hâlâ açık" karıştırılmamalıdır. Ortak tanımın `dongu_var` yordamı bunu üç renkle taşır — 0 hiç görülmedi, 1 hâlâ açık, 2 dalı bitti. Yordam **tekrar kurulmaz**, doğrudan çağrılır. Aşağıdaki ölçü önce beş bekleme çizgesini sınıyor, sonra bir durum uzayını tarıyor. ```python from itertools import permutations, product def dongu_var(bekleme: dict[str, list[str]]) -> bool: """Yonlu cizgede dongu sinamasi. renk 1 = hala acik , renk 2 = dal bitti.""" renk = {d: 0 for d in bekleme} def gez(d): renk[d] = 1 for h in bekleme.get(d, []): if renk.get(h, 0) == 1: return True if renk.get(h, 0) == 0 and gez(h): return True renk[d] = 2 return False return any(renk[d] == 0 and gez(d) for d in list(bekleme)) for ad, cizge in (("kimse beklemiyor", {"T1": [], "T2": []}), ("zincir T1 -> T2", {"T1": ["T2"], "T2": []}), ("iki dal ortak hedef", {"T1": ["T3"], "T2": ["T3"], "T3": []}), ("halka T1 -> T2 -> T1", {"T1": ["T2"], "T2": ["T1"]}), ("halka T1 -> T2 -> T3", {"T1": ["T2"], "T2": ["T3"], "T3": ["T1"]})): print(f" {ad:22s} kilitlenme {dongu_var(cizge)}") def tara(kilit_sayisi: int, is_parcacigi: int, sirali: bool) -> tuple[int, int]: """Her is parcacigi bir kilidi tutar , baska bir kilidi ister. Butun durumlar.""" kilitler = list(range(1, kilit_sayisi + 1)) durum = kilitlenen = 0 for tutulan in permutations(kilitler, is_parcacigi): for istenen in product(kilitler, repeat=is_parcacigi): if any(t == i for t, i in zip(tutulan, istenen)): continue # kendi tuttugu kilidi istemez if sirali and any(i < t for t, i in zip(tutulan, istenen)): continue # sirali edinim: yalniz buyuk numara istenir sahip = {k: f"T{j+1}" for j, k in enumerate(tutulan)} cizge = {f"T{j+1}": [] for j in range(is_parcacigi)} for j, i in enumerate(istenen): if i in sahip: # istenen kilit bostaysa kenar yoktur cizge[f"T{j+1}"].append(sahip[i]) durum += 1 if dongu_var(cizge): kilitlenen += 1 return durum, kilitlenen print() print("4 kilit , her is parcacigi bir kilit tutup baska bir kilit istiyor") print(" is parcacigi edinim durum kilitlenen kilitlenme orani") for n in (2, 3, 4): for sirali in (False, True): d, k = tara(4, n, sirali) ad = "sirali " if sirali else "serbest" oran = f"{k / d:.4f}" if d else "durum yok" print(f" {n:12d} {ad} {d:8d} {k:10d} {oran:>16s}") ``` ``` kimse beklemiyor kilitlenme False zincir T1 -> T2 kilitlenme False iki dal ortak hedef kilitlenme False halka T1 -> T2 -> T1 kilitlenme True halka T1 -> T2 -> T3 kilitlenme True 4 kilit , her is parcacigi bir kilit tutup baska bir kilit istiyor is parcacigi edinim durum kilitlenen kilitlenme orani 2 serbest 108 12 0.1111 2 sirali 22 0 0.0000 3 serbest 648 264 0.4074 3 sirali 36 0 0.0000 4 serbest 1944 1944 1.0000 4 sirali 0 0 durum yok ``` Üçüncü satır ölçünün özüdür: dört kilit ve üç iş parçacığıyla **648** ayrı bekleme durumu kurulabiliyor ve bunların **264**'ü kilitli. Oran **0,4074**. İkinci dal önemlidir: iki iş parçacığında oran **0,1111** iken üçte **0,4074**, dörtte **1,0000** oluyor. Kilitlenme, iş parçacığı eklendikçe **istisna olmaktan çıkıp kural hâline geliyor**. Dört iş parçacığının dört kilidi tuttuğu satırdaki 1,0000 rastlantı değil. Her iş parçacığı bir kilit tutup başkasını istediğinde, "kimin kilidini bekliyorum" ilişkisi düğüm başına tek çıkışlı bir çizge kurar; sonlu ve çıkışsız düğüm içermeyen böyle bir çizge **her zaman** bir halka barındırır. ## Tespit ile Önleme Aynı Şey Değildir Yukarıdaki tarama bir **tespit** yordamıdır: durum verildiğinde kilitlenmiş olup olmadığını söyler. Çalışan bir sistemde bunu kullanmak üç şey ister. Bekleme çizgesinin **sürekli güncel tutulması**, çizgenin **düzenli aralıklarla taranması** ve döngü bulunduğunda bir iş parçacığının **geri alınması**. Tarama maliyeti Veri Yapıları kursunda ölçüldü ve $O(V + E)$'dir; burada tekrarlanmaz. Üçüncü adım en pahalısıdır. Geri almak, tutulan kilidi zorla söküp o iş parçacığının yaptığı işi iptal etmek demektir; yani **önalımsızlık koşulunun kırılmasıdır** ve iptal edilen iş yeniden yapılır. Bu ders o kurtarmayı modellemez (EZ16). Önleme ise koşum sırasında **hiçbir şey ölçmez ve hiçbir şey taramaz**. Bedelini tasarım anında öder: kilitlere bir sıra verilir ve bu sıraya her yerde uyulur. ## Sıralı Edinim Tabloda `sirali` satırlarının hepsinde kilitlenen **0**. Bu bir iyileştirme değil, **yapısal bir imkânsızlıktır** ve gerekçesi tek cümleyle verilebilir. **EZ17.** Kilitler sabit bir tam sıraya konur; her iş parçacığı kilitleri **yalnız artan numara sırasında** ister. Bir halka olduğunu varsayalım. Halkadaki her iş parçacığı, tuttuğundan **büyük** numaralı bir kilidi bekliyor demektir. Halka boyunca yürünürse numaralar sürekli artar; ama halka başladığı yere döner ve bir sayı kendinden büyük olamaz. Çelişki. Yani halka yoktur. Tablo bunu iki ayrı biçimde gösteriyor. Üç iş parçacığında durum uzayı **648**'den **36**'ya iniyor ve kalan 36 durumun **hiçbiri** kilitli değil. Dört iş parçacığında sıralı edinim altında **hiç durum kalmıyor** — o durum kurulamıyor bile. Buradaki 648'den 36'ya iniş, önlemenin bedelinin nerede olduğunu da söylüyor: **ortadan kaldırılan durumların çoğu kilitli değildi.** Sıralı edinim yalnız halkaları değil, birçok zararsız bekleme biçimini de yasaklar. ## Önlemenin Bedeli Yasaklanan zararsız durumlar bir yerde ödenir. İkinci kilidi isteyen bir iş parçacığı, sıraya uymak için birinci kilidi **erken almak** ve **elinde tutmak** zorundadır; iki ayrı kritik bölge tek bir bölgeye kaynar. **EZ18.** Serbest edinimde iki kaynağın iki ayrı kilidi vardır ve aynı anda iki iş parçacığı kritik bölgede olabilir; bu iki izinli bir sayan semaforla aynı sayıyı verir. Sıralı edinimde iki kilit iç içe tutulduğu için kritik bölge tektir. ```python def kilitli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int, izin: int = 1) -> dict: kalan = [{"kritik": kritik, "disi": kritik_disi} for _ in range(is_parcacigi)] icerde, t, bekleme, mesgul = [], 0, 0, 0 while any(k["kritik"] or k["disi"] for k in kalan): calisan = 0 for j, k in enumerate(kalan): if k["disi"]: k["disi"] -= 1 calisan += 1 continue if not k["kritik"]: continue if j in icerde or len(icerde) < izin: if j not in icerde: icerde.append(j) k["kritik"] -= 1 calisan += 1 if not k["kritik"]: icerde.remove(j) else: bekleme += 1 mesgul += calisan t += 1 return {"sure": t, "bekleme": bekleme, "mesgul": mesgul, "kullanim": round(mesgul / (t * is_parcacigi), 4)} print("iki kilit , kritik bolge toplam 10 adim , kritik disi 10 adim") print(" is parcacigi edinim izin sure bekleme kullanim") for n in (2, 4, 8): for ad, izin in (("serbest", 2), ("sirali ", 1)): k = kilitli_kosum(n, 10, 10, izin) print(f" {n:12d} {ad} {izin:4d} {k['sure']:4d} {k['bekleme']:7d}" f" {k['kullanim']:8.4f}") print() for n in (2, 4, 8): s = kilitli_kosum(n, 10, 10, 1)["sure"] - kilitli_kosum(n, 10, 10, 2)["sure"] b = kilitli_kosum(n, 10, 10, 1)["bekleme"] - kilitli_kosum(n, 10, 10, 2)["bekleme"] print(f" {n} is parcacigi -> sirali edinimin bedeli: sure +{s} , bekleme +{b}") ``` ``` iki kilit , kritik bolge toplam 10 adim , kritik disi 10 adim is parcacigi edinim izin sure bekleme kullanim 2 serbest 2 20 0 1.0000 2 sirali 1 29 9 0.6897 4 serbest 2 29 18 0.6897 4 sirali 1 47 54 0.4255 8 serbest 2 47 108 0.4255 8 sirali 1 83 252 0.2410 2 is parcacigi -> sirali edinimin bedeli: sure +9 , bekleme +9 4 is parcacigi -> sirali edinimin bedeli: sure +18 , bekleme +36 8 is parcacigi -> sirali edinimin bedeli: sure +36 , bekleme +144 ``` Dört iş parçacığında sıralı edinim süreyi **29'dan 47'ye**, bekleme adımını **18'den 54'e** çıkarıyor. Sekiz iş parçacığında fark daha da açılıyor: süre **47'den 83'e**, bekleme **108'den 252'ye**. Bedel iş parçacığı sayısıyla büyüyor — **+9, +18, +36**. Bu sayılar takas edilecek şeyi net kılar. Sıralı edinim kilitlenme olasılığını 0,4074'ten **0,0000**'a indiriyor; karşılığında sekiz iş parçacığında **144 fazla bekleme adımı** ödeniyor. Sıfır kilitlenme bir başarım kaybı karşılığında alınır ve bu takas sayılmadan savunulamaz. ## Açlık Kilitlenme, iş parçacıklarının **birlikte** durmasıdır. **Açlık (starvation)** ise bir iş parçacığının, sistem çalışmaya devam ederken sırasının hiç gelmemesidir. Kilitlenmenin aksine bekleme çizgesinde döngü yoktur; kilit sürekli veriliyordur, yalnız hep aynılara. **EZ19.** İş parçacıkları kritik bölgeyi **sürekli** ister; kritik olmayan işi bitirir bitirmez yeniden sıraya girer. **EZ20.** Kilit boşaldığında bekleyenlerden biri seçilir; seçim kuralı ya en küçük numaralı bekleyeni ya da en uzun bekleyeni alır. ```python def surekli_kosum(is_parcacigi: int, kritik: int, kritik_disi: int, sure: int, adil: bool) -> dict: """Kritik bolgeyi surekli isteyen is parcaciklari. Kilit , adil ise en uzun bekleyene , degilse en kucuk numarali bekleyene verilir.""" kalan = [0] * is_parcacigi # kritik bolgede kalan adim disi = [0] * is_parcacigi # kritik olmayan iste kalan adim istek = [0] * is_parcacigi # ne zamandir bekliyor tur = [0] * is_parcacigi # kac kez kritik bolgeye girdi icerde = None for t in range(sure): for j in range(is_parcacigi): if disi[j]: disi[j] -= 1 elif icerde != j: istek[j] += 1 if icerde is None: bekleyen = [j for j in range(is_parcacigi) if not disi[j]] if bekleyen: sec = max(bekleyen, key=lambda j: istek[j]) if adil else min(bekleyen) icerde, kalan[sec], istek[sec] = sec, kritik, 0 tur[sec] += 1 if icerde is not None: kalan[icerde] -= 1 if not kalan[icerde]: disi[icerde] = kritik_disi icerde = None return {"tur": tur, "acikta": istek} # acikta: son istekten beri beklenen adim print("4 is parcacigi , kritik 10 , kritik disi 10") print(" sure secim kurali tur dagilimi toplam tur acikta beklenen") for sure in (400, 4000): for adil in (False, True): s = surekli_kosum(4, 10, 10, sure, adil) ad = "adil " if adil else "en kucuk" print(f" {sure:4d} {ad} {str(s['tur']):20s} {sum(s['tur']):10d}" f" {s['acikta']}") ``` ``` 4 is parcacigi , kritik 10 , kritik disi 10 sure secim kurali tur dagilimi toplam tur acikta beklenen 400 en kucuk [20, 20, 0, 0] 40 [0, 0, 400, 400] 400 adil [10, 10, 10, 10] 40 [20, 10, 0, 0] 4000 en kucuk [200, 200, 0, 0] 400 [0, 0, 4000, 4000] 4000 adil [100, 100, 100, 100] 400 [20, 10, 0, 0] ``` Dört yüz zaman biriminde kritik bölgeye toplam **40** giriş oluyor — **her iki seçim kuralında da**. Verim aynı. Dağılım aynı değil: en küçük numaralı bekleyeni seçen kural girişleri `[20, 20, 0, 0]` biçiminde dağıtıyor. Üçüncü ve dördüncü iş parçacıkları **hiç girmiyor** ve **400 adım boyunca** açıkta bekliyor. Süre on katına çıkarıldığında sonuç değişmiyor: `[200, 200, 0, 0]`. Açıkta beklenen adım 400'den **4000**'e çıkıyor. Bu, kilitlenmeden farklı bir arızadır ve **beklemekle geçmez**; sınırı yoktur, süreyle büyür. Adil seçim kuralı aynı 40 girişi `[10, 10, 10, 10]` biçiminde dağıtıyor. Toplam verim değişmiyor, yani **adalet burada bedava geliyor**. Bedava gelmesinin nedeni kritik bölgenin zaten sıralanmış olmasıdır; ödenen bedel önceki derste çoktan ödendi. Bu ölçünün asıl uyarısı şudur: verim ölçütü açlığı **göremez**. Toplam tur sayısı iki kuralda da 40'tır; arızayı gören tek şey **dağılımdır**. ## Üç Sayı | Ölçüt | Soyutlamasız taban | Soyutlamalı kurulum | Bedel | |---|---|---|---| | Kilitlenen durum | tek kilit, **0** | dört kilit, üç iş parçacığı, **264/648** | oran 0,4074 | | Sıralı edinim sonrası | — | **0/36** | süre +18, bekleme +36 | | Açlık | tek iş parçacığı, **0** | dört iş parçacığı, adaletsiz seçim | 2 iş parçacığı, **4000** adım açıkta | Tablonun ikinci satırı kursun kuralını taşır: kilitlenmenin ortadan kalkması bir kazanç değil, bir **takastır**. Dört iş parçacığında 0,4074'lük kilitlenme oranı sıfırlanıyor ve karşılığında her iş parçacığı daha uzun bekliyor. ## Özet - Kilitlenme dört koşulun aynı anda sağlanmasıyla oluşur; pratikte kırılabilen tek koşul dairesel beklemedir ve bu, bekleme çizgesindeki döngüdür. - Döngü tespiti yeni bir yordam değildir; Veri Yapıları kursunun derine arama dersinde kurulan üç renkli sınama aynen çağrılır. - Dört kilit ve üç iş parçacığında 648 bekleme durumunun **264**'ü kilitlidir (0,4074); iş parçacığı sayısı arttıkça oran 0,1111'den 1,0000'e çıkar. - Sıralı edinim halkayı yapısal olarak imkânsız kılar — durum uzayı 648'den 36'ya iner ve kilitlenen sayısı **0** olur; bedeli sekiz iş parçacığında 144 fazla bekleme adımıdır. - Açlıkta döngü yoktur ve verim düşmez: 400 zaman biriminde toplam 40 giriş her iki seçim kuralında da aynıdır; arıza yalnız dağılımda görünür. ## Sonraki Adım Buraya kadar ölçülen her şey tek çekirdekte oldu; iş parçacıkları hiçbir zaman gerçekten aynı anda ilerlemedi. Sonraki ders bu kısıtı kaldırır. Çekirdek eklendiğinde süre 197'den 180'e iniyor, ama dördüncü çekirdek 179'da kalıyor ve boş çekirdek adımı 108'den 1355'e çıkıyor. Aynı derste birinci dersin dilim korumasının ne olduğu da görülecek: gerçek paralellikte erişilebilen serpiştirme yeniden 20'ye çıkar ve 18'i yanlış olur.