Mutual exclusion 筆者稱為互斥鎖或排容鎖。
源於多執行緒或多行程或多處理器之運算系統下的一個必要面對的問題。
但 mutual exclusion 的對象僅對於，以下我們只以行程來稱呼，雙行程間的互斥行為。而若要超過雙行程，確保多行程的互斥行為，則單單就是將雙行程的方法擴展，不過說歸說，並不那麼簡單，筆者也沒再多去查資料了因為深知，極端困難；當然有大師有解也是確定的。

事實上，以程式語言而言，抽象的語言規範下，鎖，似乎不在語言的範疇內，因此並沒有適當的地位，放下鎖這個定義。故發展下，鎖便更適切地投入了編譯器原理結構與規範的門下，被定義，規範與引用實作。也就是說，透過編譯器的軟體支援有 atomic operations 的函式庫，引用函式庫的軟體方法來達到多行程間的互斥行為。

解決鎖這個問題，有軟體方法，也有硬體方法。而硬體方法很單純，微處理器的指令集內只要有 atomic instruction，則鎖的問題將被輕易地解決。
例如，i=1，這將使處理器使用一條 CPU 指令完成這行程式碼，所以，assignment instruction 便可視為 atomic instruction，不過，atomic instructions 的對象並不是針對 assignment 這類一般指令，而是更特定的對象；其同樣是由 CPU 以一行指令完成，常見的有兩個，TS（test and set）和 SWAP。簡單說一下 TS，若 operand 是 0，則設成 1，並得到 0 的回傳值（斥或 TSB 跳躍）以供判斷。反之若 operand 是 1，則 operand 不被更動，並回傳 1（斥或 TSB 不跳躍）以供判斷。如此簡單的指令至關重要。
由於 CPU 自古至今都是 pipeline 管線設計，故想要有 atomic instruction 並不是那麼容易，抑或耗用多個週期實現，故，微控器並不支援 atomic instruction，並不是那麼少見的。因此目前常見的狀況都是透過編譯器及軟體函式庫來支援。
而本章要／只是放程式碼而已／註記的，就是無關乎編譯器或函式庫，單純應用端的邏輯層面下的軟體互斥方法。

Uniprocessor

Uniprocessors，微控器絕大部份是此類。但仍有多執行緒或多行程的應用。因此本章適用於單執行緒或單行程的應用。
但，如此還有什麼好講的：
在一個有中斷服務的單行程系統下，也就是絕大多數微控器的應用環境，其行為就是循序執行，若遇到中斷再跳到中斷常式去執行而已。並且如筆者此前常使用的，在行程內只要用上一個全域變數 gate，將其設為 1，後處理 sensitive code，還用不上判斷 gate，便可正確無虞。因為，中斷不管在何時發生，判斷若 gate 為 1，便不會跑常式內容。因為，中斷勢必在 gate==1，gate==0，這兩種狀態下決定執行不執行常式。
假若，現在有多種中斷，乃或有優先權順序及 NMI 等問題的引入且涉及到資源共享的問題，則，要正確運行，必然要有鎖的存在才行。簡單講，資源共享是基礎成因，存取資源的對象若超過兩個是必要條件，則無鎖不能程式（成事）。
用上了鎖，反向層面的考量是，等待與否。若某中斷發生，並且等待解鎖，那麼勢必 spin waiting，因為若不返回則無法解鎖。但問題在於，若返回解鎖，那麼該次中斷沒被執行到，是否是可被接受的這個問題。
因此，涉及到資源共享問題，就算在 uniprocessor 下，也可能遭遇到無解的窘境。
再來就是，上面提到的 gate 就是適用於兩個對象，那，mutual exclusion 的軟體方法還需用上嗎？
先說 gate 方式，也只適用於特定的狀況，非泛用下都是解法。
那麼這下就可談到，mutual exclusion 在微控器應用環境下，有何裨益。後續不再強調用於兩個對象。

Design pattern－Singleton

