Java中monitor的同步设计

CS4231 – 第二次作业中Java中monitor的一些笔记

这学期跑到NUS来一不小心就选了一门难度极大的课,这第二次的作业做了半天只做对了一道题。。看了答案之后,仿佛懂了些什么,在这里大致记录下,到时候期中期末考试以便能够救自己一命。

对于monitor的设计的基本思路

Java中的每一个对象都是一个 monitor,每一个monitor都拥有着两个队列。其中一个队列是由操作系统或者说CPU进行上下文切换时使用的,另一个队列就是我们将会使用到的Wait-Notify对中使用的队列。这个队列大致来说是一个BlockingQueue,也就是会将当前的thread放入到这个队列中进行阻塞,直到notify唤醒为止。下面是设计的时候的大致思路。

  1. 首先需要确定当前的monitor,后面两个条件中的某一个满足可以考虑(个人理解):当前的synchronized区里面monitor是你想要保证的一次只能有一个线程访问的shared variable或者/并且该对象将会成为一个被阻塞的对象;

  2. 设计的时候一定要有代入感的把每一个线程操作想清楚,每一步都应该有一个比较现实、能够理解的意义。

SleepingBarber问题

题目描述

The following problem is known as the sleeping barber problem. There is one thread called barber. The barber cuts the hair of any waiting customer. If there is no customer, the barber goes to sleep. There are multiple customer threads. A customer waits for the barber if there is any chair left in the barber room. Otherwise, the customer leaves immediately. If there is a chair available, then the customer occupies it. If the barber is sleeping, then the customer wakes the barber. Assume that there are n chairs in the barber shop.

简单的来说,就是说有个理发店里有n个理发师,m个椅子。当没有顾客出现的时候,理发师们就回去睡觉,顾客来的时候,会先去叫醒理发师,然后理发。如果发现所有理发师都在理发,就会在椅子上等待,如果所有椅子都没了,这个顾客就会离开。

思路

为了实现整个模拟过程,我们很显然需要一个queue作为等待队列,以及其他一大堆约束条件。整个模拟过程如下面所示:

  • Barber:一旦没有顾客排队,就进入睡眠。有顾客出现就去给顾客理发,然后循环。

  • Customer: 首先检查是否有椅子,没有就离开。如果有,先进入队列进行排队,直到理完发被Barber提醒之后离开。

