Threads: Producer-Consumer Problem

Producer-Consumer problem is a very common question related to threads. Following is a simple solution to the problem. QueueClass represents the queue which both the Producer and Consumer has to access. The critical methods in the QueueClass - add() and remove() are synchronized in order to maintain the status quo between the Producer and Consumer threads.

view plainprint?

1. import java.util.List;  
2. import java.util.ArrayList;  
3.   
4. public class ProducerConsumerTest {  
5.   
6.  /** 
7.   * @param args 
8.   */  
9.  public static void main(String[] args) {  
10.   QueueClass q = new QueueClass();  
11.   Producer p = new Producer(q, 10);  
12.   Consumer c = new Consumer(q, 10);  
13.     
14.   Thread t1 = new Thread(p);  
15.   Thread t2 = new Thread(c);  
16.   c.setpThread(t1);  
17.   t1.start();  
18.   t2.start();  
19.  }  
20.   
21. }  
22.   
23. class Producer implements Runnable {  
24.  QueueClass q;  
25.  int size;  
26.    
27.  Producer(QueueClass q, int size) {  
28.   this.q = q;  
29.   this.size = size;  
30.  }  
31.   
32.  public void run() {  
33.   int index = -1;  
34.   while(true) {  
35.    q.add(new String("" + ++index));  
36.    try {  
37.     Thread.sleep(1000);  
38.    }  
39.    catch(InterruptedException e) {  
40.     e.printStackTrace();  
41.    }  
42.   }  
43.  }  
44. }  
45.   
46. class Consumer implements Runnable {  
47.  QueueClass q;  
48.  int size;  
49.  Thread pThread;  
50.    
51.  public void setpThread(Thread pThread) {  
52.   this.pThread = pThread;  
53.  }  
54.   
55.  Consumer(QueueClass q, int size) {  
56.   this.q = q;  
57.   this.size = size;  
58.  }  
59.   
60.  public void run() {  
61.   while(true) {  
62.    q.remove();  
63.    try {  
64.     Thread.sleep(1000);  
65.    }  
66.    catch(InterruptedException e) {  
67.     e.printStackTrace();  
68.    }  
69.   }  
70.  }  
71. }  
72.   
73. class QueueClass {  
74.  List<string> queue = new ArrayList<string>();  
75.  int size = 10;  
76.    
77.  public synchronized void add(String s) {  
78.   if(getSize() < size) queue.add(s);  
79.   System.out.println("Added: " + queue);  
80.   try {  
81.    if(getSize() >= size) {  
82.     notifyAll();  
83.     wait();  
84.    }  
85.   }  
86.   catch(InterruptedException e) {  
87.    e.printStackTrace();  
88.   }  
89.  }  
90.    
91.  public synchronized void remove() {  
92.   if(getSize() > 0) queue.remove(queue.size()-1);  
93.   System.out.println("Removed: " + queue);  
94.   try {  
95.    if(getSize() <= 0) {  
96.     notifyAll();  
97.     wait();  
98.    }  
99.   }  
100.   catch(InterruptedException e) {  
101.    e.printStackTrace();  
102.   }  
103.  }  
104.    
105.  public synchronized int getSize() {  
106.   return queue.size();  
107.  }  
108. }  
109.   
110. </string></string>  

import java.util.List;
import java.util.ArrayList;

public class ProducerConsumerTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  QueueClass q = new QueueClass();
  Producer p = new Producer(q, 10);
  Consumer c = new Consumer(q, 10);
  
  Thread t1 = new Thread(p);
  Thread t2 = new Thread(c);
  c.setpThread(t1);
  t1.start();
  t2.start();
 }

}

class Producer implements Runnable {
 QueueClass q;
 int size;
 
 Producer(QueueClass q, int size) {
  this.q = q;
  this.size = size;
 }