有人稱呼它為 antipattern。此 design pattern 衍生出諸多問題，當在多行程下的應用時。
細節介紹請自行谷歌。
甚至於有人說，它無異於一個全域變數，也是有道理的。（按，就算存取一個全域變數，多行程，就是非鎖不可。）
筆者看上它這個 class 類別，既能封裝在任意類別之下，還能擺脫類別的存取域：即便在某類別下某變數是私有變數，仍能在其他地方被存取。而它之所以有可能有問題，就發生在第一次使用，具現化，的這個時間點，需要加鎖：“判斷是否已具現化，若否則具現化”。這句話從來就不是 atomic operation。單處理這個 atomic operation 問題，就已衍生出大量的探討，與大量的 thread-nonsafe 的解法，及極少數的正確解法與深層的原理。
同理在 uniprocess & interrupt 環境下，用上 singleton，原則上，mutual exclusion 就派上用場了。故終於舉出了寫本篇文章的合理性。

Peterson method

bool id[2];
int turn;

void P0(){
    while (true){
        id[0]=true; // a.
        turn=1; // b.
        while (id[1] && turn==1); // c. spin waiting.
        // d. critical section.
        id[0]=false; // e.
    }
}

void P1(){
    while (true){
        id[1]=true; // A.
        turn=0; // B.
        while (id[0] && turn==0); // C. spin waiting.
        // D. critical section.
        id[1]=false; // E.
    }
}

int main(){
    id[0]=false;
    id[1]=false;
    parbegin(P0, P1);
}

• 說明，
• 0，1，各代表行程 P0 和 P1
• a 表示，我即將進入 critical section
• 如同黑貓白貓過橋的問題，唯有，“請您先過”，turn=對方，才有可能解套。b 代表著願意讓對方先通過
• 因此，我必須判斷，若對方也準備進入 critical section，id[對方]==true，並且事實結果是輪到對方先過，turn==對方，則我就必須等待，c 的意涵。
• 等待的解除條件是，id[對方]==false。事實上是，若對方已做完 critical section，則便能確保 id[對方]==false，因對方通過後會設定此條件，則，我便能脫離等待，接著通過。
• 因此，就如若是我通過了，我便會將 id[我方] 設為 false，對方也必然不再等待，即 e 的意涵。
• 所以以上就邏輯的層面來看正確性與可行性。
• 接著，基於同時的前提下，我們先來看互斥性，有可能同時通過嗎？則必有一方先通過，即 c 是 false 的，也因此 turn 值決定了另一方必不能通過。
• 有可能雙方都在等待嗎？當然，turn 值告訴我們不可能。
• 有可能一方通過，另一方一直在等待嗎？當然，若真有一方通過，它通過後會去設我方不準備進入 critical section，或說離開 critical section，即 id[我方]=false，則另一方必不再需等待而通過。
• 有可能雙方都進不了 critical section 嗎？糟糕，有可能！
  假設初始條件 id[甲方]=true，則，假設甲方一直都不進 critical section，則，乙方便一直進不了 critical section。故，初始條件 id[x]=false 是必要的。

Dekker method

bool id[2];
int turn;

void P0(){
    while (true){
        id[0]=true;
        while (id[1]) if (turn==1){
            id[0]=false;
            while (turn==1); // spin waiting.
            id[0]=true;
        }
        // critical section.
        turn=1;
        id[0]=false;
    }
}

void P1(){
    while (true){
        id[1]=true;
        while (id[0]) if (turn==0){
            id[1]=false;
            while (turn==0); // spin waiting.
            id[1]=true;
        }
        // critical section.
        turn=0;
        id[1]=false;
    }
}

int main(){
    id[0]=false;
    id[1]=false;
    turn=1;
    parbegin(P0, P1);
}

• 說明，
• 這條還真不知道該怎麼分析。
• 不過，我們看前一條 Peterson 的程式，turn 是在決定誰可以進入 critical section 前就會被修改的。然而 Dekker 的，turn 是不會被更動的。
• 所以看來，Dekker 的將有更大的可能可以改成泛用型的鎖的。
• 所以，這條，筆者若有頓悟再來看吧。
• 好吧還是先這樣來看一下，
• 欲進入 critical section 者，一定會設定 id[me]=true，
• 並且，如果 id[others] 是 false，則必能順利進入 critical section。離開時，不僅將 id[me] 設為 false，也將 turn 設給其他人，turn=others。
• 所以某方的進出，並不影響其他人的進出。且萬一都沒有其他人進入，本方還是可再進出。
• 而若 id[others] 為 true，則它將進行“等待的處置”，不僅設 id[me]=false，好像事情在自己身上從未發生過一樣，並且停留於等待區，而其脫離的條件就是他方離開 critical section 而得到 turn 的釋放。
• 因此其餘的分析就比照前例分析。
• 接著筆者這裏陳述用了 others，並試想，turn 如果是一個陣列或串列，是不是就可擴展成多行程了？答案是要，至少目前是要失望了。陣列的寫入，便既已涉及到需要互斥的條件存在才行了。所以，真的不簡單！
• 咦，不是才剛提到 turn 是在進入 critical section 後才被更改的嗎？
• 對厚！
• 不過，若筆者真有頓悟後再來看看吧。
  

