信号量是实现进程同步的一种重要手段

进程同步

进程同步两种形式，

• 互斥关系，
• 合作关系

进程同步机制的主要任务是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地互相合作，从而使程序的执行具有可再现性。

同步机制遵循的规则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

硬件同步机制

1. 关中断
2. 利用test-and-set指令实现互斥
3. 利用swap指令实现进程互斥

信号量机制

发展过程（也是一种分类）

1. 整型信号量
2. 记录型信号量
3. 信号量集

整型信号量

最初，整型信号量定义为一个用于表示资源数目的整型量S，

两个原子操作，执行时不可中断(即当某个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改)，且不可分割，成对出现

wait(S) ---> P

signal(S) ---> V

wait(S){
    while(S<=0);
    S--
}

signal(S){
    S++;
}

在wait操作中，只要信号量S<=0，就一直测试，没有遵循进程同步规则中的 “让权等待”

使进程处于忙等状态。

记录型信号量

机制：为了解决因为让权等待原则出现，多个进程访问同一个临界资源，增加了一个表资源数目的整型变量 value 外，还增加了一个进程链表指针，用于链接上述的所有进程。

记录型信号量是由于其采用了记录型的数据结构而得名

typedef struct{
    int value;
    struct process_control_block *list;
}semaphore;

// 相应的wait，signal操作
wait(semaphore *S){
    S->value--;
    if(S->value<0){
        block(S->list);
    }
}

signal(semaphore *S){
    S->value++;
    if(S->value<=0){
        wakeup(S->list);
    }
}

记录型信号量机制中，S->value 的初值表示系统中某类资源的数目，因而又称为资源信号量，

对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源减少一个，即S->value--，当S->value<0 时，表示该类资源已分配完毕，因此进程应用调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表中的阻塞进程链表中，这一点体现了 “让权等待”原则，此时 S->value 的绝对值表示在该信号量链表上已阻塞的进程数，

对信号量的每次signal操作，表示执行进程放弃一个单位的资源，是系统中该类资源数目加1，即S->value++,若加1后仍是 S-> value <=0，则表示在该链表中仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S->list链表中 的第一等待的进程唤醒。

互斥信号量

当记录型信号量的 S-value 初值为1时，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量

AND型信号量

产生背景

上述中针对的都是多个进程一次请求一个共享临界资源的情况。

在大多数场景下，进程需要申请多个资源才能开始执行任务，

例，两个进程A、B，它们都要求访问共享数据D和E，此时D和E都应作为临界资源。为此需要对这两个数据分别设置用于互斥的信号量Dmutex，Emutex，并令他们的初值都为1。相应地，在两个进程中都要包含对两个Dmutex，和Emutex的操作

process A{
    wait(Dmutex);
    wait(Emutex);
}
process B{
    wait(Dmutex);
    wait(Emutex);
}

此时AB按如下次序进行交替执行wait操作

A：wait(Dmutex); Dmutex 减为0

B：wait(Emutex); Emutex减为0

A：wait(Emutex); Emutex减为-1；

B：wait(Dmutex); Dmutex减为-1;

此时A,B均被阻塞，无法继续执行，也就产生了==死锁==现象

显然，当进程同时要求的共享资源越多，发生死锁的可能性也就越大。

AND型信号量机制

将进程在整个运行过程中需要的所有资源，==一次性==全部分配给进程，待进程使用完再一起释放。只要有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。

这里其实是破坏死锁的==请求和保持==条件，可以避免死锁情况的发生

为此AND型信号量中增加了一个and条件，故称为and同步，或称为 同时wait操作，即wait(simultaneous wait)

Swait(S1,S2,...,Sn){
    while(true){
        if(S1>=1 && S2>=1 &&... Sn>=1){
            for(i=1;i<=n;i++){
                Si--;
            }
            break;
        }else{
          // 将进程放入请求队列（第一个发现的请求资源<1的请求队列）中，
          // 然后将资源恢复到最初请求前的情况
        }
    }
}
Ssignal(S1,S2,...,Sn){
    while(true){
        if(S1>=1 && S2>=1 &&... Sn>=1){
            for(i=1;i<=n;i++){
                Si++;
            }
            break;
        }else{
          // remove all the process waiting in the queue associated with si into the randy queue
        }
    }
}

信号量集

