Intro

  • 多處理器處理同筆資料
  • 同時寫入 -> 錯誤
  • Race condition problem
    • 操作global的程式碼不應同步執行

Race contidion其中一解 : critical section

  • Mutual exclusion : 同一時間只有一個task在CS
  • Progress : 沒有task在CS -> 令其他task進入
  • Bounded waiting : 不讓其他task等太多次

Peterson’s solution

  • 假設只有兩個task, 且支援atomic instruction, shared memory
  • 概念可擴展到任意數量task

Code:

//Task 0
while(1) {
    flag[0]=1; //task0 want to enter CS
    turn=1; //in case task1 wants to enter CS
    while(flag[1] && turn==1); //wait for task1
    //Critical Section
    flag[0]=0;
}

//Task 1
while(1) {
    flag[1]=1;
    turn=0;
    while(flag[0] && turn==0);
    //Critical Section
    flag[1]=0;
}

註: flag與turn的設置不可對調，否則會產生同時在CS的情況

Memory barrier

Synchronization Hardware

Memory barrier

  • 保證執行的當下Sync資料
  • 分類
    • Load Barrier
    • Store Barrier
    • Full Barrier
    • Acquire/release Barrier : 確保完成後讀取/確保完成後其他threads更新

Instructions

Test-and-Set

  • Atomic執行
  • 設定*target, 回傳*target原本的值

Compare-and-swap

  • Atomic執行
  • 如*value與expected相等則swap

Atomic variables

  • Atomic update

Mutex Lock

  • acquire() 與 release()須為atomic
  • Cannot acquire lock -> busy waiting(spinlock)
while(1) {
    acquire_lock();
    //CS
    release_lock();
    //remainder
}

Semaphore

  • 定義一個counter (S), 只有此定義數量的可用資源
  • 需要wait() 以及signal() : wait until S>0 / S++
  • Counter==0 時會進行block，直到signal
  • Binary semaphore -> Mutex
wait(*S) {
    S->counter--;
    if(S->counter<0)
        block();
}
signal(*S) {
    S->counter++;
    if(S->counter<=0)
        wakeup();
}

經典問題

Bounded-buffer問題

  • 生產者

    • 放入buffer
    • buffer滿了 -> wait

  • 消費者

    • 從buffer拿走
    • 當buffer==0時需要停止

  • 生產者解法

while(1) {
    produce();
    wait(buffer); //wait until can write
    wait(mutex); //avoid race cond.
    put_to_buffer();
    signal(mutex);
    signal(full);
}
  • 消費者解法
while(1) {
    wait(full); //wait until can read
    wait(mutex); //avoid race cond.
    get_from_buffer();
    signal(mutex);
    signal(empty);
    consume();
}

Readers-writers問題

  • 讀者
    • Rdonly
    • 可能同時有很多讀者
  • 作者
    • 需要對shared memory寫入
    • 需要獨佔

解法有兩種

都需要2個semaphore : mutex, write

  • 讀者優先 : 作者需要wait所有讀者
Reader:
acquire(mutex); //保護 reader_cnt
reader_cnt++; //1 more reader
if(reader_cnt==1)
    wait(write); //1st reader block writer
release(mutex);
read_book();
acquire(mutex);
reader_cnt--;
if(!reader_cnt)
    signal(write); //no readers, write now
release(mutex);

Writer:
wait(writer); //獨佔
write_book();
signal(writer); //release
  • 作者優先 : block後來的讀者(需要writer_count)
Reader:
acquire(mutex);
while(writers_cnt)
    wait(read_queue);
reader_cnt++;
release(mutex);
read_book();
acquire(mutex);
reader_cnt--;
if(!reader_cnt)
    signal(write);
release(mutex);

Writer:
acquire(mutex);
writer_cnt++;
wait(writer);
writer_cnt--;
release(mutex);
write_book();
signal(write);

哲學家晚餐問題

  • Deadlock : 每個人都拿左邊的筷子
  • Starvation : 某些人一直吃
  • Race Condition : 兩人同時拿一支筷子

解法:

  • 指定編號，令所有人照順序拿筷子 : 可能導致Starvation
  • 向服務員請求筷子 : 服務員會成為效能瓶頸
  • 奇數人先拿左邊，偶數人先拿右邊 : 複雜度過高(需編號)
  • Semaphore
  • Deadlock Prevention

Linux Synchronization

C11

  • Atomic variables : atomic_t
  • Functions : atomic_set(), atomic_add(), atomic_read()

POSIX

Mutex locks

#include <pthread.h>

pthread_mutex_t mut;
pthread_mutex_init(&mut, NULL);
pthread_mutex_lock(&mut);
pthread_mutex_unlock(&mut);

Semaphore

#include <semaphore.h>

sem_t *sem;
sem=sem_open("SEM", O_CREAT, 0666, 1); //init
sem_wait(sem); //acquire
sem_post(sem); //release

Condition variable

#include <pthread.h>

pthread_cond_t var;
pthread_cond_init(&var, NULL);
while(a!=b)
    pthread_cont_wait(&var, &mut); //wait until a==b

Monitors

  • 抽象化同步機制
  • Condition variable
  • Monitor裡面的資料只有Monitor裡面的procedore可以存取
  • 在Monitor中同時刻只有一個active process