cs186-proj4-supplement.tar

cs186-proj4/000755 000765 000024 00000000000 12235677547 012523 5ustar00Lustaff000000 000000 cs186-proj4/test/000755 000765 000024 00000000000 12235677406 013474 5ustar00Lustaff000000 000000 cs186-proj4/test/simpledb/000755 000765 000024 00000000000 12235677406 015273 5ustar00Lustaff000000 000000 cs186-proj4/test/simpledb/DeadlockTest.java000644 000765 000024 00000016470 12235677406 020514 0ustar00Lustaff000000 000000 package simpledb;

import simpledb.TestUtil.LockGrabber;

import java.util.*;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import junit.framework.JUnit4TestAdapter;

public class DeadlockTest extends TestUtil.CreateHeapFile {
  private PageId p0, p1, p2;
  private TransactionId tid1, tid2;
  private Random rand;

  private static final int POLL_INTERVAL = 100;
  private static final int WAIT_INTERVAL = 200;

  // just so we have a pointer shorter than Database.getBufferPool
  private BufferPool bp;

  /**
   * Set up initial resources for each unit test.
   */
  @Before public void setUp() throws Exception {
    super.setUp();

    // clear all state from the buffer pool
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);

    // create a new empty HeapFile and populate it with three pages.
    // we should be able to add 512 tuples on an empty page.
    TransactionId tid = new TransactionId();
    for (int i = 0; i < 1025; ++i) {
      empty.insertTuple(tid, Utility.getHeapTuple(i, 2));
    }

    // if this fails, complain to the TA
    assertEquals(3, empty.numPages());

    this.p0 = new HeapPageId(empty.getId(), 0);
    this.p1 = new HeapPageId(empty.getId(), 1);
    this.p2 = new HeapPageId(empty.getId(), 2);
    this.tid1 = new TransactionId();
    this.tid2 = new TransactionId();
    this.rand = new Random();

