并发进程的执行可能是有关的,也可能是无关的。
无关并发进程是指他们分别在不同的变量集合上操作,所以一个进行的执行与其它并发的进程并不会有变量集(值)交集。
有关并发进程是指他们可能共享变量集上的某些变量,如果没有进行PV操作(后面会介绍,暂时挂起),那么可能在同时“存、取、改”操作上产生错误。
针对上面的的共享变量,有一个定义叫"临界区"，定义为：有关并发进程中的共享变量有关的程序段。
临界区/临界资源
一次只允许一个进程使用的资源称为临界资源。为了保证临界资源的正确使用,可以把临界资源的访问过程分成四个部分:进入区->临界区->退出区->剩余区
如何管理临界区正常的运行(也就是上面说的进行“存、取、改”操作不产生错误)呢？
总体概括为这三个要求：互斥性、进展性、有限等待性
互斥性：也就是如果一个进程已经在它的临界区执行,那么其它进程挂起,暂时不能进入该临界区执行;
进展性：如果该进程不在它的临界区执行,那么不应该阻止其他进程进入该临界区执行;
有限等待性：某个进程进入一个临界区应该在有限时间内完成。
互斥软件的实现方法
实现方法有三种:标志法、严格轮换法、Peterson算法
标志法: 例如两个进程执行,使用标记来判断他们是否进入了临界区。
缺点:刚好两个进程同时进入各自临界区的情况不能解决。
int inside1, inside2; /* 定义两个标志分别来判断是否进入了临界区 */ inside1 = 0; /* 表示进程P1不在临界区 */ inside2 = 0; /* 表示进程P2不在临界区 */ process P1{ while(inside2); /* 如果P2进程在临界区内,那么就等待P2退出临界区 */ inside1 = 1; /* 如果P2进程不在临界区,那么P1进入临界区,并进行标志 */ ... /* 进入临界区执行 */ inside1 = 0; /* 退出临界区,将标志设置为0,表示退出 */ } process P2{ while(inside1); /* 如果P1进程在临界区内,那么就等待P1退出临界区 */ inside2 = 1; /* 如果P1进程不在临界区,那么P2进入临界区,并进行标志 */ ... /* 进入临界区执行 */ inside2 = 0; /* 退出临界区,将标志设置为0,表示退出 */ }
严格轮换法: 使用指针来判断那个程序应该进入临界区。
缺点:造成while循环的忙等待。
int turn; /* 设置指针turn */ turn = 0; /* 表示进程P0可以进入进程 */ process P0{ while(turn == 1); /* 如果turn为1,表示此时该是P1进程进入临界区,那么执行等待 */ ... /* 如果上面while不等待,那么进入临界区执行 */ turn = 1; /* 在进程P0执行完毕就换为进程P1来执行 */ } process P1{ while(turn == 0); /* 如果turn为0,表示此时该是P0进程进入临界区,那么执行等待 */ ... /* 如果上面while不等待,那么进入临界区执行 */ turn = 0; /* 在进程P1执行完毕就换为进程P0来执行 */ }
Peterson算法:是上面两种情况的结合，具体是：先为每个进程设置一个标志,如果标志inside=1表明请求进入进程,然后在使用turn指针表示那个进程进入临界区。
互斥硬件的实现方法
有两种:中断屏蔽方法和硬件指令法
中断屏蔽方法:使进程进入临界区执行,不响应中断,不切换进程。
好处:简单。缺点：系统代价较高,影响了并发性,无法在多处理器系统中使用。
硬件指令法:测试并设置指令TS;使用Swap指令来管理临界区。
缺点：同样存在“忙等待”