前言

正在学习操作系统，记录笔记。

（补充一下与信号量相关的问题类型以及解决思路）

参考资料：

《操作系统（精髓与设计原理 第6版） 》

王道考研：2019 王道考研 操作系统_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

正文

先声明：为了方便（就是我懒），下文可能会用P操作来指代semWait(x)；用V操作来指代semSignal(x)。

生产者-消费者问题

问题描述：

  • 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品理解为某种数据”）

  • 生产者、消费者共享一个初始为空、大小为n的缓冲区。

  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

  • 缓冲区是临界资源，各进程必须互斥地访问（只允许一个生产者放入消息，也只允许一个消费者拿出消息）。

    再次详细解释一下最后一点。意思是，同一个时刻只能是一个生产者或者一个消费者操作缓冲区，禁止以下情况：多个生产者或者多个消费者操作缓冲区；同样，一个生产者和一个消费者同时操作也是禁止的。

分析：

  • 互斥关系：不允许有两方及以上同时访问缓冲区。
  • 同步关系：存在两种同步关系，分别为缓冲区满、缓冲区空。（当消费者消费一个产品，应该告诉生产者，缓冲区有一个空位；当生产者生产一个商品，应该告诉消费者，缓冲区非空）

所以根据以上分析得知：应该需要三对P、V操作。因此需要定义如下三个信号量：

1
2
3
semaphore mutex = 1;    //互斥信号量，实现对缓冲区的访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量（初始值为n）
semaphore full = 0;    //同步信号量，表示产品的数量，也即非缓冲区的数量（初始值为0）

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*producer*/
void producer()
{
    while(1){
        /*生产一个产品*/;
        semWait(empty);    //检查有无缓冲区可用  (Ⅰ)
        semWait(mutex);    //互斥操作  (Ⅱ)
        /*将产品放入缓冲区*/;
        semSignal(mutex);    //互斥操作
        semSignal(full);    //告诉消费者“生产了一个产品”
    }
}

/*consumer*/
void consumer()
{
    while(1){
        semWait(full);    //检查有无产品（非空缓冲区）  (Ⅲ)
        semWait(mutex);    //互斥操作  (Ⅳ)
        /*从缓冲区中取出一个产品*/;
        semSignal(mutex);    //互斥操作
        semSignal(empty);    //告诉生产者“取走了一个产品，缓冲区有空闲”
        /*使用产品*/;
    }
}

void main()
{
    parbegin(producer(), consumer());
}

思考：能否改变相邻P、V操作的顺序？（即调换(Ⅰ)、(Ⅱ)以及(Ⅲ)、(Ⅳ)的顺序）

分析：

  • 分析此种情况：若缓冲区内已经放满产品，则empty=0，full=n。
  • 则生产者先执行(Ⅱ)（semWait(mutex)）操作使得mutex变为0，在执行(Ⅰ)操作（semWait(empty)），由于已经没有空闲缓冲区，因此生产者被阻塞。接着切换至消费者进程。消费者进程首先执行(Ⅳ)（semWait(mutex)）操作，由于mutex为0，即生产者还没有释放对临界资源的控制权，因此消费者也被阻塞。
  • 这就出现了死锁的情况（生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区）
  • 同样的我们分析另一种情况：若缓冲区中没有产品，即empty=n，full=0。按照(Ⅳ)``(Ⅲ)``(Ⅱ)的顺序也会发生死锁情况。

因此：

  • 实现互斥的P操作一定要在实现同步的P操作之后。
  • V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

还需要注意的一点：

生产者“生产一个产品”的操作以及消费者“使用产品”的操作可以放置P、V操作之间，但是要意识到这些操作是非必要的，如果放置在临界区操作则会导致其代码量变大，在一个进程访问临界区的同时就要耗费更多的时间，这会导致进程之间的并发度降低。（只在临界区做必要操作）

多生产者-多消费者问题

问题描述：

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

分析：

  • 互斥关系：将盘子视为缓冲区。每个人（进程）对其访问都是互斥的。
  • 同步关系：
    1. 父亲将苹果放入盘子后，女儿才能取苹果。
    2. 母亲将橘子放入盘子后，儿子才能取橘子。
    3. 只有盘子为空时，父亲或母亲才能放入水果。（盘子为空事件可由儿子或者女儿触发）