    // forget about locks associated to tid, so they don't conflict with
    // test cases
    bp.getPage(tid, p0, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p1, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p2, Permissions.READ_WRITE).markDirty(true, tid);
    bp.flushAllPages();
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);
  }

  /**
   * Helper method to clean up the syntax of starting a LockGrabber thread.
   * The parameters pass through to the LockGrabber constructor.
   */
  public TestUtil.LockGrabber startGrabber(TransactionId tid, PageId pid,
      Permissions perm) {

    LockGrabber lg = new LockGrabber(tid, pid, perm);
    lg.start();
    return lg;
  }

  /**
   * Not-so-unit test to construct a deadlock situation.
   * t1 acquires p0.read; t2 acquires p1.read; t1 attempts p1.write; t2
   * attempts p0.write. Rinse and repeat.
   */
  @Test public void testReadWriteDeadlock() throws Exception {
    System.out.println("testReadWriteDeadlock constructing deadlock:");

    LockGrabber lg1Read = startGrabber(tid1, p0, Permissions.READ_ONLY);
    LockGrabber lg2Read = startGrabber(tid2, p1, Permissions.READ_ONLY);

    // allow read locks to acquire
    Thread.sleep(POLL_INTERVAL);

    LockGrabber lg1Write = startGrabber(tid1, p1, Permissions.READ_WRITE);
    LockGrabber lg2Write = startGrabber(tid2, p0, Permissions.READ_WRITE);

    while (true) {
      Thread.sleep(POLL_INTERVAL);

      assertFalse(lg1Write.acquired() && lg2Write.acquired());
      if (lg1Write.acquired() && !lg2Write.acquired()) break;
      if (!lg1Write.acquired() && lg2Write.acquired()) break;

      if (lg1Write.getError() != null) {
        lg1Read.stop(); lg1Write.stop();
        bp.transactionComplete(tid1);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid1 = new TransactionId();
        lg1Read = startGrabber(tid1, p0, Permissions.READ_ONLY);
        lg1Write = startGrabber(tid1, p1, Permissions.READ_WRITE);
      }

      if (lg2Write.getError() != null) {
        lg2Read.stop(); lg2Write.stop();
        bp.transactionComplete(tid2);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid2 = new TransactionId();
        lg2Read = startGrabber(tid2, p1, Permissions.READ_ONLY);
        lg2Write = startGrabber(tid2, p0, Permissions.READ_WRITE);
      }
    }

    System.out.println("testReadWriteDeadlock resolved deadlock");
  }

  /**
   * Not-so-unit test to construct a deadlock situation.
   * t1 acquires p0.write; t2 acquires p1.write; t1 attempts p1.write; t2
   * attempts p0.write.
   */
  @Test public void testWriteWriteDeadlock() throws Exception {
    System.out.println("testWriteWriteDeadlock constructing deadlock:");

    LockGrabber lg1Write0 = startGrabber(tid1, p0, Permissions.READ_WRITE);
    LockGrabber lg2Write1 = startGrabber(tid2, p1, Permissions.READ_WRITE);

    // allow initial write locks to acquire
    Thread.sleep(POLL_INTERVAL);

    LockGrabber lg1Write1 = startGrabber(tid1, p1, Permissions.READ_WRITE);
    LockGrabber lg2Write0 = startGrabber(tid2, p0, Permissions.READ_WRITE);

    while (true) {
      Thread.sleep(POLL_INTERVAL);

      assertFalse(lg1Write1.acquired() && lg2Write0.acquired());
      if (lg1Write1.acquired() && !lg2Write0.acquired()) break;
      if (!lg1Write1.acquired() && lg2Write0.acquired()) break;

      if (lg1Write1.getError() != null) {
        lg1Write0.stop(); lg1Write1.stop();
        bp.transactionComplete(tid1);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid1 = new TransactionId();
        lg1Write0 = startGrabber(tid1, p0, Permissions.READ_WRITE);
        lg1Write1 = startGrabber(tid1, p1, Permissions.READ_WRITE);
      }

      if (lg2Write0.getError() != null) {
        lg2Write0.stop(); lg2Write1.stop();
        bp.transactionComplete(tid2);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid2 = new TransactionId();
        lg2Write0 = startGrabber(tid2, p1, Permissions.READ_WRITE);
        lg2Write1 = startGrabber(tid2, p0, Permissions.READ_WRITE);
      }
    }

    System.out.println("testWriteWriteDeadlock resolved deadlock");
  }

  /**
   * Not-so-unit test to construct a deadlock situation.
   * t1 acquires p0.read; t2 acquires p0.read; t1 attempts to upgrade to
   * p0.write; t2 attempts to upgrade to p0.write
   */
  @Test public void testUpgradeWriteDeadlock() throws Exception {
    System.out.println("testUpgradeWriteDeadlock constructing deadlock:");

    LockGrabber lg1Read = startGrabber(tid1, p0, Permissions.READ_ONLY);
    LockGrabber lg2Read = startGrabber(tid2, p0, Permissions.READ_ONLY);

    // allow read locks to acquire
    Thread.sleep(POLL_INTERVAL);

    LockGrabber lg1Write = startGrabber(tid1, p0, Permissions.READ_WRITE);
    LockGrabber lg2Write = startGrabber(tid2, p0, Permissions.READ_WRITE);

    while (true) {
      Thread.sleep(POLL_INTERVAL);

      assertFalse(lg1Write.acquired() && lg2Write.acquired());
      if (lg1Write.acquired() && !lg2Write.acquired()) break;
      if (!lg1Write.acquired() && lg2Write.acquired()) break;

      if (lg1Write.getError() != null) {
        lg1Read.stop(); lg1Write.stop();
        bp.transactionComplete(tid1);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid1 = new TransactionId();
        lg1Read = startGrabber(tid1, p0, Permissions.READ_ONLY);
        lg1Write = startGrabber(tid1, p0, Permissions.READ_WRITE);
      }

      if (lg2Write.getError() != null) {
        lg2Read.stop(); lg2Write.stop();
        bp.transactionComplete(tid2);
        Thread.sleep(rand.nextInt(WAIT_INTERVAL));

        tid2 = new TransactionId();
        lg2Read = startGrabber(tid2, p0, Permissions.READ_ONLY);
        lg2Write = startGrabber(tid2, p0, Permissions.READ_WRITE);
      }
    }

    System.out.println("testUpgradeWriteDeadlock resolved deadlock");
  }

  /**
   * JUnit suite target
   */
  public static junit.framework.Test suite() {
    return new JUnit4TestAdapter(DeadlockTest.class);
  }

}

