一. 信号量
- 定义：信号量：一个用于表示系统中某种资源数量的变量。
用于解决互斥与同步的机制，只能被两个标准原语 wait()，signal() 访问，简写为 P（），V（）【或简称 P 操作，V 操作】。
- 原语：完成某种功能且不被分割、不被中断执行的操作序列，通常由硬件实现。
- 不被中断：在单处理机上可由软件通过屏蔽中断方法实现。
- 不被中断：原语变量操作过程如果被打断，，可能会运行另一个对同一变量的操作过程，出现临界段问题。
整形信号量
- 定义：用于表示资源数目的整形量 S。
- 操作：相比于普通整型变量，对整型信号量操作只有：初始化，wait 操作，signal 操作。
- 特点：wait 操作只要信号量 S≤0，就会不断循环测试。未遵循“让权等待”原则，使进程处于“忙等”状态。
记录型信号量
- 定义：不存在“忙等现象”的进程同步机制。
- 特点：需要一个整型变量 value 代表资源数目，和一个进程链表 L 用于链接所有等待该资源的进程。
- 遵循“**让权等待”**原则。
对信号量 S 进行一次** P 操作**，表示进程请求一个该类资源，执行** S.value–**，可供分配的该类资源数量减 1，
- S.value < 0 时候，资源分配完毕，调用 block 原语进行自我阻塞**【运行态—>阻塞态】, 放弃 CPU 并插入该类资源的等待队列 S.L。**
对信号量 S 进行一次** V 操作**，表示进程释放一个该类资源，执行** S.value++**，可供分配该类资源的数量加 1.
- 若 S.value++后，S.value < 0 ，则调用 wake 原语将 S.L 中第一个进程唤醒。【阻塞态—>就绪态】
利用信号量实现进程互斥
- 对于多进程访问的临界资源，设置互斥信号量 S 初值为 1；
- 将多个进程访问该资源的临界区置于 P（S）和 V（S）之间。
访问该资源的进程进入临界区之前，先对 S 进行 P 操作，
若该进程未被访问，则 S 操作成功执行，进程进入自己的临界区；否则阻塞进程。保证了资源互斥访 问。
访问该资源的进程退出后，对 S 执行 V 操作释放临界资源。
S∈[-1，0，1]。S=0：资源未被访问；S=1：有一个进程访问；S=-1：一个进程访问，一个进程阻塞，稍后需要 wake 唤醒。
P 操作，V 操作成对出现。
下图中 muxtax 即为上面的 S。
利用信号量实现同步
- 同步：源于进程之间相互合作，将原来异步并发的进程相互配合，有序推进。
例如：进程 P1 和 P2 异步并发执行，由于进程 P2 需要使用进程 P1 的结果，因此必须保证进程 P2 执行在进程 P1 执行结束之后。
- 实现方法：设置同步信号量 S，初值为 0【表示该资源最初不存在，需要由进程 P1 来产生。】
利用信号量实现前驱关系
信号量也可以用来描述程序或语句之间的前驱关系，如下图前驱图关系和代码逻辑：
分析进程同步与互斥问题
- 关系分析：找出进程数，分析同步/互斥关系。。将它们之间的关系按照上图中经典范式改写。
- 思路整理：根据进程操作流程，确定 P/V 操作的大致顺序。
- 信号量设置：设置信号量，确定信号量初值【互斥信号量初值 1，同步信号量初值视情况而定。】。
二. 经典同步问题
生产者-消费者问题
多生产者-多消费者问题
读者-写者问题
信号量设置
- 需要设置信号量 count 作为计数器，记录当前读者数量，初值为 0；
当有读者时：count > 0，写者无法写文件；同时，不同读者对计数器访问互斥。
- 设置 mutex 为互斥信号，用于保护更新 count 变量时的互斥；
- 设置互斥信号量 rw，用于保证读者和写着互斥访问。
读进程优先
- 存在读进程时，写操作被延迟
- 只要有一个读进程活跃，后续读进程都可以访问文件。
- 特点：可能造成写进程长时间等待，导致写进程“饿死”。
写进程优先
- 存在读进程时候，如果写进程请求访问，禁止后续读进程请求。
- 没有写进程时候，允许读进程运行。
- 条件：需要增加一个信号量并在上面程序 writer()和 reader() 函数中各增加一对 PV 操作，得到写进程优先程序。
这里的写进程优先 并不是真正意义的写进程优先，是相对写进程优先。该算法又称读写公平法。
例如：
如果当前存在写进程执行，后续有一个读进程+一个写进程在排队请求，则当前进程结束后先执行读进程【先来先服务】。原因在于 V 操作的唤醒进程作用于队首，而后续队列中，读进程是先来的，占据了队首。
哲学家进餐问题
思路一：出现死锁
思路二：改进策略
为了防止死锁发生，可以对哲学家加以限制。例如：最多同时允许 4 名哲学家进餐，仅当哲学家左右两边筷子都可用时候才允许他进餐；对哲学家按顺序编号，对奇偶编号哲学家规定相反先拿筷子的方向等。
制定规则：仅当哲学家左右两边筷子都可用时候才允许他进餐
吸烟者问题
信号量设置
- 信号量 offer1，offer2，offer3 分别表示 烟草和纸的组合资源，烟草和胶水组合资源，纸和胶水的组合资源。
- 信号量 finish 用于互斥进行抽烟动作。
三. 管程
- 信号量机制中，每个访问临界资源的进程都必须自备同步的 PV 操作，大量分散同步操作给操作系统管理带来麻烦 , 并且容易导致死锁。
- 管程
- 作为新的进程同步工具，保证进程的互斥，降低死锁可能性。
- 提供条件变量，让程序员灵活实现进程同步。
定义
- 管程：抽象地表示系统中共享资源的数据结构，以及对该共享数据结构实施操作的一组过程构成的资源管程序。
一组过程 作用：根据资源情况接受或阻塞进程访问，确保单进程使用共享资源，以便统一管理共享资源的访问，实现进程互斥。
- 组成：
- 管程的名称
- 局部对于管程内部的共享数据结构说明。
- 对该数据结构进行操作的一组过程 （或函数）。
- 对局部于管程内部的共享数据设置初始值的语句。
- 描述举例
》
拓：管程类似于面向对象编程（如 Java）中的类
特点：
- 管程对将对共享资源的操作封装起来
- 管程內部共享资源只能被管程内的过程访问。进程只有调用管程内过程才能访问共享资源，如上例中外部进程只能调用 take_away（）过程来申请资源。归还资源同理。
- 每次只允许一个进程进入管程
- 各进程只能串行执行管程内过程，保证了临界资源 S 的互斥访问。
条件变量
当一个进程进入管程后被阻塞，直到阻塞原因解除 期间，如果进程不释放管程，其他进程就无法进入管程。
因此，将阻塞原因定义为条件变量。
- 每个条件变量保存一个等待队列，记录由于该条件而阻塞的所有进程。
- 对条件变量只能进行两种操作：wait 和 signal。
- x.wait：当 x 对应的条件不满足时候，对正在调用管程的进程调用 x.wait 将自己插入 x 条件的等待队列，释放管程。
- x.signal：当 x 对应条件变化，调用 x.signal 唤醒一个因 x 条件阻塞的进程。
- 举例：
管程 VS 信号量
- 相似点：条件变量 wait/signal 操作类似信号变量的 P/V 操作，可以阻塞/唤醒进程。
- 不同点
- 条件变量：”没有值“，仅实现”排队等待“功能。
- 信号量：“有值”，信号量的值反映了剩余资源数量。
在管程中，剩余资源数量使用共享资源数据结构记录。
