-
Notifications
You must be signed in to change notification settings - Fork 1
/
SimpleMRLockImplementation.cpp
109 lines (90 loc) · 2.54 KB
/
SimpleMRLockImplementation.cpp
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
#include <iostream>
#include <cstdint>
#include <bitset>
#include <atomic>
#include <string>
#include <list>
using namespace std;
struct cell{
atomic<uint32_t> seq;
bitset<10> bits;
};
struct MRLock{
cell* buffer;
uint32_t mask;
atomic<uint32_t> head;
atomic<uint32_t> tail;
};
//input l: reference to the lock
//input size: suggested buffer size
void init(MRLock& l, uint32_t siz){
l.buffer = new cell[siz];
l.mask = siz - 1;
l.head.store(0, memory_order_relaxed);
l.tail.store(0, memory_order_relaxed);
//initialize bits to all 1s
for(uint32_t i =0; i<siz; i++){
l.buffer[i].bits.set();
l.buffer[i].seq.store(i, memory_order_relaxed);
}
}
void uninit(MRLock& l){
delete[] l.buffer;
}
uint32_t lock(MRLock& l, bitset<10> r){
cell* c;
uint32_t pos;
for(;;){
pos = l.tail.load(memory_order_relaxed);
c = &l.buffer[pos & l.mask];
uint32_t seq = c->seq.load(memory_order_relaxed);
int32_t dif = (int32_t)seq - (int32_t)pos;
if(dif == 0){
if(l.tail.compare_exchange_weak(pos, pos + 1, memory_order_relaxed))
break;
}
}
c->bits = r;
c->seq.store(pos + 1, memory_order_release);
uint32_t spin = l.head;
while (spin != pos){
if (pos - l.buffer[spin & l.mask].seq > l.mask || !(l.buffer[spin & l.mask].bits & r).to_ulong())
spin++;
}
return pos;
}
//input l: reference to MRLock
//input h: the lock handle
void unlock(MRLock& l, uint32_t h){
l.buffer[h & l.mask].bits.reset();
uint32_t pos = l.head.load(memory_order_relaxed);
while (l.buffer[pos & l.mask].bits == 0){
cell* c = &l.buffer[pos & l.mask];
uint32_t seq = c->seq.load(memory_order_acquire);
int32_t dif = (int32_t) seq - (int32_t)(pos + 1);
if (dif == 0){
if (l.head.compare_exchange_weak(pos, pos + 1, memory_order_relaxed)){
c->bits.set();
c->seq.store(pos + l.mask + 1, memory_order_release);
}
}
pos = l.head.load(memory_order_relaxed);
}
}
//driver code
int main()
{
//Create a MRLock object
MRLock mrlock;
//Initialize it with 65000 queue length
init(mrlock, 10000);
// Create a bitset object denoting the resources needed
string r_bitstring = "0100000000";
bitset<10> r_bitset(r_bitstring);
//Acquire the lock
uint32_t handle = lock(mrlock, r_bitset);
/*Carry out operations*/
//Release the lock
unlock(mrlock, handle);
return(0);
}