Ağ Çalışma Grubu

Yorum Talebi: 626
NIC #: 22161
Tarih: Mart 1974

L. Kleinrock (UCLA-NMC)
H. Opderbeck (UCLA-NMC)

Mesaj Sıralaması Nedeniyle IMP Alt Ağında Olası Bir Kilitlenme Durumu Üzerine

Kilitlenme ya da karşılıklı kilitlenme durumları, bir bilgisayar sistemi veya ağda ortaya çıkabilecek en ciddi sistem arızalarından biridir. İletişim protokollerinin, bu tür kilitlenmelerin meydana gelmesini önlemek amacıyla son derece dikkatli biçimde tasarlanması gerekir. Ortak özellikleri, yalnızca olağandışı koşullar altında ortaya çıkmalarıdır; bu koşullar protokol tasarımcıları tarafından ya öngörülmemiştir ya da meydana gelmesi çok düşük olasılıklı kabul edilmiştir. (Ancak, bu tasarımcılar çoğu zaman bu tür olasılıkları nicel olarak değerlendirebilecek konumda değildir.)

ARPANET’te meydana gelmiş en bilinen kilitlenme, yeniden birleştirme kilitlenmesidir [1]. Yine Kaynak 1’de tanımlanan depola-ve-ilet kilitlenmesi, yeni IMPSYS’te Kahn’ın sezgisel kurallarına [1] dikkatle uyulması sayesinde önlenmiştir. Bildiğimiz kadarıyla alt ağda meydana gelen son kilitlenme 21 Aralık 1973’te gerçekleşmiştir ("Noel kilitlenmesi"). Bu uyku hâlindeki kilitlenme durumu, tüm sitelerden eşzamanlı olarak anlık ölçüm mesajlarının toplanmasıyla ortaya çıkarılmıştır. Noel kilitlenmesi, UCLA IMP’sine, kendileri için yeniden birleştirme depolama alanı ayrılmış olan ve boş yeniden birleştirme blokları bulunmayan anlık görüntü mesajlarının ulaşmasıyla meydana gelmiştir. (Yeniden birleştirme bloğu, paketlerin yeniden mesajlara dönüştürülmesi sürecinde kullanılan bir depolama alanıdır) [2].

Karşılıklı kilitlenme durumları yalnızca alt ağda değil, daha üst seviye protokollerde de gözlemlenmiştir. Örneğin ICP’nin özgün tasarımında, ancak birkaç aylık kullanım sonrasında keşfedilen bir kusur bulunmaktaydı [3,4]. Daha yakın zamanda BBN, RSEXEC sunucusu (RSSER) programları tarafından HOST durum bilgilerinin değişimini içeren bir karşılıklı kilitlenme problemi bildirmiştir [5].

Karşılıklı kilitlenme içermeyen çalışmayı garanti eden pratik iletişim protokolleri tasarlamak mümkün olmadığı sürece, hâlihazırda kullanımda olan protokollerin bu tür hatalar açısından sürekli olarak denetlenmesi hayati önem taşır — ortaya çıkmaları "çok düşük olasılıklı" görünse bile. Bu RFC’de, bildiğimiz kadarıyla henüz meydana gelmemiş ve tanımlanmamış olan, IMP alt ağındaki olası bir karşılıklı kilitlenme durumu hakkında yorum yapıyoruz. Bu problemin gerçekten gerçekleştiğini hiç görmemiş olsak da, herhangi bir önlem alınmazsa gelecekte ortaya çıkabilir. Bu olası kilitlenme durumu, alt ağdaki mesajların sıralanmasından kaynaklanmaktadır.

Yeniden birleştirme kilitlenmesinin ortaya çıkmasını önlemek için, alt ağdaki akış denetimi mekanizması bazı önemli yönlerden değiştirilmiştir. Güncel durumda, herhangi bir kaynak ve hedef IMP çifti arasında aynı anda iletimde bulunabilecek mesaj sayısı dörtten fazla olamaz. Eski IMPSYS’teki bağlantı yönetiminin kaldırılmasının bir sonucu olarak, bir mesaj sıralama mekanizmasının tanıtılması gerekli hâle gelmiştir.

