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