第2章进程同步概念

1、mxh看第一个例子看第一个例子 某游艺场设置了一个自动计数系统，用一个计数某游艺场设置了一个自动计数系统，用一个计数器器count指示在场人数。当一个人进入时，由指示在场人数。当一个人进入时，由进进程程in实现计数加实现计数加1；当退出一人时，由；当退出一人时，由进程进程out实实现计数减现计数减1。 如果这两个进程各自顺序执行，其执行结果毫无如果这两个进程各自顺序执行，其执行结果毫无疑问是正确的。但是由于入场和退场是随机的，疑问是正确的。但是由于入场和退场是随机的，因此，这因此，这两个进程的执行是并发两个进程的执行是并发的。将并发执行的。将并发执行的进程用的进程用cobegin和和coend

2、括起来，可表示如下：括起来，可表示如下：mxhvoid processin() int R1 ; R1:=count ; R1:=R1+1 ; count:=R1; void processout() int R2 ; R2:=count ; R2:=R2-1 ; count:=R2; main() int count ; count:=0 ; cobegin processin() ; processout() ; coendmxh 假定某时刻的计数值假定某时刻的计数值count=n，这时有一这时有一个人要进入，正好另一个人要退出，于是个人要进入，正好另一个人要退出，于是进程进程 in和和o

3、ut都要执行。如果进程都要执行。如果进程in和和out的执行都没有被打断过，那么各自完成了的执行都没有被打断过，那么各自完成了count+1和和count-1的工作，使计数值保的工作，使计数值保持为持为n ,这是正确的。这是正确的。mxh 按这样的次序执行后，按这样的次序执行后，count的最终值不能保持的最终值不能保持为为n, 而变成了而变成了n+1。占用处理机的进程占用处理机的进程执行的操作执行的操作Count的值的值inR1:=countR1:=R1+1in被打断，由被打断，由out占用并运行到结束占用并运行到结束R2:=countR2:=R2-1Count:=R2in继续运行继续运行C

4、ount:=R1如果两个进程执行中，由于某种原因进程如果两个进程执行中，由于某种原因进程in被打断，且被打断，且进程调度使它们的执行呈下面的次序：进程调度使它们的执行呈下面的次序：nn-1n+1mxh如果被打断的进程情况如下表所示：如果被打断的进程情况如下表所示：占用处理机的进程占用处理机的进程执行的操作执行的操作 Count的值的值inR1:=countR1:=R1+1in被打断，被打断，out占用占用R2:=countR2:=R2-1out被打断，被打断，in占用占用Count:=R1in被打断，被打断，out占用占用Count:=R2两个进程执行完后，两个进程执行完后，count的最终值

5、为多少的最终值为多少? n-1nnn+1n-1mxh 上例中的程序段并发执行上例中的程序段并发执行出现错误结果是出现错误结果是由于由于两程序两程序段共享资源段共享资源count，从而使得执行结果受执行速度影从而使得执行结果受执行速度影响。响。 一般情况下，并发执行的各程序段如果一般情况下，并发执行的各程序段如果共享软、硬件共享软、硬件资源资源，都会造成其执行结果受执行速度影响的局面。，都会造成其执行结果受执行速度影响的局面。 怎样保证上述执行结果的正确性怎样保证上述执行结果的正确性?mxh第二个例子第二个例子mxhcp进程进程计算计算pp进程进程打印打印3574我们如何来保证进程间的我们如何来

6、保证进程间的先后次序的关系？先后次序的关系？第三个例子第三个例子mxh引入进程并发引入进程并发提高系统效率提高系统效率进程异步执行（断续）进程异步执行（断续）资源非封闭（共享）资源非封闭（共享）导致程序结果不可再现导致程序结果不可再现引入进程同步机制引入进程同步机制进程相互合作（同步）进程相互合作（同步）临界资源有效共享（互斥）临界资源有效共享（互斥）结果可再现结果可再现2.4 进进 程程 同同 步步 (协调协调) 2.4.1 进程同步的基本概念进程同步的基本概念 1. 两种形式的制约关系两种形式的制约关系 间接制约：间接制约： 对于对于临界资源共享临界资源共享的进程。的进程。 “互斥互斥”(

7、2)(2)直接制约直接制约：合作进程合作进程之间进行之间进行协作等待来自合作协作等待来自合作进程的信息。进程的信息。“同步同步”进程同步的任务进程同步的任务：保证系统中的进程保证系统中的进程互斥地访问系统临界资源互斥地访问系统临界资源。保证保证协作协作(合作合作)进程进程前后执行顺序的协调。前后执行顺序的协调。mxh11进程的同步进程的同步(synchronism)(synchronism)： 多道程序系统中，许多进程之间可能存在以下两多道程序系统中，许多进程之间可能存在以下两种制约关系：种制约关系： 1.1.源于源于资源共享资源共享的间接制约关系的间接制约关系（互斥）（互斥） 2.2.源于源

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

9、然联系固定的必然联系，哪个进程竞争到使用权就归那个进程使用，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；直到不需要使用时再归还； 则涉及共享资源的并发进程间则涉及共享资源的并发进程间有一种必然的联有一种必然的联系系，当进程必须同步时，即使无进程在使用共享资源时，那，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。么尚未得到同步消息的进程也不能去使用这个资源。mxh2. 2. 临界资源（临界资源（Critical ResourceCritical Resource） 系统中某些资源系统中某些资源一次一次只允许只允许一个进程一个进程使