上面的AND型，针对的是进程每一个请求一个单位的共享临界资源的情况，但实际场景下，可能每类资源需求请求多个后才开始执行，如果采用AND型的话，就需要连续请求多次，这样效率就比较低，还会增加死锁的可能。

在某些情况下，为保证系统的安全性，当所请求的资源数量低于某一个下限值时，还必须进行管制，不予分配。

基于上面这两点，对AND型信号量进行扩充，对进程所申请的所有资源以及每类资源的不同资源需求量，在一次PV原语操作中完成，申请和释放。且进程对信号量的测试值也不再是1，而是该资源的分配下限ti, 即要求Si>=ti,否则不予分配。

一旦允许分配，进程对该资源的需求量为di，即表示资源占有量，进行Si = Si-di操作，而不是简单的Si=Si -1。由此形成的信号量机制。对应的Swait和Ssignal格式为

Swait(S1,t1,d1,S2,t2,d2...Sn,tn,dn);
Ssignal(S1,t1,d1,S2,t2,d2...Sn,tn,dn);

信号量集的特殊情况

Swait(S,d,d)

此时在信号量集上只有一个信号量S，但允许他每次申请d个资源，当资源数少于d时，不予分配

Swait(S,1,1);

此时的信号量集已经退化为一般的记录型信号量（S>1时)或互斥型信号量（S=1时）

Swait(S,1,0);

这是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，阻止任何进程进入特定区。相当于一个==可控开关==

信号量的应用

1. 利用信号量实现 进程互斥
2. 利用信号量实现 前驱关系

有几个同步关系，几个同步量

同步在前，互斥在后

前驱图，几条边，几个信号量

生产者-消费者问题

该问题既有生产者和消费者对缓冲区的争夺即互斥问题

也有生产者生产商品对消费者的制约，也有消费者消费商品对生产者的制约，（属于暗含关系，需要分析出来）

1.记录型信号量解决生产者-消费者问题

缓冲池中可容纳n个缓冲区

互斥问题，设置互斥信号量 mutex

两个制约问题也即合作问题，分别设置两个记录型信号量 full empty = n

则有

producer{
    wait(empty);
    wait(mutex);
    produce();
    signal(mutex);
    signal(full);
}

consumer{
    wait(full);
    wait(mutex);
    consume();
    signal(mutex);
    signal(empty);
}

2.利用AND型信号量来解决生成者-消费者问题

producer同时获取到mutex和empty

consumer 同时获取到 mutex和full

producer{
    Swait(empty,mutex);
    // 放入商品
    Ssignal(mutex,full);
}

consumer{
    Swait(full,mutex);
    // 取走商品
    Ssignal(mutex,empty);
}

哲学家进餐问题

有五个哲学家共有一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。

哲学家进餐问题可看作是并发进程并发执行时处理共享资源的一个有代表性的问题。

1.利用记录型信号量解决哲学家进餐问题

记录型信号量就是针对资源数设置信号量，五个筷子都是不同的资源，需要分别设置一个信号量（也是一个互斥信号量）。

seamphore chopstick[5] = {1,1,1,1,1};

每一位哲学家就是一个并发进程，

do{
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    // 吃饭
    signal(chopstick[(i+1)%5]);
    signal(chopstick[i]);
    // 思考
}while(true)

这一算法可以保证不会有相邻的两位哲学家同时进餐，

但当每一个哲学家同时访问其左边的筷子，此时5根筷子的信号量均为0，也就无法得到其右边的筷子，此时便产生了 死锁

一些改进解法

方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。

方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。

方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

2.利用AND型信号量解决哲学家进餐问题

AND型，要么同时得到两个筷子，要么一个也不要

do{
    Swait(chopstick[i],chopstick[(i+1)%5]);
    // 吃饭
    Ssignal(chopstick[(i+1)%5],chopstick[i]);
    // 思考
}while(true)

这样不会出现死锁

读者写者问题

一个数据对象（数据文件或记录）可被多个进程共享。其中，reader 进程要求读，writer 进程要求写或修改。允许多个进程同时读一个对象，电脑不允许一个writer进程和其他reader进程或者write进程同时访问共享对象

1.利用记录型信号量解决读者-写者问题

为了实现reader和writer进程在读或写时的互斥，设置互斥信号量wmutex，另外再设置一个整型变量readcount表示正在读的进程数目。只要有一个reader进程在读，便不允许writer进程去写。因此仅当readcount = 0时reader进程才需要执行wait(wmutex)操作，(不为0的时候就表明，此时已经有读者进程在读，写者进程无法写，所以不需要执wait(wmutex)操作)readcount+1

