死锁和ThreadLocal

1 死锁/活锁

死锁： 一组互相竞争资源的线程因互相等待，导致“永久”阻塞的现象。

活锁： 活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试—失败—尝试—失败的过程。处于活锁的实体是在不断的改变状态，活锁有可能自行解开。

2 死锁发生的条件

1. 互斥，共享资源 X 和 Y 只能被一个线程占用；

2. 占有且等待，线程 T1 已经取得共享资源 X，在等待共享资源 Y 的时候，不释放共享资源 X；

3. 不可抢占，其他线程不能强行抢占线程 T1 占有的资源；

4. 循环等待，线程 T1 等待线程 T2 占有的资源，线程 T2 等待线程 T1 占有的资源，就是循环等待。

3 如何解决死锁的问题

按照前面说的四个死锁的发生条件，只需要破坏其中一个，就可以避免死锁的产生。其中，互斥这个条件没有办法破坏，因为用锁为的就是互斥，其他三个条件都有办法可以破坏。

对于“占用且等待”这个条件，可以一次性申请所有的资源，这样就不存在等待了。

对于“不可抢占”这个条件，占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源，这样不可抢占这个条件就破坏掉了。

对于“循环等待”这个条件，可以靠按序申请资源来预防。所谓按序申请，是指资源是有线性顺序 的，申请的时候可以先申请资源序号小的，再申请资源序号大的，这样线性化后自然就不存在循环了。

4 ThreadLocal

线程隔离机制。ThreadLocal实际上一种线程隔离机制，也是为了保证在多线程环境下对于共享变量的访问的安全性。

static ThreadLocal<Integer> local = new ThreadLocal<>() {
    protected Integer initialValue(){
        return 0; //初始化一个值
    }
};

public static void main(String[] args) {
    Thread[] thread = new Thread[5];
    for(int i = 0 ; i<5 ; i++){
        thread[i] = new Thread(() -> {
            int num = local.get(); //获得的值都是0
            local.set(num += 5); //设置到local中
            System.out.println(Thread.currentThread.getName() + "-" + num);
        });
    }
    for(innt i=0;i<5;i++){
        thread[i].start();
    }
}

ThreadLocal原理分析：主要介绍set方法，清理过程和替换过程。

Set()方法：

如果map为空的话，需要先创建map：

void creatMap(Thread t, T firstValue){
    t.threadLocals  = new ThreadLocalMap(this, firstValue);
}

map不为空时的执行逻辑：

1. 根据key的散列哈希计算Entry的数组下标

2. 通过线性探索探测从i开始往后一直遍历到数组的最后一个Entry

3. 如果map中的key和传入的key相等，表示该数据已经存在，直接覆盖

4. 如果map中的key为空，则用新的key、value覆盖，并清理key=null的数据

5. rehash扩容

private void set(ThreadLocal<?> key, Object value){
    Entry[] tab = table;
    int len = tab.length;
    //根据哈希码和数组长度求元素放置的位置，即数组下标
    int i = key.threadLocalHashCode & (len-1);
    //从i开始往后一直遍历到数组最后一个Entry(线性探索)
    for(Entry e = tab[i];
        e != null;
        e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();
        
        //如果key相等，覆盖value
        if(k == key) {
            e.value = value;
            return;
        }
        //如果key为null，用新key、value覆盖，同时清理历史ney=null的陈旧数据(弱引用)
        if(k == null){
            replaceStaleEntry(key, value, i);
            return;
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    //如果超过阈值，则扩容
    if(!cleanSomeSlots(i, sz) && sz >= threshold){
        rehash();
    }
}

线性探测，是用来解决hash冲突的一种策略。它是一种开放寻址策略，hash表是根据key进行直接访问的数据结构，也就是说可以通过 hash函数把key映射到hash表中的一个位置来访问记录，从而加快查找的速度。存放记录的数据就是hash表（散列表）。当针对一个key通过hash函数计算产生的一个位置，在hash表中已经被另外一个键值对占用时，那么线性探测就可以解决这个冲突，这里分两种情况：

1. 写入： 查找hash表中距冲突单元最近的空闲单元，把新的键值插入到这个空闲单元

2. 查找： 根据hash函数计算的一个位置处开始往后查找，直到找到与key对应的value或者找到空的单元。

replaceStaleEntry：

清理过程和替换过程：

private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot){
    Entry[] tab = table;
    int len = tab.length;
    Entry e;
    
    //向前扫描，查找最前一个无效的slot
    int slotToExpunge = staleSlot;
    for(int i = prevIndex(staleSlot, len);
        (e = tab[i]) != null;
        i = prevIndex(i, len)) {
        if(e.get() == null){
            //通过循环遍历，可以定位到最前面一个无效的slot
            slotToExpunge = i;
        }
    }
    //从i开始往后一直遍历到数组最后一个Entry(线性探索)
    for(int i = nextIndex(staleSlot, len);
        (e = tab[i]) != null;
        i = nextIndex(i, len)){
        ThreadLocal<?> k = e.get();
        //找到匹配的key以后
        if(k == key){
            //更新对应slot的value值
            e.value = value;
            //与无效的slot进行位置交换
            tab[i] = tab[slaleSlot];
            tab[staleSlot] = e;
            //如果最早的一个无效的slot和当前的staleSlot相等，则从i作为清理的起点
        	if(slotToExpunge = staleSlot){
            	slotToExpunge = i;
        	}
            cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
            return;
        }
        //如果当前的slot已经无效，并且向前扫描过程中没有无效slot，则更新slotToExpunge为当前位置
        if (k == null && slotToExpunge == staleSlot){
            slotToExpunge = i;
        }          
    }
    //如果key对应的value在entry中不存在，则直接放一个新的entry
    tab[staleSlot].value = null;
    tab[staleSlot] = new Entry(key, value);

	//如果有任何一个无效的slot，则做一次清理
    if (slotToExpunge != staleSlot){
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
    }
}