 public void run() {
  int index = -1;
  while(true) {
   q.add(new String("" + ++index));
   try {
    Thread.sleep(1000);
   }
   catch(InterruptedException e) {
    e.printStackTrace();
   }
  }
 }
}

class Consumer implements Runnable {
 QueueClass q;
 int size;
 Thread pThread;
 
 public void setpThread(Thread pThread) {
  this.pThread = pThread;
 }

 Consumer(QueueClass q, int size) {
  this.q = q;
  this.size = size;
 }

 public void run() {
  while(true) {
   q.remove();
   try {
    Thread.sleep(1000);
   }
   catch(InterruptedException e) {
    e.printStackTrace();
   }
  }
 }
}

class QueueClass {
 List queue = new ArrayList();
 int size = 10;
 
 public synchronized void add(String s) {
  if(getSize() < size) queue.add(s);
  System.out.println("Added: " + queue);
  try {
   if(getSize() >= size) {
    notifyAll();
    wait();
   }
  }
  catch(InterruptedException e) {
   e.printStackTrace();
  }
 }
 
 public synchronized void remove() {
  if(getSize() > 0) queue.remove(queue.size()-1);
  System.out.println("Removed: " + queue);
  try {
   if(getSize() <= 0) {
    notifyAll();
    wait();
   }
  }
  catch(InterruptedException e) {
   e.printStackTrace();
  }
 }
 
 public synchronized int getSize() {
  return queue.size();
 }
}

Linked List

Linked list is a fundamental data structure, which uses reference stored in each node to iterate through subsequent nodes. A linked list has many types like singly linked list, doubly linked list and circular linked list. Following is a simple bare bone implementation of singly linked list:

The base interface:

view plainprint?

1. public interface LinkedList<t> {  
2.  public boolean add(T t);  
3.  public boolean remove(T t);  
4.  public void removeAll();  
5.  public int size();  
6.  public boolean isEmpty();  
7. }</t>  

public interface LinkedList {
 public boolean add(T t);
 public boolean remove(T t);
 public void removeAll();
 public int size();
 public boolean isEmpty();
}

Class representing each node:

view plainprint?

1. public class LinkNode<t> {  
2.  private LinkNode<t> nextNode = null;  
3.  private T node = null;  
4.   
5.  public LinkNode() {  
6.     
7.  }  
8.    
9.  public LinkNode(T node) {  
10.   this.node = node;  
11.  }  
12.    
13.  public T getNode() {  
14.   return node;  
15.  }  
16.   
17.  public void setNode(T node) {  
18.   this.node = node;  
19.  }  
20.    
21.  public LinkNode<t> getNextNode() {  
22.   return nextNode;  
23.  }  
24.   
25.  public void setNextNode(LinkNode<t> nextNode) {  
26.   this.nextNode = nextNode;  
27.  }  
28.    
29.  public String toString() {  
30.   return node.toString();  
31.  }  
32.    
33.  public int hashCode() {  
34.   return node.hashCode();  
35.  }  
36.    
37.  public boolean equals(LinkNode<t> t) {  
38.   return node.equals(t.getNode());  
39.  }  
40. }</t></t></t></t></t>  

public class LinkNode {
 private LinkNode nextNode = null;
 private T node = null;

 public LinkNode() {
  
 }
 
 public LinkNode(T node) {
  this.node = node;
 }
 
 public T getNode() {
  return node;
 }

 public void setNode(T node) {
  this.node = node;
 }
 
 public LinkNode getNextNode() {
  return nextNode;
 }

 public void setNextNode(LinkNode nextNode) {
  this.nextNode = nextNode;
 }
 
 public String toString() {
  return node.toString();
 }
 
 public int hashCode() {
  return node.hashCode();
 }
 
 public boolean equals(LinkNode t) {
  return node.equals(t.getNode());
 }
}

Implementation for a singly linked list:

view plainprint?

