初探信号量机制

什么是信号量机制

1965年，荷兰学者 Edsger Dijkstra 提出了一种经典的实现进程互斥、同步的方法-- 信号量机制 。

信号量机制用于解决并发访问共享资源的同步问题。信号量机制的主要目的是确保多个进程在共享资源时不会发生冲突，并且能够正确地同步和通信。信号量机制如今在操作系统中被广泛应用，如进程间的同步和通信、资源分配、优先级调度等。

信号量机制诞生之前

在信号量机制出现之前，解决进程互斥问题的方法主要有以下几种：

1. 软件方法：单标志法，双标志先检查，双标志后检查，Peterson算法
2. 硬件方法：中断屏蔽法，TS/TSL指令、Swap/XCHG指令

这些方法都存在无法实现 “让权等待” 或者导致 死锁 等问题，让权等待指的是进程如果需要等待其他资源，应该立即释放CPU，让其他进程获得运行机会。

因此，信号量机制的提出提供了一种更加有效和可靠的方法来解决进程互斥问题。

信号量机制的基本概念

信号量的定义和类型

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机,就可以设置一个初值为1的信号量。

信号量有三种类型：

1. 二元信号量：这种信号量只有两种状态，通常用于实现互斥锁或二进制信号量。其取值范围为0和1，1表示资源未被分配，0表示资源已被分配。二元信号量主要用于实现资源的互斥访问。
2. 记录型信号量：这种信号量有一个整数值，用于表示可用的资源数。其取值范围为非负整数，其中整数值越大表示可用的资源越多。记录型信号量主要用于实现资源的共享访问。
3. 信号量集：这种信号量由多个信号量组成，每个信号量都有自己的整数值。信号量集主要用于实现复杂的同步操作，例如多任务单向同步、多任务双向同步等。

无论哪种类型的信号量，其主要作用都是用于控制进程或线程对共享资源的访问，以避免并发访问导致的数据不一致性和其他并发问题。

信号量的操作

信号量只能通过操作系统提供的一对 原语 操作，一般将这两种操作简称为 P、V。

在《深入理解计算机系统》一书中，旁注了 P 和 V 名字的起源。P 和 V 来源于荷兰语单词 Proberen（测试）和 Verhogen（增加），信号量的提出者正是荷兰学者。

原语是一种特殊的程序段，其执行 只能一气呵成，不可被中断 。原语是由关中断/开中断指令实现的。

PV操作：

• P(s): 如果s是非零的，那么P将s减1，并且立即返回。如果s为0，那么就 挂起 这个线程，直到S变为非0，而一个V操作会 唤醒 这个线程。在唤醒之后，P操作将S减1，并将控制返回给调用者。
• V(s): V操作将S加1。如果有任何线程阻塞在P操作等待S变成非0，那么V操作会 唤醒 这些线程中的一个，然后该线程将S减1，完成它的P操作。

信号量机制实现进程互斥

一个信号量对应一种资源

信号量 = 这种资源的剩余数量 （信号量的值如果小于0，说明此时有进程在等待这种资源）

P(s) : 申请一个资源s，如果资源不够就阻塞等待

V(s) ：释放一个资源s，如果有进程在等待该资源，则唤醒一个进程

假如两个进程要使用同一台打印机，在使用之前，通过P操作申请打印机资源，使用完成以后通过V操作释放资源，让另一个进程可以访问打印机。

信号量机制实现进程同步

除了提供互斥之外，信号量的另一个重要作用是调度对共享资源的访问。进程同步：要让各并发进程按要求有序的推进。

比如，P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行,那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

用信号量实现进程同步步骤：

1. 分析在什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作
2. 设置同步信号量 S，初始值为0，刚开始是没有这种资源的
3. 在“前操作”之后执行 V(S), 增加可用资源
4. 在“后操作”之前执行 P(S), 减少可用资源

技巧口诀：前 V 后 P

两个进程执行分别有两种顺序：

若先执行到 V(s) 操作，则 s++ 后s=1。之后当执行到 P(s) 操作时,由于s=1,表示有可用资源,会执行s--,S的值变回0,P2进程不会阻塞而是继续往下执行代码4。

若先执行到 P(S) 操作,由于s=0, s--后s=-1,表示此时没有可用资源,因此P操作中会主动请求阻塞。之后当执行完代码2，继而执行 v(s） 操作，s++，使 s 变回 0，由于此时有进程在该信号量对应的阻塞队列中,因此会在V操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行 代码4 了

信号量机制实现前驱关系

在6个进程中有6组代码 S1 - S6,这些代码存在多对前驱关系，要求按如下前驱图所示的顺序来执行：

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作），“前操作”执行完成后对“后操作”需要的资源+1，

“后操作”执行前检查资源，如果可用资源>0,则继续执行，否则挂起等待资源条件为真时被唤醒。

实现思路：

1. 要为每一对前驱关系各设置一个 同步信号量（图中的a,b,c...）
2. 在“前操作”之后对相应的同步信号量执行 V 操作
3. 在“后操作”之前对相应的同步信号量执行 P 操作

总结

参考资料：

[1] 王道计算机考研 操作系统

[2]《深入理解计算机系统》