Find duplicates in a array of elements

You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

Algorithm -
1. Read input from startPos

2. If input is within the maxRange or it's not in correct place then it's a candidate to be replaced else incrementStartPos

3. finalPosition for input is input[i]

4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange

5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance

6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array

7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element

Example 

1. Since the number's are in the range of 1..n

2. Start with a[0] and put that element in the right place and increase the element by n (sg:: if a[0]=8 and n=10 then a[8] = 18) to ensure that this element has been placed correctly.
3. Put a[8] in step1 in a[0] if (a[i] < n ) and repeat step2 till a[0] = 11 (1+n(10) = 11) in which case move to a[1]
4. At any point if you get a[i] > n which means this element is a duplicate increment a[i] +nEg: if an array had
(2, 3, 4, 3, 2}
1. n=5 after step1 we'll get
{3, 7, 4, 3, 2}
2. now a[0] = 3 so again in loop we'll get
{4, 7, 8, 3, 2}
3. now a[0] = 4 so again in loop we'll get
{3, 7, 8, 9, 2}
4. a[0] = 3 so again in loop we'll get { , 7, 13, 9, 2}
5. since a[0] is empty move to a[1] and in loop we find it's at the right place so move to next, 8, 9 are also in place so we move to last element and have the final array as
{ , 12, 13, 9, }
Now to find how many are duplicates divide every element by 5 and take the mod => m = (a[i] mod n) -1
this gives you how many times an element is repeated.
Approach and correctness
--------------------------
since we need to do in 0(n) and numbers are in 1..n we need to put one element in correct location in O(n) time and we also need to identify duplicates so increment that element by 'n'.

Java Code 

 public static void main(String[] args) {
int[] inputArr = {0, 4, 3, 4, 1};
findDuplicates(inputArr, 4);
printDuplicatesAndMissingElements(inputArr);
int[] inputArr1 = {0, 2, 3, 4, 3, 2};
findDuplicates(inputArr1, 5);
printDuplicatesAndMissingElements(inputArr1);
}private static void findDuplicates(int[] inputArr, int maxRange) {
// for simplicity reasons we will assume nothing is there in 0 index of array
// and start from 1
int i = 1;
int maxArrLength = inputArr.length;
while(true) {
if ( i > maxArrLength - 1)
break;
int finalPos = inputArr[i];
System.out.println(" Read :: " + inputArr[i]);
if (finalPos > maxRange) {
//this element is already in final position skip and move further looking for elements within maxRange
i++;
continue;
}
int finalPosElement = inputArr[inputArr[i]];
int startPos = i;
int startPosElement = inputArr[i];
// if startPos element isn't in place and it's within the maxRange..
// then candidate for swap or reaching final pos...
if (inputArr[startPos] != i ||
inputArr[startPos] <= maxRange) {
if (finalPosElement > maxRange) {
// if finalposElement > maxRange then no swapping required
// just add maxRange to denote multiple entry
inputArr[finalPos] += maxRange;
//make startPosElement as 0
inputArr[startPos] = 0;
System.out.println("No swapping required incemented " + inputArr[finalPos] );
}
else {
//swap
int temp = startPosElement;
inputArr[startPos] = finalPosElement;
inputArr[finalPos] = temp + maxRange;
System.out.println("Swapped : " + startPosElement + " with " +finalPosElement);
}
}
printArray(inputArr);
// if the element in current evaluated position isn't still correct repeat the above again
if (inputArr[startPos] == i ||
inputArr[startPos] > maxRange) {
System.out.println(" Read :: "+ inputArr[startPos] + " it's already in place");
inputArr[startPos] += maxRange;
i++;
}
else if (inputArr[startPos] == 0){
i++;
continue;
}
else {
continue;
}
}
}
private static void printArray(int[] inputArr) {
for (int i=1; i < inputArr.length; i++) {
System.out.print(inputArr[i] +",");
}
System.out.println("");
}
private static void printDuplicatesAndMissingElements(int[] inputArr) {
int maxRange = inputArr.length;
for (int i=1; i < inputArr.length; i++) {
if (inputArr[i] == 0) {
System.out.println(" Element [" + i + "] is missing");
}
int input = inputArr[i];
int mod = input / maxRange;
if ( mod > 1) {
System.out.println (" Element [" + i + "] is repeated + [" + mod + "] times");
}
}
}

}

Globalization and Localization

Applications must be designed to accommodate users from various cultures. Users in different parts of the world use different languages and different formatting standards for numbers, currency, and dates. International applications should be customizable according to the preferences of users belonging to different nations, cultures, or regions.