Mesajlar, kaynak IMP’ye girdikleri sırayla hedef IMP’den çıkarlar. (Sıralamanın HOST’tan HOST’a değil, IMP’ten IMP’ye temelinde yapıldığına dikkat edilmelidir. Bu durum, aynı hedef IMP’ye bağlı iki HOST’un, aynı kaynak IMP’den mesaj alması hâlinde istenmeyen bir "sıralama gecikmesi"ne yol açabilir.)

Mesajların sıralanması, genel olarak karşılıklı kilitlenme koşullarını ortaya çıkarma potansiyeline sahiptir. Bunun nedeni şudur: Sırası bozulmuş olan (ve bu nedenle hedef HOST’a teslim edilemeyen) herhangi bir mesaj, örneğin mesaj (n+1), sıradaki mesaj olan (n) tarafından gerekli duyulan kaynakları tüketebilir. Bu durumda mesaj (n) hedef IMP’ye ulaşamaz; bu da sırası bozuk olan diğer mesajların (n+1 vb.) hedef HOST(lar)a teslim edilmesini engeller. Bu nedenle, sırası bozuk mesajlara çok fazla kaynak (örneğin arabellek) tahsis edilmemesine büyük özen gösterilmelidir.

Kilitlenme durumlarını önlemek için mevcut IMPSYS aşağıdaki iki önlemi almaktadır:

1. Arabellek tahsisi talepleri her zaman mesaj numarası sırasına göre karşılanır; yani mesaj (n) (ya da mesaj (n) için bir arabellek tahsisi talebi) henüz alınmamış ve işlenmemişse, mesaj (n+1) için hiçbir ALLOCATE geri gönderilmez.

2. Hedef IMP’ye sırası bozuk olarak ulaşan tek paketli mesajlar (normal ve öncelikli), önceki bir arabellek tahsisine yanıt olarak yeniden iletilmedikleri sürece kabul edilmez. Bu mesajlar, daha ziyade (yukarıdaki 1’e göre) bir arabellek tahsisi isteği olarak değerlendirilir ve ardından atılır.

Bu iki önlemle birlikte, bir karşılıklı kilitlenme durumunun ortaya çıkması imkânsız gibi görünmektedir. Ancak, mesaj sıralamasına bağlı olmayan ikinci bir arabellek tahsisi mekanizması daha vardır; bu da çok paketli bir mesaj için RFNM üzerine eklenen ALLOCATE’tir. Bu ekli ALLOCATE, sıradaki mesaj için değil, sıradaki çok paketli mesaj için bir arabellek tahsisini temsil eder. Dolayısıyla, sıralamadaki bir sonraki mesaj tek paketli bir mesaj ise, ekli ALLOCATE fiilen sırası bozuk bir mesaja arabellek tahsis etmiş olur.

Bu durumun nasıl bir karşılıklı kilitlenmeye yol açabileceğini görelim. Her IMP’de en fazla 24 yeniden birleştirme arabelleği bulunduğunu varsayalım.

IMP A, B ve C’nin, aynı hedef IMP D’ye sürekli olarak 8 paketli mesajlar gönderdiğini ve bu çok paketli mesaj iletimi sonucunda IMP D’deki 24 yeniden birleştirme arabelleğinin tamamının kullanıldığını varsayalım. Eğer şimdi, 8 paketli mesaj akışı içinde, IMP A tek paketli bir mesaj gönderirse, genellikle hedef IMP D tarafından kabul edilmeyecektir; çünkü kullanılabilir yeniden birleştirme arabelleği alanı yoktur. (Tek paketli mesaj, üç adet 8 paketli mesajdan birinin HOST’una iletildiği zaman aralığında ulaşırsa, boş bir yeniden birleştirme arabelleği bulunabilir.) Bu nedenle tek paketli mesaj bir arabellek tahsisi isteği olarak ele alınacaktır. Bu istek, önceki çok paketli mesajın RFNM’si gönderilmeden önce karşılanmayacaktır. Ancak bu noktada, tüm boş yeniden birleştirme arabellekleri, ekli ALLOCATE mekanizması yoluyla bir sonraki çok paketli mesaja zaten tahsis edilmiştir. Tek paketli mesajın tahsis isteğinin karşılanabilmesi için tek olasılık, diğer iki 8 paketli mesajdan birinden bir yeniden birleştirme arabelleğini kapmaktır. Bu girişim, IMP içindeki olayların zamanlamasına bağlı olduğundan başarısız olabilir.

