嵌入式系統/執行緒與同步

多工和多執行緒是計算史上最有用的一次發展。這種技術並不總是對嵌入式系統工程師可用，但一些嵌入式系統和 RTOS 具有多執行緒 (MT) 能力。本節中的章節將討論 MT 的一些用途，並將討論與 MT 程式設計相關的一些常見陷阱。本頁僅作為多執行緒程式設計的簡要參考。

搶佔式多執行緒

當第一個多工系統建立時，它們沒有中央控制器。多工是透過讓程式自願地放棄對系統的控制來建立的，然後系統會將控制權交給另一個程序。這種系統執行得相當好，除了任何行為不端的程式都會減慢整個系統的速度。例如，如果一個程式陷入無限迴圈，它永遠不會放棄控制權，系統就會凍結。

解決這個問題的辦法是搶佔式多執行緒。在搶佔式環境中，可以隨時將控制權從一個程序轉移到另一個程序。被“搶佔”的程序甚至不會知道發生了任何事情，除了可能在 2 條指令之間出現比平時更大的延遲。搶佔式多執行緒允許程式不主動放棄控制權，也允許計算機在單個程序掛起時繼續執行。

與搶佔式多執行緒相關的許多問題都源於這樣一個事實，即當一個程序沒有準備好放棄控制權時，控制權會被從它手中奪走。例如，如果一個程序正在寫入一個記憶體位置，並且被搶佔，下一個程序將看到半寫的資料，甚至在該記憶體位置看到損壞的資料。或者，如果一個任務正在從一個輸入埠讀取資料，並且被搶佔，時間就會不對，並且資料會從該行丟失。顯然，這是不可接受的。

因此，解決這個問題的新方法是同步的概念。同步是由搶佔式多執行緒作業系統提供的一系列工具，以確保避免這些問題。同步工具可以包括計時器、“臨界區”和鎖。計時器可以確保一個給定的程序可以被搶佔，但只能在一定的時間內。臨界區是程式碼中的命令，可以防止系統在一定時間內切換控制權。鎖是命令，可以防止原子操作中的干擾。這些主題將在接下來的章節中討論。

互斥鎖

術語互斥鎖是“互斥”的簡稱，是搶佔式環境中使用的一種機制型別，可以防止對當前正在使用的資源進行未經授權的訪問。互斥鎖遵循以下幾個規則

1. 互斥鎖是系統範圍內的物件，由核心維護。
2. 互斥鎖一次只能被一個程序擁有。
3. 互斥鎖可以透過要求核心將該互斥鎖分配給當前任務來獲取。
4. 如果互斥鎖已被分配，請求函式將被阻塞，直到互斥鎖可用。

一般來說，儘快釋放互斥鎖被認為是良好的程式設計實踐。互斥鎖的一些問題將在死鎖一章中討論。

自旋鎖

自旋鎖是一種快速同步方法。它以其行為命名 - 在條件為假時迴圈自旋。為了實現自旋鎖，系統應該支援test-and-set習語或透過任何方式（遮蔽中斷、鎖定匯流排）提供對鎖定執行緒的獨佔訪問。

自旋鎖的優點是它們非常簡單。缺點是它們在迴圈等待時會浪費 CPU 週期。自旋鎖最常見的用途是同步對物件的快速訪問。在對一段程式碼進行自旋鎖時，不建議進行長時間的計算。

臨界區

臨界區是一系列計算機指令，如果被中斷，可能會出現故障。原子操作是一系列計算機指令，不能被中斷，並且可以正常執行。在實踐中，這兩個細微不同的定義通常會合並在一起。作業系統提供同步物件來滿足這些要求，並且有些實際上將這些物件稱為“臨界區”、“原子操作”或“監視器”。

臨界區的一個例子是從由中斷填充的佇列中刪除資料的程式碼。如果臨界區沒有受到保護，中斷可以在出隊函式正在更改指標時發生，並破壞佇列指標。原子操作的一個例子是 I/O 讀取，其中程序必須以特定速率讀取所有資料，並且在讀取時不能被搶佔。

一般來說，良好的程式設計實踐是讓程式儘快退出臨界區，因為長時間保持臨界區會導致系統中的其他程序無法獲得任何時間，從而導致效能大幅下降。臨界區應該謹慎使用。

優先順序排程

許多 RTOS 都有一個機制來區分不同任務的相對優先順序。高優先順序任務比低優先順序任務更頻繁地執行。但是，優先順序排程的每個實現都會略有不同。

死鎖