所以根据以上分析得知，需要定义如下四个信号量：

1
2
3
4
semaphore mutex = 1;    //实现互斥访问盘子（临界区）
semaphore apple = 0;    //盘子中有几个苹果（初始值为0）
semaphore orange = 0;    //盘子中有几个橘子（初始值为0）
semaphore plate = 1;    //盘子中还可以放多少个水果

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*dad*/
void dad()
{
    while(1){
        /*准备一个苹果*/;
        semWait(plate);    //检查盘子是否为空
        semWait(mutex);    //实现对盘子这一缓冲区的互斥访问
        /*把苹果放入盘子*/;
        semSignal(mutex);
        semSignal(apple);    //告诉女儿“盘子里有苹果了”
    }
}

/*mom*/
void mom()
{
    while(1){
        /*准备一个橘子*/;
        semWait(plate);    //检查盘子是否为空
        semWait(mutex);    //实现对盘子这一缓冲区的互斥访问
        /*把橘子放入盘子*/;
        semSignal(mutex);
        semSignal(orange);    //告诉儿子“盘子里有橘子了”
    }
}

/*daughter*/
void daughter()
{
    while(1){
        semWait(apple);    //检查盘子里有没有苹果
        semWait(mutex);    //实现对盘子这一缓冲区的互斥访问
        /*从盘子中取出苹果*/;
        semSignal(mutex);
        semSignal(plate);    //告诉父母“盘子为空了”
        /*吃掉苹果*/;
    }
}

/*son*/
void son()
{
    while(1){
        semWait(orange);    //检查盘子里有没有橘子
        semWait(mutex);    //实现对盘子这一缓冲区的互斥访问
        /*从盘子中取出橘子*/;
        semSignal(mutex);
        semSignal(plate);    //告诉父母“盘子为空了”
        /*吃掉橘子*/;
    }
}

void main()
{
    parbegin(dad(), mom(), daughter(), son());
}

思考：上述案例可不可以不使用互斥信号量（mutex）呢？

分析（删除上述代码中所有的semWait(mutex)以及semSignal(mutex)操作）：

  • 刚开始，儿子、女儿进程即使上处理机运行也会被阻塞。
  • 如果刚开始是父亲进程先上处理机运行，则：
    • 父亲执行semWait(plate)操作，可以访问盘子。
    • 母亲执行semWait(plate)操作，被阻塞等待盘子。
    • 父亲执行semSignal(apple)操作，放入苹果。
    • 女儿i进程被唤醒（其他进程即使运行也会阻塞）。
    • 女儿执行semWait(apple)操作，访问盘子。并接着执行semSignal(plate)操作。
    • 父亲或者母亲进程再次被唤醒（儿子进程访问会被阻塞）。
    • …

以上分析可以得出结论，即便没有互斥信号量（mutex），也不影响正常运行。

原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。

但是加入此题盘子的容量为2及以上，就无法保证进程互斥访问盘子。（分析过程省略）

最好直接就设置互斥信号量（mutex），以防出错。

吸烟者问题

问题描述：

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

分析：

  • 互斥关系：将桌子视为缓冲区，每个进程对其访问都是互斥的。

    值得注意的是，尽管供应者每次会将两种材料放置在桌子上，但是桌子（缓冲区）的容量仍为1，我们应该将不同的两种材料视为一种组合：

    • 组合一：纸 + 胶水
    • 组合二：烟草 + 胶水
    • 组合三：烟草 + 纸

  • 同步关系：

    1. 桌上有组合一 → 第一个抽烟者取走东西。
    2. 桌上有组合二 → 第二个抽烟者取走东西。
    3. 桌上有组合三 → 第三个抽烟者取走东西。
    4. 抽烟者抽完烟 → 供应者将下一种组合材料放到桌子上。

  • 需要让三个抽烟者轮流地抽烟。

所以根据以上分析得知，需要定义如下四个信号量：

