极客笔记操作系统 生产者-消费者问题
生产者-消费者问题是一个经典的多进程同步问题，即我们试图在多个进程之间实现同步。
生产者-消费者问题中有一个生产者，生产者正在生产一些物品，而消费者正在消费生产者生产的物品。生产者和消费者共享同一个固定大小的内存缓冲区。
生产者的任务是生产物品，将其放入内存缓冲区，然后继续生产物品。而消费者的任务是从内存缓冲区中消耗物品。
让我们了解一下问题是什么
以下是生产者-消费者问题中出现的问题：
- 只有当缓冲区不满时，生产者才能生产数据。如果发现缓冲区满了，生产者不被允许将任何数据存储到内存缓冲区中。
- 只有当缓冲区不为空时，消费者才能消费数据。如果发现缓冲区为空，消费者不被允许使用内存缓冲区中的任何数据。
- 不允许生产者和消费者同时访问内存缓冲区。
让我们看一下上述问题的代码：
生产者代码
消费者代码
让我们了解上述生产者和消费者的代码
在解释代码之前，首先要了解上述代码中使用的一些术语：
- ” in “在生产者代码中表示下一个 空缓冲区
- ” out “在消费者代码中表示第一个 填充缓冲区
- count保存缓冲区中的元素数量
- count进一步分为在生产者和消费者代码中的块表示的3行代码
如果我们首先谈论生产者代码：
--Rp是一个寄存器，它保存m[count]的值
--Rp被递增（因为已经向缓冲区中添加了元素）
--递增后的Rp值被重新存储到m[count]
类似地，如果我们接下来谈论消费者代码：
--Rc是一个寄存器，它保存m[count]的值
--Rc被递减（因为已经从缓冲区中移除了元素）
--递减后的Rc值被重新存储到m[count]。
缓冲区
从图中可以看出：缓冲区总共有8个空间，其中前5个已被填充，in = 5（指向下一个空位置），out = 0（指向第一个填充位置）。
让我们从 生产者 开始，他想要生产一个元素 “F”，根据代码他将进入producer()函数，while(1)将始终为真，itemP = F将尝试插入缓冲区，而在此之前while(count n)将被评估为假。
注意：while循环后面的分号会阻止代码继续执行，如果评估结果为真（即无限循环/缓冲区已满）。
Buffer[in] = itemP → Buffer[5] = F（F已插入）。
in = (in + 1) mod n → (5 + 1) mod 8 → 6，因此in = 6（下一个空缓冲区）。
插入F后，缓冲区如下所示。
其中out = 0，但in = 6。
由于 count = count + 1; 可分为三个部分：
Load Rp, m[count] → 将值为 5 的 count 复制到寄存器 Rp。
Increment Rp → 将 Rp 增加至 6。
假设在 Increment 执行后并在第三行（store m[count], Rp）执行之前，发生 上下文切换 ，代码跳转至 消费者代码…
消费者代码：
现在开始 消费者 想要消费第一个元素”A”，根据代码它将进入 consumer() 函数，while(1) 永远为 true，而 while(count 0) 评估结果为 False（因为 count 仍为 5，不等于 0）。
注：while 循环后的分号将阻止代码继续向前执行，如果结果为 True（即无限循环/缓冲区中没有元素）
itemC = Buffer[out]→ itemC = A（因为 out 为 0）
out = (out + 1) mod n → (0 + 1)mod 8→ 1，因此 out = 1（第一个填充位置）
A 现在被移除
移除 A 后，缓冲区如下所示
其中 out = 1 ，且 in = 6
因为 count = count – 1; 被分为三部分：
加载 Rc, m[count] → 将 count 的值 5 复制到寄存器 Rp。
减少 Rc → 将 Rc 减少为 4。
存储 m[count], Rc → count = 4。
现在 count 的当前值是 4
假设在此之后 发生了上下文切换 ，回到生产者代码的剩余部分。…
由于生产者代码的上下文切换发生在增加操作之后，第三行（存储 m[count], Rp）执行之前
所以我们从这里继续，因为 Rp 保存的是增加后的值 6
因此存储 m[count], Rp → count = 6
现在 count 的当前值为 6，但是 Buffer 只有 5 个元素，这种情况称为竞态条件，问题是生产者-消费者问题。
使用信号量解决生产者-消费者问题的解决方案
由于上下文切换和产生不一致结果导致的生产者和消费者问题，可以通过信号量来解决。
为了解决上述竞态条件引起的问题，我们将使用 **二进制信号量和计数信号量
二进制信号量： 在二进制信号量中，只有两个进程可以在任何时候争夺进入其 临界区 ，除此之外，也满足互斥条件。
计数信号量： 在计数信号量中，多于两个进程可以在任何时候争夺进入其 临界区 ，除此之外，也满足互斥条件。
信号量： 信号量是一个在初始化之外只能通过等待和信号的两种标准原子操作访问的整数变量，它们的定义如下：
1. wait( S )
{
while( S <= 0) ;
S--;
}
2. signal( S )
{
S++;
}
从上面对wait的定义来看，很明显，如果S的值小于等于0，则会进入一个无限循环（因为在while循环之后有一个分号）。而信号的作用是增加S的值。
让我们来看一下使用信号量（二进制和计数信号量）解决生产者和消费者问题的代码：
生产者代码-解决方案
void producer( void )
{
wait ( empty );
wait(S);
Produce_item(item P)
buffer[ in ] = item P;
in = (in + 1)mod n
signal(S);
signal(full);
}
消费者代码 – 解决方案
void consumer(void)
{
wait ( empty );
wait(S);
itemC = buffer[ out ];
out = ( out + 1 ) mod n;
signal(S);
signal(empty);
}
让我们了解上面生产者和消费者代码的解决方案：
在解释代码之前，先了解一下上面代码中使用的一些术语：
- ” in “在生产者代码中表示下一个 空缓冲区
- ” out “在消费者代码中表示第一个 已填充缓冲区
- ” empty “是一个计数信号量，用于记录空缓冲区的数量
- ” full “是一个计数信号量，记录已填充缓冲区的数量
- ” S “是一个二进制信号量： BUFFER
如果我们看一下缓冲区的当前情况
S = 1（二进制信号量的初始值）
in = 5（下一个空缓冲区）
out = 0（第一个已填充的缓冲区）
从图中可以看出：缓冲区总共有8个空间，其中前5个已经填满，in = 5（指向下一个空位置），out = 0（指向第一个填满的位置）。
生产者代码中使用的信号量：
6. wait(empty) 会将计数信号量变量 empty 的值减1，即当生产者生成一个元素时，缓冲区的空闲空间值会自动减1。如果缓冲区已满，即计数信号量变量”empty”的值为0，则wait(empty);会阻塞进程（根据wait的定义）并且不允许继续执行。
7. wait(S) 将二进制信号量变量S的值减为0，以阻止其他希望进入其临界区的进程进入。
8. signal(s) 将二进制信号量变量S的值增加为1，以允许其他希望进入其临界区的进程进入。
9. signal(full) 将计数信号量变量full的值增加1，因为在向缓冲区添加项时，缓冲区将占据一个空间，必须更新变量full。
生产者代码中使用的信号量：
10. wait(full) 会将计数信号量变量full的值减1，即当消费者消费一个元素时，缓冲区的占用空间值会自动减1。如果缓冲区为空，即计数信号量变量full的值为0，则wait(full);会阻塞进程（根据wait的定义）并且不允许继续执行。
11. wait(S) 将二进制信号量变量S的值减为0，以阻止其他希望进入其临界区的进程进入。
12. signal(S) 将二进制信号量变量S的值增加为1，以允许其他希望进入其临界区的进程进入。
13. signal(empty) 将计数信号量变量empty的值增加1，因为在从缓冲区移除一个项时，缓冲区将有一个空位，必须相应地更新变量empty。
生产者代码：
让我们从想要生成一个元素“F”的producer()开始，根据代码它将进入producer()函数。
wait(empty);会将empty的值减1，即empty = 2
假设在此切换上下文并跳转到consumer代码。
消费者代码：
现在开始消费者，希望消耗第一个元素“A”，根据代码它将进入consumer()函数，
wait(full);会将full的值减1，即full = 4
wait(S);会将S的值减为0
itemC = Buffer[out]; → itemC = A（因为out为0）
A现在被移除了。
out = (out + 1) mod n → (0 + 1)mod 8 → 1，因此 out = 1（第一个填充位置）
S = 0（二进制信号量的值）
in = 5（下一个空缓冲区）
out = 1（第一个已填充的缓冲区）
假设在此上下文之后，切换回生产者代码
由于producer()的下一条指令是wait(S);，这将陷入生产者进程，因为S的当前值为0，wait(0);是一个无限循环：根据wait的定义，因此生产者无法继续前进。
因此，我们转到下一个消费者进程指令。
signal(S);现在将S的值增加到1。
signal(empty);会将empty增加1，即empty = 3
现在回到producer()代码；
由于producer()的下一条指令是wait(S);将成功执行，因为S现在为1，并且它将S的值减1，即S = 0
Buffer[in] = itemP; → Buffer[5] = F.（现在插入了F）
in = (in + 1) mod n → (5 + 1)mod 8 → 6，因此in = 6（下一个空缓冲区）
signal(S);将S增加1，
signal(full);将full增加1，即full = 5
现在添加full和empty的当前值，即full + empty = 5 + 3 = 8（完全正常）。即使有那么多上下文切换，也不会生成不一致的结果。但是在没有信号量的生产者和消费者的先前条件下，我们在上下文切换的情况下看到了不一致的结果。
这是解决生产者消费者问题的解决方案。