jdk包阅读笔记 - 823126028/book_reader GitHub Wiki

https://javadoop.com/2017/06/16/AbstractQueuedSynchronizer/

可以看出entry的结构除了 value 都是final的，意味着所有的插入都是在队列头。所有删除之前都必须remove。保证了for each 遍历和read的大部分操作是不用加锁的(hashMap 普通的read 也需要加锁)。

 	static final class HashEntry<K,V> {  

   		final K key;  

  		final int hash;  
  
  		volatile V value;  
  
 		final HashEntry<K,V> next;  
   
	}  

• count volatile 判断是否有element。
• Segment分段，用锁分段来减少锁的并发问题。
• put 所有操作都是加锁的,add 加在队头，next为final。
• read 这样读可以是无锁的，因为这样只会影响头部。遍历和读的时候最多的是本次不一致。
• remove 的时候做的是一个copy on write.

当改变的时候先复制整个list

加了锁的堆排序列表

并发的跳表

线程安全的有界数组。

• 基本数据结构： 数组模式的循环队列
• takeIndex,putIndex。当插入的时候,putIndex + 1,获取的时候,takeIndex +1。判断count来判断是空，还是满。所有操作外部都是加锁的。

线程安全的链表：

• 基本结构 count:AtomicInteger , head 头结点, last 尾节点。
• Lock:putLock 头结点锁，takeLock尾节点锁。
• condition:putCondtion,takeCondtion(判断是否能放入或者取出，用于阻塞)
• 遍历是在锁的内部。fullLock

命令发布器 可循环使用。

基本原理还是 ABS QUEUE，tryAccquire是否能获取节点。

• CountDownLatch的数目为state，只有state=0，才能获得共享锁，并激活其他的node
• acquiredShared: 先尝试tryAccquire，state-1, 如果 state == 0 才能accquire。否则进去queure 执行sharedQueue的逻辑， countDown执行doReleaseShared激活所有的queue里的node。

• 所有condition.await(),condition.signal 必须在lock中。
• condition.await(). 把加进condition 的AbsQueue里，设置node的state为Conditional的，并释放持有的state释放锁,然后如果node在queue里就阻塞当前线程。
• condition.signal 将 node 从condition 的queue 里 transfer 到 lock 的 AbsQueue，等待获得锁，继续执行,当前线程释放锁。

• state 的前N位和后N位 表示 互斥锁，共享锁。

• Lock:state 如果为0, cas,如果不为0,看看是不是自己,公平锁还要看看前面有没有排队的（hasProcessors）, 然后 和 exlusive 一样进queue。
• unLock: state reduce,如果变为0,那么就notify 后面一个node。

• lock:如果 writeState 不为0，看看owner thread 是不是自己，如果是自己也可以继续获取。 否则CAS 增加。如果前面有head是否是write node，如果是write node还要block，不能和前面的write node抢,如果false就返回。没有抢到就进入addQueue,不是队头就wait。 如果从queue中抢到了锁，会激活后面所有的。

• unLock, notify后面的所有的。让他们去争夺。

线程池的关键点是： 1、尽量减少线程切换和管理的开支； 2、最大化利用cpu。 对于1，要求线程数尽量少，这样可以减少线程切换和管理的开支； 对于2，要求尽量多的线程，以保证CPU资源最大化的利用。

所以对于任务耗时短的情况，要求线程尽量少，如果线程太多，有可能出现线程切换和管理的时间，大于任务执行的时间，那效率就低了； 对于耗时长的任务，要分是cpu任务，还是io等类型的任务。如果是cpu类型的任务，线程数不宜太多；但是如果是io类型的任务，线程多一些更好，可以更充分利用cpu。 所以： 高并发，低耗时的情况：建议少线程，只要满足并发即可；例如并发100，线程池可能设置为10就可以 低并发，高耗时的情况：建议多线程，保证有空闲线程，接受新的任务；例如并发10，线程池可能就要设置为20； 高并发高耗时：1要分析任务类型，2增加排队，3、加大线程数。 抢占式上下文切换(CPU时间片用尽),让步式上下文切换(锁的影响)。

惊群效应 线程池中如果有任务进来使用signalall 会引发，所有的等待线程全部醒来。造成上下文切换过多,使用signal。

coreSize MaxSize 当总size大于Coresize时空闲线程多久能活 time 存放容器。

if(size < coresize) addWorker()(如果大于maxsize 是add不进去的) else if(!put into queue) //如果这里的queue是无限的那么不可能超过core size,这样keep alive time 就没有意义了 再尝试增加addWorker

if(!addWorker()) reject();

worker. run_worker() while(pretask != null || task != getTask()){ task.run() }

getTask 就是从queue 里取值 如果取到了返回 ，没取到，如果worker_size > core_size 那么指定时间内没有东西进来就会返回推出线程

newFixedThreadPool(int nThreads) { return new ThreadPoolExecutor(nThreads, nThreads, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue());

CachedThreadPoolExecutor SynchronousQueue 只在add的时候有take才能进去，也只有take的时候必须有人往里面放。 这个时候时间到了就有的删除了。 return new ThreadPoolExecutor(0, Integer.MAX_VALUE, 60L, TimeUnit.SECONDS, new SynchronousQueue());

newSingleThreadExecutor core 1, max 1 LinkedBlockingQueue

SchedualThreadExecutor Queue 是delay的queue 是一个小根堆， submit的时候放入的是一个Runner和时间，之后add到queue里 然后初始化core size的线程如果小于每次都加一个

• arrayList 内部是一个数组 T []element_data，达到capacity翻3倍。
• add,remove 操作本质上都是 system.copy,
• 在头部remove 的消耗性能要远大于中间，或者尾部remove,因为system copy move的大小不同。 -- size记录在结构中 -- 靠modify的版本号来判断是否进行了并发，如果在其他线程中增加了修改次数会抛出异常 -- 内部的迭代器 iterator 靠index来进行移动。

LinkedList 内部是是一个保存 head,last 的带next指针的node列表 ,内部迭代器包括index和nextNode, returnNode;

内部是以hashMap 为组件的,内部全是syncronized线程安全的

• 不能支持并发，无论是put 还是 get都需要加锁。因为get的时候要遍历拉链，所以有可能出现死锁。
• 基本结构是一个数组Array[]，内部是一个链表拉链。
• thredhole 满了，会resize.
• Entry 的迭代器 node遍历 从数组0位置开始对拉链遍历

• timsort 对反序，和基本有序的数据处理较原来的merge sort要快很多(5倍左右)。
• 内部在对小分组情况下进行二分插排 binary_search，在选择小组的时候判断是否有序，有序或者倒序的情况是直接分成一组的。

自java 7 后改称 timsort 开始是判断大小如果小于那么直接使用binary_insert. 然后从队列里去，必须是严格顺序的否则，就出来，形成若干个run 如果后面的加起来没有前面的大，或者没有前面的大，继续合并，知道结束为止

• 实现简单，性能与堆排序相近，且分段性能好，在并发开发上要优于 堆排序。ConcurrentSkipListMap (java 并发类)

• 较为有序的时候比较占优势

• 快排的使用范围是在随机性较强的时候占优势。