1. public class SingleLinkedList<t> implements LinkedList<t> {  
2.  LinkNode<t> header = null;  
3.  LinkNode<t> lastNode = null;  
4.    
5.  public SingleLinkedList() {  
6.     
7.  }  
8.    
9.  public boolean add(T t) {  
10.   LinkNode<t> newNode = new LinkNode<t>(t);  
11.   if(header == null) {  
12.    header = newNode;  
13.   }  
14.   else {  
15.    lastNode.setNextNode(newNode);  
16.   }  
17.   lastNode = newNode;  
18.   return true;  
19.  }  
20.    
21.  public boolean remove(T t) {  
22.   LinkNode<t> tmp = header;  
23.   LinkNode<t> prev = null;  
24.     
25.   while(tmp != null) {  
26.    if(tmp.getNode().equals(t)) {  
27.     if(prev == null) header = null;  
28.     else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());  
29.     return true;  
30.    }  
31.    prev = tmp;  
32.    tmp = tmp.getNextNode();  
33.   }  
34.   return false;  
35.  }  
36.    
37.  public void removeAll() {  
38.   header = null;  
39.  }  
40.    
41.  public boolean isEmpty() {  
42.   return header == null;  
43.  }  
44.    
45.  public int size() {  
46.   LinkNode<t> tmp = header;  
47.   int size = 0;  
48.   while(tmp != null) {  
49.    size++;  
50.    tmp = tmp.getNextNode();  
51.   }  
52.     
53.   return size;  
54.  }  
55.    
56.  public String toString() {  
57.   StringBuffer str = new StringBuffer("[");  
58.   LinkNode<t> tmp = header;  
59.   while(tmp != null) {  
60.    str.append(tmp.toString());  
61.    tmp = tmp.getNextNode();  
62.    if(tmp != null) str.append(", ");  
63.   }  
64.   str.append("]");  
65.   return str.toString();  
66.  }  
67. }</t></t></t></t></t></t></t></t></t></t>  

public class SingleLinkedList implements LinkedList {
 LinkNode header = null;
 LinkNode lastNode = null;
 
 public SingleLinkedList() {
  
 }
 
 public boolean add(T t) {
  LinkNode newNode = new LinkNode(t);
  if(header == null) {
   header = newNode;
  }
  else {
   lastNode.setNextNode(newNode);
  }
  lastNode = newNode;
  return true;
 }
 
 public boolean remove(T t) {
  LinkNode tmp = header;
  LinkNode prev = null;
  
  while(tmp != null) {
   if(tmp.getNode().equals(t)) {
    if(prev == null) header = null;
    else if(tmp.getNextNode() != null) prev.setNextNode(tmp.getNextNode());
    return true;
   }
   prev = tmp;
   tmp = tmp.getNextNode();
  }
  return false;
 }
 
 public void removeAll() {
  header = null;
 }
 
 public boolean isEmpty() {
  return header == null;
 }
 
 public int size() {
  LinkNode tmp = header;
  int size = 0;
  while(tmp != null) {
   size++;
   tmp = tmp.getNextNode();
  }
  
  return size;
 }
 
 public String toString() {
  StringBuffer str = new StringBuffer("[");
  LinkNode tmp = header;
  while(tmp != null) {
   str.append(tmp.toString());
   tmp = tmp.getNextNode();
   if(tmp != null) str.append(", ");
  }
  str.append("]");
  return str.toString();
 }
}

Test class which uses the singly linked list implementation:

view plainprint?