The Lock

經過一夜沈澱，再想一想，似乎一般化 mutual exclusion 是有譜的，畢竟，前輩大師們已經鋪好路了，只剩最後一吋路，不走不試不鑽研，對不起前輩們。故以下把 Dekker 的扣改成更容易判斷的寫法，如前面說明的描述方式，再來探討看看。

void Pme(){
    while (true){
        id[me]=true;
        while (id[others]) if (turn!=me){
            id[me]=false;
            while (turn!=me); // spin waiting.
            id[me]=true;
        }
        // critical section.
        turn=others;
        id[me]=false;
    }
}

void Pothers(){
    while (true){
        id[others]=true;
        while (id[me]) if (turn!=others){
            id[others]=false;
            while (turn!=others); // spin waiting.
            id[others]=true;
        }
        // critical section.
        turn=me;
        id[others]=false;
    }
}

• 首先就要提到，各行程有獨立的定址空間；各執行緒（筆者的印象），也有各自獨立的執行緒物件及屬性，其共享全域變數。而以上二者，在其所屬的可存取域之下，不論是靜態的記憶體空間配置，或是動態記憶體配置，都是經由更底層的 Virtual-MMU 及系統程式等所管理著。簡單講，以上並沒有記憶體配置上的衝突問題。
  也就是只有在應用層面，使用共享記憶體（以實現行程間溝通或同步的目的）或共同可存取到的變數時，才會有同時性存取時可能遭遇到的衝突問題並透過鎖來排除。此同時性何意，想必不需多加解釋。
• 這意謂著，在唯一的記憶體空間下，物件配置的位址是唯一的。在多行程應用下，不同行程配置到的記憶體位址可能可以重覆。
• 因此現下結論，多行程之解筆者還無能為力。微控器應用之解法筆者繼續探討如下。不過話說回來，多行程環境下，其實鎖既已存在，也就不容多加置喙了。或說，VMMU 也是使用唯一的定址空間的。
• 不過，應該結尾了。。。me 跟 others 是等價的。以上所有程式都涉及到一個無法改變的事實，即，裏面用到的變數，乃或常數，都逃不離，至少有一種數值必須靜態繫結，即，編譯時或編譯前就必須決定其數值，更白話地說，不僅 lock 的數量在編程期間就必須確定，lock 的使用對象，也必須確定。
  當前結論，似乎鎖的軟體解法，除了適合使用而使用 mutual exclusion 外，又回到只有編譯器支援這一種了。
• 不知有沒有看懂。講個最簡單的衝突，我要獲得 id，就會存在衝突了。

苟延殘喘

• 唉，筆者心死手不死，手指非要再抖個幾下不罷休。。。難道真無解？
• 答案筆者仍未查證。不過心想若，除了編譯器支援就無其他解了，那麼今日軟體不可能這麼發達。
• 順道說一下，剛查了一回資料，Dijkstra 是最早期演算法的先驅，提出了 Semaphore，wait(P)，signal(V) 的鎖的模型。
• 此外，有解的，例如 Lamport bakery algorithm，也是 id 已知的前提下。或說，
  或許我們可以退而求其次，當目前有 n 個 processes 時，使用了 id[n]，當新生成一個 process 時，delete id，再 new id[n+1]。則便交待得過去。
