寫給大忙人看的死鎖全詳解

前言

計算機系統中有很多獨佔性的資源,在同一時刻只能每個資源只能由一個進程使用,我們之前經常提到過打印機,這就是一個獨佔性的資源,同一時刻不能有兩個打印機同時輸出結果,否則會引起文件系統的癱瘓。所以,操作系統具有授權一個進程單獨訪問資源的能力。

兩個進程獨佔性的訪問某個資源,從而等待另外一個資源的執行結果,會導致兩個進程都被阻塞,並且兩個進程都不會釋放各自的資源,這種情況就是 死鎖(deadlock)

死鎖可以發生在任何層面,在不同的機器之間可能會發生死鎖,在數據庫系統中也會導致死鎖,比如進程 A 對記錄 R1 加鎖,進程 B 對記錄 R2 加鎖,然後進程 A 和 B 都試圖把對象的記錄加鎖,這種情況下就會產生死鎖。

下面我們就來討論一下什麼是死鎖、死鎖的條件是什麼、死鎖如何預防、活鎖是什麼等。

首先你需要先了解一個概念,那就是資源是什麼

資源

大部分的死鎖都和資源有關,在進程對設備、文件具有獨佔性(排他性)時會產生死鎖。我們把這類需要排他性使用的對象稱為資源(resource)。資源主要分為 可搶佔資源和不可搶佔資源

可搶佔資源和不可搶佔資源

資源主要有可搶佔資源和不可搶佔資源。可搶佔資源(preemptable resource) 可以從擁有它的進程中搶佔而不會造成其他影響,內存就是一種可搶佔性資源,任何進程都能夠搶先獲得內存的使用權。

不可搶佔資源(nonpreemtable resource) 指的是除非引起錯誤或者異常,否則進程無法搶佔指定資源,這種不可搶佔的資源比如有光盤,在進程執行調度的過程中,其他進程是不能得到該資源的。

死鎖與不可搶佔資源有關,雖然搶佔式資源也會造成死鎖,不過這種情況的解決辦法通常是在進程之間重新分配資源來化解。所以,我們的重點自然就會放在了不可搶佔資源上。

下面給出了使用資源所需事件的抽象順序

如果在請求時資源不存在,請求進程就會強制等待。在某些操作系統中,當請求資源失敗時進程會自動阻塞,當自資源可以獲取時進程會自動喚醒。在另外一些操作系統中,請求資源失敗並显示錯誤代碼,然後等待進程等待一會兒再繼續重試。

請求資源失敗的進程會陷入一種請求資源、休眠、再請求資源的循環中。此類進程雖然沒有阻塞,但是處於從目的和結果考慮,這類進程和阻塞差不多,因為這類進程並沒有做任何有用的工作。

請求資源的這個過程是很依賴操作系統的。在一些系統中,一個 request 系統調用用來允許進程訪問資源。在一些系統中,操作系統對資源的認知是它是一種特殊文件,在任何同一時刻只能被一個進程打開和佔用。資源通過 open 命令進行打開。如果文件已經正在使用,那麼這個調用者會阻塞直到當前的佔用文件的進程關閉文件為止。

資源獲取

對於一些數據庫系統中的記錄這類資源來說,應該由用戶進程來對其進行管理。有一種管理方式是使用信號量(semaphore) 。這些信號量會初始化為 1 。互斥鎖也能夠起到相同的作用。

這裏說一下什麼是互斥鎖(Mutexes):

在計算機程序中,互斥對象(mutex) 是一個程序對象,它允許多個程序共享同一資源,例如文件訪問權限,但並不是同時訪問。需要鎖定資源的線程都必須在使用資源時將互斥鎖與其他線程綁定(進行加鎖)。當不再需要數據或線程結束時,互斥鎖設置為解鎖。

下面是一個偽代碼,這部分代碼說明了信號量的資源獲取、資源釋放等操作,如下所示

typedef int semaphore;
semaphore aResource;

void processA(void){
  
  down(&aResource);
	useResource();
  up(&aResource);
  
}

上面显示了一個進程資源獲取和釋放的過程,但是一般情況下會存在多個資源同時獲取鎖的情景,這樣該如何處理?如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useAResource();
  useBResource();
  up(&aResource);
  up(&bResource);
  
}

對於單個進程來說,並不需要加鎖,因為不存在和這個進程的競爭條件。所以單進條件下程序能夠完好運行。

現在讓我們考慮兩個進程的情況,A 和 B ,還存在兩個資源。如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

在上述代碼中,兩個進程以相同的順序訪問資源。在這段代碼中,一個進程在另一個進程之前獲取資源,如果另外一個進程想在第一個進程釋放之前獲取資源,那麼它會由於資源的加鎖而阻塞,直到該資源可用為止。

在下面這段代碼中,有一些變化

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&bResource); // 變化的代碼 
  down(&aResource); // 變化的代碼
	useBothResource();
  up(&aResource); // 變化的代碼 
  up(&bResource); // 變化的代碼 
  
}

