The last modification in my series about ticket locks is about aborting locks. In an ideal world every function waiting on a mutex will eventually obtain it. However, there are times we would like a blocking function to stop blocking but not get the mutex. The most common example is during application shutdown when we need all threads to stop blocking and rejoin the main thread.
Our ticket lock implementation uses conditional variables to signal threads waiting for the mutex that the mutex has been released. During an abort we simple need to signal the waiting threads but have a flag that denotes the mutex is aborting. This information needs to be relayed to the parent function requesting the lock, and that function needs to check this status. If the lock didn’t take place, the mutex wasn’t obtained, and whatever operations were supposed to happen should be aborted. In C++ throwing an exception would be appropriate. For our C implementation, simple returning a failure code for the mutex lock will suffice.
There are just two changes and one new function. The ticket lock context will get a flag called isRunning. By default this flag is true. When forcibly shutting down, the flag is set to false. A new function called ticketLockShutdown sets the flag to false, and broadcasts a condition change to all blocking threads. The last change is in the while loop used to wait for the desired ticket number. It will additionally stop if isRunning is not set and return an error should that condition arise.
First, what is meant by recursion? A mutex is usually used to isolate a resource so only one thread can use it at a time. Typically a mutex is used to a wrapped critical section. The critical section starts with the mutex being locked and ends when the mutex is released. It is a good practice to keep critical sections short as not to starve other threads that may want the resource.
Now consider that you have a resource used in several smaller functions, but also in larger functions. Think of a scenario where there are functions to print a header, body, and footer as well as a function to print the entire page that calls each of the proceeding functions. The header, body and footer functions all use a mutex to lock the print function. However, the print page function wants to lock the print function so that the entire page is not interrupted.
If the page function calls the individual header, body and footer functions, there is the chance another thread could grab the mutex after the header or body and insert text. This is especially true with a ticket lock where mutex request order is guaranteed. The page function could re-implement the header, body and footer functions and wrap them all with the mutex but that is bad pratice. What would be best is if the page function could simple request the mutex, call each of the sub-functions that also request the mutex, and then release the mutex. What we want is a recursive mutex.
A recursive mutex allows the same thread to make multiple requests for a mutex lock. The most basic mutex could dead lock itself by simply requesting the same mutex twice. The first lock it will get, but the second lock it can never get because it didn’t release the lock it already had. Many mutex implementation allow a thread to obtain a mutex if the it is the same thread already holding the lock. In addition, such implementations also require the same number of unlocks as locks before the mutex is freed by a thread. That is, if a thread requests a mutex 3 times, it must release it 3 times before the mutex actually becomes free. We would like this functionality extended to a ticket lock.
So what additional requirements are there for a recursive ticket lock? The mutex only needs to know the ID of the thread which currently holds the lock, and a count of how many times the current thread has locked the mutex. If the mutex is already locked, but the locking thread ID matches the current thread ID, the lock count is increased and there is no block. When unlocking the mutex, the lock count is decreased. If the count is zero, the mutex is actually released. If the count is not zero, the lock remains.
You almost always desire a recursive ticket lock implementation. The only item to consider is that you must have the same number of locks as unlocks or you can create a deadlock. Combine with single-entry single exit practices and starting/ending functions with lock/unlock virtually guarantees there will never be deadlock. Since the mutex is recursive all functions that use the resource can use their own lock/unlock and not have to worry about resource overlap or deadlock.
I wrote about the theory of a ticket lock and would now like to explore an example. First we need to demonstrate what can happen without a ticket lock. The implementations will use POSIX threads (pthreads).
In this example several threads are created that all want the print resource. The thread hogs the resource by releasing the lock but immediately asking for the lock again. Typically what one will expect to see is a single thread printing its ID over and over, occasionally switching to another. The switch can happen if the operating system does a task switch just after the lock is released. Rare but it will eventually happen. The exact results will depend on the environment.
Now the same example, but with the addition of ticket locks.
In this example, the first string of output can vary depending on the sleep time. However, that sequence will repeat thereafter.
Something to note about pthread conditional variables. There are two signaling functions available, pthread_cond_signal and pthread_cond_broadcast. The broadcast alerts all waiting threads, but the signal will just signal one of the threads. We need to use broadcast because the thread that gets notified in a single signal might not be the next ticket holder and the process will deadlock.
I have found that the hog example is identical to the ticket lock example when compiled under Cygwin. This is likely because the mutex the port of pthreads is using in this environment is already a ticket lock.