并发知识补充

平时接触到的多线程知识汇总

synchronized

可以保证方法或者代码块在运行时，同一时刻只有一个方法可以进入到临界区，同时它还可以保证共享变量的内存可见性。
Java对象头和monitor是实现synchronized的基础。

修饰一个代码块，被修饰的代码块称为同步语句块，其作用的范围是大括号{}括起来的代码，作用的对象是调用这个代码块的对象；
修饰一个方法，被修饰的方法称为同步方法，其作用的范围是整个方法，作用的对象是调用这个方法的对象；
修改一个静态的方法，其作用的范围是整个静态方法，作用的对象是这个类的所有对象；
修改一个类，其作用的范围是synchronized后面括号括起来的部分，作用主的对象是这个类的所有对象。

ReentrantLock与AQS

synchronized的缺点

synchronized是一个非中断锁，当有线程需要获取已经被其他线程所占有的锁时，只能阻塞
性能较差，不过有偏向锁、轻量级锁，现在跟ReentrantLock差不多

ReentrantLock和synchronized比较

synchronized：还是有用的，隐式获取锁和释放锁，代码简单，性能现在也跟Lock差不多。而Lock必须在finally里释放锁，不然会造成死锁
lock接口，多了些附加功能，可以中断，有公平和非公平两种模式，有排他和共享模式。
都是可重入锁
synchronized是在jvm层次，而Lock是jdk层次，通过CAS+自旋实现的，提供了更加细粒度的加锁功能。

公平锁：线程获取锁的顺序和调用lock的顺序一样，FIFO；

非公平锁：线程获取锁的顺序和调用lock的顺序无关，全凭运气。

AQS（ AbstractQueuedSynchronizer）

AQS使用一个FIFO的队列表示排队等待锁的线程,每个节点维护一个等待状态waitStatus

AQS中还有一个表示状态的字段state，例如ReentrantLocky用它表示线程重入锁的次数，Semaphore用它表示剩余的许可数量，FutureTask用它表示任务的状态。对state变量值的更新都采用CAS操作保证更新操作的原子性。

例如：ReentrantLock，Semaphore，CountDownLatch，ReentrantReadWriteLock，FutureTask

ReentrantLock结构

lock()->sync.lock();调用的内部sync类的lock()

“非公平”体现在，如果占用锁的线程刚释放锁，state置为0，而排队等待锁的线程还未唤醒时，新来的线程就直接抢占了该锁，那么就“插队”了。

compareAndSetState(0, 1)，判断state是否为0（有没有其他线程占用），如果为0设置当前线程为该锁的独占线程。
如果发现该锁正在被占用，则acquire(1)(父类的)：如果此时state为0，则更改state，设置当前线程为独占线程；如果不为0，判断一下是否是当前线程占用了，如果是，更新state（可重入），不是则获取失败。
获取失败后，入队。如果尾节点不存在，需要初始化一个head节点入队列；如果尾节点存在，则通过CAS操作，判断尾节点没有发生改变，则设置当前节点为尾节点。
入队的线程不断尝试去获取获取锁，若失败就挂起（交给内核阻塞）。如果发现该节点是head节点的下一个，则可以获取锁，head节点丢弃掉（gc）。
挂起：只有前驱节点的waitState是否为SIGNAL，才能安心挂起；如果前驱节点不是SIGNAL，是CANCEL状态（取消），说明前置节点已经被放弃，通过dowhile循环，挂到SIGNAL节点下，成为它的后继，然后调用lockSupport()将自己挂起。 =>无限循环获取锁

unlock() ->sync.release(1)

流程大致为先尝试释放锁，若释放成功，那么查看头结点的状态是否为SIGNAL，如果是则唤醒头结点的下个节点关联的线程，如果释放失败那么返回false表示解锁失败。这里我们也发现了，每次都只唤起头结点的下一个节点关联的线程。

流程大概如下:

ReentrantReadWriteLock

读共享锁，如果存在其他线程获取写锁，则等待；允许多个读锁
写排他锁，如果存在其他线程获取写锁/读锁，则等待；只允许一个线程获取写锁
锁降级，如果当前线程获取写锁，可以获取读锁，降级

CountDownLatch、CyclicBarrier

Semaphore

Semaphore就是一个信号量，它的作用是限制某段代码块的并发数。
Semaphore有一个构造函数，可以传入一个int型整数n，表示某段代码最多只有n个线程可以访问，
如果超出了n，那么请等待，等到某个线程执行完毕这段代码块，下一个线程再进入。
由此可以看出如果Semaphore构造函数中传入的int型整数n=1，相当于变成了一个synchronized了。

ThreadLocal、四种引用类型

ThreadLocal：线程的局部变量，本身不存储值。通过当前线程找到ThreadLocalMap，查询ThreadLocal（key）的value
Thread有一个ThreadLocalMap<ThreadLocal,Object>,其中ThreadLocal为弱引用，如果ThreadLocal只有弱引用了，就会被gc，那么会存在<null,value>的Entry，value对象始终无法释放。

强引用 Object obj = new Object();就算oom异常，也不会gc释放
软引用内存不足时，会被gc
弱引用和软引用类似，但是不管空间足不足，只存在弱引用的对象都会被gc（我想每隔一段时间就看一下某个对象里面连各个filed的值，但我还不想强引用它以免阻止他被垃圾回收。这时候你就用weakreferrence就好了哦）
虚引用不影响对象的生命周期，用来跟踪对象被垃圾回收的活动，必须和引用队列联合使用，当对象要被gc前，会先放入引用队列。（程序可以通过判断引用队列中是否已经加入了虚引用，来了解被引用的对象是否将要被垃圾回收）

为什么有这4种：在某些情况下，我们希望有些对象不需要立刻回收或者说从全局的角度来说并没有立刻回收的必要性。比如缓存系统的设计，在内存不吃紧或者说为了提高运行效率的情况下，一些暂时不用的对象仍然可放置在内存中，而不是立刻进行回收。
区别：体现在在被GC回收的优先级上

Callable和、Future、FutureTask

Callable和Runnable类似，都可以创建线程，Callable里是实现call(),区别是有返回值的，可以通过Future接口里的get方法获取。

Thread()里只能Runnable构建，不能使用Callable。

1 2	ExecutorService executorService = Executors.newCachedThreadPool(); Future<Integer> future = executorService.submit(new CallableTest());

FutureTask实现了Future接口，可以通过callable来构建，放入Thread里，或者线程池里

1
2
3

FutureTask<Integer> futureTask = new FutureTask<Integer>(new FutureTaskTest());
Thread thread = new Thread(futureTask);
thread.start();

或者

1 2	ExecutorService executorService = Executors.newCachedThreadPool(); executorService.submit(futureTask);

ThreadPoolExecutor线程池

原因

线程的创建和销毁需要消耗资源（重复利用线程，减少创建和销毁的次数）
任务到来时，需要等待线程的创建。（提高响应速度）
如果无限制地创建，会造成系统的不稳定性。（提高线程的可管理性）

工作原理

当一个任务提交过来到线程池，线程池的处理如下：

如果正在执行任务的核心线程小于最大的核心线程数量（corePoolSize），则再创建新线程；（获取全局锁）
假如核心线程大于等于核心线程数量，加入BlockingQueue
如果BlockingQueue满了，而且没有达到线程池的最大容量（maximumPoolSize），则创建新线程执行任务（获取全局锁）
如果 BlockingQueue满了，但是如果创建新线程超出maximumPoolSize，任务被拒绝

api

execute():提交任务，给线程池执行
submit():execute+Future 相比有返回结果
shutdomn()：关闭线程池，等待任务执行完成，不影响
shutdownNow():关闭线程池，不等待任务执行完成，直接中断

四种线程池

FixedThreadPool：创建一个指定corePoolSize的线程池，当线程池小于corePoolSize，则创建；如果大于，则放进LinkedBlockingQueue（无界队列），因此线程数不会超过corePoolSize。
CachedThreadPool：跟据需要创建新线程的线程池，corePoolSize为0，最大线程数为无界的，队列为SychronousQueue，主线程提交任务，如果线程池里有向队列发起poll()操作的，则发起offer()配对；如果没有空闲或者初始化时，没有线程，则创建新线程执行任务。
SingleThreadExecutor创建一个单线程化的Executor，即只创建唯一的工作者线程来执行任务（corePoolSize为1，maximumPoolSize为1），如果这个线程异常结束，会有另一个取代它。单工作线程最大的特点是可保证顺序地执行各个任务，并且在任意给定的时间不会有多个线程是活动的。反复从LinkedBlockingQueue获取任务执行。
ScheduleThreadPool创建一个定长的线程池，而且支持定时的以及周期性的任务执行，类似于Timer。

