rust / expert
Snippet
Implementierung sperrenfreier konkurrierender Stapeleinfügung mittels atomarem Compare-Exchange
Sperrenfreie Strukturen basieren auf atomaren CAS-Operationen (Compare-And-Swap). Dieser konkurrierende Stapelspeicher verwendet compare_exchange_weak in einer Schleife, um den Head-Pointer sperrenfrei zu aktualisieren.
snippet.rs
rust
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
use std::sync::atomic::{AtomicPtr, Ordering};use std::ptr;struct Node<T> {data: T,next: *mut Node<T>,}pub struct LockFreeStack<T> {head: AtomicPtr<Node<T>>,}impl<T> LockFreeStack<T> {pub fn new() -> Self {Self { head: AtomicPtr::new(ptr::null_mut()) }}pub fn push(&self, data: T) {let new_node = Box::into_raw(Box::new(Node {data,next: ptr::null_mut(),}));let mut current = self.head.load(Ordering::Relaxed);loop {unsafe { (*new_node).next = current; }match self.head.compare_exchange_weak(current,new_node,Ordering::Release,Ordering::Relaxed,) {Ok(_) => break,Err(actual) => current = actual,}}}}
Erklärung
1
Box::into_raw(Box::new(...))
Konvertiert eine sichere Box in einen Rohzeiger, um die automatische Bereinigung zu verhindern.
2
self.head.compare_exchange_weak(current, new_node, Ordering::Release, Ordering::Relaxed)
Aktualisiert head atomar, falls es mit current übereinstimmt, und nutzt Release-Ordering für die Sichtbarkeit.
3
Err(actual) => current = actual,
Aktualisiert den aktuellen Head-Pointer mit dem tatsächlich zurückgegebenen Wert bei CAS-Fehlschlag für einen neuen Versuch.