Is not this code violating mutual exclusion in critical section?

Question

I am new to Java and trying to understand concurrency in Java. While exploring I came across this code on quite a popular page on Java concurrency:

public class CrawledSites {
  private List<String> crawledSites = new ArrayList<String>();
  private List<String> linkedSites = new ArrayList<String>();

  public void add(String site) {
    synchronized (this) {
      if (!crawledSites.contains(site)) {
        linkedSites.add(site);
      }
    }
  }


/**
   * Get next site to crawl. Can return null (if nothing to crawl)
   */

  public String next() {
    if (linkedSites.size() == 0) {
      return null;
    }
    synchronized (this) {
      // Need to check again if size has changed
      if (linkedSites.size() > 0) {
        String s = linkedSites.get(0);
        linkedSites.remove(0);
        crawledSites.add(s);
        return s;
      }
      return null;
    }
  }

}

I believe that function next() here is violating mutual exclusion, as below lines:

if (linkedSites.size() == 0) {
  return null;
}

are kept outside synchronized block so in case some thread is modifying linkedSites inside synchronized blocks in add() or next(), other threads are allowed to read it.

Please correct me in case I am wrong.

Answer 1

You are right - I think the code author probably thought they were doing something clever, saving a bit of time by checking that the linkedSites array was not empty before going into a synchronized section. This might look safe because the size is checked again inside the synchronized section.

However, the Java memory model does not guarantee that a thread calling next() will see linkedSites in the same state as the last thread to modify it unless the reading is also done in a synchronized section so theoretically the thread calling next might keep seeing the array as empty despite another thread having put data in there. Each thread can potentially have its own copy of object data which only gets synchronzied with other threads' copies by synchronized code blocks. So, the thread calling next might incorrectly see the array as empty.

Answer 2

You are right in the strict sense of mutual exclusion. But even in multi-threaded programs it is not really necesary to put all into sync when you access e.g. for reading. I don't know the whole program, but next() will be called probably several time. If the thread miss some entry probably some other will catch it later. But, as you said, it is not guaranted that other will see the changes.

Answer 3

linkedSites.size() should be inside synchronized block, otherwise it may not see changes which other threads make to the linkedSites.