同步的概念
- 协调多线程对共享数据的访问
- 任何时刻只能有一个线程执行临界区代码
信号量
是操作系统提供的一种协调共享资源访问的方法。
- OS是管理者，地位高于进程
- 用信号量表示系统资源的数量
信号是一种抽象数据类型
- 由一个整形(sem)变量和两个原子操作组成
- P操作：
a. sem减1；
b. 如sem<0,进入等待，否则继续 - V操作：
a. sem加1；
b. 若sem <=0,唤醒一个等待进程
信号量的特性：
- 信号量是被保护的整数变量
a. 初始化完成后，只能通过P和V操作修改
b. 由操作系统保证PV为原子操作 - P可能被阻塞，V不会被阻塞
- 通常信号量是”公平的“
a. 线程不会被无限期阻塞在P操作
b. 假定信号量等待按队列顺序
信号量的实现：
class Semaphore{
int sem;
WaitQueue q;
}
Semaphore::P(){
sem --;
if(sem < 0){
Add this thread t to q;
block(t);
}
}
Semaphore::V(){
sem ++;
if(sem <= 0){
Remove a thread t from q;
wakeup(t);
}
}
信号量的分类：
- 二进制信号量：资源数目为0或1
- 资源信号量：资源数目为任何非负数
信号量的使用：
- 互斥访问：临界区的互斥访问控制
每类资源设置为一个信号量，其初始值为1
mutex = new Semaphore();
mutex->P();
Critical Section;
mutex->V();
必须成对使用PV操作
P操作保证互斥访问临界资源
V操作保证使用后释放临界资源
PV操作不能次序错误，重复或遗漏
- 条件同步：线程间的事件等待
条件同步设置一个信号量，其初始值为0
conditon = new Semaphore(0);
假设线程A和B同时在执行，若要满足A在执行N操作前，线程B必须要完成X操作
线程A
....M....
conditon->P();
....N....
线程B
....X....
conditon->V();
....Y....
如上，若线程A先于线程B执行，那么执行到P操作，会被阻塞，直到线程B
完成X操作，执行V，信号量为1，这时A才可以继续执行下去。
管程
管程是一种用于多线程互斥访问共享资源的程序结构
a. 采用面向对象方法，简化了线程间的同步控制。
b. 任一时刻最多只有一个线程执行管程代码。
c. 正在管程中的线程可临时放弃管理的互斥访问，等待事件出现时恢复管程的使用
a. 在对象/模块中，收集相关共享数据
b. 定义访问共享数据的方法管程的组成
a. 一个锁：控制管理代码的互斥访问
b. 0或多个条件变量：管理共享数据的并发访问
管程
条件变量
- 条件变量是管程内的等待机制
a. 进入管程的线程因资源被占用而进入等待状态
b. 每个条件变量表示一种等待原因，对应一个等待队列 - Wait操作
a. 将自己阻塞在等待队列中
b. 唤醒一个等待者或释放管程的互斥访问 - Signal操作
a. 将等待队列中的一个线程唤醒
b. 如果等到队列为空，则等同空操作
条件变量的实现：
Class Condition{
int numWaiting = 0;
WaitQueue q;
}
Condition::Wait(lock){
numWaiting ++;
Add this thread t to q;
release(lock);
schedule();
require(lock);
}
Condition::Signal(){
if(numWaiting > 0){
Remove a thread t from q;
wakeup(t);
numWaiting --;
}
}
