【操作系统】信号量机制与生产者消费者问题
写在前面
- 关于文章
操作系统中最核心的概念是
进程,这是对正在运行程序的一个抽象。也可以说进程是程序的一次执行过程。操作系统的其他所有内容都是围绕着进程的概念展开的,所以,透彻地理解进程是非常重要的。即使可以利用的CPU只有一个,但是通过进程,可以使系统具有支持并发操作的能力,可将一个单独的CPU变换成多个虚拟的CPU。在这里主要学习信号量机制以及生产者-消费者问题等。
- 我的站点
- 联系我
🐧：
2410685763WeChat：
Super_Baby_00公众号：
编程那点事儿
信号量机制
1965年荷兰Dijkstra提出的信号量（Semaphores）是一种卓有成效的进程同步工具，在长期的应用中，得到了很大的发展，从整型信号量经过记录型信号量，进而发展为“信号量集”机制。
- 信号量就是OS提供的管理公有资源的有效手段。
- 信号量代表可用资源实体的数量。
相关概念
信号量 : 表示系统中某种资源的数量, 当它的值大于0时, 表示当前可用资源的数量; 当它的值小于0时, 其绝对值表示等待使用该资源的进程个数
P, V操作 : PV操作由P操作原语和V操作原语(不可中断)组成，针对信号量进行相应的操作. P操作相当于请求资源, V操作相当于释放资源
下面我们来讨论一下各种信号量机制的内容。
整型信号量
定义：把整型信号量定义为一个用于表示资源数目的整型量S，除初始化外，仅能通过两个原子操作wait(S),signal(S)来访问，也就是P(S)，V(S)操作。
- P操作 wait(S):
while S < 0 do no-op S: S +1 - V操作 signal(S):
S:=S+1;
注意：P、V操作是原子操作，不可中断。
本质就是一个数, 表示资源数量
C语言实现对应P、V操作：
int S = 1; // 整型信号量, 初始值为1, 表示系统中有一个资源
void P(int S){ // P操作
while(S <= 0); // 资源数不够则循环等待
S = S - 1; // 分配资源, 资源数-1
}
void V(int S){ // V操作
S = S + 1;
}
整型信号量的问题 : 存在"忙等", 即上述P操作时, 如果资源不够, 将一直执行while循环语句, 该进程会一直占用CPU, 为解决这个问题, 引入了记录型信号量。
记录型信号量
在整形信号量机制中的wait操作，只要是信号量S≤0，就会不断测试。该机制并未遵守“让权等待”的准则，而是使进程处于“忙等”的状态。
在记录型信号量是一种不存在“忙等”现象的进程同步机制。但是采取了“让权等待”的策略后又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中出了一个需要用于表示资源数目的整形变量value外，还应增加一个进程链表指针L，用于链接上述所有等待进程。
记录型数据结构：
typedef struct{
int value; // 剩余资源数
struct process *L; // 等待队列
}semaphore;
Wait 操作：
- 申请资源，减量操作，S.value:=S.value-1
- 当S.value<0时，表示资源分配完，进行自我阻塞。
wait(S) begin S.value:=S.value-1； if S.value<0 then block(S,L) end
Signal操作：
- 释放资源，增量操作，S.value:=S.value+1
- 当S.value≤0，唤醒S.L链表中的等待进程
signal(S) begin S.value:=S.value+1; if S.value<=0 then wakeup(S,L) end
value>0，代表可用资源的数量
value<0，代表由于申请资源而阻塞的进程数量
记录型信号量机制：
每次只能获得或释放一个单位的资源，低效
每次分配前必须测试资源数量，看其是否大于其下界值
C语言实现对应P、V操作：
void P(semaphore S){
S.value--;
if(S.value < 0){
block(S.L); // 使进程从运行态 -> 阻塞态
} // 如果剩余资源不够, 利用block原语使进程将进程挂起到S的等待队列(阻塞队列)中, 避免"忙等"
}
void V(semaphore S){
S.value++;
if(S.value<=0){
wakeup(S.L); // 使进程从阻塞态 -> 就绪态
} // 释放资源后, 等待队列还有进程, 那么利用wakeup原语唤醒该进程
}
AND型信号量
前面讨论的进程互斥问题都是共享一个临界资源而言的，但是在很多情况下一个进程需要获得两个或多个共享资源后才能执行其任务。如果此类问题利用上述办法将会陷入死锁状态。
AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源一次性全部分配给进程，待进程用完后再一起释放。只要尚有一个资源未分配给进程，其他所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。由死锁理论可知，可避免死锁的发生。
两个进程A和B，共享数据D和E，为其分别设置互斥信号量Dmutex和Emutex，初值均为1。
Process A：
wait(Dmutex);
wait(Emutex);
使用D、E
Signal(Dmutex)
Signal(Emutex)
Process B：
wait(Emutex);
wait(Dmutex);
使用D、E
Signal(Dmutex)
Signal(Emutex)
Process A： wait(Dmutex); 于是Dmutex=0
Process B： wait(Emutex); 于是Emutex=0
Process A： wait(Emutex); 于是Emutex=-1 A阻塞
Process B： wait(Dmutex); 于是Dmutex=-1 B阻塞
可见：共享的资源越多，死锁的可能越大
信号量集
在记录性信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时便需要进行N次操作，显然这是低效的。此外在一些情况下，当资源数量低于某一下限值时，便不予以分配。因而在每次分配之前，都必须测试该资源的数目，看其是否大于其下限值。基于以上两点，对AND型信号量加以扩充，行成一般化的“信号量集”机制。
Swait操作描述如下：
S：信号量 d：需求值 t：下限值
Swait(S1, t1, d1, …, Sn, tn, dn)
if Si >= t1 and … and Sn>= tn then
for i:=1 to n do
Si:= Si - di ;
endfor
else
Place the executing process in the waiting queue of the first Si with Si < ti and set its program counter to the beginning of the Swait Operation
endif
一般信号量集的几种特殊情况：
- Swait(信号量，下限值，需求值)
- Swait(S, d, d)，只有一个信号量S，允许每次申请d个资源，若现有资源数少于d，不予分配。
- Swait(S, 1, 1)，蜕化为一般的记录型信号量(S>1时)或互斥信号量(S=1时)。
- Swait(S, 1, 0)，当S>=1时，允许多个进程进入某特定区，当S变为0后，阻止任何进程进入特定区，相当于可控开关。
Swait(S,1,0) 这一种比较难理解，其中S表示只有S个信号量，1为下限值，如果S>=1,则允许进程进入某特定区域，需求值为0，每次S = S -0，然而当S<1时，阻止任何进程进入特定区域。
经常使用的是后两种信号量集。
利用信号量实现同步与互斥
同步
同步 : 保证"一前一后"执行两个操作
利用信号量实现同步 :
semaphore S = 0; // 初始化信号量 = 0
P1(){ // P1进程
xx1; // 操作1
xx2; // 操作2
V(S); // 信号量++
}
P2(){
P(S);
xx3; // 操作3
xx4; // 操作4
}
总结就是 : 在"前"操作之后执行V操作, 在"后"操作之前执行P操作
互斥
互斥 : 实现对临界资源(一次只能供一个进程访问的资源)的访问
利用信号量实现互斥:
semaphore mutex = 1; // 互斥信号量mutex, 初始化为1
P1(){
P(mutex);
访问临界区;
V(mutex);
}
P2(){
P(mutex);
访问临界区;
V(mutex);
}
生产者-消费者问题
问题本质 : 实现对一个大小为n的缓冲区的互斥访问, 存取操作
问题描述:
生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。
关键点 :
- 生产者消费者共享一个大小为n, 初始为空的缓冲区----缓冲区即临界资源
- 缓冲区未满时生产者才可以将产品放入----设置empty信号量
- 缓冲区不为空时消费者才可以将产品取出----设置full信号量
实现 :
信号量设置 :
semaphore mutex = 1; // 互斥信号量, 实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量, 表示空闲缓冲区数(可放产品数)
semaphore full = 0; // 同步信号量, 表示非空缓冲区数(放入产品数)
生产者消费者操作:
producer(){ // 生产者
while(1){
P(empty);
P(mutex);
产品放入缓冲区;
V(mutex);
V(full);
}
}
consumer(){ // 消费者
while(1){
P(full);
P(mutex);
取出产品;
V(mutex);
V(empty);
}
}
tips :
- P(mutex)互斥操作必须在同步操作之后, 否则会引发"死锁":
// 如果改变 P(mutex)和P(empty)顺序, 假设此时empty=0,即缓冲区已满
producer(){ // 生产者
while(1){
P(mutex);
P(empty);
产品放入缓冲区;
V(full);
V(mutex);
}
}
比如我生产者先P(mutex)申请到了临界资源访问权限, 但是之后P(empty)时被阻塞, 此时消费者一方又由于mutex被生产者占有而无法取出产品, 导致互相等待对方释放资源, 即死锁
2.在此处, 如果缓冲区大小为1, 可以不设置mutex信号量(互斥可以由empty和full满足)
微信关注
