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.