src/pthr_wait_queue.h

   1 /* Wait queues.
   2  * by Richard W.M. Jones <rich@annexia.org>
   3  *
   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.
   8  *
   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.
  13  *
  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.
  17  *
  18  * $Id: pthr_wait_queue.h,v 1.3 2002/12/01 14:29:31 rich Exp $
  19  */
  20
  21 #ifndef PTHR_WAIT_QUEUE_H
  22 #define PTHR_WAIT_QUEUE_H
  23
  24 #include <pool.h>
  25
  26 #include "pthr_pseudothread.h"
  27
  28 struct wait_queue;
  29 typedef struct wait_queue *wait_queue;
  30
  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
  36  *
  37  * @code{new_wait_queue} creates a wait queue object.
  38  *
  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.
  44  *
  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).
  47  *
  48  * @code{wq_sleep_on} sends the current thread to sleep on the wait
  49  * queue. This call blocks (obviously).
  50  *
  51  * @code{wq_nr_sleepers} returns the number of threads which are
  52  * currently asleep on the wait queue.
  53  *
  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.
  57  *
  58  * History:
  59  *
  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.
  64  *
  65  * Wait queues are now implemented using a simple hack in the reactor
  66  * which will be described below.
  67  *
  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
  77  * threads.
  78  *
  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.
  83  *
  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
  91  * these?
  92  *
  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
  99  *     space
 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.
 106  *
 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.
 112  *
 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.
 116  *
 117  */
 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);
 123
 124 #endif /* PTHR_WAIT_QUEUE_H */