Geri Dön

Dağıtılmış sistemlerde ölümcül kilitlenme algoritmaları ve uygulanması

Deadlock algorithms and their applications in distributed systems

  1. Tez No: 83123
  2. Yazar: A. SEZGİN TEPE
  3. Danışmanlar: DOÇ. DR. TEVFİK AKGÜN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 1999
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 103

Özet

DAĞITILMIŞ SİSTEMLERDE OLUMCUL KİLİTLENME ALGORİTMALARI VE UYGULANMASI ÖZET Dağıtılmış sistemlerde özkaynak atama yöntemlerinin bir sonucu olarak ölümcül kilitlenmeler ortaya çıkabilir. Ölümcül kilitlenme, özkaynaklar için rekabet eden ya da birbirleri ile haberleşen bir görevler kümesinin sürekli engellenmesidir. Ölümcül kilitlenmeler, görevler arasındaki ilişkiyi belirten bekleme graflan ile modellenir. Bir sistemde ölümcül kilitlenme ortaya çıkması için dört şartın gerçekleşmesi gereklidir. Bir ölümcül kilitlenme oluştuktan sonra, istek modeline bağlı olarak bekleme grafinda bir çevrim veya düğüm kilitlenmeyi temsil eder. Kilitlenmeleri kotarmak için üç yöntem vardır. Kaçınma yöntemleri, görevlerin özkaynak kullanımları ile ilgili ön bilgi gerektirir. Bu bilgi yardımı ile özkaynak atamaları, ancak atama ilerde bir kilitlenme ile sonuçlanmayacak ise yapılır. Önleme yöntemleri, sistemin kilitlenmeleri imkansız kılacak şekilde tasarlanmasını sağlamaya çalışır. Bu şekilde, ölümcül kilitlenmenin dört şartından en az bir tanesi hiçbir zaman gerçekleşmez. Son yöntem, kilitlenmelerin oluşmasına izin veren sezme ve çözme yöntemidir. Bu durumda sistem, kilitlenmeleri sezmek amacıyla bilgi toplar ve daha sonra kilitlenme durumundan geri kazanımın sağlanması için gerekli çözülme işlemlerini gerçekleştirir. Sezme ve çözme algoritmaları sistemdeki özkaynak istek modelleri üzerine bazı varsayımlar yaparak, algoritmaların etkin bir şekilde tasarlanmasını sağlamışlardır. Sezme ve çözme algoritmaları sistem durum bilgisini tutmada başlıca üç yöntem uygulamaktadır. Merkezi yöntemde, tüm bilgi tek bir düğümde tutulmaktadır. Hiyerarşik yöntemde bilgi, bir hiyerarşi içinde kilitlenme denetçilerine dağıtılmıştır. Dağıtılmış yöntemde sistem bilgisi, aynı seviyede konumlanan ve birbirleri ile işbirliği yapan denetçiler tararından paylaşılır. Sezme ve çözme algoritmaları dört sınıfa ayrılabilirler. Algoritmalar birbirinden, kilitlenmeleri sezme yöntemleri ile ayrılmaktadır. Yol iteleme algoritmaları açık bir bekleme grafi oluştururlar. Ayrıt takip algoritmaları, bekleme grafinın ayrıtları boyunca öncü mesajlar gönderirler. Yayılan hesaplamalar algoritmaları, yayılan mesaj iletimi başlatırlar. Global durum tespit algoritmaları sistem bilgisini her an için tutarlı şekilde tutmaya çalışırlar. Bu çalışmada, merkezi algoritmalara uygulanabilecek bazı ekler önerilmiştir. Buna göre, mesaj trafiğini azaltmak amacıyla bekleme grafinın farklı bir yapıda tutulması gerekir. Oluşturulan bekleme grafi özkaynak kuyruklanndaki sıralamayı içerir ve kilitlenme yöneticisi öncül bilgiye sahip olur. Kilitlenme yöneticisi, kurban seçilen görevin kilitlenme anında bırakacağı özkaynaklann hangi vngörevlere atanacağım içeren bu bilgiyi kullanır. Bunun sonucunda özkaynak yöneticilerinden kilitlenme yöneticisine, kilitlenmeden kaynaklanan bırakma mesajlarının gönderilmesine gerek kalmaz. Kilitlenme yöneticisi öncül bilgiye sahip olduğundan, tabloda yer alan bekleme İlişkileri kurban tüm özkaynaklannı bırakınca oluşacak duruma göre düzenlenir. Kurban seçilen görev, kilitlenme anındaki bırakma mesajlarım diğer bırakma mesajlarından ayırmak için, özkaynak yöneticisine gönderdiği mesajlara özel bir bilgi ekler. Özkaynak yöneticisi, bu bilgiyi kullanarak kilitlenme kaynaklı bırakma mesajlarını kilitlenme yöneticisine iletmez. Kilitlenme yöneticisinin öncül bilgiye sahip olmasından dolayı, özkaynak yöneticilerinden kilitlenme yöneticisine gönderilen mesajların tutarsızlık yaratma olasılığı vardır. Kilitlenme yöneticisi, kurban seçilen görevin tüm özkaynaklan bıraktığı bilgisini tablosuna işlemiştir. Bu sırada özkaynak yöneticileri, kurbanın beklenen görev olduğu istek mesajları gönderebilir. Gelen mesajların tabloya düzeltilerek işlenmesi gerekir. Bu amaçla, kilitlenme yöneticisi kurban seçilen görevlerin kimliğim sakladığı bir“kurbanlar”tablosu tutar. Gelen mesajlar kontrol edilerek, beklenen görev kurbanlar tablosunda araştırılır. Görev, tabloda bulunuyorsa, gelen mesaj uygun şekilde değiştirilir. Uygulanan hiyerarşik algoritmada mesaj gecikmelerinden dolayı, kilitlenme yöneticilerine tutarsız bilgiler ulaşmaktadır. Bazı önlemler alınarak algoritmanın doğru çalışması sağlanmıştır. Ancak tüm olası durumlar gözönüne alınmamıştır. Son olarak, dağıtılmış bir algoritma önerilmiş ve gerçeklenmiştir. Önerilen dağıtılmış kilitlenme sezme ve çözme algoritmasında, tüm kilitlenme yöneticilerinin halka yapısında konumlanarak global kilitlenmeleri bulmaları amaçlanır. Sistemdeki her kilitlenme yöneticisi kendi yerel bölgesindeki kilitlenmeleri sezmek ve çözmek ile yükümlüdür. Kendi bölgesinde bulamadığı global kilitlenmeler için diğer kilitlenme yöneticileri ile işbirliği yapar. İstek ve bırakma mesajları halkanın tüm düğümlerini dolaşır ve halkadaki tüm düğümler global durum hakkında ansal olarak yaklaşık aynı bilgiye sahip olurlar. Oluşan bir global kilitlenmeyi tüm kilitlenme yöneticileri bulacaktır. Bu nedenle, kilitlenme amnda tüm kilitlenme yöneticilerinin aynı görevi kurban seçmelerini sağlamak gerekmektedir. Tekil kurban seçimim sağlamak için, halkadaki düğümlerden bir tanesi (denetçi) temel alınır ve istek mesajlarının bu düğümden geçme sırasına göre kurban seçimi yapılır. Denetçi düğüm, kendisine gelen çevrim tamamlayan son istek mesajının sahibi görevi kurban seçer ve istek mesajının halkadaki dolaşımım sonlandınr. Bunun dışında, denetçi düğüm kendisinden geçen her istek mesajına“onay”adı verilen özel bir bilgi ekler. Bu bilginin yer aldığı istek mesajları diğer kilitlenme yöneticileri tarafından bir kurban isteği olarak seçilmezler. Kilitlenme yöneticileri global kurban seçimi yaparken, kendilerine onaysız gelen son istek mesajının sahibi görevi kurban seçerler. Birden fazla onaysız mesaj arasında seçim yapabilmek için, onaysız mesajlar tabloya işlenirken birer sıra numarası verilerek işlenir. vıııMerkezi, hiyerarşik ve dağıtılmış algoritmalar bir dağıtılmış sistem benzetim modeli kurularak uygulanmıştır. Benzetim modeli kuruluken, gerçek zamanlı bir çok görevli çekirdek kullanılmıştır. IX

