互斥演算法的效能指標

---

互斥是一個程式物件，它與以下條件相關：不允許兩個併發程序同時處於同一臨界區。它用於防止發生競爭條件。如果當前程序正在訪問臨界區，則它會阻止其他併發程序進入該區域。簡而言之，在任何一個時刻，只有一個程序被授權執行臨界區。

互斥的效能指標有哪些？

程式物件互斥描述了不允許兩個併發程序同時在一個臨界區中執行的需求。它被提出用於服務於競爭環境。如果當前程序正在使用臨界區，則其他併發程序無法訪問它。換句話說，在任何一個時刻，只有一個程序被允許執行臨界功能。

執行分散式互斥的通用方法

基於令牌的技術

基於令牌的方法透過站點共享一個特殊的授權（也稱為許可權訊息）。只要站點擁有令牌，就可以訪問其臨界區，並在臨界區完成之前保留令牌。由於令牌是唯一的，因此可以確保互斥。從這個角度來看，演算法與網站提供搜尋令牌的方式有著根本的不同。在令牌環演算法中，令牌在程序或執行緒的環形結構中依次傳遞。只有擁有令牌的程序或執行緒才能訪問共享資源。集中式令牌演算法利用中央機構來處理令牌分發。分散式令牌演算法以去中心化的方式在程序或執行緒之間分發令牌。

非基於令牌的技術

為了選擇哪個站點將接下來到達臨界區，站點之間至少需要傳送兩輪增量通訊。當由其本地寫入器宣告的公告發生時，站點進入臨界區。基於仲裁的方法 - 在基於仲裁的策略中，每個站點都必須獲得一個站點的重要子集（稱為仲裁）的批准。當兩個站點同時請求訪問臨界區時，仲裁旨在確保在任何一個時刻只有一個請求填充臨界區。

四個指標

為了評估互斥擴充套件中指標的成功，可以使用許多效能指標。此數字表示程式嘗試訪問必須從磁碟調入的頁面的次數，因為該頁面實際上不在記憶體中。如果頁面失效率過高，則系統可能花費過多的時間將頁面交換進出記憶體，這可能會影響系統性能。以下是互斥擴充套件的指標。

訊息複雜度

透過網站完成 CS 所需的訊息數量。訊息複雜度表示可以在任何給定邊緣上傳輸的最大訊息數。分散式演算法的時間複雜度通常定義為直到最終節點完成該過程的輪數。

同步延遲

站點離開 CS 到下一個站點到達 CS 之間的時間間隔。同步延遲被測量為平均訊息延遲 T [8]，並且是站點離開 CS 到下一個站點加入 CS 之間的時間間隔。存在基於令牌或非基於令牌的分散式互斥演算法。

響應時間

傳送查詢訊息到 CS 後完成請求所需的時間。響應時間包括提交請求、在計算機中處理請求以及將結果傳送回終端所需的時間。反應時間通常用於評估智慧系統的效能。

系統效率

（CS）是系統滿足需求的速率。必須構建作業系統以允許快速開發、測試和實施新的系統功能，同時保持服務。

低負載和高負載效能

負載由完成關鍵部分的傳入請求數表示。低負載發生在每個關鍵區域有多個請求時。當持續存在掛起的請求時，就會發生高負載。如果發生高負載，則在請求完成後，站點會立即開始操作以滿足下一個關鍵需求。在高負載條件下，目標僅在極少數情況下處於非活動狀態。簡單的數學推理可用於有效地記錄幾種互斥演算法在低負載和高負載下的效能測量結果。總的來說，低負載和高負載效能指標對於評估系統或應用程式的可靠性和有效性都至關重要，因為它們闡明瞭系統在各種使用場景下的執行方式以及如何對其進行最佳化以適應不斷增長的需求。

互斥的要求

不應該有死鎖：站點不應該無限期地等待掛起的訊息到來。

沒有飢餓

需要一個閾值，低於該閾值，一個站點不能重複執行臨界區，而另一個站點則等待而不執行臨界區。

容錯

它應該自動識別自己的故障，並繼續操作，幾乎沒有中斷。作業系統對硬體或軟體故障做出響應的過程稱為容錯。根據此定義，容錯是指系統即使在出現錯誤或故障時也能繼續執行的能力。

指標對互斥的有效性有什麼影響？

互斥演算法通常提供最優和最差效能特徵。在最佳情況下，增益條件有利，使得效能指標達到最大值。大多數常見禁止計算的最佳反應時間估計是 2T E-返回訊息延遲以及關鍵段執行時間。在互斥演算法中，最佳和最差情況通常分別對應於低負載和高負載。例如，當負載極低和極高時，可以分別獲得最佳和最差響應時間；在某些互斥演算法中，當負載極低和極高時，可以分別建立最佳和最差訊息流量。所選指標會極大地影響互斥演算法的有效性。

例如，如果指標側重於減少系統的平均響應時間，則互斥方法可能會優先考慮快速鎖定獲取。這可能會導致爭用增加，並且某些程序的等待時間更長。另一方面，如果指標側重於最大化吞吐量，則互斥方法可能會優先考慮允許更多程序同時進入其臨界區，這可能會導致更多衝突和更長的總執行時間。

結論

互斥演算法幾乎總是提供最優和最差效能的指標。在最佳情況下，獲勝條件非常有利，使得關鍵效能指標達到最大值。正在處理對關鍵部分的訪問請求。在非基於令牌的方法中，時間戳的順序很重要。因此，確保了公平性。在與基於令牌的演算法相比時，它們在互動中的公平性。非基於令牌的演算法需要訊息。沒有完美的演算法，因為每個演算法都有優點和缺點。它不是基於令牌的，因此不需要令牌來訪問 CS。這種方法被稱為基於許可權的演算法。