Transaction

A. First Edition
This is the so-called project of comp346! What a shame! If this is known by other university, what would they 
think about Concordia?
B.The problem
[Comp346-w04] programming project (Feb 28) 
David K. Probst PROBST@vax2.concordia.ca 
Sat, 28 Feb 2004 19:39:30 -0400 (EDT) 

Previous message: [Comp346-w04] Information regarding Dr. Goswami's section (Section Y) 
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] 

--------------------------------------------------------------------------------

COMP 346                      Final Project                    Winter 2004
 
Issued: Week of March 1, 2004                Due: When teaching labs close

The project concerns the design and implementation of a transactional
programming abstraction.  There are 8 threads and 32 objects.  A data
structure indicates, for each thread, the set of objects it must have 
exclusive access to---by locking them in sequence---before proceeding
to perform a multi-object atomic update.  We pretend the thread is not
told the next object it needs to lock until it has acquired the lock
for this one.  (In the actual code, all the objects required for a
transaction are visible in 'objects_required[tid]' but we pretend you
have to lock the first object in this list before learning the identity
of the next object).

The whole idea is that threads who need access to the same objects cannot
agree on a lock order, and so risk deadlock.  For this reason, we build 
a special primitive that is deadlock free.

In particular, we build a "transaction primitive" with the following four
properties:

 - for each thread, we have a linked list indicating which objects must
   be locked, starting from the object at the head of the list

 - if the lock is available, the thread grabs it, and moves on to the
   next object on the list

 - if the lock is not available, the transaction aborts, and all locks
   acquired so far are released in the reverse order of their acquisition

 - if all locks are acquired, the transaction commits, and then all locks
   are released in the reverse order of their acquisition

There is a test program written.  Students must fill in incomplete classes.
You must submit the entire listing and the output.

Two runs are required.  In the first run, there are no 'yields' so lock
acquisition is always successful.  In the second run, a thread must 'yield'
after acquiring each lock.  You may put print statements where you like, but
I have indicated where I think the print statements will be most informative.

Since the templates for manipulating linked lists are provided for you,
student may _not_ use Java utilities.

For example, thread 1 needs to lock object 1, object 2, ..., and object 4
(in this order), because that is what 'objects_required[1]' indicates.
Suppose thread 1 succeeds in locking object 1 and object 2 but finds object
3 already locked.  In this case, thread 1 returns the two locks it holds
and terminates.

Here is the required part of the code:

---

public class Transaction {
  static int objects = 32;                               // number of objects
  static int threads =  8;                               // number of threads

  static Daemon  daemon           = new Daemon ();
  static Lock[]  lock             = new Lock[objects+1];
  static List[]  locks_held       = new List[threads+1];
  static List[]  objects_required = new List[threads+1];

  public static void main (String[] args) {

    Worker[] w = new Worker[threads+1];

    for (int j = 1; j <= objects; j++)                   // all locks available
      lock[j] = new Lock (true);

    for (int j = 1; j <= threads; j++) {
      //locks_held[j] = new List ();
      daemon.build_ObjReq_list (j);
    }

    for (int j = 1; j <= threads; j++) {                 // mix things up
      int tid = daemon.permutation (j);
      w[tid] = new Worker (tid);
      w[tid].start ();
    }
    System.out.println ("Eight workers have started.");
    System.out.println ( );

    for (int j = 1; j <= threads; j++) {                 // threads finished?
      try { w[j].join (); }
      catch (InterruptedException e) { };
    }

    System.out.println ();
    for (int j = 1; j <= threads; j++) {
      System.out.print ("ObjReq list for thread " + j + ": ");
      daemon.print_list (objects_required[j]);
    };
    System.out.print ("Lock values: ");
    for (int j = 1; j <= objects; j++)
      if (lock[j].available ())
        System.out.print ("+");
      else
        System.out.print ("-");
    System.out.println ();
    System.out.println ("System terminates normally.");
  }
}

class Daemon {
  private static int[]   worker   = new int[] {0, 4, 7, 6, 8, 5, 3, 2, 1};
  private static int[]   daemon   = new int[] {0, 4, 4, 4, 4, 4, 4, 4, 4};
  private static int[][] required = new int[][] {
                                      {0},
                                      {0,  4,  3,  2,  1, 0},
                                      {0,  8,  7,  6,  5, 0},
                                      {0, 12, 11, 10,  9, 0},
                                      {0, 12, 11, 10,  9, 0},
                                      {0, 18, 17, 15, 13, 0},
                                      {0, 17, 18, 16, 14, 0},
                                      {0, 25, 24, 23, 21, 19, 0},
                                      {0, 23, 24, 25, 22, 20, 0},
                                    };

  public int permutation (int tid) {
    return worker[tid];
  }

  public void interrupt (int tid) {
    if (daemon[tid] > 4)
      Thread.yield ();
  }
 
  public void build_ObjReq_list (int tid) {
    Transaction.objects_required[tid] = null;
    int j = 1;
    while (required[tid][j] != 0) {
      List p  = new List ();
      p.value = required[tid][j];
      p.next  = Transaction.objects_required[tid];
      Transaction.objects_required[tid] = p;
      j = j + 1;
    }
  }