cs186-proj4/test/simpledb/LockingTest.java000644 000765 000024 00000014561 12235677406 020373 0ustar00Lustaff000000 000000 package simpledb;

import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNull;
import junit.framework.JUnit4TestAdapter;

public class LockingTest extends TestUtil.CreateHeapFile {
  private PageId p0, p1, p2;
  private TransactionId tid1, tid2;

  /** Time to wait before checking the state of lock contention, in ms */
  private static final int TIMEOUT = 100;

  // just so we have a pointer shorter than Database.getBufferPool()
  private BufferPool bp;

  /**
   * Set up initial resources for each unit test.
   */
  @Before public void setUp() throws Exception {
    super.setUp();

    // clear all state from the buffer pool
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);

    // create a new empty HeapFile and populate it with three pages.
    // we should be able to add 512 tuples on an empty page.
    TransactionId tid = new TransactionId();
    for (int i = 0; i < 1025; ++i) {
      empty.insertTuple(tid, Utility.getHeapTuple(i, 2));
    }

    // if this fails, complain to the TA
    assertEquals(3, empty.numPages());

    this.p0 = new HeapPageId(empty.getId(), 0);
    this.p1 = new HeapPageId(empty.getId(), 1);
    this.p2 = new HeapPageId(empty.getId(), 2);
    this.tid1 = new TransactionId();
    this.tid2 = new TransactionId();

