動機

解解LC的題目

lockfree

只要一讀一寫就ok了，之後就是搭配while(cond) { Thread.yield(); }

但事情沒這麼簡單

  1. 修改變數時要加上條件(前提)，不要無條件的write，以保證一讀一寫
  2. write不要與其他東西混用
  • 像1116的printNumber.accept(i++);，會錯
  1. 在多thread協作的場景下，lockfree很沒效率，見1117

1114

class Foo {
    private volatile int n = 0;
    public Foo() {
        
    }

    public void first(Runnable printFirst) throws InterruptedException {
        while (n < 1) {
            printFirst.run();
            n = 1;
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        while (n < 2) {
            if (n == 1) {
                printSecond.run();
                n++;
            }
            Thread.yield();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
        while (n < 3) {
            if (n == 2) {
                printThird.run();
                n++;
            }
            Thread.yield();
        }
    }
}

1115

class FooBar {
    private int n;
    private volatile boolean pFoo = true;

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

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

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

1116

class ZeroEvenOdd {
    private final int n;
    private volatile int i = 1;
    private volatile boolean need_zero = false;
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    public void genOneZero() {
        need_zero = true;
        while (need_zero) { Thread.yield(); }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        while (i <= n) {
            if (need_zero) {
                printNumber.accept(0);
                need_zero = false;
            }
            Thread.yield();
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        while (i <= n) {
            if (i % 2 == 0 && !need_zero) {
                genOneZero();
                // printNumber.accept(i++); NO!!!!
                printNumber.accept(i);
                i++;
            } else {
                Thread.yield();
            }
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        while (i <= n) {
            if (i % 2 != 0 && !need_zero) {
                genOneZero();
                printNumber.accept(i);
                i++;
            } else {
                Thread.yield();
            }
        }
    }
}

1195

class FizzBuzz {
    private final int end;
    private volatile int n = 1;
    public FizzBuzz(int n) {
        this.end = n;
    }
    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        while (n <= end) {
            if (n % 3 == 0 && n % 5 != 0) {
                printFizz.run();
                n++;
            } else {
                Thread.yield();
            }
        }

    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        while (n <= end) {
            if (n % 5 == 0 && n % 3 != 0) {
                printBuzz.run();
                n++;
            } else {
                Thread.yield();
            }
        }

    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (n <= end) {
            if (n % 3 == 0 && n % 5 == 0) {
                printFizzBuzz.run();
                n++;
            } else {
                Thread.yield();
            }
        }

    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        while (n <= end) {
            if (n % 3 != 0 && n % 5 != 0) {
                printNumber.accept(n);
                n++;
            } else {
                Thread.yield();
            }
        }

    }
}

1117

semaphore

兩個H後才有一個O，對應到兩個semaphore

先放H再放O

class H2O {
    private Semaphore h = new Semaphore(2), o = new Semaphore(0);

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        h.acquire();
        releaseHydrogen.run();
        o.release();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        o.acquire(2);
        releaseOxygen.run();
        h.release(2);
    }
}

synchronized (blockfree)

synchronized中不會reorder且具atomic

應該要上volatile，但我把volatile拿掉也是AC了!!

class H2O {
    private int h = 2, o = 0;
    private Integer a=1,b=2;

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        synchronized(a) {
            while (h <= 0) Thread.yield();
            h--;
            releaseHydrogen.run();        
            o++;
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        synchronized(b) {
            while (o < 2) Thread.yield();
            o-=2;
            releaseOxygen.run();
            h+=2;
        }
    }
}

lockfree (TLE)

lockfree就是不符合執行條件就丟出去，這樣有可能浪費很多次做事的機會

lock不是不好，怕的是有人長期持有，又有一堆人去搶

class H2O {
    private volatile int h = 0;

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        while (h <= 0) Thread.yield();
        releaseHydrogen.run();
        if (h > 0) { h--; }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        while (h > 0) Thread.yield();
        releaseOxygen.run();
        if (h <= 0) { h+=2; }
    }
}

1226. The Dining Philosophers

其實重點就是相鄰的哲學家要先去搶同一個叉子

class DiningPhilosophers {
    private Integer[] lks;
    public DiningPhilosophers() {
        lks = new Integer[] {0, 1, 2, 3, 4};
    }

    // call the run() method of any runnable to execute its code
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        int left = philosopher;
        int right = (philosopher+5-1) % 5;
        if (philosopher % 2 == 1) {
            left = left ^ right; right = left ^ right; left = left ^ right;
        }
        synchronized(lks[left]) {
            synchronized(lks[right]) {
                pickLeftFork.run();
                pickRightFork.run();
                eat.run();
                putRightFork.run();
                putLeftFork.run();
            }
        }
    }
}