這種情況就不同了,可能會發生同時獲取兩個資源並有效地阻塞另一個過程,直到完成為止。也就是說,可能會發生進程 A 獲取資源 A 的同時進程 B 獲取資源 B 的情況。然後每個進程在嘗試獲取另一個資源時被阻塞。

在這裏我們會發現一個簡單的獲取資源順序的問題就會造成死鎖,所以死鎖是很容易發生的,所以下面我們就對死鎖做一個詳細的認識和介紹。

死鎖

如果要對死鎖進行一個定義的話,下面的定義比較貼切

如果一組進程中的每個進程都在等待一個事件,而這個事件只能由該組中的另一個進程觸發,這種情況會導致死鎖

簡單一點來表述一下,就是每個進程都在等待其他進程釋放資源,而其他資源也在等待每個進程釋放資源,這樣沒有進程搶先釋放自己的資源,這種情況會產生死鎖,所有進程都會無限的等待下去。

換句話說,死鎖進程結合中的每個進程都在等待另一個死鎖進程已經佔有的資源。但是由於所有進程都不能運行,它們之中任何一個資源都無法釋放資源,所以沒有一個進程可以被喚醒。這種死鎖也被稱為資源死鎖(resource deadlock)。資源死鎖是最常見的類型,但不是所有的類型,我們後面會介紹其他類型,我們先來介紹資源死鎖

資源死鎖的條件

針對我們上面的描述,資源死鎖可能出現的情況主要有

  • 互斥條件:每個資源都被分配給了一個進程或者資源是可用的
  • 保持和等待條件:已經獲取資源的進程被認為能夠獲取新的資源
  • 不可搶佔條件:分配給一個進程的資源不能強制的從其他進程搶佔資源,它只能由佔有它的進程显示釋放
  • 循環等待:死鎖發生時,系統中一定有兩個或者兩個以上的進程組成一個循環,循環中的每個進程都在等待下一個進程釋放的資源。

發生死鎖時,上面的情況必須同時會發生。如果其中任意一個條件不會成立,死鎖就不會發生。可以通過破壞其中任意一個條件來破壞死鎖,下面這些破壞條件就是我們探討的重點

死鎖模型

Holt 在 1972 年提出對死鎖進行建模,建模的標準如下:

  • 圓形表示進程
  • 方形表示資源

從資源節點到進程節點表示資源已經被進程佔用,如下圖所示

在上圖中表示當前資源 R 正在被 A 進程所佔用

由進程節點到資源節點的有向圖表示當前進程正在請求資源,並且該進程已經被阻塞,處於等待這個資源的狀態

在上圖中,表示的含義是進程 B 正在請求資源 S 。Holt 認為,死鎖的描述應該如下

這是一個死鎖的過程,進程 C 等待資源 T 的釋放,資源 T 卻已經被進程 D 佔用,進程 D 等待請求佔用資源 U ,資源 U 卻已經被線程 C 佔用,從而形成環。

總結一點:吃着碗里的看着鍋里的容易死鎖

那麼如何避免死鎖呢?我們還是通過死鎖模型來聊一聊

假設有三個進程 (A、B、C) 和三個資源(R、S、T) 。三個進程對資源的請求和釋放序列如下圖所示

操作系統可以任意選擇一個非阻塞的程序運行,所以它可以決定運行 A 直到 A 完成工作;它可以運行 B 直到 B 完成工作;最後運行 C。

這樣的順序不會導致死鎖(因為不存在對資源的競爭),但是這種情況也完全沒有并行性。進程除了在請求和釋放資源外,還要做計算和輸入/輸出的工作。當進程按照順序運行時,在等待一個 I/O 時,另一個進程不能使用 CPU。所以,嚴格按照串行的順序執行並不是最優越的。另一方面,如果沒有進程在執行任何 I/O 操作,那麼最短路徑優先作業會優於輪轉調度,所以在這種情況下串行可能是最優越的

現在我們假設進程會執行計算和 I/O 操作,所以輪詢調度是一種合理的調度算法。資源請求可能會按照下面這個順序進行

下圖是針對上面這六個步驟的資源分配圖。

這裏需要注意一個問題,為什麼從資源出來的有向圖指向了進程卻表示進程請求資源呢?筆者剛開始看也有這個疑問,但是想了一下這個意思解釋為進程佔用資源比較合適,而進程的有向圖指向資源表示進程被阻塞的意思。

在上面的第四個步驟,進程 A 正在等待資源 S;第五個步驟中,進程 B 在等待資源 T;第六個步驟中,進程 C 在等待資源 R,因此產生了環路並導致了死鎖。

然而,操作系統並沒有規定一定按照某種特定的順序來執行這些進程。遇到一個可能會引起死鎖的線程后,操作系統可以乾脆不批准請求,並把進程掛起一直到安全狀態為止。比如上圖中,如果操作系統認為有死鎖的可能,它可以選擇不把資源 S 分配給 B ,這樣 B 被掛起。這樣的話操作系統會只運行 A 和 C,那麼資源的請求和釋放就會是下面的步驟

