aboutsummaryrefslogtreecommitdiff
path: root/nptl/DESIGN-condvar.txt
diff options
context:
space:
mode:
Diffstat (limited to 'nptl/DESIGN-condvar.txt')
-rw-r--r--nptl/DESIGN-condvar.txt90
1 files changed, 90 insertions, 0 deletions
diff --git a/nptl/DESIGN-condvar.txt b/nptl/DESIGN-condvar.txt
new file mode 100644
index 0000000000..303807be6d
--- /dev/null
+++ b/nptl/DESIGN-condvar.txt
@@ -0,0 +1,90 @@
+Conditional Variable pseudocode.
+================================
+
+ int pthread_cond_timedwait (pthread_cond_t *cv, pthread_mutex_t *mutex);
+ int pthread_cond_signal (pthread_cond_t *cv);
+ int pthread_cond_broadcast (pthread_cond_t *cv);
+
+struct pthread_cond_t {
+
+ unsigned int lock:
+
+ internal mutex
+
+ unsigned int nr_wakers:
+
+ number of threads signalled to be woken up.
+
+ unsigned int nr_sleepers:
+
+ number of threads waiting for the cv.
+
+}
+
+#define ALL_THREADS (1 << (BITS_PER_LONG-1))
+
+cond_wait_timeout(cv, mutex, timeout):
+{
+ lll_lock(cv->lock);
+ mutex_unlock(mutex);
+
+ cv->nr_sleepers++;
+ for (;;) {
+
+ if (cv->nr_wakers) {
+ cv->nr_wakers--;
+ break;
+ }
+ val = cv->nr_wakers;
+
+ lll_unlock(cv->lock);
+
+ ret = FUTEX WAIT (cv->nr_wakers, val, timeout)
+
+ lll_lock(cv->lock);
+
+ if (ret == TIMEOUT)
+ break;
+ ret = 0;
+ }
+ if (!--cv->nr_sleepers)
+ cv->nr_wakers = 0; /* no memory of wakeups */
+ lll_unlock(cv->lock);
+ mutex_lock(mutex);
+
+ return ret;
+}
+
+cond_signal(cv)
+{
+ int do_wakeup = 0;
+
+ lll_lock(cv->lock);
+ if (cv->nr_sleepers) {
+ if (!++cv->nr_wakers) /* overflow detection for the nutcase */
+ cv->nr_wakers = ALL_THREADS;
+ do_wakeup = 1;
+ }
+ lll_unlock(cv->lock);
+ if (do_wakeup)
+ FUTEX WAKE (cv->nr_wakers, 1)
+}
+
+cond_broadcast(cv)
+{
+ int do_wakeup = 0;
+
+ lll_lock(cv->lock);
+ if (cv->nr_sleepers) {
+ cv->nr_wakers |= ALL_THREADS;
+ do_wakeup = 1;
+ }
+ lll_unlock(cv->lock);
+ if (do_wakeup)
+ FUTEX WAKE (cv->nr_wakers, ALL_THREADS);
+}
+
+weaknesses of the implementation:
+
+ it might generate spurious wakeups in the broadcast case, but those are
+ allowed by POSIX.