王道操作系统笔记，视频链接：2.3.4.1 信号量机制

知识总览

1. 信号量机制：
   • 整型信号量
   • 记录型信号量
2. 复习回顾+思考：之前学习的这些进程互斥的解决方案分别存在哪些问题？
   • 进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）
   • 进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）
3. • 在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
   • 所有的解决方案都无法实现“让权等待”
4. 1965年，荷兰学者DIjkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

信号量机制

1. 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
2. 信号量其实就是一个变量**（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量**
   • 比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
3. 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断，原语是由关中断/开中断指令实现的。
   • 软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，
   • 因此如果能把进入区、退出区的操作都用“原语”实现，
   • 使这些操作能“一气呵成”就能避免问题。
4. 第1点中的一对原语指的是wait(S)原语和signal(S)原语。
   • 可以把原语理解为我们自己写的函数，函数名分别为wait和signal，
   • 括号里的信号量S其实就是函数调用时传入的一个参数。
5. wait、signal原语常简称为P、V操作（来自荷兰语proberen和verhogen）。因此，做题的时候常把wait(S)和signal(S)两个操作分别写为P(S)、V(S)
6. 总结：
   • 信号量是一种变量，用来表示系统中某种资源的数量
   • 可以用系统中的一对原语（wait与signal）来对信号量进行操作
   • 信号量可以根据其类型分为整型信号量和记录型信号量

整型信号量

1. 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
   • 与普通整数变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作
   • 例子：某计算机系统中有一台打印机

int S = 1;   					// 初始化整型信号量S，表示当前系统中可用的打印机资源数

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

void signal (int S) { 	//signal 原语，相当于“退出区”
    S=S+1;   					//使用完资源后，在退出区释放资源
}

进程P0:
...
wait(S);        				//进入区，申请资源
使用打印机资源...  			//临界区，访问资源
signal(S);      				//退出区，释放资源
...

2. 特点：
   • 优点：类似先检查，后上锁，但是这里是原语，一气呵成，避免了并发、异步导致的问题
   • 缺点：不满足“让权等待”原则，会发生“忙等”
3. 补充：
   • 问：为什么原语有个while循环，又不可被中断，会不会导致一直占用处理器卡死？
     • 答：（来自视频）确实不太严谨，但是很多经典教材都这么写的，姑且认为没问题。
     • 答：（来自deepseek）会，所以该代码只能作为理论上的概念引入，实际系统中绝不可能直接这么写，否则系统一遇到资源竞争就会立刻卡死，这也是早期“整型信号量”机制被淘汰的原因。

记录型信号量

1. 整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
2. 代码示例：

/*记录型信号量的定义*/
typedef struct {
    int value;      //剩余资源数
    struct process *L;   //等待队列
} semaphore;

/*某进程需要使用资源时，通过 wait 原语申请*/
void wait (semaphore S) {
    S.value--;
    if (S.value < 0 ) {
        block (S.L);
        // 如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态
        // 并把其挂到信号量S的等待队列（即阻塞队列）中
    }
}

/*进程使用完资源后，通过 signal 原语释放*/
void signal (semaphore S) {
    S.value++;
    if (S.value <= 0) {
        wakeup(S.L);
        // 释放资源后，若还有别的进程在等待这种资源，
        // 则使用wakeup原语唤醒等待队列中的一个进程，
        // 该进程从阻塞态变为就绪态
    }
}

3. 补充：（个人总结）
   • 为什么wait的判断条件是S.value < 0，而signal是S.value <= 0？
     • 答：如果value无限大，也就是资源十分充足，wait中就不会有进程进入阻塞，
     • 所以前者的S.value < 0是资源不够的情况下，才有进程进入阻塞。
     • 后者在判断前S.value++，所以此时S.value <= 0就代表还有进程阻塞，就需要进行唤醒。
     • 注意，这里只针对每次申请和释放都是一个资源，如果同时申请、释放多个资源，那这个代码就有些问题。比如总共5个，A要3个，B要3个，B阻塞，资源数为-1，A释放后，资源数为2，此时就不会唤醒B了。
     • 其实原因也很简单，之前是S.value++，所以条件是S.value <= 0，之前的改成S.value+=k（k＞0），条件就应该改成S.value <= k-1

Pi进程：（用于第4点的例子）
...
wait(S);        				//进入区，申请资源
使用打印机资源...  			//临界区，访问资源
signal(S);      				//退出区，释放资源
...

4. 例子：
   • 某个计算机系统中有2台打印机，则可在初始化信号量S时将S.value的值设为2，队列S.L设置为空。
   • 假设有P0到P3总共4个进程如Pi所示，四个进程依次上CPU运行，过程如下：
     • P0上处理机：S.value=1，S.L={}
     • P1上处理机：S.value=0，S.L={}
     • P2上处理机：S.value=-1，S.L={P2}
     • P3上处理机：S.value=-2，S.L={P2,P3}
     • P0上处理机：S.value=-1，S.L={P3}
     • P1上处理机：S.value=0，S.L={}
     • P2上处理机：S.value=1，S.L={}
     • P3上处理机：S.value=2，S.L={}
5. 总结：
   • 在考研题目中，wait(S)和、signal(S)也可以记为P(S)、V(S)，这对原语可用于实现系统资源的“申请”和“释放”。
   • S.value的初值表示系统中某种资源的数目。
   • 对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value–，表示资源数-1，
     • 当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态$\to$阻塞态），主动放弃处理机，并插入该类资源的等待队列S.L中。
     • 可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
   • 对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数+1，
     • 若+1后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态$\to$就绪态）

知识回顾与重要考点

1. 整型信号量比较容易考察的是它存在的问题——不满足“让权等待”，可能出现“忙等”现象
2. 记录型信号量是操作系统这门课最重要的知识点，大题小题都有很高概率考察
3. 记录型信号量能够实现进程互斥、进程同步，这部分知识点会在下一小节进行讲解。