1.概念
synchronization
processes同步平行處理
容易發生race condition
race condition
多個processes同一時間點存取shared resource,未協調好而導致data inconsientency
ex:
將專屬的設備當成共用設備使用，而造成設備出現異常
…………………….
critical-section
避免race condition的一種方法
一段code,code內的共用資源禁止多個process在裡面執行
結構如下
do{
//entry section 進入critical section的入口區
critical section
//exit section
remainder section非critical section的其他程式
}while(1);
critical-section三要素
mutual exclusion(互斥): 只允許1個process在critical-section裡執行
當process在critical-section存取resource時，其他process無法進入critical-section存取相同資源
progress(進行): 選擇下一個process進入critical-section的時間不可被無限delay
1.其他process(在remainder section)不能干預其他process進入critical section的決策過程
2.當多個process要進入時，決定那一個process可先進入critical-section的時間是有限的,(防止deadlock)
bounded waiting(有限等待):
當process被獲准可進入critical-section後,進入critical-section的等待時間是有限的(防止starvation)
ex:
若有n個processes想進入Critical Section，則每個process最多只要等待n-1的時間後就可進入
……………………………………………….
2.解決方案
解決race condition常見的方法有以下
硬體和軟體
semaphore
monitor
….
硬體
開發同步程式較方便
提昇系統效率
常見的有
disable interrupts
TestAndSet 一種極小的硬體指令
CompareAndSwap 一種極小的硬體指令
disable interrupts
適合在單cpu，但較不適合在多cpu系統
TestAndSet
保證mutual exclusion與progress,但是不保證符合bounded waiting
結構大致如下
boolean TestAndSet (Boolean *locked) {
boolen uv=locked;
*locked = true;
return uv;
}
應用在critical section大致如下
do{ //lock是shared variable
while (TestAndSet(&lock)); //將lock變數的記憶體位置傳入TestAndSet
/*critical section*/
lock = false; //critical section結束後,則會將lock解除,
/* remainder section */
}while(true)
CompareAndSwap
結構大致如下
int CompareAndSwap(int *v, int exptd, int new){
int tmp=*v
if(*v==exptd)*v=new;
return tmp;
}
應用在critical section大致如下
do{ //lock是shared variable
while (CompareAndSwap(&lock,0,1));
/*critical section*/
lock = 0; //critical section結束後,則會將lock解除,
/* remainder section */
}while(true)
…
軟體
禁止中斷法:使用disable系統呼叫,僅適合在單cpu環境
Dekker’s algorithms
peterson’s algorithms
bakery algorithms:適合解決多個行程同步問題
mutex locks
mutex locks
最簡單的其中一種方法
缺點是會有busy waiting
大致如下
do{
acquire_lock()
/* critical section */
release_lock()
/* remainder section */
}while(1);
busy waiting(忙碌等待)
當process在critical-section時，其他想進入critical-section的process會在entry section一直執行loop來等待
ps:也被稱為spinlock(旋轉鎖),意指cpu會不斷測試該條件是否成立,會浪費cpu cycle
………………
semaphore
常見的synchronization工具,可解決更複雜的synchronization
是一個protected variable
僅提供critical section的同步機制，不保證有mutual exclusion特性，不保證避免deadlock
透過wait()和singal()運算修改protected variable，以達到process synchronization
ps:semaphore常以S表示,wait()常以P()表示,signal()常以V()表示;
semaphore分為
counting semaphore(計數號誌):可製作no busy waiting的mutex locks
binary semaphore(二元號誌): 只有0和1,容易實作,常用在mutex locks
no busy-waiting on counting semaphore
主要透過block()和wakeup()這兩個atomic operate(最小運算)
block():將process改為wait state,也就是將process移到wait queue中
wakeup():將要被wakeup的process從wait queue移到ready queue
ps:也被稱為suspend-lock
no busy-waiting on counting semaphore結構
大致如下
typedef struct{
int value;
struct process*list
}semaphore;
wait(semaphore *s){
s.value–;
if(s.value <0){
//add this process to s.list;
block(); //將process放入waiting queue
}
}
signal(semaphore *s){
s.value++;
if(s.value <=0){
//remove a process from s.list;
wakeup(P); //將process從waiting queue移到ready queue
}
}
應用在critical section的結構如下
semahore mutex; //初始化為1
do{
wait(mutex);
/* critical section */
signal(mutex);
/* remainder sectoin */
}while(TRUE);
………………………………..
monitor
以程式語言達到synchronization的機制
保證任何process存取資料是mutex
以blocking和wakeup機制處理process進入critical section
………..
3.synchronization的典型議題
bounded-buffer problem(有限緩衝區問題)
readers and writers problem(讀取寫入問題)
dining-philosophers problem(哲學家進餐問題)
bounded-buffer problem
有n個buffer,每個buffer可保存一個項目,以及多個producer和consumer
程式碼大致如下
initialized: mutex=1,full=0,empty=n
producer process
do{
//produce an item in nextp
wait(empty);
wait(mutex);
//add the item to the buffer
signal(mutex);
signal(full);
}
consumer process
do{
wait(full);
wait(mutex);
//remove an item from the buffer to nextc
signal(mutex);
signal(empty);
//consume the item in nextp
}
readers and writers problem
一個shared data能被同時存取
目標:允許多個reader在相同時間讀取,但僅能一個writer在相同時間存取
程式碼大致如下
initialized: mutex=1,wrt=1,readcount=0
writer process
do{
wait(wrt);
//writing is performed
signal(wrt);
}
reader process
do{
wait(mutex);
readcount++;
if(readcount==1)wait(wrt);
singal(mutex);
//reading is performed
wait(mutex);
readcount–;
if(readcount==0)signal(wrt);
signal(mutex);
}while(TRUE);