PV操作

飞机票问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int A[m];
semaphore s[m];
cobegin
process Pi {
    int Xi;
	while (true) {
        按乘客要求找到A[j];
        P(s[j]);
        Xi = A[j];
        if (Xi > 0) {
            Xi = Xi - 1;
            A[j] = Xi;
            输出一张票
        } else {
            输出“票已售完”
        }
        V(s[j]);
    }
}
coend

哲学家就餐问题

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
// 方法一：每次最多4人进入房间
semaphore fork[5];
for (int i = 0;i < 5; i++) {
    fork = 1;
}
semaphore room = 4;
cobegin
process philosopher_i() {
    while (ture) {
        think();
        P(room);
        P(fork[i]);
        P(fork[(i + 1) % 5]);
        eat();
        V(frok[i]);
        V(fork[(i + 1) % 5]);
        V(room);
    }
}
coend
    
// 方法二：偶数位先左再右；奇数先右再左
semaphore fork[5];
for (int i = 0;i < 5; i++) {
    fork = 1;
}
cobegin
process philosopher_i() {
    while (ture) {
        think();
		if (i % 2 == 0) {
            P(fork[i]);
            P(fork[(i + 1) % 5]);
            eat();
            V(frok[i]);
            V(fork[(i + 1) % 5]);
        } else {
            P(fork[(i + 1) % 5]);
            P(fork[i]);
            eat();
            V(frok[(i + 1) % 5]);
            V(fork[i]);        
        }
    }
}
coend

生产者消费者

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
int buffer[k];
int putptr = 0, getptr = 0;
semaphore sput = k;
semaphore sget = 0;
semaphore m1 = 1, m2 = 1;
cobegin
process producer() {
    while (true) {
        P(sput);
        P(m1);
        buffer[putptr] = product;
        putptr = (putptr + 1) % k;
        V(m1);
        V(sget);
    }
}
process comsumer() {
    while (true) {
        P(sget);
        P(m2);
        product = buffer[getptr];
        getptr = (getptr + 1) % k;
        V(m2);
        V(sput);
    }
}
coend

🍎🍊问题

桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。

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
semaphore sp = 1;
semaphore apple = 0;
semaphore orange = 0;
cobegin
process father() {
    while (true) {
        P(sp);
        V(apple)
    }
}
process mother() {
    while (true) {
        P(sp);
        V(orange);
    }
}
process son() {
    while (true) {
        P(orange);
        V(sp);
    }
}
process daughter() {
    while (true) {
        P(apple);
        V(sp);
    }
}
coend

读写者问题

读者优先

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
semaphore wlock = 1;
semaphore rlock = 1;
int readcount = 0;
cobegin
process reader() {
    while (true) {
        P(rlock);
        readcount++;
        if (readcount == 1) {
            P(wlock);
        }
        V(rlock);
        // reading...
        P(rlock);
        readcount--;
        if (readcount == 0) {
            V(wlock);
        }
        V(rlock);
    }
}
process writer() {
    while (true) {
        P(wlock);
        // writing;
        V(lock);
    }
}
coend

写者优先

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
semaphore rlock = 1;
semaphore wlock = 1;
semaphore S1 = 1, S2 = 1, S3 = 1;
int readercount = 0, writercount;
cobegin 
process reader() {
    P(S3);
    P(rlock);
    P(S1);
   	if (readercount == 0) {
        P(wlock);
    }
    readercount++;
    V(S1);
    V(rlock);
    V(S3);
    // reading
    P(S1);
    readercount--;
   	if (readercount == 0) {
        V(wlock);
    }
    V(S1);    
}
process writer() {
    P(S2);
    if (writercount == 0) {
        P(rlock);
    }
    writercount++;
    V(S2);
    P(wlock);
    // writing...
    V(wlock);
    P(S2);
    writercount--;
    if (writercount == 0) {
        V(rlock);
    }
    V(S2);   
}

读写公平

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
semaphore wlock = 1;
semaphore rlock = 1;
semaphore s = 1;
int readercount = 0;
cobegin
process reader() {
    while (ture) {
        P(s);
        P(rlock);
        if (readercount == 0) {
            P(wlock);
        }
        readercount++;
        V(rlock);
        V(s);
        // reading...
        P(rlock);
        readercount--;
        if (readercount == 0) {
            V(wlock);
        }
        V(rlock);
    }
}
process writer() {
    while (true) {
        P(s);
        P(wlock);
        // writing...
        V(wlock);
        V(s);
    }
}
coend

