欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线程创建,并发,信号量,可重入锁 加例题(Leetcode1116)详解

程序员文章站 2022-06-07 13:22:29
...

例题:Leetcode1116. Print Zero Even Odd

无锁并发

class ZeroEvenOdd {
    private int n;
    // volatile变量用来控制各个方法的输出顺序
    private volatile int state;
    public ZeroEvenOdd(int n) {
        this.state = 0;
        this.n = n;
    }

    /**
     * state作用:当state = 0,表示轮到zero()方法使用cpu;
     *           当state = 1,表示轮到odd()方法使用cpu;
     *           当state = 2,表示轮到odd()方法使用cpu;
     * 如果某方法还没有轮到它,它会一直通过Thread.yield()让出CPU资源。
     * Thread.yield()的作用是线程让出CPU资源,重新进入就绪队列去和
     * 其他线程竞争CPU,Thread.yield()之后有可能又是该线程得到CPU,
     * 也有可能不是它。
    */
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i++){
            while (state != 0){
                Thread.yield();
            }
            printNumber.accept(0);
            if(i % 2 == 1){
                state = 1;
            } else {
                state = 2;
            }
        }
    }

    // 输出偶数
    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i = 2; i <= n; i += 2){
            while (state != 2){
                Thread.yield();
            }
            printNumber.accept(i);
            state = 0;
        }
    }

    // 输出奇数
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i += 2){
            while (state != 1){
                Thread.yield();
            }
            printNumber.accept(i);
            state = 0;
        }
    }
}

信号量

首先,我们应该知道,信号量Semaphore的release()操作可以在acquire()操作的前面,这在Semaphore源码中有提到:“There is no requirement that a thread that releases a permit must have acquired that permit by calling”

    /**
     * Releases a permit, returning it to the semaphore.
     *
     * <p>Releases a permit, increasing the number of available permits by
     * one.  If any threads are trying to acquire a permit, then one is
     * selected and given the permit that was just released.  That thread
     * is (re)enabled for thread scheduling purposes.
     *
     * <p>There is no requirement that a thread that releases a permit must
     * have acquired that permit by calling {@link #acquire}.
     * Correct usage of a semaphore is established by programming convention
     * in the application.
     */
    public void release() {
        sync.releaseShared(1);
    }
class ZeroEvenOdd {
    private int n;

    Semaphore evenSem = new Semaphore(0);
    Semaphore oddSem = new Semaphore(0);
    Semaphore zeroSem = new Semaphore(1);
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    /**
     * zero函数acquire zeroSem之后才能进行 输出0 和 release evenSem、release oddSem,
     * 且release zeroSem的操作应该交给其它两个函数来进行,也就是输出0后得先输出奇数或偶数之后,
     * 才能再输出0。同样的,输出奇数或偶数后,也得先输出0才能继续输出奇数或偶数。
     */
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i++){
            zeroSem.acquire();
            printNumber.accept(0);
            if(i % 2 == 1){
                oddSem.release();
            } else {
                evenSem.release();
            }
        }
    }

    // 输出偶数
    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i = 2; i <= n; i += 2){
            evenSem.acquire();
            printNumber.accept(i);
            // evenSem.release(); 不能release(),只能由zero()函数来release
            zeroSem.release();
        }
    }

    // 输出奇数
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i += 2){
            oddSem.acquire();
            printNumber.accept(i);
            zeroSem.release();
        }
    }
}

可重入锁(ReentrantLock)和条件变量(Condition)

首先,可重入锁的实例对象 lock 通过lock.newCondition()创建一个 lock 的条件变量 condition 。

使用 condition.await() 可以使线程在该锁的condition条件上等待。使用 condition.signal() 可以唤醒一个正在该条件上等待的线程,使用await()和signal()都应该在lock() 和 unlock() 之间 (signal()在很多情况下都是如此)。

condition.await()会释放锁若没获得锁,则会抛出 IllegalMonitorStateException 异常,可以看Condition.java的源码。然后await()之后,线程会等待被唤醒,被唤醒之后回去重新获得锁,因此执行完工作后需要再释放锁。

condition.signal()会唤醒在该条件上等待的一个线程,规定也需包裹在lock()和unlock()之间。可以查看ReentrantLock的源码,发现ReentrantLock创建condition返回的是一个由final修饰的ConditionObject类的实例对象。通过查看源码,我们发现ConditionObject类的signal()方法如下:

/**
 * Moves the longest-waiting thread, if one exists, from the
 * wait queue for this condition to the wait queue for the
 * owning lock.
 *
 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
 *         returns {@code false}
 */
public final void signal() {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    Node first = firstWaiter;
    if (first != null)
        doSignal(first);
}

如果不持有锁,它也会抛出IllegalMonitorStateException异常。而且,调用signal()后需释放锁,以便唤醒的线程能去获取锁。

例题三个条件变量的解法

class ZeroEvenOdd {
    private int n;

    private volatile int state;
    private ReentrantLock rLock = new ReentrantLock();
    private Condition zeroCond;
    private Condition oddCond;
    private Condition evenCond;
    public ZeroEvenOdd(int n) {
        this.n = n;
        this.state = 0;
        this.zeroCond = rLock.newCondition();
        this.oddCond = rLock.newCondition();
        this.evenCond = rLock.newCondition();
    }

    /**
     * zero函数acquire zeroSem之后才能进行 输出0 和 release evenSem、release oddSem,
     * 且release zeroSem的操作应该交给其它两个函数来进行,也就是输出0后得先输出奇数或偶数之后,
     * 才能再输出0。同样的,输出奇数或偶数后,也得先输出0才能继续输出奇数或偶数。
     */
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i++){
            rLock.lock();
            try {
                // await()需要包裹在循环里,因为线程可能不经过signal就被
                // 唤醒,且唤醒后可能不符合条件得继续await()
                while (state != 0){
                    zeroCond.await();
                }
                printNumber.accept(0);
                if (i % 2 == 1){
                    state = 1;
                    oddCond.signal();
                } else {
                    state = 2;
                    evenCond.signal();
                }
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }

    // 输出偶数
    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i = 2; i <= n; i += 2){
            rLock.lock();
            try {
                while (state != 2){
                    evenCond.await();
                }
                printNumber.accept(i);
                state = 0;
                zeroCond.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }

    // 输出奇数
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i += 2){
            rLock.lock();
            try {
                while (state != 1){
                    oddCond.await();
                }
                printNumber.accept(i);
                state = 0;
                zeroCond.signal();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }
}

例题一个条件变量的解法(使用signalAll())

class ZeroEvenOdd {
    private int n;

    private volatile int state;
    private ReentrantLock rLock = new ReentrantLock();
    private Condition cond;
    public ZeroEvenOdd(int n) {
        this.n = n;
        this.state = 0;
        this.cond = rLock.newCondition();
    }

    /**
     * zero函数acquire zeroSem之后才能进行 输出0 和 release evenSem、release oddSem,
     * 且release zeroSem的操作应该交给其它两个函数来进行,也就是输出0后得先输出奇数或偶数之后,
     * 才能再输出0。同样的,输出奇数或偶数后,也得先输出0才能继续输出奇数或偶数。
     */
    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i++){
            rLock.lock();
            try {
                // await()需要包裹在循环里,因为线程可能不经过signal就被
                // 唤醒,且唤醒后可能不符合条件得继续await()
                while (state != 0){
                    cond.await();
                }
                printNumber.accept(0);
                if (i % 2 == 1){
                    state = 1;
                } else {
                    state = 2;
                }
                // 只使用一个条件变量必须signalAll()
                // 三个线程都在该条件上等待
                // 不确定唤醒的是那个线程
                cond.signalAll();
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }

    // 输出偶数
    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i = 2; i <= n; i += 2){
            rLock.lock();
            try {
                while (state != 2){
                    cond.await();
                }
                printNumber.accept(i);
                state = 0;
                cond.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }

    // 输出奇数
    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i = 1; i <= n; i += 2){
            rLock.lock();
            try {
                while (state != 1){
                    cond.await();
                }
                printNumber.accept(i);
                state = 0;
                cond.signalAll();
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                rLock.unlock();
            }
        }
    }
}

线程创建

public static void main(String[] args) {
    PrintZeroEvenOdd4 p = new PrintZeroEvenOdd4();
    ZeroEvenOdd z = p.new ZeroEvenOdd(4);

    new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                z.zero(new IntConsumer() {
                    @Override
                    public void accept(int value) {
                        System.out.println(value);
                    }
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }, "ThreadA").start();
    new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                z.even(new IntConsumer() {
                    @Override
                    public void accept(int value) {
                        System.out.println(value);
                    }
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }, "ThreadB").start();
    new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                z.odd(new IntConsumer() {
                    @Override
                    public void accept(int value) {
                        System.out.println(value);
                    }
                });
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }, "ThreadC").start();
}