    // forget about locks associated to tid, so they don't conflict with
    // test cases
    bp.getPage(tid, p0, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p1, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p2, Permissions.READ_WRITE).markDirty(true, tid);
    bp.flushAllPages();
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);
  }

  /**
   * Generic unit test structure for BufferPool.getPage() assuming locking.
   *
   * @param tid1 the first transaction Id
   * @param pid1 the first page to lock over
   * @param perm1 the type of lock for the first page
   * @param tid2 the second transaction Id
   * @param pid2 the second page to lock over
   * @param perm2 the type of lock for the second page
   * @param expected true if we expect the second acquisition to succeed;
   *   false otherwise
   */
  public void metaLockTester(
      TransactionId tid1, PageId pid1, Permissions perm1,
      TransactionId tid2, PageId pid2, Permissions perm2,
      boolean expected) throws Exception {

    bp.getPage(tid1, pid1, perm1);
    grabLock(tid2, pid2, perm2, expected);
  }

  /**
   * Generic unit test structure to grab an additional lock in a new
   * thread.
   *
   * @param tid the transaction Id
   * @param pid the first page to lock over
   * @param perm the type of lock desired
   * @param expected true if we expect the acquisition to succeed;
   *   false otherwise
   */
  public void grabLock(TransactionId tid, PageId pid, Permissions perm,
      boolean expected) throws Exception {

    TestUtil.LockGrabber t = new TestUtil.LockGrabber(tid, pid, perm);
    t.start();

    // if we don't have the lock after TIMEOUT, we assume blocking.
    Thread.sleep(TIMEOUT);
    assertEquals(expected, t.acquired());
    assertNull(t.getError());

    // TODO(ghuo): yes, stop() is evil, but this is unit test cleanup
    t.stop();
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires two read locks on the same page.
   */
  @Test public void acquireReadLocksOnSamePage() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_ONLY,
                   tid2, p0, Permissions.READ_ONLY, true);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires a read lock and a write lock on the same page, in that order.
   */
  @Test public void acquireReadWriteLocksOnSamePage() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_ONLY,
                   tid2, p0, Permissions.READ_WRITE, false);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires a write lock and a read lock on the same page, in that order.
   */
  @Test public void acquireWriteReadLocksOnSamePage() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_WRITE,
                   tid2, p0, Permissions.READ_ONLY, false);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires a read lock and a write lock on different pages.
   */
  @Test public void acquireReadWriteLocksOnTwoPages() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_ONLY,
                   tid2, p1, Permissions.READ_WRITE, true);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires write locks on different pages.
   */
  @Test public void acquireWriteLocksOnTwoPages() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_WRITE,
                   tid2, p1, Permissions.READ_WRITE, true);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Acquires read locks on different pages.
   */
  @Test public void acquireReadLocksOnTwoPages() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_ONLY,
                   tid2, p1, Permissions.READ_ONLY, true);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * Attempt lock upgrade.
   */
  @Test public void lockUpgrade() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_ONLY,
                   tid1, p0, Permissions.READ_WRITE, true);
    metaLockTester(tid2, p1, Permissions.READ_ONLY,
                   tid2, p1, Permissions.READ_WRITE, true);
  }

  /**
   * Unit test for BufferPool.getPage() assuming locking.
   * A single transaction should be able to acquire a read lock after it
   * already has a write lock.
   */
  @Test public void acquireWriteAndReadLocks() throws Exception {
    metaLockTester(tid1, p0, Permissions.READ_WRITE,
                   tid1, p0, Permissions.READ_ONLY, true);
  }

  /**
   * Unit test for BufferPool.getPage() and BufferPool.releasePage()
   * assuming locking.
   * Acquires read locks on different pages.
   */
  @Test public void acquireThenRelease() throws Exception {
    bp.getPage(tid1, p0, Permissions.READ_WRITE);
    bp.releasePage(tid1, p0);
    bp.getPage(tid2, p0, Permissions.READ_WRITE);

    bp.getPage(tid2, p1, Permissions.READ_WRITE);
    bp.releasePage(tid2, p1);
    bp.getPage(tid1, p1, Permissions.READ_WRITE);
  }

  /**
   * JUnit suite target
   */
  public static junit.framework.Test suite() {
    return new JUnit4TestAdapter(LockingTest.class);
  }

}

cs186-proj4/test/simpledb/systemtest/000755 000765 000024 00000000000 12235677406 017517 5ustar00Lustaff000000 000000 cs186-proj4/test/simpledb/TransactionTest.java000644 000765 000024 00000007447 12235677406 021277 0ustar00Lustaff000000 000000 package simpledb;

import java.util.*;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.assertEquals;
import junit.framework.JUnit4TestAdapter;

public class TransactionTest extends TestUtil.CreateHeapFile {
  private PageId p0, p1, p2;
  private TransactionId tid1, tid2;

  // just so we have a pointer shorter than Database.getBufferPool()
  private BufferPool bp;

  /**
   * Set up initial resources for each unit test.
   */
  @Before public void setUp() throws Exception {
    super.setUp();

    // clear all state from the buffer pool
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);

    // create a new empty HeapFile and populate it with three pages.
    // we should be able to add 512 tuples on an empty page.
    TransactionId tid = new TransactionId();
    for (int i = 0; i < 1025; ++i) {
      empty.insertTuple(tid, Utility.getHeapTuple(i, 2));
    }

    // if this fails, complain to the TA
    assertEquals(3, empty.numPages());

    this.p0 = new HeapPageId(empty.getId(), 0);
    this.p1 = new HeapPageId(empty.getId(), 1);
    this.p2 = new HeapPageId(empty.getId(), 2);
    this.tid1 = new TransactionId();
    this.tid2 = new TransactionId();

