摘要：否則會報錯誤不過的原理是基于內(nèi)核中的對象監(jiān)視器完成的有可能導致大量的上下文切換。為了更好的性能，往往使用基于的顯示鎖中的成員變量代替。其中條件隊列是通過鏈表實現(xiàn)的，所以可以支持多個等待隊列。

一、Print in Order
Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Example 1:
Input: [1,2,3]
Output: “firstsecondthird”
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). “firstsecondthird” is the correct output.

方法1：信號量，semaphore和mutex都是內(nèi)核對象，都可用于進程間的同步，并且都特別占用系統(tǒng)資源,區(qū)別是，mutex只能由一個線程(進行)訪問被保護的資源。semaphore 是一種帶計數(shù)的mutex的鎖定，可定義同時訪問被保護的資源的線程數(shù)

import java.util.concurrent.Semaphore;
class Foo {
private static Semaphore firstSemaphore = new Semaphore(1);
private static Semaphore secordSemaphore = new Semaphore(0);
private static Semaphore thirdSemaphore = new Semaphore(0);
public Foo() {

}
public void first(Runnable printFirst) throws InterruptedException {
    firstSemaphore.acquire();
    // printFirst.run() outputs "first". Do not change or remove this line.
    printFirst.run();
    secordSemaphore.release();
}
public void second(Runnable printSecond) throws InterruptedException {
    secordSemaphore.acquire();
    // printSecond.run() outputs "second". Do not change or remove this line.
    printSecond.run();
    thirdSemaphore.release();
}
public void third(Runnable printThird) throws InterruptedException {
    thirdSemaphore.acquire();
    // printThird.run() outputs "third". Do not change or remove this line.
    printThird.run();
    firstSemaphore.release();
}

}
方法2、原子類AtomicInteger,AtomicInteger是一個提供原子操作的Integer類，通過線程安全的方式操作加減

import java.util.concurrent.atomic.AtomicInteger;
class Foo {

private final AtomicInteger count = new AtomicInteger(0);
public Foo() {

}
public void first(Runnable printFirst) throws InterruptedException {
    //自旋，避免進入內(nèi)核態(tài)，不過浪費CPU資源
    while (count.get() != 0) {}
    printFirst.run();
    count.incrementAndGet();
}
public void second(Runnable printSecond) throws InterruptedException {
    while (count.get() != 1) {}
    printSecond.run();
    count.incrementAndGet();
}
public void third(Runnable printThird) throws InterruptedException {
    while (count.get() != 2) {}
    printThird.run();
    count.set(0);
}

}
方法3：倒計時器CountDownLatch，參考方法2。在多線程協(xié)作完成業(yè)務功能時，CountDownLatch能讓我們很輕松實現(xiàn)下面這個需求，當需要等待其他多個線程完成任務之后，主線程才能繼續(xù)往下執(zhí)行業(yè)務功能

二、Print FooBar Alternately
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 2:
Input: n = 2
Output: “foobarfoobar”
Explanation: “foobar” is being output 2 times.

這題其實是題目一的升級版，也可以使用信號量來輕松完成，這里給出其他解法

線程問題無非是要保證一致性、有序性和避免死鎖，可見性可以使用volatile來保證，有序性可以使用鎖來保證，死鎖問題我們可以打破死鎖的條件，也就是需要批量申請好資源或者按順序獲取到所有資源后才算獲取到鎖，比如

class FooBar {
private int n;

private List als;

public FooBar(int n) {
    this.n = n;
    als = new ArrayList<>(2);
}

synchronized void  apply(String pre,String next) {
    while (als.contains(pre)||als.contains(next)) {
        try {
            wait();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    als.add(pre);
    als.add(next);
}

synchronized void  free(String pre,String next) {
    als.remove(pre);
    als.remove(next);
    notifyAll();
}

public void foo(Runnable printFoo) throws InterruptedException {

    for (int i = 0; i < n; i++) {
            apply("bar","foo");
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            free("foo","bar");

    }
}

public void bar(Runnable printBar) throws InterruptedException {

    for (int i = 0; i < n; i++) {
        apply("foo","bar");
        // printBar.run() outputs "bar". Do not change or remove this line.
        printBar.run();
        free("bar","foo");
    }
}

}
但是上面的示例無法滿足本題要求，當n=1時輸出結(jié)果可能是foobar也可以是barfoo，同理n=k時也會有順序性問題，看似通過add和remove字符串順序來解決，但是沒有達到效果，具體分析過程留給讀者完成

我們換種方法來完成，使用標準的生產(chǎn)-消費模型

class FooBar {
private int n;
private Object lock;
private Boolean printFooStatus;
public FooBar(int n) {
    this.n = n;
    lock = new Object();
    printFooStatus = true;
}

public void foo(Runnable printFoo) throws InterruptedException {
    for (int i = 0; i < n; i++) {
          synchronized (lock) {
              //必須使用while
              while (!printFooStatus){
                  lock.wait();
              }
              // printFoo.run() outputs "foo". Do not change or remove this line.
              printFoo.run();
              printFooStatus = false;
               //必須放在synchronized里面
              lock.notifyAll();
          }
    }
}
public void bar(Runnable printBar) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        synchronized (lock) {
            //必須使用while
            while (printFooStatus) {
                lock.wait();
            }
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            printFooStatus = true;
            //必須放在synchronized里面
            lock.notifyAll();
        }
    }
}
}

這里需要注意的幾個點：

