王道操作系统笔记，视频链接：2.3.4.2 用信号量实现进程互斥、同步、前驱关系

知识总览

1. 信号量机制：
   • 实现进程互斥
   • 实现进程同步
   • 实现进程的前驱关系
2. 注意：
   • 不要死磕代码，要注意理解信号量的含义，一个信号量对应一种资源。
   • 信号量的值=这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）
   • P(S)——申请一个资源S，如果资源不够就阻塞等待
   • V(S)——释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

信号量机制实现进程互斥

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应该放在临界区）
2. 设置互斥信号量mutex，初值为1。
   • 可以理解为进入临界区的名额为1
3. • 在进入区P(mutex)——申请资源
   • 在退出区V(mutex)——释放资源
4. 代码举例：

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

/*信号量机制实现互斥*/
semaphore mutex=1;  //初始化信号量
//题目没有特别说明的情况下，
//对信号量的定义直接用“semaphore mutex=1;”
//这种类似的形式即可，不用写出信号量的数据结构（就是前文的struct）
//但是依然需要会写信号量的数据结构
//semaphore定义的信号量就是记录型信号量，带有阻塞队列的

P1() {
    ...
    P(mutex);     //使用临界资源前需要加锁
    临界区代码段...
    V(mutex);     //使用临界资源后需要解锁
    ...
}

P2() {
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

5. 注意：
   • 只要用了semaphore关键字定义的信号量就一定是记录型信号量，附带阻塞队列，不会出现忙等
   • 对于不同的临界资源需要设置不同的互斥信号量
   • P、V操作必须成对出现
     • 缺少P操作，就不能保证临界资源的互斥访问
     • 缺少V操作，会导致资源永不被释放，等待进程永不被唤醒

信号量机制实现进程同步

1. 进程同步：要让各并发进程按要求有序地推进。
2. 需要进程同步的例子：
   • 比如，P1、P2并发执行，由于存在异步性，因此二者交替推进地次序是不确定地。
   • 若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。
3. 用信号量实现进程同步：
   • 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
   • 设置同步信号量S, 初始为0
4. 代码示例：（依据第2点给的例子）

/*信号量机制实现同步*/
semaphore S=0; //初始化同步信号量，初始值为0
// 这里的信号量S就可以看作P1代码1和代码2给出的运行结果
// 当代码1和代码2没有运行完成时，S就一直为0
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了。

5. 总结：（前V后P）
   • 在“前操作”之后执行V(S)
   • 在“后操作”之前执行P(S)
   • 说明：
     • 也就是在要先运行的代码之后用V，释放资源
     • 在后要运行的代码之前用P，占用资源
     • 用P、V的特性来确保两者的先后顺序

信号量机制实现前驱关系

1. 进程P1中有句代码S1，P2中有句代码S2，P3中有句代码S3……P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：
   

• 如图所示，箭头方向代表执行顺序，比如S6，需要S4、S5、S3都运行完后才能运行。
• 其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作），因此：
  • ①要为每一对前驱关系各设置一个同步信号量
    • 就是下图中的a,b,c,d这些小写字母
  • ②在“前操作”之后对相应的同步信号量执行V操作
  • ③在“后操作”之前对相应的同步信号量执行P操作
    
• 对应的代码图如下：
  

知识回顾与重要考点

1. 几乎每一年都有一个大题考察怎么用信号量机制实现进程的互斥同步
2. 除了互斥、同步问题外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行V操作即可。
3. • 互斥问题，信号量初值为1
   • 同步问题，信号量初值为0
   • 前驱关系问题，本质上就是多级同步问题
4. 下一个小节将介绍几个经典的进程同步问题辅助理解学习