synchronization

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);

 

 

 

2014-01-12 08:56:40發表 2014-01-12 08:59:09修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法
Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統

數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net