1
2
3
4
5
semaphore offer1 = 0;    //桌上组合一的数量
semaphore offer2 = 0;    //桌上组合二的数量
semaphore offer3 = 0;    //桌上组合三的数量
semaphore finish = 0;    //抽烟是否完成
int i = 0;    //用于实现“三个抽烟者轮流地抽烟”

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*provider*/
void provider()
{
    while(1){
        if(i == 0){
            /*将组合一放桌上*/;
            semSignal(offer1);    //告诉第一个抽烟者“桌上有组合一”
        }
        else if(i == 1){
            /*将组合二放桌上*/;
            semSignal(offer2);    //告诉第二个抽烟者“桌上有组合二”
        }
        else if(i == 2){
            /*将组合三放桌上*/;
            semSignal(offer3);    //告诉第三个抽烟者“桌上有组合三”
        }
        i = (i + 1) % 3;
        semWait(finish);    //判断抽烟者是否已经完成吸烟
    }
}

/*smoker1*/
void smoker1()
{
    while(1){
        semWait(offer1);    //判断桌子上有没有组合一
        /*从桌子上拿走组合一；卷烟；抽掉*/;
        semSignal(finish);    //告诉提供者“桌子上已经空了”
    }
}

/*smoker2*/
void smoker2()
{
    while(1){
        semWait(offer2);    //判断桌子上有没有组合二
        /*从桌子上拿走组合二；卷烟；抽掉*/;
        semSignal(finish);    //告诉提供者“桌子上已经空了”
    }
}

/*smoker3*/
void smoker3()
{
    while(1){
        semWait(offer3);    //判断桌子上有没有组合三
        /*从桌子上拿走组合三；卷烟；抽掉*/;
        semSignal(finish);    //告诉提供者“桌子上已经空了”
    }
}

void main()
{
    parbegin(provider(), smoker1(), smoker2(), smoker3());
}

分析：是否需要专门再设置一个互斥信号量（mutex）？

因为桌子的容量为1（同上面一个例子相同），因此不必设置也不会出错。

读者-写者问题

问题描述：

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此我们要求：

  • 允许多个读者可以同时对文件执行读操作；
  • 只允许一个写者往文件中写信息；
  • 任一写者在完成写操作之前不允许其他读者或写者工作；
  • 写者执行写操作前，应让已有的读者和写者全部退出。

分析：

  • 互斥关系：

    1. 写进程——写进程

    2. 写进程——读进程

      （读进程之间不存在互斥关系，因此可以同时读文件，如何实现该操作是此类问题的关键）

所以根据以上分析得知，需要定义如下三个信号量：

1
2
3
semaphore rw = 1;    //用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;    //用于记录当前有几个读进程在访问文件
semaphore mutex = 1;    //用于保证对count变量的互斥访问

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*writer*/
void writer()
{
    while(1){
        semWait(rw);    //在写文件之前“上锁”
        /*写文件*/;
        semSignal(rw);    //在写完之后“解锁”
    }
}

/*reader*/
void reader()
{
    while(1){
        semWait(mutex);    //各读进程互斥访问count
        if(count == 0){
            semWait(rw);    //第一个读进程负责“上锁”
        }
        count++;    //访问文件的读进程数加一
        semSignal(mutex);    
        /*读文件*/;
        semWait(mutex);    //各读进程互斥访问count
        count--;    //访问文件的读进程数减一
        if(count == 0){
            semSignal(rw);    //最后一个读进程负责“解锁”
        }
        semSignal(mutex);
    }
}

void main()
{
    parbegin(writer(), reader1(), reader2(),...,readern());
}

分析：

mutex变量的设置是为了解决读进程对count的访问（解决多个读进程访问的操作）

  • 第一个读进程执行semWait(mutex)操作，顺利通过，并执行之后的semWait(rw)操作（保证了读进程与写进程的互斥）
  • 若此时另一个读进程访问，在执行semWait(mutex)操作会被阻塞，直到第一个读进程执行semSignal(mutex)操作（“解锁”对count的访问，注意此时count值为1）
  • 当count“解锁”后，另一个读进程再执行semWait(mutex)操作，判断count的值不为0，直接跳过semWait(rw)访问，这样就避免了各个读进程之间的互斥访问