  public void print_list (List p) {
    while (p != null) {
      System.out.print (p.value + " ");
      p = p.next;
    };
    System.out.println ();
  }

}

class List {
  int value;                                             // value in node
  List next;                                             // pointer to node
}

class Lock {
  private boolean available;
  Lock (boolean available1) {
    available = available1;
  }

  public synchronized boolean acquire () {
    ...
  }

  public synchronized void release () {
    ...
  }

  public synchronized boolean available () {             // used by main thread
    return available;                                    // NOT by workers
  }

}

class Manager {

  public boolean acquire_all (int tid) {

    ...
    while ... {
      acquired = ...
      if (!acquired) {
        System.out.println ("Worker " + tid + " denied lock " + p.value + ".");
        ...
      };
      System.out.println ("Worker " + tid + " grabs lock " + p.value + ".");
      ...
      Thread.yield ();                                   // only in 2nd run
    };
    ...
  }

  public void release_all (int tid) {
    ...
  }

}

class Worker extends Thread {
  static Manager manager = new Manager ();

  private int tid;
  Worker (int tid1) {
    tid = tid1;
  }

  public void run () {
    System.out.println ("Worker " + tid + " begins execution.");
    yield ();
    System.out.println ();
    System.out.println ("Worker " + tid + " initiates a transaction.");
    boolean acquired = manager.acquire_all (tid);
    if (acquired) {
      System.out.print ("Locks held by thread " + tid + ": ");
      Transaction.daemon.print_list (Transaction.locks_held[tid]);
      System.out.println ("Transaction commits.");
      manager.release_all (tid); }
    else
      System.out.println ("Transaction for thread " + tid + " aborts.");
    System.out.println ("Worker " + tid + " terminates.");
  }
}


กก

C.The idea of program
กก
This is rather like a word-guess game and what you should do is just filling up those blanks. And what you should 
do? It is a simple link-list and it is the basic operation in data structure. Should this be used as a project in
Operating System? I highly doubt it.
D.The major functions
E.Further improvement
F.File listing
1. Transaction.java
file name: Transaction.java
public class Transaction {
  static int objects = 32;              // number of objects
  static int threads =  8;              // number of threads

  static Daemon  daemon           = new Daemon ();
  static Lock[]  lock             = new Lock[objects+1];
  static List[]  locks_held       = new List[threads+1];
  static List[]  objects_required = new List[threads+1];

  public static void main (String[] args) {

    Worker[] w = new Worker[threads+1];

    for (int j = 1; j <= objects; j++)              // all locks available
      lock[j] = new Lock (true);

    for (int j = 1; j <= threads; j++) {
      locks_held[j] = new List ();
      daemon.build_ObjReq_list (j);
    }

    for (int j = 1; j <= threads; j++) {                 // mix things up
      int tid = daemon.permutation (j);
      w[tid] = new Worker (tid);
      w[tid].start ();
    }
    System.out.println ("Eight workers have started.");
    System.out.println ( );

    for (int j = 1; j <= threads; j++) {              // threads finished?
      try { w[j].join (); }
      catch (InterruptedException e) { };
    }

    System.out.println ();
    for (int j = 1; j <= threads; j++) {
      System.out.print ("ObjReq list for thread " + j + ": ");
      daemon.print_list (objects_required[j]);
    };
    System.out.print ("Lock values: ");
    for (int j = 1; j <= objects; j++)
      if (lock[j].available ())
        System.out.print ("+");
      else
        System.out.print ("-");
    System.out.println ();
    System.out.println ("System terminates normally.");
  }
}

class Daemon {
  private static int[]   worker   = new int[] {0, 4, 7, 6, 8, 5, 3, 2, 1};
  private static int[]   daemon   = new int[] {0, 4, 4, 4, 4, 4, 4, 4, 4};
  private static int[][] required = new int[][] {
                                      {0},
                                      {0,  4,  3,  2,  1, 0},
                                      {0,  8,  7,  6,  5, 0},
                                      {0, 12, 11, 10,  9, 0},
                                      {0, 12, 11, 10,  9, 0},
                                      {0, 18, 17, 15, 13, 0},
                                      {0, 17, 18, 16, 14, 0},
                                      {0, 25, 24, 23, 21, 19, 0},
                                      {0, 23, 24, 25, 22, 20, 0},
                                    };

  public int permutation (int tid) {
    return worker[tid];
  }

  public void interrupt (int tid) {
    if (daemon[tid] > 4)
      Thread.yield ();
  }
 
  public void build_ObjReq_list (int tid) {
    Transaction.objects_required[tid] = null;
    int j = 1;
    while (required[tid][j] != 0) {
      List p  = new List ();
      p.value = required[tid][j];
      p.next  = Transaction.objects_required[tid];
      Transaction.objects_required[tid] = p;
      j = j + 1;
    }
  }

  public void print_list (List p) {
    while (p != null) {
      System.out.print (p.value + " ");
      p = p.next;
    };
    System.out.println ();
  }

}

class List {
  int value;                                             // value in node
  List next;                                          // pointer to node
}

