一、管程

一种新的同步机制

1.1 为什么会出现管程

• 问题
  信号量机制的不足：程序编写困难、易出错
• 解决
  在程序设计语言中引入管程成分，这是一种高级同步机制

1.2 定义

• 是一种特殊的模块
• 有一个名字
• 由关于共享资源的数据结构及在其上操作的一组过程组成
• 进程与管程：进程只能通过调用管程中的过程来间接的访问管程中的数据结构

1.3 管程要保证什么

作为一种同步机制，管程要解决两个问题：

• 互斥
  管程是互斥进入的，主要是为了保证管程中数据结构的数据完整性。管程的互斥性是由编译器负责保证的。

• 同步
  管程中设置条件变量及等待/唤醒操作以解决同步问题。这两个操作可以让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

1.4 应用管程时遇到的问题

设问：是否会出现这样一种场景，与多个进程同时在管程中出现？
场景：当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权。当后面进入管程的进程执行唤醒操作时（例如P唤醒Q，即将前面的进程唤醒了），管程中便存在两个同时处于活动状态的进程。
如何解决：有三种处理方法

• P等待Q执行（Hoare管程）
• Q等待P继续执行（MESA管程）
• 规定唤醒操作为管程中最后一个可执行的操作（Hansen管程）

1.4.1 Hoare管程

1
说明：上图中的资源为共享资源，而对资源的操作我们使用多个过程表示。有些进程在进入管程时可能条件不成熟，需要等待，这里为不同的等待进程设置了不同的条件变量，这通过wait操作完成，当然，在后面可能条件成熟了，需要唤醒，这里使用signal操作完成。在这种管程中，前面的进程进入等待，后面被唤醒的进程执行，此时前面的进程是管程内的进程，于是进入的是紧急等待队列。

• 因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入口处等待。为此，管程的入口处设置一个进程等待队列，称为入口等待队列。
• 如果进程P唤醒进程Q，则P等待Q执行；如果进程Q执行中又唤醒进程R，则Q等待R执行；....,如此，在管程内部可能会出现多个等待进程。于是在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列。

条件变量的实现

• 条件变量：在管程内部说明和使用的一种特殊类型的变量。如var c : condition
• 对于条件变量，可以执行wait和singal操作
• wait(c)操作：如果等待紧急队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入c链的末尾。
• singal(c)操作：如果c链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾。

二、管程的应用

2.1 管程的实现

管程的实现有两种途径：

• 直接构造：效率高
• 间接构造：用某种已经实现的同步机制去构造，例如信号量和PV操作。

2.2 用管程解决生产者消费者问题

2
说明：左边的代码是管程的代码，右边是生产者消费者代码。生产者生产一个进程或线程后只需要调用管程，将其添加进去即可。而消费者只需要从管程中取即可。因为管程每次只允许一个进程或线程执行，所以可以保证同步问题。在Java中有类似的机制，但是C/C++中没有。

三、MESA管程

• Hoare管程的一个缺点
  两次额外的进程切换
• 解决
  将Hoare管程中的signal改成了notify，就是当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到一个通知，发信号的进程继续执行。
• notify的结果：位于条件队列的进程在将来合适的视乎且当处理器可用时恢复执行
• 由于不能保证在它之前没有其他进程进入管程，因而这个进程必须重新检查条件（while循环取代if语句）
• 导致对条件变量至少一次额外的检测（但不再有额外的进程切换），并且对等待进程在notify之后何时运行没有任何限制，这是其缺点，但是确实比Hoare管程的效率要高。

3.1 生产者/消费者问题

3
说明：从上图可以看到只是判断有所区别，其他的和之前的都差不多。

3.2 改进notify

• 对notify的一个很有用的改进
  1、给每个条件原语关联一个监视计时器，不论是否被通知，一个等待的时间超时的进程将被设为就绪态。
  2、当该进程被调度时，会再次检查相关条件，如果条件满足则继续执行。

• 超时可以防止如下情况的发生
  当某些进程产生相关条件的信号之前失败时，等待该条件的进程就会被限制地推迟执行而处于饥饿状态。

