Чередование вывода `foo` и `bar`

34. Обеспечить чередование вывода foo и bar

Условие задачи:
Дан класс FooBar. Одна и та же его инстанция используется двумя потоками:

поток A вызывает метод foo();
поток B вызывает метод bar().

Каждый метод должен выполнить вывод n раз.

Необходимо синхронизировать потоки так, чтобы строки foo и bar выводились строго по очереди:

foobarfoobar...

Всего последовательность foobar должна повториться ровно n раз.

Код:

class FooBar {
    private final int n;

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

    public void foo() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            System.out.print("foo");
        }
    }

    public void bar() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            System.out.print("bar");
        }
    }
}

Примеры:

n = 1
→ foobar

n = 2
→ foobarfoobar

n = 5
→ foobarfoobarfoobarfoobarfoobar

Спойлеры к решению

Подсказки

💡 Удобно использовать два Semaphore.
💡 Для foo создай семафор с одним разрешением, чтобы этот поток мог начать первым.
💡 Для bar создай семафор с нулём разрешений, чтобы он сначала ожидал.
💡 После вывода foo нужно разрешить работу bar, а после bar — снова разрешить foo.

Решение

class FooBar {

    private final int n;

    private final Semaphore fooSemaphore = new Semaphore(1);
    private final Semaphore barSemaphore = new Semaphore(0);

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

    public void foo() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSemaphore.acquire();

            System.out.print("foo");

            barSemaphore.release();
        }
    }

    public void bar() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSemaphore.acquire();

            System.out.print("bar");

            fooSemaphore.release();
        }
    }
}

Начальные значения семафоров:

new Semaphore(1);
new Semaphore(0);

означают, что foo() может начать работу сразу, а bar() должен ждать.

Последовательность для первой итерации выглядит так:

fooSemaphore = 1
barSemaphore = 0

foo:
acquire() → 0
print("foo")
barSemaphore.release() → 1

bar:
acquire() → 0
print("bar")
fooSemaphore.release() → 1

После этого цикл повторяется.

Таким образом, даже если поток bar запустится раньше потока foo, он остановится на:

barSemaphore.acquire();

поскольку изначально разрешений у barSemaphore нет.

Для n = 3 гарантируется порядок:

foo → bar → foo → bar → foo → bar

и результат:

foobarfoobarfoobar

Методы acquire() и release() обеспечивают необходимую синхронизацию и видимость изменений между потоками.

Для каждой итерации выполняется константное число операций, поэтому общая сложность — O(n). Дополнительная память — O(1).

Если один из потоков будет прерван и завершит работу раньше второго, второй поток потенциально может остаться ждать разрешения. Для базовой задачи это обычно не требуется обрабатывать отдельно, но в production-коде стоит предусмотреть общий механизм остановки обоих потоков.