Cultoy

Leetcode1115. 交替打印 FooBar

借助这题复习一下 Java 并发类和工具。

题目描述

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

请设计修改程序，以确保 “foobar” 被输出 n 次。

我们提供一个类：

class FooBar {
    private int n;

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

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            
        	// printFoo.run() outputs "foo". Do not change or remove this line.
        	printFoo.run();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            
            // printBar.run() outputs "bar". Do not change or remove this line.
        	printBar.run();
        }
    }
}

示例 1:

输入: n = 1
输出: “foobar”
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，”foobar” 将被输出一次。
示例 2:

输入: n = 2
输出: “foobarfoobar”
解释: “foobar” 将被输出两次。

思路

这题考的是线程同步，那么显而易见，信号量、互斥锁、共享内存这些方案都是可行的。

题解

信号量 Semaphore

Semaphore 翻译成字面意思为信号量，Semaphore 可以控同时访问的线程个数，通过 acquire() 获取一个许可，如果没有就等待，而 release() 释放一个许可。

Semaphore 类位于 java.util.concurrent 包下，它提供了 2 个构造器：

public Semaphore(int permits) {          // 参数 permits 表示许可数目，即同时可以允许多少线程进行访问
    sync = new NonfairSync(permits);
}
public Semaphore(int permits, boolean fair) {    // 这个多了一个参数 fair 表示是否是公平的，即等待时间越久的越先获取许可
    sync = (fair)? new FairSync(permits) : new NonfairSync(permits);
}

下面说一下 Semaphore 类中比较重要的几个方法，首先是 acquire()、release()方法：

public void acquire() throws InterruptedException {  }     // 获取一个许可
public void acquire(int permits) throws InterruptedException { }    // 获取 permits 个许可
public void release() { }          // 释放一个许可
public void release(int permits) { }    // 释放 permits 个许可

acquire()用来获取一个许可，若无许可能够获得，则会一直等待，直到获得许可。

release()用来释放许可。注意，在释放许可之前，必须先获获得许可。

这 4 个方法都会被阻塞，如果想立即得到执行结果，可以使用下面几个方法：

public boolean tryAcquire() { };    
// 尝试获取一个许可，若获取成功，则立即返回 true，若获取失败，则立即返回 false
public boolean tryAcquire(long timeout, TimeUnit unit) throws InterruptedException { };  
// 尝试获取一个许可，若在指定的时间内获取成功，则立即返回 true，否则则立即返回 false
public boolean tryAcquire(int permits) { }; 
// 尝试获取 permits 个许可，若获取成功，则立即返回 true，若获取失败，则立即返回 false
public boolean tryAcquire(int permits, long timeout, TimeUnit unit) throws InterruptedException { }; // 尝试获取 permits 个许可，若在指定的时间内获取成功，则立即返回 true，否则则立即返回 false

另外还可以通过 availablePermits()方法得到可用的许可数目。

此题可设置两个信号量分别标示 FooBar 的可用状态。

代码

class FooBar {
    private int n;

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

    Semaphore foo = new Semaphore(1);
    Semaphore bar = new Semaphore(0);

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            foo.acquire();
            printFoo.run();
            bar.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            bar.acquire();
            printBar.run();
            foo.release();
        }
    }
}

公平锁

锁提供对共享资源的独占访问：一次只能有一个线程可以获取锁，并且对共享资源的所有访问都要求首先获取锁。但是，一些锁可能允许并发访问共享资源，如 ReadWriteLock 的读写锁。在 Lock 接口出现之前，Java 程序是靠 synchronized 关键字实现锁功能的。JDK1.5 之后并发包中新增了 Lock 接口以及相关实现类来实现锁功能。

Lock 接口的实现类： ReentrantLock ， ReentrantReadWriteLock.ReadLock ， ReentrantReadWriteLock.WriteLock

Lock 接口提供的 synchronized 关键字不具备的主要特性：

特性	描述
尝试非阻塞地获取锁	当前线程尝试获取锁，如果这一时刻锁没有被其他线程获取到，则成功获取并持有锁
能被中断地获取锁	获取到锁的线程能够响应中断，当获取到锁的线程被中断时，中断异常将会被抛出，同时锁会被释放
超时获取锁	在指定的截止时间之前获取锁，超过截止时间后仍旧无法获取则返回

Lock 接口基本的方法：

方法名称	描述
void lock()	获得锁。如果锁不可用，则当前线程将被禁用以进行线程调度，并处于休眠状态，直到获取锁。
void lockInterruptibly()	获取锁，如果可用并立即返回。如果锁不可用，那么当前线程将被禁用以进行线程调度，并且处于休眠状态，和 lock()方法不同的是在锁的获取中可以中断当前线程（相应中断）。
Condition newCondition()	获取等待通知组件，该组件和当前的锁绑定，当前线程只有获得了锁，才能调用该组件的 wait()方法，而调用后，当前线程将释放锁。
boolean tryLock()	只有在调用时才可以获得锁。如果可用，则获取锁定，并立即返回值为 true；如果锁不可用，则此方法将立即返回值为 false 。
boolean tryLock(long time, TimeUnit unit)	超时获取锁，当前线程在一下三种情况下会返回： 1. 当前线程在超时时间内获得了锁；2. 当前线程在超时时间内被中断；3. 超时时间结束，返回 false.
void unlock()	释放锁。

class FooBar {
    private int n;

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

    Lock lock = new ReentrantLock(true);
    volatile boolean permitFoo = true;

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; ) {
            lock.lock();
            try {
            	if(permitFoo) {
            	    printFoo.run();
                    i++;
                    permitFoo = false;
            	}
            }finally {
            	lock.unlock();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; ) {
            lock.lock();
            try {
            	if(!permitFoo) {
            	    printBar.run();
            	    i++;
            	    permitFoo = true;
            	}
            }finally {
            	lock.unlock();
            }
        }
    }
}

无锁

以上的公平锁方案完全可以改造成无锁方案：

class FooBar {
    private int n;

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

    volatile boolean permitFoo = true;

    public void foo(Runnable printFoo) throws InterruptedException {     
        for (int i = 0; i < n; ) {
            if(permitFoo) {
        	printFoo.run();
            	i++;
            	permitFoo = false;
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {       
        for (int i = 0; i < n; ) {
            if(!permitFoo) {
        	printBar.run();
        	i++;
        	permitFoo = true;
            }
        }
    }
}

CyclicBarrier 类

循环场景中常用 CyclicBarrier

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

    CyclicBarrier cb = new CyclicBarrier(2);
    volatile boolean fin = true;

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while(!fin);
            printFoo.run();
            fin = false;
            try {
		cb.await();
	    } catch (BrokenBarrierException e) {
	    }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            try {
		cb.await();
	    } catch (BrokenBarrierException e) {
	    }
            printBar.run();
            fin = true;
        }
    }
}