再仔细体会会发现上述代码存在一个潜在的问题，即：如果读进程一直在不停地访问（count值永不为0），就无法对文件“解锁”，写者进程就可能“饿死”。

因此该种写法是读进程优先。

如何实现写进程优先呢？

这里我们再增加一个信号量：semaphore w = 1。

即现在一共有如下四个信号量：

1
2
3
4
semaphore rw = 1;    //用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;    //用于记录当前有几个读进程在访问文件
semaphore mutex = 1;    //用于保证对count变量的互斥访问
semaphore w = 1;    //用于实现“写进程优先”

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*writer*/
void writer()
{
    while(1){
        semWait(w);    //Ⅰ
        semWait(rw);    //在写文件之前“上锁”  Ⅱ
        /*写文件*/;
        semSignal(rw);    //在写完之后“解锁”  Ⅲ
        semSignal(w);    //Ⅳ
    }
}

/*reader*/
void reader()
{
    while(1){
        semWait(w);    //Ⅴ
        semWait(mutex);    //各读进程互斥访问count  
        if(count == 0){
            semWait(rw);    //第一个读进程负责“上锁”  Ⅵ
        }
        count++;    //访问文件的读进程数加一
        semSignal(mutex);
        semSignal(w);    //Ⅶ
        /*读文件*/;
        semWait(mutex);    //各读进程互斥访问count
        count--;    //访问文件的读进程数减一
        if(count == 0){
            semSignal(rw);    //最后一个读进程负责“解锁”  Ⅷ
        }
        semSignal(mutex);
    }
}

void main()
{
    parbegin(writer(), reader1(), reader2(),...,readern());
}

分析：（容我吐槽一下，简直头皮发麻）

  1. 读者1 → 读者2

    • 第一个读进程顺利通过Ⅴ（semWait(w)）操作，并对文件（rw）“上锁”，count++，…，到最后顺利地读文件。
    • 第二个读进程同上。
    • 即在增添了Ⅴ（semWait(w)）操作以及Ⅶ（semSignal(w)）对多个读进程并发访问文件是没有影响的。

  2. 写者1 → 写者2

    • 第一个写进程会顺利通过Ⅰ（semWait(w)）操作，Ⅱ（semWait(rw)）操作，并顺利写文件。
    • 第二个写进程如果并发执行会被阻塞在Ⅰ处，直到第一个写进程执行Ⅳ（semSignal(w)）“解锁写操作”，才可以继续执行。
    • 实现了多个写进程之间的互斥。

  3. 写者1 → 读者1

    • 写着进程顺利通过Ⅰ（semWait(w)）操作，Ⅱ（semWait(rw)）操作，开始写文件。
    • 此时如果读进程要执行，就会被阻塞在Ⅴ（semWait(w)）操作，直到写进程执行完Ⅳ（semSignal(w)）“解锁写操作”，才可以继续执行。
    • 实现了读者与写者的互斥。

  4. 读者1 → 写者1 → 读者2

    • 第一个读进程可以顺利执行到读文件操作。
    • 此时若写进程执行，可以顺利执行Ⅰ（semWait(w)）操作，但在Ⅱ（semWait(rw)）操作会被阻塞。
    • 然后第二个读进程并发执行，由于上一步读进程顺利执行Ⅰ（semWait(w)）操作，所以第二个读进程会被阻塞在Ⅴ（semWait(w)）操作。
    • 直到第一个读进程执行完Ⅷ（semSignal(rw)）操作对文件“解锁”，此时写进程就可以被唤醒，开始写文件。
    • 第二个读进程依然被阻塞在Ⅴ（semWait(w)）操作，直到写进程执行完Ⅳ（semSignal(w)）操作，第二个读进程才可以继续执行。
    • 所以这种情况并不会导致写进程“饥饿”。

  5. 写者1 → 读者1 → 写者2

    • 第一个写进程顺利执行前面的操作，开始写文件。

    • 此时如果读进程执行，则会被阻塞在Ⅴ（semWait(w)）操作。

    • 此时如果第二个写进程执行，则也会被阻塞在Ⅰ（semWait(w)）操作。

    • 如果第一个写进程执行完Ⅳ（semSignal(w)）操作，则此时会根据“先来先得”的原则，首先唤醒读进程，读进程顺利执行。

    • 然后读进程会执行Ⅵ（semWait(rw)）操作对文件“上锁”，在执行完Ⅶ（semWait(w)）操作时释放对写进程的操作，第二个写进程就继续执行，但是会被阻塞在Ⅱ（semWait(rw)）操作。

    • 读进程继续执行，直到结束，释放对文件的访问控制，第二个写进程才可以顺利执行。

    • 在这种情况我们可以分析出，尽管不会使得写进程“饥饿”，但也不是真正的“写进程优先”，而是符合相对公平的先来先服务的原则。

