Fair lock

Не так давно у нас на собеседовании был кандидат, который произвел довольно хорошее впечатление, поэтому было решено предложить ему более сложную задачу, которую обычно мы не спрашиваем. Вот ее немного видоизмененный вариант:

Переделайте следующий код оставив его многопоточным таким образом, чтобы лампочки зажигались и гасли строго по очереди и в любой момент времени должна быть включена только одна лампочка:

package me.bazhenov.bulb;

public class Main {

 public static void main(String[] args) {
  new Thread(new Bulb("first")).start();
  new Thread(new Bulb("seconds")).start();
 }
}

public class Bulb implements Runnable {

 private final String name;

 public Bulb(String name) {
  this.name = name;
 }

 public void run() {
  Thread self = currentThread();
  while(!self.isInterrupted()) {
   System.out.println(name + " bulb is on");
   try {
    sleep(300);
   } catch (InterruptedException e) {
    self.interrupt();
   }
   System.out.println(name + " bulb is off");
  }
 }
}

Кандидат предложил использовать ReentrantLock в FairSync режиме. В первом приближении эта идея может показаться рабочей. Передать общий лок в оба оъекта типа Bulb и синхронизироватся там на нем. Тем не менее, этот подход не работает. Если мы заглянем в документацию к классу, то увидим следующее описание:

The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. [...] Note however, that fairness of locks does not guarantee fairness of thread scheduling.

FairSync не гарантирует отсутствие race condition'а между потоками. Единственное что он гарантирует это то, что лок возьмет поток который ждал на локе дольше всего. Отсутствие контроля за CPU шедулером не дает нам гарантии что в момент когда поток отпускает лок его оппонент уже попытался сделать acquire на этом же локе (что необходимо для того чтобы сработал FairSync в этой задаче).

К сожалению у меня нет под рукой соответствующего железа, но я подозреваю что на однопроцессорной машине разницы между FairSync и NonfairSync вообще не будет, так как у параллельного потока не будет возможности поставить в очередь заявку на acquire, чтобы при следующем unlock'е его заявка была обслужена.

Правильное же решение задачи остается на совести читателя :)