keos_project4/sync/
condition_variable.rs

1//! # Condition Variable.
2//!
3//! A **Condition Variable** allows a thread to efficiently block until a
4//! certain condition is met, without consuming CPU cycles. It is always used
5//! in conjunction with a [`Mutex`] that guards access to shared data. It is
6//! generally used when a thread needs to *wait for a specific state*
7//! in shared data, and another thread will *notify* it when that state changes.
8//!
9//! Condition variables enable complex synchronization patterns such as thread
10//! coordination, resource availability signaling, or implementing blocking
11//! queues.
12//!
13//! ## `ConditionVariable` in KeOS
14//! Condition variable must work with the shared [`Mutex`]. To enforce this,
15//! KeOS's [`ConditionVariable`] api takes either [`Mutex`] or [`MutexGuard`] as
16//! an argument. This enforces that the apis are called with a mutex, but does
17//! not fully ensure that the mutex is the associated one.
18//!
19//! The [`ConditionVariable::wait_while`] method automatically checks the
20//! predicate, blocks the current thread if the condition is true, and re-checks
21//! it upon wakeup. The method takes care of locking, checking the condition,
22//! blocking, and waking up:
23//!
24//! ```rust
25//! let guard = condvar.wait_while(&mutex, |state| state.is_empty());
26//! ```
27//!
28//! There are two signaling methods that takes the [`MutexGuard`]:
29//! - [`ConditionVariable::signal`] wakes **one** waiting thread and
30//! - [`ConditionVariable::broadcast`] wakes **all** waiting threads.
31//!
32//! ## Implementation Requirements
33//! You need to implement the followings:
34//! - [`ConditionVariable::wait_while`]
35//! - [`ConditionVariable::signal`]
36//! - [`ConditionVariable::broadcast`]
37//!
38//! After implement the functionalities, move on to the next [`section`].
39//!
40//! [`Mutex`]: crate::sync::Mutex
41//! [`section`]: crate::sync::semaphore
42
43use super::mutex::{Mutex, MutexGuard};
44use alloc::collections::vec_deque::VecDeque;
45use keos::{sync::SpinLock, thread::ParkHandle};
46
47/// A Condition Variable
48///
49/// Condition variables represent the ability to block a thread such that it
50/// consumes no CPU time while waiting for an event to occur. Condition
51/// variables are typically associated with a boolean predicate (a condition)
52/// and a mutex. The predicate is always verified inside of the mutex before
53/// determining that a thread must block.
54///
55/// Functions in this module will block the current **thread** of execution.
56/// Note that any attempt to use multiple mutexes on the same condition
57/// variable may result in a runtime panic.
58#[derive(Default)]
59pub struct ConditionVariable {
60    waiters: SpinLock<VecDeque<ParkHandle>>,
61}
62
63impl ConditionVariable {
64    /// Creates a new condition variable which is ready to be waited on and
65    /// signaled.
66    pub fn new() -> Self {
67        Self {
68            waiters: SpinLock::new(VecDeque::new()),
69        }
70    }
71
72    /// Blocks the current thread while `predicate` returns `true`.
73    ///
74    /// This function takes reference of a [`Mutex`] and checks the
75    /// predicate. If it returns `true`, the thread is blocked and the mutex is
76    /// temporarily released. When the thread is signaled and wakes up, it
77    /// reacquires the mutex and re-evaluates the predicate. This loop continues
78    /// until the predicate returns `false`.
79    ///
80    /// # Example
81    /// ```rust
82    /// let guard = condvar.wait_while(&mutex, |state| state.count == 0);
83    /// ```
84    ///
85    /// There is **no need to check the predicate before calling** `wait_while`.
86    /// It performs the entire check-and-sleep logic internally.
87    pub fn wait_while<'a, T>(
88        &self,
89        mutex: &'a Mutex<T>,
90        predicate: impl Fn(&mut T) -> bool,
91    ) -> MutexGuard<'a, T> {
92        todo!()
93    }
94
95    /// Wakes up one blocked thread on this condvar.
96    ///
97    /// If there is a blocked thread on this condition variable, then it will
98    /// be woken up from its call to [`wait_while`]. Calls to `signal` are not
99    /// buffered in any way.
100    ///
101    /// To wake up all threads, see [`broadcast`].
102    ///
103    /// [`broadcast`]: ConditionVariable::broadcast
104    /// [`wait_while`]: ConditionVariable::wait_while
105    pub fn signal<'a, T>(&self, guard: MutexGuard<'a, T>) {
106        todo!()
107    }
108
109    /// Wakes up all blocked threads on this condvar.
110    ///
111    /// This method will ensure that any current waiters on the condition
112    /// variable are awoken. Calls to `broadcast()` are not buffered in any
113    /// way.
114    ///
115    /// To wake up only one thread, see [`signal`].
116    ///
117    /// [`signal`]: ConditionVariable::signal
118    pub fn broadcast<'a, T>(&self, guard: MutexGuard<'a, T>) {
119        todo!()
120    }
121}
keos_project4/sync/condition_variable.rs

keos_project4/sync/
condition_variable.rs
