type
status
date
slug
summary
tags
category
icon
password
能力模型
能力分类
省赛
全球总决赛
学习进度
中国总决赛
本篇主要是目的是进行个人知识梳理和总结，不含技术性实现的详细内容，若涉及实际技术性操作的内容，会另起一文。
本篇主要参考王道考研书籍。
信号量机制
背景
进程通常分为就绪、运行和阻塞三个工作状态。三种状态在某些条件下可以转换，三者之间的转换关系如下：
进程三个状态之间的转换就是靠PV操作来控制的。PV操作主要就是P操作、V操作和信号量。其中信号量起到了至关重要的作用。
定义
信号量机制是由荷兰学者Dijkstra提出的，用于解决进程互斥与同步问题。用户进程可以通过OS提供的一对原语来操作信号量，从而方便的实现进程的同步与互斥。信号量是最早出现的用来解决进程同步与互斥的机制
信号量
信号量(Saphore)由一个值和一个指针组成，指针指向等待该信号量的进程，信号量的值表示相应资源的使用情况。信号量可以理解为一个用于表示系统中资源数量的变量.
- 当S > 0时，表示当前可用资源的数量；
- 当S < 0时，其绝对值表示等待使用该资源的进程个数。
eg：系统中一台打印机，可以设置一个初值为1的信号量。
原语
原语是一种特殊的无法被中断的程序段，由关中断/开中断指令实现。
P、V操作
即wait(S)和signal(S)原语，人们常称PV操作（首字母来自于荷兰单词）。P（S）等同于wait（S），V（S）等同于signal（S）。
- P操作（wait）：申请一个单位资源，进程进入，S=S-1
- V操作（signal）：释放一个单位资源，进程出来，S=S+1
注：信号量的值只能由PV操作来改变。
信号量机制
P（S）：
①将信号量S的值减1，即进行S = S-1；
②如果S < 0，则该进程进入阻塞队列；
③如果S >= 0, 则该进程继续执行。
执行一次P操作意味着请求分配一个资源，因此S的值减1。当信号量的值小于0，那么就表示没有可用资源，那么进程就只能进行等待其他拥有该资源的进程释放资源之后，才能进行执行；当信号量大于0的时候，那么表示还有足够的资源，所以，当前进程就可以继续执行。
V（S）：
①将信号量S的值加1，即 S = S + 1；
②如果S > 0，则该进程继续执行；
③如果S < 0, 则释放阻塞队列中的第一个等待信号量的进程。
执行一个V操作意味着释放一个资源，因此S的值加1。当信号量的值大于0，那么就表示有可用资源，那么表示信号量的资源足够进程进行申请，就不需要将进程进行放入到阻塞队列中；而当信号量小于0的时候，就表示针对这个信号量，还有其他的进程是已经进行了申请信号量的操作，而只是之前是无法满足进程获取资源的，简单点说，就是表示阻塞队列中还有其他的进程是执行了P操作，在等待信号量，所以，这样的话，就讲阻塞队列中的第一个等待信号量的进程进行处理即可。
使用PV操作时的注意事项
（1）每个程序中用户实现互斥的P、V操作必须成对出现。
（2）互斥信号量的初值一般为1。
（3）互斥时PV在同一进程出现，而同步时PV在不同进程出现。
（4）互斥信号量的初值一般为1。
（5）同步P在互斥P前，即mutex是紧挨着临界区操作的。
信号量分类
整型信号量
信号量如果单纯是一个整数型的变量，那么就称为整型信号量，它的值记录了系统中某种资源的数量。在使用整型信号量的情况下，P 、V 操作是类似这样的：
以进程 P0，P1 为例进行说明：
假定 P0 想要进入临界区，那么它就会在进入区申请资源：执行 P 操作，进行“检查”和“上锁”，由于 S 一开始是1（表示目前有一个资源可以使用），所以 P0 可以跳过循环，成功申请到资源。此后，S 减一变为 0，代表已经没有可用资源了 —— 这一步也相当于上锁；对于 P1，当他想要申请资源的时候，同样先来到进入区执行 P 操作，由于 S = 0，所以此时 P1 陷入了死循环；再回到 P0 ，他完成任务后会在退出区释放资源，S加一变为 1，这时候 P1 才有机会退出循环，进而申请资源。
由于“检查”和“上锁”两个操作被封装在一个原语里，所以P、V这两个操作必定是一气呵成、无法被打断的，这就避免了某个进程钻空子的现象。但是同时我们也发现，在 P0 时间片用完后，P1 仍然会占用处理机进行没有意义的死循环，也就是仍然违背了“让权等待”的原则。
于是在此基础上，又出现了记录型信号量。
记录型信号量
与整型信号量仅用一个单一变量记录可用资源数不同，记录型信号量的数据结构类似于一个结构体，它不仅记录了可用资源数
value，而且还提供了一个等待队列 L。记录型信号量的思想其实是，如果由于 P0 在使用临界资源而导致 P1 暂时无法使用，那么干脆就不给 P1 陷入循环的机会，直接让它自己去阻塞队列，这样 P1 在被唤醒之前，永远无法占用处理机，也自然就不可能出现白白占用处理机的情况。而在 P0 释放资源后，我们才来考虑唤醒 P1。
记录型信号量的结构如下所示：
同时，记录型信号量的 P、V 操作也有所不同，如下所示：
- 这里要注意的第一个地方是，
value是可用的资源数，当它大于 0 的时候自然是存在可用资源（供大于求），当它小于 0 的时候，则说明不仅无可用资源而且有其他进程等着用（供不应求）。
- 第二个地方是，在进入区 value 一定会减一，表示申请到了资源，或者表示存在着某个进程有想要申请资源的意愿
下面我们用例子来说明记录型信号量工作的过程，为了加深记忆，这里用四个进程来说明：
假设计算机中有两台可用的打印机 A 和 B（也就是说，value = 2），有四个进程需要用到打印机资源。
一开始假定是 P0 先占有处理机，那么 P0 就会在进入区申请资源 。由于 value 一开始是 2，所以 P0 成功申请到资源 A，之后 value 数量减一变为 1，同时来到临界区开始“干活”；在 P0 的时间片完了之后，P1 占有处理机，此时同样申请到资源 B，value 由 1 变为 0，之后来到临界区“干活”。自此，两个打印机都被占用了。
在 P1 的时间片完了之后，P2 占有处理机，value 由 0 变为 -1 < 0，前面我们说过，value < 0 说明无可用资源，所以此时 P2 将自己主动送到了阻塞队列。接着来到了 P3，value 由 -1 变为 -2，P3 同样进入阻塞队列。P2，P3 都从运行态转为阻塞态。
处理机又来到 P0，P0 很快执行完了，于是在退出区执行 P 操作释放资源，将 value 加一变为 -1，之后由于通过 if 检测到阻塞队列中有进程等着用资源，所以马上唤醒了队头的 P2 ，P2 从阻塞态回到就绪态，并直接进入临界区开始自己的工作，在完成后同样来到退出区释放资源，value 由 -1 变为 0，但是在 if 中还是检测到了队列中仍然有进程等着用资源，于是马上把队头的 P3 唤醒，P3 回到就绪态，并直接进入临界区开始工作，此后，value 由 0 变为 1，此时 if 不通过，说明队列中再也没有其它进程等着了，该拿到资源的进程都拿到了。自此，P0，P2，P3 都拿到了 A 资源，而 P1 也在不久后完成工作，在退出区释放资源 B，此时 value 从 1 变回最初的 2 ，代表占用的资源已经全数归还。
PS：当然，实际情况还可能是，P2 拿到了 A 资源，P3 拿到了 B 资源，但分析过程也是大同小异的。
显然，记录型信号量与前面介绍的所有方法最大的区别就在于，不会再有进程白白占用处理机进行没有意义的循环 —— 相反地，这些进程非常“老实”地把自己送到了阻塞队列，选择在那里慢慢地等待，等待其它进程完成后将自己唤醒，这种做法“既方便了别人，也方便了自己”。这就正好与我们多次强调的”让权等待“非常契合了。
记录型信号量明显优于整型信号量，所以在提到 PV 操作的时候，一般默认指的都是记录型信号量。
同步与互斥的实现
互斥信号量
如果要使得两个进程互斥访问共享内存，我们可以初始化信号量为
1。
具体过程如下：
- 进程 A 在访问共享内存前先执行 P 操作，因为信号量的初始值为 1，执行 P 操作后信号量变为 0，表示共享资源可用，进程 A 可以访问共享内存。
- 此时，如果进程 B 也想访问共享内存并执行 P 操作，信号量会变为 -1，表示临界资源已被占用，因此进程 B 被阻塞。
- 直到进程 A 访问完共享内存后，执行 V 操作，信号量恢复为 0，并唤醒被阻塞的进程 B，使其可以继续访问共享内存。最后，进程 B 完成访问后执行 V 操作，信号量恢复到初始值
1。
可以发现，信号初始化为
1 表示这是一个互斥信号量，它可以确保在任何时刻只有一个进程可以访问共享内存，这有效地保护了共享内存的安全性。伪代码实现如下：同步信号量
如果要实现多线程同步，我们可以初始化信号量为
0。
具体过程如下：
- 如果进程 B 先执行，那么在执行 P 操作时，信号量初始值为 0，因此信号量会变为 -1，表示进程 A 还没有生产数据，结果导致进程 B 被阻塞等待。
- 随后，当进程 A 生产完数据并执行 V 操作时，信号量会变为 0，进程 B 被唤醒。
- 此时，进程 B 被唤醒后，意味着进程 A 已经生产了数据，因此可以正常读取数据。
可以发现，信号量初始化为
0 表示这是一个同步信号量，确保进程 A 先于进程 B 执行。进程同步的关键步骤如下:
- 设置信号量初始值为 0
- 在”前操作“之后执行 V(S)
- 在”后操作“之前执行 P(S)
P 先于 V 执行 ===> P 所在进程会被阻塞 ===> ”后操作“始终无法执行
示例如下：
信号量实现进程前驱关系
是否可以理解为是同步关系的多个信号量的扩充？
其实这种情况就是把多个同步问题结合起来，对于每一对前驱关系来说，都有属于本关系的信号量，所以我们仍然是可以用信号量机制来实现的。代码大概如下：
可以观察到，除了 P1 进程之外，其它进程首先执行的都是 P 操作，所以一旦这些进程之一首先拿到处理机使用权，都无一例外地会进入阻塞队列。由于情况很多，这里我们试着只分析某一种情况 ——
假设一开始是 P2 占有处理机，那么由于 signal1 初始为 0，导致了 P2 进队列，此后处理机来到 P3，P3 同样进队列… 以此类推，阻塞队列就会变成：
随后总算来到 P1 进程了，P1 进程作为一切的开始，特殊之处就在于它不是以 P 操作开始的，P1 会首先执行 V(signal1)，这一步把 signal1 加一，同时唤醒 P2 进程，P2 进程进入就绪队列：
再之后，P1 执行 V(signal2)，这一步把 signal2 加一，同时唤醒 P3 进程，P3 进程也进入就绪队列。
P1 执行完之后，就绪队列队头的 P2 进入运行态，执行到 V(signal3) 的时候，signal3 加一，同时唤醒 P4 进程，P4 进程进入就绪队列，
再之后，P2 执行 V(signal4)，这一步把 signal4 加一，同时唤醒 P5 进程，P5 进程也进入就绪队列。
P2 执行完之后，处理机调度就绪队列队头的 P3 开始执行，P3 执行到 V(signal7) 的时候，signal7 加一，注意这一步没有唤醒任何进程
P3 执行完之后，处理机调度就绪队列队头的 P4 开始执行，P4 执行到 V(signal5) 的时候，signal5 加一，同时唤醒 P6 进程，P6 进程进入就绪队列
P4 执行完之后，处理机调度就绪队列队头的 P5 开始执行，P5 执行到 V(signal6) 的时候，signal6 加一，注意这一步没有唤醒任何进程（阻塞队列已经没有进程了）
P5 执行完之后，处理机调度就绪队列队头的 P6 开始执行，P6 的 signal6 、signal7 在前面已经得到加一操作，所以此时绝对不会在这里卡住，可以顺利执行，直到结束。
分析进程同步和互斥问题的方法步骤
- 关系分析：找出问题中的进程数，并分析它们之间的同步和互斥关系，其中进程可以理解为一个操作。
- 整理思路：进程数n，缓冲区大小m
- 信号量设置：互斥信号量=1，同步和前驱关系信号量=0
经典同步问题
生产者-消费者（有界缓冲区问题）
- 问题描述
一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中读取消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。
- 问题分析
- 关系分析
- 整理思路
- 信号量设置
生产者和消费者对缓冲区的访问属于互斥关系，而针对“消息”则生产者和消费者属于协作关系，只有生产者生产了消息，消费者才能使用消息，因此又是同步关系。
两组进程存在互斥和同步关系，也就是要解决互斥和同步PV的操作的位置。
设置一个 mutex 为互斥信号量，用于控制互斥访问缓冲池，初值设为 1；
信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为 0；
信号量 empty 用于记录当前缓冲池中“空”的缓冲区数，初值为 n；
- 进程描述
- Note
- 两个进程中两个P操作顺序不能颠倒，颠倒可能发生以下情况：empty=0，mutex=1时producer执行P(mutex)进入临界区后P(empty)进行阻塞，此时consumer执行P(mutex)也阻塞，从而导致无休止的等待。
- 两个进程中两个V操作顺序可以颠倒
- AND信号量解法
利用 AND 信号量来解决时，用 Swait(empty，mutex) 来代替 wait(empty) 和 wait(mutex)，用 Ssignal(mutex, full) 来代替 signal(mutex) 和 signal(full)。用 Swait(full，mutex) 代替 wait(full) 和 wait(mutex)，以及用 Ssignal(mutex，empty) 代替 Signal(mutex) 和 Signal(empty)。利用 AND 信号量来解决生产者-消费者问题的代码描述如下：
- 管程解法
利用管程来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为 procducerconsumer(PC)。用整型变量 count 来表示在缓冲池中已有的产品数目，其中包括两个过程：
过程 | 说明 |
put(x) | 生产者利用该过程将自己生产的产品投放到缓冲池中 |
get(x) | 消费者利用该过程从缓冲池中取出一个产品 |
对于条件变量 notfull 和 notempty，分别有两个过程 cwait 和 csignal 对它们进行操作：
过程 | 说明 |
cwait(condition) | 当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件 condition 的队列上 |
csignal(condition) | 唤醒在 cwait 执行后阻塞在条件 condition 队列上的进程 |
PC 管程可描述如下：
在利用管程解决生产者-消费者问题时，可用代码描述为：
读者-写者问题
- 问题描述
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程同时访问共享数据时则可能导致数据不一致的错误，因此：
① 允许多个读者可以同时对文件执行读操作；
② 只允许一个写者往文件中写信息；
③ 任一写者在完成写操作之前不允许其他读者进程或写者工作；
④ 写者执行写操作前，应让已有的读者和写者全部退出。
- 问题分析
- 关系分析
- 整理思路
- 信号量设置
读者和写者互斥的，写者和写者互斥，读者和读者之间不互斥。
两个进程，读者和写者。由于写者和其他进程都互斥，因此可用互斥信号量的P操作、V操作解决；读者则较为复杂，与写者互斥的同时，又要与其他读者同步，需要一个计数器用于判断当前是否有读者读文件：当有读者时，写者不能写文件，此时读者一直占用文件直到退出，写者才可以写文件；同时，不同读者对计数器的访问也是互斥的。
设置 count 信号量为计数器，初值为 0；
mutex 为互斥信号量，用于保护更新count 变量时的互斥；
互斥信号量 rw 用于保证读者和写者互斥访问。
- 进程描述
- 读进程优先
- 读写公平
- 信号量集机制解法
此时读者一写者问题引入一个限制，最多只允许 RN 个读者同时读，为此又引入了一个信号量 L，并赋予其初值为 RN。通过执行 wait(L, 1, 1) 操作来控制读者的数目，每当有一个读者进入时，就要先执行 wait(L，1，1) 操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN + 1 个读者要进入读时，必然会因 wait(L，1，1) 操作失败而阻塞。
哲学家就餐问题
- 问题描述
一张圆桌上坐着5名哲学家，每两名哲学家之间的桌子上摆着一根筷子，两根筷子之间是一碗米饭，如下图所示：
哲学家倾注毕生精力于思考和进餐，哲学家思考时不影响其他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿地哲学家只有同时拿到了两根筷子才能开始进餐，进餐完毕，放下筷子继续思考。
- 问题分析
- 关系分析
- 整理思路
- 信号量设置
5 名哲学家与左右邻座对其中间的筷子的访问时互斥关系。
5 个哲学家对应5 个进程，问题解决的关键就是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。
解决方法有两个：
①让他们同时拿两根筷子；
② 是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
互斥信号量数组
chopstick[5]={1,1,1,1,1}，用于对 5 个筷子的互斥访问；哲学家编号顺序：0~4，哲学家 I 左边筷子的编号为 i，哲学家右边筷子的编号为(i+1)%5。- 进程描述
解决死锁
关于PV操作容易产生的一些疑问：
1，S大于0那就表示有临界资源可供使用，为什么不唤醒进程？
S大于0的确表示有临界资源可供使用，也就是说这个时候没有进程被阻塞在这个资源上，所以不需要唤醒。
2，S小于0应该是说没有临界资源可供使用，为什么还要唤醒进程？
V原语操作的本质在于：一个进程使用完临界资源后，释放临界资源，使S加1，以通知其它的进程，这个时候如果S<0，表明有进程阻塞在该类资源上，因此要从阻塞队列里唤醒一个进程来“转手”该类资源。比如，有两个某类资源，四个进程A、B、C、D要用该类资源，最开始S=2，当A进入，S=1，当B进入S=0，表明该类资源刚好用完， 当C进入时S=-1，表明有一个进程被阻塞了，D进入，S=-2。当A用完该类资源时，进行V操作，S=-1，释放该类资源，因为S<0，表明有进程阻塞在该类资源上，于是唤醒一个。
3，如果是互斥信号量的话，应该设置信号量S=1，但是当有5个进程都访问的话，最后在该信号量的链表里会有4个在等待，也是说S=-4，那么第一个进程执行了V操作使S加1，释放了资源，下一个应该能够执行，但唤醒的这个进程在执行P操作时因S<0，也还是执行不了，这是怎么回事呢？
当一个进程阻塞了的时候，它已经执行过了P操作，并卡在临界区那个地方。当唤醒它时就立即进入它自己的临界区，并不需要执行P操作了，当执行完了临界区的程序后，就执行V操作。
4，S的绝对值表示等待的进程数，同时又表示临界资源，这到底是怎么回事？
当信号量S小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目.S大于0时表示可用的临界资源数。注意在不同情况下所表达的含义不一样。当等于0时，表示刚好用完。
以上就是我对PV操作的一些肤浅理解，还请多多指教。
参考链接
信号量之PV操作
经典同步问题
- 操作系统 经典同步问题（51CTO博客）
- 【Linux多线程】三个经典同步问题（C语言实现代码）
- 经典同步问题（附上习题）
- 操作系统—经典同步问题（稀土掘金）
- 操作系统：经典同步问题（乌漆）（提供多种解法）
有关问题，欢迎您在底部评论区留言，一起交流~
- Author:Koreyoshi
- URL:https://Koreyoshi1216.com/article/10ec7b13-c6a7-80e5-a198-c886c29b3a6a
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!