資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學硬體同步
在硬體同步中，我們探索了更多解決臨界區問題的方案，這些方案使用了從基於硬體到基於軟體的API等多種技術，這些API可供應用程式程式設計師使用。這些解決方案基於鎖定的前提；但是，此類鎖的設計可能非常複雜。
這些硬體特性可以簡化任何程式設計任務並提高系統效率。在這裡，我們介紹一些許多系統上都可用的簡單硬體指令，並展示如何有效地使用它們來解決臨界區問題。如果我們能夠防止在修改共享變數時發生中斷，則可以在單處理器環境中簡單地解決臨界區問題。透過這種方式，我們可以確保當前指令序列能夠按順序執行而不會被搶佔。不會執行其他指令，因此不會對共享變數進行意外修改。非搶佔式核心採用的就是這種方法。但不幸的是，這種解決方案在多處理器環境中並不那麼可行。由於訊息被傳遞到所有處理器，因此在多處理器上停用中斷可能非常耗時。
當此訊息傳遞延遲進入每個臨界區時，系統效率會降低。如果時鐘由中斷保持更新，則還會考慮對系統時鐘的影響。因此，許多現代計算機系統都提供特殊的硬體指令，允許我們以原子方式測試和修改字的內容或交換兩個字的內容——也就是說，作為一個不可中斷的單元。我們可以使用這些特殊指令以相對簡單的方式解決臨界區問題。現在我們抽象出這些指令背後的主要概念。TestAndSet() 指令可以定義如下所示。
boolean test and set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}TestAndSet() 指令的定義。
其基本特徵是此指令以原子方式執行。因此，如果同時執行兩個 TestAndSet() 指令（每個指令在不同的 CPU 上），則它們將按某種任意順序順序執行。如果機器支援 TestAndSet() 指令，我們可以透過宣告一個初始化為 false 的布林變數 lock 來實現互斥。程序 P 的結構如下所示。
示例
do {
while (test and set(&lock)) ;
/* do nothing */
/* critical section */
lock = false;
/* remainder section */
}
while (true);使用 TestAndSet() 實現互斥。
與 TestAndSet() 指令相反，Swap() 指令操作於兩個字的內容；它以原子方式執行。如果機器支援 Swap() 指令，則可以如下提供互斥。這裡，宣告一個全域性布林變數 lock 並將其初始化為 false。此外，每個程序都有一個區域性布林變數 key。程序 P 的結構如下圖所示。
int compare_and_swap(int *val, int expected, int new val){
int temp = *val;
if (*val == expected)
*val = new val;
return temp;
}Compare and Swap() 指令的定義。
do{
while (compare_and_swap(&lock, 0, 1) != 0) ;
/* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
while (true);使用 Compare and Swap() 指令實現互斥。
由於這些演算法滿足互斥要求，因此它們不滿足有界等待要求。在下面的程式碼中，我們介紹了另一個使用 TestAndSet() 指令的演算法，該演算法滿足所有臨界區要求。
do{
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test and set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
}
while (true);使用 TestAndSet() 實現有界等待互斥。
相同的資料結構是 boolean waiting[n]; boolean lock; 這些資料結構初始化為 false。為了證明滿足互斥要求，我們注意到程序 P; 只有當 waiting[i] == false 或 key == false 時才能進入其臨界區。只有當執行 TestAndSet() 時，key 的值才能變為 false。第一個執行 TestAndSet() 的程序將發現 key == false；所有其他程序都必須等待。只有當另一個程序離開其臨界區時，變數 waiting[i] 才能變為 false；只有一個 waiting[i] 設定為 false，從而保持互斥要求。
為了證明滿足進展要求，我們注意到為互斥提出的論點也適用於此，因為程序退出臨界區要麼將 lock 設定為 false，要麼將 waiting[j] 設定為 false。兩者都允許等待進入其臨界區的程序繼續執行。為了證明滿足有界等待要求，我們注意到，當一個程序離開其臨界區時，它會以迴圈順序 (i + 1, i + 2,..., n - 1, 0, ..., i - 1) 掃描陣列 waiting。它將此順序中第一個處於入口段 (waiting[j] == true) 的程序指定為下一個進入臨界區的程序。
任何等待進入其臨界區的程序都將在 n - 1 個輪次內這樣做。不幸的是，對於硬體設計人員而言，在多處理器上實現原子 TestAndSet() 指令並非易事。
14K+ 次瀏覽
