CS 241: Deadlock Resilient Mutex



Due: Monday, Dec. 3, 2012 at 11:59pm

Introduction

This MP will help you to be familiar with POSIX mutex locks in C. POSIX mutexes are prone to deadlocks and contain no deadlock prevention, detection, or avoidance mechanisms. In this MP, you will be writing a C library that extends POSIX mutexes allowing for deadlock prevention, detection, and avoidance.

To make the programming easier, we split this MP up into two unique parts: the deadlock resilient mutexes part and the wait-for graph part (as detecting deadlocks in mutexes require checking for cycles inside a wait-for graph).

Tasks

[Part 1]

Complete the wait-for graph library (libwfg) functions. You will need to edit both libwfg.c and libwfg.h to complete this part. We have provided testwfg.c to allow you to test your wait-for graph independently of the rest of this MP.

We have also provided you with our standard queue data structure. You can use this as either a queue or a vector if you need to store lists of data for either part of this MP.

[Part 2]

Complete the deadlock resilient mutex (libdrm) functions. You will need to edit both libdrm.c and libdrm.h to complete this part.

As part of implementing libdrm, you will find that the drm_setmode() function takes in four different modes that your library must operate under. Your library should behave in the following way, based on the mode set in drm_setmode():

• NO_DEADLOCK_CHECKING: Your mutexes should run identically to pthread mutexes. (This does not require a libwfg.)
  
  
• DEADLOCK_PREVENTION: You must prevent deadlocks by ensuring that your mutexes are acquired in a strict order. (This does not require a libwfg.)
  
  If a specific threads needs access to mutexes r1, r2, and r3, drm_lock() must fail if:
  • The user tries to drm_lock() on r1 after the user already acquired a drm_lock() on r2 or r3.
  • The user tries to drm_lock() on r2 after the user already acquired a drm_lock() on r3.
  
  In this method, every thread must get the lower ID mutex first. By doing this, we prevent any possible cycles in the wait-for graph (without even building a wait-for graph).
  
  For this method, the first mutex to call drm_init() should be considered to have the "lower ID" and must be acquired first. The following code shows how the example above relates directly to code:

  drm_init(&mutex1); /* r1 */
  drm_init(&mutex2); /* r2 */
  drm_init(&mutex3); /* r3 */
  

• DEADLOCK_AVOIDANCE: You must prevent deadlocks by constructing a wait-for graph. When a thread attempts to acquire a lock (by calling drm_lock()), check if granting the request would result in a cycle in the graph. If a cycle would exist, the drm_lock() call must fail (and remember to remove the edge you added!). If a cycle doesn't exist, the call is successful.
  
  In order to check if a cycle would exist at any point in the graph, you will need to update the wait-for graph every time your library changes the state of a mutex.
  
  In this method, no thread is allowd to make a request that would result in a cycle. Since a cycle is a condition of deadlock, we avoid deadlock.
  
  
• DEADLOCK_DETECTION: Always grant the lock, just like NO_DEADLOCK_CHECKING. However, you must also launch a single thread that periodicly checks if a cycle currently exists in the wait-for graph. Similiar to DEADLOCK_AVOIDANCE, you will need to constantly maintain a wait-for graph of your current state.
  
  In th thread:
  
  • call wfg_print_graph() to output the current state of your program,
  • check if a cycle exists in the wait-for graph,
  • if a cycle does exist: randomly (rand()) choose one of the threads to notify to release its locks (explained below), and
  • sleep for one second by calling sleep(1) (this is the only time you will ever be allowed to use sleep() in CS 241)
  
  To notify a thread to release its locks, we will be using a signal. It's not necessary to understand how a singal works at this point (you will learn about it in CS 241 later if you haven't already), but you can signal the thread by running the following line of code:

  pthread_kill(thread_id, SIGUSR1);

  ...where thread_id is the ID of the thread you wish to signal.

In order to complete these functions, you will need to create your own mutexes to protect your own access to libwfg from within libdrm. Each drm_t will also need to contain a pthread_mutex_t in order to actually preform the underlying locking and unlocking that is requried as part of the mutex. Since you are preventing or avoiding deadlock, you may not always actaully call the underlying pthread_mutex_lock() if it may cause a deadlock.

Test Files

We have provided you with five test programs for you:

• testwfg, to test your wait-for graph
• example-NDC, an example with NO_DEADLOCK_CHECKING
• example-DP, an example with DEADLOCK_PREVENTION
• example-DA, an example with DEADLOCK_AVOIDANCE
• example-DD, an example with DEADLOCK_DETECTION

Feel free to modify or change these examples. The only files that are picked up by the autograder for this MP are libwfg.c, libwfg.h, libdrm.c, and libdrm.h.

Compile / Run

To compile, run the following commands from a command prompt on a Linux machine:

$ make clean
$ make

To run the example code:

$ ./testwfg
$ ./example-NDC
$ ./example-DP
$ ./example-DA
$ ./example-DD