10、用使用，称这样的资源为，称这样的资源为临界资源临界资源. . 临界资源分为临界资源分为硬临界资源硬临界资源、软临界资源软临界资源解决第一个例子这种问题的解决第一个例子这种问题的关键是关键是，把共把共享变量享变量countcount作为临界资源处理作为临界资源处理。让进程互。让进程互斥的访问共享变量斥的访问共享变量countcount。mxh3. 临界区临界区 把在每个进程中把在每个进程中访问临界资源的那段代访问临界资源的那段代码码，称为，称为临界区临界区。 如能保证如能保证进程互斥的进入自己的临界区进程互斥的进入自己的临界区，便可实现进程对临界资源的互斥访问。，便可实现进程对临界资源的互斥访问

11、。 当进程需要使用临界资源时，通过获得当进程需要使用临界资源时，通过获得临界区的临界区的使用权使用权实现的。实现的。mxh 首先，在首先，在“进入区进入区”，判断是否可进入。，判断是否可进入。如果可以进入，则如果可以进入，则必须设置临界区使用标志必须设置临界区使用标志。后来的进程通过标志，知道不能进入临界区，后来的进程通过标志，知道不能进入临界区，就进入阻塞队列。就进入阻塞队列。 当临界区内的进程使用完毕，退出临界当临界区内的进程使用完毕，退出临界区时，即在区时，即在“退出区退出区”修改临界区使用标志修改临界区使用标志，并唤醒阻塞队列一个进程，让其进入临界区。并唤醒阻塞队列一个进程，让其进入临

12、界区。mxh3. 临界区临界区 把把每个进程每个进程中访问临界资源的那段代码中访问临界资源的那段代码称为临界区（称为临界区（critical region）。）。不允许多个不允许多个并发进程交叉执行的一段程序。并发进程交叉执行的一段程序。 任何时刻，任何时刻，只允许一个进程只允许一个进程进入临界区进入临界区，以此实现进程对临界资源的，以此实现进程对临界资源的互斥访问互斥访问。While(TRUE) .进入区进入区临界区临界区退出区退出区mxh进程间的互斥关系进程间的互斥关系 进程互斥（间接制约）进程互斥（间接制约） 由于由于竞争临界资源竞争临界资源而相互制约。这种而相互制约。这种对共享资源的对

13、共享资源的排他性的使用关系排他性的使用关系就是就是进程的互斥关系。进程的互斥关系。 临界资源访问控制是进程同步的基本问题。临界资源访问控制是进程同步的基本问题。对对临界区临界区的访问要的访问要互斥访问互斥访问。mxh4. 进入临界区的准则进入临界区的准则 空闲让进：空闲让进：当临界资源空闲时，允许一当临界资源空闲时，允许一个进程进入临界区。个进程进入临界区。 忙则等待：忙则等待：临界资源正被访问时，其它临界资源正被访问时，其它进程必须等待。进程必须等待。 有限等待：有限等待：应保证进程能在有限时间内应保证进程能在有限时间内能进入自己的临界区。能进入自己的临界区。 让权等待：让权等待：如果进程不

14、能进入自己的临如果进程不能进入自己的临界区、应立即释放处理机。界区、应立即释放处理机。mxhmxh 例：mxh实现进程间的互斥访问方法实现进程间的互斥访问方法软件方法软件方法硬件方法硬件方法信号量方法信号量方法管程方法管程方法消息传递方法消息传递方法mxh软件方法软件方法 采用软件方法实现互斥，采用软件方法实现互斥，很难很难。能实现两个。能实现两个进程互斥，但进程互斥，但很难控制多个很难控制多个进程互斥。软件设计进程互斥。软件设计不能解决不能解决忙等忙等现象。现象。mxh2.4.2 硬件同步机制硬件同步机制1. 关中断关中断While (true)关中断关中断临界区临界区打开中断打开中断剩余区

15、剩余区 处理机的调度都是由中断所引起的（主要是定时处理机的调度都是由中断所引起的（主要是定时器中断）。如果器中断）。如果进入临界区前进入临界区前将所有将所有外部中断屏蔽外部中断屏蔽，则在运行临界区时将不会响应所有外部中断事件，也则在运行临界区时将不会响应所有外部中断事件，也就不可能发生进程切换，待进程执行完临界区后就不可能发生进程切换，待进程执行完临界区后再开再开中断中断。mxh缺点：缺点：交由用户进程管理中断的开关是交由用户进程管理中断的开关是非常不安全非常不安全的，的，一旦用户程序关中断后忘记打开，则整个系统将无法响一旦用户程序关中断后忘记打开，则整个系统将无法响应外部事件而崩溃；另外，在

16、应外部事件而崩溃；另外，在多处理器系统多处理器系统中，关中断中，关中断也仅屏蔽本处理器的中断响应，对其他处理器中运行的也仅屏蔽本处理器的中断响应，对其他处理器中运行的进程无法屏蔽。进程无法屏蔽。因而通常中断屏蔽都由因而通常中断屏蔽都由OS进行管理，由进行管理，由OS使用它来保使用它来保证一些核心操作的不可中断性。证一些核心操作的不可中断性。mxh2.4.2 硬件同步机制硬件同步机制2. 这是一种借助一条硬件指令这是一种借助一条硬件指令“测试并建立测试并建立”指令指令TS(Test-and-Set)以实现互斥的方法。在许多以实现互斥的方法。在许多计算机中都提供了这种指令。计算机中都提供了这种指令。 该指令称为对换指令，在该指令称为对换指令，在Intel 80 x86中又中又称为称为XCHG指令，用于交换两个字的内容。指令，用于交换两个字的内容。 mxhTS(Test-an