下圖是針對上面這六個步驟的資源分配圖。

在第六步執行完成后,可以發現並沒有產生死鎖,此時就可以把資源 S 分配給 B,因為 A 進程已經執行完畢,C 進程已經拿到了它想要的資源。進程 B 可以直接獲得資源 S,也可以等待進程 C 釋放資源 T 。

有四種處理死鎖的策略:

  • 忽略死鎖帶來的影響(驚呆了)
  • 檢測死鎖並回復死鎖,死鎖發生時對其進行檢測,一旦發生死鎖后,採取行動解決問題
  • 通過仔細分配資源來避免死鎖
  • 通過破壞死鎖產生的四個條件之一來避免死鎖

下面我們分別介紹一下這四種方法

鴕鳥算法

最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm),把頭埋在沙子里,假裝問題根本沒有發生。每個人看待這個問題的反應都不同。數學家認為死鎖是不可接受的,必須通過有效的策略來防止死鎖的產生。工程師想要知道問題發生的頻次,系統因為其他原因崩潰的次數和死鎖帶來的嚴重後果。如果死鎖發生的頻次很低,而經常會由於硬件故障、編譯器錯誤等其他操作系統問題導致系統崩潰,那麼大多數工程師不會修復死鎖。

死鎖檢測和恢復

第二種技術是死鎖的檢測和恢復。這種解決方式不會嘗試去阻止死鎖的出現。相反,這種解決方案會希望死鎖盡可能的出現,在監測到死鎖出現后,對其進行恢復。下面我們就來探討一下死鎖的檢測和恢復的幾種方式

每種類型一個資源的死鎖檢測方式

每種資源類型都有一個資源是什麼意思?我們經常提到的打印機就是這樣的,資源只有打印機,但是設備都不會超過一個。

可以通過構造一張資源分配表來檢測這種錯誤,比如我們上面提到的

的算法來檢測從 P1 到 Pn 這 n 個進程中的死鎖。假設資源類型為 m,E1 代表資源類型1,E2 表示資源類型 2 ,Ei 代表資源類型 i (1 <= i <= m)。E 表示的是 現有資源向量(existing resource vector),代表每種已存在的資源總數。

現在我們就需要構造兩個數組:C 表示的是當前分配矩陣(current allocation matrix) ,R 表示的是 請求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數。所以,Cij 表示 Pi 持有資源 j 的數量。Rij 表示 Pi 所需要獲得的資源 j 的數量

一般來說,已分配資源 j 的數量加起來再和所有可供使用的資源數相加 = 該類資源的總數。

死鎖的檢測就是基於向量的比較。每個進程起初都是沒有被標記過的,算法會開始對進程做標記,進程被標記后說明進程被執行了,不會進入死鎖,當算法結束時,任何沒有被標記過的進程都會被判定為死鎖進程。

上面我們探討了兩種檢測死鎖的方式,那麼現在你知道怎麼檢測后,你何時去做死鎖檢測呢?一般來說,有兩個考量標準:

  • 每當有資源請求時就去檢測,這種方式會佔用昂貴的 CPU 時間。
  • 每隔 k 分鐘檢測一次,或者當 CPU 使用率降低到某個標準下去檢測。考慮到 CPU 效率的原因,如果死鎖進程達到一定數量,就沒有多少進程可以運行,所以 CPU 會經常空閑。

從死鎖中恢復

上面我們探討了如何檢測進程死鎖,我們最終的目的肯定是想讓程序能夠正常的運行下去,所以針對檢測出來的死鎖,我們要對其進行恢復,下面我們會探討幾種死鎖的恢復方式

通過搶佔進行恢復

在某些情況下,可能會臨時將某個資源從它的持有者轉移到另一個進程。比如在不通知原進程的情況下,將某個資源從進程中強製取走給其他進程使用,使用完后又送回。這種恢復方式一般比較困難而且有些簡單粗暴,並不可取。

通過回滾進行恢復

如果系統設計者和機器操作員知道有可能發生死鎖,那麼就可以定期檢查流程。進程的檢測點意味着進程的狀態可以被寫入到文件以便後面進行恢復。檢測點不僅包含存儲映像(memory image),還包含資源狀態(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測點,而是每出現一個檢測點都要把它寫入到文件中,這樣當進程執行時,就會有一系列的檢查點文件被累積起來。

為了進行恢復,要從上一個較早的檢查點上開始,這樣所需要資源的進程會回滾到上一個時間點,在這個時間點上,死鎖進程還沒有獲取所需要的資源,可以在此時對其進行資源分配。

殺死進程恢復

最簡單有效的解決方案是直接殺死一個死鎖進程。但是殺死一個進程可能照樣行不通,這時候就需要殺死別的資源進行恢復。

另外一種方式是選擇一個環外的進程作為犧牲品來釋放進程資源。

死鎖避免

我們上面討論的是如何檢測出現死鎖和如何恢復死鎖,下面我們探討幾種規避死鎖的方式

單個資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調度算法,它本身是一種死鎖的調度算法。它的模型是基於一個城鎮中的銀行家,銀行家向城鎮中的客戶承諾了一定數量的貸款額度。算法要做的就是判斷請求是否會進入一種不安全的狀態。如果是,就拒絕請求,如果請求后系統是安全的,就接受該請求。

比如下面的例子,銀行家一共為所有城鎮居民提供了 15 單位個貸款額度,一個單位表示 1k 美元,如下所示

城鎮居民都喜歡做生意,所以就會涉及到貸款,每個人能貸款的最大額度不一樣,在某一時刻,A/B/C/D 的貸款金額如下

上面每個人的貸款總額加起來是 13,馬上接近 15,銀行家只能給 A 和 C 進行放貸,可以拖着 B 和 D、所以,可以讓 A 和 C 首先完成,釋放貸款額度,以此來滿足其他居民的貸款。這是一種安全的狀態。

如果每個人的請求導致總額會超過甚至接近 15 ,就會處於一種不安全的狀態,如下所示

這樣,每個人還能貸款至少 2 個單位的額度,如果其中有一個人發起最大額度的貸款請求,就會使系統處於一種死鎖狀態。

這裏注意一點:不安全狀態並不一定引起死鎖,由於客戶不一定需要其最大的貸款額度,但是銀行家不敢抱着這種僥倖心理。

銀行家算法就是對每個請求進行檢查,檢查是否請求會引起不安全狀態,如果不會引起,那麼就接受該請求;如果會引起,那麼就推遲該請求。

類似的,還有多個資源的銀行家算法,讀者可以自行了解。

破壞死鎖

死鎖本質上是無法避免的,因為它需要獲得未知的資源和請求,但是死鎖是滿足四個條件后才出現的,它們分別是

  • 互斥
  • 保持和等待
  • 不可搶佔
  • 循環等待

我們分別對這四個條件進行討論,按理說破壞其中的任意一個條件就能夠破壞死鎖

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個進程獨佔,那麼死鎖肯定不會產生。如果兩個打印機同時使用一個資源會造成混亂,打印機的解決方式是使用 假脫機打印機(spooling printer) ,這項技術可以允許多個進程同時產生輸出,在這種模型中,實際請求打印機的唯一進程是打印機守護進程,也稱為後台進程。後台進程不會請求其他資源。我們可以消除打印機的死鎖。

後台進程通常被編寫為能夠輸出完整的文件后才能打印,假如兩個進程都佔用了假脫機空間的一半,而這兩個進程都沒有完成全部的輸出,就會導致死鎖。

因此,盡量做到盡可能少的進程可以請求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進程請求其他資源,我們就能夠消除死鎖。一種實現方式是讓所有的進程開始執行前請求全部的資源。如果所需的資源可用,進程會完成資源的分配並運行到結束。如果有任何一個資源處於頻繁分配的情況,那麼沒有分配到資源的進程就會等待。

很多進程無法在執行完成前就知道到底需要多少資源,如果知道的話,就可以使用銀行家算法;還有一個問題是這樣無法合理有效利用資源

還有一種方式是進程在請求其他資源時,先釋放所佔用的資源,然後再嘗試一次獲取全部的資源。

破壞不可搶佔條件

破壞不可搶佔條件也是可以的。可以通過虛擬化的方式來避免這種情況。

破壞循環等待條件

現在就剩最後一個條件了,循環等待條件可以通過多種方法來破壞。一種方式是制定一個標準,一個進程在任何時候只能使用一種資源。如果需要另外一種資源,必須釋放當前資源。對於需要將大文件從磁帶複製到打印機的過程,此限制是不可接受的。

另一種方式是將所有的資源統一編號,如下圖所示

進程可以在任何時間提出請求,但是所有的請求都必須按照資源的順序提出。如果按照此分配規則的話,那麼資源分配之間不會出現環。

儘管通過這種方式來消除死鎖,但是編號的順序不可能讓每個進程都會接受。

其他問題

下面我們來探討一下其他問題,包括 通信死鎖、活鎖是什麼、飢餓問題和兩階段加鎖

兩階段加鎖

雖然很多情況下死鎖的避免和預防都能處理,但是效果並不好。隨着時間的推移,提出了很多優秀的算法用來處理死鎖。例如在數據庫系統中,一個經常發生的操作是請求鎖住一些記錄,然後更新所有鎖定的記錄。當同時有多個進程運行時,就會有死鎖的風險。

一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分為兩個階段,一階段是進程嘗試一次鎖定它需要的所有記錄。如果成功后,才會開始第二階段,第二階段是執行更新並釋放鎖。第一階段並不做真正有意義的工作。

如果在第一階段某個進程所需要的記錄已經被加鎖,那麼該進程會釋放所有鎖定的記錄並重新開始第一階段。從某種意義上來說,這種方法類似於預先請求所有必需的資源或者是在進行一些不可逆的操作之前請求所有的資源。

不過在一般的應用場景中,兩階段加鎖的策略並不通用。如果一個進程缺少資源就會半途中斷並重新開始的方式是不可接受的。

通信死鎖

我們上面一直討論的是資源死鎖,資源死鎖是一種死鎖類型,但並不是唯一類型,還有通信死鎖,也就是兩個或多個進程在發送消息時出現的死鎖。進程 A 給進程 B 發了一條消息,然後進程 A 阻塞直到進程 B 返迴響應。假設請求消息丟失了,那麼進程 A 在一直等着回復,進程 B 也會阻塞等待請求消息到來,這時候就產生死鎖

儘管會產生死鎖,但是這並不是一個資源死鎖,因為 A 並沒有佔據 B 的資源。事實上,通信死鎖並沒有完全可見的資源。根據死鎖的定義來說:每個進程因為等待其他進程引起的事件而產生阻塞,這就是一種死鎖。相較於最常見的通信死鎖,我們把上面這種情況稱為通信死鎖(communication deadlock)

通信死鎖不能通過調度的方式來避免,但是可以使用通信中一個非常重要的概念來避免:超時(timeout)。在通信過程中,只要一個信息被發出后,發送者就會啟動一個定時器,定時器會記錄消息的超時時間,如果超時時間到了但是消息還沒有返回,就會認為消息已經丟失並重新發送,通過這種方式,可以避免通信死鎖。

但是並非所有網絡通信發生的死鎖都是通信死鎖,也存在資源死鎖,下面就是一個典型的資源死鎖。

當一個數據包從主機進入路由器時,會被放入一個緩衝區,然後再傳輸到另外一個路由器,再到另一個,以此類推直到目的地。緩衝區都是資源並且數量有限。如下圖所示,每個路由器都有 10 個緩衝區(實際上有很多)。

假如路由器 A 的所有數據需要發送到 B ,B 的所有數據包需要發送到 D,然後 D 的所有數據包需要發送到 A 。沒有數據包可以移動,因為在另一端沒有緩衝區可用,這就是一個典型的資源死鎖。

活鎖

你會發現一個很有意思的事情,死鎖就跟榆木腦袋一樣,不會轉彎。我看過古代的一則故事:

如果說死鎖很痴情的話,那麼活鎖用一則成語來表示就是 弄巧成拙

某些情況下,當進程意識到它不能獲取所需要的下一個鎖時,就會嘗試禮貌的釋放已經獲得的鎖,然後等待非常短的時間再次嘗試獲取。可以想像一下這個場景:當兩個人在狹路相逢的時候,都想給對方讓路,相同的步調會導致雙方都無法前進。

現在假想有一對并行的進程用到了兩個資源。它們分別嘗試獲取另一個鎖失敗后,兩個進程都會釋放自己持有的鎖,再次進行嘗試,這個過程會一直進行重複。很明顯,這個過程中沒有進程阻塞,但是進程仍然不會向下執行,這種狀況我們稱之為 活鎖(livelock)

飢餓

與死鎖和活鎖的一個非常相似的問題是 飢餓(starvvation)。想象一下你什麼時候會餓?一段時間不吃東西是不是會餓?對於進程來講,最重要的就是資源,如果一段時間沒有獲得資源,那麼進程會產生飢餓,這些進程會永遠得不到服務。

我們假設打印機的分配方案是每次都會分配給最小文件的進程,那麼要打印大文件的進程會永遠得不到服務,導致進程飢餓,進程會無限制的推后,雖然它沒有阻塞。

總結

死鎖是一類通用問題,任何操作系統都會產生死鎖。當每一組進程中的每個進程都因等待由該組的其他進程所佔有的資源而導致阻塞,死鎖就發生了。這種情況會使所有的進程都處於無限等待的狀態。

死鎖的檢測和避免可以通過安全和不安全狀態來判斷,其中一個檢測方式就是銀行家算法;當然你也可以使用鴕鳥算法對死鎖置之不理,但是你肯定會遭其反噬。

也可以在設計時通過系統結構的角度來避免死鎖,這樣能夠預防死鎖;也可以破壞死鎖的四個條件來破壞死鎖。資源死鎖並不是唯一性的死鎖,還有通信間死鎖,可以設置適當的超時時間來完成。

活鎖和死鎖的問題有些相似,它們都是一種進程無法繼續向下執行的狀態。由於進程調度策略導致嘗試獲取進程的一方永遠無法獲得資源后,進程會導致飢餓的出現。

尾聲

提出一個勘誤,已反饋給出版社

關於我

我自己現在寫了三本 PDF,讀者回復都非常不錯,現在免費分享出來,關注我的公眾號即可領取

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

自已做動畫及編寫程序搞清楚最大堆的實現原理

目錄

  • 背景
  • 概念
  • 最大堆
    • 最大堆的線性存儲
    • 動畫實現最大堆加入新元素
    • 代碼實現最大堆加入新元素
    • 動畫實現最大堆取出最大元素
    • 代碼實現最大堆取出最大元素
    • 程序測試
  • 最大堆的應用–優先隊列
  • 寫在最後

背景

  • 二叉樹是數據結構中的重點,也是難點。二叉樹比數組、棧、隊列等線性結構相比複雜度更高,想要做到心中有“樹”,需要自己動手畫圖、觀察、思考,才能領會其真諦。
  • 在上篇文章《自己動手作圖深入理解二叉樹、滿二叉樹及完全二叉樹》中,我們對完全二叉樹有了一定認識,該文將對一種特殊的完全二叉樹”最大堆”進行底層研究。

概念

堆(heap)通常是一個可以被看做一棵二叉樹的數組對象。堆總是滿足下列性質:

  • 堆總是一棵完全二叉樹。
  • 堆中某個節點的值總是不大於或不小於其父節點的值;

最大堆

  • 根節點最大的堆叫做最大堆
最大堆的線性存儲
  • 由於堆是一種特殊的完全二叉樹,可以利用數組集合形成線性存儲的數據結構。
/**
 * 最大堆的底層實現--數組集合形成線性存儲的數據結構
 *  * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的數組集合
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 得到左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 得到右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 得到父結點索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }
}
動畫實現最大堆加入新元素
  • 加入到數組集合尾部的元素與父結點進行比較,通過上浮操作,保證所有子結點不能大於父結點。
代碼實現最大堆加入新元素
/**
 * 最大堆的底層實現
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的數組集合
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 得到左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 得到右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 得到父結點索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }

    // 添加元素
    public void add(E e) {
        this.list.add(e);
        /**
         * 將加入的結點與父結點進行比較:
         * 如果加入的結點大於父結點,則進行上浮
         * 直至新結點小於或等於父結點為止
         */

        // 獲取當前添加元素在數組中的索引
        int i = this.list.size() - 1;
        while (i > 0) {
            E current = this.list.get(i);
            E parent = this.list.get(getParentIndex(i));
            // 如果父結點元素大於當前加入的元素,則進行交換
            if (parent.compareTo(current) < 0) {
                // 交換新加入的結點與父結點的位置
                Collections.swap(this.list, i, getParentIndex(i));
            } else {
                break;
            }
            i = getParentIndex(i);
        }
    }
    
}
動畫實現最大堆取出最大元素
  • 獲取最大堆中的根結點,即為最大元素;並把尾部結點放置到根結點,並通過下沉操作,把子結點中的最大元素移動根結點。
代碼實現最大堆取出最大元素
/**
 * 最大堆的底層實現
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeap<E extends Comparable<E>> {

    // 存放元素的數組集合
    private ArrayList<E> list;

    MaxHeap() {
        this.list = new ArrayList<>();
    }

    // 得到左孩子索引
    private int getLeftChildIndex(int i) {
        return (2 * i + 1);
    }

    // 得到右孩子索引
    private int getRightChildIndex(int i) {
        return (2 * i + 2);
    }

    // 得到父結點索引
    private int getParentIndex(int i) {
        if (i == 0) {
            throw new IllegalArgumentException("非法索引值");
        } else {
            return ((i - 1) / 2);
        }
    }

    // 查找最大元素
    public E findMax() {
        if (this.list.size() == 0) {
            return null;
        }
        // 最大堆中的元素永遠在根結點
        return this.list.get(0);
    }

    // 取出最大元素
    public E getMax() {
        if (findMax() != null) {
            E e = findMax();

            /**
             * 取出最大元素后,需要把堆中第二大的元素放置在根結點:
             * 將根結點元素與最後面的元素進行交換,
             * 讓最後面的元素出現在根結點,並移除最大元素
             * 將根結點的元素與左右孩子結點比較,直至根結點的元素變成最大值
             */
            int i = 0;
            Collections.swap(this.list, i, this.list.size() - 1);
            this.list.remove(this.list.size() - 1);

            // 通過循環進行當前結點與左右孩子結點的大小比較
            while (getLeftChildIndex(i) < this.list.size() && getRightChildIndex(i) < this.list.size()) {
                int leftIndex = getLeftChildIndex(i);
                int rightIndex = getRightChildIndex(i);

                // 通過比較左右孩子的元素哪個較大,確定當前結點與哪個孩子進行交換
                int index = this.list.get(leftIndex).compareTo(this.list.get(rightIndex)) > 0 ? leftIndex : rightIndex;
                if (this.list.get(i).compareTo(this.list.get(index)) < 0) {
                    Collections.swap(this.list, i, index);
                } else {
                    // 如果當前結點都大於左右孩子,則結束比較
                    break;
                }
                i = index;
            }

            return e;
        } else {
            return null;
        }
    }
}