睡眠理发师问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开使用PV操作求解该问题

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
semaphore barber = 0;
semaphore customer = 0;
semaphore mutex = 1;
int CHAIRS = n;
int waiting = 0;
int customercount = 0;
cobegin
process barber() {
    while (true) {
        P(customer);
        P(mutex);
        waiting--;
        V(barber);
        V(mutex);
        cut_hair();
    }
}
process cuntomer() {
    P(mutex)
    if (waiting < CHAIRS) {
        waiting++;
        V(customer);
        V(mutex);
        P(barber);
        get_haircut();
    } else {
        leave; // 椅子满，离开
        V(mutex);
    }
}
coend

农夫猎人问题

有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农夫向笼中放入羊；动物园等待取笼中的老虎，饭店等待取笼中的羊。请用P、V操作原语写出同步执行的程序

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
semaphore cage = 1;
semaphore tiger = 0;
semaphore sheep = 0;
cobegin
process hunter() {
    while (true) {
        P(cage);
        V(tiger);
    }
}
process farmer() {
    while (true) {
        P(cage);
        V(sheep);
    }
}
process zoo() {
    while (true) {
        P(tiger);
        V(cage);
    }
}
process restaurant() {
    while (true) {
        P(sheep);
        V(cage);
    }
}
coend

银行业务问题

某大型银行办理人民币储蓄业务，由n个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号。请用信号量和P，V操作正确编写储蓄员进程和顾客进程的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
semaphore customer = 0;
semaphore server = 0;
semaphore mutex = 1;
cobegin
process customer() {
    // take a number 
    P(mutex);
    // take a seat
    V(mutex);
    V(customer);
    P(server);
}
process server() {
    P(customer);
    P(mutex);
    // call a number
    V(mutex);
    // serve a customer
    // customer leave
    V(server);
}
coend

缓冲区管理

有n个进程将字符逐个读入到一个容量为80的缓冲区中(n>1)，当缓冲区满后，由输出进程Q负责一次性取走这80个字符。这种过程循环往复，请用信号量和P、V操作写出n个读入进程(P1， P2，…Pn)和输出进程Q能正确工作的动作序列

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
semaphore sget = 0;
semaphore sput = 80;
semaphore mutex = 0;
int buffer[80];
int in = 0;
int count = 0;
cobegin
process input() {
    while (true) {
        // input x
        P(sput);
        P(mutex);
        buffer[i] = x;
        in = (in + 1) % 80;
        count++;
        if (count == 80) {
            V(sput);
            count = 0;
        }
        V(mutex);
    }
}
process output() {
    while (true) {
        P(sget);
        P(mutex);
        for (int i = 0;i < 80; i++) {
            out(buffer[i]);
        }
        in = 0;
        V(mutex);
        for (int i = 0;i < 80; i++) {
            V(sput);
        }
    }
}
coend

售票问题

汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好门应通知司机开车，然后售票员进行售票。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员，汽车当前正在始发站停车上客，试用信号量与P、V操作写出他们的同步算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
semaphore stop = 0;
semaphore run = 0;
cobegin
process driver() {
    while (true) {
		P(run);
        P(run);
        // runing...
        V(stop);
        V(stop);
    }
}
process seller() {
    while (true) {
        // 上乘客
        // 关门
        V(run);
        // sell ticket
        P(stop);
        // 开门
        // 下乘客
    }
}
coend

吸烟者问题

一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试用信号量和P、V操作求解该问题

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
semaphore sput = 1;
semaphore sget[3] = {0, 0, 0};
cobegin
process businessman() {
    while (true) {
        do {
            i = RAND() % 3;
            j = RAND() % 3;
        } while (i == j);
        P(sput);
        // put i on table
        // put j on table
        if ((i == 0 && j == 1) || (i == 1 && j == 0)) V(sget[2]);
        if ((i == 0 && j == 2) || (i == 2 && j == 0)) V(sget[1]);
        if ((i == 2 && j == 1) || (i == 1 && j == 2)) V(sget[0]);
    }
}
process consumer(k) {
    while (true) {
        P(sget[k]);
        // take k from table
        // smoking
        V(sput);
    }
}

独木桥问题

LV1

独木桥问题1：东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后，另一方的车才允许过桥。请用信号量和PV操作写出过独木桥问题的同步算法。

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
semaphore turn = 1;
int count1 = 0, count2 = 0;
semaphore mutex1 = 1, mutex2 = 1;
cobegin
process east() {
    while (true) {
        P(mutex1);
        if (count1 == 0) {
            P(turn);
        }
        count1++;
        V(mutex1);
        // 过桥
        P(mutex1);
        count1--;
        if (count1 == 0) {
            V(turn);
        }
        V(mutex1);
    }
}
process west{
    while (true) {
        P(mutex2);
        if (count2 == 0) {
            P(turn);
        }
        count2++;
        V(mutex2);
        // 过桥
        P(mutex2);
        count2--;
        if (count2 == 0) {
            V(turn);
        }
        V(mutex2);
    }
}
coend

LV2

