Version: Next

信号量

软件实现互斥：双标志检查法不能保证 检查 与 上锁 两步操作合并为一个原子操作
先前所有的软硬件互斥算法都不能保证 让权等待

信号量机制：实现进程互斥、进程同步的方法
用户进程可以通过使用操作系统提供的 一对原语 来对 信号量 进行操作，从而很方便的实现进程互斥、进程同步
信号量 其实就是一个变量（可以是一个整数，也可以是更复杂的数据结构），可以用一个信号量来 表示系统中某种资源的 数量。
一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的 信号量 S 其实就是函数调用时传入的一个参数
Wait、Signal 原语常 简称 P、V 操作（来自荷兰语 proberen 和 verhogen）因此时长把 wait(S) 和 signal(S) 两个操作写为 P(S)、V(S)

整型信号量

用一个 整型变量 作为信号量，用来表示系统中某种资源的数量
普通的整型变量可以进行加减乘除等等操作
整型信号量只允许进行 3 种操作：初始化、P 操作、V 操作

系统中只有一台打印机，使用信号量来实现互斥
int S = 1; // 初始化整型信号量 S，表示当前系统中可用打印机数目

void wait (int S) { // wait 原语相当于进入区
while (S <= 0); // 如果资源不够，就一直循环等待
S = S - 1; // 如果资源数够，则占用一个资源
}

void signal (intS) { // signal 原语，相当于退出区
S = S + 1; // 使用完资源后，在退出区释放资源
}
使用
wait(S);
使用打印机;
signal(S);
其实和双标志先检查思想一样，只不过用原语保证了 检查 与 操作 之间不可中断
因此：依然不满足 让权等待，自旋等待消耗 CPU 算力

记录型信号量

整型信号量的缺陷是 忙等待，因此改用记录型数据结构表示信号量
// 记录型信号量定义
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
// 某进程需要使用资源时，通过 wait 原语申请
void wait (semaphore S) {
S.value--; // 资源数目 --
if (S.value < 0) { // 如果剩余资源不够
block (S.L); // block 原语
}
}
如果剩余资源不够，则使用 block 原语使进程从 运行态 进入 阻塞态，并把信号量挂到资源的等待队列（阻塞队列）中
// 进程使用完资源后，通过 signal 原语释放
void signal (semaphore S) {
s.value++;
if (S.value <= 0) { // 说明阻塞队列中有东西
wakeup(S.L);
}
}
释放资源后，若还有别的进程在等待这种资源，则使用 wakeup 原语唤醒等待队列中的一个进程，该进程会从 阻塞态 变为 就绪态

例：有 2 台打印机
线程1
wait(S); // 申请资源
使用打印机;
signal(S);
线程2
wait(S); // 申请资源
使用打印机;
signal(S);
线程3
wait(S); // 申请资源
使用打印机;
signal(S);
线程4
wait(S); // 申请资源
使用打印机;
signal(S);
线程1、线程2 被分配打印机资源
线程3 把自己阻塞，并把自己挂到打印机的等待队列中
线程4 把自己阻塞，并把自己挂到打印机的等待队列中，在线程3 的后面
线程1 执行到 signal(S)，value++，但 value <= 0 说明等待队列中有东西，执行 wakeup 原语唤醒等待队列队头的进程，线程3 从阻塞队列跑到就绪队列，资源被分配给线程3

信号量实现进程互斥

划定临界区
设置互斥信号量 mutex，初始值为 1
在临界区之前执行 P(mutex)
在临界区之后执行 V(mutex)
semaphore mutex = 1;

P1() {
P(mutex); // 上锁
临界区代码段;
V(mutex); // 解锁
}

P2() {
P(mutex); // 上锁
临界区代码段;
V(mutex); // 解锁
}

信号量实现进程同步

要让各并发进程按照要求有序的推进
线程1、线程2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的

确定需要同步执行的两个操作
设置同步信号量 S，初始值为 0
在 前操作 之后执行 V(S)
在 后操作 之前执行 P(S)

假设代码4 必须在代码4 之后执行
P1() {
代码1;
代码2;
V(S);
代码3;
}

