信号量机制（重要）-第二十八天

目录

前言

信号量机制

信号量S

整型信号量

记录型信号量

四个原语

实例（对于单核CPU的情况）

本节思维导图

---

前言

????????之前我们学习了关于进程互斥的四种软件实现方法（单标志法、双标志先检查法、双标志后检查法、Peterson算法）和三种硬件实现方法（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）但是它们都存在一定的缺陷：

1. 双标志先检查法中，进入区的"检查"、“上锁”操作无法一气呵成，从而导致了两个进程可能同时进入临界区
2. 所有解决方案都无法实现“让权等待”

为此，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制??

信号量机制

基本概念：用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程同步

信号量S

基本概念：一个变量，可以用来表示系统中某种资源的数量（系统中只有一台打印机，就可以设置一个初始值为1的信号量）

原语： 一种特殊的程序段，其执行只能一气呵成，不可被中断（原语是由关中断/开中断指令实现的。进程互斥的软件实现方式的主要问题是“进入区和退出区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题）

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的参数?

wait、signal原语通常被简称为P、V操作（来自荷兰语proberen和verhogne）因此，wait(S)和signal(S)两个操作也可以写为P(S)、V(S)

整型信号量

基本概念：用一个整型数的变量作为信号量，用来表示系统中某种资源的数量

与普通整型变量的区别：对信号量的操作只有三种：初始化、P操作、V操作

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

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

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

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



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


其他进程...


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

优点：进入区的“检查”和“上锁”、退出区的“解锁”都依靠原语一气呵成，避免了进程并发、互斥导致的问题

缺点：不满足“让权等待”原则，还是会发生“忙等”

记录型信号量

基本概念：用记录型数据结构表示的信号量：

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

四个原语

/*某进程需要使用资源时，通过wait原语申请*/
void wait(semaphore S)
{
    S.value--;
    if(S.value < 0)
    {
        block(S.L); 
    }
}

/*进程使用完资源后，通过signal原语释放*/
void signal(semaphore S)
{
    S.value++;
    if(S.value <= 0)
    {
        wakeup(S.L);    
    }
}

block原语：剩余资源数不足，使用block原语使进程从运行态转为阻塞态，并将其挂至信号量S的 等待队列（阻塞队列）中 （S.L）

wakeup原语：释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态

实例（对于单核CPU的情况）

有两台打印机，初始化记录型信号量S时，剩余资源数value=2、等待队列L =? NULL

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

?现有四个进程要使用临界区资源（两台打印机）

！！！对于单核CPU，同一时间只运行一个进程上CPU 执行！！！

根据时间片轮转：

1、进程P0先上CPU，P0进程执行wait原语后value--变为1，不会执行block原语

2、进程P1接着上CPU，P1进程执行wait原语后value--变为0，不会执行block原语

3、进程P2接着上CPU，P2进程执行wait原语后value--变为-1，执行block原语，P2进程被挂在阻塞队列

4、进程P3接着上CPU，P2进程执行wait原语后value--变为-2，执行block原语，P2进程被挂在阻塞队列

根据时间片轮转：

1、P0可以访问临界区资源（上CPU）

2、P1可以访问临界区资源（上CPU）

3、P0执行signal原语，value++变为-1，执行wakeup原语，此时P2被唤醒（阻塞态->就绪态）P3仍为阻塞态，P0下CPU【假设此时P0已执行完毕】

4、P2可以访问临界区资源（上CPU）

5、P2执行signal原语，value++变为0，执行wakeup原语，此时P3被唤醒（阻塞态->就绪态），P2下CPU【假设此时P2已执行完毕】

6、P1接着访问临界区资源（上CPU，上一次给的时间片不够用）

7、P1执行signal原语，value++变为1，不执行wakeup原语，P1下CPU【假设此时P1已执行完毕】

8、P3可以访问临界区资源（上CPU）

9、P3执行signal原语，value++变为2，不执行wakeup原语，P3下CPU【假设此时P3已执行完毕】

本节思维导图

~over~