class Lock {
  private boolean available;
  Lock (boolean available1) {
    available = available1;
  }

  public synchronized boolean acquire () {
    if (available==true){
	available=false;
	return true;
   }
    else
	return false;
  }

  public synchronized void release () {
    available=true;
  }

  public synchronized boolean available () {       // used by main thread
    return available;                                    // NOT by workers
  }

}

class Manager {

  public boolean acquire_all (int tid) {

   boolean acquired=false;
   List p=Transaction.objects_required[tid];
   Transaction.locks_held[tid]=null;
    while (p!=null){
      acquired = Transaction.lock[p.value].acquire();
      if (!acquired) {
        System.out.println ("Worker " + tid + " denied lock " + p.value + ".");
        release_all(tid);
	return false;
      }
      System.out.println ("Worker " + tid + " grabs lock " + p.value +".");
      List temp=new List();
      temp.value=p.value;
      temp.next=Transaction.locks_held[tid];
      Transaction.locks_held[tid]=temp;
      p=p.next; 
      Thread.yield ();                               // only in 2nd run
    }
    return true;
    
  }

  public void release_all (int tid) {
   	List p= Transaction.locks_held[tid];
	while(p!=null)
	{
		Transaction.lock[p.value].release();
		p=p.next;
	}
	Transaction.locks_held[tid]=null;
  }

}

class Worker extends Thread {
  static Manager manager = new Manager ();

  private int tid;
  Worker (int tid1) {
    tid = tid1;
  }

  public void run () {
    System.out.println ("Worker " + tid + " begins execution.");
    yield ();
    System.out.println ();
    System.out.println ("Worker " + tid + " initiates a transaction.");
    boolean acquired = manager.acquire_all (tid);
    if (acquired) {
      System.out.print ("Locks held by thread " + tid + ": ");
      Transaction.daemon.print_list (Transaction.locks_held[tid]);
      System.out.println ("Transaction commits.");
      manager.release_all (tid);
    }
    else
      System.out.println ("Transaction for thread " + tid + " aborts.");
      System.out.println ("Worker " + tid + " terminates.");
  }
}



กก

The input is something like following:
Here is the result:
[qingz_hu@alpha PA3] % javac Transaction.java
[qingz_hu@alpha PA3] % java Transaction
Eight workers have started.

Worker 4 begins execution.
Worker 7 begins execution.
Worker 6 begins execution.
Worker 8 begins execution.
Worker 5 begins execution.
Worker 3 begins execution.
Worker 2 begins execution.
Worker 1 begins execution.

Worker 4 initiates a transaction.
Worker 4 grabs lock 9.

Worker 7 initiates a transaction.
Worker 7 grabs lock 19.

Worker 6 initiates a transaction.
Worker 6 grabs lock 14.

Worker 8 initiates a transaction.
Worker 8 grabs lock 20.

Worker 5 initiates a transaction.
Worker 5 grabs lock 13.

Worker 3 initiates a transaction.
Worker 3 denied lock 9.
Transaction for thread 3 aborts.
Worker 3 terminates.

Worker 2 initiates a transaction.
Worker 2 grabs lock 5.

Worker 1 initiates a transaction.
Worker 1 grabs lock 1.
Worker 4 grabs lock 10.
Worker 7 grabs lock 21.
Worker 6 grabs lock 16.
Worker 8 grabs lock 22.
Worker 5 grabs lock 15.
Worker 2 grabs lock 6.
Worker 1 grabs lock 2.
Worker 4 grabs lock 11.
Worker 7 grabs lock 23.
Worker 6 grabs lock 18.
Worker 8 grabs lock 25.
Worker 5 grabs lock 17.
Worker 2 grabs lock 7.
Worker 1 grabs lock 3.
Worker 4 grabs lock 12.
Worker 7 grabs lock 24.
Worker 6 denied lock 17.
Transaction for thread 6 aborts.
Worker 6 terminates.
Worker 8 denied lock 24.
Transaction for thread 8 aborts.
Worker 8 terminates.
Worker 5 grabs lock 18.
Worker 2 grabs lock 8.
Worker 1 grabs lock 4.
Locks held by thread 4: 12 11 10 9 
Transaction commits.
Worker 4 terminates.
Worker 7 grabs lock 25.
Locks held by thread 5: 18 17 15 13 
Transaction commits.
Worker 5 terminates.
Locks held by thread 2: 8 7 6 5 
Transaction commits.
Worker 2 terminates.
Locks held by thread 1: 4 3 2 1 
Transaction commits.
Worker 1 terminates.
Locks held by thread 7: 25 24 23 21 19 
Transaction commits.
Worker 7 terminates.

ObjReq list for thread 1: 1 2 3 4 
ObjReq list for thread 2: 5 6 7 8 
ObjReq list for thread 3: 9 10 11 12 
ObjReq list for thread 4: 9 10 11 12 
ObjReq list for thread 5: 13 15 17 18 
ObjReq list for thread 6: 14 16 18 17 
ObjReq list for thread 7: 19 21 23 24 25 
ObjReq list for thread 8: 20 22 25 24 23 
Lock values: ++++++++++++++++++++++++++++++++
System terminates normally.


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)