变强日记1

主要内容

java中的等待通知机制
动态规划解leetcode10:Regular Expression Matching

java中的等待通知机制

什么是等待通知机制

一个线程因为执行目标动作锁需要的保护条件未满足而被暂停的过程就被成为等待。
一个线程更新了系统的状态，使得其它线程所需要的保护条件成立，唤醒那些被暂停的线程的过程被称为通知。

wait/notfy方案

java中提供了Object.wait()/Object.wait(long timeoout),Object.notify()/Object.notifyAll()可以用来实现等待和通知

synchronized(someObject){
    while(保护条件不成立){
        someObject.wait();
    }
    //执行目标动作
    doAction();
}

synchronized(someObject){
    //更新保护条件涉及的共享变量
    updateSharedState();
    //通知等待的线程
    someObject.notify();
}
```、
该方案存在的问题：
1. 过早唤醒
因为同一个对象上可以有多个wait的线程。假设一组等待/通知线程同步在对象someObject上，初始状态下均不成立，当线程N1更新了共享变量state1使得N1执行notifyAll方法唤醒所有线程，当其它线程的保护条件可能并不成立，这使得线程唤醒后还得睡眠。
2. 信号丢失
如果等待线程在wait之前没有判断保护条件是否成立，那么有这样一种情况，就是通知线程在等待线程进入等待之前就更新了保护条件，使得保护条件成立，等待线程在睡眠后就再也不会收到唤醒通知了。
比如下面这个例子：

T1:
synchronized(sharedMonitor){
updateSomeCondition();//更新保护条件
sharedMonitor.notify();

}
T2:
while(someCondition){
//Point1:
synchronized(sharedMonitor){
sharedMonitor.wait();
}
}

假如T2先执行，当它判断保护条件someCondition成立后，进入Point1时（注意synchronized代码块的位置），线程调度器可能切换到了T1，T1发出唤醒信号。然后线程调度器重新回到point1执行，T2线程进入等待。T2也就错过了唤醒信号，再也不会被唤醒了。所以一定要注意`synchronized`关键字的位置。
3. 欺骗性唤醒。等待线程也可能存在没有其它任何线程执行notify和notifyAll线程的情况下被唤醒。
4. 上下文切换问题。wait/notify的时候可能导致较多的上下文切换

### 条件变量方案
一种比wait/notfy方案更好的实现方案是使用jdk1.5之后引入的条件变量java.util.concurent.locks.Condition接口。

`Lock.newCondition()`的返回值就是一个Condition实例。因此调用任何一个显示锁的实例的newCondition方法都可以创建一个相应的Condition接口。Condition.await()/signal()也要求其执行线程持有创建该Condition实例的**显示锁**。每个Condition实例内部都维护乐一个用于存储等待线程的队列。

假设cond1和cond2是两个不同的Condition实例，一个线程执行Cond1.await()会导致其被暂停，并被存入cond1的等待队列。cond1.signal会使cond1的等待队列中的任意线程被唤醒。调用cond1.signalAll()会使cond1的等待队列中的所有线程被唤醒。而cond2等待队列中的任何一个等待线程都不会受此影响。这样就避免了过早唤醒的问题。
```java
public class Test {
    //显示锁
    private final Lock lock=new ReentrantLock(); 
    //条件变量
    private final Condition condition=lock.newCondition();
    
    public void methodA() throws InterruptedException {
        lock.lock();
        try {
            while (保存条件不成立){
                condition.await();
            }
            //执行目标动作
            doAction();
            
        }finally {
            lock.unlock();
        }
    }
    public void methodB(){
        lock.lock();
        try {
            //更新保护条件
            updateState();
            //唤醒该条件变量上的等待线程
            condition.signal();
        }finally {
            lock.unlock();
        }
    }
}

该方案很好的解决了过早唤醒问题。并且boolean awaitUntil(Date deadline)可以根据返回值区分是等待超时唤醒的还是被其它线程唤醒的。

CountDownLatch方案

CountDownLatch叫做倒计时协调器。
ConutDownLatch内部维护了一个用于表示未完成的先决操作数量的计数器。每调用一次countDown（）相应实例的计数器值会减少1（先决条件完成了一个），await()方法相当于一个受保护的方法，其保护条件为计数器的值为0(先决条件全部完成)。
因此，当计数器的值不为0的时候，CountDownLatch.await()的执行线程会被暂停。这些线程就被称为CountDownLatch上的等待线程。CountDownlatch.countDown()相对于一个通知方法，它会在计数器达到0的时候唤醒相应实例上的等待线程。
因为CountDownLatch内部封装了对“全部先决条件的等待与通知的逻辑”，所以客户端代码在调用await,countDown方法都无需加锁。

