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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
range-lock - Multithread range lock for Vec
===========================================
`https://bues.ch/ <https://bues.ch/>`_
Provides multi-threaded access to a single Vec<T> instance. Any thread can atomically request access to a slice of the Vec. Such access is granted, if no other thread is simultaneously holding the right to access an overlapping slice.
Usage
=====
Add this to your Cargo.toml:
.. code:: toml
[dependencies]
range-lock = "0.1"
RangeLock example usage
-----------------------
General purpose RangeLock:
.. code:: rust
extern crate range_lock;
use range_lock::RangeLock;
use std::sync::{Arc, Barrier};
use std::thread;
// The data that will simultaneously be accessed from the threads.
let data = vec![10, 11, 12, 13];
// Embed the data in a RangeLock
// and clone atomic references to it for the threads.
let data_lock0 = Arc::new(RangeLock::new(data));
let data_lock1 = Arc::clone(&data_lock0);
let data_lock2 = Arc::clone(&data_lock0);
// Thread barrier, only for demonstration purposes.
let barrier0 = Arc::new(Barrier::new(2));
let barrier1 = Arc::clone(&barrier0);
// Spawn first thread.
let thread0 = thread::spawn(move || {
{
let mut guard = data_lock0.try_lock(0..2).expect("T0: Failed to lock 0..2");
guard[0] = 100; // Write to data[0]
}
barrier0.wait(); // Synchronize with second thread.
{
let guard = data_lock0.try_lock(2..4).expect("T0: Failed to lock 2..4");
assert_eq!(guard[0], 200); // Read from data[2]
}
});
// Spawn second thread.
let thread1 = thread::spawn(move || {
{
let mut guard = data_lock1.try_lock(2..4).expect("T1: Failed to lock 2..4");
guard[0] = 200; // Write to data[2]
}
barrier1.wait(); // Synchronize with first thread.
{
let guard = data_lock1.try_lock(0..2).expect("T1: Failed to lock 0..2");
assert_eq!(guard[0], 100); // Read from data[0]
}
});
// Wait for both threads to finish and check result.
thread0.join().expect("Thread 0 failed");
thread1.join().expect("Thread 1 failed");
// Unwrap the data from the lock.
let data = Arc::try_unwrap(data_lock2).expect("Arc unwrap failed").into_inner();
// Check the data that has been modified by the threads.
assert_eq!(data, vec![100, 11, 200, 13]);
RepRangeLock example usage
--------------------------
The RepRangeLock is a restricted range lock, that provides interleaved patterns of slices to the threads.
Locking a RepRangeLock is more lightweight than locking a RangeLock.
Please see the example below.
.. code:: rust
use range_lock::RepRangeLock;
use std::sync::Arc;
use std::thread;
let data = vec![1, 2, 3, 4, 5, 6, // <- cycle 0
7, 8, 9, 10, 11, 12]; // <- cycle 1
// ^--^ ^---^ ^----^
// | | |
// offset-0 offset-1 offset-2
let lock = Arc::new(RepRangeLock::new(data,
2, // slice_len: Each slice has 2 elements.
3)); // cycle_len: Each cycle has 3 slices (offsets).
let lock0 = Arc::clone(&lock);
let lock1 = Arc::clone(&lock);
let lock2 = Arc::clone(&lock);
let thread0 = thread::spawn(move || {
// Lock slice offset 0:
let mut guard = lock0.try_lock(0).expect("Failed to lock offset.");
// Read:
assert_eq!(guard[0][0], 1); // Cycle 0, Slice element 0
assert_eq!(guard[0][1], 2); // Cycle 0, Slice element 1
// let _ = guard[0][2]; // Would panic. Slice len is only 2.
assert_eq!(guard[1][0], 7); // Cycle 1, Slice element 0
assert_eq!(guard[1][1], 8); // Cycle 1, Slice element 1
// let _ = guard[2][0]; // Would panic: The data vec is only 2 repeat cycles long.
// Write:
guard[0][0] = 10; // Cycle 0, Slice element 0
guard[0][1] = 20; // Cycle 0, Slice element 1
// guard[0][2] = 42; // Would panic: Slice len is only 2.
guard[1][0] = 30; // Cycle 1, Slice element 0
guard[1][1] = 40; // Cycle 1, Slice element 1
// guard[2][0] = 42; // Would panic: The data vec is only 2 repeat cycles long.
});
let thread1 = thread::spawn(move || {
// Lock slice offset 1:
let mut guard = lock1.try_lock(1).expect("Failed to lock offset.");
guard[0][0] = 100; // Cycle 0, Slice element 0
guard[0][1] = 200; // Cycle 0, Slice element 1
guard[1][0] = 300; // Cycle 1, Slice element 0
guard[1][1] = 400; // Cycle 1, Slice element 1
});
let thread2 = thread::spawn(move || {
// Lock slice offset 2:
let mut guard = lock2.try_lock(2).expect("Failed to lock offset.");
guard[0][0] = 1000; // Cycle 0, Slice element 0
guard[0][1] = 2000; // Cycle 0, Slice element 1
guard[1][0] = 3000; // Cycle 1, Slice element 0
guard[1][1] = 4000; // Cycle 1, Slice element 1
});
thread0.join();
thread1.join();
thread2.join();
// Get the data that has been modified by the threads.
let data = Arc::try_unwrap(lock).expect("Thread is still using data.").into_inner();
assert_eq!(data,
vec![10, 20, 100, 200, 1000, 2000,
30, 40, 300, 400, 3000, 4000]);
TODOs for future releases
=========================
The following new features might be candidates for future releases:
* Optimize the range overlap search algorithm.
* Sleeping lock, in case of lock contention.
* Add support for arrays.
License
=======
Copyright (c) 2021 Michael Buesch <m@bues.ch>
Licensed under the Apache License version 2.0 or the MIT license, at your option.
|