Eğer IMP B ve IMP C de, aynı nedenle karşılanamayan tek paketli birer mesajı kendi 8 paketli mesaj akışları içinde gönderirse, bir karşılıklı kilitlenme durumu ortaya çıkabilir. Bu durumda, daha sonra IMP D’ye ulaşacak olan üç adet 8 paketli mesaj, sıraları bozuk olduğu için hedef HOST(lar)a teslim edilemez. Buna karşılık, sırada teslim edilmesi gereken üç tek paketli mesaj, kullanılabilir yeniden birleştirme alanı bulunmadığından hedef IMP’ye asla ulaşamaz.

Karşılıklı kilitlenme durumuna yol açan olası bir olay dizisi aşağıdaki gibi tanımlanabilir:

Gösterim için Örnekler

• Olay: A8 arrives → IMP A’dan gelen 8 paketli mesajın tüm 8 paketi IMP D’ye ulaşmıştır
• Olay: C1 arrives → IMP C’den gelen tek paketli bir mesaj IMP D’ye ulaşmıştır (ve bir arabellek tahsisi isteği olarak değerlendirilir)
• Olay: B8 complete → IMP B’den gelen 8 paketli mesajın son paketi hedef HOST tarafından alınmıştır
• Olay: A8 RFNM/ALL → ekli ALLOCATE içeren bir RFNM, IMP A’ya gönderilir

Yeniden Birleştirme Arabelleği Tahsis Tablosu

A1, B1 ve C1 tek paketli mesajlarından herhangi biri için bir ALLOCATE’in, sırasıyla kaynak IMP A, B ve C’ye, ancak önceki 8 paketli mesaj için (ekli ALLOCATE içeren) RFNM gönderildikten sonra geri döndürülebileceğine dikkat edilmelidir. Eğer bu RFNM’ler, arada tek paketli mesajlardan biri için bir ALLOCATE olmaksızın, ardışık olarak gönderilirse, geçici olarak serbest bırakılan yeniden birleştirme depolama alanı (7–9 numaralı olaylar), tek paketli mesajlardan hiçbirine değil, örtük biçimde bir sonraki çok paketli mesajlara (10–12 numaralı olaylar) tahsis edilmiş olur. Ancak sonraki 8 paketli mesajlar sırası bozuk durumdadır ve hedef HOST(lar)a teslim edilemez.

Şu an için, böyle bir kilitlenmenin yalnızca yeniden birleştirme arabelleği sayısının sekizin katı olduğu durumlarda ortaya çıkabileceği görülmektedir. Gerçekten de, bu durumda kilitlenme olasılığı çok daha yüksektir. Ancak, yeniden birleştirme arabelleği sayısı sekizin katı olmasa bile karşılıklı kilitlenmeler meydana gelebilir.

