[發明專利]操作系統中的死鎖檢測方法

有效

• 申請號: 201310351342.3
• 申請日: 2013-08-13
• 公開（公告）號: CN103399818A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 李曦;陳香蘭;周學海;張海鵬;賈剛勇;朱宗衛
• 申請（專利權）人: 中國科學技術大學蘇州研究院
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F9/46
• 代理公司: 蘇州創元專利商標事務所有限公司 32103
• 代理人: 范晴

技術領域

本發明屬于操作系統優化技術領域，具體涉及一種操作系統中的死鎖檢測方法。

背景技術

為了充分發揮cpu多核的性能，并發程序設計已經十分廣泛，但是開發并發程序面臨很多挑戰，死鎖就是其中的一個。在設備驅動錯誤中有19%的錯誤是由于并發導致的，在這些并發錯誤中72%（67/93）跟死鎖有關，文獻S.Lu,S.Park,E.Seo,et?al.Learning?from?mistakes–a?comprehensive?study?on?real?world?concurrency?bug?characteristics.In?Proc.13th?Intl.Conf.on?Architectural?Support?for?Programming?Languages?and?Operating?Systems,2008通過對4大開源軟件：MySQL、Apache、Mozilla和OpenOffice中的并發錯誤進行分析，發現30%（31/105）的錯誤是由死鎖造成的。

死鎖檢測的方法分為靜態和動態兩種，靜態檢測通過工具來分析待檢測程序的源代碼來找出可能要發生死鎖的程序位置，這種方法不適用于檢測代碼量大的程序，而且很不準確，動態檢測是在程序運行時，檢查可能發生的死鎖，但是動態監測性能開銷大，不適用于內核、驅動中死鎖的檢測。

關于java多線程程序中的死鎖檢測，無論是靜態方法還是動態方法，過去都已經做過大量研究，而且目前已經有比較成熟的工具可以直接檢查java程序中的死鎖，如jstack、lockstat等。由于操作系統代碼量大、對性能敏感，過去關于操作系統死鎖方面的研究比較少，死鎖檢測工具pluse是在操作系統層實現的，但是該工具只能檢測應用程序中的死鎖，并不能檢測操作系統本身的死鎖。本發明因此而來。

發明內容

為了克服背景知識中的不足，本發明提供一種操作系統中動態檢測死鎖的方法，在保證性能的條件下，可以準確檢測出操作系統中的死鎖。

為了解決現有技術中的這些問題，本發明提供的技術方案是：

一種操作系統中的死鎖檢測方法，其特征在于所述方法包括操作系統中多線程或進程并發執行時進行以下檢測：

1）每隔預定的死鎖檢測周期檢查鎖的持有者鏈表HOLDER_LIST是否為空；

2）當鎖的持有者鏈表HOLDER_LIST不為空時，檢查鎖的持有者鏈表HOLDER_LIST中每個鎖的持有者是不是鎖的等待者；

3）當鎖的持有者為鎖的等待者時，檢測鎖的持有者與鎖的等待者之間是否會形成循環等待圖；

當且僅當鎖的持有者鏈表HOLDER_LIST不為空，鎖的持有者鏈表HOLDER_LIST中鎖的持有者是鎖的等待者，鎖的持有者與鎖的等待者之間形成循環等待圖三者條件同時滿足時，判斷操作系統中線程或進程并行處理時存在死鎖；否則判斷不存在死鎖。

優選的，所述方法中先構建空的鎖的持有者鏈表HOLDER_LIST，采用操作系統內核跟蹤探測工具在操作系統的加鎖函數的函數出口處探測，獲取鎖的持有者信息；當加鎖函數退出時，將進程號或線程號、鎖類型、資源地址作為新的鎖的持有者信息插入鎖的持有者鏈表HOLDER_LIST；當解鎖函數退出時，將相應的鎖的持有者信息從鎖的持有者鏈表HOLDER_LIST刪除。

優選的，所述方法中操作系統內核跟蹤探測工具選自linux內核函數的工具systemtap、Solaris內核或FreeBSD內核中的DTrace。

優選的，所述方法中鎖的等待者是通過篩選異常進程或線程的方法獲取的，所述異常進程或線程為在預定閾值內獲不到處理器或在預定閾值內一直占有處理器的進程或線程。

優選的，所述方法中進程或線程的等待時間通過使用當前的系統時間減去進程或線程描述符中的進程或線程最后一次運行的時間來獲得的。

優選的，所述方法中預定閾值為進程的時間片與進程持有鎖的時間的較大值。

優選的，所述方法中進程持有鎖的時間是通過加鎖函數與解鎖函數之間的時間統計出來的；所述進程的時間片是通過進程的描述符中記錄進程總的運行時間與運行次數的比值統計獲得的。

優選的，所述方法中預定閾值為10s。

優選的，所述方法中異常進程或線程的篩選是通過判斷異常進程的內核棧上有無加鎖函數，從異常進程中篩選出鎖的等待者。