1115. alternate printing foobar

Title Description

We provide a class ：

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");
    }
  }
}

Two different threads will share one FooBar example . One of the threads will call foo() Method , Another thread will call bar() Method .

Please design a modification program , In order to ensure that “foobar” Output by n Time .

1. Semaphore

Set two semaphores , Obtain the corresponding semaphore for each output , Provide a semaphore for the other party after output .

class FooBar {
    
    private int n;
    private Semaphore barPermit, fooPermit;

    public FooBar(int n) {
    
        this.n = n;
        barPermit = new Semaphore(0);
        fooPermit = new Semaphore(1);
    }

    public void foo(Runnable printFoo) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            fooPermit.acquire();
            printFoo.run();
            barPermit.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            barPermit.acquire();
            printBar.run();
            fooPermit.release();
        }
    }
}

2. Atomic variable coordination LockSupport

rely on AtomicBoolean The atomic method of get and compareAndSet Synchronize the two processes .

class FooBar {
    

    private final int n;

    private final AtomicBoolean state;

    private final Map<String, Thread> map;

    public FooBar(int n) {
    
        this.n = n;
        state = new AtomicBoolean(false);
        map = new HashMap<>();
    }

    public void foo(Runnable printFoo) throws InterruptedException {
    
        map.put("foo", Thread.currentThread());
        for (int i = 0; i < n; i++) {
    
            while(state.get()) {
    
                LockSupport.park();
            }
            printFoo.run();
            while(!state.compareAndSet(false, true)) {
    }
            LockSupport.unpark(map.get("bar"));
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    
        map.put("bar", Thread.currentThread());
        for (int i = 0; i < n; i++) {
    
            while(!state.get()) {
    
                LockSupport.park();
            }
            printBar.run();
            while(!state.compareAndSet(true, false)) {
    }
            LockSupport.unpark(map.get("foo"));
        }
    }
}

3. Blocking queues

The method is similar to that of semaphore , Get a value from the corresponding blocking queue before printing each time , After printing, provide a value for the blocking queue of another process .

class FooBar {
    

    private int n;

    private BlockingQueue<Integer> outputFoo, outputBar;

    public FooBar(int n) {
    
        this.n = n;
        outputBar = new LinkedBlockingQueue<>(1);
        outputFoo = new LinkedBlockingQueue<>(1);
    }

    public void foo(Runnable printFoo) throws InterruptedException {
    
        try {
    
            outputFoo.put(1);
        } catch (InterruptedException e) {
    
            e.printStackTrace();
        }
        for (int i = 0; i < n; i++) {
    
            outputFoo.take();
            printFoo.run();
            outputBar.put(1);
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            outputBar.take();
            printBar.run();
            outputFoo.put(1);
        }
    }
}

4. spinlocks

utilize volatile Type to synchronize the two processes .

class FooBar {
    

    private int n;

    private volatile boolean done = false;

    private final CyclicBarrier barrier = new CyclicBarrier(2);

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

    public void foo(Runnable printFoo) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            while(done) {
    }
            printFoo.run();
            done = true;
            try {
    
                barrier.await();
            } catch (BrokenBarrierException e) {
    
                e.printStackTrace();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            try {
    
                barrier.await();
            } catch (BrokenBarrierException e) {
    
                e.printStackTrace();
            }
            printBar.run();
            done = false;
        }
    }
}

5. utilize Thread Of yield Method

utilize flag Synchronize the two processes , Print when satisfied , otherwise Thread.yield() Give up cpu.

class FooBar {
    

    private int n;

    private volatile boolean flag = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
    

        for (int i = 0; i < n; ) {
    
            if(!flag) {
    
                printFoo.run();
                i++;
                flag = true;
            } else {
    
                Thread.yield();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; ) {
    
            if(flag) {
    
                printBar.run();
                i++;
                flag = false;
            } else {
    
                Thread.yield();
            }
        }
    }
}

6. Condition variables,

utilize volatile Variables as flags 、 Explicit reentrant lock 、 Conditional variables coordinate two processes . When flag When not satisfied , The thread waits on the condition variable . Wake up the thread waiting on the condition variable after execution .

class FooBar {
    

    private int n;

    private final ReentrantLock lock = new ReentrantLock();

    private final Condition condition = lock.newCondition();

    private volatile boolean flag = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            lock.lock();
            try {
    
                while(flag) {
    
                    condition.await();
                }
                printFoo.run();
                flag = true;
                condition.signal();
            } finally {
    
                lock.unlock();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            lock.lock();
            try {
    
                while(!flag) {
    
                    condition.await();
                }
                printBar.run();
                flag = false;
                condition.signal();
            } finally {
    
                lock.unlock();
            }
        }
    }
}

7. utilize synchronized Lock

Declare a lock object and as a token volatile Variable , Each round of inspection marks 、 Lock before printing , If the sign does not allow printing, wait on the lock . Wake up the thread waiting on the lock when one round of execution is completed .

class FooBar {
    

    private int n;

    private final Object lock = new Object();

    private volatile boolean flag = false;

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

    public void foo(Runnable printFoo) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            synchronized (lock) {
    
                while(flag) {
    
                    lock.wait();
                }
                printFoo.run();
                flag = true;
                lock.notify();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
    

        for (int i = 0; i < n; i++) {
    
            synchronized (lock) {
    
                while(!flag) {
    
                    lock.wait();
                }
                printBar.run();
                flag = false;
                lock.notify();
            }
        }
    }
}