操作系统原理，并发环境下进程互斥与同步，软件层实现临界区，lock封装成为原语实现临界区，afteryou思想类似trylock引发活锁，Dekker由系统决定进程，Peterson避免忙等待，硬件层

操作系统原理，并发环境下进程互斥与同步，软件层实现临界区，lock封装成为原语实现临界区，afteryou思想类似trylock引发活锁，Dekker由系统决定进程，Peterson避免忙等待，硬件层

O、进程同步互斥机制
并发是所有问题产生的基础，也是系统设计的基础。

一、并发环境下的进程特点：
1、并发的，单个进程的执行是间断性的，进程的相对执行速度不可预测
2、资源共享，进程和线程之间同时占用某个资源会引发错误，如多个进程同时使用打印机打印文件，或者同时对一个文件进行写入
3、进程执行的结果与其执行的相对速度有关，是不确定的，对于有执行先后顺序要求的多个进程，可能引发时序问题，例如ATM取钱等

二、进程互斥：
1、各进程需要共享资源，包括变量和文件等
2、进程使用资源时需要排他性使用，避免同时使用
3、进程之间竞争使用这些资源，这种关系叫做互斥

三、临界区（互斥区）与临界资源
1、临界资源：critical resource，系统中的某些资源一次只允许一个进程使用，这种资源就是临界资源，或互斥资源，共享变量啥的
2、临界区：critical section，各个进程中对某个临界资源实施操作的程序片段，这样的程序片段存在于各种检查中，当进程A进入一个临界区，进程B想要进入这个临界区，就会进入等待（阻塞），直到进程A离开临界区，临界区空出来，进程B再进入，利用临界资源。

四、临界区使用原则：
1、临界区无进程时，想加入临界区的进程可进入临界区
2、不允许两个进程同时进入临界区
3、临界区外运行的进程不得阻塞其他进程进入临界区
4、不得使进程无限期等待进入临界区

五、软件层面实现临界区：
1、lock
使用标志free代表临界区状态，默认为false
While(free)
{
Free=true;
…
Free=false;
}
进程对变量free的写操作分为多步，如果一个进程写free为true之前另一个进程读到free为false，也进入临界区，临界区中还是有了两个进程。
将写free的操作封装为lock和unlock并将其设置为避免中断的原语，就可以实现临界区的功能。

2、afteryou思想，另一个不进的情况下，自己进，引发活锁，类似try lock
进程A
Aturn=true;
While(Bturn)
{
…临界区
Aturn=false;
}
进程B
Bturn=true;
While(Aturn)
{
…临界区
Bturn=false;
}
进入临界区的条件：
进程A：Aturn ^ not Bturn
进程B：not Aturn ^ Bturn

3、Dekker算法，使用变量turn代表可以进入临界区的进程
进程q和基础p都想要进入临界区时，临界区标识符turn为2表示希望进程q进入，turn为1表示希望进程p进入。
进程P：
Pturn=true;
While(qturn)
{
If(turn == 2)
{
Pturn =false;//让出CPU
While(turn ==2)
{
Pturn = true;//让自己进入循环
}
}
}//等待对方让出临界区
…临界区
Turn=2;//执行完毕
Pturn=false;

进程q：
qturn=true;
While(Pturn)
{
If(turn == 1)//临界区希望进程p进入
{
qturn =false;//q让出CPU
While(turn ==2)
{
qturn = true;//q让自己进入循环
}
}
}//等待对方让出临界区
…临界区
Turn=1;//执行完毕
qturn=false;

这里的while为qturn不停赋值仍然会消耗CPU的时间片（强制轮流），称为忙等待，浪费了一定的CPU资源，但实现了临界区的功能。

4、Peterson算法
进程通过enter_region(i)函数进入临界区，函数leave_region(i)离开临界区
两个函数的实现
#define FALSE 0
#define TRUE 1
#define N 2 //进程个数
Int turn; //轮到谁
Int interested[N];//想要进入临界区的进程，默认都为FALSE
Void enter_region(int process)//process为0或1
{
Int other;//另一个进程的pid
Other=1-process;
Interested[process]=TRUE;
Turn=process;
While(turn==process && inerested[other]==TRUE);//进入循环，即阻塞，不进入循环则是成功进入临界区
}

Void leave_region(int process)
{
Interested[process]=FALSE;//本进程已离开临界区
}
peterson算法解决了互斥问题，并且克服了强制轮转的缺点，可以完全正常的工作

软件层面主要通过while循环阻塞实现互斥。

硬件层面的解决方案：

一、“开关中断”指令，锁CPU
1、流程
执行“关中断”指令
临界区操作
执行“开中断”指令
2、特点：
简单高效，代价高昂（临界区的大小会对CPU的并发能力产生限制）
不适用于多处理器
操作系统能调用但应用进程无法调用

二、TSL指令，测试并加锁指令，锁总线
三、交换指令，XCHG，交换寄存器处操作
四、多处理器情况下有一种叫做自旋锁的概念

来源：优秀的邓宗磊