1115. 交替打印FooBar

发表于

算法分类：并发编程

url：https://leetcode-cn.com/problems/print-foobar-alternately/

​

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
1115. 交替打印FooBar
我们提供一个类：

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");
    }
  }
}
两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

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

 

示例 1:

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-foobar-alternately
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

​

Java解法

synchronized 解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class FooBar {
    private int n;
    private Object lock = new Object();
    private volatile boolean toBar = false; // 是否应该打印Bar

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

    public void foo(Runnable printFoo) throws InterruptedException {
        synchronized (lock) {
            for (int i = 0; i < n; i++) {
                toBar = true;
                printFoo.run(); // 线程的run调用相当于直接执行，不启动线程
                lock.notify();
                if (i < n-1) lock.wait();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        synchronized (lock) {
            if (!toBar) lock.wait(); // 第一次如果还没有打印foo，则等待，让出锁
            for (int i = 0; i < n; i++) {
                printBar.run();
                lock.notify();
                if (i < n-1) lock.wait();
            }
        }
    }
}

image-20200820171557421

ReentrantLock非公平锁

解法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class FooBar {
    private int n;
    private ReentrantLock lock = new ReentrantLock();
    private Condition condition = lock.newCondition();
    private volatile boolean toBar = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
        lock.lock();
        for (int i = 0; i < n; i++) {
            printFoo.run();
            toBar = true;
            condition.signal();
            if (i < n-1) condition.await();
        }
        lock.unlock();
    }

    public void bar(Runnable printBar) throws InterruptedException {
        lock.lock();
        if (!toBar) condition.await();
        for (int i = 0; i < n; i++) {
            printBar.run();
            condition.signal();
            if (i < n-1) condition.await();
        }
        lock.unlock();
    }
}

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class FooBar {
    private int n;
    private ReentrantLock lock = new ReentrantLock(); // 非公平锁
    private Condition condition = lock.newCondition();
    private volatile boolean toBar = false;
    
    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        lock.lock();
        try {
            for (int i = 0; i < n; i++) {
                while (toBar) condition.await();
                printFoo.run();
                toBar = true;
                condition.signal();
            }
        } finally {
            lock.unlock();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        lock.lock();
        try {
            for (int i = 0; i < n; i++) {
                while (!toBar) condition.await();
                printBar.run();
                toBar = false;
                condition.signal();
            }
        } finally {
            lock.unlock();
        }
    }
}

image-20200821115539149

ReentrantLock 公平锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class FooBar {
    private int n;
    private ReentrantLock lock = new ReentrantLock(true); // 公平锁
    private Condition condition = lock.newCondition();
    private volatile boolean toBar = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
        lock.lock();
        for (int i = 0; i < n; i++) {
            printFoo.run();
            toBar = true;
            condition.signal();
            if (i < n-1) condition.await();
        }
        lock.unlock();
    }

    public void bar(Runnable printBar) throws InterruptedException {
        lock.lock();
        if (!toBar) condition.await();
        for (int i = 0; i < n; i++) {
            printBar.run();
            condition.signal();
            if (i < n-1) condition.await();
        }
        lock.unlock();
    }
}

image-20200821133124750

无锁实现

一、分析题意：
1、（问题一）首先是两条线程异步调用，两条线程不能确定他们谁先谁有，也就是有序性
2、（问题二）在线程执行的时候需要保证foo每次循环都在bar前，这样的话肯定是需要线程不能往下执行。
3、 解决以上两个问题基本就解决了，所以联想到以下两个关键字解决，volatile 可见性且有序，yield()让线程暂停。
二、首先解释两个用到的关键字 volatile yield();
yield ：暂停当前正在执行的线程对象，yield()只是使当前线程重新回到可执行状态，所以执行yield()的线程有可能在进入到可执 行状态后马上又被执行。
volatile：保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。 （实现可见性）
禁止进行指令重排序。（实现有序性）
volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。
三、解题过程
循环执行两次，首先确认目前的flag的状态以确保一定是foo执行（为了解决问题一，关键词volatile），来判断是否往下执 行，如果不是那么让当前不往下执行（关键词yield()）
优化：可以在 yield() 时增限制，避免无限的循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class FooBar {
    private int n;
    private volatile boolean toBar = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (toBar) Thread.yield();
            printFoo.run();
            toBar = true;
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (!toBar) Thread.yield();
            printBar.run();
            toBar = false;
        }
    }
}

image-20200821134458619

BlockingDeque 实现

BlockingDeque 是java.util.concurrent包中提供的一个接口。该接口表示一个双端队列。该双端队列，线程可以安全的插入，和取出元素。线程插入或者移出队列中的元素时，可能会阻塞。

一个线程可以插入元素到队列的任一端。如果队列full,那么线程将会阻塞，直到其他线程从队列中取出一个元素为止。如果队列empty,那么从队列中取元素的线程将会阻塞，直到其他线程插入一个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;

