由水果问题引出的一系列思考

发表于 更新于

题目

有一个盘子，可以放5个水果（苹果or桔子）。父亲每次向盘子随机放入一个水果（苹果or桔子），父亲放入水果的次数不少于11次。儿子只吃桔子，女儿只吃苹果。请编程使用信号量机制模拟解决此进程同步问题。打印信息包括盘子的情况、调度的情况以及父亲、儿子或者女儿执行的操作。

思考

这是由经典生产消费者问题引申出的一道题，我使用的是Java并发的Semaphore来实现的。其中我使用到了如下几个信号量：

1
2
3
4
Semaphore mutex = new Semaphore(1);		// 盘子互斥量
Semaphore empty = new Semaphore(5);		// 容量同步信号量
Semaphore orange = new Semaphore(0);	// 橘子同步信号量
Semaphore apple = new Semaphore(0);		// 苹果同步信号量

实验结果也是正确的：

但是我也产生了以下疑问：盘子互斥量（mutex）是否是必须的？

Talk is cheap, show me the code

当我去除了mutex信号量后问题很快就出现了：

可以看到我们的输出竟然乱序了！这个现象很有意思，先看我们父亲的源代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
empty.acquire();
//mutex.acquire();
if (random.nextBoolean()) {
	plate.putApple();
	System.out.println("father put an apple");
	System.out.println("\t" + plate);
	apple.release();
} else {
	plate.putOrange();
	System.out.println("father put an orange");
	System.out.println("\t" + plate);
	orange.release();
}
//mutex.release();

初看可能会感到疑惑，V(apple/orange) <=> apple/orange.release()的操作明明是在println之后做的，为什么还会出现输出不规则的情况？事实上输出是没问题的，原因在于当父亲前一次放置了水果后触发同步信号，引起女儿/儿子的eat行为，结果在父亲后一次放置水果时发生了和女儿/儿子eat行为的并行情况！可以参考如下图所示：

现在输出问题已经明了了，我们着眼于并发安全性，这样会导致程序执行的结果出错吗？我们还是先用实验来说明问题，在前面的实验中，我们限制了父亲放置水果的总量为12：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class People {
    private Runnable thing;
    private int times;
	// ...
    public void start() {
        new Thread(() -> {
            int times = this.times;
            while (times == -1 || times-- > 0) {	// 限制了执行次数
                thing.run();
            }
        }).start();
    }
}

我们将times设置为-1，这将时程序无限执行下去，同时我们也加入了错误检查代码，一旦执行出错，结束程序：

1
2
3
4
5
6
7
8
9
private void checkCapacity() {
	if (apple + orange > capacity) {
		System.err.println("error: the num of fruits is greater than capacity!");
		System.exit(-1);
	} else if (apple < 0 || orange < 0) {
		System.err.println("error: the num of fruits should not be minus!");
		System.exit(-2);
	}
}

其实这样做不是十分严谨的，因为万一我们执行了几分钟，程序还未出错，我们并不能百分比确定这样的程序是正确的，但是十分幸运，我们很快就得到了验证：

可以看到我们的水果竟然超过了盘子的容量！

接下来，我们在理论部分验证一下程序的正确性，由之前的输出错误分析部分我们可以知道，去掉盘子的mutex互斥量后，父亲在放置水果和孩子在拿水果的过程是可以同时执行的，也就是说他们同时可以改变orange或者apple的数量，如果种类不同还可以接受，但是一旦对相同类别的水果进行加减操作，则必然会造成并发安全问题！这也就是我们常说的临界区代码：

1
2
3
4
5
6
7
8
public void putOrange() {
	orange++;
	checkCapacity();

public void getOrange() {
	orange--;
	checkCapacity();
}

源代码

main.java

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
import java.util.Random;
import java.util.concurrent.Semaphore;

public class Main {


    public static void main(String[] args) {
        Random random = new Random();
        Semaphore mutex = new Semaphore(1);
        Semaphore empty = new Semaphore(5);
        Semaphore orange = new Semaphore(0);
        Semaphore apple = new Semaphore(0);

        Plate plate = new Plate(5);
        People father = new People(() -> {
            try {
                empty.acquire();
                mutex.acquire();
                if (random.nextBoolean()) {
                    plate.putApple();
                    System.out.println("father put an apple");
                    System.out.println("\t" + plate);
                    apple.release();
                } else {
                    plate.putOrange();
                    System.out.println("father put an orange");
                    System.out.println("\t" + plate);
                    orange.release();
                }
                mutex.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, -1);

        People son = new People(() -> {
            try {
                orange.acquire();
                mutex.acquire();
                plate.getOrange();
                System.out.println("son eat an orange");
                System.out.println("\t" + plate);
                mutex.release();
                empty.release();
            }catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, -1);

        People daughter = new People(() -> {
            try {
                apple.acquire();
                mutex.acquire();
                plate.getApple();
                System.out.println("daughter eat an apple");
                System.out.println("\t" + plate);
                mutex.release();
                empty.release();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }, -1);

        son.start();
        daughter.start();
        father.start();
    }

}

People.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class People {
    private Runnable thing;
    private int times;

    public People(Runnable thing, int times) {
        this.thing = thing;
        this.times = times;
    }

    public void start() {
        new Thread(() -> {
            int times = this.times;
            while (times == -1 || times-- > 0) {
                thing.run();
            }
        }).start();
    }
}

Plate.java

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
public class Plate {
    public final int capacity;
    public int apple;
    public int orange;

    public Plate(int capacity) {
        this.capacity = capacity;
    }

    private void checkCapacity() {
        if (apple + orange > capacity) {
            System.err.println("error: the num of fruits is greater than capacity!");
            System.exit(-1);
        } else if (apple < 0 || orange < 0) {
            System.err.println("error: the num of fruits should not be minus!");
            System.exit(-2);
        }
    }

    public void putApple() {
        apple++;
        checkCapacity();
    }

    public void putOrange() {
        orange++;
        checkCapacity();
    }

    public void getOrange() {
        orange--;
        checkCapacity();
    }

    public void getApple() {
        apple--;
        checkCapacity();
    }

    @Override
    public String toString() {
        return "Plate{" +
                "apple=" + apple +
                ", orange=" + orange +
                '}';
    }
}