1. public class LinkedListTest {  
2.   
3.  /** 
4.   * @param args 
5.   */  
6.  public static void main(String[] args) {  
7.   // TODO Auto-generated method stub  
8.   LinkedList<string> list = new SingleLinkedList<string>();  
9.   System.out.println("Is list empty? " + list.isEmpty());  
10.     
11.   list.add("1");  
12.   list.add("2");  
13.   list.add("3");  
14.   list.add("2");  
15.   list.add("2");  
16.   list.add("3");  
17.   System.out.println(list.size());  
18.   System.out.println(list);  
19.   System.out.println("Is list empty? " + list.isEmpty());  
20.     
21.   list.remove("2");  
22.   System.out.println(list.size());  
23.   System.out.println(list);  
24.   System.out.println("Is list empty? " + list.isEmpty());  
25.     
26.   list.removeAll();  
27.   System.out.println("Is list empty? " + list.isEmpty());  
28.  }  
29.   
30. }</string></string>  

public class LinkedListTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  LinkedList list = new SingleLinkedList();
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("2");
  list.add("2");
  list.add("3");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.remove("2");
  System.out.println(list.size());
  System.out.println(list);
  System.out.println("Is list empty? " + list.isEmpty());
  
  list.removeAll();
  System.out.println("Is list empty? " + list.isEmpty());
 }

}

Adapter Pattern

-  The adapter acts as the middleman by receiving requests from the client and converting them into requests that make sense on the vendor classes

­-  The adapter implements the target interface and holds an instance of the adaptee

-  The actual interface that the client needs is the target interface

-  We wrap the target interface with an adaptee interface, which does the work of the target interface

-  The client makes the request on the adapter, and the adapter delegates it to the adaptee interface

-  The client doesn't know that the actual work was done by the adaptee

-  Client and the adaptee are decoupled – neither knows about the other

-  Here's how the client uses the adapter

o        The client makes a request to the adapter by calling a method on it using the target interface

o        The adapter translates that request into one or more calls on the adaptee using the adaptee interface

o        The client receives the results of the call and never knows there is an adapter doing the translation

­           

­-  The Adapter Pattern converts the interface of a class into another interface the clients expect

­-  Adapter lets classes work together that couldn't otherwise because of incompatible interfaces

­-  This decouples the client from the implemented interface,

­-  If the interface changes over time, the adapter encapsulates the change so that the client doesn't have to be modified each time it needs to operate against a different interface

­-  It is not necessary that the adapter should wrap only one adaptee – it can hold two or more adaptees that are need to implement the target interface

 

­- There are two types of adapters

o        object adapters – uses composition - the adapter is composed of adaptee

§         it can not only adapt an adaptee class, but any of its subclasses

o        class adapters – uses multiple inheritance - the adapter subclasses both the target and the adaptee

§         it is committed to one specific adaptee class, but it doesn't have to reimplement the entire adaptee

§         it can also override the behavior of the adaptee, since its just subclassing

§         this cannot be used in Java since it involves multiple inheritance

 

­- Although Decorator and Adapter patterns looks similar, they are totally different in intent

o        Decorator wraps an object and adds new behavior

o        Adapter wraps an object and converts it into an interface the client expects

 

­- Following is an example of Adapter pattern. This example adapts an Enumerator to act as an Iterator

view plainprint?

1. public class EnumerationAdapter implements Iterator {  
2.   
3.     Enumeration enumeration;  
4.   
5.     public EnumerationAdapter(Enumeration enumeration) {  
6.   
7.         this.enumeration = enumeration;  
8.   
9.     }  
10.   
11.     public boolean hasNext() {  
12.   
13.         enumeration.hasMoreElements();  
14.   
15.     }  
16.   
17.     public Object next() {  
18.   
19.         enumeration.nextElement();  
20.   
21.     }  
22.   
23.     public void remove() {  
24.   
25.         throw new UnsupportedOperationException();  
26.   
27.     }  
28.   
29. }  

	public class EnumerationAdapter implements Iterator {

		Enumeration enumeration;

		public EnumerationAdapter(Enumeration enumeration) {

			this.enumeration = enumeration;

		}

		public boolean hasNext() {

			enumeration.hasMoreElements();

		}

		public Object next() {

			enumeration.nextElement();

		}

		public void remove() {

			throw new UnsupportedOperationException();

		}

	}