程序測試
/**
 * 最大堆的底層實現--測試程序
 *
 * @author zhuhuix
 * @date 2020-06-28
 */
public class MaxHeapTest {
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<>();

        // 將10個数字加入形成最大堆
        int[] arrays = {19,29,4,2,27,0,38,15,12,31};
        for (int i = 0; i < arrays.length; i++) {
            maxHeap.add(arrays[i]);
        }

        // 依次從堆中取出最大值
        for (int i = 0; i < arrays.length; i++) {
            System.out.println("第"+(i+1)+"次取出堆目前的最大值:"+maxHeap.getMax());
        }
    }
}

最大堆的應用–優先隊列

優先隊列:出隊的和順序與入隊的順序無關,只與優先級相關;
優先隊列通常可以採用最大堆的數據結構來實現。

/**
 * 用最大堆的數據結構實現優先隊列
 * 
 * @author zhuhuix
 * @date 2020-06-28
 */
public class PriorityQueue<E extends Comparable<E>>  {
    private MaxHeap<E> mhp;
    PriorityQueue() {
        mhp=new MaxHeap<>();
    }

    // 入隊
    public void enqueue(E e) {
        mhp.add(e);
    }

    // 優選級最高的元素出隊
    public E dequeue() {
        return mhp.getMax();
    }

