Last active
August 29, 2016 07:40
-
-
Save critiqjo/26e9f4ef4c22ab4eaae97870d6af272e to your computer and use it in GitHub Desktop.
Memory Ordering
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::cell::UnsafeCell; | |
use std::sync::atomic::{AtomicUsize, Ordering}; | |
use std::sync::{Arc, Barrier}; | |
use std::thread; | |
struct UsizePair { | |
atom: AtomicUsize, | |
norm: UnsafeCell<usize>, | |
} | |
static NTHREADS: usize = 8; | |
static NITERS: usize = 1000000; | |
fn main() { | |
let upair = Arc::new(UsizePair::new(0)); | |
// Barrier is a counter-like synchronization structure (not to be confused | |
// with a memory barrier). It blocks on a `wait` call until a fixed number | |
// of `wait` calls are made from various threads (like waiting for all | |
// players to get to the starting line before firing the starter pistol). | |
let barrier = Arc::new(Barrier::new(NTHREADS + 1)); | |
let mut children = vec![]; | |
for _ in 0..NTHREADS { | |
let upair = upair.clone(); | |
let barrier = barrier.clone(); | |
children.push(thread::spawn(move || { | |
barrier.wait(); | |
let mut v = 0; | |
while v < NITERS - 1 { | |
// Read both members `atom` and `norm`, and check whether `atom` | |
// contains a newer value than `norm`. See `UsizePair` impl for | |
// details. | |
let (atom, norm) = upair.get(); | |
if atom > norm { | |
// If `Acquire`-`Release` ordering is used in `get` and | |
// `set`, then this statement will never be reached. | |
println!("Reordered! {} > {}", atom, norm); | |
} | |
v = atom; | |
} | |
})); | |
} | |
barrier.wait(); | |
for v in 1..NITERS { | |
// Update both members `atom` and `norm` to value `v`. See the impl for | |
// details. | |
upair.set(v); | |
} | |
for child in children { | |
let _ = child.join(); | |
} | |
} | |
impl UsizePair { | |
pub fn new(v: usize) -> UsizePair { | |
UsizePair { | |
atom: AtomicUsize::new(v), | |
norm: UnsafeCell::new(v), | |
} | |
} | |
pub fn get(&self) -> (usize, usize) { | |
let atom = self.atom.load(Ordering::Relaxed); //Ordering::Acquire | |
// If the above load operation is performed with `Acquire` ordering, | |
// then all writes before the corresponding `Release` store is | |
// guaranteed to be visible below. | |
let norm = unsafe { *self.norm.get() }; | |
(atom, norm) | |
} | |
pub fn set(&self, v: usize) { | |
unsafe { *self.norm.get() = v }; | |
// If the below store operation is performed with `Release` ordering, | |
// then the write to `norm` above is guaranteed to be visible to all | |
// threads that "loads `atom` with `Acquire` ordering and sees the same | |
// value that was stored below". However, no guarantees are provided as | |
// to when other readers will witness the below store, and consequently | |
// the above write. On the other hand, there is also no guarantee that | |
// these two values will be in sync for readers. Even if another thread | |
// sees the same value that was stored below, it may actually see a | |
// "later" value in `norm` than what was written above. That is, there | |
// is no limit on the future visibility. | |
self.atom.store(v, Ordering::Relaxed); //Ordering::Release | |
} | |
} | |
// UnsafeCell is not thread-safe. So manually mark it as `Send` and `Sync`. | |
unsafe impl Send for UsizePair {} | |
unsafe impl Sync for UsizePair {} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment