Pixiv - KiraraShss
Welcome to my blog
675 words
3 minutes
作業系統Ch6 Synchronization Tools
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 0while(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 1while(1) { flag[1]=1; turn=0; while(flag[0] && turn==0); //Critical Section flag[1]=0;}註: flag與turn的設置不可對調，否則會產生同時在CS的情況
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_cntreader_cnt++; //1 more readerif(reader_cnt==1) wait(write); //1st reader block writerrelease(mutex);read_book();acquire(mutex);reader_cnt--;if(!reader_cnt) signal(write); //no readers, write nowrelease(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); //initsem_wait(sem); //acquiresem_post(sem); //releaseCondition variable
#include <pthread.h>
pthread_cond_t var;pthread_cond_init(&var, NULL);while(a!=b) pthread_cont_wait(&var, &mut); //wait until a==bMonitors
- 抽象化同步機制
- Condition variable
- Monitor裡面的資料只有Monitor裡面的procedore可以存取
- 在Monitor中同時刻只有一個active process
作業系統Ch6 Synchronization Tools
https://blog.cyberangel.work/posts/os-ch6/ Last updated on 2024-12-19，350 days ago
Some content may be outdated