信号量

在临界区管理中，如果使用硬件方法，则存在问题：

1965 年 Dijkstra 提出了新的同步工具——「信号量」（Semaphore）是一种软件资源，除了初始化外，仅能由两个同步原语对其进行操作的整型变量。

一个进程在某一特殊点上被迫停止执行，直到接收到一个对应的特殊变量值，这种特殊变量就是信号量，复杂的进程合作需求都可以通过适当的信号结构得到满足。

操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。

img-2024-05-18 09-39-06.png

物理意义

信号量 S 的初值表示可用资源数

设可用资源数为 m，进程数为 n，则信号量的取值范围为

若多个进程共享临界资源，并且对资源的访问是互斥的，资源可用单位数为 1，则进程关于此资源互斥。例如下图

img-2024-05-18 09-46-34.png

进程 P1, P2, ... , Pn 关于资源 X 互斥。进程 P1, P2, ... , Pn 可并行执行，他们的运行时序是随机的、异步的。但对于 X 的操作只能互斥、排他的进行.

根据信号量的定义，可以设置：

此时 s 的绝对值表示由于申请临界资源 X 而处于进程等待状态的进程数。

由此，就可以使用代码实现互斥。任意一个进程 Pi 就可以表示为

Pi(){
	...
	P(s);
	X=X+1;
	V(s)
	...
}

由此可以归纳出信号量实现互斥的要点

为临界资源设置一个互斥信号量 mutex，其初值为 N（系统提供的同类资源最大数目）；在每个进程中将临界区代码置于 P(mutex) 和 V(mutex) 原语之间。
必须成对使用 P 和 V 原语：遗漏 P 原语则不能保证互斥访问，遗漏 V 原语则不能在使用临界资源之后将其释放（给其他等待的进程）；
P、V 原语不能次序错误、重复或遗漏。

若进程 A、B 可并行执行，B 的执行必须等待 A 都输出 X 完成后才能开始执行，则两个进程构成进程同步关系。为了实现同步，可以设置信号量 s，其中

则 A 和 B 的代码分别表示为

A()
{
	...
	计算 X
	V(s)
}

进程 B

B()
{
	...
	P(s),
	打印 X
	...
}

主程序可以表示为

main()
{
	int s=0;
	cobegin
		A;
		B;
	coend;
}

虽然时序上，先启动 B 再启动 A，但是即使 A 后启动，但是通过 PV 操作的调整，仍然保证了进程 A 先计算出 X，再由 B 打印出来。由此实现了逻辑上的先后顺序保证。