死鎖發生在搶佔式 MT 系統中的一系列同步物件被以這樣一種方式持有，即任何程序都無法前進。讓我們看一個例子

假設我們有 2 個執行緒：T1 和 T2。我們還有 2 個互斥鎖，M1 和 M2。

1. T1 請求並獲取互斥鎖 M1。
2. T2 獲取 M2。
3. T1 請求 M2，系統將控制權轉移到 T2，直到 T2 釋放 M2。
4. T2 請求 M1，系統陷入死鎖（兩個執行緒都不能繼續，直到另一個釋放它的互斥鎖）。

這是一個非常難以診斷的問題，也是一個更難解決的問題。本章將提供一些關於如何防止死鎖的一般性指導。

看門狗定時器

參見嵌入式系統/看門狗定時器.

在沒有鎖的情況下讀取計數器

讀取兩次並比較

也許嵌入式系統中最常見的併發演算法是“讀取計數器兩次並比較”的樂觀併發控制模式。

許多硬體計時器和硬體計數器透過 8 位匯流排連線到 CPU。如果計時器的低位元組在開始讀取計時器時恰好為 0xFF，如果計時器在兩次位元組讀取之間遞增，則簡單地分別讀取每個位元組將得到一個損壞的值。 如果先讀取低位元組，再讀取高位元組，或者反過來，我們將得到略微不同的損壞值，但無論哪種方式，它都是損壞的。

一個簡單的解決方案是讀取計數器兩次並比較：

long atomic_read_counter(volatile long *counter){
    long counter_old, counter_new;
    do{
        counter_old = *counter; // alas, not an atomic operation when the timer is connected to the CPU over an 8-bit bus.
        counter_new = *counter;
    }while( counter_old != counter_new );
    return counter_new;
}

或者

// "optimized" routine hard-wired to read a 16-bit Counter1:
// the entire routine takes 3 machine instructions on the 8051 -- see Craig Steiner, Abhishek Yadav, etc.
inline
int atomic_read_counter1(){
    byte upper, lower;
    do{
        upper = Counter1H;
        lower = Counter1L;
    }while( upper != Counter1H );
    return( (upper << 8) | lower );
}

由於沒有使用鎖，雙重讀取演算法避免了死鎖、優先順序反轉以及其他與鎖相關的問題。

還有許多其他基於這種讀取兩次並比較演算法的演算法。

例如，Linux 中使用的 seqlock 使用這種讀取兩次並比較演算法。

例如，單讀單寫環形緩衝區在嵌入式系統中也很常見，讀寫器都可以使用類似的無鎖演算法實現。

遞增計數器

當使用讀取兩次並比較演算法來同步多個程序（而不是上面提到的硬體計數器和讀取計數器的程序）時，更改計數器的程序需要以對其他程序看起來原子化的方式進行更改。

許多架構都有一條指令可以原子地遞增變數。可惜的是，確切的細節因架構而異，也因 C 編譯器而異。一些相對可移植的方法來告訴 C 編譯器原子地遞增變數包括來自標準原子操作庫的 std::atomic 模板類，它是 C 程式語言 C11 標準的一部分； 或者 tbb::atomic 模板類；或者 boost::atomic 模板類；等等。

// rough draft -- untested code

__interrupt_handler h(){
        // ...
        // inside interrupt handler, interrupts are already turned off, so it's safe to increment the counter
        raw_counter++;
        // ...
}

// using CAS to update the counter is safe even if interrupts are turned on.
// inspired by example_atomic_inc() in
// https://kernel.linux.club.tw/doc/Documentation/atomic_ops.txt
void increment_counter(volatile long *counter){
    _Bool ret;
	do{
		long old = *counter;
		long new = old + 1;
		// requires #include <stdatomic.h>
		ret = atomic_compare_exchange_strong( counter, &old, new );
	}while(!ret);
}

// only use if interrupts are turned on, and it's not a multiprocessor machine:
void increment_counter(volatile long *counter){
    disable_interrupts();
        (*counter)++;
    enable_interrupts();
}

雙重讀取演算法的主要問題是 ABA 問題。 為了避免 ABA 問題，我們使用只向上計數的計數器， 我們給計數器足夠的位，以便在任何合理的時間內，執行緒可能在讀取第一次讀取的第一個位元組和第二次讀取的最後一個位元組之間被延遲（例如，最大 1 秒），計數器足夠長，以至於在最壞情況下（最高頻率）計數率，它需要比這長得多的時間——例如，溢位所需的最短時間是每 10 秒一次。

例如，可以從 2 個計數器合成上下計數器，一個計數器只向上計數，另一個計數器只向下計數。