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."); } }
กก
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.
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.