CSE522-Assignmentd 3: Part 1 and 2 Solved

Part 1: Thread Safe Trees 


Refer to file ThreadSafeTree.java whose main method creates and starts five concurrent threads, each of which inserts five random integers into a tree, and finally prints out all values in the tree.   The code as given invokes the standard Tree.insert method, which is not thread-safe, meaning that it is not suited for concurrent insertion of values into the tree, as values will be dropped from the tree due to the lack of any synchronization – as can be observed from the object diagram.    


A preliminary solution to this problem is to declare insert as a synchronized method.  Doing so will solve the problem of dropped values, but this solution is not desirable because it sacrifices concurrency – essentially, all values are now inserted sequentially into the tree.   You might try this out as a preliminary step.
 

Your task in Part 1 is to write a subclass SafeTree of class Tree with a thread-safe definition of insert(n), i.e., it preserves the basic logic of Tree.insert, but permits concurrent insertion of values into the tree, with no dropped values.  Concurrent insertion into disjoint subtrees as well as concurrent insertion at different nodes along any path from the root to a leaf should be supported.  To meet these objectives:

1.      Do not declare SafeTree.insert(n)  as a synchronized method.    


2.      Define two synchronized methods in class SafeTree, called lock() and unlock(), using which SafeTree.insert(n)   can ensure that one thread at a time is accessing any given  

SafeTree object, but other SafeTree objects can be accessed concurrently by other threads. 

 

3.      Call the lock() and unlock()  methods from SafeTree.insert(n) in such a way that any SafeTree object is locked for as short a duration as possible. 

 

4.      Define lock() and unlock() using Java’s wait-notify constructs.   Their definitions are similar to other wait-notify examples discussed in the lectures.
 

Run ThreadSafeTree.java to completion after replacing the instruction ‘new Tree(5000)’ by ‘new SafeTree(5000)’ in ThreadSafeTree.main.   Proceed as follows:
 

1. Check the JIVE object diagram to make sure that it does not have any dropped values, and check the console output to make sure that the printed values are in ascending order.  
 

2. Bring up the JIVE Search window, choose the Object Created option, enter SafeTree for the class name, and press Search.  There should be 31 entries in the Search Results window for the given test case.


3. Step through the search results one by one, observing the object diagram (using the ‘Objects’ option) at each step, until you locate at an object diagram showing maximal concurrency, i.e., where there is a maximum number of active threads in disjoint subtrees and also a maximum number of active threads at different nodes along a path in the tree.  There could be more than one such diagram; choose any object diagram with maximal concurrency. 

4. Save the chosen object diagram from step 3 in a file called A3_part1.png.

 

Using the JIVE Search Window 

 

Click in the source code window and do Ctrl-h in order to bring up the JIVE Search Window.  Alternatively, from Eclipse's Search menu, select the first entry, also called Search.   Then select the JIVE Search tab from the menu of tabs presented.

 

For Part 1, choose the Object Created query option, enter SafeTree for the class name, and press Search.  There should be 31 entries in the Search Results window for the given test case.

   

The search results are shown in under the Search tab located near the Console.    If the results are not being shown as a table, use the inverted triangle menu located third from the right, and choose the Show as List option.

 

Using the two solid yellow arrows (called Show Next Match and Show Previous Match) in order to cycle through the results.   Observe the object diagram (in the Objects mode) and save the diagram with maximal concurrency.

Part 2: Readers-Writers with Writers Priority 

 

The Readers-Writers problem, discussed in Lecture 14, is a classic example in the study of concurrency control.   There are two types of concurrent threads, reader threads (readers) and writer threads (writers), and they concurrently access a database.  Readers execute the database ‘read’ operation while writers execute the database ‘write’ operation.   The basic requirement of concurrency control is that a ‘read’ operation may be executed concurrently by two or more readers, but a ‘write’ operation should not be executed concurrently with any ‘read’ or any ‘write’ operation.


An important variant of the basic problem is the Readers-Writers problem with Writers Priority.   Here, when a writer tries to access the database and is made to wait because either a read or write is in progress, all subsequent read requests are delayed until this writer gets to access the database.  In other words, a waiting writer takes precedence over every waiting reader regardless of the order of their arrival.  Note: Active (or, running) readers are not pre-empted but are allowed to complete their read operations before the waiting writer begins its operation.    

 

Posted on Piazza is a file ReadersWriters.java containing a complete implementation of the Readers-Writers problem with Writers Priority.  This program is written with wait-notify constructs.   Your task in Part 2 is to translate all synchronized methods and wait-notify constructs in terms Java Semaphores using the methodology outlined in Lecture 14 slide 31.  Name your semaphores as follows:

 

1.      Use one semaphore (named s1) for translating synchronized methods.

 

2.      Use one semaphore (named s2_r) for waiting readers and another semaphore (named s2_w) for waiting writers.    

 

3.      Implement notifyAll by performing release(s) on the appropriate semaphores, as explained in Lecture 14 slide 31.

 

Name your translated program as ReadersWritersSemaphore.java.   

 

Install in Eclipse the State Diagram and Property Checker plugin posted on Piazza following the instructions posted at Resources → Software Tools → FSM_Installation_Usage.pdf, and proceed as follows:

 

1.      Run the program to completion and check that the data field in object Database:1 has the value 55555 for the given test case.

 

2.      Save the Execution Trace in a file called RWS.csv and load this file into the Property Checker – see the abovementioned file on installation instructions and usage.

 

3.      From the dropdown menu, choose the fields


 Database:1.r, Database:1.w,  Database:1.ww  

      Enlarge the Canvas Dimension (using the text boxes at bottom of diagram), and draw.

 

4.      In the Abbreviations text box enter (but avoid cutting and pasting from PDF file):   

 

Database:1.r = r, Database:1.w = w, Database:1.ww = ww  

5.      In the Properties textbox, enter (but avoid cutting and pasting from PDF file):

 

G [ (w == 1 -> r == 0) &&  

         (r > 0 -> w == 0)  &&  

        (w == 0 || w == 1) && 

         (r > 0 && ww > 0 -> r’ <= r)  

       ] 

 

-          The first three conjuncts express the basic readers-writers concurrency control policy, and the last conjunct expresses the writers-priority condition.   

-          The variable r’ refers to the value of r in the next state, and the condition states that the number of running readers must monotonically decrease when there are waiting writers.    

-          The outermost G specifies that this property must hold globally, i.e., in all states.   



6.      Press Validate and look for the message “All properties satisfied.” below the Properties textbox.   If this message does not appear, look for states highlighted in red in the state diagram, as they will help determine the cause of failure.    (The topmost state is always redhighlighted when a G property fails.)   Use this information to correct your program.


7.      When all properties are satisfied, save the diagram in a file called A3_state1.svg.  This can be done by right-clicking on the diagram and choosing Save picture as…

 

8.      Reset previous choices and, again, from the dropdown menu, choose the fields   
 

Database:1.r, Database:1.w,  Database:1.data

 
9.      Draw the State Diagram and save it to a file called A3_state2.png.   This diagram helps visually check the Writers priority condition – the diagram should slope to the right and end with a long tail of read operations.