1、初學者理解wait()的時候都認為是將當前線程阻塞，所以Thread.currentThread().wait();視乎很有道理。但是不知道大家有沒有發(fā)現(xiàn)，在JDK類庫中wait()和notify()方法并不是Thread類的，而是Object()中的。在其他線程調(diào)用此對象的 notify() 方法或 notifyAll() 方法前，當前線程等待
2、始終使用while循環(huán)來調(diào)用wait方法，永遠不要在循環(huán)外調(diào)用wait方法，這樣做的原因是盡管并不滿足條件，但是由于其他線程調(diào)用notifyAll方法會導致被阻塞線程意外喚醒，此時執(zhí)行條件不滿足，它會導致約束失效
3、喚醒線程，應該使用notify還是notifyAll?notify會隨機通知等待隊列中的一個線程，而notifyAll會通知等待隊列中所有線程，可知notify是有風險的 ，可能導致某些線程永遠不會被通知到
4、當前線程必須擁有此對象監(jiān)視器，然后才可以放棄對此監(jiān)視器的所有權(quán)并等待 ，直到其他線程通過調(diào)用notify方法或notifyAll方法通知在此對象的監(jiān)視器上等待的線程醒來,然后該線程將等到重新獲得對監(jiān)視器的所有權(quán)后才能繼續(xù)執(zhí)行。否則會報IllegalMonitorStateException 錯誤

不過Object的waitnotifynotifyAll原理是基于內(nèi)核中的對象監(jiān)視器Monitor完成的,有可能導致大量的上下文切換。為了更好的性能，往往使用基于AQS的顯示鎖ReetrantLock中的成員變量ConditionObject代替。AQS中存在一個同步隊列，當一個線程沒有獲取到鎖時就會進入到同步隊列中進行阻塞，如果被喚醒后獲取到銷，則移出同步隊列。另外AQS中還存在一個條件隊列，通過addWaiter方法，可以將wait()方法調(diào)用的線程放入到條件隊列中，線程進入等待狀態(tài)，當調(diào)用signal或者signalAll方法時，線程就會被喚醒，之后進入到同步隊列中。其中條件隊列是通過鏈表實現(xiàn)的，所以可以支持多個等待隊列。也就是說使用基于AQS接口的awaitsignalsignalAll原理是基于JAVA代碼層實現(xiàn)的，性能有更大的優(yōu)勢

所以本題的另外一種寫法是

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
class FooBar {
private int n;
private Boolean printFooStatus;
private ReentrantLock reentrantLock;
private Condition condition;
public FooBar(int n) {
    this.n = n;
    printFooStatus = true;
    //不管使用公平鎖還是非公平鎖，在本題中都沒有區(qū)別
    reentrantLock= new ReentrantLock(false);
    condition = reentrantLock.newCondition();
}
public void foo(Runnable printFoo) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        reentrantLock.lock();
        try {
            while (!printFooStatus){
                condition.await();
            }
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
        } catch (Exception e) {
           e.printStackTrace();
        } finally {
            printFooStatus = false;
            //同理：必須放在鎖內(nèi)
             condition.signalAll();
            reentrantLock.unlock();

        }
    }
}
public void bar(Runnable printBar) throws InterruptedException {
    for (int i = 0; i < n; i++) {
      reentrantLock.lock();
      try {
          while (printFooStatus){
              condition.await();
          }
          // printBar.run() outputs "bar". Do not change or remove this line.
          printBar.run();
      } catch (Exception e) {
         e.printStackTrace();
      } finally {
          printFooStatus = true; 
          //同理：必須放在鎖內(nèi)
           condition.signalAll();
          reentrantLock.unlock();

      }
    }
}

}
三、Print Zero Even Odd
Suppose you are given the following code:

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // constructor
  public void zero(printNumber) { ... }  // only output 0"s
  public void even(printNumber) { ... }  // only output even numbers
  public void odd(printNumber) { ... }   // only output odd numbers
}

The same instance of ZeroEvenOdd will be passed to three different threads:

Thread A will call zero() which should only output 0’s.
Thread B will call even() which should only ouput even numbers.
Thread C will call odd() which should only output odd numbers.
Each of the thread is given a printNumbermethod to output an integer. Modify the given program to output the series 010203040506… where the length of the series must be 2n.
Example 1:
Input: n = 2
Output: “0102”
Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). “0102” is the correct output.

Example 2:
Input: n = 5
Output: “0102030405”

提示：使用信號量

四、Building H2O
There are two kinds of threads, oxygen and hydrogen. Your goal is to group these threads to form water molecules. There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given a releaseHydrogen and releaseOxygen method respectfully, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must be able to immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

In other words:

If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.
If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.
We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that bond and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.
Example 1:
Input: “HOH”
Output: “HHO”
Explanation: “HOH” and “OHH” are also valid answers.

class H2O {

private Object lock = new Object();
private int counter =0;
public H2O() {

}
public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {

 synchronized (lock) {
        while(counter==2){
            lock.wait();
        }
        releaseHydrogen.run();
        counter++;
        lock.notifyAll();
  }
}

public void oxygen(Runnable releaseOxygen) throws InterruptedException {
    synchronized (lock) {
        while(counter!=2){
            lock.wait();
        }
        releaseOxygen.run();
        counter=0;
        lock.notifyAll();
  }

}
}

文章來源：www.liangsonghua.me

作者介紹：京東資深工程師-梁松華，在穩(wěn)定性保障、敏捷開發(fā)、JAVA高級、微服務架構(gòu)方面有深入的理解