spthread (Smart pthread)
by Kevin Prewitt & Steven Zhang
Building upon the pthread library, we are going to develop threading library which is able to detect deadlocks caused by mutexes and either back away from deadlocks or abort. Using graph theoretic ideas, we will design or implement a way to recognize cyclic dependencies between threads/mutexes. Once one is recognized, the library takes certain measures to recover from the deadlocks or abort based on predefined user options.
As has been discussed in detail in class, deadlock is a large issue for parallel programs. If a programmer is careless, it is possible for locks to be handed out in such a way that a program is completely unable to proceed. Of course, due to the nature of programming, this means that most programmers will write deadlocks into their programs at some point. However, what if there was a better way for mutexes to be implemented which could detect and report and even resolve deadlocks conditions itself?
In general, a deadlock will occur when there is a cycle of dependencies between threads, where Thread A holds a lock Thread B needs, while Thread B is holding a lock that another thread needs, and so on, until one of these locks is needed by Thread A. However, this can be represented as a bipartite graph with threads on one side and locks on the other. In this graph, there is an edge from a thread to a lock if the thread needs that lock, and an edge from a lock to a thread if the thread currently holds that lock. In this case, there will be deadlock if there is a cycle in this graph. However, this can be computed, so we can calculate if one of these cycles exist, and thus help deal with the deadlock without needing the help of the programmer.
After we detect a deadlock, we can of course kill some of the threads to allow progress or simply abort. But it is also possible we can recover from a deadlock by unlocking one mutex to break the chain and revert the thread who locked that mutex back to the state before it locked the mutex. As a preliminary though, this can be implemented by keeping a write buffer/undo log in every mutex to allow for reversion, and the reversion is most likely to be the user's responsibility.
We would need to modify locks in such a way that they are able to know when they have run into deadlock conditions. In order to do this, we need to keep track of which threads have which locks at each point, in addition to which threads need which locks to progress. Then, having done this, we need to be able to detect cycles in these dependencies. Additional synchronization might be required upon creating new threads and mutexes because they need to be made globally accessible by every other thread and mutex. To be able to recover from deadlock is also challenging since we are not entirely sure how we should do it.
We will be using the Gates machines to develop and test our code. We believe that there exist papers talking about this subject, some of which may describe algorithms that have been developed to work on this exact problem. However, we do not have any of them currently, so we will be looking for these throughout the first week of the project. We will be starting from the mutexes of the pthread library, as these are what we are trying to improve. Through these, and through the algorithms described in any existing papers about this subject, we should be able to make our additions to the pthread library.
Goals & Deliverables
Our goal is to develop a wrapper around pthread that is able to detect deadlock and either abort or back out of the deadlock.
The achievement of the goal is verified by running certain test programs which we know will have deadlock issues. We will be spending much time designing these test programs as well as reusing some of the example deadlocking programs mention in lecture in order to verify our results.
We will be developing in C for this language this, since our project is an extension to the pthread C library.
Look for extant research on the topic of deadlock and race condition detection. Develop a clear description of what our code should do. Either find a paper with a relevant algorithm that is feasible for us to implement or come up with an outline of our own algorithm to tackle this problem.
By this time we should have our algorithm either on a paper or whiteboard. Implement the algorithm.
Debug and run small test cases on our code.
Design and implement a couple larger test cases that really show that our mutex can detect and back out from deadlocks.
Make our presentation for our project.