6.830 Lab 3 notes Dan Ports This lab implements transactional isolation via locking with deadlock detection. Locks have a page-level granularity, and are implemented through a LockManager class, which contains records for each current page in the system, with associated locks. BufferPool.getPage() calls the LockManager to obtain either a shared or exclusive lock, as appropriate for the permissions requested. Locks are released only on transaction commit or abort, i.e. from BufferPool.transactionCompleted(). Implementing aborts also required adding support for clearing pages from the buffer pool without flushing them. This is done on transction abort to clear all changes made; the old copy is restored from disk the next time it is needed. Also, the buffer pool size was increased to 4096 pages; this should be large enough to accommodate all tables used in testing, and is about 16 MB of cache, which is about 25% of the 64 MB allocated for the Java VM. Two different deadlock detectors (one of which has some bugs) are included. To support different deadlock detection policies, a DeadlockDetector interface is provided. The LockManager instantiates a DeadlockDetector, and calls it before and after a lock is acquired, as well as when transactions complete or abort. An AbstractDeadlockDetector provides some additional helpful functionality for tracking the reports of lock requests and acquisitions. In addition, it contains the implementations for aborting transactions. When a deadlock is detected, one of the blocked transactions is selected arbitrarily. It is aborted by interrupting the thread that is executing the transaction (and currently waiting on a lock). Since the thread might have been interrupted for other reasons, the lock manager calls a function in the deadlock detector to check whether that transaction has been aborted, and if so throws a TransactionAbortedException. The simplest deadlock detection policy is a timeout-based one. This is implemented as the TimeoutDeadlockDetector, which functions by spawning a separate thread that periodically checks how long lock requests have been pending. If any of them have been pending for too long (greater than some specified timeout), they are aborted. The thread is marked as a daemon so it won't prevent the Java VM from exiting when the queries complete. A more complex, and more efficient deadlock detection policy is based on searching for cycles in the waits-for graph. This is fairly easy to implement using the information tracked by the AbstractDeadlockDetector. It's implemented as the WaitsForDeadlockDetector, but the implementation is still buggy. It passes the DeadlockTest unit test, but not grader test 7. If working, however, it should be a better design than the TimeoutDeadlockDetector in several key respects: it is correct even for long-running transactions (which might cause other transactions to time out); it is more efficient since it doesn't require running the daemon thread periodically to check for timeouts; and it detects deadlocks instantly rather than waiting for the timeout.