P2() {
P(S);
代码4;
代码5;
代码6;
}
情况一
若先执行到 V(S) 操作，则 S++ 后 S = 1
当执行到 P(S) 操作时，由 S = 1，表示有可用资源，会执行 S--，S 的值变为0
P2 进程不会执行 block 原语，而是继续向下执行代码4
情况二
若先执行到 P(S) 操作，由于 s = 0, s-- 后 s = -1，表示此时没有可用资源，因此 P 操作中会执行 Block 原语，主动请求阻塞
之后当执行完代码2，继而继续执行 V(S) 操作， S++，是 S = 0。
此时由于有进程在该信号量的阻塞队列中，因此会在 V 操作中执行 wakeup 原语，唤醒 P2 进程
P2 进程执行代码4

信号量实现进程的前驱关系

为每一对前驱关系各设置一个同步变量
在 前操作 之后进行 V 操作
在 后操作 之前执行 P 操作

生产者消费者问题

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用

生产者、消费者共享一个初始为空，大小为 n 的缓冲区
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待（同步关系一）
只有缓冲区不空时，消费者才能从缓冲区拿走产品，否则必须等待（同步关系二）
缓冲区属于临界资源，各进程必须互斥访问（互斥关系一）

分析进程数目，进而分析进程间的同步、互斥关系
根据各进程的操作流程确定 P、V 操作的大致顺序
生产者每次消耗 (P) 一个空闲缓冲区，并生产 (V) 一个产品
消费者每次消耗 (P) 一个产品，并释放一个空闲缓冲区 (V)
往缓冲区放入/取走产品需要互斥
设置信号量：确定需要设置的信号量数目，并根据条件确定信号量初始值（互斥信号量初值一般为1，同步信号量的初始值需要根据对应资源的初始值决定）

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); //  生产一个空闲缓冲区 
        使用产品;
    }
}

提示

实现 互斥 是在同一进程中进行一对 PV 操作
实现 同步 是在其中一个进程中 P，另一个进程中 V

警告

实现互斥的 P 操作必须放在实现同步的 P 操作之后，否则会发生死锁

V 操作不会导致进程阻塞，因此两个 V 操作顺序可以交换

多生产者多消费者问题

问题——多 指多类别
桌子上有一个盘子，每次只能向其中放一个水果（大小为1 初始值为0 的缓冲区）
容量为 1 时可以省略互斥信号量
大于 1 则必须设置互斥信号量
爸爸专门向盘子里放苹果，妈妈专门向盘子里放句子（生产者1、生产者2）
儿子专门等着吃盘子中的橘子，女儿专等着吃盘子里的苹果（消费者1、消费者2）
只有当盘子为空时，爸爸妈妈才能向盘子中放一个水果
仅当盘子中有自己需要的水果时，儿子、女儿才可以从盘子中取出水果

分析 4 个进程的同步、互斥关系
盘子 互斥访问
同步关系：
父亲 - 女儿
母亲 - 儿子
盘子为空 - 爸爸妈妈放水果
设置信号量，确定信号量个数与信号量的初始值

semaphore mutex = 1; // 互斥访问盘子
semaphore apple = 0; // 盘子中有几个苹果
semaphore orange = 0; // 盘子中有几个橘子
semaphore plate = 1; // 盘子中可以放几个水果

dad() {
    while(1) {
        准备一个苹果;
        P(plate);
        P(mutex); // 互斥访问盘子
        把苹果放入盘子;
        V(mutex);
        V(apple);
    }
}

mom() {
    while(1) {
        准备一个橘子;
        P(plate)
        P(mutex); // 互斥访问盘子
        把橘子放入盘子;
        V(mutex);
        V(orange);
    }
}

daughter() {
    while(1) {
        P(apple)
        P(mutex); // 互斥访问盘子
        从盘子中取出苹果;
        V(mutex);
        V(plate)
        吃掉苹果;
    }
}

son() {
   while(1) {
       P(orange)
       P(mutex); // 互斥访问盘子
       从盘子中取出橘子;
       V(mutex);
       V(plate);
       吃掉橘子;
   } 
}

吸烟者问题

假设一个系统中有
3 个吸烟者
1 个供应者
每个抽烟者不停地卷烟并抽掉，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸、胶水
3 个抽烟这种，第一个拥有烟草、第二个拥有纸、第三个拥有胶水
供应者无限制的提供三种材料，供应者每次将两种材料放在桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供给者进程一个信号告诉它自己完成了，供应者就会放另外两种材料在桌子上，这个过程一致重复（让 3 个抽烟者轮流抽烟）

