信号量

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

整型信号量

记录型信号量

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

信号量机制

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

经典问题

PV操作题目分析步骤:
1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。 (互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)

生产者-消费者问题

系统中有一-组生产者进程和- -组消费者进程，生产者进程每次生产-一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注: 这里的“产品”理解为某种数据)
生产者、消费者共享-一个初始为空、大小为n的缓冲区。

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（同步关系，当缓冲区满时，生产者必须等待消费者取走产品）
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（同步关系，消费者必须等到生产者放入产品才可以取出）
缓冲区是临界资源，各进程必须互斥地访问。

生产者每次要消耗(P)一个空闲缓冲区，并生产(V)一个产品
消费者每次要消耗(P)一个产品，并释放一个空闲缓冲区(V)
往缓冲区放入/取走产品需要互斥

在该问题中，同时使用两个p操作，第一个p操作是用以实现进程同步的，第二个p操作实现进程互斥的；
能否而改变顺序？

多生产者-多消费者

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
用PV操作实现上述过程。

可不可以不用互斥信号量？

原因在于:本题中的缓冲区大小为1，在任何时刻，apple、 orange、 plate 三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区..
但如果时多个资源互斥的话，有可能会造成写入数据的相互覆盖。

实现互斥的p一定要在实现同步的p后面

吸烟者问题

假设一个系统有三个抽烟者进程和一-个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉- - 支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第- -个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供.应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)

读者-写者

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求:
①允许多个读者可以同时对文件执行读操作;
②只允许-一个写者往文件中写信息;
③任一写者在完成写操作之前不允许其他读者或写者工作;
④写者执行写操作前，应让已有的读者和写者全部退出。

P(rw)和V(rw)其实就是对共享文件的“加锁”和“解锁”。既然各个读进程需要同时访问，而读进程与写进程又必须互斥访问，那么我们可以让第-一个访问文件的读进程“加锁”，让最后-一个访问完文件的读进程“解锁”。可以设置—个整数变量count来记录当前有几个读进程在访问文件。

先来先服务

读者-写者问题为我们解决复杂的互斥问题提供了-一个参考思路。其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第- 一个/最后一个读进程，从而做出不同的处理。另外，对count变量的检查和赋值不能一- 气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。最后，还要认真体会我们是如何解决“写进程饥饿”问题的。

哲学家进餐问题

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是- -碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时,才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

意思就是如果想给某个哲学家筷子，就将他需要的所有资源都给他，然后让他进餐，否则就一个都不给他

semaphore chopstick[5]={1,1,1,1,1};
do{
   //think;
   Swait(chopstick[(i+1)%5],chopstick[i]);
   //eat
   Ssignal(chopstick[(i+1)%5],chopstick[i]);
   //think
}while(TRUE);
void philosopher (void* arg) {
    while (1) {
        think();
        hungry();
        pthread_mutex_lock(mutex);
        pthread_mutex_lock(&chopsticks[left]);
        pthread_mutex_lock(&chopsticks[right]);
        pthread_mutex_unlock(mutex);
        eat();
        pthread_mutex_unlock(&chopsticks[left]);
        pthread_mutex_unlock(&chopsticks[right]);
    }
}

最多只允许四个哲学家进餐

①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就
避免了占有一支后再等待另一只的情况。

void philosopher (void* arg) {
    int i = *(int *)arg;
    int left = i;
    int right = (i + 1) % N;
    while (1) {
        printf("哲学家%d正在思考问题\n", i);
        delay(50000);
        printf("哲学家%d饿了\n", i);
        if (i % 2 == 0) {//偶数哲学家，先右后左
            pthread_mutex_lock(&chopsticks[right]);
            pthread_mutex_lock(&chopsticks[left]);
            eat();
            pthread_mutex_unlock(&chopsticks[left]);
            pthread_mutex_unlock(&chopsticks[right]);
        } else {//奇数哲学家，先左后又
            pthread_mutex_lock(&chopsticks[left]);
            pthread_mutex_lock(&chopsticks[right]);
            eat();
            pthread_mutex_unlock(&chopsticks[right]);
            pthread_mutex_unlock(&chopsticks[left]);
        }
    }
}

期末考试题

设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。
解：因为打印机是一种临界资源，所以这三个进程只能互斥使用这台打印机，即一个用户的计算结果打印完之后，另一个用户再打印。
设三个进程分别为A、B和C。
设一个互斥信号量mutex，其初值为1。
信号量 - 图24

两次生产-消费者

:::danger 新冠疫情下，某医院检验室开展疫情检测。假设有3个工作人员，护士负责检测患者获取样本，并传送给检验师；检验师检验后，将结果传送给资料员；资料员将结果生成检验报告并打印。护士、检验师共用一个容量为m个单元的样本放置架；检验师和资料员共用一个容量为n个单元的结果放置架。请写出满足上述条件的并发程序。（6分） ::: 这是两次生产者-消费者问题。护士进程为P，检验师进程为Q，资料员进程为R。P，Q，R共三个进程。其中，Q既是PQ中的消费者，又是QR中的生产者。1分.
信号量：
full_pq：PQ缓冲区的可用信息数，初值为0；
full_qr：QR缓冲区的可用信息数，初值为0；
empty_pq: PQ缓冲区的可用空位数，初值为m；
mpty_qr: QR缓冲区的可用空位数，初值为n；
mutex_pq：PQ缓冲区的互斥信号量，初值为1;
mutex_qr：QR缓冲区的互斥信号量，初值为1; 1分
算法：4分

semaphore full_pq=0,empty_pq=m,full_qr=0,empty_qr=n,mutex_pq=1,mutex_qr=1;
void p( )
{
    while(1) 
    {
        P从输入设备上读入信息;
        p(empty_pq);
        p(mutex_pq);
        P把信息放入缓冲区PQ;
        v(mutex_pq);
        v(full_pq);
   }
}
void q( )
{
    while(1) 
    {
        p(full_pq);
        p(mutex_pq);
        Q将信息从缓冲区PQ取出;
        v(mutex_pq);
        v(empty_pq);
        Q将信息加工;
        p(empty_qr);
        p(mutex_qr);
        Q将信息放入缓冲区QR;
        v(mutex_qr);
        v(full_qr);
   }
}
void r( )
{
    while(1) 
    {
        p(full_qr);
        p(mutex_qr);
        R将信息从缓冲区QR取出;
        v(mutex_qr);
        v(empty_qr);
        R打印;
   }
}