Home CPSC 425

Lab 3: Deadlock

Objective

To identify and resolve deadlock in a threaded program.


Task

This lab will deal with the 03-deadlock.c program. This program simulates bank account transactions. It keeps an array of bank account balances, and an array of mutexes to lock each account.

The program takes input files that contain lines of the following form:

from to amount

Which specifies that the "from" account should transfer "amount" to the "to" account.

For example, this line:

1 3 75.00

Indicates that account 1 should transfer $75.00 to account 3.

The program uses 4 accounts numbered (0, 1, 2, 3) and spawns four threads to perform these transactions. Use the following test files:

Each thread will open its file, and perform the transactions one by one until it hits the end. It must lock each account it touches before executing a transaction.

However, this program can deadlock! If you run it enough times, it will at some point hang forever.

Your job is to figure out why and fix it!


Details

  1. Download and run the 03-deadlock.c program. You must download the four test files as well.
  2. Observe that the program can deadlock.
  3. Figure out why the program deadlocks either by inserting print statements, or through carefully thinking over how the program works.
  4. Fix the program so it can no longer cause deadlock.
  5. If you want to run the program several times automatically to test for deadlock, you can use a script like the following:
    
    #!/bin/bash
    
    for i in $(seq 1 100)
    do
        ./a.out
    done
    
  6. Make sure to reason about the code to ensure that the program can't deadlock. Just because it doesn't deadlock, doesn't mean it can't.

Submitting

When you have gotten the program to run without deadlock, send the code to ifinlay@umw.edu. In the email body, include a brief description of what caused the deadlock and how you fixed it.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.