一、背景
确保同步，需要高层次的编程抽象(锁)，从底层硬件支持编译
二、信号量
1. 信号量抽象数据类型
一个整型，两个原子操作:
- P()：sem减1，如果 sem<0，等待，否则继续
- V()：sem加1，如果sem<=0，唤醒一个等待的P
2. 概述
a. 特点
特点：信号量是整数，P()能阻塞，V()不会阻塞
信号量是被保护的变量：
- 初始化完成后，唯一改变一个信号量的方法是通过P()和V()
- 操作必须是原子的
信号量可以是公平的：
- 如果V()被无限频繁调用，则没有线程被一直阻塞在P()
- 信号量阻塞队列可以是FIFO的
b. 类型
- 二进制信号量：可以是0或者1
- 一般/计数信号量：可取任意非负值
两者互为表现(给定一个，可以实现另一个)
c. 作用场景
- 互斥
- 条件同步(调度约束 - 一个线程等待另一个线程的事件发生)
三、信号量使用
1. 用二进制信号量实现互斥
mutex=new Semaphore(1);// 加锁
mutex.P();// 操作
dosomething();// 解锁
mutex.V();2. 使用二进制信号量实现调度约束
condition=new Semaphore(0);// 线程A
do something...
condition.P() // 线程A等待B中 v()发出信号，以便进行下一步操作
do something...// 线程B
do something...
condition.V() // 线程B 发出 V() 信号，唤醒线程A 等待
do somthing...3. 例子
伪代码实现：
/**
* 公共变量初始化
**/
mutex=new Semaphore(1);
fullBuffers=new Semaphore(0); // 用以标识buffer中物品数量
emptyBuffers=new Semaphore(n); // 用以标识buffer空间/**
* 生产者伪代码
**/
emptyBuffers.P(); // 申请空缓存区，若无空缓冲区，则等待进程
mutex.P(); // 限制同一时刻只能有一个线程进入缓冲区
add c to the buffer; // 操作并往缓冲区增加物品
mutex.V(); // 解锁
fullBuffers.V(); // 增加缓冲区物品数/**
* 消费者代码
**/
fullBuffers.P(); // 判断缓冲区是否有物品，无物品则等待
mutex.P(); // 限制同一时刻只能有一个线程进入缓冲区
sub c to the buffer // 消费物品
mutex.V(); // 解锁
emptyBuffers.V(); // 缓冲区空闲空间增加
注意：生产者与消费者程序中，V操作交换不会产生问题，但P操作顺序交换，可能导致死锁
四、信号量实现
a. 实现方式
使用硬件原语: 禁用中断；原子指令(test-and-set)
例如：
b. 信号量问题
读写代码比较困难，容易出错，不能处理死锁问题
五、管程
1. 概述
目的：分离互斥和条件同步的关注
什么是管程：
- 一个锁：指定临界区
- 0或者多个条件变量：等待/通知信号量用于管理并发访问共享数据
一般方法：
- 收集在对象/模块中的相关共享数据
- 定义方法来访问共享数据
2. 流程
a. 管程组成
Lock：
- Acquire：等待直到锁可用，然后抢占锁
- Release：释放锁，如果有等待者，则唤醒
Condition Variable:
- 允许等待状态进入临界区：允许处于等待(睡眠)的线程进入临界区
- wait() 操作: 释放锁，睡眠
- signal() 操作：唤醒等待者
b. 管程执行流程
管程原理流程：
- 进入管程需要一个队列，取得lock
- 进入管程后，可以执行管程维护的一系列函数
- 若线程资源得不到满足，需要挂在某个队列中，并释放lock
// 初始化
int numWating=0;
WaitQueue q;// 等待线程 wait(lock)
numWating++; // 等待的线程数加一
add this thread to q; // 将线程加入到等待队列
release(lock); // 释放线程持有的锁
schedule(); // 调度,需要加锁
require(lock); // 获得调度的线程请求获得锁// 唤醒线程 signal()
if(numWating>0){Remove a thread t from q; // 将线程从等待队列中取出wakeup(t); // 唤醒线程，需要加锁numWating--; // 等待的线程数减1
}c. 管程实现生产者/消费者问题
// 初始化
Lock lock;
int count=0;
Condition notFull,notEmpty;// 生产者
lock.Acquire();
while(count==n){ // buffer已经满了，生产者需要等待notFull.Wait(&lock); // 线程于等待队列中等待，并释放锁
}
Add to buffer; // 生产数据
count++;
notEmpty.Signal(); // 唤醒消费者
lock.Release(); // 释放锁// 消费者
lock.Acuqire(); // 获取锁
while(count==0){notEmpty.Wait(&lock); // 等待审查者生产数据
}
Remove from buffer; // 消费数据
count--;
notFull.Signal(); // 唤醒生产者
lock.Release(); // 释放锁问题：
线程A发起signal() 后，是立即执行唤醒的线程，还是等线程A执行完毕再执行唤起的线程?若立即唤醒的线程，则管程中会同时出现两个线程
六、经典同步问题
1. 读者-写者问题信号量实现
a. 概述
b. 读者优先
// 初始化
CountMutex=new Semaphore(1);
WriteMutex=new Semaphore(1);
int count=0;// 写者
WriteMutex.P(); // 等待写锁
write; // 写入数据
WriteMutex.V(); // 读者
CountMutex.P(); // 计数器加锁
if(count==0){ // 如果不存在读者，则需要获取写锁，避免有写线程存在WriteMutex.P(); // 增加写锁
}
count++; // 读线程数量+1
CountMutex.V();read(); // 读数据CountMutex.P();
count--;
if(count==0){WriteMutex.V(); // 计数器为0，释放写锁
}
CountMutex.V(); c. 写者优先
// 初始化
ReadCountMutex=new Semaphore(1);
WriteCountMutex=new Semaphore(1);
WriteMutex=new Semaphore(1);
ReadMutex=new Semaphore(1);
int writeCnt=0;
int readCnt=0;// 写者
WriteCountMutex.P(); // 获取计数器锁
if(writeCnt==0){ // 若计数器为0，则需要竞争读锁ReadMutex.P();
}
writeCnt++; // 写数量加1
WriteCountMutex.V(); // 请求写锁WriteMutex.P(); // 一次仅有一个线程可以写
write;
WriteMutex.V(); // 释放写锁WriteCountMutex.P();
writeCnt--;
if(writeCnt==0){ReadMutex.V(); // 释放读锁
}
WriteCountMutex.V();// 读者
ReadMutex.P(); // 申请锁，使得有写线程等待时，读线程需要排在写线程之后被唤醒
ReadCountMutex.P();
if(readCnt==0){WriteMutex.P(); // 若不存在读线程，则需要等待写锁
}
readCnt++; // 若在写线程之前，读线程之后，有读线程到达，不加锁，直接进入临界区
ReadCountMutex.V();
ReadMutex.V();do_read(); // 读数据ReadCountMutex.P();
readCnt--;
if(readCnt==0){WriteMutex.V();
}
ReadCountMutex.V();
2. 读者-写者问题管程实现(TODO)
思路:
