信号量 (semaphore) 与 互斥 (mutex) 的介绍和原理

编辑于 2016-09-21

* 移动设备下, 可左滑手指以查看较宽代码

信号量用于多线程/进程的同步, 在操作系统和一些多线程软件 (如 MySQL) 中用到.



参考文献: Operating Systems A Modern Perspective

临界区

在解释信号量之前, 先看下这个问题:

有一程序, 使得两个进程 p1 和 p2 并行执行, 都访问一个共同的整数变量 x. 例如, 进程 p1 处理存款, 同时进程 p2 处理借贷.如:

//假设为公共变量
double balance; 

//进程 p1
balance = balance + a;

//进程 p2
balance = balance - a;

当上面的代码同时执行时, 就会出现临界区问题. 假设单 CPU 上进程 p1 执行到 balance = balance + a; , 然后调度到进程 p2, 就会使 p1 的操作丢失.

balance = balance + a; 和 balance = balance - a; 所在的区域就是 临界区 (critical section). 让任何一个进程进入临界区的时候, 排斥其他进程进入此临界区, 这样就可以避免临界区问题.

信号量

信号量 (semaphore) 是操作系统中的一种抽象数据类型, 它实现多进程的临界区约束.

P (s) : [while(s==0)(wait); s--]

V (s) : [s++]

信号量 s 是一个非负整数变量. 而方括号内的语句, 表示其中的操作是原子性 (atomic) 的(即不可分割的操作). 为此, 信号量通常在内核中实现. 其中 v 操作的执行不可中断, P 操作的目的是, 不可分割地检测一个整数变量, 如果变量为 0, 则阻塞进程; 而 v 操作则是通知一个被阻塞的进程恢复执行.

上面是标准定义,也常见这种定义:

P (s) : [s--; if(s<0) asleep(queue);]

V (s) : [s++; if(s<=0) wakeup(queue);]

asleep(queue):执行此操作的进程的 PCB 进入 queue 尾部,进程变成等待状态
wakeup(queue):将 queue 头进程唤醒插入就绪队列

设有两个同时执行的进程:

//进程1
int mutex=1;
while(1) {
    //非临界区
    p(mutex);
    //临界区
    v(mutex);
}

//进程2
int mutex=1;
while(1) {
    //非临界区
    p(mutex);
    //临界区
    v(mutex);
}

如上, mutex (意为互斥) 的初始值为1, 当一个进程准备进入相应的临界区, 它先进行 p 操作. 第一个进程激活 p 操作后, 第二个进程就会被阻塞. 当第一个进程执行到 v 操作后, 因而第二个进程获得 CPU 的控制权, 进而继续执行. 这样, 两个(或多个)进程不会同时进入临界区.

扩展到应用层, 比如 MySQL 的锁, 就是基于此思想实现. 它是利用嵌入机器码来屏蔽中断以实现原子性.

常用模型

有限缓存区生产-消费者模型:

生产者 (producer)向缓存区放入数据, 消费者(consumer)读. 当缓存区满就阻塞生产者, 当缓存区空或者有消费者占用此资源时阻塞消费者.

semaphore mutix = 1;
semaphore full = 0; // 缓存区初始为空
semaphore empty = N; // 缓存区的大小

producer () { //生产者进程
    while(1) {
        P(empty); //是否空缓冲区
        P(mutex); //进入临界区
        //将数据放入缓冲区
        V(mutex); //离开临界区,释放互斥信号量
        V(full); //满缓冲区数加1
    }
}
consumer () { //消费者进程
    while(1) {
        P(full); //判断缓冲区是否有
        P(mutex); //进入临界区
        //从缓冲区中取出数据
        V(mutex); //离开临界区,释放互斥信号量
        V(empty); //空缓冲区数加1
    }
}

注意 P 操作的次序, 如果 P(mutex) 和 P(full) 互换, 如果某时刻缓存区空, 消费者将获得 mutex, 然后被 full 阻塞, 形成死锁.