1、进程管理进程管理2进程互斥进程互斥两种形式的制约关系两种形式的制约关系系统中诸进程之间在逻辑上存在着两种制约关系：o直接制约关系（进程同步）直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。o间接制约关系（进程互斥）间接制约关系（进程互斥）：是进程共享独占型资源而必须互斥执行的间接制约关系。进程互斥进程互斥同同 步步互互 斥斥进程-进程进程-资源-进程时间次序上受到某种限制竞争到某一物理资源时不允许进程工作相互清楚对方的存在及作用，交换信息不一定清楚其进程情况往往指有几个进程共同完成一个任务往往指多个任务多个进程间通讯制约
2、例：生产与消费之间，发送与接受之间，作者与读者之间，供者与用者之间例：交通十字路口，单轨火车的拨道岔同步与互斥比较同步与互斥比较进程互斥进程互斥1 1、临界区、临界资源、临界区、临界资源 1 1次仅允许次仅允许1 1个进程使用个进程使用 具备这种特性的资源称为临界资源具备这种特性的资源称为临界资源(critical(critical resource)resource)，使用临界资源的那段程序称为临界段使用临界资源的那段程序称为临界段(critical section)(critical section)从进程角度看，它被各个进程互斥地使用从进程角度看，它被各个进程互斥地使用 临界资源、临界区
3、临界资源、临界区o例例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改:o其中R1和R2为处理机中的两个寄存器。A与B均对X+1，即X+2。o若按另一顺序对变量进行修改：o结果x只加了1。A:R1=X;A:R1=X;B:R2=X;B:R2=X;A:R1=R1+1;A:R1=R1+1;X=R1;X=R1;B:R2=R2+1;B:R2=R2+1;X=R2;X=R2;A:R1=X;A:R1=X;R1=R1+1;R1=R1+1;X=R1;X=R1;B:R2=X;B:R2=X;R2=R2+1;R2=R2+1;X=R2;X=R2;（1 1）变量）变量X X必必需按临界资源
4、需按临界资源处理。处理。（2 2）每个进程）每个进程中访问临界资中访问临界资源的那段代码源的那段代码称为临界区称为临界区临界资源、临界区临界资源、临界区o例例2 2：getspace和release:getspace:begin local g g stacktop top top-1 end release(ad):begin top top+1 stacktop ad end两个进程公用一个堆栈，堆栈是临界资源；访问堆栈的程序段就是临界区。临界资源、临界区临界资源、临界区为了保证临界资源的正确使用，可以把临界临界资源的访问过程资源的访问过程分成以下几部分：进入区临界区退出区剩余区v进入区增
5、加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问。v退出区增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。v剩余区进程中除了进入区、临界区及退出区之外的其余代码。临界资源、临界区临界资源、临界区 要进入临界区的若干进程必须满足要进入临界区的若干进程必须满足：（1 1）一次只允许一个进程进入临界区）一次只允许一个进程进入临界区（2 2）任何时候，处于临界区的进程不得多于一个）任何时候，处于临界区的进程不得多于一个（3 3）进入临界区的进程要在有限的时间内退出）进入临界区的进程要在有限的时间内退出（4 4）如果不能进入自己的临界区，则应让出处理机资源）如果不
6、能进入自己的临界区，则应让出处理机资源解决临界区（互斥）问题的几类方法：解决临界区（互斥）问题的几类方法：（1 1）软件方法）软件方法（2 2）硬件方法）硬件方法（3 3）P-VP-V操作操作进入区进入区临界区临界区退出区退出区剩余区剩余区互斥的定义互斥的定义 互斥的定义：互斥的定义：不允许两个以上的共享某一公有资源的并不允许两个以上的共享某一公有资源的并发进程同时进入临界区称为互斥。发进程同时进入临界区称为互斥。一组并发进程互斥执行需满足的准则一组并发进程互斥执行需满足的准则信号量（信号量（SemSem）的物理意义：的物理意义：信号量（信号量（SemSem）是一整数；是一整数；当当semse
7、m 0 0时代表可供并发进程使用的资源实体的数目；时代表可供并发进程使用的资源实体的数目；当当semsem 0=0调用进程入等待队列转进程调度返回V V操作的定义：操作的定义：信号量信号量semsem加加1 1；若若semsem加加1 1后仍大于零，则进程继续执行；后仍大于零，则进程继续执行；若若semsem加加1 1后小于或等于零，则从与该信号相对后小于或等于零，则从与该信号相对应的等待队列中唤醒一个等待进程，然后返回原应的等待队列中唤醒一个等待进程，然后返回原进程继续执行或转进程调度。进程继续执行或转进程调度。信号量的值仅能由信号量的值仅能由P P、V V原语操作改变。原语操作改变。P,V
8、P,V原语原语V操作流程图入口S=S+1S0唤醒等待队列中的一个进程返回或转进程调度返回用P、V操作实现简单的进程互斥或同步o解决此类问题的一般方式：n根据问题给出的条件，确定进程有几个或几类；n确定进程间的制约关系是互斥，还是同步；n各相关进程间通过什么信号量实现彼此的制约，标明信号量的含义和初值。n用P、V操作写出相应的代码段。n验证代码的正确性：设以不同的次序运行各进程，是否能保证问题的圆满解决。切忌按固定顺序执行各进程。用用P P、V V操作实现互斥操作实现互斥o用用信息量和信息量和P P、V V操作实现互斥的一般模型操作实现互斥的一般模型进程进程1 1P(mutex)P(mutex)
9、临界区临界区V(mutex)V(mutex)进程进程2 2P(mutex)P(mutex)临界区临界区V(mutex)V(mutex)进程进程n nP(mutex)P(mutex)临界区临界区V(mutex)V(mutex)例子：例子：设某游艺场设置了一个自动计数系统，用设某游艺场设置了一个自动计数系统，用一个计数器一个计数器count count 来指示在场的人数。当有一来指示在场的人数。当有一个人进入时，进程个人进入时，进程PINPIN实现计数加实现计数加1 1，当退出一，当退出一人时，进程人时，进程POUTPOUT实现计数减实现计数减1 1。由于入场和退场。由于入场和退场是随机的，因此是
10、随机的，因此PINPIN和和POUTPOUT是并发的。是并发的。用用cobegincobegin和和coendcoend表示并发执行，这两个表示并发执行，这两个进程的程序如下：进程的程序如下：用用P P、V V操作实现互斥操作实现互斥 main()begin count:integer;count:=0;cobegin process PIN Ru:integer;Begin Ru:=Count;Ru:=Ru+1;Count:=Ru;End;process POUT Cu:integer;Begin Cu:=Count;Cu:=Cu-1;Count:=Cu;End;Coend;End;用用P
11、P、V V原语实现进程的互斥原语实现进程的互斥（例如这里是互斥进入临界区）main()begin count:integer;S:semaphore;count:=0;S:=1;cobegin process PIN Ru:integer;Begin P(s);Ru:=Count;Ru:=Ru+1;Count:=Ru;V(s);End;process POUT Cu:integer;Begin P(s);Cu:=Count;Cu:=Cu-1;Count:=Cu;V(s);End;Coend;End;设置互斥信号量sem；给信号量置初值sem=1。进入临界区前，安排一条P操作指令。进入临界区。退出临界区后，安排一条V操作指令。用用P P、V V原语实现进程的互斥方法原语实现进程的互斥方法 P（sem）V（sem）临界区