class FooBar {
    private int n;
    private BlockingDeque queue = new LinkedBlockingDeque(1);

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

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

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            queue.take();
            queue.take();
            printBar.run();
            queue.take();
        }
    }
    public static void main(String[] args) throws InterruptedException {
        FooBar t = new FooBar(3);
        Thread foo = new Thread(() -> {
            try {
                t.foo(() -> System.out.print("foo"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        foo.setDaemon(false);
        foo.start();

        Thread bar = new Thread(() -> {
            try {
                t.bar(() -> System.out.print("bar"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        bar.setDaemon(false);
        bar.start();
    }
}

image-20200821183329608

Semaphore 实现

acquire实现，核心代码如下：

1
2
3
4
5
6
7
8
9
10
>final int nonfairTryAcquireShared(int acquires) {
>    for (;;) {
>        int available = getState();
>        int remaining = available - acquires;
>        if (remaining < 0 ||
>            compareAndSetState(available, remaining))
>            return remaining;
>    }
>}
>

acquires值默认为1，表示尝试获取1个许可，remaining代表剩余的许可数。

release实现，核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
>protected final boolean tryReleaseShared(int releases) {
>    for (;;) {
>        int current = getState();
>        int next = current + releases;
>        if (next < current) // overflow
>            throw new Error("Maximum permit count exceeded");
>        if (compareAndSetState(current, next))
>            return true;
>    }
>}
>

releases值默认为1，表示尝试释放1个许可，next 代表如果许可释放成功，可用许可的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    private Semaphore semaphoreFoo = new Semaphore(1);
    private Semaphore semaphoreBar = new Semaphore(0);

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

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

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            semaphoreBar.acquire();
            printBar.run();
            semaphoreFoo.release();
        }
    }
    public static void main(String[] args) throws InterruptedException {
        FooBar t = new FooBar(3);
        Thread foo = new Thread(() -> {
            try {
                t.foo(() -> System.out.print("foo"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        foo.setDaemon(false);
        foo.start();

        Thread bar = new Thread(() -> {
            try {
                t.bar(() -> System.out.print("bar"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        bar.setDaemon(false);
        bar.start();
    }
}

image-20200824093540822

CyclicBarrier 实现

默认的构造方法是CyclicBarrier(int parties)，其参数表示屏障拦截的线程数量，每个线程调用await方法告诉CyclicBarrier已经到达屏障位置，线程被阻塞。

  1. 每当线程执行await，内部变量count减1，如果count！= 0，说明有线程还未到屏障处，则在锁条件变量trip上等待。
  2. 当count == 0时，说明所有线程都已经到屏障处，执行条件变量的signalAll方法唤醒等待的线程。
    其中 nextGeneration方法可以实现屏障的循环使用：
  • 重新生成Generation对象
  • 恢复count值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

class FooBar {
    private int n;
    private CyclicBarrier cb = new CyclicBarrier(2);
    private volatile boolean toBar = false;

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

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

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (!toBar);
            printBar.run();
            toBar = false;
            try {
                cb.await();
            } catch (BrokenBarrierException e) {
                e.printStackTrace();
            }
        }
    }
    public static void main(String[] args) throws InterruptedException {
        FooBar t = new FooBar(3);
        Thread foo = new Thread(() -> {
            try {
                t.foo(() -> System.out.print("foo"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        foo.setDaemon(false);
        foo.start();

        Thread bar = new Thread(() -> {
            try {
                t.bar(() -> System.out.print("bar"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        bar.setDaemon(false);
        bar.start();
    }
}

image-20200824100232452

CountDownLatch + CyclicBarrier

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.CyclicBarrier;

class FooBar {
    private int n;
    private CountDownLatch a;
    private CyclicBarrier barrier;// 使用CyclicBarrier保证任务按组执行
    public FooBar(int n) {
        this.n = n;
        a = new CountDownLatch(1);
        barrier = new CyclicBarrier(2);// 保证每组内有两个任务
    }

    public void foo(Runnable printFoo) throws InterruptedException {

        try {
            for (int i = 0; i < n; i++) {
                printFoo.run();
                a.countDown();// printFoo方法完成调用countDown
                barrier.await();// 等待printBar方法执行完成
            }
        } catch(Exception e) {}
    }

    public void bar(Runnable printBar) throws InterruptedException {

        try {
            for (int i = 0; i < n; i++) {
                a.await();// 等待printFoo方法先执行
                printBar.run();
                a = new CountDownLatch(1); // 保证下一次依旧等待printFoo方法先执行
                barrier.await();// 等待printFoo方法执行完成
            }
        } catch(Exception e) {}
    }

    public static void main(String[] args) throws InterruptedException {
        FooBar t = new FooBar(3);
        Thread foo = new Thread(() -> {
            try {
                t.foo(() -> System.out.print("foo"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        foo.setDaemon(false);
        foo.start();

        Thread bar = new Thread(() -> {
            try {
                t.bar(() -> System.out.print("bar"));
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });
        bar.setDaemon(false);
        bar.start();
    }
}

image-20200824102103872

Python3解法

简单公平锁搞定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from threading import Lock

class FooBar:
    def __init__(self, n):
        self.n = n
        self.fooLock = Lock()
        self.barLock = Lock()
        self.fooLock.acquire()


    def foo(self, printFoo: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            self.barLock.acquire()
            printFoo()
            self.fooLock.release()


    def bar(self, printBar: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            self.fooLock.acquire()
            printBar()
            self.barLock.release()

image-20200821092211425