    // 查看優先級最高的元素
    public E getFront() {
        return mhp.findMax();
    }
}

寫在最後

  • 以上通過畫圖、動畫演示、代碼編寫對堆與最大堆的概念和底層實現方式,都作了深入分析;作為最大堆的反向結構,最小堆的實現也是一樣,讀者可參考以上動畫和代碼,動手練習。
  • 畫圖、編碼不易,請點贊、收藏、關注三連!!!

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

※超省錢租車方案

日本國土百萬年的惡夢 每日數百噸的福島輻射污染水

文:宋瑞文(媽媽監督核電廠聯盟特約撰述)

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

印度環境部長:解決首都空污時間 會比北京短

摘錄自2019年11月23日中央通訊社印度報導

印度環境、森林與氣候變遷部部長賈瓦德卡爾昨天(22日)在印度國會下院答詢時聲稱,空污需要大規模運動來解決,「北京花了15年的時間,我們將花費更少時間(解決空污問題)」。

印度包含新德里在內國家首都區每年冬天因農民焚燒農田殘梗、車輛排放、建築工地揚塵、6000家餐廳用炭火燒烤雞肉、窮人焚燒垃圾取暖等諸多因素,陷入嚴重空氣污染,但印度政府一直無法拿出有效解決對策。空污在今年11月更有惡化趨勢,引發民眾不滿。

賈瓦德卡爾指出,政府已針對城市制定監測空氣污染計畫,目前在全印度355個城市監測空污。此外,政府正每天展開工作以消除空污威脅,包括2018年啟用東、西部外環高速公路,且已把碳排放降低了22%;在第6期汽車廢氣排放標準(BS VI)明年4月實施後,汽車廢氣排放量將可減少80%。

他還把空污問題與氣候變遷聯繫起來,並說印度的總發電量在2030年之前,將有40%是來自可再生能源;而且印度的綠地覆蓋率不斷增加,使印度成為可達到綠地覆蓋率標準的少數國家之一,更五度在國家首都區種植更多樹木,以替代因興建地鐵而砍伐掉的樹木。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

新北清潔公司,居家、辦公、裝潢細清專業服務

澳洲森林大火 空污程度空前

摘錄自2019年11月22日中央通訊社澳洲報導

澳洲新南威爾斯省遍布森林野火,飄散出的煙霧使今天(22日)空污程度空前,造成就醫人數激增,並引起駕駛人視線不良等危險。

澳洲人口第一大城雪梨(Sydney)已連續4天被煙霧籠罩,罕見但一再成為世界空污最嚴重的10大城市之一。近幾天來某些時候,全球城市空氣品質監測網站Air Visual排行顯示,雪梨名列世界空污最嚴重的第8大城市,排名在雅加達及深圳之前,位居孟買之後。

隨著強風吹送林火煙霧以及因全澳3年乾旱而堆積的灰塵,波克鎮的空污比安全標準高出15倍。煙霾挾帶著來懸浮微粒污染物,形成官員所說新南威爾斯省紀錄中的最嚴重污染。這種粒子會被人體吸入血液中。

大火迄今仍在新南威爾斯省、維多利亞省(Victoria)、南澳省(South Australia)及昆士蘭省(Queensland)燃燒。澳洲總理莫里森(Scott Morrison)因為這次危機而受到壓力,批評者指稱,莫里森並未盡力處理氣候變遷的衝擊。氣象學家則指出,氣候變遷正導致野火季節的時間延長。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

馬來西亞最後一頭蘇門答臘犀牛病逝 全球剩80頭

摘錄自2019年11月24日中央通訊社馬來西亞報導