24 yerine 26 yeniden birleştirme arabelleği bulunduğunu varsayalım. Ayrıca, alternatif yollar, hat arızası ya da yeniden iletim nedeniyle, 2 paketli bir mesajın ikinci paketinin, aynı kaynak IMP A’dan gelen tek paketli bir mesajdan önce IMP D’ye ulaştığını varsayalım. Tek paketli mesaj daha küçük bir sıra numarasına sahiptir ve bu nedenle 2 paketli mesajdan önce hedef HOST’a teslim edilmelidir. 2 paketli mesajın ikinci paketi IMP D’ye ulaştığında, IMP ayrılmış 8 arabellekten yalnızca 2’sinin gerekli olduğunu fark eder. Bu nedenle 6 arabellek, boş yeniden birleştirme arabelleği havuzuna geri verilir. Eğer havuzda önceden 26 − 3×8 = 2 arabellek bulunuyorsa, havuz boyutu 6 artarak 8 arabelleğe çıkar. Ancak bu 8 arabellek, bir başka ekli ALLOCATE göndermek için tam olarak yeterlidir. Bu nedenle tek paketli mesaj, toplam yeniden birleştirme arabelleği sayısı sekizin katı olmasa bile, boş yeniden birleştirme arabelleği havuzunu boş bulacaktır. 2 paketli mesaj, sırası bozuk olduğu için hedef HOST’a teslim edilemez. Dolayısıyla, daha önce tanımladığımız karşılıklı kilitlenme durumu yeniden ortaya çıkabilir.

Yukarıda belirtilen olay dizisinin meydana gelme olasılığının düşük olduğu konusunda hemfikiriz (aksi hâlde muhtemelen şimdiye kadar gözlemlenmiş olurdu). Bu durum, özellikle mevcut en yüksek yeniden birleştirme arabelleği sayısının (58) 24’ten çok daha büyük olması nedeniyle geçerlidir. Ancak bilgisayar sistemleri ve ağlarla ilgili geçmiş deneyimlerimize dayanarak, çok düşük olasılıklı olayların bile uzun vadede gerçekleşme eğilimi gösterdiğini biliyoruz. Ayrıca, ağdaki trafik arttıkça bu karşılıklı kilitlenme durumunun olasılığı da artmaktadır. Bu nedenle, IMPSYS’in bu kilitlenmenin ortaya çıkamayacağı şekilde değiştirilmesi kesinlikle değerlidir. Görülmektedir ki, küçük bir değişiklik bile istenen etkiyi sağlamaktadır. Tanımlanan kilitlenmenin yalnızca tek ve çok paketli mesajların aynı yeniden birleştirme arabelleği havuzunu kullanması nedeniyle ortaya çıkabildiğini hatırlayalım. Yalnızca tek paketli mesajlar tarafından kullanılabilecek tek bir yeniden birleştirme arabelleği (ya da her hedef HOST için bir tane) ayırırsak, mesaj sıralamasından kaynaklanan bu kilitlenme durumu ortaya çıkamaz.

Bu probleme yönelik bir diğer çözüm elbette mesaj sıralamasını IMP düzeyinden HOST düzeyine taşımaktır. Bu, benzer kilitlenme problemlerinin HOST düzeyinde ortaya çıkamayacağı anlamına gelmez. Ayrıca, şu anda bu problemi IMPSYS’te yapılacak küçük bir değişiklikle çözmek, çeşitli HOST’ların tümünü koordine etmekten çok daha kolaydır. Bir başka alternatif de çok paketli mesajların kullanımını sonlandırmaktır. Ancak bu seçenek, dikkatli değerlendirme gerektiren çok daha köklü değişiklikleri beraberinde getirir.

Kaynaklar

1. Kahn, R. E., ve W. R. Crowther, Flow Control in a Resource-Sharing Computer Network, IEEE Transactions on Communication, Cilt COM-20, No. 3, Haziran 1972.
2. BBN Raporu No. 2717, Interface Message Processors for the ARPA Computer Network, Üç Aylık Teknik Rapor No. 4, Ocak 1974.
3. Naylor, W., J. Wong, C. Kline ve J. Postel, Regarding Proffered Official ICP, RFC 143, NIC 6728.
4. Postel, J. B., A Graph Model Analysis of Computer Communications Protocols, Doktora tezi, University of California, Los Angeles.
5. BBN Raporu No. 2670, Natural Communication with Computers IV, Üç Aylık İlerleme Raporu No. 12, Ekim 1973.