doc/wq_wake_up_one.3.html

   1 <html>
   2 <head>
   3 <meta name="generator" content="groff -Thtml, see www.gnu.org">
   4 <meta name="Content-Style" content="text/css">
   5 <title>new_wait_queue</title>
   6 </head>
   7 <body>
   8
   9 <h1 align=center>new_wait_queue</h1>
  10 <a href="#NAME">NAME</a><br>
  11 <a href="#SYNOPSIS">SYNOPSIS</a><br>
  12 <a href="#DESCRIPTION">DESCRIPTION</a><br>
  13 <a href="#AUTHOR">AUTHOR</a><br>
  14 <a href="#LICENSE">LICENSE</a><br>
  15 <a href="#VERSION">VERSION</a><br>
  16 <a href="#HISTORY">HISTORY</a><br>
  17
  18 <hr>
  19 <!-- Creator     : groff version 1.17.2 -->
  20 <!-- CreationDate: Fri Aug 30 16:16:46 2002 -->
  21 <a name="NAME"></a>
  22 <h2>NAME</h2>
  23 <table width="100%" border=0 rules="none" frame="void"
  24        cols="2" cellspacing="0" cellpadding="0">
  25 <tr valign="top" align="left">
  26 <td width="10%"></td><td width="90%">
  27 new_wait_queue, wq_wake_up, wq_wake_up_one, wq_sleep_on, wq_nr_sleepers - wait queues</td></table>
  28 <a name="SYNOPSIS"></a>
  29 <h2>SYNOPSIS</h2>
  30
  31 <table width="100%" border=0 rules="none" frame="void"
  32        cols="2" cellspacing="0" cellpadding="0">
  33 <tr valign="top" align="left">
  34 <td width="10%"></td><td width="90%">
  35 <pre><b>#include &lt;pthr_wait_queue.h&gt;
  36
  37 wait_queue new_wait_queue (pool);
  38 void wq_wake_up (wait_queue);
  39 void wq_wake_up_one (wait_queue);
  40 void wq_sleep_on (wait_queue, pseudothread);
  41 int wq_nr_sleepers (wait_queue);
  42 </b></pre></td></table>
  43 <a name="DESCRIPTION"></a>
  44 <h2>DESCRIPTION</h2>
  45
  46 <table width="100%" border=0 rules="none" frame="void"
  47        cols="2" cellspacing="0" cellpadding="0">
  48 <tr valign="top" align="left">
  49 <td width="10%"></td><td width="90%">
  50 <b>new_wait_queue</b> creates a wait queue
  51 object.</td></table>
  52
  53 <table width="100%" border=0 rules="none" frame="void"
  54        cols="2" cellspacing="0" cellpadding="0">
  55 <tr valign="top" align="left">
  56 <td width="10%"></td><td width="90%">
  57 <b>wq_wake_up</b> wakes up all the threads which are
  58 currently sleeping on the wait queue. Note that this
  59 function does not block, and because pseudothreads are
  60 non-preemptive, none of the sleeping threads will actually
  61 begin running until at least the current thread blocks
  62 somewhere else.</td></table>
  63
  64 <table width="100%" border=0 rules="none" frame="void"
  65        cols="2" cellspacing="0" cellpadding="0">
  66 <tr valign="top" align="left">
  67 <td width="10%"></td><td width="90%">
  68 <b>wq_wake_up_one</b> wakes up just the first thread at the
  69 head of the wait queue (the one which has been waiting the
  70 longest).</td></table>
  71
  72 <table width="100%" border=0 rules="none" frame="void"
  73        cols="2" cellspacing="0" cellpadding="0">
  74 <tr valign="top" align="left">
  75 <td width="10%"></td><td width="90%">
  76 <b>wq_sleep_on</b> sends the current thread to sleep on the
  77 wait queue. This call blocks (obviously).</td></table>
  78
  79 <table width="100%" border=0 rules="none" frame="void"
  80        cols="2" cellspacing="0" cellpadding="0">
  81 <tr valign="top" align="left">
  82 <td width="10%"></td><td width="90%">
  83 <b>wq_nr_sleepers</b> returns the number of threads which
  84 are currently asleep on the wait queue.</td></table>
  85
  86 <table width="100%" border=0 rules="none" frame="void"
  87        cols="2" cellspacing="0" cellpadding="0">
  88 <tr valign="top" align="left">
  89 <td width="10%"></td><td width="90%">
  90 Please read the HISTORY section below for some background
  91 into how wait queues are implemented. This may help if you
  92 find there are tricky race conditions in your
  93 code.</td></table>
  94 <a name="AUTHOR"></a>
  95 <h2>AUTHOR</h2>
  96
  97 <table width="100%" border=0 rules="none" frame="void"
  98        cols="2" cellspacing="0" cellpadding="0">
  99 <tr valign="top" align="left">
 100 <td width="10%"></td><td width="90%">
 101 Richard Jones &lt;rich@annexia.org&gt;</td></table>
 102 <a name="LICENSE"></a>
 103 <h2>LICENSE</h2>
 104
 105 <table width="100%" border=0 rules="none" frame="void"
 106        cols="2" cellspacing="0" cellpadding="0">
 107 <tr valign="top" align="left">
 108 <td width="10%"></td><td width="90%">
 109 GNU LGPL (see http://www.gnu.org/)</td></table>
 110 <a name="VERSION"></a>
 111 <h2>VERSION</h2>
 112
 113 <table width="100%" border=0 rules="none" frame="void"
 114        cols="2" cellspacing="0" cellpadding="0">
 115 <tr valign="top" align="left">
 116 <td width="10%"></td><td width="90%">
 117 pthrlib-3.0.3</td></table>
 118 <a name="HISTORY"></a>
 119 <h2>HISTORY</h2>
 120
 121 <table width="100%" border=0 rules="none" frame="void"
 122        cols="2" cellspacing="0" cellpadding="0">
 123 <tr valign="top" align="left">
 124 <td width="10%"></td><td width="90%">
 125 Originally, wait queues were implemented using underlying
 126 Unix pipes. This worked (to some extent) but the overhead of
 127 requiring one pipe (ie. one inode, two file descriptors) per
 128 wait queue made this implementation unacceptably
 129 heavyweight.</td></table>
 130
 131 <table width="100%" border=0 rules="none" frame="void"
 132        cols="2" cellspacing="0" cellpadding="0">
 133 <tr valign="top" align="left">
 134 <td width="10%"></td><td width="90%">
 135 Wait queues are now implemented using a simple hack in the
 136 reactor which will be described below.</td></table>
 137
 138 <table width="100%" border=0 rules="none" frame="void"
 139        cols="2" cellspacing="0" cellpadding="0">
 140 <tr valign="top" align="left">
 141 <td width="10%"></td><td width="90%">
 142 Wait queues are subtle. Consider this example: Threads 1, 2
 143 and 3 are sleeping on a wait queue. Now thread 4 wakes up
 144 the queue. You would expect (probably) threads 1, 2 and 3 to
 145 each be woken up and allowed to start running. However,
 146 since this is a cooperatively multitasking environment, it
 147 may happen that thread 1 wakes up first, does some work and
 148 then goes back to sleep on the wait queue, all before
 149 threads 2 and 3 have woken up. With a naive implementation
 150 of wait queues, thread 4 might end up waking up thread 1
 151 *again* (and even again after that), never waking up threads
 152 2 and 3 and ultimately starving those threads.</td></table>
 153
 154 <table width="100%" border=0 rules="none" frame="void"
 155        cols="2" cellspacing="0" cellpadding="0">
 156 <tr valign="top" align="left">
 157 <td width="10%"></td><td width="90%">
 158 To avoid this situation, we might consider two possible
 159 alternatives: either when thread 1 goes back to sleep, it
 160 goes to sleep on a 'different' queue, or else thread 4 might
 161 take a copy of the wait queue and delete the queue before it
 162 wakes any of the threads up.</td></table>
 163
 164 <table width="100%" border=0 rules="none" frame="void"
 165        cols="2" cellspacing="0" cellpadding="0">
 166 <tr valign="top" align="left">
 167 <td width="10%"></td><td width="90%">
 168 Another nasty situation which might arise in real life is
 169 this: Again, threads 1, 2 and 3 are sleeping. Thread 4 wakes
 170 them up. Thread 1, while processing its work, happens also
 171 to wake up the same wait queue. What should happen to this
 172 second wake-up event? Should it be ignored? Should it wake
 173 up threads 2 and 3? Should it wake up any other threads
 174 which happen to have gone to sleep on the queue after 1, 2
 175 and 3? Or perhaps some combination of these?</td></table>
 176
 177 <table width="100%" border=0 rules="none" frame="void"
 178        cols="2" cellspacing="0" cellpadding="0">
 179 <tr valign="top" align="left">
 180 <td width="10%"></td><td width="90%">
 181 The solution that we have come up with is as follows. A wait
 182 queue consists of a simple list of threads which are
 183 sleeping on it. When a thread wishes to sleep on the wait
 184 queue, it is added to this list, and it switches back into
 185 the reactor context. When a thread wishes to wake up all
 186 sleepers, it: (a) copies the list of sleeping pseudothreads
 187 into its own private space (b) clears the list of sleeping
 188 pseudothreads (c) registers a prepoll handler to run which
 189 will wake up (ie. switch into the context of) each of these
 190 threads in turn (d) continues to run to completion. A thread
 191 which wishes to wake just one pseudothread works similarly
 192 except that it only copies (and removes) a single item off
 193 the list.</td></table>
 194
 195 <table width="100%" border=0 rules="none" frame="void"
 196        cols="2" cellspacing="0" cellpadding="0">
 197 <tr valign="top" align="left">
 198 <td width="10%"></td><td width="90%">
 199 Note various invariant conditions: A thread cannot be
 200 entered on the wait queue sleeping list more than once
 201 (because it cannot call sleep_on when it is already
 202 sleeping). For similar reasons, a thread cannot be entered
 203 on any of the multiple lists at the same time. This implies
 204 that a thread cannot be woken up multiple
 205 times.</td></table>
 206
 207 <table width="100%" border=0 rules="none" frame="void"
 208        cols="2" cellspacing="0" cellpadding="0">
 209 <tr valign="top" align="left">
 210 <td width="10%"></td><td width="90%">
 211 The reader should satisfy themselves that this algorithm is
 212 free of races, and solves all the problems outlined above.
 213 In addition, it has the desirable property that wake_up*
 214 never sleeps.</td></table>
 215 <hr>
 216 </body>
 217 </html>