An application uses the locale to identify the preference of a user. The local is the combination of a language and a country. For example, the locale of a user speaking English and belonging to the United States is "en-US". The locale includes information about the formats used for representing time and date, symbols and conventions used for representing currency, and the character encoding scheme being used.

The structure of an internationalized application is divided into two blocks:

• Code Block: Contains the application code or the executable part of an application. This block will remain the same for all locales.
• Data Block: Contains all the resources, such as text and images used by the user interface (UI). This block is locale-specific, and each locale will have one data block.

The process of making  an application ready for customers is called internationalization. It includes three phases:

Globalization: 

Involves writing the executable code for an application in such a way that makes it culture-neutral and language-neutral. While incorporating globalization, you must ensure that the culture-specific details are not hard-coded into the executable code. The primary task in this phase is to identify the various locale-sensitive resources and to isolate these resources from the executable code.

Localizability:

An application that has been globalized must be tested to ensure that its executable code is independent of the culture and language-specific data. This is called localizability testing. The focus of localizability testing is to check how the application adapts itself to different locales.

Localization:

Involves the customization of an application for a specific locale. One major task in this phase is the translation of resources identified during the globalization phase. During this phase, various resources, such as images and text, for the designated locale are created.

• When designing an international application, you should ensure the following factors:

User Interface (UI): The language used to design different UI components, such as menu, message box, static-text holder (label), is not fixed during design phase of the application.
Information Formats: The formats of different elements, such as currency, number, and date, are not fixed during design phase of the application.

The different aspects of an application that should be taken into account while incorporating localization are:

• Formats: The formats used for displaying numbers, time, dates and currency should be considered while incorporating localization.

Graphics: The locale-sensitive graphics, such as maps, traffic signs, and calendar should be considered while incorporating localization.

MVC 1 Vs MVC 2

• Following are the important feature of MVC1 architecture:
  • HTML or JSP files are used to code the presentation. JSP files use java beans to retrieve data if required.
  • MVC1 architecture is page-centric design all the business and processing logic means any JSP page can either present in the JSP or may be called directly from the JSP page.
  • Data access is usually done using Custom tag or through java bean call.Therefore we can say that in MVC1 there is tight coupling between page and model.

• Following are the important feature of MVC2 architecture:
  • This architecture removes the page-centric property of MVC1 architecture by separating Presentation Control logic and Application state
  • In MVC2 architecture there is one Controller which receive all request for the application and is responsible for taking appropriate action in response to each request. Second one is Model which is represented by JavaBeans business object and database. Third one is View or is JSP page it takes the information provided by Controller and Module and presents it to user.

Figure 1: JSP Model 1 architecture

Figure 2: JSP Model 2 architecture

Introduction of Cloud Computing

I have gone through couple of documents but I come across below youtube video which explain about Cloud Computing.

This video explain about :
1. Web Hosting
2. Virtualization
3. Cloud Computing

Difference between shallow cloning and deep cloning of objects

The default behaviour of an object’s clone() method automatically yields a shallow copy. So to achieve a deep copy the classes must be edited or adjusted.

Shallow copy: If a shallow copy is performed on obj-1 as shown in fig-2 then it is copied but its contained objects are not. The contained objects Obj-1 and Obj-2 are affected by changes to cloned Obj-2. Java supports shallow cloning of objects by default when a class implements the java.lang.Cloneable interface.

Deep copy: If a deep copy is performed on obj-1 as shown in fig-3 then not only obj-1 has been copied but the objects contained within it have been copied as well. Serialization can be used to achieve deep cloning. Deep cloning through serialization is faster to develop and easier to maintain but carries a performance overhead.

For example, invoking clone() method on a HashMap returns a shallow copy of HashMap instance, which means the keys and values themselves are not cloned. If you want a deep copy then a simple method is to serialize the HashMap to a ByteArrayOutputSream and then deserialize it. This creates a deep copy but does require that all keys and values in the HashMap are Serializable. Its primary advantage is that it will deep copy any arbitrary object graph.

Memory allocation in Java

Each time an object is created in Java it goes into the area of memory known as heap. The primitive variables like  int and double are allocated in the stack, if they are local method variables and in the heap if they are member  variables (i.e. fields of a class). In Java methods local variables are pushed into stack when a method is invoked and stack pointer is decremented when a method call is completed. In a multi-threaded application each thread will have its own stack but will share the same heap. This is why care should be taken in your code to avoid any concurrent access issues in the heap space. The stack is threadsafe (each thread will have its own stack) but the heap is not threadsafe unless guarded with synchronisation through your code.