    // forget about locks associated to tid, so they don't conflict with
    // test cases
    bp.getPage(tid, p0, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p1, Permissions.READ_WRITE).markDirty(true, tid);
    bp.getPage(tid, p2, Permissions.READ_WRITE).markDirty(true, tid);
    bp.flushAllPages();
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);
  }

  /**
   * Unit test for BufferPool.transactionComplete().
   * Try to acquire locks that would conflict if old locks aren't released
   * during transactionComplete().
   */
  @Test public void attemptTransactionTwice() throws Exception {
    bp.getPage(tid1, p0, Permissions.READ_ONLY);
    bp.getPage(tid1, p1, Permissions.READ_WRITE);
    bp.transactionComplete(tid1, true);

    bp.getPage(tid2, p0, Permissions.READ_WRITE);
    bp.getPage(tid2, p0, Permissions.READ_WRITE);
  }

  /**
   * Common unit test code for BufferPool.transactionComplete() covering
   * commit and abort. Verify that commit persists changes to disk, and
   * that abort reverts pages to their previous on-disk state.
   */
  public void testTransactionComplete(boolean commit) throws Exception {
    HeapPage p = (HeapPage) bp.getPage(tid1, p2, Permissions.READ_WRITE);

    Tuple t = Utility.getHeapTuple(new int[] { 6, 830 });
    t.setRecordId(new RecordId(p2, 1));

    p.insertTuple(t);
    p.markDirty(true, tid1);
    bp.transactionComplete(tid1, commit);

    // now, flush the buffer pool and access the page again from disk.
    bp = Database.resetBufferPool(BufferPool.DEFAULT_PAGES);
    p = (HeapPage) bp.getPage(tid2, p2, Permissions.READ_WRITE);
    Iterator<Tuple> it = p.iterator();

    boolean found = false;
    while (it.hasNext()) {
      Tuple tup = (Tuple) it.next();
      IntField f0 = (IntField) tup.getField(0);
      IntField f1 = (IntField) tup.getField(1);

      if (f0.getValue() == 6 && f1.getValue() == 830) {
        found = true;
        break;
      }
    }

    assertEquals(commit, found);
  }

  /**
   * Unit test for BufferPool.transactionComplete() assuing commit.
   * Verify that a tuple inserted during a committed transaction is durable
   */
  @Test public void commitTransaction() throws Exception {
    testTransactionComplete(true);
  }

  /**
   * Unit test for BufferPool.transactionComplete() assuming abort.
   * Verify that a tuple inserted during a committed transaction is durable
   */
  @Test public void abortTransaction() throws Exception {
    testTransactionComplete(false);
  }

  /**
   * JUnit suite target
   */
  public static junit.framework.Test suite() {
    return new JUnit4TestAdapter(TransactionTest.class);
  }

}

cs186-proj4/test/simpledb/systemtest/AbortEvictionTest.java000644 000765 000024 00000002566 12235677406 024003 0ustar00Lustaff000000 000000 package simpledb.systemtest;

import java.io.IOException;

import simpledb.*;

import static org.junit.Assert.*;
import org.junit.Test;

public class AbortEvictionTest extends SimpleDbTestBase {
    /** Aborts a transaction and ensures that its effects were actually undone.
     * This requires dirty pages to <em>not</em> get flushed to disk.
     */
    @Test public void testDoNotEvictDirtyPages()
            throws IOException, DbException, TransactionAbortedException {
        // Allocate a file with ~10 pages of data
        HeapFile f = SystemTestUtil.createRandomHeapFile(2, 512*10, null, null);
        Database.resetBufferPool(2);

        // BEGIN TRANSACTION
        Transaction t = new Transaction();
        t.start();

        // Insert a new row
        EvictionTest.insertRow(f, t);

        // The tuple must exist in the table
        boolean found = EvictionTest.findMagicTuple(f, t);
        assertTrue(found);
        // ABORT
        t.transactionComplete(true);

        // A second transaction must not find the tuple
        t = new Transaction();
        t.start();
        found = EvictionTest.findMagicTuple(f, t);
        assertFalse(found);
        t.commit();
    }

