D-OS-Ch06db-Atomic_Hardware_Instruction

Atomic Hardware Instruction

Introduction

Atomic hardware instruction 把「讀取、檢查、修改」做成不可被中斷的一個 unit，常用來實作 mutex lock、spinlock、atomic variable。

test_and_set()

test_and_set() atomically 讀出舊值，並把目標設成 true。

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

用來實作 lock：

while (test_and_set(&lock))
    ;
 
/* critical section */
lock = false;

第一個看到 lock == false 的 process 會把它改成 true 並進入；其他 process 繼續 spin。

compare_and_swap()

CAS 檢查 *value 是否等於 expected，若是才改成 new_value，並回傳原本的值。

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

用來實作 lock：

while (compare_and_swap(&lock, 0, 1) != 0)
    ;
 
/* critical section */
lock = 0;

Limitation

簡單 CAS lock 可保證 mutual exclusion，但不保證 bounded waiting；lock 釋放後誰搶到取決於 timing，可能造成 starvation。