A method in stack is re-entrant allowing multiple concurrent invocations that do not interfere with each other. A function is recursive if it calls itself. Given enough stack space, recursive method calls are perfectly valid in Java though it is tough to debug. Recursive functions are useful in removing iterations from many sorts of algorithms. All recursive functions are re-entrant but not all re-entrant functions are recursive. Idempotent methods are methods, which are written in such a way that repeated calls to the same method with the same arguments yield same results. For example clustered EJBs, which are written with idempotent methods, can automatically recover from a server failure as long as it can reach another server.

Find nth last element from linked list

Problem : How do we find the nth element from the right of a singly linked list? Would reversing the link list and traversing n elements be the only possible solution?

Solution : Take two pointer's

1. Keep a distance of (n-1) between the two pointers.
2. Increment the first then by 1 and second also by 1
3. When second reaches end of list first is pointing to the desired node.

Difference Between ArrayList and Linklist

The LinkedList and ArrayList represent some of the widely used data structures of the Java Collections Framework. You might have had a chance to already use both classes several times so far; however, if you have wondered on what makes them fundamentally different, then continue reading.

Although both the LinkedList and ArrayList classes implement the List interface, they differ on the following 3-key issues: 1) Data Storage, 2) Data Access, 3) Data Management.

DATA STORAGE: Linked-list versus Array

• LinkedList uses the design of a linked-list data structure (from where it get its name) to store data elements (i.e. objects). In this manner, each data element -- depending on the position of the list -- has a link to the previous and next element. This storage approach proves to be very efficient, as it uses only as much memory as it needs; no more, no less.
• ArrayList uses an Object array for storing the data elements. By default the array starts with a capacity of 10; unless otherwise specified at the time of instantiation. For example, if we want to instantiate an ArrayList of strings with an initial capacity of 1024 then we would use:

ArrayList<String> stringArrayList = new ArrayList<String>(1024);

Thus, by default the ArrayList can be more wasteful as far as the memory allocation goes.

DATA ACCESS: Sequential Access versus Random Access

• LinkedList due to the nature of its data storage, has a sequential access approach. Thus, if we want to retrieve an element at a specific index through the public E get(int index) method, we would have to iterate either from the beginning or the end, depending if the requested index is greater than or less than half the length of the list. It can easily be seen how this sequential access can become quite timely as we deal with longer and longer lists. As the public E get(int index)method uses the Node node(int index) method for data retrieval, we can see the implications of LinkedList's sequential access in the following code:

570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587

/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

• ArrayList supports random access as it has an internal array for data storage. Thus, when we call the public E get(int index) method in an ArrayList instance, we get forwarded to the E elementData(int index) method which simply returns the element located at the specified position within the array, i.e.:

333 334 335 336 337 338

// Positional Access Operations @SuppressWarnings("unchecked") E elementData(int index) { return (E) elementData[index]; }

Needless to say, ArrayList's random access approach is far more efficient, as it doesn't have to waste computing cycles on iteration.

DATA MANAGEMENT: Linking and Unlinking versus Array Copying

• LinkedList can very efficiently undergo any changes in its collection of data elements. For example, if we want to remove a specific data element from the LinkedList instance -- through the public boolean remove(Object o) method -- then we go ahead and link the neighbors (i.e. previous and next data elements) of the unwanted data element, and the Garbage Collector will take care of the rest. Thus, if we have a linked-list structure with three string data elements (with previous and next links), as follow:

["A"] <-> ["B"] <-> ["C"]

Then, when we request removal of the "B" string data element, "A" and "C" get linked together, and "B" is left alone, thus becoming eligible for Garbage Collection:

["A"].next = ["B"].next => ["A"].next = ["C"]
["C"].prev = ["B"].prev => ["C"].prev = ["A"]

The Java implementation behind this pseudo-code looks like the following:

213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240

/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }

Do note that the code displayed above is for the E unlink(Node x) method on which LinkedList's public boolean remove(Object o) method relies. In addition to the efficiency of the remove method, LinkedList is very flexible when it comes to enlarging or shrinking its collection of data elements. In a LinkedList instance whenever we need to add to the collection, a call is made to the void linkLast(E e) method, which simply appends the new data element to the end of the list, as seen below:

144 145 146 147 148 149 150 151 152 153 154 155 156 157

/** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<E>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

• ArrayList due to the usage of its internal array it copies all of the elements to a new array every time there's a removal request, or when there's not enough room to add a new element. Thus, for every new addition or removal from our ArrayList collection a call is made to the public void ensureCapacity(int minCapacity) method, which carries out the necessary copying and shifting of the elements, as seen below:

171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188

/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }

Needless to say, you can imagine how much work these operations carry out, especially when dealing with very large arrays.

In conclusion, we can see that both the LinkedList and ArrayList have their positives and negatives; however, by having a good understanding of these issues you can make a better decision on what implementation should you use, based on the data size and usage requirements.

Synchronous JMS Communication

Here are few easy steps to create synchronous JMS communication.

The solution is like :

- Sender class which sends a message to permanent input queue and create a temporary 

queue and waits for response.

connection = jmsTemplate.getConnectionFactory().createConnectio n();
Session session = connection.createSession(false, Session.AUTO_ACKNOWLEDGE);
MessageProducer producer = session.createProducer(queue);
connection.start();
TemporaryQueue outDest = session.createTemporaryQueue(); // return destination 

// Create message
TextMessage message = session.createTextMessage("Hello World");
message.setJMSReplyTo(outDest);
producer.send(message);

// Get a response
MessageConsumer consumer = session.createConsumer(outDest);
Message msgBack = null;
msgBack = consumer.receive(12000);

and here is code for the receiver class which extends

org.springframework.jms.listener.SessionAwareMessa geListener;..

String messageId = message.getJMSMessageID();
TextMessage textMessage = (TextMessage) message;
System.out.println(" Sending response to OUT QUEUE ");
ApplicationContext ac = new ClassPathXmlApplicationContext("com\\cisco\\iam\\a ac\\config\\JmsServerClientClasses.xml");
SendResponseBackToInputQueue recMessage = (SendResponseBackToInputQueue)ac.getBean("recMessa ge");
recMessage.sendResponseFromTheReceivingQueue(messa ge, session);

In this approach the request queue is permanent and the response queue is temporary.

Now here is the code for the sender class which sends a message to a permanent request queue and waits for response on a another permanent queue.

jmsTemplate.send(queue,msg);//msg is a instance of MessageCreator class
Message message = msg.getMsg();

String messageId = message.getJMSMessageID();
System.out.println("Message id is "+messageId);

System.out.println(" Receiving response at the OUT Queue ");
Message msg1 = jmsTemplate.receiveSelected(responseQueue,"JMSCorr elationID='"+messageId+"'");
if(null == msg1)
System.out.println("Receive Timeout -- ");
if(null != msg1){
TextMessage messageText = (TextMessage)msg1;
System.out.println("JMS Coorelation id is "+msg1.getJMSCorrelationID());
System.out.println("****************************** *************");
}

JAX-RPC vs JAX-WS

Java API for XML-Based RPC (JAX-RPC) is a Legacy Web Services Java API, it uses SOAP and HTTP to do RPCs over the network and enables building of Web services and Web applications based on the SOAP 1.1 specification, Java SE 1.4 or lower, or when rpc/encoded style must be used.

You can use the JAX-RPC programming model to develop SOAP-based web service clients and endpoints. JAX-RPC enables clients to invoke web services developed across heterogeneous platforms. Likewise, JAX-RPC web service endpoints can be invoked by heterogeneous clients. JAX-RPC requires SOAP and WSDL standards for this cross-platform interoperability.

JAX-RPC lets people develop a web service endpoint using either a Servlet or Enterprise JavaBeans (EJB) component model. The endpoint is then deployed on either the Web or EJB container, based on the corresponding component model. Endpoints are described using a Web Services Description Language (WSDL) document.(This WSDL document can be published in a public or private registry, though this is not required). A client then uses this WSDL document and invokes the web service endpoint.

JAX-RPC in J2ee 1.4 supports 4 types of stubs and invocations: static stub, dynamic proxy, Dynamic Invocation Interface (DII) and Application client.

Static Stub Client
Web service client makes a call through a stub, a local object that acts as a proxy for the remote service. Because the stub is created by wscompile at development time (as opposed to runtime), it is usually called a static stub.

Example: Invoking a Stub Client
Stub stub = (Stub) (new MyHelloService_Impl().getHelloIFPort());
stub._setProperty (javax.xml.rpc.Stub.ENDPOINT_ADDRESS_PROPERTY,endpoint_address_string);
HelloIF hello = (HelloIF)stub;
System.out.println(hello.sayHello("Duke!"));

Dynamic Proxy Client
In contrast, the client call a remote procedure through a dynamic proxy, a class that is created during runtime. Although the source code for the static stub client relies on an implementation-specific class, the code for the dynamic proxy client does not have this limitation.

Example: Dynamic Proxy
javax.xml.rpc.Service service = ServiceFactory.newInstance().createService(...);
com.example.StockQuoteProvider sqp = (com.example.StockQuoteProvider)service.getPort(portName, StockQuoteProvider.class);
float price = sqp.getLastTradePrice("ACME");

Dynamic Invocation Interface Client
With the dynamic invocation interface (DII), a client can call a remote procedure even if the signature of the remote procedure or the name of the service is unknown until runtime. In contrast to a static stub or dynamic proxy client, a DII client does not require runtime classes generated by wscompile.

Example: Dynamic Invocation Interface
javax.xml.rpc.Service service = ServiceFactory.newInstance().createService(...);
javax.xml.rpc.Call call = service.createCall(portName, "getLastTradePrice");
// This example assumes that addParameter and setReturnType methods are not required to be called
Object[] inParams = new Object[] {"ACME"};
Float quotePrice = (Float)call.invoke(inParams);

Application Client
Unlike the stand-alone clients, for an application client, because it's a J2EE component, an application client can locate a local web service by invoking the JNDI lookup method.

Example: Application Client
Context ic = new InitialContext();
MyHelloService myHelloService = (MyHelloService)
ic.lookup("java:comp/env/service/MyJAXRPCHello");
appclient.HelloIF helloPort = myHelloService.getHelloIFPort();
((Stub)helloPort)._setProperty(Stub.ENDPOINT_ADDRESS_PROPERTY,args[0]);
System.out.println(helloPort.sayHello("Jake!"));


Service Endpoint Model
JAX-RPC supports a client model for the service consumer, and a service endpoint model for the service producer.

Application-Level Interaction Modes
JAX-RPC specifies three client application interaction models:
* Synchronous request-response two-way RPC
* Asynchronous (non-blocking) request-response two-way RPC
* One-way RPC


JAX-WS

JAX-WS 2.0 is the successor of JAX-RPC 1.1 - the Java API for XML-based Web services. If possible, JAX-WS should be used instead as it is based on the most recent industry standards.

What remains the same?

Before we itemize the differences between JAX-RPC 1.1 and JAX-WS 2.0, we should first discuss what is the same.

* JAX-WS still supports SOAP 1.1 over HTTP 1.1, so interoperability will not be affected. The same messages can still flow across the wire.

* JAX-WS still supports WSDL 1.1, so what you've learned about that specification is still useful. A WSDL 2.0 specification is nearing completion, but it was still in the works at the time that JAX-WS 2.0 was finalized.

What is different?

* SOAP 1.2
JAX-RPC and JAX-WS support SOAP 1.1. JAX-WS also supports SOAP 1.2.

* XML/HTTP
The WSDL 1.1 specification defined an HTTP binding, which is a means by which you can send XML messages over HTTP without SOAP. JAX-RPC ignored the HTTP binding. JAX-WS adds support for it.

* WS-I's Basic Profiles
JAX-RPC supports WS-I's Basic Profile (BP) version 1.0. JAX-WS supports BP 1.1. (WS-I is the Web services interoperability organization.)

* New Java features
o JAX-RPC maps to Java 1.4. JAX-WS maps to Java 5.0. JAX-WS relies on many of the features new in Java 5.0.
o Java EE 5, the successor to J2EE 1.4, adds support for JAX-WS, but it also retains support for JAX-RPC, which could be confusing to today's Web services novices.

* The data mapping model
o JAX-RPC has its own data mapping model, which covers about 90 percent of all schema types. Those that it does not cover are mapped to javax.xml.soap.SOAPElement.
o JAX-WS's data mapping model is JAXB. JAXB promises mappings for all XML schemas.

* The interface mapping model
JAX-WS's basic interface mapping model is not extensively different from JAX-RPC's; however:
o JAX-WS's model makes use of new Java 5.0 features.
o JAX-WS's model introduces asynchronous functionality.

* The dynamic programming model
o JAX-WS's dynamic client model is quite different from JAX-RPC's. Many of the changes acknowledge industry needs:
+ It introduces message-oriented functionality.
+ It introduces dynamic asynchronous functionality.
o JAX-WS also adds a dynamic server model, which JAX-RPC does not have.

* MTOM (Message Transmission Optimization Mechanism)
JAX-WS, via JAXB, adds support for MTOM, the new attachment specification. Microsoft never bought into the SOAP with Attachments specification; but it appears that everyone supports MTOM, so attachment interoperability should become a reality.

* The handler model
o The handler model has changed quite a bit from JAX-RPC to JAX-WS.
o JAX-RPC handlers rely on SAAJ 1.2. JAX-WS handlers rely on the new SAAJ 1.3 specification.

Reference Origination Link: http://www.ibm.com/developerworks/webservices/library/ws-tip-jaxwsrpc.html

ReadWrite Locks in Java

A read / write lock is more sophisticated lock than the Lock implementations shown in the text Locks in Java. Imagine you have an application that reads and writes some resource, but writing it is not done as much as reading it is. Two threads reading the same resource does not cause problems for each other, so multiple threads that want to read the resource are granted access at the same time, overlapping. But, if a single thread wants to write to the resource, no other reads nor writes must be in progress at the same time. To solve this problem of allowing multiple readers but only one writer, you will need a read / write lock.

Java 5 comes with read / write lock implementations in the java.util.concurrent package. Even so, it may still be useful to know the theory behind their implementation.

Here is a list of the topics covered in this text:

1. Read / Write Lock Java Implementation
2. Read / Write Lock Reentrance
3. Read Reentrance
4. Write Reentrance
5. Read to Write Reentrance
6. Write to Read Reentrance
7. Fully Reentrant Java Implementation
8. Calling unlock() from a finally-clause

Read / Write Lock Java Implementation

First let’s summarize the conditions for getting read and write access to the resource:
Read Access       If no threads are writing, and no threads have requested write access.
Write Access       If no threads are reading or writing.

If a thread wants to read the resource, it is okay as long as no threads are writing to it, and no threads have requested write access to the resource. By up-prioritizing write-access requests we assume that write requests are more important than read-requests. Besides, if reads are what happens most often, and we did not up-prioritize writes, starvation could occur. Threads requesting write access would be blocked until all readers had unlocked the ReadWriteLock. If new threads were constantly granted read access the thread waiting for write access would remain blocked indefinately, resulting in starvation. Therefore a thread can only be granted read access if no thread has currently locked the ReadWriteLock for writing, or requested it locked for writing.

A thread that wants write access to the resource can be granted so when no threads are reading nor writing to the resource. It doesn’t matter how many threads have requested write access or in what sequence, unless you want to guarantee fairness between threads requesting write access.

With these simple rules in mind we can implement a ReadWriteLock as shown below:

public class ReadWriteLock{

  private int readers       = 0;
  private int writers       = 0;
  private int writeRequests = 0;

  public synchronized void lockRead() throws InterruptedException{
    while(writers > 0 || writeRequests > 0){
      wait();
    }
    readers++;
  }

  public synchronized void unlockRead(){
    readers--;
    notifyAll();
  }

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;

    while(readers > 0 || writers > 0){
      wait();
    }
    writeRequests--;
    writers++;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    writers--;
    notifyAll();
  }
}

The ReadWriteLock has two lock methods and two unlock methods. One lock and unlock method for read access and one lock and unlock for write access.

The rules for read access are implemented in the lockRead() method. All threads get read access unless there is a thread with write access, or one or more threads have requested write access.

The rules for write access are implemented in the lockWrite() method. A thread that wants write access starts out by requesting write access (writeRequests++). Then it will check if it can actually get write access. A thread can get write access if there are no threads with read access to the resource, and no threads with write access to the resource. How many threads have requested write access doesn’t matter.

It is worth noting that both unlockRead() and unlockWrite() calls notifyAll() rather than notify(). To explain why that is, imagine the following situation:

Inside the ReadWriteLock there are threads waiting for read access, and threads waiting for write access. If a thread awakened by notify() was a read access thread, it would be put back to waiting because there are threads waiting for write access. However, none of the threads awaiting write access are awakened, so nothing more happens. No threads gain neither read nor write access. By calling noftifyAll() all waiting threads are awakened and check if they can get the desired access.

Calling notifyAll() also has another advantage. If multiple threads are waiting for read access and none for write access, and unlockWrite() is called, all threads waiting for read access are granted read access at once – not one by one.

Read / Write Lock Reentrance

The ReadWriteLock class shown earlier is not reentrant. If a thread that has write access requests it again, it will block because there is already one writer – itself. Furthermore, consider this case:

1. Thread 1 gets read access.

2. Thread 2 requests write access but is blocked because there is one reader.

3. Thread 1 re-requests read access (re-enters the lock), but is blocked because there is a write request

In this situation the previous ReadWriteLock would lock up – a situation similar to deadlock. No threads requesting neither read nor write access would be granted so.

To make the ReadWriteLock reentrant it is necessary to make a few changes. Reentrance for readers and writers will be dealt with separately.

Read Reentrance

To make the ReadWriteLock reentrant for readers we will first establish the rules for read reentrance:

A thread is granted read reentrance if it can get read access (no writers or write requests), or if it already has read access (regardless of write requests).

To determine if a thread has read access already a reference to each thread granted read access is kept in a Map along with how many times it has acquired read lock. When determing if read access can be granted this Map will be checked for a reference to the calling thread. Here is how the lockRead() and unlockRead() methods looks after that change:

public class ReadWriteLock{

  private Map readingThreads =
      new HashMap();

  private int writers        = 0;
  private int writeRequests  = 0;

  public synchronized void lockRead() throws InterruptedException{
    Thread callingThread = Thread.currentThread();
    while(! canGrantReadAccess(callingThread)){
      wait();
    }

    readingThreads.put(callingThread,
       (getAccessCount(callingThread) + 1));
  }

  public synchronized void unlockRead(){
    Thread callingThread = Thread.currentThread();
    int accessCount = getAccessCount(callingThread);
    if(accessCount == 1){ readingThreads.remove(callingThread); }
    else { readingThreads.put(callingThread, (accessCount -1)); }
    notifyAll();
  }

  private boolean canGrantReadAccess(Thread callingThread){
    if(writers > 0)            return false;
    if(isReader(callingThread) return true;
    if(writeRequests > 0)      return false;
    return true;
  }

  private int getReadAccessCount(Thread callingThread){
    Integer accessCount = readingThreads.get(callingThread);
    if(accessCount == null) return 0;
    return accessCount.intValue();
  }

  private boolean isReader(Thread callingThread){
    return readingThreads.get(callingThread) != null;
  }

}

As you can see read reentrance is only granted if no threads are currently writing to the resource. Additionally, if the calling thread already has read access this takes precedence over any writeRequests.

Write Reentrance

Write reentrance is granted only if the thread has already write access. Here is how the lockWrite() and unlockWrite() methods look after that change:

public class ReadWriteLock{

    private Map readingThreads =
        new HashMap();

    private int writeAccesses    = 0;
    private int writeRequests    = 0;
    private Thread writingThread = null;

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;
    Thread callingThread = Thread.currentThread();
    while(! canGrantWriteAccess(callingThread)){
      wait();
    }
    writeRequests--;
    writeAccesses++;
    writingThread = callingThread;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    writeAccesses--;
    if(writeAccesses == 0){
      writingThread = null;
    }
    notifyAll();
  }

  private boolean canGrantWriteAccess(Thread callingThread){
    if(hasReaders())             return false;
    if(writingThread == null)    return true;
    if(!isWriter(callingThread)) return false;
    return true;
  }

  private boolean hasReaders(){
    return readingThreads.size() > 0;
  }

  private boolean isWriter(Thread callingThread){
    return writingThread == callingThread;
  }
}

Notice how the thread currently holding the write lock is now taken into account when determining if the calling thread can get write access.

Read to Write Reentrance

Sometimes it is necessary for a thread that have read access to also obtain write access. For this to be allowed the thread must be the only reader. To achieve this the writeLock() method should be changed a bit. Here is what it would look like:

public class ReadWriteLock{

    private Map readingThreads =
        new HashMap();

    private int writeAccesses    = 0;
    private int writeRequests    = 0;
    private Thread writingThread = null;

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;
    Thread callingThread = Thread.currentThread();
    while(! canGrantWriteAccess(callingThread)){
      wait();
    }
    writeRequests--;
    writeAccesses++;
    writingThread = callingThread;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    writeAccesses--;
    if(writeAccesses == 0){
      writingThread = null;
    }
    notifyAll();
  }

  private boolean canGrantWriteAccess(Thread callingThread){
    if(isOnlyReader(callingThread))    return true;
    if(hasReaders())                   return false;
    if(writingThread == null)          return true;
    if(!isWriter(callingThread))       return false;
    return true;
  }

  private boolean hasReaders(){
    return readingThreads.size() > 0;
  }

  private boolean isWriter(Thread callingThread){
    return writingThread == callingThread;
  }

  private boolean isOnlyReader(Thread thread){
      return readers == 1 && readingThreads.get(callingThread) != null;
  }

}

Now the ReadWriteLock class is read-to-write access reentrant.

Write to Read Reentrance

Sometimes a thread that has write access needs read access too. A writer should always be granted read access if requested. If a thread has read access no other threads can have read nor write access, so it is not dangerous. Here is how the canGrantReadAccess() method will look with that change:

public class ReadWriteLock{

    private boolean canGrantReadAccess(Thread callingThread){
      if(isWriter(callingThread)) return true;
      if(writingThread != null)   return false;
      if(isReader(callingThread)  return true;
      if(writeRequests > 0)       return false;
      return true;
    }

}

Fully Reentrant ReadWriteLock

Below is the fully reentran ReadWriteLock implementation. I have made a few refactorings to the access conditions to make them easier to read, and thereby easier to convince yourself that they are correct.

public class ReadWriteLock{

  private Map readingThreads =
       new HashMap();

   private int writeAccesses    = 0;
   private int writeRequests    = 0;
   private Thread writingThread = null;

  public synchronized void lockRead() throws InterruptedException{
    Thread callingThread = Thread.currentThread();
    while(! canGrantReadAccess(callingThread)){
      wait();
    }

    readingThreads.put(callingThread,
     (getReadAccessCount(callingThread) + 1));
  }

  private boolean canGrantReadAccess(Thread callingThread){
    if( isWriter(callingThread) ) return true;
    if( hasWriter()             ) return false;
    if( isReader(callingThread) ) return true;
    if( hasWriteRequests()      ) return false;
    return true;
  }

  public synchronized void unlockRead(){
    Thread callingThread = Thread.currentThread();
    if(!isReader(callingThread)){
      throw new IllegalMonitorStateException("Calling Thread does not" +
        " hold a read lock on this ReadWriteLock");
    }
    int accessCount = getReadAccessCount(callingThread);
    if(accessCount == 1){ readingThreads.remove(callingThread); }
    else { readingThreads.put(callingThread, (accessCount -1)); }
    notifyAll();
  }

  public synchronized void lockWrite() throws InterruptedException{
    writeRequests++;
    Thread callingThread = Thread.currentThread();
    while(! canGrantWriteAccess(callingThread)){
      wait();
    }
    writeRequests--;
    writeAccesses++;
    writingThread = callingThread;
  }

  public synchronized void unlockWrite() throws InterruptedException{
    if(!isWriter(Thread.currentThread()){
      throw new IllegalMonitorStateException("Calling Thread does not" +
        " hold the write lock on this ReadWriteLock");
    }
    writeAccesses--;
    if(writeAccesses == 0){
      writingThread = null;
    }
    notifyAll();
  }

  private boolean canGrantWriteAccess(Thread callingThread){
    if(isOnlyReader(callingThread))    return true;
    if(hasReaders())                   return false;
    if(writingThread == null)          return true;
    if(!isWriter(callingThread))       return false;
    return true;
  }

  private int getReadAccessCount(Thread callingThread){
    Integer accessCount = readingThreads.get(callingThread);
    if(accessCount == null) return 0;
    return accessCount.intValue();
  }

  private boolean hasReaders(){
    return readingThreads.size() > 0;
  }

  private boolean isReader(Thread callingThread){
    return readingThreads.get(callingThread) != null;
  }

  private boolean isOnlyReader(Thread callingThread){
    return readingThreads.size() == 1 &&
           readingThreads.get(callingThread) != null;
  }

  private boolean hasWriter(){
    return writingThread != null;
  }

  private boolean isWriter(Thread callingThread){
    return writingThread == callingThread;
  }

  private boolean hasWriteRequests(){
      return this.writeRequests > 0;
  }

}

Calling unlock() From a finally-clause

When guarding a critical section with a ReadWriteLock, and the critical section may throw exceptions, it is important to call the readUnlock() and writeUnlock() methods from inside a finally-clause. Doing so makes sure that the ReadWriteLock is unlocked so other threads can lock it. Here is an example:

lock.lockWrite();
try{
  //do critical section code, which may throw exception
} finally {
  lock.unlockWrite();
}

This little construct makes sure that the ReadWriteLock is unlocked in case an exception is thrown from the code in the critical section. If unlockWrite() was not called from inside a finally-clause, and an exception was thrown from the critical section, the ReadWriteLock would remain write locked forever, causing all threads callinglockRead() or lockWrite() on that ReadWriteLock instance to halt indefinately. The only thing that could unlock the ReadWriteLockagain would be if the ReadWriteLock is reentrant, and the thread that had it locked when the exception was thrown, later succeeds in locking it, executing the critical section and calling unlockWrite() again afterwards. That would unlock the ReadWriteLock again. But why wait for that to happen, if it happens? CallingunlockWrite() from a finally-clause is a much more robust solution.

Original link: http://www.javaol.net/2011/02/read-write-locks-in-java/