Programming with POSIX® Threads

132 printf (
133 'lock backward got all locks, %d backoffs
', backoffs);
134 pthread_mutex_unlock (&mutex[0]);
135 pthread_mutex_unlock (&mutex[l]);
136 pthread_mutex_unlock (&mutex[2]);
137 sched_yield ();
138 }
139 return NULL;
140 } 141
142 int main (int argc, char *argv[])
143 {
144 pthread_t forward, backward;
145 int status;
146
147 #ifdef sun
148 /*
149 * On Solaris 2.5, threads are not timesliced. To ensure
150 * that our threads can run concurrently, we need to
151 * increase the concurrency level.
152 */
153 DPRINTF (('Setting concurrency level to 2
'));
154 thr_setconcurrency (2);
155 #endif
156
157 /*
158 * If the first argument is absent, or nonzero, a backoff
159 * algorithm will be used to avoid deadlock. If the first
160 * argument is zero, the program will deadlock on a lock
161 * 'collision.'
162 */
163 if (argc > 1)
164 backoff = atoi (argv[l]);
165
166 /*
167 * If the second argument is absent, or zero, the two threads
168 * run 'at speed.' On some systems, especially uniprocessors,
169 * one thread may complete before the other has a chance to run,
170 * and you won't see a deadlock or backoffs. In that case, try
171 * running with the argument set to a positive number to cause
172 * the threads to call sched_yield() at each lock; or, to make
173 * it even more obvious, set to a negative number to cause the
174 * threads to call sleep(l) instead.
175 */
176 if (argc > 2)
177 yield_flag = atoi (argv[2]);
178 status = pthread_create (
179 &forward, NULL, lock_forward, NULL);
180 if (status != 0)
181 err_abort (status, 'Create forward');
182 status = pthread_create (
183 &backward, NULL, lock_backward, NULL);
184 if (status != 0)
185 err_abort (status, 'Create backward');
186 pthread_exit (NULL);
187 }

Whatever type of hierarchy you choose, document it, carefully, completely, and often. Document it in each function that uses any of the mutexes. Document it where the mutexes are defined. Document it where they are declared in a project

header file. Document it in the project design notes. Write it on your whiteboard. And then tie a string around your finger to be sure that you do not forget.

You are free to unlock the mutexes in whatever order makes the most sense. Unlocking mutexes cannot result in deadlock. In the next section, I will talk about a sort of 'overlapping hierarchy' of mutexes, called a 'lock chain,' where the normal mode of operation is to lock one mutex, lock the next, unlock the first, and so on. If you use a 'try and back off algorithm, however, you should always try to release the mutexes in reverse order. That is, if you lock mutex 1, mutex 2, and then mutex 3, you should unlock mutex 3, then mutex 2, and finally mutex 1. If you unlock mutex 1 and mutex 2 while mutex 3 is still locked, another thread may have to lock both mutex 1 and mutex 2 before finding it cannot lock the entire hierarchy, at which point it will have to unlock mutex 2 and mutex 1, and then retry. Unlocking in reverse order reduces the chance that another thread will need to back off.

3.2.5.2 Lock chaining

'Chaining' is a special case of locking hierarchy, where the scope of two locks overlap. With one mutex locked, the code enters a region where another mutex is required. After successfully locking that second mutex, the first is no longer needed, and can be released. This technique can be very valuable in traversing data structures such as trees or linked lists. Instead of locking the entire data structure with a single mutex, and thereby preventing any parallel access, each node or link has a unique mutex. The traversal code would first lock the queue head, or tree root, find the desired node, lock it, and then release the root or queue head mutex.

Because chaining is a special form of hierarchy, the two techniques are compatible, if you apply them carefully. You might use hierarchical locking when balancing or pruning a tree, for example, and chaining when searching for a specific node.

Apply lock chaining with caution, however. It is exceptionally easy to write code that spends most of its time locking and unlocking mutexes that never exhibit any contention, and that is wasted processor time. Use lock chaining only when multiple threads will almost always be active within different parts of the hierarchy.

3.3 Condition variables

'There's no sort of use in knocking,' said the Footman, 'and that for two reasons. First, because I'm on the same side of the door as you are: secondly, because they're making such a noise inside, no one could possibly hear you.'

— Lewis Carroll, Alice's Adventures in Wonderland