• 在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于系统中的诸进程之间存在两种不同形式的制约关系

并发进程的关系

• 两种形式的制约关系
• 间接相互制约关系
  • 资源共享关系：同处于一个系统中的进程必然共享某种资源
  • 需互斥地访问临界资源。
  • 如A、B共享打印机，若A申请打印时，打印机已分配给B，则A只能阻塞，等B释放后再改为就绪，又称为"互斥"
• 直接相互制约关系
  • 相互合作关系：（进程直接制约）
  • 如进程A向B提供数据，当输入缓冲空时，B不能得到数据而阻塞；反之当缓冲满时，A无法写入而阻塞，又称为"同步"

进程的互斥与同步

示例

互斥关系

进程A和进程B在各自的执行过程中，都需要使用变量M作为其中间变量

同步关系

进程A和进程B共用堆栈S的情况
目标：由进程A将数据顺序压入堆栈，再由进程B将数据反向弹出堆栈

进程的互斥与同步

进程同步的示例

进程的互斥与同步

进程同步的示例

进程的相互关系：可以按照相互感知的程度来分类

互斥，指多个进程不能同时使用同一个资源；
死锁，指多个进程互不相让，都得不到足够的资源；
饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）

临界资源与临界区

临界资源：

• 引起不可再现性是因为临界资源没有互斥访问。
• 一次仅允许一个进程使用的资源
• 系统中许多硬件如打印机等，诸进程之间只能用互斥的方式进行访问
• 每个进程中访问临界资源的那段代码（程序段）称为临界区。
• 同时对临界资源提出访问的 诸进程执行时要加以限制，即对临界资源- 必须排它性访问。这种排它性访问就是应保证共享临界资源的诸进程互斥地进入自己的临界区。

临界资源：某段时间内只允许一个进程使用的资源（即互斥资源）。

临界区：进程中访问临界资源的代码段。

• 解决办法：把公用变量s作为临界资源处理，进程P1和进程地P2互斥地访问公用变量s。

临界区（critical section）

• 不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问
• 在每个进程中访问临界资源的那段代码称为临界区(critical section)
• 每个进程进入临界区之前应先对欲访问的临界资源进行检查，看是否正在被访问。如果此刻该临界资源未被访问，该进程可进入临界区，并设置它正在被访问的标志，在临界区之前执行的这段代码称为进入区（entry section）
• 在临界区之后也要加上一段代码，用于将临界区被访问的标志恢复为未被访问的标志，称为退出区（exit section）

同步机制应遵循的规则

• 空闲让进
  当无进程处于临界区时，应允许一个进程进入临界区
• 忙则等待
  当已有进程进入临界区时，其他进程必须等待
• 有限等待
  对要求访问临界资源的进程，应保证在有限时间内进入自己的临界区，防止"死等"
• 让权等待
  当进程不能进入自己的临界区时，应立即释放处理机，防止"忙等"

同步机制应遵循的准则

• 空闲让进
  当无进程处于临界区时，临界资源处于空闲状态。此时允许进程进入临界区。
• 忙则等待
  当已有进程进入临界区时，临界资源正在被访问，其他想进入临界区的进程必须等待。
• 有限等待
  对于要求访问临界资源的进程，应保证在有效的时间内进入，以免进入“死等”状态。
• 让权等待
  当进程不能进入临界区时，应立即释放处理机，以免进程进入“忙等”。

信号量机制

• 1965年，荷兰学者Dijkstra提出的信号量（Semaphores）机制是一种有效的进程同步工具,所以P、V分别是荷兰语的test(proberen)和increment(verhogen)
• 信号量机制已从整型信号量发展为记录型信号量，又进一步发展为信号量集
• 目前，信号量机制已广泛应用于单处理机、多处理机以及计算机网络中
• 信号量就是OS提供的管理公有资源的有效手段
• 信号量代表可用资源实体的数量

信号量

整型信号量

• 最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作P(S)和V (S)来访问。这两个操作一直被分别称为P、V操作。 操作可描述为：
  P (S): while S≤0 do no-op
  S∶=S-1;
  V (S): S∶=S+1;
• P(S)和V (S)是原子操作，执行时是不可中断的。另外，在wait操作中，对S的测试和做S∶=S-1操作时都不可中断，信号量只能通过原语操作来访问，不能被进程调度所打断
• 缺点：信号量S≤0时“忙等”，未遵循“让权等待”

结构体型信号量

• **采取了“让权等待”**的策略，是一种不存在“忙等”现象的进程同步机制。
• 在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在记录型信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。

信号量的物理意义

从资源的观点看信号量的意义:

• s.value的初值表示系统中某种资源数目。

• P(s)表示要申请一个资源。P(S)操作表示“等信号”，即测试一个要等的信号是否到达；

• V(s)表示要释放一个资源。这个信号在实现同步时就是“合作者的伙伴进程已完成前趋任务”，在实现互斥时就是“临界资源可用”。

• s.value<0时，|s.value|表示等待队列的进程数。

• 当S≥0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；

• 当S＜0时，其绝对值表示信号量S的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。

• 另外，S的值只能由P、V操作来改变。

使用信号量实现进程互斥

• 有两个进程P1和P2要访问某一临界资源，它们各自的临界区为L1和L2。可设S为这两个进程的互斥信号量，其S.value的初值为1。这时，只需把临界区置于P(S) 和V(S) 之间即可实现两进程的互斥。
  
  为临界区设置一个互斥信号量mutex，将mutex.value 初值设置为1，然后将各进程的临界区（访问临界资源的那段代码）置于P(mutex) 和V(mutex) 之间。
  
  利用P、V操作原语实现进程的互斥
  即保证进程互斥地进入各自的临界区。
  • 这里所用信号量的初值一般为1，表示临界资源未被占用，且其可用数目为1。
  • 用P、V操作原语实现进程互斥的效率更高一些，因为P操作中引入了阻塞机制，所以消除了CPU忙等现象。

用信号量解决同步问题

• 若干进程为完成一个共同的任务而相互合作，这就需要相互合作的进程在某些协调点处（即需要同步的地方）插入对信号量的P操作或Ｖ操作，以便协调它们的工作（实现进程间的同步）。

公交车示例：

用信号量解决同步问题

使用信号量实现进程同步

• P、V操作原语
  信号量是一个数据结构
  由两个变量构成：整型变量S、指针变量Q
  初始化时，整型变量S为一非负整数
  当S变量的值为负数时，该值的绝对值代表Q指针所指向的进程控制块PCB的数目，被该指针所指向的进程处于等待状态
  当S变量的值不为负数时，Q指针指向空
  信号量的值只能被P、V操作原语进行改变
• 用P、V操作实现计数
  例：设有M个进程都要以独享的方式用到某一种资源，且一次只申请一个资源，该种资源的数目为Ｎ
  
• 用P、V操作实现进程的同步
  

信号量实现进程同步与互斥

用信号量机制的三个步骤：

（1）分析进程间的制约关系
（2）设置信号量
（3）实施P、V操作。

第一步是基础、关键，第三步是核心。

• 实现进程互斥与进程同步 ,P、V操作总是配对出现的。
• P,V在互斥问题中总是出现在同一个进程的代码中，临界区位于P,V之间；
• 在同步问题中， P、V操作是分别出现在两个合作进程的代码中，需要等消息的一方用P操作，相应的对同一信号量的V操作则在发出此消息的另一方中。