todc_mem/
snapshot.rs

1//! `N`-process snapshot objects.
2//!
3//! This module contains implementations of `N`-process snapshot objects. All
4//! implementations are abstracted over a generic type `R: Register`, which is the
5//! type of primitive used to store data. Many properties, such as wait-freedom and
6//! linearizability, depend on the properties of the underlying register `R`.
7//!
8//! In general, if `R` is wait-free and linearizable, then all snapshot implementations
9//! in this module will be as well. For more details on the differences between
10//! register implementations, see [`AtomicRegister`](crate::register::AtomicRegister).
11//!
12//! # Restrictions on Atomic Snapshot Values
13//!
14//! Due to restrictions on the number of bits of atomic shared-memory that is
15//! available on most hardware (a maximum of 64), the [`BoundedAtomicSnapshot`]
16//! and [`UnboundedAtomicSnapshot`] objects may only store values of type [`u8`].
17//! Similarily, the number `N` of components available in these snapshots is
18//! limited to `6` and `5`, respectively.
19//!
20//! # Examples
21//!
22//! Obtain a consistent view of progress being made by a set of threads.
23//!
24//! ```
25//! # use std::sync::atomic::{AtomicU8, Ordering};
26//! use std::sync::Arc;
27//! use std::thread;
28//! use todc_mem::snapshot::{Snapshot, BoundedAtomicSnapshot};
29//!
30//! const N: usize = 6;
31//!
32//! let snapshot: Arc<BoundedAtomicSnapshot<N>> = Arc::new(BoundedAtomicSnapshot::new());
33//!
34//! # static hidden_state: [AtomicU8; N] = [
35//! #   AtomicU8::new(0), AtomicU8::new(0), AtomicU8::new(0),
36//! #   AtomicU8::new(0), AtomicU8::new(0), AtomicU8::new(0)
37//! # ];
38//! fn do_work(i: usize) -> Option<u8> {
39//!     // -- snipped --
40//! #    let percent = hidden_state[i].load(Ordering::Acquire);
41//! #    if percent < 100 {
42//! #        hidden_state[i].store(percent + 1, Ordering::Release);
43//! #        Some(percent)
44//! #    } else {
45//! #        None
46//! #    }
47//! }
48//!
49//! // Each worker thread does some work and periodically updates
50//! // its component of the snapshot with the amount of progress
51//! // it has made so far.
52//! let mut handles = Vec::new();
53//! for i in 1..N {
54//!     let mut snapshot = snapshot.clone();
55//!     handles.push(thread::spawn(move || {
56//!         while let Some(percent_complete) = do_work(i) {
57//!             snapshot.update(i, percent_complete);
58//!         }        
59//!     }));
60//! }
61//!
62//! // The main thread waits until all workers have completed
63//! // at least half of their work, before printing a message.
64//! snapshot.update(0, 100);
65//! loop {
66//!     let view = snapshot.scan(0);
67//!     if view.iter().all(|&p| p >= 50) {
68//!         println!("We're at-least half-way done!");
69//!         break;
70//!     }
71//! }
72//!
73//! for thread in handles {
74//!     thread.join().unwrap();
75//! }
76//! ```
77pub mod aad_plus_93;
78pub mod ar_98;
79pub mod mutex;
80
81pub use self::aad_plus_93::{
82    BoundedAtomicSnapshot, BoundedMutexSnapshot, UnboundedAtomicSnapshot, UnboundedMutexSnapshot,
83};
84pub use self::ar_98::LatticeMutexSnapshot;
85
86/// An ID for a process (or thread).
87pub type ProcessId = usize;
88
89/// An `N`-component snapshot object.
90pub trait Snapshot<const N: usize> {
91    type Value: Clone;
92
93    /// Creates a snapshot object.
94    fn new() -> Self;
95
96    /// Returns an array containing the value of each component in the object.
97    fn scan(&self, i: ProcessId) -> [Self::Value; N];
98
99    /// Sets contents of the _i^{th}_ component to the specified value.
100    fn update(&self, i: ProcessId, value: Self::Value);
101}
todc_mem/snapshot.rs

todc_mem/
snapshot.rs
