Synchronizing Threads with Semaphores: Practicing Concurrency in Java - LeetCode Problem 1115, "Print FooBar Alternately"

Introduction to Concurrency
In software development, concurrency allows multiple processes or threads to execute simultaneously, often leading to faster execution times and more efficient use of resources. However, effective concurrency management is crucial to avoid issues like race conditions, deadlocks, and inconsistent states. This is where synchronization mechanisms such as semaphores are essential.

Understanding Semaphores
A semaphore is a synchronization tool that controls access to a common resource by multiple threads in a concurrent system. It acts like a counter that regulates how many threads can access a specific part of the code at the same time. The semaphore operations are:

• Acquire: Decreases the semaphore's counter if it's above zero, allowing the thread to proceed. If it's zero, the thread is blocked until another thread releases the semaphore.
• Release: Increments the semaphore's counter, signaling that the thread has finished using the resource, allowing other waiting threads to proceed.

Semaphores are particularly useful for managing dependencies between tasks or ensuring that certain parts of the program run in a specific order.

Problem Description

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");
    }
  }
}

We are given a class FooBar with two methods, foo() and bar(). These methods are designed to print "foo" and "bar," respectively. The challenge is to modify the class so that when these methods are executed by two different threads, the output consistently reads "foobar" repeated n times. This must be achieved regardless of the threads' execution order by the scheduler.

This problem is sourced from LeetCode, specifically from Problem 1115, "Print FooBar Alternately".

Solution Approach
To ensure the correct order of execution ("foo" followed by "bar"), we can use semaphores to coordinate the threads. Here’s how we can modify the existing FooBar class using semaphores to achieve the desired behavior:

1. Introduce Two Semaphores: One semaphore (semFoo) will control the execution of foo(), and the other (semBar) will control bar().
2. Initialize Semaphores: semFoo is initialized with a permit (count = 1), allowing foo() to execute first. semBar is initialized with no permits (count = 0), preventing bar() from executing until foo() is done.
3. Modify the Methods: Each method must acquire its semaphore before proceeding and release the other semaphore after it has performed its task.

Here is the modified version of the FooBar class:

class FooBar {
    private int n;
    private Semaphore semFoo = new Semaphore(1); // Initially, allow foo() to proceed
    private Semaphore semBar = new Semaphore(0); // Initially, prevent bar() from proceeding

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

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            semFoo.acquire(); // Wait until it's allowed to proceed
            printFoo.run();   // This will print "foo"
            semBar.release(); // Allow bar() to proceed
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            semBar.acquire(); // Wait until it's allowed to proceed
            printBar.run();   // This will print "bar"
            semFoo.release(); // Allow foo() to proceed again
        }
    }
}

Running the Code
To demonstrate this solution, we can create an instance of FooBar and start two threads, each responsible for one of the methods:

public class Main {
    public static void main(String[] args) {
        FooBar fooBar = new FooBar(2); // Example for n = 2

        Thread threadA = new Thread(() -> {
            try {
                fooBar.foo(() -> System.out.print("foo"));
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        Thread threadB = new Thread(() -> {
            try {
                fooBar.bar(() -> System.out.print("bar"));
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });

        threadA.start();
        threadB.start();
    }
}

This setup ensures that the output on the console will be "foobarfoobar" for n = 2, demonstrating the power of semaphores in controlling the execution order of threads in Java applications.