StackThreads/MP: version 0.77 User's Guide
StackThreads/MP: version 0.77 User's Guide
typedef struct st_int_loc st_int_loc_t;
@ typedef struct st_long_loc st_long_loc_t;
@ typedef struct st_ptr_loc st_ptr_loc_t;
@ int st_read_and_lock_int(il);
@ long st_read_and_lock_long(ll);
@ void * st_read_and_lock_ptr(pl);
@ void st_write_and_unlock_int(il, i);
@ void st_write_and_unlock_long(ll, l);
@ void st_write_and_unlock_ptr(pl, p);
@ int ST_INT_LOC_INIT(il, i);
@ long ST_LONG_LOC_INIT(ll, l);
@ void * ST_PTR_LOC_INIT(pl, p);
@ st_int_loc_t * il; int i;
@ st_long_loc_t * ll; long l;
@ st_ptr_loc_t * pl; void * p;
@ st_int_loc_t v = ST_INT_LOC_INITIALIZER(x);
@ st_long_loc_t v = ST_LONG_LOC_INITIALIZER(x);
@ st_ptr_loc_t v = ST_PTR_LOC_INITIALIZER(x);
Type st_int_loc_t is int type that is `tagged' by `lock bits.'
Similarly, st_long_loc_t and st_ptr_loc_t are tagged long
and void *, respectively.
st_read_and_lock_int(il) waits for the location pointed to by
il to become unlocked. When it is unlocked, it atomically lock the
location and returns the value previously written at the location
pointed to by il. Lock bits are
stripped. st_read_and_lock_long(ll) and
st_read_and_lock_ptr(pl) work similarly, but on locations that
hold values of type st_loc_long_t and st_loc_ptr_t,
respectively.
st_write_and_unlock_int(il, i) writes value i to the
location pointed to by il and unlocks the location. The location
must be locked upon calling the procedure.
st_write_and_unlock_long(ll, l) and
st_write_and_unlock_ptr(pl, p) are similar procedures for
st_long_loc_t * and st_ptr_loc_t *, respectively.
ST_INT_LOC_INT(il, i) initializes the location pointed to by
il by i. The location is initialized to `unlocked' state.
ST_LONG_LOC_INT(ll, l) and ST_PTR_LOC_INT(pl, p)
are similar procedures for st_long_loc_t * and st_ptr_loc_t *,
respectively.
st_int_loc_t v = ST_INT_LOC_INITIALIZER(x); defines a global
or static variable of st_int_loc_t that is initialized to x.
ST_LONG_LOC_INITIALIZER(x) and ST_PTR_LOC_INITIALIZER(x)
are similar initializers for st_long_loc_t and st_ptr_loc_t,
respectively.
st_read_and_lock and st_write_and_unlock can be used to perform
an atomic read-modify-write sequence on a single location. Here is a
typical example.
st_int_loc_t il = ST_INT_LOC_INITIALIZER(1);
@
@ void read_modify_write()
@ {
@ int x = st_read_and_lock_int(&il);
@ st_write_and_unlock_int(&il, 3 * x);
@ }
This code atomically multiplies the value at the location il by 3.
Remark 1: Primitives st_read_and_lock_xxx never block the
calling thread; they just wait for the location to become unlocked by
spinning. Therefore, do every effort to make the critical section as short as possible. How short should they be? Well, as a
rough approximation, avoid anything more than a couple of arithmetics
and a couple of loads and stores. Avoid dynamic memory allocations such
as malloc when you are holding a lock. Also, never try to lock
a location when you are locking another location. It is a common source
of deadlocks.
If you cannot avoid having a long critical section, you should not use
spin-lock primitives in the first place, but use blocking
synchronization primitives. As already shown, StackThreads/MP provides
synchronization primitives that block the calling thread and schedule
another thread when necessary. st_mutex_t will be most useful for
such purposes.
Nonetheless, spin-locks are useful for short-critical sections. You cannot unconditionally adopt blocking primitives, as critical sections can be made short in many cases and in such cases spin-locks are both time- and space- efficient.
To avoid deadlocks and severe performance degradation due to a wrong use
of spin-locks, st_read_and_lock primitives will timeout after a
certain number of attempts. More specifically, when they fail to obtain
a lock 1,000 times in a row, they sleep the calling worker 1 millisecond
and retry. They repeat this process 10 times. When the lock is not still
granted, it displays an error message and the application dies. It may
kill an application that would otherwise be correct. However, it can
detect a common programming error in which the programmer forgets to
write a necessary unlock operation. Even if the application works,
holding a lock 10 milliseconds typically degrades performance of the
application, so you should take the error message as a strong suggestion
that your locking strategy is wrong.
Remark 2: These primitives assume that two bits are embedded
for tags within a single word. For example, on machines where int is
32 bits, st_int_loc_t uses the least significant two bits for
tags. The value is left-shifted by two bits and stored in the most
significant 30 bits. Consequently the most significant two bits are
discarded when a value is stored. Conversely, when a value is read, the
most significant two bits are sign-extended. Therefore, values
representable by st_int_loc_t are restricted to -2^30 ... 2^30 -
1. For pointers, we assume the value of a pointer is 4 bytes
aligned. That is, the least significant two bits of a pointer are zeroes
and we use these two bits for tags. When a value that is not properly
aligned is given to st_write_and_unlock_ptr, the least significant
two bits are just discarded.