分析各进程之间的同步、互斥关系
桌子可抽象为容量为 1，初始为空的缓冲区（互斥访问）
为什么容量是 1 不是 2：不应把握两种物品，而是把握两种物品形成 一种组合
同步关系：
桌子上有组合一（纸+胶水） → 第一个抽烟者取走
桌子上有组合二（烟草+胶水） → 第二个抽烟者取走
桌子上有组合三（烟草+纸） → 第三个抽烟者取走
发出完成信号 → 供应者将下一个组合放在桌上

semaphore offer1 = 0; // 桌子上组合1的数目
semaphore offer2 = 0; // 桌子上组合2的数目
semaphore offer3 = 0; // 桌子上组合3的数目
semaphore empty = 1; // 桌子是否是空的
int i = 0; //用于实现3个抽烟者轮流抽烟

provider() {
    while(1) {
        P(empty); // 桌子变为不空
        if (i == 0) {
            将组合1放在桌上;
            V(offer1);
        } else if (i == 1) {
            将组合2放在桌上;
        } else if (i == 2) {
            将组合3放在桌上;
        }
             
        i = (i + 1) % 3;
    }
}

smoker1() {
    while(1) {
        P(offer1)
        从桌子上拿走组合一;
        卷烟;
        抽掉;
        V(empty); // 生产一个空位：桌子变为空的
    }
}

smoker2() {
    while(1) {
        P(offer2);
        从桌子上拿走组合二;
        卷烟;
        抽掉;
        V(empty);
    }
}

smoker3() {
    while(1) {
        P(offer3);
        从桌子上拿走组合三;
        卷烟;
        抽掉;
        V(empty);
    }
}

总结

吸烟者问题为解决 可以生产多个产品的单生产者 问题提供了一个思路

体会如何使用 int i 实现轮流
前驱事件 -> V -> P -> 事件

读者-写者问题

有读者-写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致错误
因此要求：
允许多个读者可以同时对文件执行读操作
只允许一个写者往文件中写信息
任何写者在完成操作之前不允许其他读者或写者工作
写者执行写操作前，应让已有的读者和写者全部退出

确定各进程之间的同步、互斥关系
两类进程：写进程、读进程
互斥关系：写进程-写进程；写进程-读进程；
读进程与读进程并不互斥
根据各进程操作流程确定 P、V 操作的大致顺序
确定信号量数目与初始值（互斥信号两一般初始化为 1，同步信号量的值取决于可用系统资源）
写进程和任何进程都互斥，设置一个互斥信号量 rw，在写者访问共享文件前后分别执行 P、V 操作
读者进程和写者进程也互斥，因此读者访问文件前后也要对 rw 执行 P、V 操作
如果所有读者进程在访问共享文件前都执行 P(rw) 操作，会导致 读进程与读进程也发生互斥
读者写者问题的核心——如何解决读读互斥

如何解决读读互斥
设置一个 int count 记录当前有几个读进程在访问文件
如果有多个读进程，那么后续读进程跳过 P(rw) 操作直接进行读取文件操作
semaphore rw = 1; // 用于实现对文件的互斥访问，表示是否有进程在访问共享文件 (写锁)
int count = 0; // 记录当前有几个读进程在访问文件

writer() {
while(1) {
P(rw); //加锁
写文件;
V(rw); //解锁
}
}

reader() {
while(1) {
if (count == 0) // 如果没有其他读进程
P(rw); // 那么加锁，与写进程互斥
count++; // 读进程数目++

读文件;

count--; // 读进程数目--
if (count == 0) // 如果自己是唯一的读进程
V(rw); // 那么负责解锁，让写进程可以写入文件
}
}
如果两个读进程并发执行，则两个读进程可能先后执行 P(rw)，从而第二个读进程会被阻塞
出现该问题的原因是 count 变量的检查和复制无法一气呵成，不是原子操作，因此可以另外设置一个 互斥信号量 来保证各读取进程对 count 的访问时互斥的
semaphore rw = 1; // 用于实现对文件的互斥访问，表示是否有进程在访问共享文件 (写锁)
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 读锁，用来互斥访问 count

writer() {
while(1) {
P(rw); //加锁
写文件;
V(rw); //解锁
}
}