• 引入BROADCAST
  使所有在该条件上等待的进程都被释放并进入就绪队列

  • 当一个进程不知道有多少个进程被激活时，这种方式是非常方便的。
    例子：生产者/消费者问题中，假设insert和remove函数都适用于可变长度的字符块，此时，如果一个生产者往缓冲区中添加了一批字符，它不需要知道每个正在等待的消费者准备消耗多少字符，而仅仅执行一个broadcast，所有正在等待的进程都得到通知并再次尝试运行。
  • 当一个进程难以判断将激活哪个进程时，也可以使用这种广播机制

3.3 Hoare管程与MESA管程的比较

• Mesa管程优于Hoare管程之处在于Mesa管程错误比较少
• 在Mesa管程，由于每个过程在收到信号后都重新检查管程变量，并且由于使用了while结构，一个进程不正确的broadcast广播或发信号notify不会导致收到信号的程序出错。收到信号的程序将检查相关的变量，如果期望的条件没有满足，它会重新继续等待

四、PTHREAD中的同步机制

这种同步机制其实就是POSIX Threads同步机制，是一个线程函数库。

4
说明：在这种机制中对于互斥的保证是使用一个互斥量mutex。我们可以可能可以创建init和销毁destroy。可以加锁lock和解锁unlock，还有尝试加锁trylock。在解决同步问题的时候使用的是条件变量。同时是可以进行创建和销毁等操作。

4.1 讨论PTHREAD_COND_WAIT

这个函数执行可以分解为三个主要动作：

• 1、解锁（释放锁）
• 2、等待
  当收到一个解除等待的信号（pthread_cond_sinal或者pthread_cond_broad_cast）之后，pthread_cond_wait马上需要做的动作是：
• 3、上锁

五、进程间通信IPC

5.1 为什么需要通信机制

• 信号量和管程的不足：不能传递大量的信息
• 不适用多处理器的情况
• 进程间通信机制
  消息传递：send & receive原语。适用于分布式系统、基于共享内存的多处理器系统、单处理器系统，可以解决进程间的同步问题、通信问题。

5.2 基本通信方式

• 消息传递
• 共享内存
• 管道
• 套接字
• 远程过程调用

5.3 消息传递

5
说明：当发送进程将相关的消息准备好之后，由于其不能直接操作接收进程，所有相关的发送工作需要操作系统来完成，发送进程将消息发送给操作系统之后就不需要管理了。这里执行了陷入内核和复制消息两部操作。而操作系统在接收到消息之后，是将消息队列的指针挂到接收进程的PCB末尾，当接收进程被调度上cpu之后，此进程才会去内核中复制相关的消息。

5.3.1 用PV操作实现send原语

6
说明：对于receive的原语实现这里就多说了。

5.4 共享内存

7
说明：这里有两个问题需要解决

• 1、两个进程之间如何共享内存，我们可以将两个进程的地址空间映射到同一块物理地址空间上，于是其操作的资源是相同的。
• 2、读者写者问题。共享的内存不能同时写，但是可以同时读。我们可以使用读者写者方法解决互斥问题。

5.5 管道通信方式PIPE

8

利用一个缓冲传输介质（内存或文件）连接两个相互通信的进程

• 按字符流的方式写入读出
• 先进先出顺序
• 管道通信机制必须提供的协调能力
  互斥、同步、判断对方进程是否存在

六、典型操作系统中的IPC机制

6.1 进程同步/通信实例

9

6.2 Linux的进程通信机制

10
说明：从图中可以看到Linux继承了多个操作系统的IPC机制。同时也是基于POSIX机制。

6.2.1 Linux内核同步机制

11

原子操作

• 不可分割，在执行之前不会被其他任务或事件中断
• 常用于实现资源的引用计数
• atomic_t
  12

屏障

• 一种同步机制（又称栅栏、关卡）
• 用于对一组线程进行协调
• 应用场景
  一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进，比如矩阵运算。