同样对于当readcount 减1后值为0时，才执行signal(wmutex)操作，以便让writer进程写

又由于 readcount 这个数据也要被多个reader进程访问，也是临界资源，也需要为其设置一个访问的互斥信号量 rmutex

semaphore rmutex = 1,wmutex = 1;
int readcount = 0;
void reader(){
    do{
        wait(rmutex);
        if(readcount==0){wait(wmutex);}
        readcount ++;
        signal(rmutex);
        // 进行读操作

        wait(rmutex);
        readcount--;
        if(readcount == 0){signal(wmutex);}
        signal(rmutex);
    }while(true)
}

void writer(){
    do{
        wait(wmutex);
        // 执行写操作 
        signal(wmutex);

    }while(true)
}

读者，写者进程互相并发

2.利用信号量集解决读者-写者问题

增加了一个限制，最多允许RN个读者进行访问，增加一信号量L = RN

每有一个读者进程访问就执行wait(L，1,1)，当RN个进程访问后，此时L减到0，当第RN+1个读者进程来访问，执行wait(L,1,1)就会阻塞

int RN;
seamphore L = RN,mx = 1;
void reader(){
    do{
        Swait(L,1,1);
        Swait(mx,1,0); // 相当于一个开关,允许任何进程进入
        // 执行读操作
        Ssignal(L,1);

    }while(true)
}

void writer(){
    do{
        Swait(L,RN,0;mx,1,1);
        // L,RN,0, 在没有读者即L=RN时，允许写进程进入，又mx,1,1 一个记录型信号量，保证一次只能又一个进程写，所以这两个信号量共同保证了正常执行
        // 执行写操作
        Ssignal(mx,1);
    }while(true)
}

读者，写者并发执行

一些实际问题

例：有一只铁笼子，每次只能放入一只动物。猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用 P、V 操作写出能同步执行的程序。

这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲器。生产者各自生产不同的产品，消费者各自取自己需要的产品。

这里存在一个互斥，农民，饭店，动物园，三者访问铁笼，铁笼且只能放入一个动物，设置资源信号量 S = 1

这里存在着2种制约，农民、猎手制约动物园，饭店；动物园，饭店又制约农民、猎手 设置 2个记录型信号量，S1 表示是否有老虎，S2表示是否有猪，初值均为0

hunter{
    P(S);
    // 放入老虎
    V(S1)
}

farmer{
    P(S);
    // 放入猪
    V(S2);
}

zoo{
    P(S1);
    // 取走老虎
    V(S);
}

restrant{
    P(S2);
    // 取走猪
    V(S);
}

四个进程相互并发执行

例：桌上有一空盘，允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定盘空时一次只能放一只水果供吃者取用，请用 P、V 原语实现爸爸、儿子、女儿三个并发进程的同步。

盘子访问作为一种资源 设信号量S = 1;

一次只能放入一个水果，对于两种水果，设置两个信号量 S1 = 0，S2 = 0；

father{
    P(S);
    if(放入苹果){
        S(S1);
    }else{
        S(S2);
    }
}

son{
    P(S1);
    // 取橘子
    V(S);
}

daughter{
    P(S2);
    // 取苹果
    V(S);
}

例：若有一售票厅只能容纳 300 人，当少于 300 人时可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用 P、V 操作编程，并写出信号量的初值。

购票者进程Pi i=1,2,3...

设信号量S，初值 = 300

P(S)

进入售票厅

购票

退出售票厅

V(S)

例：有一阅览室，读者进入时必须先在一张表上进行登记。该表为每一座位列出一个表目（包括座号、姓名、阅览时间），读者离开时要撤消登记信息。阅览室有 100 个座位。‹为描述读者的动作，应编写几个程序，应设置几个进程？程序和进程之间的对应关系如何？
试用 P、V 操作描述这些进程间的同步关系。

100个座位即100个进程

登记与注销互斥，设置一个互斥信号量 mutex = 1

对座位资源设置一个资源信号量 S=100

P(S);
P(mutex);  // 一定是先同步，后互斥 先P(S) 后P(mutex)
登记;
V(mutex);
阅览;
P(mutex);
注销;
V(mutex);
V(S); // 释放座位