馬來西亞最後一隻蘇門答臘犀牛,25歲的母犀牛伊曼自2014年被捕獲後,一直在野生動物保護區接受妥善照顧,牠今天(24日)因癌病逝於婆羅洲(Borneo)沙巴(Sabah)。沙巴野生動物部門(Sabah Wildlife Department)主任奧古斯丁(Augustine Tuuga)說:「伊曼的死亡比預期要快,但我們知道,牠已經開始承受極大痛苦。」

蘇門答臘犀牛是體型最小的犀牛,曾廣布亞洲各地,野生蘇門答臘犀牛如今已近乎絕種,據保育人士估計,目前全球僅剩約30至80頭,大多棲息在蘇門答臘和印尼所管轄的婆羅洲地區。馬來西亞2015年宣布野生蘇門答臘犀牛絕種,最後一頭公蘇門答臘犀牛今年5月離世。

保育團體國際犀牛基金會(International Rhino Foundation)說,棲地減少和盜獵導致蘇門答臘犀牛生存於孤立區域,代表牠們繁衍困難,數十年內可能就會滅絕。

自2011年以來,馬來西亞不斷嘗試以體外受精方式,繁殖人工飼養的蘇門答臘犀牛,但迄今尚未成功。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

韓國入冬後空氣污染物八成來自中國

摘錄自2019年11月21日大紀元報導

韓、日、中三國對大氣污染物流動的共同研究顯示,韓國境內有高達三成的細懸浮污染物(PM2.5)來自中國,入冬後這個數字更飆高至八成。

據韓聯社報導,韓國環境部下屬國立環境科學院20日發布報告概要指,韓日主要城市由國內因素導致污染的比例分別為51%和55%,而中國是91%。

從國外成因來看,韓國的空氣污染物中,來自中日兩國的各占32%和2%,其餘來自朝鮮、蒙古、東南亞等地區。從韓日兩國流入中國的空氣污染物比重分別僅占2%和1%,從韓中兩國流入日本的比重分別為8%和25%。

然而,如果將時間範圍限定在12月至3月,中國的空氣污染物對韓國的影響更為嚴重。據韓國國立環境科學院的調查,今年1月11日至15日韓國空氣污染物中只有18%至31%來自國內因素,其餘69%至82%來自國外,其中中國占絕大多數。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

違法噴灑遭禁殺蟲劑 孟山都將付3億罰款

摘錄自2019年11月22日中央通訊社美國報導

美國農業生技巨擘孟山都(Monsanto)今天(22日)同意認罪,承認在夏威夷毛伊島(Maui)的設施對研究作物違法噴灑遭禁的劇毒殺蟲劑,將支付1000萬美元(約新台幣3億532萬元)罰款。

法新社報導,孟山都在提交給檀香山聯邦地區法院的法庭文件中承認,2014年在農場谷(Valley Farm)對玉米種子等作物噴灑Penncap-M殺蟲劑,即使已知環境保護署於2013年禁用這款化學物。

審理此案的加州中區聯邦檢察官韓納(Nick Hanna)說:「此案的違法行徑對環境、周圍社區和孟山都工人構成威脅。」他說:「聯邦法律與相關規範規定,使用管制和危險化學物的每個人,都有責任確保產品是經過安全儲存、運送與使用。」

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

南投搬家前需注意的眉眉角角,別等搬了再說!

新北清潔公司,居家、辦公、裝潢細清專業服務

新宿市民測定所 發表嬰幼兒奶粉輻射檢查報告

文:宋瑞文(媽媽監督核電廠聯盟特約撰述)

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※想知道最厲害的網頁設計公司"嚨底家"!

※幫你省時又省力,新北清潔一流服務好口碑

※別再煩惱如何寫文案,掌握八大原則!

一口氣投80億人民幣 比亞迪建長沙、青島兩個新能源車生產基地

比亞迪汽車於5月18日與湖南省長沙市雨花區經開區簽署合作備忘錄,比亞迪將投資50億元人民幣(下同),在長沙比亞迪汽車城二期興建電動卡車及專用車生產基地,計畫年內投產。   長沙比亞迪專案將由電動轎車、電動客車和電動卡車及專用車三部分組成。電動卡車及專用車專案,現已動工建設,是比亞迪電動卡車及專用車全球製造中心,含整車及相應配套零部件,目標向全中國工廠提供電動底盤、車橋等核心部件。比亞迪預計2016年將達產2500輛,規劃至2020年達5000輛年產能,2025年擴建到10000輛年產能。   此外,比亞迪在青島市城陽區投資30億元的新能源汽車專案一期目前已開工建設,這是青島城陽首個新能源汽車產業專案,也是建區以來引進的最大工業專案。根據規劃分三期建設完成,預計2017年全部建成。專案全部建成後,將年產電動汽車5000輛,年可實現銷售收入105億元。   此專案位於棘洪灘軌道交通裝備製造產業園內,規劃佔地1000畝,主要生產純電動轎車、中巴、小巴、物流車等產品,以及從事車輛電池、電機、電控等核心零部件的研發和製造。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?