StackThreads/MP: version 0.77 User's Guide
StackThreads/MP: version 0.77 User's Guide
This section describes how to implement your own synchronizing data
structure on top of the bottom-level primitives
(st_suspend_thread and st_resume_thread). Before using
bottom-level primitives, examine if it is possible to implement your
synchronization just by combining higher-level primitives (mutex,
semaphore, and condition variables). High-level primitives often save
your time for debugging. In particular, condition variable is very
general. You need bottom-level primitives only when they are necessary
for performance or when your synchronization is most conveniently expressed
with them.
Consider a simple example in which two threads, a producer (writer) and a consumer (reader), are synchronized through a location. The synchronization constraint is that the consumer must wait for the producer to put the result. We assume there is only a single writer and a reader. We must still resolve the races between the writer and the reader.
@ 1 typedef struct buffer
@ 2 {
@ 3 st_int_loc_t status; /* 0 for empty, 1 for full */
@ 4 int val;
@ 5 st_context_t waiter; /* waiting context */
@ 6 } * buffer_t;
@ 7
@ 8 void init_buffer(buffer_t b)
@ 9 {
10 ST_INT_LOC_INIT(&b->status, 0);
11 b->waiter = 0; /* no threads are waiting */
12 }
13
14 int GET(buffer_t b)
15 {
16 if (st_read_int(&b->status) == 1) {
17 return b->val; /* full */
18 } else {
19 /* atomically swap -1 and the current status */
20 int s = st_read_and_lock_int(&b->status);
21 if (s == 1) {
22 int val = b->val;
23 st_write_and_unlock_int(&b->status, s); /* unlock */
24 return val;
25 } else {
26 struct st_context c[1];
27 c->valid = 0;
28 b->waiter = c;
29 st_write_and_unlock_int(&b->status, 0); /* unlock */
30 st_suspend_thread(c);
31 return b->val;
32 }
33 }
34 }
35
36 int PUT(buffer_t b, int val)
37 {
38 /* atomically swap -1 and the current status */
39 st_read_and_lock_int(&b->status);
40 b->val = val;
41 if (b->w) {
42 /* somebody is waiting */
43 st_context_t w = b->w;
44 st_write_and_unlock_int(&b->status, 1); /* unlock */
45 st_resume_context(w);
46 } else {
47 st_write_and_unlock_int(&b->status, 1); /* unlock */
48 }
49 }
The buffer has three fields. The first one is val, the value
written by the writer. The second is waiter, which is a pointer
to a context. When a reader is blocked waiting for the value, the
context is written to waiter. Waiter is zero when nobody is
waiting. Finally it has status field to describe the status of
the buffer. It also serves as a lock variable to make modifications to
multiple words atomic. It is either full, in which the writer has
already performed a PUT, empty, in which it has not.
GET checks b->status and if it is not full, it suspends
the current thread by putting a context to b->waiter (the line
26---31). PUT checks b->waiters and if it is not zero, it
resumes the waiting thread (the line 42---45).
To resolve possible race conditions between the writer and the reader,
the above code looks more complicated than it ought to be. When the
reader decides to suspend, we must guarantee that the writer will see b->waiter after the reader writes to b->waiter. We
guarantee this by associating a lock with the status field. Before the
reader decides to suspend, it first obtains the lock by
st_read_and_lock_int(&b->status).
Since the writer first obtains the lock before reading b->waiter,
it is guaranteed that at line 26, the writer is not reading
b->waiter. The rest of the code is straightforward.
Here is very important notes on the use of
st_read_and_lock_int. First, do not forget unlock. Second, do not
spend a long time when you are locking any location by
st_read_and_lock_int. Once you obtain a lock, you must unlock it
as soon as possible. Typically, what you do while locking
something is a very short sequence of simple primitives like
arithmetics. Do not call any function that may take a long time. For
example, do not call malloc or printf. Finally, never try to obtain two
or more locks at the same time. This is naturally avoided if you try to
make critical sections as short as possible.
In short, st_read_and_lock_int itself should not be regarded as a
thread synchronization primitive, but be a primitive to support atomic
transactions to a single location. If you want to have an exclusive
access to a data structure for a long time (this is already an
unadvisable programming style, though) for some reasons, use
synchronization primitives such as mutex.