9 Replies Latest reply: Sep 12, 2011 10:05 AM by YoungWinston RSS

    syncing on the HashMap element

    Johnny_hunter
      Hello All:

      My understanding is that if we want to guarantee the thread safety of the value of a HashMap, syncing on HashMap along is not enough - we have to sync on the value elements as well, if they are used by multiple threads. I wrote a test program to verify this idea:
      import java.util.HashMap;
      import java.util.Map;
      
      public class ThreadSafeMapTest {
      
           static class TestClass{
                private int count=0;
                
                public void increment(){
                     try {
                          Thread.sleep(100);
                     } catch (InterruptedException e) {
                          e.printStackTrace();
                     }
                     count++;
                }
                public void decrement(){
                     try {
                          Thread.sleep(100);
                     } catch (InterruptedException e) {
      
                          e.printStackTrace();
                     }
                     count--;
                }
                public int getCount(){
                     return count;
                }
           }
           
           private Map<String, TestClass> map = new HashMap<String,TestClass>();
           private TestClass tc = new TestClass();
           
           public synchronized void add(){
                map.put("1", tc);
           }
           
           public synchronized TestClass get(String id){
                return map.get(id);
           }
           
           static class Task1 implements Runnable{
                private ThreadSafeMapTest tst;
                Task1(ThreadSafeMapTest tst){
                     this.tst = tst;
                }
                
                @Override public void run(){
                     tst.add();
                     TestClass ts = tst.get("1");
                     for(int i=0;i<10;i++)
                          ts.increment();
                }
           }
           
           static class Task2 implements Runnable{
                private ThreadSafeMapTest tst;
                Task2(ThreadSafeMapTest tst){
                     this.tst = tst;
                }
                
                @Override public void run(){
                     tst.add();
                     TestClass ts = tst.get("1");
                     for(int i=0;i<5;i++)
                          ts.decrement();
                }
           }
           
           public static void main(String[] args) {
                ThreadSafeMapTest tst = new ThreadSafeMapTest();
                Thread t1 = new Thread(new Task1(tst));
                t1.start();
                Thread t2 = new Thread(new Task2(tst));
                t2.start();
                
                /*try {
                     t1.join();
                     t2.join();
                } catch (InterruptedException e) {
                     e.printStackTrace();
                }*/
                
                try {
                     Thread.sleep(1000);
                } catch (InterruptedException e) {
                     e.printStackTrace();
                }
                TestClass ts = tst.get("1");
                System.out.println(ts.getCount());
           }
      }
      In the code above, operations such as "add" and "get" against the Map are properly synced, but it's element, whose type is TestClass, is not (the methods in TestClass don't have synced block). So when the TestClass instance is exposed to my two threads, carried out by Task1 (increasing a counter by 10 times) and Task2(decreasing the same counter by 5 times) , I am expecting some count other than 5. However, when the counter is printed, the result is always 5 - as if TestClass is thread safe too.

      Is there anything wrong in my designed test? Or my understanding is wrong, or is that the test is not sufficient?

      Thanks,
      John
        • 1. Re: syncing on the HashMap element
          796440
          Johnny_hunter wrote:
          Hello All:

          My understanding is that if we want to guarantee the thread safety of the value of a HashMap, syncing on HashMap along is not enough - we have to sync on the value elements as well, if they are used by multiple threads.
          Yes and no. You do have to sync on something for objects that are used by multiple threads where one or more of the threads can be changing the object's state. But it doesn't matter what you sync on, as long as all threads use the same lock. And I would not generally sync my map operations on the same lock as my operations on the value objects.

          If every access to the Map is synced on the same lock--typically the Map itself--and every iteration over keySet(), entrySet(), and values() is also synced on that same lock, then your use of the Map will be threadsafe.

          Now, if you get() a value from the map and then use that element in multiple threads, and at least one of those threads is changing the state of that object, then, yes, the use of that object would need to be synchronized as well. That generally has nothing to do with the Map, however, and I would usually use a separate lock for that synchronization. It really depends on you specific use case though.
          I wrote a test program to verify this idea:
          buncha code snipped
          In the code above, operations such as "add" and "get" against the Map are properly synced, but it's element, whose type is TestClass, is not (the methods in TestClass don't have synced block). So when the TestClass instance is exposed to my two threads, carried out by Task1 (increasing a counter by 10 times) and Task2(decreasing the same counter by 5 times) , I am expecting some count other than 5. However, when the counter is printed, the result is always 5 - as if TestClass is thread safe too.
          Just because something can go wrong with multithreading, that doesn't mean it will. It's basically impossible to test for thread safety.

          I'm not going to read your code, but my guess is that whatever you're testing is happening too fast for a context switch. That's often the case when people try to write small test programs to show threads running concurrently.

          Edited by: jverd on Sep 11, 2011 10:24 AM
          • 2. Re: syncing on the HashMap element
            Johnny_hunter
            thanks, Jverd.
            >
            ...however, and I would usually use a separate lock for that synchronization.
            >
            agree. I wouldn't use Map as the monitor if I did want to make the value object thread safe(which didn't serve my purpose of testing thou), I might have just put "synchronized" to decorate the value object's methods, thus factually syncing on value object itself.

            >
            but my guess is that whatever you're testing is happening too fast for a context switch. That's often the case when people try to write small test programs to show threads running concurrently.
            >
            That's why i put the Thread.sleep for a delay before I increment/decrement the counter, will it help?

            Thanks again, John
            • 3. Re: syncing on the HashMap element
              796440
              Johnny_hunter wrote:
              >
              but my guess is that whatever you're testing is happening too fast for a context switch. That's often the case when people try to write small test programs to show threads running concurrently.
              >
              That's why i put the Thread.sleep for a delay before I increment/decrement the counter, will it help?
              It can, yes, that's a common way to observe multithreading effects. I haven't looked closely enough at your code to see what's going on though.
              • 4. Re: syncing on the HashMap element
                796440
                Okay, I looked at your code, and I stand by my initial guess. You're doing 10 incs and 5 decs, so in a single-threaded context or a properly synced multithreaded context, you'll get 5.

                So what could cause a different value? The only possibility in a single CPU situation is due to the non-atomicity of ++ and ---, and in a multi-CPU situation we also have the chance of threads' local copies of shared variables leading to different values.

                For instance, count++ involves 1) read count, 2) add 1, 3) write the new value back to count, and likewise for --. So if count is at 3, we could have the following:
                T1 reads 3. 
                                   T2 reads 3.
                                   T2 decrements to 2. 
                                   T2 writes 2. 
                T1 incs to 4.
                T1 writes 4.
                So we end up with 4, when the inc and dec should have left us back at 3.

                However, this kind of concurrent inc/dec is the only way in which we could get a different values. The sleeps don't help you to get different values here. In fact, they probably hurt you. You'd have to be able to put a sleep between the above 1, 2, 3 steps.

                If you're running on a single CPU/core, it's unlikely that a thread will get swapped out mid inc/dec, especially with those sleeps there. And if you take the sleeps out, then one thread will get to do all its incs or decs before the other thread does anything. The only way you might see a different value in a single-CPU situation is if you have no sleeps and a very large number of incs/decs (million or billions).

                If you've got multiple CPUs and get rid of the sleeps and use a larger number of incs and decs, then you could get a different value. This will not be due to non-atomicity reasons, however, but because each thread can have its own copy of the count variable. There's no guarantee though. We only know that it can happen, not that it will.
                • 5. Re: syncing on the HashMap element
                  Johnny_hunter
                  >
                  You'd have to be able to put a sleep between the above 1, 2, 3 steps.
                  >
                  I think this tells me how to proceed - I made these code changes:
                  public void increment(){
                                 int temp = count;
                                 temp++;
                                 
                                 try {
                                      Thread.sleep(100);
                                 } catch (InterruptedException e) {
                                      e.printStackTrace();
                                 }
                                 
                                 count = temp;
                            }
                  the same change to decrement was applied. And now I can see the inconsistency of the counter: it returns randomly 2, 6, 8,10, etc.

                  BTW, my CPU is i7-950, the spec says it has 4 physical cores with 2 virtual ones each, and Runtime#availableProcessor() returns 8. However, as you said, we might need to iterate millions or billions times plus some baby luck to observe the inconsistency, if not deliberately manipulating the code.

                  Thanks, John
                  • 6. Re: syncing on the HashMap element
                    Johnny_hunter
                    and put synchronized in the code
                    public synchronized void increment()
                    public synchronized void decrement()
                    public synchronized int getCount()
                    makes the value object thread safe, the test is as expected.
                    • 7. Re: syncing on the HashMap element
                      YoungWinston
                      Johnny_hunter wrote:
                      and put synchronized in the code
                      public synchronized void increment()
                      public synchronized void decrement()
                      public synchronized int getCount()
                      makes the value object thread safe, the test is as expected.
                      An alternative would be to use an AtomicInteger as your counter; in fact, it might be preferable.

                      Also, as far as syncing a HashMap is concerned, I'd suggest looking at [url http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedMap%28java.util.Map%29]Collections.synchronizedMap().

                      Winston
                      • 8. Re: syncing on the HashMap element
                        Johnny_hunter
                        thanks Winston. However, the purpose of my test is to prove that syncing on a hashmap along can't safegouard its value object. To prove it, I need to delibrately break the atomicity rather than enforcing it. Sure, later I also synced on the value object to prove that what we need to do to make both map and its values thread safe, but the specific techniques (using AtomicInteger or simply syncing on values) is not very relevant to the argument.
                        • 9. Re: syncing on the HashMap element
                          YoungWinston
                          Johnny_hunter wrote:
                          thanks Winston. However, the purpose of my test is to prove that syncing on a hashmap along can't safegouard its value object.
                          I guess I don't understand the rationale then. A class is either Thread-safe or it isn't; the fact that your class happens to be the value in a Map entry is irrelevant. A HashMap itself can be made "Thread safe" as far as atomic operations are concerned, but not as far as it's overall contents are (at least not without external code).

                          And AtomicInteger is a bit more than just a synchronized Integer; it uses native code (including, I believe, hardware CAS instructions, if available) to provide a Thread-safe mutable value that is as fast as it can be...until the next improvement, that is :-).

                          Winston