Linux kilitlenme kavramını, gerekli koşulları, önleme yöntemleri-bankacı algoritmasını ayrıntılı olarak açıklayın
Genel Bakış
Bugün, temel olarak, kilitlenmenin bazı nedenlerini ve koşullarını, bankacıların algoritmasını ve önleme yöntemlerini tanıtacağım. Bankacılar hakkında konuşmak istiyorsanız, önce kilitlenme sorunundan bahsetmelisiniz, çünkü bankacı algoritması kilitlenmeyi önlemek için önerilmiştir. Öyleyse, kilitlenme nedir? Basit bir örnek: iki kişi köfte yiyor, bir kişi elinde soya sosu tutuyor, bir kişi elinde sirke tutuyor ve soya sosunu tutan kişi sirkeyi tutan kişiye "Bana sirkeyi ver, ben de sana soya sosunu vereyim" diyor. ; Sirke sahibi, soya sosunu tutan kişiye: "Hayır, bana soya sosunu ver, ben sana sirke vereceğim." Dedi.
Dolayısıyla bu iki kişi asla iki sosu yemeyecek. Bu bir çıkmazdır.
01
Kilitlenmenin nedenleri ve gerekli koşulları
1. Kilitlenme kavramı
Genel olarak, eğer aynı iş parçacığı iki kez kilit çağrısı yaparsa, ilk çağrıda kilit zaten dolu olduğundan, iş parçacığı diğer iş parçacıklarının kilidi açmasını beklerken kilitlenecektir, ancak kilit kendisi tarafından işgal edilmiştir. İş parçacığı tekrar askıya alınır, kilidi açma şansı yoktur, bu nedenle kilitlenme (Deadlock) olarak adlandırılan her zaman askıda bekleme durumundadır. Diğer bir tipik kilitlenme durumu şudur: iplik A, kilit 1'i alır, iplik B, kilit 2'yi alır. Bu sırada, iplik A, kilit 2'yi almaya çalışmak için kilidi çağırır. Sonuç olarak, telefonu kapatması ve kilit 2'yi serbest bırakması için iplik B'yi beklemesi gerekir. İplik B ayrıca kilit 1'i elde etmeye çalışmak için kilidi çağırır. Sonuç olarak, askıya alması ve A ipliğinin kilidi 1 bırakmasını beklemesi gerekir, böylece A ve B dişleri sonsuza kadar askıda kalır.
Kilitlenme
Sözde çıkmaz, çalışan süreçte (DeadlyEmbreace) kaynaklar için yarışan birden fazla iş parçacığının neden olduğu bir çıkmaza (DeadlyEmbreace), yani birbirini bekleme olgusuna işaret eder.İşlikler bu çıkmazda olduğunda, dış güç yoksa, yapamazlar. İleri.
2. Kilitlenmenin nedeni
(1) Kaynaklar için rekabet etmek. Sistemdeki yazıcılar, genel kuyruklar vb. Gibi birden çok iş parçacığı tarafından paylaşılan kaynakların sayısı iş parçacıklarının ihtiyaçlarını karşılamak için yetersiz olduğunda, iş parçacıklarının kaynaklar için rekabet etmesine ve kilitlenmeye neden olur.
(2) İplikler arasındaki ilerleme sırası geçersizdir. Bir iş parçacığı çalışırken, kaynakları isteme ve serbest bırakmanın uygun olmayan sırası da iş parçacığı kilitlenmesine neden olabilir.
Aşağıda, kilitlenmenin nedenlerinin ayrıntılı bir analizi yer almaktadır:
(1) Kaynaklar için rekabet, kilitlenmeye neden olur
1) Yoksunluk ve yoksun bırakmama kaynakları
Sistem kaynakları iki kategoriye ayrılabilir: Biri yoksun kaynaklardır, yani bir iş parçacığı bu tür kaynakları aldıktan sonra, iş parçacığı diğer iş parçacıkları veya sistem tarafından yoksun bırakılabilir. Örneğin, yüksek önceliğe sahip bir iş parçacığı, kaynakları düşük önceliğe sahip bir iş parçacığından mahrum bırakabilir. Başka bir örnek, iş parçacıkları arasında geçiş yapmaktır. Diğer tür, yoksun bırakmayan kaynaklardır Sistem bu tür kaynakları bir iş parçacığına ayırdığında, zorla kurtarılamaz ve yalnızca teyp sürücüleri ve yazıcılar gibi kullanıldıktan sonra serbest bırakılabilir.
2). Mahrumiyet dışı kaynaklar için rekabet
Sistemde yapılandırılan yoksun bırakmayan kaynaklar, sayıları iş parçacıkları ihtiyaçlarını karşılayamadığı için, iş parçacıklarının çalışan süreç sırasında bu kaynaklar için rekabet nedeniyle kilitlenmesine neden olacaktır.
3). Geçici kaynaklar için rekabet
Yazıcı kaynakları sırayla yeniden kullanılabilir kaynaklardır ve kalıcı kaynaklar olarak adlandırılır. Sözde geçici kaynaklar, kısa bir süre için iş parçacıkları tarafından kullanıldıktan sonra yararsız olan kaynaklara atıfta bulunur, bu nedenle bunlara aynı zamanda kilitlenmelere neden olabilecek sarf malzemesi kaynakları da denir.
(2). Uygun olmayan iplik ilerletme sırasından kaynaklanan kilitlenme
Başlangıçta bahsedildiği gibi, iplik A, kilit 1 elde edildi ve iplik B, kilit 2'yi aldı. Bu anda, iş parçacığı, kilit 2'yi almaya çalışmak için kilidi çağırır. Sonuç olarak, kapatması ve B iş parçacığının kilidi 2'yi serbest bırakması için beklemesi gerekir. Kilit 1, sonuç, askıya almanız ve A dişlisinin kilidi 1'i serbest bırakmasını beklemeniz gerektiğidir, böylece A ve B dişleri her zaman askıya alınmış durumda olacaktır.
3. Kilitlenme için gerekli koşullar
İş parçacığı, çalışan işlem sırasında kilitlenebilir, ancak kilitlenme de belirli koşulları karşılamalıdır. Özetle, kilitlenme oluşumunun aşağıdaki dört gerekli koşulu karşılaması gerektiğini görmek zor değildir.
(1) Karşılıklı dışlama koşulu: Tahsis edilen kaynakların evreler tarafından özel olarak kullanılması, yani belirli bir kaynağın belirli bir süre içinde yalnızca bir iş parçacığı tarafından işgal edilmesi anlamına gelir. Şu anda kaynağı isteyen başka iş parçacıkları varsa, istekte bulunan kişi yalnızca kaynağı kullanan iş parçacığı serbest bırakılıncaya kadar bekleyebilir.
(2). İstek ve saklama koşulları: iş parçacığının en az bir kaynak tuttuğunu, ancak yeni bir kaynak isteğinde bulunduğunu ve kaynak başka iş parçacıkları tarafından işgal edildiğini veya kaynağın zaten sahip olduğu ancak şu anda yeniden talep edildiğini ifade eder İş parçacığı engellendi, ancak hala elde ettiği kaynakları elinde tutuyor.
(3) Yoksun bırakmama koşulu: İpliğin kullanılmadan önce edindiği kaynakları ifade eder, yoksun bırakılamaz ve ancak tükendiğinde kendiliğinden serbest bırakılabilir.
(4) Döngü bekleme koşulu: Bir kilitlenme meydana geldiğinde, bir iplik kaynağı dairesel zincir olmalıdır, yani iplik setindeki P0 {P0, P1, P2, P3, ... Pn} P1'i bekliyor İşgal edilen kaynaklar; P1, P2 tarafından işgal edilen kaynakları bekliyor, ..., Pn, P0 tarafından işgal edilen kaynakları bekliyor.
4. Kilitlenme ile başa çıkmanın temel yöntemi
Sistemdeki dişlerin normal çalışmasını sağlamak için, kilitlenmeleri önlemek için önceden gerekli önlemler alınmalıdır. Sistemde kilitlenme oluştuktan sonra zaman içinde düşünce oluşumu tespit edilmeli ve kilitlenmeyi gidermek için uygun önlemler alınmalıdır. Şu anda, kilitlenmelerle başa çıkma yöntemleri aşağıdaki dörtte özetlenebilir:
(1). Kilitlenmeyi önleyin. Bu nispeten basit ve sezgisel bir yöntemdir. Bu yöntem, kilitlenme için gerekli dört koşuldan birini veya birkaçını ortadan kaldırmak için belirli kısıtlamalar koyarak kilitlenmeyi önlemektir. Ancak, uygulanan kısıtlamalar genellikle çok katıdır ve bu da düşük sistem kaynağı kullanımı ve sistem verimi ile sonuçlanır.
(2) Çıkmazdan kaçının. Bu yöntem aynı zamanda bir ön önleme stratejisidir, ancak kilitlenmeler için dört gerekli koşulu ortadan kaldırmak için önceden çeşitli kısıtlayıcı önlemlerin alınması gerekmez, ancak dinamik kaynak tahsisi sürecinde, sistemin girmesini önlemek için belirli bir yöntem kullanılır. Kilitlenmeyi önlemek için güvensiz durum. Bu yöntemin yalnızca daha yüksek kaynak kullanımı ve sistem verimi elde etmek için önceden daha zayıf kısıtlamalar getirmesi gerekir, ancak aslında bazı zorlukları vardır. Şu anda bu yöntem, kilitlenmeyi önlemek için daha eksiksiz sistemlerde yaygın olarak kullanılmaktadır.
(3). Kilitlenmeyi tespit edin. Bu yöntemin önceden herhangi bir kısıtlayıcı önlem alması veya sistemin güvenli olmayan bir alana girip girmediğini kontrol etmesi gerekmez, ancak sistemin çalışma sırasında kilitlenmesine izin verir. Bununla birlikte, sistem tarafından belirlenen algılama mekanizması, zaman içinde kilitlenme oluşumunu algılayabilir ve kilitlenme ile ilgili iş parçacıkları ve kaynakları doğru bir şekilde belirleyebilir ve ardından kilitlenmeyi sistemden kaldırmak için uygun önlemleri alabilir.
(4) Kilitlenmeyi kaldırın. Bu, kilitlenmenin tespit edilmesiyle bağlantılı bir önlemdir. Sistemde bir kilitlenme olduğu tespit edildiğinde, iş parçacığı kilitlenme durumundan çıkarılmalıdır. Yaygın olarak kullanılan uygulama yöntemi, bazı kaynakları geri kazanmak için bazı iş parçacıklarını iptal etmek veya askıya almak ve daha sonra bu kaynakları zaten engellenmiş durumda olan iş parçacıkları için tahsis etmek ve ardından çalışmaya devam etmek için hazır duruma getirmektir. Kilitlenme tespiti ve kaldırma önlemleri, sistemin daha iyi kaynak kullanımı ve verimi elde etmesini sağlayabilir ancak aynı zamanda uygulanması en zor olanıdır.
02
Kilitlenmeyi önlemenin yolları
Kilitlenmeyi önlemenin yöntemi, kilitlenmeyi önlemek için dört gerekli koşulun ikinci, üçüncü ve dördüncü koşullarından birini tutmamaktır. Gerekli koşul 1'e gelince, ekipmanın kendine özgü özellikleri tarafından belirlendiği için, yalnızca değiştirilemez, aynı zamanda garanti edilmelidir.
1. "İste ve beklet koşulları" nı terk edin
Bu yöntemi benimserken, sistem tüm iş parçacıklarının çalıştırmaya başlamadan önce tüm işlem boyunca ihtiyaç duydukları tüm kaynaklar için tek seferde başvurmaları gerektiğini şart koşar.
Avantajlar: basit, uygulaması kolay ve güvenli
Dezavantajlar: kaynaklar ciddi şekilde boşa harcanır, iş parçacığı çalışması gecikir
2. "Yoksun bırakmama" koşulunu terk edin
Bu yöntemi benimserken, sistem iş parçacıklarının kaynaklar için gereksinimleri tek tek ortaya koymasını şart koşar. Belirli kaynakları ayıran bir iş parçacığı yeni bir kaynak isteğinde bulunduğunda ve hemen karşılanamadığında, ayırdığı tüm kaynakları serbest bırakmalı ve daha sonra gerektiğinde tekrar başvurmalıdır.
Bu yöntemin uygulanması daha karmaşıktır ve büyük bir bedel ödemelidir. Ve sürecin yürütülmesini süresiz olarak ertelemek mümkündür, bu da sistem ek yükünü artırır ve sistem verimini azaltır.
3. "Döngü bekleme" koşulunu terk edin
Bu yöntem, sistemin tüm kaynakları türe göre doğrusal olarak sıraladığını ve farklı seri numaraları atadığını öngörür.
Avantajlar: kaynak kullanımı ve sistem verimi önemli ölçüde iyileştirildi
Dezavantajlar: (1) Kaynağın seri numarası nispeten sabit olmalıdır ve bu da yeni ekipman türlerinin artışını sınırlar
(2) Kullanıcıların basit ve bağımsız programlamasını kısıtlayın.
(3). Kaynakları israf edecek
Ek: Bankanın Algoritması
Kilitlenme önleme algoritmaları arasında en temsili algoritma, 1968'de Dijkstra E.W tarafından önerilen banker algoritmasıdır:
Bankerin algoritması, kilitlenmeleri önlemek için önemli bir yöntemdir.Kilitlenmeyi önleyen kurumlar, yalnızca yukarıdaki dört durumdan birinin oluşmamasını sağlayabilir ve sistem kilitlenmeyecektir. Bu algoritma, banka kredileri gibi hayattaki pratik sorunları çözmek için kullanılabilir.
Bu algoritmaya neden bankacılar algoritması deniyor? Çünkü bu algoritma banka kredisi işi için kullanılabilir. Aşağıdaki durumu düşünün.
Bir bankacının 2 milyar varlığı var
İlk geliştirici: 1.5 milyar ödünç verildi, ancak sıkı fonlar nedeniyle hala 300 milyona ihtiyaç var.
İkinci geliştirici: 500 milyon kredi verdi ve iyi çalışırsa kurtarılabilir.
Üçüncü geliştirici: 1,8 milyar kredi vermek istiyor
Bu durumda bankacıysanız bu durumla nasıl başa çıkıyorsunuz? Geleneksel bir fikir, ikinci geliştiricinin parayı geri almasını beklemek ve ardından elinde 500 milyon olmak, ardından ilk geliştiriciye 300 milyon kredi vermek ve ilk geliştiricinin iyileşmesini beklemektir. Milyar ve sonra parayı üçüncü bir geliştiriciye ödünç verin.
Bunda öğrenmeye değer nedir? En önemli şey biraz daha uzun bakmak, sadece ne kadar paranız olduğuna bakmakla kalmayın, aynı zamanda başkalarının size borçlu olduğu parayı nasıl geri alabileceğinize de dikkat edin.
Başlangıçta bahsettiğimiz ilk örnek: sirke ve soya sosu kaynaklardır ve köfte yiyen ikisi süreçlerdir ve bu örnekte: bankacılar kaynaklardır ve geliştiriciler süreçlerdir. İşletim sisteminde bellek, sabit disk gibi birçok işlemin arzuladığı kaynaklar vardır, peki bu kaynaklar "iflas" riskinden kaçınmak için onlara nasıl tahsis edilebilir?
Bankacı algoritması
Program gerçekleştirme fikirleri Bankacının algoritması, adından da anlaşılacağı gibi, bankanın kredi verme işinden gelmektedir. Birden fazla müşterinin kredi cirosu için belirli bir miktar anapara kullanılmalıdır. Bankacıların fonlarının dönmemesi için, her bir kredi için kullanılıp kullanılamayacağını incelemek gerekir. Bir süre içinde iade edin. İşletim sisteminde kaynak tahsis stratejileri çalışılırken benzer problemler vardır.Sistemdeki sınırlı kaynakların birden fazla süreç tarafından kullanılması gerekir.Elde edilen kaynaklarla yapılan sürecin, diğer süreçlerin kaynakları kullanması için sınırlı bir süre içinde kaynakları geri verebilmesini sağlamak gerekir. Kaynak ayrılmamışsa, sürecin kaynakları beklerken döndüğü ve işlemin çalışmaya devam edemediği bir kilitlenme meydana gelir.
Bir prosesin ihtiyaçlarını ve proses kontrolünde işgal ettiği kaynakları kaydedin Proses kontrol bloğu PCB "durumlarının" hazır, beklemede ve tamamlanmış olduğu varsayılır. Süreç bekleme durumundayken, sistemin sürecin mevcut kaynak talebini karşılayamayacağı anlamına gelir. "Toplam kaynak talebi", sürecin tüm yürütülmesi sırasında uygulanacak toplam kaynak miktarını belirtir. Açıktır ki, her bir sürecin toplam kaynak talebi, sistemin sahip olduğu toplam kaynak sayısını aşamaz ve bankanın kaynak tahsisi için algoritması kilitlenmeyi önleyebilir.
Daha fazla devop ve DBA içeriği daha sonra paylaşılacak, ilgilenen arkadaşlar buna dikkat edebilir!
