Results 1 to 3 of 3
  1. #1
    gandrew is offline Member
    Join Date
    Nov 2010
    Posts
    8
    Rep Power
    0

    Default HashSet, Testing Concurrency using multiple threads

    A number of threads will access a serial number generator (class SerialNumberGenerator). The threads will generate and store the numbers in a HashSet. The purpose of the HashSet is to verify that the numbers are unique. According to Java documentation on HashSets these recommendations are made (https://docs.oracle.com/javase/7/doc...HashSet.html):

    Note that this implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set:

    Set s = Collections.synchronizedSet(new HashSet(...));

    The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.


    The HashSet is defined in class SerialNoHashSet with this declaration: set = Collections.synchronizedSet(new HashSet<Integer>());


    The threads that access the number generator and store the serial numbers into the HashSet are from class RetrieveSerialNumbers. Three of these runnable tasks are instantiated. They will each contribute 20 integers to the HashSet (1..60). Another thread (TraverseThread) will iterate through the HashSet to check that the HashSet has been populated with unique numbers. It seems that the TraverseThread which simply prints the HashSet integers will sometimes (or very often) throw a ConcurrentModificationException*. There will be different results in program runs on account of operating system interleaving. For example, the traverse thread might run first and there is nothing in the HashSet to print out.

    The ConcurrentModificationException is thrown by the Traverse thread-task by accessing the printSerialNumbers method in the SerialNoHashSet class. The HashSet will still fill up with 60 integers. The exception is not fatal as the documentation points out. Commenting out the launch of the Traverse thread will eliminate the exception. (RetrieveSerialNumbers class, main method)

    launchFirst.start();
    launchSecond.start();
    launchThird.start();
    // Commenting out the below line will eliminate the ConcurrentModificationException
    //launchTraverse.start();

    1. What then is the value of the synchronizedSet wrapper on the HashSet when its difficult to tell what's in it? The iterator is only displaying contents, it's not modifying the HashSet. A strange limitation.

    2. In fact the Collections.synchronizedSet(...) seems to be unnecessary--even in this multi-threaded experiment. Surprisingly, this declaration works. (At least I can't get it to fail. The trouble-making Traverse iterating thread is commented out as above)

    In the SerialNoHashSet class. The original synchronized wrapper is commented out.

    //set = Collections.synchronizedSet(new HashSet<Integer>());
    set = new HashSet<Integer>();

    It appears the threads fill the HashSet with its 60 integers, despite the documentation warning. Synchronization is not used anywhere. What to conclude from this?

    -----------------------------------------------------------------------
    *Example run with exception.

    Main begin...
    Main end...
    Now running First Thread
    Now running Second Thread
    Now running Traverse Thread
    Printing HashSet contents of 0 elements
    Second Thread 1
    First Thread 2
    ....
    Second Thread 59
    Second Thread 60
    Finished running Second Thread
    Exception in thread "Traverse Thread" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.ja va:1429)
    at java.util.HashMap$KeyIterator.next(HashMap.java:14 53)
    at bloch.SerialNoHashSet.printSerialNumbers(SerialNoH ashSet.java:67)
    at bloch.TraverseThread.run(TraverseThread.java:16)
    at java.lang.Thread.run(Thread.java:745)


    Java Code:
    
    /*
     *  Bloch p262  A case where volatile will not always work.  ++ is not an atomic operation.
     *  The cure is using AtomicInteger.
     */
    
    
    public class SerialNumberGenerator {
    
        private static volatile int nextSerialNumber = 1;
       
        public static int generateSerialNumber() {
            return nextSerialNumber++;
        }
        
    }
    
    
    /*
    * Some Oracle documentation on Sets:  https://docs.oracle.com/javase/7/docs/api/index.html?java/util/HashSet.html
    * 
    * Note that this implementation is not synchronized. If multiple threads access a hash set
    * concurrently, and at least one of the threads modifies the set, it must be synchronized
    * externally. This is typically accomplished by synchronizing on some object that naturally
    *  encapsulates the set. If no such object exists, the set should be "wrapped" using the
    *  Collections.synchronizedSet method. This is best done at creation time, to prevent
    *  accidental unsynchronized access to the set:
    
      Set s = Collections.synchronizedSet(new HashSet(...));
    
    The iterators returned by this class's iterator method are fail-fast: if the set is modified
     at any time after the iterator is created, in any way except through the iterator's own 
     remove method, the Iterator throws a ConcurrentModificationException. Thus, in the face
      of concurrent modification, the iterator fails quickly and cleanly, rather than risking
       arbitrary, non-deterministic behavior at an undetermined time in the future.
    
    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally
     speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent
      modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort
       basis. Therefore, it would be wrong to write a program that depended on this exception
        for its correctness: the fail-fast behavior of iterators should be used only to detect
         bugs. 
    */
    
    import java.util.Collections;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.Set;
    
    import javax.swing.JOptionPane;
    
    public class SerialNoHashSet {
    
    	
        private static Set<Integer> set;
       
        public SerialNoHashSet() {
           
        	// Synchronized wrapper on the HashSet--does not prevent the ConcurrentModificationException
        	// if a thread is traversing the set, depending on timing. There is no advantage over using
        	// the commented out declaration.
            set = Collections.synchronizedSet(new HashSet<Integer>());
             //set = new HashSet<Integer>();  
        }
       
        // Adds an integer to the hashset. Attempt to add a duplicate number is flagged.
        public static void addSerialNumber(int sn) {
            Integer i = (Integer)sn;
            if (set.add(i)==false) {
                System.out.println("Tried to add duplicate " + i.toString());
                JOptionPane.showMessageDialog(null, "Tried to add duplicate no. " + i.toString());
               
            }
            
            i = null;
        }
     
        // Display hashset integers for verification. Making this method public synchronized seems
        // to get rid of the Concurrent ModificationException. May have no entries though, depending
        // on thread interleaving.
        public static void printSerialNumbers() {
        	System.out.println("Printing hashSet contents of " + set.size() + " elements ");
        	for (int i: set) {
        		System.out.print(i + " ");
        	}
        	System.out.println();
        }
    }
    /*
     *  Program:    RetrieveSerialNumbers.java
     *  Date:        05-09-2016    26C 
     *  Purpose:     Trying to demonstrate Bloch's example of a volatile serial number generator
     *  that has a flaw.  It involves generating possibly duplicate numbers. 
        Adds consecutive integers from SerialNumberGenerator into a hashset.
        
     */
    
    public class RetrieveSerialNumbers implements Runnable {
    
    	private String threadName;
        private final int  LIMIT = 20;
        private SerialNoHashSet hashSet;
       
        public RetrieveSerialNumbers(String threadName) {
            this.threadName = threadName;
            hashSet = new SerialNoHashSet();  // Stores the serial numbers retrieved into a HashSet
            //System.out.println("Thread name: " + Thread.currentThread().getName());
        }
       
    
        public void run() {
            Thread.currentThread().setName(threadName);
            int i = 1;
            int serialNo = 0;
    
            //System.out.println();
            System.out.println("Now running " + Thread.currentThread().getName());
           
            while (i <= LIMIT) {
                serialNo = SerialNumberGenerator.generateSerialNumber();
                System.out.println(Thread.currentThread().getName() + " " + serialNo);
                // Put the serial numbers in a HashSet to see if there are any duplicates
                hashSet.addSerialNumber(serialNo);
                i++;
            }
           
            // Did it work?
            //hashSet.printSerialNumbers();
            System.out.println("Finished running " + Thread.currentThread().getName());
        }
       
       
        public static void main(String[] args) {
            System.out.println("Main begin...");
           
            
            RetrieveSerialNumbers firstThread = new RetrieveSerialNumbers("First Thread");
            RetrieveSerialNumbers secondThread = new RetrieveSerialNumbers("Second Thread");
            RetrieveSerialNumbers thirdThread = new RetrieveSerialNumbers("Third Thread");
            TraverseThread traverseThread = new TraverseThread("Traverse Thread");
            
            Thread launchFirst = new Thread(firstThread);
            Thread launchSecond = new Thread(secondThread);
            Thread launchThird = new Thread(thirdThread);
            Thread launchTraverse = new Thread(traverseThread);
            
            launchFirst.start();
            launchSecond.start();
            launchThird.start();
            // Commenting out the below line will eliminate the ConcurrentModificationException
            launchTraverse.start();
            
           
            System.out.println("Main end...");
    
        }
    
    }
    
    
    // Simply prints out contents of the hashset, hopefully while it's being constructed.
    public class TraverseThread implements Runnable {
    
    	private String threadName;
    	
    	public TraverseThread(String threadName) {
    		this.threadName = threadName;
    	}
    	
    	public void run() {
    		Thread.currentThread().setName(threadName);
    		
    		System.out.println("Now running " + Thread.currentThread().getName());
    		SerialNoHashSet.printSerialNumbers();
    		System.out.println("Finished Thread: " + Thread.currentThread().getName());
    	}
    }

  2. #2
    Norm's Avatar
    Norm is online now Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    20,001
    Rep Power
    33

    Default Re: HashSet, Testing Concurrency using multiple threads

    Do you have any java programming questions?
    If you don't understand my response, don't ignore it, ask a question.

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: HashSet, Testing Concurrency using multiple threads

    Quote Originally Posted by gandrew View Post
    What to conclude from this?
    That either you did it wrong or I don't know what you are trying to do. Here is a simpler example of what
    I think you are trying to test.

    Java Code:
    import java.util.Collections;
    import java.util.HashSet;
    import java.util.Set;
    
    public class SyncSetDemo {
       volatile boolean    flag    = true;
       Set<Integer>        dataSet    = Collections.synchronizedSet(new HashSet<>());
    //    Set<Integer> dataSet = new HashSet<>();
    
       public static void main(String[] args) {
          new SyncSetDemo().start();
       }
    
       public void start() {
          int reps = 20;
          while (reps-- > 0) {
             Thread t1 = new Thread(getRunnable(dataSet, 1, 20_000));
             Thread t2 = new Thread(getRunnable(dataSet, 20_001, 40_000));
             Thread t3 = new Thread(getRunnable(dataSet, 40_001, 60_000));
             t1.start();
             t2.start();
             t3.start();
             flag = false; // and they're off!!
             while (Thread.activeCount() > 1) {
                try {
                   Thread.sleep(100);
                }
                catch (InterruptedException ie) {
                }
             }
             System.out.println(dataSet.size());
             dataSet.clear();
          }
       }
    
       public Runnable getRunnable(Set<Integer> set, int start, int end) {
          return new Runnable() {
             public void run() {
                int number = start;
                while (flag) {
                } ;
                while (number <= end) {
                   set.add(number++);
                }
             }
          };
       }
    }
    Note that when all three threads run with unsynchronized set, the total number of entries is inconsistent and usually less than
    the expected 60,000. And in some cases, internal errors arise. If you choose the synchronized set, then the entries are added
    appropriately and they always total 60,000.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Similar Threads

  1. testing threads
    By phoenox7 in forum Threads and Synchronization
    Replies: 3
    Last Post: 02-24-2013, 02:12 PM
  2. One process open multiple threads on multiple CPUs
    By kfcnhl in forum Threads and Synchronization
    Replies: 2
    Last Post: 12-12-2011, 08:27 AM
  3. Running multiple threads on multiple CPU cores?
    By Dosta in forum Threads and Synchronization
    Replies: 2
    Last Post: 09-19-2010, 03:48 PM
  4. Concurrency system, and threads.
    By scarymovie in forum New To Java
    Replies: 2
    Last Post: 03-05-2009, 02:20 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •