这次的比喻场景要升级了,因为它既能解决互斥问题,也能解决同步问题。我们用一个更综合的场景:一个拥有多辆共享单车的站点。
- 共享单车 (资源):站点里有多辆共享单车,数量是有限的。
- 你 (进程):想借一辆车去办事。
- 站点管理员 (操作系统):他提供了一套标准化的借车、还车流程(P、V操作)。
1. 为什么需要新工具?—— 回顾历史遗留问题
在发明信号量之前,我们遇到的最大问题是 “忙等待”。无论是 Peterson 算法还是 TSL 指令,当一个进程拿不到锁(借不到车)时,它只会在原地打转,不停地问“有车了吗?有车了吗?”,白白浪费自己的精力(CPU资源)。这不高效!
我们需要一个更聪明的机制,让进程在借不到车时,可以去旁边的休息室睡觉,等有车了再被叫醒。
2. 信号量机制的核心思想
- 信号量 (Semaphore):你可以把它理解成站点门口的一个记分牌,上面写着当前可用单车的数量。比如,牌子上写着
5
,就表示还有5辆车可用。 - 原语 (Primitive):管理员提供了一对不可分割的、标准化的操作流程,叫做原语。这意味着,当管理员在执行这个流程时,谁也不能打扰他,必须让他一气呵成地做完。这两个流程就是大名鼎鼎的 P操作 和 V操作。
3. 整型信号量 - “简陋的记分牌”
这是信号量的第一版设计,比较简单,但也暴露了问题。
数据结构:就是一个简单的整数
S
(比如,int S = 5;
)。P操作 (荷兰语 Proberen, 尝试):相当于“借车”流程。
- 你想借车,就去执行P操作。
- 管理员看一眼记分牌
S
。 - 只要
S > 0
(还有车),他就让S--
(车数减一),然后让你通过。 - 如果
S <= 0
(没车了),他就把你拦在门口,让你在门口一直等(while(S<=0);
),直到有人还车。
V操作 (荷兰语 Verhogen, 增加):相当于“还车”流程。
- 你用完车,回来执行V操作。
- 管理员直接让
S++
(车数加一)。
存在的问题:
- 这个设计最大的问题是,当没车时,你还是得在门口“忙等待”,死死盯着记分牌,没有解决根本问题。它不满足“让权等待”原则。
4. 记录型信号量 - “带排队系统的智能记分牌”
这是整型信号量的完美升级版,也是我们现在操作系统中真正使用的信号量。它解决了“忙等待”问题。
数据结构:它不再是一个简单的整数,而是一个“智能记分牌”,包含两个部分:
- 一个整数
value
:表示当前可用资源的数量。 - 一个等待队列
L
:这是一个“排队列表”,用来记录所有正在等待借车的进程。
- 一个整数
P操作 (智能的“借车”流程):
- 你想借车,执行P操作。
- 管理员先让
value--
。这一步很有意思,可以理解为“先预定一辆车”。 - 然后他检查
value
的值:- 如果
value >= 0
:这说明在你预定之前,车是富余的。你预定成功,直接骑车走人。 - 如果
value < 0
:这说明在你预定之前,车就已经没了(甚至已经有人在排队等了)。你的这次“预定”让欠账变得更多了。于是,管理员会把你这个进程**“挂起”(阻塞),然后把你的名字登记到那个等待队列L
** 上,让你去休息室睡觉。
- 如果
V操作 (智能的“还车”流程):
- 你用完车,回来执行V操作。
- 管理员先让
value++
。这可以理解为“还了一辆车回来,可用资源增加了”。 - 然后他检查
value
的值:- 如果
value > 0
:这说明即使加上你还的这辆车,也没有人在排队等车。一切正常。 - 如果
value <= 0
:这说明在你还车之前,是有人在排队等车的(value
是负数或零)。现在你还了一辆车,正好可以满足一个在排队的人。于是,管理员会从等待队列L
里唤醒一个进程,让他从休息室出来,把这辆车骑走。
- 如果
精髓所在:
- 记录型信号量通过引入“等待队列”和“阻塞/唤醒”机制,完美地实现了**“让权等待”**。进程在获取不到资源时,会主动让出CPU去“睡觉”,而不是空转,极大地提高了系统效率。
value
的绝对值在value < 0
时,也巧妙地表示了正在等待队列中排队的进程数量。
一句话总结:记录型信号量 = 资源计数器 + 等待队列,是实现进程同步与互斥的终极武器之一。
必会题与详解
题目一:什么是“原语”?为什么P、V操作必须是原语?如果不是原语会发生什么?
答案详解:
原语的定义:原语(Primitive)是由若干条指令组成的,用于完成特定功能的一个过程。它最大的特点是执行的原子性,即它的执行过程是不可中断的,必须一气呵成。这通常是通过硬件支持(如关中断/开中断、TSL指令等)来实现的。
必须是原语的原因:P、V操作都涉及到对信号量
S
的检查和修改。如果这个过程可以被中断,就会出现严重问题。- 以P操作为例:
P(S)
的伪代码是S--
。如果两个进程同时执行P(S)
,正确的逻辑是S被减2。但如果S--
不是原语,它在机器层面可能分为三步:1. 读S到寄存器;2. 寄存器减1;3. 写回S。 - 可能发生的错误:
- 进程A执行第1步,读取S=1到自己的寄存器。
- 此时发生中断,切换到进程B。
- 进程B也执行第1步,读取S=1到自己的寄存器。然后执行完2、3步,将S写回为0。
- 切换回进程A,它从第2步继续执行,将自己的寄存器(值仍为1)减1得0,再写回S。
- 结果:两个进程都执行了P操作,但S最终只被减了1,而不是2。这会导致一个资源被两个进程同时获取,破坏了互斥性。
- 以P操作为例:
结论:因此,P、V操作必须是原语,以确保对信号量变量访问的原子性,从而保证进程互斥与同步的正确实现。
题目二:记录型信号量是如何实现“让权等待”的?请与整型信号量进行对比说明。
答案详解:
“让权等待”指的是进程在无法获取所需资源时,应主动释放CPU,进入阻塞状态。
记录型信号量的实现方式:
- 它通过一个等待队列(阻塞队列)和阻塞/唤醒原语来实现让权等待。
- 当一个进程执行P操作,发现资源不足(
value
变为负数)时,操作系统会调用**block
原语**,将该进程的状态从“运行态”变为“阻塞态”,并将其PCB(进程控制块)放入信号量的等待队列中。这个过程进程主动放弃了CPU。 - 当其他进程执行V操作释放资源,并发现等待队列中有人时,操作系统会调用**
wakeup
原语**,从等待队列中取出一个进程,将其状态从“阻塞态”变为“就绪态”,放入就绪队列,等待被调度。 - 通过这种“睡下-被叫醒”的模式,CPU在进程等待期间可以去服务其他进程,实现了“让权等待”。
与整型信号量的对比:
- 整型信号量在资源不足时(
S<=0
),其P操作会进入一个while(S<=0);
的循环。进程会一直处于“运行态”,持续占用CPU来反复检查S的值,这就是“忙等待”。它没有让出CPU,因此不满足“让权等待”原则,效率低下。
- 整型信号量在资源不足时(
题目三:在一个使用记录型信号量的系统中,若某个信号量S的当前值为-3,这代表什么物理含义?
答案详解:
在记录型信号量机制中,S.value
的值具有双重含义:
- 当
S.value >= 0
时,它表示当前系统中剩余可用资源的数量。 - 当
S.value < 0
时,它表示当前没有可用资源,并且其绝对值代表正在该信号量的等待队列中排队等待的进程数量。
因此,如果信号量S的当前值为-3,其物理含义是:
- 该类资源已经全部被分配完毕,没有剩余可用资源。
- 有 3个 进程因为请求该资源而被阻塞,并正在该信号量的等待队列中排队等待。