dol/src/dol/visitor/cell/lib/pt/pt-sem.h

   1 /*
   2  * Copyright (c) 2004, Swedish Institute of Computer Science.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the Institute nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  * This file is part of the protothreads library.
  30  *
  31  * Author: Adam Dunkels <adam@sics.se>
  32  *
  33  * $Id: pt-sem.h 1 2010-02-24 13:03:05Z haidw $
  34  */
  35
  36 /**
  37  * \addtogroup pt
  38  * @{
  39  */
  40
  41 /**
  42  * \defgroup ptsem Protothread semaphores
  43  * @{
  44  *
  45  * This module implements counting semaphores on top of
  46  * protothreads. Semaphores are a synchronization primitive that
  47  * provide two operations: "wait" and "signal". The "wait" operation
  48  * checks the semaphore counter and blocks the thread if the counter
  49  * is zero. The "signal" operation increases the semaphore counter but
  50  * does not block. If another thread has blocked waiting for the
  51  * semaphore that is signalled, the blocked thread will become
  52  * runnable again.
  53  *
  54  * Semaphores can be used to implement other, more structured,
  55  * synchronization primitives such as monitors and message
  56  * queues/bounded buffers (see below).
  57  *
  58  * The following example shows how the producer-consumer problem, also
  59  * known as the bounded buffer problem, can be solved using
  60  * protothreads and semaphores. Notes on the program follow after the
  61  * example.
  62  *
  63  \code
  64 #include "pt-sem.h"
  65
  66 #define NUM_ITEMS 32
  67 #define BUFSIZE 8
  68
  69 static struct pt_sem mutex, full, empty;
  70
  71 PT_THREAD(producer(struct pt *pt))
  72 {
  73   static int produced;
  74
  75   PT_BEGIN(pt);
  76
  77   for(produced = 0; produced < NUM_ITEMS; ++produced) {
  78
  79     PT_SEM_WAIT(pt, &full);
  80
  81     PT_SEM_WAIT(pt, &mutex);
  82     add_to_buffer(produce_item());
  83     PT_SEM_SIGNAL(pt, &mutex);
  84
  85     PT_SEM_SIGNAL(pt, &empty);
  86   }
  87
  88   PT_END(pt);
  89 }
  90
  91 PT_THREAD(consumer(struct pt *pt))
  92 {
  93   static int consumed;
  94
  95   PT_BEGIN(pt);
  96
  97   for(consumed = 0; consumed < NUM_ITEMS; ++consumed) {
  98
  99     PT_SEM_WAIT(pt, &empty);
 100
 101     PT_SEM_WAIT(pt, &mutex);
 102     consume_item(get_from_buffer());
 103     PT_SEM_SIGNAL(pt, &mutex);
 104
 105     PT_SEM_SIGNAL(pt, &full);
 106   }
 107
 108   PT_END(pt);
 109 }
 110
 111 PT_THREAD(driver_thread(struct pt *pt))
 112 {
 113   static struct pt pt_producer, pt_consumer;
 114
 115   PT_BEGIN(pt);
 116
 117   PT_SEM_INIT(&empty, 0);
 118   PT_SEM_INIT(&full, BUFSIZE);
 119   PT_SEM_INIT(&mutex, 1);
 120
 121   PT_INIT(&pt_producer);
 122   PT_INIT(&pt_consumer);
 123
 124   PT_WAIT_THREAD(pt, producer(&pt_producer) &
 125                      consumer(&pt_consumer));
 126
 127   PT_END(pt);
 128 }
 129  \endcode
 130  *
 131  * The program uses three protothreads: one protothread that
 132  * implements the consumer, one thread that implements the producer,
 133  * and one protothread that drives the two other protothreads. The
 134  * program uses three semaphores: "full", "empty" and "mutex". The
 135  * "mutex" semaphore is used to provide mutual exclusion for the
 136  * buffer, the "empty" semaphore is used to block the consumer is the
 137  * buffer is empty, and the "full" semaphore is used to block the
 138  * producer is the buffer is full.
 139  *
 140  * The "driver_thread" holds two protothread state variables,
 141  * "pt_producer" and "pt_consumer". It is important to note that both
 142  * these variables are declared as <i>static</i>. If the static
 143  * keyword is not used, both variables are stored on the stack. Since
 144  * protothreads do not store the stack, these variables may be
 145  * overwritten during a protothread wait operation. Similarly, both
 146  * the "consumer" and "producer" protothreads declare their local
 147  * variables as static, to avoid them being stored on the stack.
 148  *
 149  *
 150  */
 151
 152 /**
 153  * \file
 154  * Couting semaphores implemented on protothreads
 155  * \author
 156  * Adam Dunkels <adam@sics.se>
 157  *
 158  */
 159
 160 #ifndef __PT_SEM_H__
 161 #define __PT_SEM_H__
 162
 163 #include "pt.h"
 164
 165 struct pt_sem {
 166   unsigned int count;
 167 };
 168
 169 /**
 170  * Initialize a semaphore
 171  *
 172  * This macro initializes a semaphore with a value for the
 173  * counter. Internally, the semaphores use an "unsigned int" to
 174  * represent the counter, and therefore the "count" argument should be
 175  * within range of an unsigned int.
 176  *
 177  * \param s (struct pt_sem *) A pointer to the pt_sem struct
 178  * representing the semaphore
 179  *
 180  * \param c (unsigned int) The initial count of the semaphore.
 181  * \hideinitializer
 182  */
 183 #define PT_SEM_INIT(s, c) (s)->count = c
 184
 185 /**
 186  * Wait for a semaphore
 187  *
 188  * This macro carries out the "wait" operation on the semaphore. The
 189  * wait operation causes the protothread to block while the counter is
 190  * zero. When the counter reaches a value larger than zero, the
 191  * protothread will continue.
 192  *
 193  * \param pt (struct pt *) A pointer to the protothread (struct pt) in
 194  * which the operation is executed.
 195  *
 196  * \param s (struct pt_sem *) A pointer to the pt_sem struct
 197  * representing the semaphore
 198  *
 199  * \hideinitializer
 200  */
 201 #define PT_SEM_WAIT(pt, s)      \
 202   do {                                          \
 203     PT_WAIT_UNTIL(pt, (s)->count > 0);          \
 204     --(s)->count;                               \
 205   } while(0)
 206
 207 /**
 208  * Signal a semaphore
 209  *
 210  * This macro carries out the "signal" operation on the semaphore. The
 211  * signal operation increments the counter inside the semaphore, which
 212  * eventually will cause waiting protothreads to continue executing.
 213  *
 214  * \param pt (struct pt *) A pointer to the protothread (struct pt) in
 215  * which the operation is executed.
 216  *
 217  * \param s (struct pt_sem *) A pointer to the pt_sem struct
 218  * representing the semaphore
 219  *
 220  * \hideinitializer
 221  */
 222 #define PT_SEM_SIGNAL(pt, s) ++(s)->count
 223
 224 #endif /* __PT_SEM_H__ */
 225
 226 /** @} */
 227 /** @} */
 228