四个拒绝策略

ThreadPoolExecutor.AbortPolicy() 直接抛出异常RejectedExecutionException
ThreadPoolExecutor.CallerRunsPolicy() 直接调用run方法并且阻塞执行
ThreadPoolExecutor.DiscardPolicy() 直接丢弃后来的任务
ThreadPoolExecutor.DiscardOldestPolicy() 丢弃在队列中队首的任务

线程池配置

cpu密集型，就需要尽量压榨CPU，NCPU+1
IO密集型，2*NCPU

Volatile

保证可见性：可见性的意思是当一个线程修改一个共享变量时，另外一个线程能读到这个修改的值。volatile变量进行写操作时，会加上#Lock前缀指令，当前处理器缓存行会立马写到系统内存里，使其他cpu缓存行里的缓存数据无效
禁止重排列，cpu和编译器会进行优化而导致指令重排列，加上内存屏障。进行写入操作时，会在写后面加上一条store指令，将本地内存中的共享变量值立即刷新到主存。在进行读操作时，会在读前面加上一条load指令，从主存中读取变量。

为什么重排列：CPU的主频越来越高，与cache的交互次数也越来越多，当CPU的计算速度远远超过访问cache，会产生cache wait。于是将cache进行分片，CPU可以自行选择多个闲置的分片（bank）

不保证原子性(i++,单例 new Instance(),long double 32位会分两次操作)

为对象分配内存；
调用对应的构造做对象的初始化操作；（构造函数）
将引用instance 指向新分配的空间。
可能第三步移到了第二步，导致其他线程可能会得到未初始化的非null对象
双重校验锁：
解决：需要加上volatile防止重排序出错，synchronized 保证非原子性不出错

CAS

多线程操作共享资源时，会出现三个问题：可见性、有序性以及原子性。

乐观锁

乐观锁: 假设不会发生并发冲突,只有在最后更新共享资源的时候会判断一下在此期间有没有别的线程修改了这个共享资源。如果发生冲突就重试，直到没有冲突，更新成功。CAS就是一种乐观锁实现方式。

悲观锁会阻塞其他线程。乐观锁不会阻塞其他线程，如果发生冲突，采用死循环的方式一直重试，直到更新成功。

cas就是一种乐观锁的实现，compare and swap

如果内存位置V的值与预期原值A相匹配，那么处理器会自动将该位置值更新为新值B,返回true。否则处理器不做任何操作，返回false。

比如当前线程比较成功后，准备更新共享变量值的时候，这个共享变量值被其他线程更改了，那么CAS函数必须返回false。

Unsafe类

java中提供了Unsafe类，它提供了三个函数，分别用来操作基本类型int和long，以及引用类型Object

public final native boolean compareAndSwapObject
       (Object obj, long valueOffset, Object expect, Object update);

    public final native boolean compareAndSwapInt
       (Object obj, long valueOffset, int expect, int update);

    public final native boolean compareAndSwapLong
      (Object obj, long valueOffset, long expect, long update);

参数的意义：

obj 和 valueOffset：表示这个共享变量的内存地址。这个共享变量是obj对象的一个成员属性，valueOffset表示这个共享变量在obj类中的内存偏移量。所以通过这两个参数就可以直接在内存中修改和读取共享变量值。
expect: 表示预期原来的值。
update: 表示期待更新的值。

getAndAddInt

