用信号量解决三种进程的同步问题

发表于 分类于 ， Waline：
本文字数： 3k 阅读时长 ≈ 3 分钟

问题描述

Santa Claus sleeps in his shop at the North Pole and can only be wakened by either

  1. all nine reindeer being back from their vacation in the South Pacific, or

  2. some of the elves having difficulties making toys;

To allow Santa to get some sleep, the elves can only wake him when three of them have problems. When three elves are having their problems solved, any other elves wishing to visit Santa must wait for those elves to return. If Santa wakes up to find three elves waiting at his shop’s door, along with the last reindeer having come back from the tropics, Santa has decided that the elves can wait until after Christmas, because it is more important to get his sleigh ready. (It is assumed that the reindeer do not want to leave the tropics, and therefore they stay there until the last possible moment.) The last reindeer to arrive must get Santa while the others wait in a warming hut before being harnessed to the sleigh.

Solve this problem using semaphores.

解决

信号量声明

1
2
3
4
class Semaphore;

void semWait(Semaphore&);
void semSignal(Semaphore&);

实现

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 圣诞老人数
#define MAX_SANTA       6
// 驯鹿数
#define MAX_REINDEER    9
// 小精灵数
#define MAX_ELF         3

Semaphore
reindeer_waiting = 0,       // 驯鹿在棚子里等待
reindeer_sleigh_ready = 0,  // 驯鹿的雪橇准备好了
reindeer_deliver_toys = 0,  // 驯鹿送完礼物

elf_can_goto_santa = 3,     // 小精灵可以去找圣诞老人
elf_waiting = 0,            // 小精灵在门口等待
elf_solve_problem = 0,      // 小精灵解决了问题

santa_sleeping = 0;         // 圣诞老人在睡觉

int 
reindeer_back = 0,          // 已经回来的驯鹿数
elf_problem = 0;            // 遇到问题的小精灵数 

Semaphore
reindeer_back_mutex = 1,    // 保证互斥更新已经回来的驯鹿数
elf_problem_mutex = 1;      // 保证互斥更新遇到问题的小精灵数

// 驯鹿
void Reindeer(){
    for(;;){
        semWait(reindeer_back_mutex);
        reindeer_back++;
        if(reindeer_back == MAX_REINDEER){  // 所有驯鹿已经回来，让圣诞老人醒来
            semSignal(reindeer_back_mutex);
            semSignal(santa_sleeping);
        }else{                              // 否则在棚子里等待
            semSignal(reindeer_back_mutex);
            semWait(reindeer_waiting);
        }
        semWait(reindeer_sleigh_ready);     // 等待套上雪橇
        semWait(reindeer_deliver_toys);     // 等待派送礼物
    }
}

// 小精灵
void Elf(){
    for(;;){
        semWait(elf_can_goto_santa);        // 最多3个小精灵去找圣诞老人
        semWait(elf_problem_mutex);
        elf_problem++;
        if(elf_problem == MAX_ELF){         // 已经有3个小精灵遇到问题，让圣诞老人醒来
            semSignal(elf_problem_mutex);
            semSignal(santa_sleeping);
        }else{                              // 否则在门口等待
            semSignal(elf_problem_mutex);
            semWait(elf_waiting);
        }
        semWait(elf_solve_problem);         // 等待解决问题
        semSignal(elf_can_goto_santa);      // 离开
    }
}

// 圣诞老人
void Santa(){
    for(;;){
        semWait(santa_sleeping);                    // 等待被唤醒
        if(reindeer_back == MAX_REINDEER){          // 如果是因为驯鹿都回来了
            semWait(reindeer_back_mutex);
            reindeer_back = 0;
            semSignal(reindeer_back_mutex);
            for(int i = 1; i <= MAX_REINDEER; i++){ // 让棚子里的驯鹿取消等待
                semSignal(reindeer_waiting);
            }
            for(int i = 1; i <= MAX_REINDEER; i++){ // 给驯鹿套上雪橇
                semSignal(reindeer_sleigh_ready);
            }
            for(int i = 1; i <= MAX_REINDEER; i++){ // 骑着驯鹿派送礼物
                semSignal(reindeer_deliver_toys);
            }
        }else{                                      // 否则是因为有3个小精灵遇到了问题
            for(int i = 1; i <= MAX_ELF; i++){      // 让门口的小精灵取消等待
                semSignal(elf_waiting);
            }
            semWait(elf_problem_mutex);
            elf_problem = 0;
            semSignal(elf_problem_mutex);
            for(int i = 1; i <= MAX_ELF; i++){      // 解决小精灵的问题
                semSignal(elf_solve_problem);
            }
        }
    }
}
相关文章