算法部分：
复习一下二叉树的题目：
简单的前中后序遍历：
解二叉树的题目的逻辑：
1.确定入参和返参
2.确定终止条件
3.确认每层的逻辑
例如简单的后续遍历。 后续遍历是左右中。
那么入参和返参根据题目来做。
终止条件是： 遍历下去，遍历到的根节点为null
每层的逻辑是：左右中
代码如下，前中序列类似：
安排周末把二叉树重新过一遍。刷过的题忘了一大半。
今天时间有限，先继续往下刷，刷回溯算法。
回溯算法的本质是穷举，效率一般，如果想要提高效率，就需要进行剪纸操作。
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
1.返回值以及参数
void backtracking(val1，val2.....)
2.回溯函数终止条件
if (终止条件) {
存放结果;
return;
}3.回溯搜索遍历过程
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
for循环相当于在横向遍历，backtracking相当于调用自己，挖掘深度的纵向遍历。回溯算法都可以抽象成N叉树的问题。把回溯看做树的遍历
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
表锁：共享锁、排它锁、意向锁、MDL锁
行锁：共享锁、排它锁
区间锁：间隙锁、临键锁
共享锁和排它锁：
共享锁：
共享锁可以被多个线程共同持有。获取共享锁只能去读数据，不能写数据。
排它锁：
排它锁也叫互斥锁、独占锁。只能被一个线程独享，独享期间可以读写数据。synchronized和JUC的lock实现类用的是独占锁。
从ReentrantReadWriteLock的源代码来了解一下共享锁和互斥锁：
我们可以看出来，这个可冲入读写锁的类，有读锁和写锁的分别实现，通过传入是否公平fair来实现公平版本和非公平版本的锁机制。
接下来看一下读锁和写锁分别的实现过程。
读写锁都是依靠sync来实现，sync是AQS的一个子类。
读锁是共享锁，写锁是独享锁。读锁的共享锁可保证并发读非常高效，而读写、写读、写写的过程互斥，因为读锁和写锁是分离的。所以ReentrantReadWriterLock并发性相比一般的互斥锁有了很大提升。
既然是基于AQS，那么AQS中的很多东西都是公用的，比如比较重要的state属性，用来描述有多少线程获取到锁。
在共享锁，state一般标识有多少获取锁；在独占锁，state一般只有0和1两种状态；在重入锁中，state表示重入的次数
由于ReentrantReadWriteLock有读写两把锁，所以一个state被区分为高16位和低16位，分别标识读锁和写锁的个数
写锁获取：
由于写锁是基于sync，所以我们可以在sync的代码中看到加写锁的源码：
1.首先我们通过getState取到锁的个数。然后通过exclusiveCount方法获取到写锁的个数（低16位）。
2.判断是否已经有线程持有写锁？ 写锁数目为0（由于c!=0,但是w=0，所以此时存在读锁）或者持有锁的线程不是当前线程（写锁可能被其他线程获取但不是当前线程） --->返回false
3.如果写锁个数超出最大值，抛出异常。
排除以上的情况，写锁重入成功
c=0的情况（没有任何锁）：
这里牵扯到公平锁和非公平锁，需要判断一下是否要阻塞：
非公平锁直接返回false
公平锁 ：需要判断当前同步队列中是否有阻塞的线程，如果有，那么当前线程也需要去同步队列阻塞
如果不需要阻塞，就通过CAS去修改state属性值，然后将当前线程设置为独占线程
写锁的释放：
由于可重入，释放一次写锁后需要判断是否需要再次释放。如果释放之后扣完state值为0，说明没有写锁被占用，设置独占线程为null，返回true。在release()中就会去唤醒同步队列中阻塞的线程
读锁的获取（共享锁）：
读锁的获取调用的是AQS的acquireShared()，ReentrantReadWriteLock.Sync中实现了tryAcquireShared()方法
excluscie：独占 share：共享
1.如果当前写锁个数不为0，且获取写锁的线程不是当前线程，那么不能获取读锁，并加入读写锁的同步队列。
2.获取当前读锁的个数，判断读锁是否需要阻塞：
1）如果不需要阻塞读锁，并且读锁数量合法，并且视图通过CAS去修改获取读锁次数成功，那么就把当前线程读锁次数+1.
读锁通过firstReader和firstReaderHoldCount的属性值来记录第一个获取读锁的线程。
如果当前线程就是第一个获取锁的线程，且是重入获取读锁，直接将firstReaderHoldCount+1
如果不是第一个获取，那么就修改cachedHoldCounter的值，这个cachedHoldCounter用来缓存最近一个获取读锁的线程.
如果缓存cachedHoldCounter中的线程不是当前线程，则从readHolds中获取当前线程获取读锁的情况，readHolds.get()返回的是一个HoldCounter对象，最后将HoldCounter对象中的count属性值+1。
3.如果获取读锁失败：最后调用fullTryAcquireShared()去自旋尝试获取读锁，该方法的源码基本与tryAcquireShared()是一样的，就不再赘述
读锁的释放：
读锁释放调用的是AQS的releaseShared()，核心逻辑在tryReleaseShared()中
顺序是：第一个获取读锁的线程释放锁，然后其他线程释放
如果该线程释放读锁后读锁个数为0，应该同步清除ThreadLocal中的HoldCounter值。
读锁的释放是可以并发进行的,所以通过CAS来修改state属性值
总结：
共享锁和独占锁互斥，但是共享锁和共享锁是不互斥的。
多个事务同时更新一行数据，都会加锁，然后排队等待，必须一个事务执行完毕提交了，释放锁，才能唤醒下一个事务继续执行，这个时候加的是独占锁。
当有人在更新数据时，其他事务可以读，因为读写两个操作不互斥MVCC机制，但是读写锁是互斥的。
标签：乔亚,互斥,写锁,读锁,---,获取,Day16,线程,共享 From： https://www.cnblogs.com/dwj-ngu/p/17137157.html