public final int getAndAddInt(Object obj, long valueOffset, int var) {
        int expect;
        // 利用循环，直到更新成功才跳出循环。
        do {
            // 获取value的最新值
            expect = this.getIntVolatile(obj, valueOffset);
            // expect + var表示需要更新的值，如果compareAndSwapInt返回false，说明value值被其他线程更改了。
            // 那么就循环重试，再次获取value最新值expect，然后再计算需要更新的值expect + var。直到更新成功
        } while(!this.compareAndSwapInt(obj, valueOffset, expect, expect + var));

        // 返回当前线程在更改value成功后的，value变量原先值。并不是更改后的值
        return expect;
    }

i++，自增的过程包含了读改写，非原子操作。在改的过程时，其他cpu也许会更改共享变量的值，这时需要CAS操作来试探是否更改，如果发现更改，那么当前i+1 并非我们希望set的值，需要重新计算…

AtomicInteger类

成员变量和静态代码块

private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset; 

static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
}

private volatile int value; // 使用volatile修饰，解决了可见性和有序性问题。

value为AtomicInteger对象的值
valueOffset为value在对象内存空间的偏移
unsafe 一些native方法，通过它实现CAS操作，因为共享变量是int类型，所以调用compareAndSwapInt方法。

value是一个volatile变量，在内存中可见，任何线程都不允许对其进行拷贝，因此JVM可以保证任何时刻任何线程总能拿到该变量的最新值。

static中valueOffset=unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
通过unsafe 获取valueOffset（对象内存偏移量）

get/set

// 直接读取。因为是volatile关键子修饰的，总是能看到(任意线程)对这个volatile变量最新的写入
    public final int get() {
        return value;
    }

    // 直接写入。因为是volatile关键子修饰的，所以它修改value变量也会立即被别的线程读取到。
    public final void set(int newValue) {
        value = newValue;
    }

compareAndSet

1
2
3

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

如果value变量的当前值(内存值)等于期望值(expect)，那么就把update赋值给value变量，返回true。
如果value变量的当前值(内存值)不等于期望值(expect)，就什么都不做，返回false。
这个就是CAS操作，使用unsafe.compareAndSwapInt方法，保证整个操作过程的原子性

ABA问题

CAS通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

内存地址（c++）
线程 1 从内存位置V中取出A，A指向内存位置W。
线程 2 从位置V中取出A。
线程 2 进行了一些操作，释放了A指向的内存。
线程 2 重新申请内存，并恰好申请了内存位置W，将位置W存入C的内容。
线程 2 将内存位置W写入位置V。
线程 1 进行CAS操作，发现位置V中仍然是A指向的即内存位置W，操作成功

内存管理机制中广泛使用的内存重用机制，发现内存地址还是那个旧的指针变量，跟期待的值一样，则CAS操作成功，但实际指针变量的所指向内存空间里的值发生了改变

普通数据
进程P1读取了一个数值A
P1被挂起(时间片耗尽、中断等)，进程P2开始执行
P2修改数值A为数值B，然后又修改回A
P1被唤醒，比较后发现数值A没有变化，程序继续执行。

解决

对于内存重用机制导致ABA问题，java的垃圾回收机制帮我们解决了；
而第二个问题，加入版本号即可解决

HashMap

capacity:HashMap中桶的数量。默认值为16
transient int size;HashMap中存放KV的数量（为链表和树中的KV的总和）
int threshold; 如果当前size超过threshold，会调用resize方法（capacity * load factor）

put

首先检测table是否为空，为空则创建一个数组
判断key是否为null。若为null，特殊处理，创建一个（key为null）hash值为0的k-v对
算出key所对应的hash值，找出数组中对应的下标i
遍历table[i]是否存在相同的键值，如果相同则覆盖，返回一个老value值
如果没有一样的，调用addEntry()，判断在插入之前的size是否超过threshold，如果超过就调用resize()扩容两倍的长度,注意扩容的顺序，扩容之前old1->old2->old3，扩容之后old3->old2->old1
如果扩容了，因为数组的长度变了，需要重新计算下标。
插入：注意插入的顺序，原先table[index]的链表比如 old1->old2->old3，插入新值之后为new1->old1->old2->old3.

1.7之前是头插法，1.8之后是尾插法。因为1.8是数组+ 链表+红黑树（table[i]超过8个），效率变高，之前头插法是因为如果链表接了10000个，尾插法遍历太多。

get

