[發明專利]避免死鎖的資源分配方法及系統

有效

• 申請號: 201310422363.X
• 申請日: 2013-09-16
• 公開（公告）號: CN103473137B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 孫浩
• 申請（專利權）人: 東軟集團股份有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京鴻元知識產權代理有限公司11327
• 代理人: 陳英俊

技術領域

本發明涉及計算機系統技術領域，更為具體地，涉及一種避免死鎖的資源分配方法及系統。

背景技術

在計算機系統的使用中，經常出現多個并發進程搶占同一資源的現象。如果進行占用資源的順序不合理，則有可能出現死鎖。為了避免死鎖的出現，程序設計者有必要保證各個進程對資源的占用處于一種“安全狀態”。安全狀態是指系統能按某種順序，例如按照P1，P2，....Pn這樣一個安全序列，為每個進程分配其所需資源，直到最大需求，使每個進程都可順序完成。若系統不存在一個安全序列，則系統處于不安全狀態。

避免死鎖所處理的問題就是如何保證在每次分配資源之后，整個系統都能處于安全狀態。經典的解決方案是所謂的“銀行家算法”，此算法對于每次的資源申請都去做一次模擬運算，即所謂的“安全性檢查”，看是否在資源分配后每個進程都能順利完成。如果可以則接受請求，分配資源；否則拒絕請求。假設在進程數N固定，單一資源的情形下，銀行家算法的運行原理主要分為以下4步：

步驟1：正確性判斷。如果資源請求量大于現存的剩余資源總量，則直接拒絕分配。

步驟2：假設資源y是可分配的，確定分配后的進程序列。

步驟3：對分配后的進程序列做安全性檢查，確保N個進程中的每一個都可以擁有足夠的資源順利完成；

步驟4：將沒有通過安全性檢查的進程序列恢復至分配前的狀態。

作為銀行家算法的一個實施例，圖1示出了傳統的銀行家算法的流程。

如圖1所示，設x表示現有資源剩余量，共有N個進程，r[i]與a[i]分別表示第i個進程的資源需求量與資源占有量，且r[i]<r[i+1]，即各進程按資源需求量從小到大有序排列，bank(i,y)表示為資源需求量第i小的進程分配y個單位的資源,分配成功返回1，拒絕分配返回-1。具體地流程如下所示：

S101：輸入進程排序號i與資源申請量y；

S102：判斷資源申請量y是否大于剩余總資源量x（即y>x），如果是，進入S103，否則進入S104；

S103：申請失敗，return-1；

S104：記錄分配后的變量值，即r_j=r[i]-y，a_j=a[i]+y，j=i。

S105：判斷j>1且r_j<r[j-1]，如果是，進入S106，否則進入S107。

S106：變更進程序列排名，即r[j]=r[j-1]，a[j]=a[j-1]，--j，然后返回S105重新進行判斷。

S107：確定排序為i的進程下降至第j位，即r[j]=r_j，a[j]=a_j。

S108：對分配后的進程序列做安全性檢查，即x-=y，s=x。

S109：循環計算第k個進程所獲取的資源量，即s+=a[k]，++k。

S110：判斷系數變量k是否小于等于進程總數N，即k<=N，如果是，進入S111，否則進入S112。

S111：判斷r[k]>s，如果是，返回S109，否則進入S112。

S112：判斷k>N，如果是，進入S113，否則進入S114。

S113：申請成功，返回return1。

S114：恢復變量至原狀態，即x+=y，r_j=r[j]，a_j=a[j]，k=j。

S115：判斷k<i，如果是，進入S116，否則，進入S117。

S116：恢復進程排序r[j]=r[j+1]；a[j]=a[j+1]，++k，返回S115。

S117：r[i]=r_j+y，a[i]=a_j-y。

S118：申請失敗，return-1。

從銀行家算法的運行原理，再結合圖1所示的流程可以看出，銀行家算法在理論上是出色的，但在算法性能上卻存在著本質的不足。對于每一次資源申請其都要做一整套的流程判斷才能最終得到結論，這一點阻礙了其應用。通過分析可以大致計算出，算法運行一次的運算量在接受申請時約為3（i-j）+N步，拒絕申請時約為5(i-j)+N步。在具體的工程中，實時用戶往往要求有更好的響應速度，這一點該算法無法滿足用戶的需求。

發明內容

鑒于上述問題，本發明的目的是提供一種避免死鎖的資源分配方法及系統，以在多個并發進程中實現對資源分配的合理性及實時性。

根據本發明的一個方面，提供一種避免死鎖的資源分配方法，包括：

按照進程對資源的需求量從小到大對進程進行排序；