为什么提出信号量机制?

进程互斥的四种软件实现方法(单标志法，双标志先检查、双标志后检查，Peterson算法)

进程互斥的三种硬件实现方法(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)

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

信号量机制

信号量机制是1965年由荷兰学者Dijkstra提出的一种为实现进程互斥、同步卓有成效的方法

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

整型信号量

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

//初始化整型信号量S，表示当前系统中可用的打印机资源数
int S = 1;
//wait原语 相当于进入“进入区”（检查 和 上锁 一气呵成避免了并发、异步导致的问题）
void wait(int S){
  //如果资源数不够，就一直循环等待（存在的问题：不满足让权等待原则，会发生忙等）
  while (S<=0);
  //如果资源数够，则占用一个资源
  S=S-1;
}
//signal原语，相当于退出区
void signal(int S ){
 //使用完资源后，在退出区释放资源 
 S=S+1;
}

记录型信号量

整型信号量的缺陷是存在忙等的问题，因此又提出了“记录型信号量“，即用记录型数据结构表示的信号量

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

//某进程需要使用资源时，通过wait原语申请
void wait(semaphore S){
  S.value--;
  if(S.value<0){
    /**
    * 执行wait后 -- 如果--后小于0了，证明在--之前就已经没有这种系统资源了
    * 所以，使用block原语使进程从运行态进入阻塞态，并挂到信号量S的等待队列(即阻塞队列)中
    */
    block(S.L);
  }
}

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

S.value的初值表示系统中某种资源的数目。
对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减1，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态->阻塞态)，主动放弃处理机，并插入该类资源的等待队列S.L中。可见，改机制遵循了让权等待原则，不会出现忙等的现象。
对信号量S的一次V操作意味着进程释放了一个单位的该类资源，因此需要执行S.value++,表示资源数加1。若加1后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(别唤醒进程从阻塞态->就绪态)

用信号量机制实现进程互斥、同步、前驱关系

信号量的值=这种资源的剩余数量(信号量的值如果小于0，说明此事有进程在等待这种资源)

P(S)--申请一个资源S，如果资源不够就阻塞等待

V(S)--释放一个资源S，如果有进程正在等待该资源，则唤醒一个进程

信号量机制实现进程互斥

分析并发进程的关键活动，划定临界区(如，对临界资源打印机的访问就应该放在临界区)
设置互斥信号量mutex，初始值为1
在进入区执行P(mutex)--申请资源
在退出区执行V(mutex)--释放资源

记录型信号量简写 semaphore mutex=1;

要回自己定义记录型信号量，但如果题目中没特别说明，可以把信号量的声明简写

//记录型信号量
typedef struct{
  int value;
  struct process *L;
}semaphopre;

注意：对于不同的临界资源需要设置不提供的互斥信号量。

P、V操作必须成对出现，缺少P(mutex)就不能保证临界资源的互斥访问。

缺少V(mutex)会导致资源永不释放，等待进程永不被唤醒

信号量机制实现进程同步

进程同步：要让各并发进程有序的进行

用信号量实现进程同步

分析什么地方需要实现“同步关系”，即必须保证”一前一后”执行的两个操作
设置同步信号S,初始值为0；
在“前操作”之后执行V(S);
在“后操作“前执行P(S);

//信号量
semaphore S=0;

P1(){             p2(){
  代码1;              P(S);
  代码2;              代码4;
  V(S);//释放资源      代码5;
  代码3;              代码6;
}                 }

代码中："semaphore S=0;"

信号量S代表 ”某种资源“，刚开始是没有这种资源的，P2需要使用这种资源就必须由P1释放这种资源也就是产生这种资源

若先执行到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(S)操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了。

这种操作可以称为前V后P

信号量机制实现前驱关系

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

其实每一对前驱关系都是一个进程同步问题(需要保证前V后P的操作)

因此

要为每一对前驱关系设置一个同步信号量
在”前操作”之后对应的同步信号量执行V操作
在“后操作”之前对应的同步信号量执行P操作

信号量机制
- 实现进程互斥
  - 分析问题，确定临界区
  - 设置互斥信号量，初始值为1
  - 临界区之前对信号量执行P操作
  - 临界区之后对信号量执行V操作
- 实现进程同步
  - 分析问题，找出哪里需要实现“一前一后”的同步关系
  - 设置同步信号量，初始值为0
  - 在”前操作“之后执行V操作
  - 在”后操作“之前执行P操作
- 实现进程的前驱关系
  - 分析问题，画出前驱图，把每一对前驱关系都堪称一个同步问题
  - 为每一个前驱关系设置同步信号量，初值为0
  - 在每个”前操作“之后执行V操作
  - 在每个”后操作“之前执行P操作

除了互斥、同步问题之外，还会考察有多个资源的问题，有多少资源就把信号量的初值设为多少。

申请资源时进行P操作，释放资源时执行V操作即可