    /** Make test compatible with older version of ant. */
    public static junit.framework.Test suite() {
        return new junit.framework.JUnit4TestAdapter(AbortEvictionTest.class);
    }
}
cs186-proj4/test/simpledb/systemtest/TransactionTest.java000644 000765 000024 00000022572 12235677406 023517 0ustar00Lustaff000000 000000 package simpledb.systemtest;

import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.Arrays;

import org.junit.Test;

import simpledb.*;

import static org.junit.Assert.*;

/**
 * Tests running concurrent transactions.
 * You do not need to pass this test until lab3.
 */
public class TransactionTest extends SimpleDbTestBase {
    // Wait up to 10 minutes for the test to complete
    private static final int TIMEOUT_MILLIS = 10 * 60 * 1000;
    private void validateTransactions(int threads)
            throws DbException, TransactionAbortedException, IOException {
        // Create a table with a single integer value = 0
        HashMap<Integer, Integer> columnSpecification = new HashMap<Integer, Integer>();
        columnSpecification.put(0, 0);
        DbFile table = SystemTestUtil.createRandomHeapFile(1, 1, columnSpecification, null);

        ModifiableCyclicBarrier latch = new ModifiableCyclicBarrier(threads);
        XactionTester[] list = new XactionTester[threads];
        for(int i = 0; i < list.length; i++) {
            list[i] = new XactionTester(table.getId(), latch);
            list[i].start();
        }

        long stopTestTime = System.currentTimeMillis() + TIMEOUT_MILLIS;
        for (XactionTester tester : list) {
            long timeout = stopTestTime - System.currentTimeMillis();
            if (timeout <= 0) {
                fail("Timed out waiting for transaction to complete");
            }
            try {
                tester.join(timeout);
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            }
            if (tester.isAlive()) {
                fail("Timed out waiting for transaction to complete");
            }

            if (tester.exception != null) {
                // Rethrow any exception from a child thread
                assert tester.exception != null;
                throw new RuntimeException("Child thread threw an exception.", tester.exception);
            }
            assert tester.completed;
        }

        // Check that the table has the correct value
        TransactionId tid = new TransactionId();
        DbFileIterator it = table.iterator(tid);
        it.open();
        Tuple tup = it.next();
        assertEquals(threads, ((IntField) tup.getField(0)).getValue());
        it.close();
        Database.getBufferPool().transactionComplete(tid);
        Database.getBufferPool().flushAllPages();
    }

    private static class XactionTester extends Thread {
        private final int tableId;
        private final ModifiableCyclicBarrier latch;
        public Exception exception = null;
        public boolean completed = false;

        public XactionTester(int tableId, ModifiableCyclicBarrier latch) {
            this.tableId = tableId;
            this.latch = latch;
        }

        public void run() {
            try {
                // Try to increment the value until we manage to successfully commit
                while (true) {
                    // Wait for all threads to be ready
                    latch.await();
                    Transaction tr = new Transaction();
                    try {
                        tr.start();
                        SeqScan ss1 = new SeqScan(tr.getId(), tableId, "");
                        SeqScan ss2 = new SeqScan(tr.getId(), tableId, "");

                        // read the value out of the table
                        Query q1 = new Query(ss1, tr.getId());
                        q1.start();
                        Tuple tup = q1.next();
                        IntField intf = (IntField) tup.getField(0);
                        int i = intf.getValue();

                        // create a Tuple so that Insert can insert this new value
                        // into the table.
                        Tuple t = new Tuple(SystemTestUtil.SINGLE_INT_DESCRIPTOR);
                        t.setField(0, new IntField(i+1));

                        // sleep to get some interesting thread interleavings
                        Thread.sleep(1);

                        // race the other threads to finish the transaction: one will win
                        q1.close();

                        // delete old values (i.e., just one row) from table
                        Delete delOp = new Delete(tr.getId(), ss2);

                        Query q2 = new Query(delOp, tr.getId());

                        q2.start();
                        q2.next();
                        q2.close();

                        // set up a Set with a tuple that is one higher than the old one.
                        HashSet<Tuple> hs = new HashSet<Tuple>();
                        hs.add(t);
                        TupleIterator ti = new TupleIterator(t.getTupleDesc(), hs);

                        // insert this new tuple into the table
                        Insert insOp = new Insert(tr.getId(), ti, tableId);
                        Query q3 = new Query(insOp, tr.getId());
                        q3.start();
                        q3.next();
                        q3.close();

                        tr.commit();
                        break;
                    } catch (TransactionAbortedException te) {
                        //System.out.println("thread " + tr.getId() + " killed");
                        // give someone else a chance: abort the transaction
                        tr.transactionComplete(true);
                        latch.stillParticipating();
                    }
                }
                //System.out.println("thread " + id + " done");
            } catch (Exception e) {
                // Store exception for the master thread to handle
                exception = e;
            }
            
            try {
                latch.notParticipating();
            } catch (InterruptedException e) {
                throw new RuntimeException(e);
            } catch (BrokenBarrierException e) {
                throw new RuntimeException(e);
            }
            completed = true;
        }
    }
    