reader() {
while(1) {
P(mutex); // 上读锁
if (count == 0) // 如果没有其他读进程
P(rw); // 那么加锁，与写进程互斥
count++; // 读进程数目++
V(mutex); // 解读锁
读文件;
P(mutex); // 上读锁
count--; // 读进程数目--
if (count == 0) // 如果自己是唯一的读进程
V(rw); // 那么负责解锁，让写进程可以写入文件
V(mutex); // 解读锁
}
}
这种写法实际上是 读优先 ，可能会出现大量读进程下，被阻塞的写进程一致不被唤醒的情况

写优先——相对公平先来先服务原则——读写公平法
再设置一个信号量，用于实现写优先
semaphore rw = 1; // 用于实现对文件的互斥访问，表示是否有进程在访问共享文件 (写锁)
int count = 0; // 记录当前有几个读进程在访问文件
semaphore mutex = 1; // 读锁，用来互斥访问 count
semaphore w = 1; // 用于实现 "写优先"

writer() {
while(1) {
P(w);
P(rw); //加锁
写文件;
V(rw); //解锁
V(w);
}
}

reader() {
while(1) {
P(w);
P(mutex); // 上读锁
if (count == 0) // 如果没有其他读进程
P(rw); // 那么加锁，与写进程互斥
count++; // 读进程数目++
V(mutex); // 解读锁
V(w);
读文件;
P(mutex); // 上读锁
count--; // 读进程数目--
if (count == 0) // 如果自己是唯一的读进程
V(rw); // 那么负责解锁，让写进程可以写入文件
V(mutex); // 解读锁
}
}

哲学家进餐问题

问题描述
一张圆桌上作者 5 位哲学家
每两个哲学家之间的桌上摆着一根筷子
筷子的中间是一碗米饭
哲学家倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人
只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）
如果筷子已在他人手上，则需等待
饥饿的哲学家只有同时拿起两根筷子才能进餐
进餐完毕后，放下筷子继续思考

每个哲学家与自己相邻的两个哲学家对中间的筷子的访问是 互斥 的
此问题中只有互斥问题
但每个哲学家进程需要同时持有两个临界资源才能吃饭
如何避免临界资源分配不当，造成 死锁，是此问题的核心

信号量设置
定义互斥信号量数组 choostick[5] = {1, 1, 1, 1, 1} 用于实现对 5 个筷子的互斥访问
对哲学家按 0, 1, 2, 3, 4 编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 (i + 1) % 5

直观想法：依次拿起左、右两支筷子
semaphore chopstick[5] = {1, 1, 1, 1, 1};

Pi() { // 哲学家 i 的进程
while(1) {
P(chopstick[i]); // 拿左
P(chopstick[(i + 1) % 5]); // 拿右
吃饭;
V(chopstick[i]); // 放左
V(chopstick[(i + 1) % 5]); // 放右
思考;
}
}
问题：所有人都拿起了左边的筷子，等待自己右边的筷子被释放，于是就 死锁 了
在此场景下，如何防止 死锁 ？
方案一：可以对哲学家进程进行一些限制，比如最多允许 4 个哲学家同时进餐，那么就能保证至少有一个哲学家可以拿到一双筷子
方案二：要求奇数哲学家先拿左筷子，然后再拿右筷子，而偶数哲学家相反。这种方法可以保证相邻的两个奇偶号哲学家都想吃饭，那么只要有一人拿起了第一只筷子，另一个就会直接阻塞
方案三：仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子（不准确说法）；准确说法：各哲学家拿筷子这件事必须互斥进行。保证即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家继续尝试拿筷子。当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1; // 互斥的拿筷子

Pi() { // 哲学家 i 的进程
while(1) {
P(mutex);
P(chopstick[i]); // 拿左
P(chopstick[(i + 1) % 5]); // 拿右
V(mutex);
吃饭;
V(chopstick[i]); // 放左
V(chopstick[(i + 1) % 5]); // 放右
思考;
}
}

信号量#

整型信号量#

记录型信号量#

信号量实现进程互斥#

信号量实现进程同步#

信号量实现进程的前驱关系#

生产者消费者问题#

问题描述

提示

警告

多生产者多消费者问题#

吸烟者问题#

总结

读者-写者问题#

哲学家进餐问题#

信号量

整型信号量

记录型信号量

信号量实现进程互斥

信号量实现进程同步

信号量实现进程的前驱关系

生产者消费者问题

多生产者多消费者问题

吸烟者问题

读者-写者问题

哲学家进餐问题