第2章进程同步概念

看第一个例子某游艺场设置了一个自动计数系统，用一个计数器count指示在场人数。当一个人进入时，由进程in实现计数加1；当退出一人时，由进程out实现计数减1。如果这两个进程各自顺序执行，其执行结果毫无疑问是正确的。但是由于入场和退场是随机的，因此，这两个进程的执行是并发的。将并发执行的进程用cobegin和coend括起来，可表示如下：voidprocessin(){intR1;R1:=count;R1:=R1+1;count:=R1;}voidprocessout(){intR2;R2:=count;R2:=R2-1;count:=R2;}main(){intcount;count:=0;cobeginprocessin();processout();coend}假定某时刻的计数值count=n，这时有一个人要进入，正好另一个人要退出，于是进程in和out都要执行。如果进程in和out的执行都没有被打断过，那么各自完成了count+1和count-1的工作，使计数值保持为n,这是正确的。按这样的次序执行后，count的最终值不能保持为n,而变成了n+1。占用处理机的进程执行的操作Count的值inR1:=countR1:=R1+1in被打断，由out占用并运行到结束R2:=countR2:=R2-1Count:=R2in继续运行Count:=R1如果两个进程执行中，由于某种原因进程in被打断，且进程调度使它们的执行呈下面的次序：nn-1n+1如果被打断的进程情况如下表所示：占用处理机的进程执行的操作Count的值inR1:=countR1:=R1+1in被打断，out占用R2:=countR2:=R2-1out被打断，in占用Count:=R1in被打断，out占用Count:=R2两个进程执行完后，count的最终值为多少?n-1nnn+1n-1上例中的程序段并发执行出现错误结果是由于两程序段共享资源count，从而使得执行结果受执行速度影响。一般情况下，并发执行的各程序段如果共享软、硬件资源，都会造成其执行结果受执行速度影响的局面。怎样保证上述执行结果的正确性?第二个例子cp进程计算pp进程打印3574我们如何来保证进程间的先后次序的关系？第三个例子引入进程并发提高系统效率进程异步执行（断续）资源非封闭（共享）导致程序结果不可再现引入进程同步机制进程相互合作（同步）临界资源有效共享（互斥）结果可再现2.4进程同步(协调)

2.4.1进程同步的基本概念1.两种形式的制约关系间接制约：对于临界资源共享的进程。“互斥”(2)直接制约：合作进程之间进行协作－－等待来自合作进程的信息。“同步”进程同步的任务：保证系统中的进程互斥地访问系统临界资源。保证协作(合作)进程前后执行顺序的协调。11进程的同步(synchronism)：

多道程序系统中，许多进程之间可能存在以下两种制约关系：

1.源于资源共享的间接制约关系（互斥）

2.源于相互合作的直接制约关系（同步）后者即一种合作进程在独自并发执行过程中的某些确定的时序点上“你等我，我也等你”的同步约束，前者可视为后者的特例。进程同步和互斥间的关系：相似处：进程的互斥实际上是进程同步的一种特殊情况；进程的互斥和同步统称为进程同步。差别：进程互斥是进程间共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；

进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。2.临界资源（CriticalResource）系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源.临界资源分为硬临界资源、软临界资源解决第一个例子这种问题的关键是，把共享变量count作为临界资源处理。让进程互斥的访问共享变量count。3.临界区把在每个进程中访问临界资源的那段代码，称为临界区。如能保证进程互斥的进入自己的临界区，便可实现进程对临界资源的互斥访问。当进程需要使用临界资源时，通过获得临界区的使用权实现的。

首先，在“进入区”，判断是否可进入。如果可以进入，则必须设置临界区使用标志。后来的进程通过标志，知道不能进入临界区，就进入阻塞队列。当临界区内的进程使用完毕，退出临界区时，即在“退出区”修改临界区使用标志，并唤醒阻塞队列一个进程，让其进入临界区。3.临界区把每个进程中访问临界资源的那段代码称为临界区（criticalregion）。不允许多个并发进程交叉执行的一段程序。任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。 While(TRUE) {…...

进入区

临界区

退出区 …… }进程间的互斥关系进程互斥（间接制约）

由于竞争临界资源而相互制约。这种对共享资源的排他性的使用关系就是进程的互斥关系。

临界资源访问控制是进程同步的基本问题。对临界区的访问要互斥访问。4.进入临界区的准则空闲让进：当临界资源空闲时，允许一个进程进入临界区。忙则等待：临界资源正被访问时，其它进程必须等待。有限等待：应保证进程能在有限时间内能进入自己的临界区。让权等待：如果进程不能进入自己的临界区、应立即释放处理机。例：进程A进程B请求资源R请求资源RR释放资源R唤醒分配拒绝释放资源R继续调度实现进程间的互斥访问方法软件方法硬件方法信号量方法管程方法消息传递方法软件方法采用软件方法实现互斥，很难。能实现两个进程互斥，但很难控制多个进程互斥。软件设计不能解决忙等现象。2.4.2硬件同步机制1.关中断While(true){关中断临界区打开中断剩余区}处理机的调度都是由中断所引起的（主要是定时器中断）。如果进入临界区前将所有外部中断屏蔽，则在运行临界区时将不会响应所有外部中断事件，也就不可能发生进程切换，待进程执行完临界区后再开中断。缺点：交由用户进程管理中断的开关是非常不安全的，一旦用户程序关中断后忘记打开，则整个系统将无法响应外部事件而崩溃；另外，在多处理器系统中，关中断也仅屏蔽本处理器的中断响应，对其他处理器中运行的进程无法屏蔽。因而通常中断屏蔽都由OS进行管理，由OS使用它来保证一些核心操作的不可中断性。2.4.2硬件同步机制

2.利用Test-and-Set指令实现互斥

这是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实现互斥的方法。在许多计算机中都提供了这种指令。3.利用Swap指令实现进程互斥

该指令称为对换指令，在Intel80x86中又称为XCHG指令，用于交换两个字的内容。TS(Test-and-Set)booleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}参数是true，返回true，lock=true参数是false，返回false，lock