• 再踹！
• 轉圜點：真的現下也沒有方法，但還是得提醒一下自己可能轉圜的基礎性質，也是由 Dijkstra 所啟發。鎖的性質，mutual exclusion，no starvation，no spin waiting，no deadlock。Lock 物件，也只存在於絕對定址空間，也就是共享空間。於絕對的定址空間下獲得的位址是唯一的。沒有 atomic instructions，難道真不能從其他 instructions 來加工獲得；畢竟至少於 2 objects mutual exclusion 是確定有解的。
  以上，不全廢話。。。

參考資料

• 本篇文章依然沒有結論。
• 或許反向求解，可以使用 thread-safe 的 singleton 來實作 lock。但這單單就是編譯器支援的解法。並且 ironic 是 singleton 本身就可能要用到 lock。
• 以下列一下 singleton 的參考資料。有人說 Meyers 的 singleton 是 threadsafe，到底何是，沒查到資料。
• https://en.wikipedia.org/wiki/Mutual_exclusion
• https://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf
• https://stackoverflow.com/questions/1008019/c-singleton-design-pattern
• https://stackoverflow.com/questions/1661529/is-meyers-implementation-of-the-singleton-pattern-thread-safe

class S
{
    public:
        static S& getInstance()
        {
            static S    instance; // Guaranteed to be destroyed.
                                  // Instantiated on first use.
            return instance;
        }
    private:
        S() {}                    // Constructor? (the {} brackets) are needed here.

        // C++ 03
        // ========
        // Don't forget to declare these two. You want to make sure they
        // are inaccessible(especially from outside), otherwise, you may accidentally get copies of
        // your singleton appearing.
        S(S const&);              // Don't Implement
        void operator=(S const&); // Don't implement

        // C++ 11
        // =======
        // We can use the better technique of deleting the methods
        // we don't want.
    public:
        S(S const&)               = delete;
        void operator=(S const&)  = delete;

        // Note: Scott Meyers mentions in his Effective Modern
        //       C++ book, that deleted functions should generally
        //       be public as it results in better error messages
        //       due to the compilers behavior to check accessibility
        //       before deleted status
};

追述

• 以上有一點應是有說錯／應說不恰當，當再說明一下。
• 就系統程式對於任一行程的共享記憶體配置與存取而言，假設是不預設立場的，則仍涉及衝突問題，（應看不懂，故我說），反之，若系統程式於行程創建之初，就安排好配置共享記憶體的前置作業，則便能依 n processes mutual exclusion 來排解。
• 其次雙行程的解法，當兩行程同時進來，誰先進後進可說無意義，而誰先出後出，則看 context switching 的順序，不過也都確保了不 starvation。
• 最後，用以下程式結案。
• 另歡迎提供說明指教（筆者當前都看不通），已實現的 n processes，其不僅沒有 id 配置衝突問題也適用於任意個 processes mutual exclusion。
• 20240203 無想法後能靠的就是外在的雜訊不經意地勾引出稀微的雜念：n 的話，可分為 1, (n-1)；再分為 1*, 1, (n-2)；以此類推；當下能通過的只有一個，我，看能不能從此最細微的一點展開化解。是否文不對題乃或可不可行我不知道，前面的全忘光了XXD
  （咦，前面有提過了？）

// processes are numbering from 1 to N.
int same_time=0; // 1 to N processes.
int ts[N+1]={0}; // storing timestamp, from index 1 to N.

void DekkerN(){
    ts[me]=TimeStamp();
    same_time++;
    while (same_time>1 && GetOldestP()!=me);

    // critical section.

    ts[me]=0;
    same_time--;
}

// 幾點原則，
// 1. 已不再存在配置 id 將造成衝突這種原生性問題.
// 2. 既然第一點可成立，表示行程立基於相當程度的底層之上，該底層將輕易使得行程可獲得唯一的 timestamp.
// 3. 無庸置疑，++，--，a>b，a!=b，如此一般指令即是 atomic instructions.
// 4. 基於以上三點便可迎刃而解了。
// 5. 當然以上，就是將同步問題轉移至 get_cpu_clock_cycles 問題。而此問題，最好該是 CPU atomic instructions 所。。。自然支援。
// 6. 以 esp8266 而言，筆者不知道 micros() 是如何實作，但我們可大膽地用 while (micros()==micros()) while (1); 來實證。
// 7. 但。。。千萬別問我，有沒有這樣執行過。。。因為。。。不試就知道答案了 Orz