Özet (Çeviri)

DEADLOCK ALGORITHMS AND THEIR APPLICATIONS IN DISTRIBUTED SYSTEMS SUMMARY In distributed systems, deadlocks may arise as a result of resource allocation policies. Deadlock is the permanent blocking of a set of processes which compete for resources or communicate with each other. Deadlocks can be modelled using wait-for-graphs (WFG) which define the relations among the waiting processes. There are four conditions necessary for deadlock situation to arise in a system. After a deadlock situation arises, depending on the request model a cycle or a knot in the WFG represents the deadlock. There are three methods to handle deadlocks. Avoidance methods require advance knowledge of resource usage by processes. Using that information, a resource allocation is done only when this allocation eventually does not lead to a deadlock. Prevention methods try to design the system in such a way that deadlocks become impossible. In that way, at least one of the four necessary conditions for deadlock is not satisfied. The last method is detection and resolution, where deadlocks are allowed to occur. In this case, the system gathers information to detect deadlocks, and then takes necessary resolution actions to recover from deadlock. Deadlock detection and resolution algorithms make some assumptions about the resource request models in the system, so that algorithms are designed effectively. Detection and resolution algorithms have three different methods in keeping the system state information. In the centralized method, all information is kept at one site. In the hierarchical method, the information is distributed in a hierarchy of deadlock controllers. In the distributed method, deadlock controllers, which share all the system information, are located at the same level and cooperate to detect and resolve deadlocks. Detection and resolution algorithms can be classified into four groups. The algorithms differ from each other by using the methods of deadlock detection. Path pushing algorithms constitute an explicit WFG. Edge chasing algorithms send probe messages along the edges of the WFG. Diffusing computation algorithms initiate diffusing message transfers. Global state detection algorithms try to keep system information consistent at each moment. In this study, some extensions to the centralized algorithms are proposed. Thus, the wait-for-graph has to be constructed in a different form to reduce the message traffic. The constructed wait-for-graph includes the sequence in the resourcequeues and the deadlock manager has a priori information. The deadlock manager uses this information that contains to which tasks the resources will be assigned in deadlock situation when the victim releases the resources. As a result, there will be no need to resend the release messages generated from the deadlock situation. Since the deadlock manager has a priori information, the relations in the table are arranged according to the state which will arise when the victim releases all the resources it holds. The victim attaches a special field to the messages sent to resource managers, in order to distinguish the release messages in deadlock from the other release messages. Using this information, the resource manager does not propagate the release messages in deadlock to the deadlock manager. There is the possibility that the messages sent by resource managers to deadlock manager can result in inconsistency because of the a priori information. The deadlock manager has already updated its table with the information that the victim has released all the resources. At that time, the resource manager might send request messages to the deadlock manager including the victim as the waited task. The messages should be recorded after they are corrected. Therefore, the deadlock manager maintains a table called“victims”where it keeps the identities of the tasks selected as victims. The received messages are checked and the waited task is searched in the“victims”table. If the task is found in the table, the message is corrected as it should be. In the applied hierarchical algorithm, inconsistent information is received by the deadlock managers because of the message delays. It is provided that the algorithm functions correctly by taking some precautions. However, all the possible situations are not considered. Finally, a distributed algorithm has been proposed and it has been implemented. In the proposed distributed deadlock detection and resolution algorithm, all the deadlock managers are located in ring structure in order to detect global deadlocks. Every deadlock manager in the system is responsible for the detection and resolution of the deadlocks in its local region. It cooperates with other deadlock managers in order to detect global deadlocks which they can not detect in their own region. The request and release messages are circulated through all nodes of the ring and all the nodes have approximately the same information at any time. A global deadlock will be detected by all deadlock managers. Therefore, it should be ensured that all deadlock managers select the same task as the victim. In order to provide unique victim selection, one of the managers in the ring is selected as the controller node and victim selection is made according to the order the messages pass through this node. The controller node selects the owner of the request message, which completes the deadlock cycle, as the victim and ends the transmission of this message in the ring. In addition, the controller node adds a field called“approval”to the request messages that pass through it. The messages which contain this field will not be selected as a victim's request. The deadlock managers select the task, which is the owner TC YÜKSEK'“'”...jof the last arrived disapproved request message, as a victim. When the disapproved messages are recorded to the table, a sequence number is given to these messages in order to distinguish among many disapproved messages. The centralized, hierarchical and distributed algorithms have been implemented by using a distributed system simulation model. A real time multitasking kernel has been used for modelling the distributed system. XII