代码及具体分析:

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
public void barber() {
try {
while (true) {
// 此时选用customerQueue作为monitor的理由在于:
// 1.我不希望有人和我同时操作queue;
// 2.顾客能够通过queue来唤醒理发师(某种意义上,理发师是被这个队列管理的)
synchronized (customerQueue) {
// 如果只有一个理发师,下面可以用if而不是while
// 因为多个理发师的话,可能wait醒来之后又已经空了
while (customerQueue.isEmpty()) {
customerQueue.wait();
}
// 将一个顾客带走进行理发
customer = customerQueue.remove();
}
System.out.println("Barber " + num + " is doing barber");
// 此时选用customer作为monitor的理由在于:
// 1. 这个customer可能还没能进入检测头发是否剪好的区域,我不希望出现冲突;
// 2. 这个customer将会wait,我必须将其唤醒
synchronized (customer) {
customer.isDone = true;
customer.notifyAll();
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public void hairCut() {
// 此时选用chairsFree作为monitor的理由在于:
// 我不希望有人和我同时操作chairsFree。
synchronized (chairsFree) {
if (chairsFree == 0) {
return;
}
chairsFree--;
}
// 这个地方和之前的wait相互对照
// 通过queue来对barber进行管理,并且将自己加入队列,这样可以在另一个
// 线程获取并且进行notify操作。
synchronized (customerQueue) {
customerQueue.add(this);
customerQueue.notifyAll();
}
System.out.println("Customer " + num + " is being haircut");
// 对自己进行wait、notify操作
synchronized (this) {
try {
// 可能会出现某些customer动作很慢,barber已经结束了操作之后还未能进行,所以就要对isDone进行判断,否则将会进入饥饿
if (!this.isDone) {
this.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
synchronized (chairsFree) {
chairsFree++;
}
}

一些需要注意的:

  • 这个isDone作为Customer内部的一个成员,其意义在于防止可能会出现的死锁。因为如果不是一个内部成员的话,可能将会使用其他的某个东西来进行操作,然后那个东西可能会因为操作域的锁限制,导致无法touch到。

  • Barber是被queue管理的,而不是Barber在管理这个queue。

  • 这个queue和其中的元素进行同步,似乎是个很好的trick

ReaderWriter问题

题目描述

Give a starvation-free solution to the reader-writer problem.

直接给代码算了,懒得分析了,和上面差不多

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
mport java.util.ArrayDeque;
import java.util.Queue;
/**
* Created by tangyifeng on 2018/1/31.
* Email: yifengtang_hust@outlook.com
*/
public class NoStarvationRW_Ans {
private Queue<Object> queue = new ArrayDeque<>();
private int readerNum = 0;
private int writerNum = 0;
private class Reader extends Thread {
private boolean okToGo = false;
private int num;
private Reader(int num) {
this.num = num;
}
@Override
public void run() {
try {
synchronized (queue) {
if (writerNum > 0) {
this.okToGo = false;
queue.add(this);
} else {
this.okToGo = true;
readerNum++;
}
}
synchronized (this) {
if (!this.okToGo) {
this.wait();
}
}
System.out.println("reader " + num + " is reading.");
synchronized (queue) {
readerNum--;
while (!queue.isEmpty()) {
Object one = queue.remove();
if (one instanceof Writer) {
((Writer)one).okToGo = true;
writerNum++;
one.notify();
break;
} else {
((Reader)one).okToGo = true;
readerNum++;
one.notify();
}
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private class Writer extends Thread {
private int num;
private boolean okToGo;
private Writer(int num) {
this.num = num;
}
@Override
public void run() {
try {
synchronized (queue) {
if (readerNum > 0 || writerNum > 0) {
this.okToGo = false;
queue.add(this);
} else {
this.okToGo = true;
writerNum++;
}
}
synchronized (this) {
if (!this.okToGo) {
this.wait();
}
}
System.out.println("writer " + num + " is writing.");
synchronized (queue) {
writerNum--;
while (!queue.isEmpty()) {
Object one = queue.remove();
if (one instanceof Writer) {
((Writer)one).okToGo = true;
writerNum++;
one.notify();
break;
} else {
((Reader)one).okToGo = true;
readerNum++;
one.notify();
}
}
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
NoStarvationRW_Ans noStarvationRW = new NoStarvationRW_Ans();
for (int i = 0; i < 10; i++) {
noStarvationRW.new Writer(i).start();
for (int j = 0; j < 5; j++) {
noStarvationRW.new Reader(i * 3 + j).start();
}
}
}
}

另一种可能的实现

实际上,如果不考虑先来先获取的情况的话,应该有一种更简单的实现,我也不知道这种简单的实现对不对。。不过实现的很不直观。这种实现的思路是,每一个reader、writer在进入的时候需要等待两次,这两次等待第一次将会阻止在有人等待的时候继续加入到运行队列中,第二次就是常规的等待。

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
92
93
94
95
96
97
98
99
import java.util.Random;
/**
* Created by tangyifeng on 2018/1/26.
* Email: yifengtang_hust@outlook.com
*/
public class NoStarvationRW {
private final Object lock = new Object();
private boolean anyWait = false;
private int numReader = 0;
private int numWriter = 0;
private Random random = new Random();
private class Writer extends Thread {
private int num;
private Writer(int num) {
this.num = num;
}
@Override
public void run() {
try {
synchronized (lock) {
while (anyWait) {
lock.wait();
}
while (numWriter > 0 || numReader > 0) {
anyWait = true;
lock.wait();
}
anyWait = false;
numWriter++;
}
System.out.println(num + " writing...");
Thread.sleep(Math.abs(random.nextLong() % 1000));
System.out.println(num + " writing done.");
synchronized (lock) {
lock.notifyAll();
numWriter--;
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private class Reader extends Thread {
private int num;
private Reader(int num) {
this.num = num;
}
@Override
public void run() {
try {
synchronized (lock) {
while (anyWait) {
lock.wait();
}
while (numWriter > 0) {
anyWait = true;
lock.wait();
}
anyWait = false;
numReader++;
}
System.out.println(num + " Reading...");
Thread.sleep(Math.abs(random.nextLong() % 1000));
System.out.println(num + " Reading done.");
synchronized (lock) {
lock.notifyAll();
numReader--;
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public static void main(String[] args) {
NoStarvationRW noStarvationRW = new NoStarvationRW();
for (int i = 0; i < 10; i++) {
noStarvationRW.new Writer(i).start();
for (int j = 0; j < 5; j++) {
noStarvationRW.new Reader(i * 3 + j).start();
}
}
}
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2018 Alex's Blog All Rights Reserved.

Yifeng Tang hält Urheberrechtsansprüche.