[TOC] ## 信號量(semaphore) - 一個控制同時訪問一個資源的線程(進程)數量的抽象數據類型 - Semaphore內部封裝一個整數(p)和一個睡眠線程集合(s),并提供兩個原子操作 ``` up() p=p+ 如果s.size0>0,從s中選擇一個喚醒并執行 down() if(p==0)( sleep(&semaphore)) p-- ``` ### 解決有界緩存區問題:生產者/消費者 類似隊列形式進行消費生產模型 bad ``` // Producer while(true){ tiem = produce_item() insert_item(item) } // Consumer while(true){ item = remove_item() consume_item() } ``` good ``` // 用到了3個信號量 empty=N, mutex=1,ful=0 // Producer while(true){ tiem = produce_item() down(&empty) // 要放東西前先empty 間一,down中可判斷如果empt滿了,不然其他進來 down(&mutex) insert_item(item) up(&mutex) up(&full) } // Consumer while(true){ down(&full) down(&mutex) item = remove_item() up(&mutex) up(&empty) consume_item() } ``` ## 互斥量(mutex) - 初始值為1的 信號量(semaphore) - 可以用來鎖住臨界區 ## 多信號量造成的死鎖 bad 造成死鎖 ``` semaphore m1 = 1; semaphore m2 = 1: // 進程1 down(m1) down(m2) criticalRegion() up(m1) up(m2) // 進程2 down(m2) down(m1) critcalRegion() up(m1) up(m2) ``` good ``` semaphore m1 = 1; semaphore m2 = 1: // 進程1 down(m1) down(m2) criticalRegion() up(m1) up(m2) // 進程2 down(m1) down(m2) critcalRegion() up(m1) up(m2) ``` ## 如何理解TSL/ Semaphore/ Mutex的關系 1. TSL/XCHG是基礎能力(否則就得用忙等待算法) 2. Semaphore是一種基于TSL成立的算法和數據結構〔理解成解決方 案) - Mutex是 Semaphore的一種產出(特殊情況) 3. 算法數據結構當然無窮無盡,參考:AQS( Abstract Queued Synchronization)