在独木桥问题1中，限制桥面上最多可以有k辆汽车通过。试用信号量和P，V操作写出过独木桥问题的同步算法

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
semaphore turn = 1;
int count1 = 0, count2 = 0;
semaphore mutex1 = 1, mutex2 = 1;
semaphore bridge = k;
cobegin
process east() {
    while (true) {
        P(mutex1);
        if (count1 == 0) {
            P(turn);
        }
        count1++;
        V(mutex1);
        P(bridge);
        // 过桥
        V(bridge);
        P(mutex1);
        count1--;
        if (count1 == 0) {
            V(turn);
        }
        V(mutex1);
    }
}
process west{
    while (true) {
        P(mutex2);
        if (count2 == 0) {
            P(turn);
        }
        count2++;
        V(mutex2);
        P(bridge);
        // 过桥
        V(bridge);
        P(mutex2);
        count2--;
        if (count2 == 0) {
            V(turn);
        }
        V(mutex2);
    }
}
coend

LV3

在独木桥问题1中，以三辆汽车为一组，要求保证东方和西方以组为单位交替通过汽车。试用信号量和P，V操作写出汽车过独木桥问题的同步算法

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
semaphore S1 = 3, S2 = 0;
semaphore wait = 1;
semaphore mutex1 = 1, semaphore mutex2 = 1;
int countu1 = 0, countd1 = 0;
int countu2 = 0, countd2 = 0;
cobegin
process east() {
    while (true) {
        P(S1);
        P(mutex1);
        countu1++;
        if (countu1 == 1 && countd1 == 0) {
            P(wait);
        }
        V(mutex1);
        // 过桥
        V(S2);
        P(mutex1);
        countu1--, countd1++;
        if (countu1 == 0 && countd1 == 3) {
            V(wait);
            countd1 = 0;
        }
        V(mutex1);
    }
}
process west() {
    while (true) {
        P(S2);
        P(mutex2);
        countu2++;
        if (countu2 == 1 && countd2 == 0) {
            P(wait);
        }
        V(mutex2);
        // 过桥
        V(S1);
        P(mutex2);
        countu2--, countd2++;
        if (countu2 == 0 && countd2 == 3) {
            V(wait);
            countd2 = 0;
        }
        V(mutex2);
    }
}

LV4

在独木桥问题1中，要求各方向的汽车串行过桥，但当另一方提出过桥时，应能阻止对方未上桥的后继车辆，待桥面上的汽车过完桥后，另一方的汽车开始过桥。试用信号量和P、V操作写出过独木桥问题的同步算法。

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
semaphore wait = 1;
semaphore stop = 1;
semaphore mutex1 = 0, mutex2 = 0;
int count1 = 0, count2 = 0;
cobegin
process east() {
    while (true) {
        P(stop);
        P(mutex1);
        count1++;
        if (count1 == 1) {
            P(wait);
        }
        V(mutex1);
        V(stop);
        // 过桥
        P(mutex1);
        count1--;
        if (count1 == 0) {
            V(wait);
        }
        V(mutex);
    }
}
process west() {
    while (true) {
        P(stop);
        P(mutex2);
        count2++;
        if (count2 == 1) {
            P(wait);
        }
        V(mutex2);
        V(stop);
        // 过桥
        P(mutex2);
        count2--;
        if (count2 == 0) {
            V(wait);
        }
        V(mutex2);
    }
}

仓库进货（2019年）

⼀个仓库，最多能放A，B产品各m个。每次⽣产需要A，B产品各⼀个。两组供应商分别⽣产A，B产品。当某个产品的数量⽐另⼀个产品数量多n(n<m)个时，仓库暂时停⽌该产品的进货，集中进货另⼀个产品。

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
semaphore emptyA, emptyB;
emptyA = m, emptyB = m;
semaphore fullA, fullB;
semaphore mutex = 1;
fullA = 0, fullB = 0;
int countA = 0, countB = 0;
process producerA() {
    while (true) {
        P(emptyA);
        P(mutex);
        if (countA - countB >= n) {
            V(emptyA);
        } else {
            V(fullA);
            countA++;
        }
        V(mutex);
    }
}
process producerB() {
    while (true) {
        P(emptyB);
        P(mutex);
        if (countB - countA >= n) {
            V(emptyB);
        } else {
            V(fullB);
            countB++;
        }
        V(mutex);
    }
}
process comsumer() {
    while (true) {
        P(fullA);
        P(fullB);
        P(mutex);
        countA--, countB--;
        P(mutex);
        V(emptyA);
        V(emptyA);
    }
}

管程

Hoare管程的PV操作实现

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
typedef struct InterfaceModule {
    semaphore mutex;
    semaphore next;
    int next_count;
} InterfaceModule;
mutex = 1, next = 0, next_count = 0;

void enter(InterfaceModule &IM) {
    P(IM.mutex);
}