//使用实例，演示了如何用CountDownLatch实现10个线程同时启动
public class CountDownLatchTest {

    public static void main(String[] args) {
        CountDownLatchTest countDownLatchTest=new CountDownLatchTest();
        countDownLatchTest.runThread();
    }
    CountDownLatch countDownLatch=new CountDownLatch(10);

    /**
     * 创建一个线程
     * @return
     */
    private Thread createThread(int i){
        Thread thread=new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    countDownLatch.await();
                    System.out.println("thread"+Thread.currentThread().getName()+"准备完毕"+System.currentTimeMillis());
                }catch (InterruptedException e){
                    e.printStackTrace();
                }

            }
        });
        thread.setName("thread-"+i);
        return  thread;
    }

    public void runThread(){
        ExecutorService executorService= Executors.newFixedThreadPool(10);

        try {
            for(int i=0;i<10;i++){
                Thread.sleep(100);
                executorService.submit(createThread(i));
                //待等待的线程数减去一
                countDownLatch.countDown();
            }
        }catch (InterruptedException e){
            e.printStackTrace();
        }

    }
}

CountDownLatch是无法重用的。

CyclicBarrier方案

jdk1.5之后引入了java.util.concurrent.CyclicBarrier类，该类也可以实现等待通知。
CyclicBarrier方案让多个线程相互等待，直到达到一个屏障点，并且CyclicBarrier是可重用的。
比如让10个线程相互等待，以实现10个线程同时开始执行：

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CyclicBarrierTest {

    public static void main(String[] args) {
        CyclicBarrierTest cyclicBarrierTest=new CyclicBarrierTest();
        cyclicBarrierTest.runThread();
    }
    CyclicBarrier cyclicBarrier=new CyclicBarrier(10);

    /**
     * 创建一个线程
     * @return
     */
    private Thread createThread(int i){
        Thread thread=new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                /*除了最后一个线程，其余的线程都会在此等待，
                直到最后一个线程执行到此，唤醒之前所有等待的线程*/
                    cyclicBarrier.await(); 
                    System.out.println("thread"+Thread.currentThread().getName()+"准备完毕"+System.currentTimeMillis());
                }catch (InterruptedException e){
                    e.printStackTrace();
                }catch (BrokenBarrierException e){
                    e.printStackTrace();
                }

            }
        });
        thread.setName("thread-"+i);
        return  thread;
    }

    public void runThread(){
        ExecutorService executorService= Executors.newFixedThreadPool(10);

        try {
            for(int i=0;i<10;i++){
                Thread.sleep(100);
                executorService.submit(createThread(i));
            }
        }catch (InterruptedException e){
            e.printStackTrace();
        }

    }
}

动态规划解leetcode10:Regular Expression Matching

题目：
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

思路：
使用一个二维数组来表示匹配结果b[i+1][j+1]表示s[0..i]匹配p[0..j]
两个边界条件：

b[0][0],及两个空串进行匹配，为true
对于空串的匹配b[i+1][0]的数值必须为False

解法：

class Solution {
    public boolean isMatch(String s, String p) {
        int lenA=s.length();
        int lenP=p.length();
        char[] charsS=s.toCharArray();
        char[] charsP=p.toCharArray();

        boolean[][] b=new boolean[lenA+1][lenP+1];
        b[0][0]=true;
        for(int i=0;i<lenA;i++){
            b[i+1][0]=false;
        }
        for(int j=0;j<lenP;j++){
            b[0][j+1]=j>0&&charsP[j]=='*'&&b[0][j-1];
        }
        for(int i=0;i<lenA;i++){
            for(int j=0;j<lenP;j++){
                if(charsP[j]!='*'){
                    b[i+1][j+1]=b[i][j]&&('.'==charsP[j]||charsS[i]==charsP[j]);
                }else{
                    b[i+1][j+1]=b[i + 1][j - 1] && j > 0 || b[i + 1][j] ||
                    b[i][j + 1] && j > 0 && ('.' == charsP[j - 1] || charsS[i] == charsP[j - 1]);
                }
            }
        }
        return b[lenA][lenP];
    }
}