[發明專利]一種低開銷的死鎖預測方法、裝置及電子設備

有效

• 申請號: 202010468645.3
• 申請日: 2020-05-28
• 公開（公告）號: CN111752718B
• 公開（公告）日: 2022-07-12
• 發明（設計）人: 不公告發明人
• 申請（專利權）人: 西安深信科創信息技術有限公司
• 主分類號: G06F9/52
• 分類號: G06F9/52
• 代理公司: 西安嘉思特知識產權代理事務所(普通合伙) 61230
• 代理人: 王海棟

本發明公開了一種低時間開銷的死鎖預測方法、裝置及電子設備；該方法包括：在多線程程序的執行過程中，響應于鎖操作，維護一個預測性可達關系圖，并記錄預測性可達關系圖對應的程序執行路徑信息；其中，該預測性可達關系圖，用于表征鎖操作涉及的各個鎖之間存在的可達性關系；在執行過程中的任一時刻，響應于死鎖檢測需求，根據當前維護的預測性可達關系圖和對應的程序執行路徑信息，利用多項式時間復雜度的算法，預測多線程程序中存在的死鎖。本發明可以有效降低死鎖預測的時間開銷。

技術領域

本發明屬于軟件測試技術領域，特別涉及一種低開銷的死鎖預測方法、裝置及電子設備。

背景技術

多核處理器的快速發展極大推動了大規模多線程程序的廣泛使用。從底層的操作系統到上層的應用程序、從服務器到客戶端都大量使用并發處理。多線程程序開發的復雜性帶來了嚴重的并發缺陷。死鎖作為一類重要的并發缺陷，其發生會阻止程序的進一步運行，嚴重影響軟件的可用性和可靠性。死鎖是由于多個線程之間的不正確同步引起的，多個線程在相互等待別的線程所擁有的鎖，從而進入一個僵持狀態，造成死鎖。

程序中已經發生的死鎖很容易在測試過程中被檢測到。但是由于線程交錯順序的不確定性，程序中潛在的一些死鎖在程序有限次的執行過程中卻很難暴露。雖然理論上，模型檢測技術可以遍歷所有的線程交錯狀態，從而發現全部的潛在死鎖。但是由于線程交錯狀態空間爆炸的問題，該方法在真實的大規模程序上并不實用。因此，在線的死鎖預測變得十分必要。然而，目前已有的預測性死鎖檢測方法主要針對離線測試，即將程序執行軌跡映射到一個大的數據結構上，在該數據結構上運行指數級時間復雜度的算法來發現環，并將發現的環作為死鎖報告出來。然而，這類方法會引入幾十倍乃至上千倍的時間開銷，而通常情況下在線測試工具所允許的時間開銷僅在5％以內。

發明內容

為了降低在線死鎖預測的時間開銷，本發明提出一種低時間開銷的死鎖預測方法、裝置及電子設備。

本發明要解決的技術問題通過以下技術方案實現：

第一方面，本發明提供了一種低時間開銷的死鎖預測方法，包括：

在多線程程序的執行過程中，響應于鎖操作，維護一個預測性可達關系圖，并記錄所述預測性可達關系圖對應的程序執行路徑信息；其中，所述預測性可達關系圖，用于表征所述鎖操作涉及的各個鎖之間存在的可達性關系；

在所述執行過程中的任一時刻，響應于死鎖檢測需求，根據當前維護的預測性可達關系圖和對應的程序執行路徑信息，利用多項式時間復雜度的算法，預測所述多線程程序中存在的死鎖。

在一種可選實現方式中，所述鎖操作包括鎖獲取操作、鎖釋放操作和鎖銷毀操作；

所述在多線程程序的執行過程中，響應于鎖操作，維護一個預測性可達關系圖，包括：

在多線程程序的執行過程中，

根據所述鎖獲取操作或所述鎖釋放操作所涉及的鎖之間存在的可達性關系，構建所述預測性可達關系圖的內容；

根據所述鎖銷毀操作所要銷毀的鎖的入度和出度，對所述預測性可達關系圖的內容進行約減。

在一種可選實現方式中，所述預測性可達關系圖包括：已執行所述鎖獲取操作，且未執行所述鎖銷毀操作的每個鎖的第一邊集和第二邊集；

其中，每個鎖的第一邊集由該鎖通往其他鎖的邊構成，每個鎖的第二邊集由其他鎖通往該鎖的邊構成；

任一所述邊為一直接邊或一間接邊；所述直接邊用于表征位于同一鎖集合的兩個鎖之間的可達性關系；所述間接邊用于表征同一鎖序列中位置不相鄰的兩個鎖之間的可達性關系；同一鎖序列中位置相鄰的任意兩個鎖之間的可達性關系為所述直接邊。