Contiki-NG
pt-sem.h
Go to the documentation of this file.
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 Contiki operating system.
30  *
31  * Author: Adam Dunkels <adam@sics.se>
32  *
33  */
34 
35 /**
36  * \addtogroup pt
37  * @{
38  */
39 
40 /**
41  * \defgroup ptsem Protothread semaphores
42  * @{
43  *
44  * This module implements counting semaphores on top of
45  * protothreads. Semaphores are a synchronization primitive that
46  * provide two operations: "wait" and "signal". The "wait" operation
47  * checks the semaphore counter and blocks the thread if the counter
48  * is zero. The "signal" operation increases the semaphore counter but
49  * does not block. If another thread has blocked waiting for the
50  * semaphore that is signaled, the blocked thread will become
51  * runnable again.
52  *
53  * Semaphores can be used to implement other, more structured,
54  * synchronization primitives such as monitors and message
55  * queues/bounded buffers (see below).
56  *
57  * The following example shows how the producer-consumer problem, also
58  * known as the bounded buffer problem, can be solved using
59  * protothreads and semaphores. Notes on the program follow after the
60  * example.
61  *
62  \code
63 #include "pt-sem.h"
64 
65 #define NUM_ITEMS 32
66 #define BUFSIZE 8
67 
68 static struct pt_sem mutex, full, empty;
69 
70 PT_THREAD(producer(struct pt *pt))
71 {
72  static int produced;
73 
74  PT_BEGIN(pt);
75 
76  for(produced = 0; produced < NUM_ITEMS; ++produced) {
77 
78  PT_SEM_WAIT(pt, &full);
79 
80  PT_SEM_WAIT(pt, &mutex);
81  add_to_buffer(produce_item());
82  PT_SEM_SIGNAL(pt, &mutex);
83 
84  PT_SEM_SIGNAL(pt, &empty);
85  }
86 
87  PT_END(pt);
88 }
89 
90 PT_THREAD(consumer(struct pt *pt))
91 {
92  static int consumed;
93 
94  PT_BEGIN(pt);
95 
96  for(consumed = 0; consumed < NUM_ITEMS; ++consumed) {
97 
98  PT_SEM_WAIT(pt, &empty);
99 
100  PT_SEM_WAIT(pt, &mutex);
101  consume_item(get_from_buffer());
102  PT_SEM_SIGNAL(pt, &mutex);
103 
104  PT_SEM_SIGNAL(pt, &full);
105  }
106 
107  PT_END(pt);
108 }
109 
110 PT_THREAD(driver_thread(struct pt *pt))
111 {
112  static struct pt pt_producer, pt_consumer;
113 
114  PT_BEGIN(pt);
115 
116  PT_SEM_INIT(&empty, 0);
117  PT_SEM_INIT(&full, BUFSIZE);
118  PT_SEM_INIT(&mutex, 1);
119 
120  PT_INIT(&pt_producer);
121  PT_INIT(&pt_consumer);
122 
123  PT_WAIT_THREAD(pt, producer(&pt_producer) &
124  consumer(&pt_consumer));
125 
126  PT_END(pt);
127 }
128  \endcode
129  *
130  * The program uses three protothreads: one protothread that
131  * implements the consumer, one thread that implements the producer,
132  * and one protothread that drives the two other protothreads. The
133  * program uses three semaphores: "full", "empty" and "mutex". The
134  * "mutex" semaphore is used to provide mutual exclusion for the
135  * buffer, the "empty" semaphore is used to block the consumer is the
136  * buffer is empty, and the "full" semaphore is used to block the
137  * producer is the buffer is full.
138  *
139  * The "driver_thread" holds two protothread state variables,
140  * "pt_producer" and "pt_consumer". It is important to note that both
141  * these variables are declared as <i>static</i>. If the static
142  * keyword is not used, both variables are stored on the stack. Since
143  * protothreads do not store the stack, these variables may be
144  * overwritten during a protothread wait operation. Similarly, both
145  * the "consumer" and "producer" protothreads declare their local
146  * variables as static, to avoid them being stored on the stack.
147  *
148  *
149  */
150 
151 /**
152  * \file
153  * Counting semaphores implemented on protothreads
154  * \author
155  * Adam Dunkels <adam@sics.se>
156  *
157  */
158 
159 #ifndef PT_SEM_H_
160 #define PT_SEM_H_
161 
162 #include "sys/pt.h"
163 
164 struct pt_sem {
165  unsigned int head, tail;
166 };
167 
168 #define PT_SEM_COUNT(s) ((s)->head - (s)->tail)
169 
170 /**
171  * Initialize a semaphore
172  *
173  * This macro initializes a semaphore with a value for the
174  * counter. Internally, the semaphores use an "unsigned int" to
175  * represent the counter, and therefore the "count" argument should be
176  * within range of an unsigned int.
177  *
178  * \param s (struct pt_sem *) A pointer to the pt_sem struct
179  * representing the semaphore
180  *
181  * \param c (unsigned int) The initial count of the semaphore.
182  * \hideinitializer
183  */
184 #define PT_SEM_INIT(s, c) \
185  do { \
186  (s)->tail = 0; \
187  (s)->head = (c); \
188  } while(0)
189 
190 /**
191  * Wait for a semaphore
192  *
193  * This macro carries out the "wait" operation on the semaphore. The
194  * wait operation causes the protothread to block while the counter is
195  * zero. When the counter reaches a value larger than zero, the
196  * protothread will continue.
197  *
198  * \param pt (struct pt *) A pointer to the protothread (struct pt) in
199  * which the operation is executed.
200  *
201  * \param s (struct pt_sem *) A pointer to the pt_sem struct
202  * representing the semaphore
203  *
204  * \hideinitializer
205  */
206 #define PT_SEM_WAIT(pt, s) \
207  do { \
208  PT_WAIT_UNTIL(pt, PT_SEM_COUNT(s) > 0); \
209  ++(s)->tail; \
210  } while(0)
211 
212 /**
213  * Signal a semaphore
214  *
215  * This macro carries out the "signal" operation on the semaphore. The
216  * signal operation increments the counter inside the semaphore, which
217  * eventually will cause waiting protothreads to continue executing.
218  *
219  * \param pt (struct pt *) A pointer to the protothread (struct pt) in
220  * which the operation is executed.
221  *
222  * \param s (struct pt_sem *) A pointer to the pt_sem struct
223  * representing the semaphore
224  *
225  * \hideinitializer
226  */
227 #define PT_SEM_SIGNAL(pt, s) (++(s)->head)
228 
229 #endif /* PT_SEM_H_ */
230 
231 /** @} */
232 /** @} */
233 
Protothreads implementation.