概念:
进程具有异步性特征:异步性指各并发执行的进程以各自独立、不可预知的速度向前推进。
如:读进程和写进程并发运行会导致异步性,所以操作系统使用“进程同步”解决异步问题。
一个时间段内只允许一个进程使用的资源称为临界资源。对临界资源的访问必须互斥的访问。
进程互斥指当一个进程访问某临界资源时,另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束,释放该资源之后,另一个进程才能去访问临界资源。
对临界资源的访问,逻辑上分四部分:
do{
entry section; // 进入区:检查是否可进入临界区,若可进,设置正在访问临界资源标志(上锁)。
critical section; // 临界区(段):访问临界资源的代码
exit section; // 退出区:解锁
remainder section; // 做其他处理
} while(true)
为实现对临界资源的互斥访问,同时保证系统整体性能,应遵循:
1、空闲让进。临界区空闲时允许一个进程访问
2、忙则等待。临界区正在被访问时,其他试图访问的进程需等待
3、有限等待。在有限时间内进入临界区,保证不饥饿。
4、让权等待。进不了临界区的进程,释放处理机,防止忙等。
软件实现方法:单标志法、双标志先检查、双标志后检查、Peterson算法
单标志法
两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是每个进程进去临界区的权限只能被另一个进程赋予。
int turn=0; //turn 表示当前允许进入临界区的进程号 P0进程: p1进程: while(turn !=0); while(turn != 1); // 进入区 critical section; critical section; // 临界区 turn =1; turn = 0; // 退出区 remainder section; remainder section; // 剩余区
该算法可实现“同一时刻最多只允许一个进程访问临界区”但违背“空闲让进”原则。
双标志先检查法
设置一个布尔型数组flag[],数组中各个元素用来标记各进程想进入临界区的意愿。
违反“忙则等待”原则,检查和上锁不是一气呵成的。
双标志后检查法
违背“空闲让进”和“有限等待”原则。
Peterson算法
结合双标志法、单标志法的思想,如果双方都争着想进入临界区,可以做谦让动作。
flag[1] = false;
remainder section;
未遵循“让权等待”原则。
硬件实现方法:中断屏蔽方法、testandset(ts指令/tsl指令)、swap指令(XCHG指令)
中断屏蔽方法:
利用“开/关中断指令”实现(同原语实现思想)。
优点:简单高效。
缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程。
TS/TSL指令:
用硬件实现
swap指令:
互斥锁。
需要连续循环忙等等互斥锁,都可成为自旋锁
信号量机制:整形信号量和记录型信号量。
整型信号量
记录型信号量:
遵循“让权等待”原则。
信号量机制: