Process Synchronization
进程同步
背景
协作进程 ：与系统内的其它进程相互影响的进程
协作有两个方面的体现
- 共享逻辑地址空间
- 通过文件或消息来共享数据
共享逻辑地址空间可能会导致各种各样的问题，比如共享数据可能因为并发的访问而不同
假设有两个协作进程要访问修改共享地址中的Counter变量，CPU修改变量要经过三步
1
2
3
MOV ax,Counter
ADD ax,1
MOV Counter,ax
然而在系统中进程是并发执行的；这意味着P1进程可能还没执行完这三个步骤就被P2抢占执行了，这时Counter的值可能会跟我们预想的不一样
我们把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步；
进程同步的各种机制确保协作进程有序的执行
临界区问题
每个进程都有一段临界区，当一个进程进入临界区，没有其他进程可被允许在临界区内执行，即没有两个进程可同时在临界区执行
临界区的通用结构：
1
2
3
4
5
6
7
8
9
do{
/* 进入区 */
临界区
/* 退出区 */
剩余代码
}while(1)
临界区问题的解答要满足三个要求
- 互斥
前进 ：如果没有进程在临界区执行，那么就要选择进程进入临界区执行
- 有限等待 ：从一个进程请求进入临界区的请求允许为止，其它进程允许进入临界区的次数有限
软件同步（Peterson算法）
该算法是一个基于软件的对临界区问题的解答，Peterson算法适用于两个进程在临界区和剩余区交替执行，该算法在两个进程共享两个数据项
- int turn 表示哪个进程可以进入临界区
- bool flag[2] 表示哪个进程请求进入临界区
turn = i 时，进程i允许进入临界区执行
硬件同步
任何临界区都需要一个简单工具 锁；进入临界区要请求锁，退出临界区要释放锁
- 在单处理器系统中，可以通过禁止中断来解决临界区问题
- 在多处理器系统中，提供了特殊硬件指令以允许原子地（不可中断）执行一些操作
信号量
对于应用程序而言，解决临界区问题可用成为 信号量 的同步工具，信号量S是个整数变量，除了初始化外，只能通过两个标准原子操作：wait() 和 signal() 来访问；这些操作原来被称为PV原语（荷兰语proberen，测试；荷兰语verhogen，增加）
wait()的定义可表示为
1
2
3
4
5
6
7
8
wait(S){
while(S <= 0){
//循环等待
}
S--;
}
signal()的定义可表示为
1
2
3
4
signal(S){
S++;
}
在PV操作中，对信号量的修改必须不可分地执行，即当一个进程修改信号量时不能有其它进程也在修改信号量
计数信号量的值域不受限制，二进制信号量的值只有0和1，经常称二进制信号量为互斥锁，因为可以提供互斥
自旋锁
上面所定义的信号量的主要缺点是忙等待；当一个进程进入临界区，任何试图进入其临界区的进程都必须在wait() 中无限循环等待，在多道程序系统中这显然是个问题，忙等待白白浪费了CPU的时钟；这类的信号量也称为自旋锁
为了克服忙等待，可以修改wait() 和 signal() 的定义
当一个进程执行wait() 必须等待时，该进程会阻塞自己，阻塞操作将一个进程放入到与信号量有关的等待队列中，并将该进程的状态切换成阻塞态
一个被阻塞的进程可以通过其它进程执行signal() 操作来唤醒，通过执行wakeup() ，该进程从阻塞态切换到就绪态，该进程会被调入到就绪队列中等待被调度
死锁和饥饿
死锁 ：两个或多个进程无线等待一个事件，而该事件只能由等待进程之一来产生
饥饿 ：无限期阻塞，进程在信号量内无线等待