void leave(InterfaceModule &IM) {
    if (IM.next_count > 0) {
        V(IM.next);
    } else {
        V(IM.mutex);
    }
}

void wait(semaphore &x_sem, int &x_count, InterfaceModule &IM) {
    x_count++;
    if (IM.next_count > 0) {
        V(IM.next);
    } else {
        V(IM.mutex);
    }
    P(x_sem);
    x_xount--;
}

void signal(semaphore &x_sem, int &x_count, Interface &IM) {
    if (x_count > 0) {
        IM.next_count++;
        V(x_sem);
        P(IM.next);
        IM.next_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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
TYPE read_write = monitor {
    int rc, wc;
    semaphore R, W;
    R = 0, W = 0;
    int R_count, W_count;
    R_count = W_count = 0;
    InterfaceModlule IM;
    DEFINE start_read, end_read, start_write, end_write;
    USE wait, signal, enter, leave;
    
    void start_read() {
        enter(IM);
        if (wc > 0) {
            wait(R, R_count, IM);
        }
        rc++;
        signal(R, R_count, IM);
        leave(IM);
    }
    void end_read() {
        enter(IM);
        rc--;
        if (rc == 0) {
            signal(W, W_count, IM);
        }
        leave(IM);
    }
    void start_write() {
        enter(IM);
        wc++;
        if (wc > 1 || rc > 0) {
            wait(W, W_count, IM);
        }
        leave(IM);
    }
    void end_write() {
        enter(IM);
        wc--;
        if (wc > 0) {
        	signal(W, W_count, IM);
        } else {
            signal(R, R_count, IM);
        }
        leave(IM);
    }
}
cobegin 
process writer() {
    read_write.start_write();
    // writing...
    read_write.end_write();
}
process reader() {
    read_write.start_read();
    // reading
    read_write.end_read();
}
coend

哲学家就餐问题

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
TYPE ining_philosophers = monitor {
    enum {HUNGRY, EATING, THINKING} state[5];
    semaphore self[5];
    int self_count[5];
    for (int i = 0; i < 5; i++) {
        self[i] = 0;
        self_count[i] = 0;
    }
    InterfaceModule IM;
    DEFINE pickup, putdown;
    USE enter, leave, wait, signal;
    
    void pickup(int i) {
        enter(IM);
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING) {
            wait(self[i], self_count[i], IM);
        }
        leave(IM);
    }
    
    void putdown(int i) {
        enter(IM);
        state[i] = THINKING;
        test(i);
        test((i + 1) % 5);
        leave(IM);
    }
    
    void test(int i) {
        if (state[i] == HUNGRY 
            && state[(i + 4)& 5] != EATING 
            && state[(i + 1) % 5)] != EATING) {
            state[i] = EATING;
            signal(self[i], self_count[i], IM);
        }
    }
}

生产者消费者问题

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
TYPE producer_consumer = monitor {
    int buffer[k];
    int in, out;
    in = out = 0;
    int count = 0;
    semaphore notfull, notempty;
    notfull = 0, notempty = 0;
    int notfull_count = 0, notempty_count = 0;
    InterfaceModule IM;
    DEFINE append, take;
    USE enter, leave, wait, signal;
    
    void append(int p) {
        enter(IM);
        if (count == k) {
            wait(notfull, notfull_count, IM);
        }
        buffer[in] = p;
        in = (in + 1) % k;
        count++;
        signal(notempty, notempty_count, IM);
        leave(IM);
    }
    void take(int &p) {
        enter(IM);
        if (count == 0) {
            wait(notempty, notempty_count, IM);
        }
        p = buffer[out];
        out = (out + 1) % k;
        count--;
        signal(notfull, notfull_count, IM);
        leave(IM);
    }
}

🍎🍊问题

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
TYPE apple_orange = monitor {
    semophore sp, ss, sd;
    sp = 0, ss = 0, sd = 0;
    int sp_count = 0, ss_count = 0, sd_count = 0;
    int apple = 0;
    enum {APPLE, APPLE} FRUIT;
    FRUIT plate;
    bool full;
    DEFINE put, get;
    USE enter, leave, wait, signal;
    
    void put(FRUIT fruit) {
        enter(IM);
        if (full) {
            wait(sp, sp_count, IM);
        }
        plate = fruit;
        full = true;
        if (fruit == APPLE) {
            signal(sd, sd_count, IM);
        } else {
            signal(ss, ss_count, IM);
        }
        leave(IM);
    }
    void get(FRUIT fruit, FRUIT &x) {
        enter(IM);
        if (!full || fruit != plate) {
            if (fruit == ORANGE) {
                wait(ss, ss_count, IM);
            } else {
                wait(sd, sd_count, IM);
            }
        }
        x = plate;
        full = false;
        signal(sp, sp_coumt, IM);
        leave(IM);
    }   
}