1
\$\begingroup\$

Here is my implementation of an all-or-wait-until-all kind of process. Each thread (kid) needs to guarantee it is the only thread processing the required resources (toys) at that moment.

If some resources are not available (being marked by another thread), then it should wait for them and check again next time.

Thread finished processing should notify others about the resources being available again.

Different thread may process on different combination of resources, hence it is possible that multiple threads can be processing together as long as their resources are all different.

package mycode;

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class PlayGround {
    public static class Toy {
        private final String name;
        public Toy(final String name) {
            this.name = new String("<" + name + ">");
        }
        @Override
        public String toString() {
            return name;
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((name == null) ? 0 : name.hashCode());
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            return this == obj || obj != null && obj instanceof Toy && Objects.equals(name, ((Toy) obj).name);
        }
    }

    public static class Kid {
        private final String name;
        public final List<Toy> toysWantToPlay;
        public Kid(final String name, final Toy... toys) {
            this.name = "[" + name + "]";
            toysWantToPlay = Arrays.asList(toys);
        }
        @Override
        public String toString() {
            return name;
        }
    }

    private final ReentrantLock lock = new ReentrantLock();
    private final Map<Toy, Kid> toysTaken = new HashMap<>();

    public void welcome(Kid kid) {
        boolean allToysAreReady = false;
        try {
            try {
                do {
                    lock.lock();
                    allToysAreReady = false;
                    System.out.println(kid + " is checking");
                    Toy toyTaken = kid.toysWantToPlay.stream().filter(toy -> toysTaken.containsKey(toy)).findAny().orElse(null);
                    if (allToysAreReady = (toyTaken == null)) {
                        kid.toysWantToPlay.forEach(toy -> toysTaken.put(toy, kid));
                        System.out.println(kid + " got all toys wanted!");
                    } else {
                        Kid toyOwner = toysTaken.get(toyTaken);
                        synchronized (toyOwner) {
                            System.out.println(kid + " needs to wait for " + toyOwner + " to finish playing " + toyTaken);
                            lock.unlock();
                            toyOwner.wait();
                            System.out.println(toyOwner + " tells " + kid + " " + toyTaken + " has been returned");
                        }
                    }
                } while (!allToysAreReady);
            } finally {
                if (lock.isHeldByCurrentThread()) {
                    lock.unlock();
                }
            }
            if (allToysAreReady) {
                System.out.println(kid + " starts playing~~~");
                Thread.sleep(2000); // busy time
                System.out.println(kid + " finished playing");
            }
        } catch (InterruptedException ie) {
            ie.printStackTrace();
        } finally {
            if (allToysAreReady) {
                lock.lock();
                try {
                    kid.toysWantToPlay.forEach(toy -> {
                        Kid toyOwner = toysTaken.get(toy);
                        synchronized (toyOwner) {
                            toysTaken.remove(toy);
                            toyOwner.notifyAll();
                        }
                    });
                    System.out.println(kid + " returned all the toys");
                } finally {
                    lock.unlock();
                }
            }
        }
    }

    public static void main(String[] args) {
        final Kid e1 = new Kid("Alice", new Toy("DOLL"));
        final Kid e2 = new Kid("Bob", new Toy("ROBOT"));
        final Kid e3 = new Kid("Charlie", new Toy("SLIME"), new Toy("DOLL"), new Toy("ROBOT"));
        final Kid e4 = new Kid("David", new Toy("ROBOT"), new Toy("SLIME"));
        final PlayGround pg = new PlayGround();
        new Thread(() -> pg.welcome(e1)).start();
        new Thread(() -> pg.welcome(e2)).start();
        new Thread(() -> pg.welcome(e3)).start();
        new Thread(() -> pg.welcome(e4)).start();
    }

}

I have tested the code many times and tried many different thread scheduling and I did not see any deadlocking. Could you please see if there are any potential error or any unnecessary exclusive blocking that lowered the efficiency? Thank you.

\$\endgroup\$
2
\$\begingroup\$

The program looks to be thread-safe and is correctly implemented. I have some feedback though.

1. Small improvements

You can simplify the hashCode method of class Toy:

public int hashCode() {
  return Objects.hashCode(name);
}

Make Kid @Immutable:

this.toysWantToPlay = Collections.unmodifiableList(Arrays.asList(toys));

Use Optional:

Optional<Toy> toyTaken = kid.toysWantToPlay.stream().filter(toy -> toysTaken.containsKey(toy)).findAny();

2. Locks and monitors

Instead of using a Lock and monitors (wait/notifyAll), it's easier to use Conditions for such cases.

A taken toy would need to have a condition attached to it. It can either be stored in another Map, or we can store both the Kid and Condition in an object:

public static class ToyOwner {
    public final Kid kid;
    public final Condition condition;

    public ToyOwner(Kid kid, Condition condition) {
        this.kid = kid;
        this.condition = condition;
    }
}

And the program becomes simpler:

private final Map<Toy, ToyOwner> toysTaken = new HashMap<>();

public void welcome(Kid kid) {
    try {
        lock.lock();
        try {
            while (true) {
                System.out.println(kid + " is checking");
                Toy toyTaken = kid.toysWantToPlay.stream().filter(toy -> toysTaken.containsKey(toy)).findAny().orElse(null);

                if (toyTaken == null) {
                    kid.toysWantToPlay.forEach(toy -> toysTaken.put(toy, new ToyOwner(kid, lock.newCondition())));
                    break;
                } else {
                    ToyOwner toyOwner = toysTaken.get(toyTaken);
                    System.out.println(kid + " needs to wait for " + toyOwner.kid + " to finish playing " + toyTaken);
                    toyOwner.condition.await();
                    System.out.println(toyOwner.kid + " tells " + kid + " " + toyTaken + " has been returned");
              }
          }
      } finally {
          lock.unlock();
      }

      System.out.println(kid + " got all toys wanted!");
      System.out.println(kid + " starts playing~~~");
      Thread.sleep(2000); // busy time
      System.out.println(kid + " finished playing");

      lock.lock();
      try {
          kid.toysWantToPlay.forEach(toy -> toysTaken.remove(toy).condition.signalAll());
          System.out.println(kid + " returned all the toys");
      } finally {
          lock.unlock();
      }
   } catch (Exception e) {
      e.printStackTrace();
   }
}

3. Waiting for the threads

At the end of the program, the main thread needs to wait for all threads to finish execution, by calling it's join() method. The reason why the program works is because threads are not daemon.

Another alternative would be to use a ExecutorService.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you so much! I am surprised that using condition can completely replace monitors. Especially the outer most finally to release all the monitors is not needed anymore. Great one! \$\endgroup\$ – user1589188 Nov 1 '17 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.