哲学家进餐问题

问题描述：

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

分析：

  • 互斥关系：系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。

    这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的关键。

所以根据以上分析得知，需要定义如下信号量数组以及一个互斥信号量：

1
2
semaphore chopstick[5] = {1,1,1,1,1};    //用于实现对5根筷子的互斥访问
semaphore mutex = 1;    //互斥地取筷子

并规定对哲学家按0~4编号，哲学家 i 左边的筷子编号为 i，右边的筷子编号为 ( i + 1 ) % 5。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*philosopher*/
void philosopher(int i)
{
    while(1){
        /*思考*/;
        semWait(mutex);
        semWait(chopstick[i]);    //拿起左筷
        semWait(chopstick[(i+1)%5]);    //拿起右筷
        semSignal(mutex);
        /*进餐*/;
        semSignal(chopstick[i]);    //放下左筷
        semSignal(shopstick[(i+1)%5]);    //放下右筷
        /*思考*/;
    }
}

void main()
{
    parbegin (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
}

分析：

哲学家进程要想正常进行就需要同时拿起左右两根筷子，一旦请求资源无法满足，就会进入阻塞态。

方法二：

分析：根据“鸽笼原理”，只要最多只有四位哲学家并发争夺筷子进餐，那么肯定会有一位哲学家可以同时拿到两根筷子。为此我们定义如下信号量：

1
2
semaphore chopstick[5] = {1,1,1,1,1};    //用于实现对5根筷子的互斥访问
semaphore room = 4;    //最多允许4为哲学家进餐

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*philosopher*/
void philosopher(int i)
{
    while(1){
        /*思考*/;
        semWait(room);
        semWait(chopstick[i]);    //拿起左筷
        semWait(chopstick[(i+1)%5]);    //拿起右筷
        /*进餐*/;
        semSignal(chopstick[i]);    //放下左筷
        semSignal(shopstick[(i+1)%5]);    //放下右筷
        semSignal(room);
        /*思考*/;
    }
}

void main()
{
    parbegin (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
}

方法三：

要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子；而偶数号的哲学家相反，先拿右边的筷子，再拿左边的筷子。在这种策略下，如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一支的情况。

首先定义如下信号量：

1
semaphore chopstick[5] = {1,1,1,1,1};    //用于实现对5根筷子的互斥访问

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*philosopher*/
void philosopher(int i)
{
    while(1){
        if(i % 2 == 1){    //奇数号哲学家
            /*思考*/;
            semWait(chopstick[i]);    //拿起左筷
            semWait(chopstick[(i+1)%5]);    //拿起右筷
            /*进餐*/;
            semSignal(chopstick[i]);    //放下左筷
            semSignal(shopstick[(i+1)%5]);    //放下右筷
            /*思考*/;
        }
        if(i % 2 == 0){    //偶数号哲学家
            /*思考*/;
            semWait(chopstick[(i+1)%5]);    //拿起右筷
            semWait(chopstick[i]);    //拿起左筷
            /*进餐*/;
            semSignal(shopstick[(i+1)%5]);    //放下右筷
            semSignal(chopstick[i]);    //放下左筷
            /*思考*/;
        }
    }
}

void main()
{
    parbegin (philosopher(0), philosopher(1), philosopher(2), philosopher(3), philosopher(4));
}

后记

本篇还没结束，持续更新中。

（欢迎评论区批评指正）