    private static class ModifiableCyclicBarrier {
        private CountDownLatch awaitLatch;
        private CyclicBarrier participationLatch;
        private AtomicInteger nextParticipants;
        
        public ModifiableCyclicBarrier(int parties) {
            reset(parties);
        }
        
        private void reset(int parties) {
            nextParticipants = new AtomicInteger(0);
            awaitLatch = new CountDownLatch(parties);
            participationLatch = new CyclicBarrier(parties, new UpdateLatch(this, nextParticipants));
        }
        
        public void await() throws InterruptedException, BrokenBarrierException {
            awaitLatch.countDown();
            awaitLatch.await();
        }

        public void notParticipating() throws InterruptedException, BrokenBarrierException {
            participationLatch.await();
        }

        public void stillParticipating() throws InterruptedException, BrokenBarrierException {
            nextParticipants.incrementAndGet();
            participationLatch.await();
        }

        private static class UpdateLatch implements Runnable {
            ModifiableCyclicBarrier latch;
            AtomicInteger nextParticipants;
            
            public UpdateLatch(ModifiableCyclicBarrier latch, AtomicInteger nextParticipants) {
                this.latch = latch;
                this.nextParticipants = nextParticipants;
            }

            public void run() {
                // Reset this barrier if there are threads still running
                int participants = nextParticipants.get();
                if (participants > 0) {
                    latch.reset(participants);
                }
            }           
        }
    }
    
    @Test public void testSingleThread()
            throws IOException, DbException, TransactionAbortedException {
        validateTransactions(1);
    }

    @Test public void testTwoThreads()
            throws IOException, DbException, TransactionAbortedException {
        validateTransactions(2);
    }

    @Test public void testFiveThreads()
            throws IOException, DbException, TransactionAbortedException {
        validateTransactions(5);
    }
    
    @Test public void testTenThreads()
    throws IOException, DbException, TransactionAbortedException {
        validateTransactions(10);
    }

    @Test public void testAllDirtyFails()
            throws IOException, DbException, TransactionAbortedException {
        // Allocate a file with ~10 pages of data
        HeapFile f = SystemTestUtil.createRandomHeapFile(2, 512*10, null, null);
        Database.resetBufferPool(1);

        // BEGIN TRANSACTION
        Transaction t = new Transaction();
        t.start();

        // Insert a new row
        EvictionTest.insertRow(f, t);

        // Scanning the table must fail because it can't evict the dirty page
        try {
            EvictionTest.findMagicTuple(f, t);
            fail("Expected scan to run out of available buffer pages");
        } catch (DbException e) {}
        t.commit();
    }

    /** Make test compatible with older version of ant. */
    public static junit.framework.Test suite() {
        return new junit.framework.JUnit4TestAdapter(TransactionTest.class);
    }
}