dekker/
lib.rs

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
use std::ops::{Deref, DerefMut};

#[cfg(test)]
mod tests;

/// Provides mutually exclusive access to a shared object using Dekker's algorithm.
pub struct Dekker<T> {
    shared: T,
    turn: usize,
    wants_to_enter: [bool; 2],
    processes: u8,
}

impl<T> Dekker<T> {
    /// Allocates a new shared object and returns two processes to access it.
    pub fn new(shared: T) -> (Process<T>, Process<T>) {
        let dekker = Dekker {
            shared,
            turn: 0,
            wants_to_enter: [false; 2],
            processes: 2,
        };

        let dekker = Box::leak(Box::new(dekker));

        (Process::new(0, dekker), Process::new(1, dekker))
    }
}

/// Used to access the critical section from one of two concurrent processes.
pub struct Process<T> {
    index: usize,
    owner: *mut Dekker<T>,
    locked: bool,
}

unsafe impl<T> Send for Process<T> {}

impl<T> Process<T> {
    fn new(index: usize, owner: *mut Dekker<T>) -> Process<T> {
        Process {
            index,
            owner,
            locked: false,
        }
    }

    /// Acquire the lock for the critical section.
    pub fn lock(&mut self) -> Guard<T> {
        unsafe {
            (*self.owner).wants_to_enter[self.index] = true;
            while (*self.owner).wants_to_enter[1 - self.index] {
                if (*self.owner).turn != self.index {
                    (*self.owner).wants_to_enter[self.index] = false;
                    while (*self.owner).turn != self.index {}
                    (*self.owner).wants_to_enter[self.index] = true;
                }
            }
        }

        self.locked = true;

        Guard::new(self as *mut Process<T>)
    }
}

impl<T> Drop for Process<T> {
    // We can deallocate if both processes are finished.
    fn drop(&mut self) {
        let guard = self.lock();

        unsafe {
            (*self.owner).processes -= 1;
            if (*self.owner).processes == 0 {
                let dekker = Box::from_raw(self.owner);
                drop(dekker);
            }
        }

        drop(guard);
    }
}

/// Holds the lock until dropped.
pub struct Guard<T> {
    owner: *mut Process<T>,
}

impl<T> Guard<T> {
    fn new(owner: *mut Process<T>) -> Guard<T> {
        Guard {
            owner,
        }
    }
}

impl<T> Deref for Guard<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        unsafe {
            &(*(*self.owner).owner).shared
        }
    }
}

impl<T> DerefMut for Guard<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe {
            &mut (*(*self.owner).owner).shared
        }
    }
}

impl<T> Drop for Guard<T> {
    // Let other process enter the critical section if guard is dropped.
    fn drop(&mut self) {
        unsafe {
            (*self.owner).locked = false;
            (*(*self.owner).owner).turn = 1 - (*self.owner).index;
            (*(*self.owner).owner).wants_to_enter[(*self.owner).index] = false;
        }
    }
}