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