2009-07-22 113 views
32

在多任務系統中,一些異常情況會阻止執行進程或線程的進度。我將把進程和線程簡單地稱爲「進程」。其中兩個條件稱爲死鎖和活鎖。什麼是飢餓?

前者指的是互相阻塞的進程,因此阻止執行。後者是指阻止彼此進展的過程,但並不實際阻止執行。例如,他們可能會不斷導致對方回滾交易,而且無法完成交易。

另一種情況稱爲資源匱乏,其中進程進程所需的一個或多個有限資源已被其耗盡,並且除非進程進展,否則無法恢復。這也是活鎖的特例。

我想知道是否有任何其他定義,特別是學術定義,因爲「飢餓」不限於「資源匱乏」。特別歡迎參考。

而且,不,這不是家庭作業。 :-)

+4

雖然你在這個問題上,你也應該檢查鎖定車隊,他們是非常有趣的。和討厭。 http://en.wikipedia.org/wiki/Lock_convoy – 2009-07-22 23:45:44

+0

即使它是作業,這將是我見過的最好的家庭作業問題。 – 2017-12-14 23:12:31

回答

26

我不會說資源匱乏是一個活鎖的特例。通常:

  • 在活鎖中,沒有線程取得進展,但它們仍在執行。 (在死鎖狀態下,它們甚至不會繼續執行)

  • 當飢餓時,某些線程進行中並且某些線程未執行。

一個很好的解釋:http://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html。但我明白朮語的選擇可能會有所不同。

當談到飢餓,我聽到的定義是:

假設它是可以指定執行(隔行掃描)的無限路徑與假設一致(旗語語義,OS調度器的行爲...),使得線程T暫停等待一些資源,並且不會恢復,即使可能無限多次。然後T被稱爲捱餓。

但是,這種做法不符。假設兩個線程在無限循環中執行關鍵部分。您的同步代碼允許第一個線程每小時進入一次關鍵部分。它餓嗎?這兩個線程都允許進行,但第一個線程正在慢慢地完成它的工作。

最簡單的飢餓來源是弱信號量。如果您使用的行爲相似的同步原語(或構建您自己的),則會導致飢餓。

經典問題在那裏飢餓是衆所周知的:

有關詳細信息,我衷心推薦信號燈的小書(免費):http://www.greenteapress.com/semaphores/

你在問是否每個飢餓都是由於等待一些資源而引起的。我會說 - 是的。

一個線程可以被掛起:

(1)上的一些阻塞系統調用 - 等待/獲取互斥,旗語,條件變量; write(),poll()等。

(2)關於某些非阻塞操作 - 就像執行計算。

(1)上的飢餓在資源(互斥,緩衝等)上捱餓。 (2)上的捱餓在CPU上捱餓 - 你可以把它當作資源。如果發生,問題在於調度程序。

HTH

1

工作也是一種資源。當生產者 - 消費者設置中的工作分配不公平(或理想)時,某些線程可能無法獲得足夠的工作項目來保證它們始終處於忙碌狀態。

38

想象一下,您正排隊在餐廳購買食物,孕婦優先考慮。還有一大批孕婦一直到來。

你很快就會捱餓。 ;)

現在想象你是一個低優先級的過程,孕婦是高優先級的過程。 =)

+0

可笑但最好的解釋 – user8027365 2018-02-09 18:32:03

12

在討論優先級調度算法時,通常會出現飢餓或「不確定阻塞」的另一個領域。優先級調度算法有可能使一些低優先級進程無限期地等待。穩定的高優先級進程可以防止低優先級進程的運行。

在優先級調度程序的情況下,解決方案是「老化」。老化是逐漸增加在系統中等待很長時間的進程的優先級的技術。

6

飢餓就是當一個進程或服務沒有被服務時,即使系統沒有死鎖。

這是我剛剛爲澄清目的而編寫的一個示例。

想象一下控制計算機訪問WAN或類似的算法。這個算法可能有一個策略,說「提供優先訪問那些將使用較少帶寬的計算機」,這看起來像是一個合適的策略,但是當單臺計算機想要訪問網絡以獲取ftp上傳時會發生什麼情況在某處發送幾個GB。僅憑這一政策,該計算機就會捱餓,因爲該算法永遠不會選擇該計算機,因爲總會有其他計算機請求較小的帶寬使用量。

這就是所謂的飢餓。

1

舉一個例子,在java中鎖定飢餓。這是關於線程優先級的。不知道這個例子是否好,但你可以看看here

0

進程無法獲得更長時間的資源或資源。這不是一個僵局,因爲一個進程沒有問題。 老化可以用來解決這個問題,老化因素用於每個請求。