Play around with wait and notify

Question

The following is an a self-tutored attempt to take a leap into understanding simple usage of wait() and notify() methods.

The code is responsible for scanning a directory structure with each directory being scanned by a new thread, for the files present in it. All results to get accumulated in a data collection and displayed at the end. The problem is to detect the end, since this is a chain reaction type.

class MyThreadA implements Runnable {
 private String path;
 private static List<String> FILE_LIST;
 private static AtomicInteger ATOMIC_COUNTER;
 static {
 ATOMIC_COUNTER = new AtomicInteger(0);
 FILE_LIST = new LinkedList<>();
 }
 public MyThreadA(String path) {
 this.path = path;
 }
 @Override
 public void run() {
 try {
 int begin = ATOMIC_COUNTER.getAndIncrement();
 File filePath = new File(path);
 File[] listOfFiles = filePath.listFiles();
 synchronized (System.out) {
 for (File temp : listOfFiles) {
 if (temp.isFile()) {
 FILE_LIST.add(temp.getAbsolutePath());
 } else if (temp.isDirectory()) {
 Thread t = new Thread(new MyThreadA(temp.getPath()));
 t.start();
 }
 }
 }
 MyThreadA.decrementCounter();
 //if(begin == 0)
 try {
 synchronized (FILE_LIST) {
 FILE_LIST.wait();
 }
 printList();
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 } catch (Exception e) {
 e.printStackTrace();
 }
 }
 private static void decrementCounter() {
 if (ATOMIC_COUNTER.decrementAndGet() == 0)
 synchronized(FILE_LIST){
 FILE_LIST.notifyAll();
 }
 }
 private static void printList(){
 for(String temp:FILE_LIST){
 System.out.println(temp);
 }
 }
}

Now, as you can see, all such spawned threads will wait to be notified. I can minimize this by letting the 1st thread only to wait, but that introduces one more critical section. I am looking for if there can be a better solution to this using wait() and notify() constructs only, with minimal concurrency tools.

I understand that there are better tools for solving this, but this is solely for learning purpose.

• Dan: I have rolled back the last edit. Please see What to do when someone answers .

Answer 1

There is a race condition in your code. When you call t.start() the thread doesn't start immediately which means that it's possible to have a thread waiting to execute but the current thread can call notifyall before the new thread has a chance to increment the counter. This can be fixed by doing the increment in the constructor instead of in run.

On another note, FILE_LIST.add is not safe to call from multiple threads. All the rest around that is safe. So, the for loop can be reduced to:

for (File temp : listOfFiles) {
 if (temp.isFile()) {
 synchronized (FILE_LIST) {
 FILE_LIST.add(temp.getAbsolutePath());
 }
 } else if (temp.isDirectory()) {
 Thread t = new Thread(new MyThreadA(temp.getPath()));
 t.start();
 }
}

When waiting on an object there is the (documented) possibility of a spurious wakeup, which means that the thread woke up without anyone calling notify.

The way to deal with that is to wait in a loop:

synchronized (FILE_LIST) {
 while(ATOMIC_COUNTER.get() > 0)
 FILE_LIST.wait();
}

The condition is inside the synchronized to avoid a race condition (not the one detailed above though).

• soufrk: Agreed to all your points, but my dilemma is between, - adding a critical section to prevent every thread from waiting, or - lessen the critical section and let all thread wait to be notified
• soufrk: Executed the code with your suggested changes. But it runs significantly slower. I guess that a free gift from concurrent programs.
• ratchet freak: @soufrk yeah just adding threads will add significant overhead for the synchronization between al the threads. I didn't mention doing a threadpool because you wanted to stay with the basics.
• soufrk: Completely agreed with you. Can you take a look at the updated code.

Answer 2

Modified the code like

class MyThreadA implements Runnable {
 private String path;
 // private static List<String> FILE_LIST;
 /*
 * Choosing a simple concurrent collection over
 * traditional List.
 */
 private static Queue<String> FILE_LIST;
 private static AtomicInteger ATOMIC_COUNTER;
 static {
 ATOMIC_COUNTER = new AtomicInteger(0);
 // FILE_LIST = new LinkedList<>();
 /*
 * Initializing 
 */
 FILE_LIST = new ConcurrentLinkedQueue<String>();
 }
 public MyThreadA(String path) {
 this.path = path;
 }
 @Override
 public void run() {
 try {
 int begin = ATOMIC_COUNTER.getAndIncrement();
 File filePath = new File(path);
 File[] listOfFiles = filePath.listFiles();
 synchronized (System.out) {
 for (File temp : listOfFiles) {
 if (temp.isFile()) {
 FILE_LIST.add(temp.getAbsolutePath());
 } else if (temp.isDirectory()) {
 Thread t = new Thread(new MyThreadA(temp.getPath()));
 t.start();
 }
 }
 }
 MyThreadA.decrementCounter();
 // if(begin == 0)
 /*
 * Difficult to understand, but theoretically notify() might
 * get invoked before the following; or wait might be released
 * by JVM without your notice due to internal reasons. 
 */
 while (ATOMIC_COUNTER.get() > 0)
 try {
 synchronized (FILE_LIST) {
 FILE_LIST.wait();
 }
 // printList();
 } catch (InterruptedException e) {
 e.printStackTrace();
 }
 printList();
 } catch (Exception e) {
 e.printStackTrace();
 }
 }
 private static void decrementCounter() {
 if (ATOMIC_COUNTER.decrementAndGet() == 0)
 synchronized (FILE_LIST) {
 FILE_LIST.notifyAll();
 }
 }
 private static void printList() {
 for (String temp : FILE_LIST) {
 System.out.println(temp);
 }
 }
}

There is a significant performance degradation that can be observed. Secondly, I am still wondering if, making 100 threads wait, is better than asking them to execute one more critical section (check for 0 before increment and exit if not).