2 * by Richard W.M. Jones <rich@annexia.org>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the Free
16 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
18 * $Id: pthr_wait_queue.h,v 1.3 2002/12/01 14:29:31 rich Exp $
21 #ifndef PTHR_WAIT_QUEUE_H
22 #define PTHR_WAIT_QUEUE_H
26 #include "pthr_pseudothread.h"
29 typedef struct wait_queue *wait_queue;
31 /* Function: new_wait_queue - wait queues
32 * Function: wq_wake_up
33 * Function: wq_wake_up_one
34 * Function: wq_sleep_on
35 * Function: wq_nr_sleepers
37 * @code{new_wait_queue} creates a wait queue object.
39 * @code{wq_wake_up} wakes up all the threads which are currently
40 * sleeping on the wait queue. Note that this function does not block,
41 * and because pseudothreads are non-preemptive, none of the sleeping threads
42 * will actually begin running until at least the current thread
43 * blocks somewhere else.
45 * @code{wq_wake_up_one} wakes up just the first thread at the head
46 * of the wait queue (the one which has been waiting the longest).
48 * @code{wq_sleep_on} sends the current thread to sleep on the wait
49 * queue. This call blocks (obviously).
51 * @code{wq_nr_sleepers} returns the number of threads which are
52 * currently asleep on the wait queue.
54 * Please read the HISTORY section below for some background into
55 * how wait queues are implemented. This may help if you find there
56 * are tricky race conditions in your code.
60 * Originally, wait queues were implemented using underlying Unix
61 * pipes. This worked (to some extent) but the overhead of requiring
62 * one pipe (ie. one inode, two file descriptors) per wait queue
63 * made this implementation unacceptably heavyweight.
65 * Wait queues are now implemented using a simple hack in the reactor
66 * which will be described below.
68 * Wait queues are subtle. Consider this example: Threads 1, 2 and 3 are
69 * sleeping on a wait queue. Now thread 4 wakes up the queue. You would
70 * expect (probably) threads 1, 2 and 3 to each be woken up and allowed
71 * to start running. However, since this is a cooperatively multitasking
72 * environment, it may happen that thread 1 wakes up first, does some
73 * work and then goes back to sleep on the wait queue, all before threads
74 * 2 and 3 have woken up. With a naive implementation of wait queues,
75 * thread 4 might end up waking up thread 1 *again* (and even again after
76 * that), never waking up threads 2 and 3 and ultimately starving those
79 * To avoid this situation, we might consider two possible alternatives:
80 * either when thread 1 goes back to sleep, it goes to sleep on a
81 * 'different' queue, or else thread 4 might take a copy of the wait
82 * queue and delete the queue before it wakes any of the threads up.
84 * Another nasty situation which might arise in real life is this:
85 * Again, threads 1, 2 and 3 are sleeping. Thread 4 wakes them up.
86 * Thread 1, while processing its work, happens also to wake up the
87 * same wait queue. What should happen to this second wake-up event?
88 * Should it be ignored? Should it wake up threads 2 and 3? Should
89 * it wake up any other threads which happen to have gone to sleep
90 * on the queue after 1, 2 and 3? Or perhaps some combination of
93 * The solution that we have come up with is as follows. A wait queue
94 * consists of a simple list of threads which are sleeping on it. When
95 * a thread wishes to sleep on the wait queue, it is added to this list,
96 * and it switches back into the reactor context. When a thread wishes
97 * to wake up all sleepers, it:
98 * (a) copies the list of sleeping pseudothreads into its own private
100 * (b) clears the list of sleeping pseudothreads
101 * (c) registers a prepoll handler to run which will wake up (ie. switch
102 * into the context of) each of these threads in turn
103 * (d) continues to run to completion.
104 * A thread which wishes to wake just one pseudothread works similarly
105 * except that it only copies (and removes) a single item off the list.
107 * Note various invariant conditions: A thread cannot be entered on the
108 * wait queue sleeping list more than once (because it cannot call
109 * sleep_on when it is already sleeping). For similar reasons, a thread
110 * cannot be entered on any of the multiple lists at the same time.
111 * This implies that a thread cannot be woken up multiple times.
113 * The reader should satisfy themselves that this algorithm is free
114 * of races, and solves all the problems outlined above. In addition, it
115 * has the desirable property that wake_up* never sleeps.
118 extern wait_queue new_wait_queue (pool);
119 extern void wq_wake_up (wait_queue);
120 extern void wq_wake_up_one (wait_queue);
121 extern void wq_sleep_on (wait_queue);
122 extern int wq_nr_sleepers (wait_queue);
124 #endif /* PTHR_WAIT_QUEUE_H */