Requirements
Exercise 158：
\1. 掌握并发Chained HashSet实现；
\2. 掌握读写锁(Readers-Writers Lock)使用。
作业提交：
写出代码，并结合代码阐述读写锁的原理及使用。（不需要编程运行）
Answer 1:
什么时候会发生resize(): If any bucket’s elements’ amount exceeds the threshold, double the capacity of the chain.
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
| public class SimpleHashSet{
protected capacity;
protected orig_capacity;
protected LockFreeList[] table;
protected ReadLock[] rlock_table;
protected WriteLock[] wlock_table;
protected ReadLock read_remove_lock, read_contains_lock;
protected WriteLock write_remove_lock, write_contains_lock;
protected int bucket_threshold;
boolean _resize;
public SimpleHashSet(int cap, int threshold){
capacity = cap;
orig_capacity = cap;
table = new LockFreeList[cap];
rlock_table = new ReadLock[cap];
wlock_table = new WriteLock[cap];
read_remove_lock = new ReadLock;
write_remove_lock = new WriteLock;
read_contains_lock = new ReadLock;
write_contains_lock = new WriteLock;
bucket_threshold = threshold;
_resize = false;
for(int i = 0 ; i < cap; i++){
table[i] = new LockFreeList;
rlock_table[i] = new ReadLock;
wlock_table[i] = new WriteLock;
}
}
public boolean add(Object key){
rlock_table[hash%orig_capacity].lock();
int hash = key.hashCode() % capacity;
boolean result = table[hash].add(key);
rlock_table[hash%orig_capacity].unlock();
if(table[hash].length() > bucket_threshold){
if (_resize.CompareAndSet(false, true)){
resize();
}
}
return result;
}
public boolean remove(Object key){
read_remove_lock.lock();
int hash = key.hashCode() % capacity;
boolean result = table[hash].remove(key);
read_remove_lock.unlock();
return result;
}
public boolean contains(Object key){
read_contains_lock.lock();
int hash = key.hashCode() % capacity;
boolean result = table[hash].contains(key);
read_contains_lock.unlock();
return result;
}
public boolean resize(){
write_remove_lock.lock();
write_contains_lock.lock();
int old_cap = capacity;
capacity = capacity * 2;
LockFreeList[old_cap] old_table = table;
table = new LockFreeList[capacity];
for(int i = 0 ; i < capacity ; i++){
table[i] = new LockFreeList;
}
for(int i = 0; i < old_cap; i++){
wlock_table[i % orig_capacity].lock();
AtomicMarkbleReference head = old_table[i];
for(AtomicMarkbleReference i = head->next ; i!= head; i = i->next){
boolean[] mark = {false};
Object key = i.get(mark);
if(mark == false){
int hash = key % capacity;
table[hash].add(key);
}
}
wlock_table[i % orig_capacity].unlock();
}
write_remove_lock.unlock();
write_contains_lock.unlock();
_resize.CompareAndSet(true, false);
}
}
|
解释：
resize()的基本思想是，当任何一个桶的数量超过阈值时，则将哈希表翻倍。
在本类中实现了3个基本方法: add(), remove(), contains()和拓展方法resize()。
在书籍中，resize()方法与add(), remove(), contains()三个方法互斥，但是在本实现中，将resize()与add()并非绝对互斥，即resize()与add()方法是可以并行工作的，且不会导致错误情况的产生，在代码中是如此实现的：
首先，rlock_table, wlock_table分别为，读写锁数组，大小为orig_capacity，即为初始容量，且不会改变。resize()的工作流程为，当拷贝旧表时(old_table)中的某一个元素时，不妨假设为i, 此时会将读写表中的写表进行加锁，即wlock_table[i % capacity].lock()。在加锁的过程中，会将old_table[i]的所有元素根据计算新的哈希值重新加入新的table中。而当add工作时，会首先尝试将rlock_table[key % orig_capacity]加锁，如果加锁成功，则表示wlock_table[ key % orig_capacity] 并没有加锁，此时代表3种情况，第一种，resize()没有进行，此时add()没有任何问题，第二种，resize()正在进行但还没有对于wlock_table[key % orig_capacity]加锁，那么此时包含多种情况(使用例子key = 7, 数组长度为4来说明)： add可能将key=9加入old_table[3]或者加入new_table[7]，当对于加入new_table[7]时情况是正确的，但如果加入old_table[3]时，由于add将rlock_table[3]加了锁，那么resize()则无法对于wlock_table[3]进行加锁，只能等待add在old_table[3]加入完毕才能继续处理old_table[3]，由于resize()还会处理old_table[3]，那么表示add尽管加入了old_table，但是在resize()的帮助下仍然能进入新的正确的位置。第三种，resize()对于wlock_table[key % orig_capacity]已经加完锁，且已经解锁，那么此时表示已经更新了table为new_table，且capacity也已经翻倍，此时add()一定正确。如果add()加锁失败，说明wlock_table对应位置已经被加锁，此时表明已经更新了table为new_table，且capacity也已经翻倍，后续resize()解锁后，add()加入一定是正确的。
对于resize()与remove(), contains()都是使用互斥的读写锁实现的：read_remove_lock ,write_remove_lock, read_contains_lock, write_contains_lock。进入remove()时会将read_remove_lock进行加锁，退出则解锁，进入resize()时会将write_remove_lock加锁，避免后续的remove()操作，退出解锁。对于contains()操作是类似的。
在本实现中，没有对于锁大小进行改变，避免了由于更新锁而导致的一些新的问题出现。
Answer 2
在Answer 1中使用的锁都为读写锁。读写锁的原理为：读写锁使用的是阻塞锁，即当获取锁失败后，会进行休眠等待其他线程进行唤醒。对于获取写锁，当获取失败时，表示已经有写锁或者读锁存在，进入休眠。如果获取成功，表示写锁或者读锁存在，当释放写锁时，会将所有阻塞的唤醒。
对于获取读锁，如果获取失败，表示已经有写锁，进入休眠。如果获取成功，表示不存在写锁，当所有的读锁都解锁时，唤醒所有阻塞的线程。
读写锁，最大的特点就是，读操作是可以并发的，而写则是互斥的(既不允许，读写，写写同时存在)。
在Answer 1中，由于桶中使用的无锁链表，add, contains, remove的并行操作的正确性已经由无锁链表自身已经实现了，因此对于add, contains, remove的使用是任意并行的，因此对于这3个操作分配读锁，而对于resize()来说 ，由于与contains, remove完全互斥，因此分配写锁，与add部分互斥，同样分配写锁。
