2
\$\begingroup\$

Inspired by the following leet-code

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads. Thread A will call foo() while thread B will call bar(). Modify the given program to output "foobar" n times.

Example 1:

Input: n = 1 Output: "foobar" Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar(). "foobar" is being output 1 time.

Example 2:

Input: n = 2 Output: "foobarfoobar" Explanation: "foobar" is being output 2 times.

My solution, which is was accepted:

class FooBar {
    private static class Syncer {
        int status;
    }
    
    private int n;
    private Syncer syncer = new Syncer();

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        synchronized(syncer) {
            for (int i = 0; i < n; i++) {
                while (syncer.status != 0){
                    syncer.wait();
                }            
                printFoo.run();
                syncer.status = 1;
                syncer.notifyAll();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        synchronized(syncer) {
            for (int i = 0; i < n; i++) {
                while (syncer.status != 1){
                    syncer.wait();
                }   
                printBar.run();
                syncer.status = 0;
                syncer.notifyAll();            
            }
         }
    }
}

Questions:

  • Do you see any cases, where this solution would not work? (Assuming the input is correct, i.e. n>=1.)

I'm thinking of cases where one thread would not necessarily see the changes to syncer due to it not being volatile and synchronized. (I know this exact issue does not affect my solution, because syncer is, in fact synchronized, so what I mean if there are other similar "pitfalls" which affect the code above.)

  • Do you see any issues with performance? (I know the code waits in a while-loop, but it calls wait, which is supposed to be optimal.)

  • In general, is there a way this solution could be improved?

  • Does this pattern (threads running multiple times in a given order and waiting for each other) have a name, or a high-level Java concurrency object which implements them? (Slightly related: what better name would you give to syncer?)

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

Because of the initial constraints (a for loop for two threads different why one prints "foo" and the other one prints "bar") set by leetcode site on the problem I see no alternatives to the way you solved it. Answering your first question:

Do you see any cases, where this solution would not work? (Assuming the input is correct, i.e. n>=1.)

None, because you are setting the guard condition to one initial value (0) and you are ensuring the alternate order with wait and notify.

Your second question:

Do you see any issues with performance? (I know the code waits in a while-loop, but it calls wait, which is supposed to be optimal.)

Again, following leetcode constraints there are no alternatives, while it seems that from some solutions posted on the site if you are less strict with constraints performance can be better, but this is probably bound to the fact that threads just print one string and nothing else, so wait and notify calls represent a significative portion of working time.

Your third question:

In general, is there a way this solution could be improved?

You can use for the lock instead of your static class an Object instance and a boolean variable for the condition, but result should be quite similar.

Fourth question:

Does this pattern (threads running multiple times in a given order and waiting for each other) have a name, or a high-level Java concurrency object which implements them? (Slightly related: what better name would you give to syncer?)

I see this situation like a token ring anomalous case where the token is in this case the value of the status guard, with more than two threads you could use a String token with the name of thread that would be activated.

\$\endgroup\$

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.