如果key为null，则在table[0]寻找
否则计算key对应的hash，找到在table表中的下标
遍历table[i]的链表，通过hash和equals找到Entry
得到entry中的value

多线程为什么导致死循环

size超过当前最大容量*负载因子时候会发生resize
两个线程同时执行了resize的方法（transfer()），在各自内部线程的栈里都生成了局部的table。
比如：
扩容前 table[i] - >3 - > 7 - > null
需要扩容了，transfer方法：
- 线程1： e指向3,nexr指向7 暂时挂起
- 线程2：完成扩容，table[j] = 7 -> 3 - > null
线程1获取时间片，继续执行循环，这时把table[j] - >3 -> null，此时e指向7，next指向3；
然后继续插入，table[j] -> 7 -> 3 - >null，但是此时7的next已经是3，不是null了，则继续循环3；
e指向3，next为null；循环之后，3指向7；
互相指向，以后一旦执行到遍历next操作，会死循环，cpu占用率到100%

负载因子

默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本

hash算法： h & (length-1)

最常见的取hash算法是value mod length，而这里用的是‘&’运算
分析：HashMap的capacity都是2的幂，length-1转换成二进制就全是1，例如（16的容量，length-1就为1111），这样&运算的话，参与运算的另一个成员的每位是什么，运算结果就是什么。假设与hash值参与运算的某一位为0，那么不管hash的对应的那一位是什么，对应的运算结果位都为0，造成hash冲突。
&运算的好处

length（2的整数次幂）的特殊性导致了length-1的特殊性（二进制全为1）
位运算快于十进制运算，hashmap扩容也是按位扩容，所以相比较就选择了后者

如何解决hash冲突

哈希表：散列表（Hashtable，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希冲突：对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为哈希冲突。
解决hash冲突的方法：
（1）开放定址法（线性探测再散列，线性补偿探测法，伪随机探测）：这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi。
（2）再哈希法：就是算hashcode的方法不止一个，一个要是算出来重复啦，再用另一个算法去算，直到冲突不再发生为止。
（3）链地址法(Javahashmap就是这么做的)：这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
（4）建立一个公共溢出区：将哈希表分为基本表和溢出表两个部分，凡是和基本表发生冲突的元素，一律填入溢出表。

ConcurrentHashMap：分段锁

结构：Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

死锁

原因

1.因竞争资源发生死锁现象：系统中供多个进程共享的资源的数目不足以满足全部进程的需要时，就会引起对诸资源的竞争而发生死锁现象 2.进程推进顺序不当发生死锁

死锁的四个必要条件：

互斥条件：进程对所分配到的资源不允许其他进程进行访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源
请求和保持条件：进程获得一定的资源之后，又对其他资源发出请求，但是该资源可能被其他进程占有，此事请求阻塞，但又对自己获得的资源保持不放
不可剥夺条件：是指进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用完后自己释放
环路等待条件：是指进程发生死锁后，若干进程之间形成一种头尾相接的循环等待资源关系

检测死锁

有两个容器，一个用于保存线程正在请求的锁，一个用于保存线程已经持有的锁。每次加锁之前都会做如下检测:

检测当前正在请求的锁是否已经被其它线程持有,如果有，则把那些线程找出来
遍历第一步中返回的线程，检查自己持有的锁是否正被其中任何一个线程请求，如果第二步返回真,表示出现了死锁

死锁的预防：

破坏互斥条件：如果允许系统资源都能共享使用，则系统不会进入死锁状态。但有些资源根本不能同时访问，如打印机等临界资源只能互斥使用。所以，破坏互斥条件而预防死锁的方法不太可行，而且在有的场合应该保护这种互斥性。
破坏请求和保持条件：釆用预先静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源请求，
破坏剥夺条件：当一个已保持了某些不可剥夺资源的进程，请求新的资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。
破坏环路等待条件：为了破坏循环等待条件，可釆用顺序资源分配法。首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。

死锁的避免：

（1）安全序列：避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则让进程等待。所谓安全状态，是指系统能按某种进程推进顺序( P1，P2，…， Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称P1，P2，…，Pn为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
（2）银行家算法：银行家算法是最著名的死锁避免算法。它提出的思想是：把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前申请量分配资源，否则也要推迟分配。