Lab 9: Deadlock Detection

  • Course: COSC 460 Databases Fall 2018
  • Instructor: Michael Hay
  • Assignment: Lab 9: Deadlock Detection
  • Due: Mon, Nov 19 at 11:59 PM
  • Starter code: lab9.zip

Introduction

This is a continuation of the previous lab. To your existing Lock Manager implementation, we add the ability to detect deadlock.

Environment setup

See previous labs.

Saving and accessing your files

See previous labs.

Assignment overview

You should take a moment to review the details from the previous lab about deadlock detection. Here are additional details to consider.

  • Deadlock detection There are many possible ways to detect deadlock. For example, you may implement a simple timeout policy that aborts a transaction if it has not completed after a given period of time. Alternately, as an additional challenge problem, you may implement cycle-detection in a dependency graph data structure. In this scheme, you would check for cycles in a dependency graph whenever you attempt to grant a new lock, and abort something if a cycle exists.
  • Timeout duration If you go with the timeout approach, how long should you wait? There’s no simple answer. Suggested implementation: wait a random period of time between 100 milliseconds and 200 milliseconds. The randomness helps avoid the situation where multiple transactions start waiting at exactly the same time and thus timeout at the same time, preventing any one of them from making progress.
  • Choosing a victim After you have detected that a deadlock exists, you must decide how to improve the situation. Assume you have detected a deadlock while transaction t is waiting for a lock. The simplest strategy is to simply abort t. This is acceptable but you should be aware of the potential downsides of this simple strategy.
  • Cleaning up Once deadlock is detected and you have chosen a victim, you must do a little clean up before aborting the victim. You should not release the victim’s locks. This will be handled by other mechanisms outside of the LockManager. However, you should remove any outstanding requests (there should be only one). In addition, if you implement the waits for graph approach, be sure to clean up the graph. There are two cases:
    • Lock acquired on page p: this transaction is no longer waiting. At a minimum, any edges added while waiting for p can be removed. But, depending on your implementation, it may be acceptable to simply remove the transaction from the graph (provided that other waiting transactions can add it back as necessary).
    • Transaction aborted: it’s sufficient to remove all outgoing edges from the victim transaction since the victim is about to abort and therefore no longer waiting on any other transaction.

Starter code

You are expected to modify these files:

  • LockManagerImpl.java

You are expected to read but not modify the other files that were provided.

Tasks

  • Task 0 Run the new unit tests provided LockScheduleMoreTest. If your current implementation does not pass these tests, be sure to address them before moving on to deadlock detection.
  • Task 1 Implement a mechanism for deadlock detection. When complete, you should be able to pass DeadlockTest. DeadlockTest runs a series of tests that you should be able to pass regardless of which implementation you choose for deadlock.

Milestone

The milestone for this lab will be to complete the above tasks and pass the tests described above. In addition, please submit your code for a labs 8 and 9 code review.

Submission instructions

Upload your files to Gradescope twice: once to lab9 and once to lab89codereview.