#6–4 作業系統

硬體也支援的同步

因為我們上篇說 Peterson’s Solution
只是軟體上的演算法，在現在的電腦上不一定可行
（像是Reorder的問題）
所以這篇要來說 有哪些硬體上的技術也能夠支援同步

前言

#6–1 Race Condition

#6_1 作業系統

#6–2 Critical Section

#6_2 作業系統

#6–3

#6–3 作業系統

正文開始

接下來會介紹3種硬體實作
(Memory Barriers, Hardware Instructions, Atomic Variables)
來解決Critical Section Problem

Memory Barriers

memory_barrier()：就是告訴complier不要reorder，這樣順序就不會亂掉

Memory Barriers

Hardware Instructions

接下來要講的都是指令
寫成function的形式只是為了更好理解
因為是指令，所以過程中不會有context switch

test_and_set()

boolean test_and_set(boolean *target){
    boolean rv = *target;
    *target = true;        //把target的值改成true
    return rv;             //回傳原本的值
}

用test_and_set() 來實作 mutual-exclusion

執行順序(搭配下面的圖看，左邊是process i，右邊是process j)
假設一開始lock=false，在process i
可以把lock想成 有沒有人想進去critical section
如果有人想lock=true，反之lock=false
執行完test_and_set(&lock)之後，lock=true

此時process i已進入critical section
然而不幸的是，發生了context switch
現在換成process j
不過沒關係，因為lock=true
process j什麼事都不會做（因為while(true)）
等再次發生context switch
回到process i，i就繼續執行critical section

用test_and_set() 來實作 bounded-waiting & mutual-exclusion

compare_and_swap()

int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;
    if (*value == expected)    //如果value跟預期的一樣
        *value = new_value;    //就把value改成新的value
    return temp;               //回傳原本的value
}

用compare_and_swap() 來實作 mutual-exclusion

執行順序(搭配下面的圖看，左邊是process i，右邊是process j)

假設一開始lock = 0，在process i
return 0，現在lock = 1
直接進入critical section
就算context switch到process j也無所謂
因為lock=1，1!=0
process j什麼都不會做(while(true))
等到context switch回去process i
process i繼續critical section
做完之後，lock = 0
context switch到其他process時
其他process就能進入他們自己的critical section

用compare_and_swap() 來實作 bounded-wating & mutual-exclusion

概念是學peterson’s solution的，都先禮讓對方

執行順序(搭配下面的圖看，左邊是process i，右邊是process j)

假設一開始lock = 0(沒有其他人在執行critical section)，在process i
一開始的while迴圈一定會成立
這個迴圈的目的，是為了檢查有沒有其他process在執行自己的critical section
如果「有」其他人在執行它的critical section，則lock=1，key=1，while(true)
直到別人結束critical section，process i就會離開while迴圈
如果「沒有」其他人在執行它的critical section，則lock=0，key=0
process i離開while迴圈

接著waiting = flase(因為已經不需要等待了)
然後進入自己的critical section
執行完critical section之後

找到下一個想要進入critical section的process
如果沒有process想進去，則lock=0（代表沒人想進去）
如果有人的話，把他的waiting改成false
因為要換他執行了，他就不需要等待了