Benzer Tezler

  1. Tez No

    496361

    Dynamic optimization of radio resource management in LTE-based high-speed railway wireless networks

    LTE tabanlı hızlı demiryolu kablosuz ağlarda radyo kaynak yönetiminin dinamik optimizasyonu

    ALİ HÜSEYİN RÜSTEM

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. HAKAN ALİ ÇIRPAN

  2. Tez No

    825981

    Predicting of distributed denial of service using machine learning algorithms

    Başlık çevirisi yok

    HANEEN KHAIRULLAH TALIB ALSELMI

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. OSMAN NURİ UÇAN

  3. Tez No

    97318

    Toplam kalite yönetiminde insan kaynaklarının eğitimi

    Education and training in total quality management

    KEMAL OK

    Yüksek Lisans

    Türkçe

    Türkçe

    2000

    İşletmeKocaeli Üniversitesi

    İşletme Yönetimi ve Organizasyon Ana Bilim Dalı

    PROF. DR. AVNİ YÜCEL ERYILMAZ

  4. Tez No

    893641

    Kanser hücre membranı kaplı manyetik nanoparçacıkların sentezlenmesi ve glioblastoma tedavisinde sitotoksik etkinliğinin incelenmesi

    Synthesis of cancer cell membrane coated magnetic iron oxide nanoparticles and investigation of cytotoxic efficacy in glioblastoma treatment

    BUSE SANCAKLI

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    BiyoteknolojiBezm-i Alem Vakıf Üniversitesi

    Biyoteknoloji Ana Bilim Dalı

    PROF. DR. AYDAN DAĞ

  5. Tez No

    731065

    Developing a novel recombinant IL-1 receptor antagonist to treat the cytokine storm in Covid-19

    Covid-19 hastalığında sitokin fırtınasını tedavi etmek üzere yeni IL-1 reseptör antagonist geliştirilmesi

    BURCU BEYAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2022

    BiyomühendislikKoç Üniversitesi

    Biyomedikal Bilimler ve Mühendislik Ana Bilim Dalı

    DOÇ. DR. SEDA KIZILEL

Geri Dön