本文選題：死鎖檢測(cè)　切入點(diǎn)：等待圖　出處：《北京交通大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：隨著當(dāng)前信息技術(shù)的高速發(fā)展,日常學(xué)習(xí)、工作、生產(chǎn)和生活中的數(shù)據(jù)呈現(xiàn)出指數(shù)型爆炸增長的趨勢(shì)。而近年來以大容量、多種類、高速度、高價(jià)值為主要特征的大數(shù)據(jù)處理技術(shù)日益成為生產(chǎn)系統(tǒng)中不可或缺的重要技術(shù)。作為大數(shù)據(jù)處理技術(shù)的重要實(shí)現(xiàn)架構(gòu),分布式系統(tǒng)的重要性也日漸顯現(xiàn)。但是在分布式系統(tǒng)中還存在著不少問題難以完美解決,例如數(shù)據(jù)一致性,系統(tǒng)的穩(wěn)定性等問題。但是本文將主要研究分布式系統(tǒng)中的死鎖問題。死鎖的產(chǎn)生主要是因?yàn)橄到y(tǒng)對(duì)于共享資源的分配或者程序推進(jìn)的順序不當(dāng)。在分布式系統(tǒng)中,死鎖會(huì)導(dǎo)致系統(tǒng)的吞吐量下降,并且無法得到正常的運(yùn)行結(jié)果。同時(shí),發(fā)生死鎖的進(jìn)程不再釋放已經(jīng)占有的資源又會(huì)降低資源的利用效率。因此,分布式系統(tǒng)中需要有高效處理死鎖的模塊。為了高效地檢測(cè)分布式系統(tǒng)中的死鎖,本文中提出了一種基于探針消息的死鎖檢測(cè)算法。首先,當(dāng)分布式系統(tǒng)中發(fā)生死鎖時(shí),系統(tǒng)中的某些節(jié)點(diǎn)會(huì)觸發(fā)死鎖檢測(cè)算法的執(zhí)行,這類節(jié)點(diǎn)被稱為發(fā)起節(jié)點(diǎn)。當(dāng)發(fā)起節(jié)點(diǎn)發(fā)起死鎖檢測(cè)算法的執(zhí)行時(shí),它們會(huì)向自身的后繼節(jié)點(diǎn)發(fā)送探針消息。然后,非發(fā)起節(jié)點(diǎn)將自身收到的探針消息又轉(zhuǎn)發(fā)給自己的后繼節(jié)點(diǎn)。在這過程中引入了優(yōu)先級(jí)的概念來區(qū)分不同發(fā)起節(jié)點(diǎn)的算法實(shí)例。采用這樣的策略傳遞探針消息可以使系統(tǒng)中所有的節(jié)點(diǎn)都能收到探針消息,并參與進(jìn)死鎖的檢測(cè)過程當(dāng)中。接著,當(dāng)非發(fā)起節(jié)點(diǎn)收到的探針消息的數(shù)量等于自身的前驅(qū)的數(shù)量時(shí),它將向自己所屬的死鎖檢測(cè)算法實(shí)例的發(fā)起節(jié)點(diǎn)發(fā)送報(bào)告消息。最后,發(fā)起節(jié)點(diǎn)根據(jù)接收到的消息中的權(quán)值決定消息的發(fā)送和接收階段是否結(jié)束。并且,在此階段結(jié)束時(shí),利用收到的報(bào)告消息中的依賴信息進(jìn)行死鎖的檢測(cè)。在現(xiàn)有的死鎖檢測(cè)算法中,依賴信息會(huì)在節(jié)點(diǎn)之間重復(fù)傳遞。在系統(tǒng)中存在多個(gè)算法實(shí)例時(shí),這樣的重復(fù)傳遞會(huì)加重網(wǎng)絡(luò)通信的負(fù)擔(dān)。而本文中所描述的算法可以減少消息的重復(fù)傳遞。實(shí)驗(yàn)結(jié)果也證明了這一優(yōu)勢(shì)。特別是在擁有多個(gè)發(fā)起節(jié)點(diǎn)的并發(fā)執(zhí)行情況下,本文中所描述的算法能顯著的減少消息發(fā)送的數(shù)量和降低算法執(zhí)行過程中總的發(fā)送的消息的大小。
[Abstract]:With the rapid development of information technology, the data in daily study, work, production and daily life are increasing exponentially. And in recent years, with large capacity, many kinds and high speed, Big data's processing technology, which is characterized by high value, has increasingly become an indispensable and important technology in the production system. The importance of distributed systems is becoming more and more important. However, there are still many problems in distributed systems that are difficult to solve perfectly, such as data consistency. However, this paper will focus on the deadlock problem in distributed systems. The deadlock is mainly caused by the improper allocation of shared resources or the improper sequence of program advancement. Deadlocks can cause system throughput to decline and fail to get normal results. At the same time, the process that occurs deadlocks will no longer release the resources already occupied and will reduce the efficiency of the resources. In order to detect deadlock efficiently in distributed system, a deadlock detection algorithm based on probe message is proposed. Some nodes in the system trigger the execution of the deadlock detection algorithm, which is called the initiating node. When the initiating node initiates the implementation of the deadlock detection algorithm, they send a probe message to their successors. The non-initiating node forwards the probe message it receives to its successor node. In the process, the concept of priority is introduced to distinguish the algorithm instance of different initiating node. Using this policy, the probe message can be transmitted. So that all nodes in the system can receive probe messages, Then, when the number of probe messages received by the non-initiator node is equal to the number of its own precursors, it will send a report message to the initiating node of the deadlock detection algorithm to which it belongs. Finally, when the number of probe messages received by the non-initiator node is equal to the number of its precursors, it will send a report message to the initiating node of its own deadlock detection algorithm. The initiating node determines whether the sending and receiving stages of the message end based on the weights in the received message. And, at the end of this phase, In the existing deadlock detection algorithms, the dependency information is repeatedly passed between nodes. When there are many instances of algorithms in the system, the deadlock is detected by using the dependency information in the received report message. The algorithm described in this paper can reduce the repeated transmission of messages. The experimental results also prove this advantage, especially in the case of concurrent execution with multiple initiating nodes. The algorithm described in this paper can significantly reduce the number of messages sent and the total size of messages sent during the execution of the algorithm.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP338.8

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 周建勇;于杰;劉海陽;孫燕;劉久富;王志勝;楊忠;劉春生;;Petri網(wǎng)并發(fā)進(jìn)程的死鎖避免策略[J];計(jì)算機(jī)技術(shù)與發(fā)展;2016年11期

2 黃正鵬;;計(jì)算機(jī)操作系統(tǒng)中死鎖問題研究[J];電腦知識(shí)與技術(shù);2016年20期

3 趙寧;井海明;馬增強(qiáng);陳遠(yuǎn)云;;操作系統(tǒng)中多進(jìn)程并行時(shí)的死鎖問題[J];鐵路計(jì)算機(jī)應(yīng)用;2007年12期

4 郝朝輝,麥中凡;面向?qū)ο髷?shù)據(jù)庫死鎖檢測(cè)方法研究[J];軟件學(xué)報(bào);1996年12期

相關(guān)碩士學(xué)位論文 前1條

1 陳鵬;分布式數(shù)據(jù)庫死鎖檢測(cè)算法研究[D];重慶大學(xué);2004年

，

本文編號(hào)：1630432