发表于 | 分类于

Java反射

Java 反射机制在程序运行时，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意一个方法和属性。这种 动态的获取信息 以及 动态调用对象的方法 的功能称为 Java 的反射机制。

反射机制很重要的一点就是“运行时”，其使得我们可以在程序运行时加载、探索以及使用编译期间完全未知的 .class 文件。换句话说，Java 程序可以加载一个运行时才得知名称的 .class 文件，然后获悉其完整构造，并生成其对象实体、或对其 fields（变量）设值、或调用其 methods（方法）。

反射可以实现在运行时知道一个类的属性和方法。

阅读全文 »

发表于 | 分类于

Java异常

下图是Java异常层次结构图：

在Java中，所有的异常都有一个公共父类Throwable，其有两个重要的子类Error错误和Exception异常。其中，Error大多是虚拟机层面发生的错误，是程序无法处理的错误；而Exception则是用户程序可以捕获或可以处理的异常。Exception可以分为运行时异常RuntimeException和非运行时异常；又可以分为不受检查异常Unchecked Exception和检查异常Checked Exception。

阅读全文 »

发表于 | 分类于

常见排序算法

一. 选择排序

在循环中，每次找到剩下数组中最小的元素，并将这个最小的元素与当前元素交换位置。最后，整个数组就是有序的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        //k记录最小元素的下标
        int k = i;
        //在剩下元素中找最小元素的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[k]) {
                k = j;
            }
        }
        //如果最小元素不是自己，则交换位置
        if (k != i) {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
    System.out.println("selectSort:");
    for (int value : arr) {
        System.out.println(value);
    }
}

选择排序是最稳定的排序算法，哪怕是已经有序的数组进行选择排序的时间复杂度仍为O(n^2)，其不会利用数组的初始状态。空间复杂度为O(1)。

二. 插入排序

与选择排序一样，插入排序当前索引左侧的所有元素都是有序的，但他们的最终位置不确定。

对于当前元素current，取出上一个元素arr[preIndex]，如果上一个元素大于当前元素则将其移动到其下一个位置，重复此过程。这就相当于将current左侧比current大的元素全部右移一位，给current腾出位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void insertSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int preIndex = i - 1;
        //当前元素
        int current = arr[i];
        //如果上一个元素大于当前元素则将其右移一位，重复此过程
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        //将current插入到该腾出的位置
        arr[preIndex + 1] = current;
    }
    System.out.println("insertSort:");
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

插入排序利用了初始数组部分有序的特点，因此适合于局部有序的情况。

平均时间复杂度为O(n^2)，对于已经有序的数组，时间复杂度为O(n)。空间复杂度为O(1)。

三. 希尔排序

希尔排序是基于插入排序的改进排序算法。对于大规模乱序数组，插入排序很慢，因为它只会移动相邻的元素。希尔排序为了加快速度改进了插入排序，交换不相邻的元素以对数组进行局部排序，并最终用插入排序对局部有序的数组进行排序。

设置h作为间隔，对于每个h，用插入排序将h个子数组进行独立的排序，只需将插入排序中移动元素的距离由1改为h即可。

希尔排序比插入排序高效的原因是其权衡了子数组的规模和有序性。排序之初，子数组都很小，排序后子数组是局部有序的，这都有利于插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private static void shellSort(int[] arr) {
    int n = arr.length;
    int h = 1;
    //h= 1, 4, 13, 40, 121, 364, 1093
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        //将数组变为h有序
        for (int i = h; i < n; i++) {
            int preIndex = i - h;
            int current = arr[i];
            //将当前元素插入到arr[i-h]、arr[i-2*h]....中去
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + h] = arr[preIndex];
                preIndex -= h;
            }
            arr[preIndex + h] = current;
        }
        h /= 3;
    }
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

在我个人本地随机数组测试中，当数据规模大于等于10000时，希尔排序比插入排序近似快了一倍，且随着数据规模的扩大，速度差距也跟着扩大。

希尔排序的平均复杂度为O(n^1.3)，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。

四. 归并排序

归并排序是建立在归并基础上的排序算法。归并时将元素复制到辅助数组aux中，再把归并结果放回到原数组中。

自顶向下的归并排序

自顶向下的归并排序是分治思想的典型示例。要对子数组arr[left, right]进行排序，先将其分为arr[left...mid]和arr[mid+1...right]两部分，分别通过递归调用将他们单独排序，最后将排序好的子数组归并成最终的排序结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
   //用到的辅助数组
static int[] aux;   

public static void mergeSort(int[] arr) {
       int n = arr.length;
       aux = new int[n];
       mergeSort(arr, 0, n - 1);
       for(int value:arr){
           System.out.print(value+" ");
       }
   }
   //进行排序
   private static void mergeSort(int[] arr, int left, int right) {
       //递归终止条件
       if (left >= right) {
           return;
       }
       int mid = left + (right - left) / 2;
       //将左半部分排序
       mergeSort(arr, left, mid);
       //将右半部分排序
       mergeSort(arr, mid + 1, right);
       //归并
       //当arr[mid] <= arr[mid + 1]时已经有序，可以跳过归并
       if (arr[mid] > arr[mid + 1]) {
           merge(arr, left, mid, right);
       }
   }

   private static void merge(int[] arr, int left, int mid, int right) {
       //i,j为两个指针，起始时分别指向两个已经排序序列的起始位置
       int i = left, j = mid + 1;
       //将需要归并部分复制到辅助数组
       for (int k = left; k <= right; k++) {
           aux[k] = arr[k];
       }
       for (int k = left; k <= right; k++) {
           //左半部分用尽，取右半部分元素
           if (i > mid) {
               arr[k] = aux[j++];
               //右半部分用尽，取左半部分元素
           } else if (j > right) {
               arr[k] = aux[i++];
               //左半部分的当前元素小于右半部分的当前元素
           } else if (aux[i] < aux[j]) {
               arr[k] = aux[i++];
               //左半部分的当前元素大于等于右半部分的当前元素
           } else {
               arr[k] = aux[j++];
           }
       }
   }

自底向上的归并排序

自底向上的归并排序使用的是迭代的形式，先归并小数组，再成对归并得到的子数组。

初始时设置步长sz为1，因为是成对归并，所以每次步长长度增长一倍即sz = sz + sz。

枚举数组左边界lo，lo从0开始，每次增长一对sz的大小，将这一对sz大小的区间进行归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static void mergeSortIterator(int[] arr) {
    int n = arr.length;
    aux = new int[n];
    //步长增长一倍
    for (int sz = 1; sz < n; sz = sz + sz) {
        //子数组一对一对的归并
        for (int lo = 0; lo < n - sz; lo = lo + sz + sz) {
            //注意右边界要小于等于n-1
            merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, n - 1));
        }
    }
    for (int value : arr) {
        System.out.print(value + " ");
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int i = left, j = mid + 1;
    //将需要归并部分复制到辅助数组
    for (int k = left; k <= right; k++) {
        aux[k] = arr[k];
    }
    for (int k = left; k <= right; k++) {
        //左半部分用尽，取右半部分元素
        if (i > mid) {
            arr[k] = aux[j++];
            //右半部分用尽，取左半部分元素
        } else if (j > right) {
            arr[k] = aux[i++];
            //左半部分的当前元素小于右半部分的当前元素
        } else if (aux[i] < aux[j]) {
            arr[k] = aux[i++];
            //左半部分的当前元素大于等于右半部分的当前元素
        } else {
            arr[k] = aux[j++];
        }
    }
}

归并排序的时间复杂度为O(nlogn), 空间复杂度为O(n)。

在归并排序中使用了全局辅助数组aux，更好的做法是把aux作为mergeSort方法的局部变量，并把它作为参数每次传递给merge方法。

Wiki-归并排序

五. 快速排序

快速排序也是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序与归并排序是互补的：归并排序将数组分成两部分分别排序，并将有序的子数组归并来将整个数组排序；而快速排序则是当两个子数组都有序时整个数组就有序了。归并排序的递归调用发生在处理整个数组之前；快速排序的递归调用发生在处理整个数组之后。

快速排序通过递归调用切分来排序。先排定一个基准元素，一般是arr[left]，然后从数组左端开始扫描直到找到一个比他大的元素，再从数组右端进行扫描直到找到一个比他小的元素。交换他们的位置，直到左右指针相遇，再将基准元素与相遇位置的元素交换位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        System.out.println("quickSort:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //切分
        int j = partition(arr, left, right);
        quickSort(arr, left, j - 1);
        quickSort(arr, j + 1, right);
    }

    private static int partition(int[] arr, int left, int right) {
        //i，j为左右扫描指针
        int i = left;
        int j = right + 1;
        //key为基准元素
        int key = arr[left];
        while (true) {
            //向右扫描直到遇到一个大于等于基准的元素
            while (arr[++i] < key) {
                if (i == right) {
                    break;
                }
            }
            //向左扫描直到遇到一个小于等于基准的元素
            while (arr[--j] > key) {
                if (j == left) {
                    break;
                }
            }
            //指针相遇时结束
            if (i >= j) {
                break;
            }
            //交换i，j位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //交换基准元素与相遇时元素位置
        int temp = arr[left];
        arr[left] = arr[j];
        arr[j] = temp;
        return j;
    }

快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，空间复杂度为O(nlogn)。

六. 堆排序

堆是一种近似二叉树的结构，一般用一维数组表示，且子节点的键值或索引总小于(或者大于)他的父节点。若按升序排列，则把数组换成最大堆。重复从最大堆取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆维持最大堆性质。

对于起始索引为0的数组来说，节点索引为i的节点：

  • 左子节点为2*i+1；
  • 右子节点为2*i+2;
  • 父节点为floor((i-1)/2)。

堆中最大值总是位于根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
   public static void heapSort(int[] arr) {
       int len = arr.length - 1;
       //将数组堆化， beginIndex为第一个非叶子节点索引，叶子节点可以看成满足堆结构的节点
       int beginIndex = (arr.length >> 1) - 1;
       for (int i = beginIndex; i >= 0; i--) {
           maxHeapify(i, len, arr);
       }
       //对堆化数据排序
       //每次都移出最顶层的根节点与最尾部节点进行交换，同时遍历长度减一
       //然后重新整理被交换到根节点的元素进行下沉操作使其满足堆的结构
       //直到未排序堆的长度为0
       for (int i = len; i > 0; i--) {
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;
           maxHeapify(0, i - 1, arr);
       }
       System.out.println("HeapSort:");
       for (int value : arr) {
           System.out.print(value + " ");
       }
   }
//调整索引为index处的元素，使其满足堆结构，len为未排序堆的长度
   private static void maxHeapify(int index, int len, int[] arr) {
       //左子节点索引
       int li = (index << 1) + 1;
       //右子节点索引
       int ri = li + 1;
       //左子节点超出计算范围
       if (li > len) {
           return;
       }
       //子节点最大值索引，初始默认为左节点
       int maxIndex = li;
       if (ri <= len && arr[li] < arr[ri]) {
           maxIndex = ri;
       }
       //如果子节点最大值大于父节点，交换，并继续递归调用直到满足堆结构
       if (arr[maxIndex] > arr[index]) {
           int temp = arr[index];
           arr[index] = arr[maxIndex];
           arr[maxIndex] = temp;
           maxHeapify(maxIndex, len - 1, arr);
       }
   }

堆排序的时间复杂度为O(nlogn)。

发表于 | 分类于

并发容器集合

java.util包下提供了一些容器类，其中vector和HashTable是线程安全的容器类。但这些容器类实现同步的方式是通过对方法加锁(synchronized)来实现的。这样的话读写操作均需要锁操作，造成效率低下。

因此，Java5之后提供了一些并发容器来在多线程下代替同步容器，提高容器的并发访问性，同时定义了线程安全的复合操作。

并发容器类

阅读全文 »

发表于 | 分类于

Java多线程-锁接口和类

Java原生的锁是基于对象的锁，一般是配合synchronized使用的。而在java.util.concurrent包下，还提供了几个关于锁的接口和类。

synchronized的不足

  • 使用synchronized，临界区的代码同一时间只有一个线程能执行。即便临界区是只读操作。
  • synchronized无法知道线程有没有成功获得锁。
  • 使用synchronized如果临界区因为IO或者sleep等阻塞了，当前线程又没有释放锁，就会导致所有的线程都会等待。

锁的分类

锁可以根据不同的方式进行分类。

可重入锁和不可重入锁

可重入锁就是支持重新进入的锁，也就是支持一个线程对资源重复加锁。

synchronized就是使用的可重入锁。可重入性实际上是基于线程的分配，而不是基于方法调用的分配。

Lock也是一个可重入锁。

公平锁与非公平锁

这里的公平指的是先来先执行。如果一个锁对先请求获取的线程先满足，对后请求获取的线程后满足，这个锁就是一个公平锁。

一般，非公平锁能提升效率，但非公平锁可能会导致一些线程长时间获取不到锁。

ReentrantLock支持公平锁与非公平锁两种。

读写锁和排它锁

synchronized和ReetrantLock都是排它锁，这些锁在同一时间内只允许一个线程进行访问。

而读写锁同一时刻允许多个线程访问。Java提供了ReetrantReadAndWriterLock类作为读写锁的默认实现，其内部维护了两个锁：一个读锁、一个写锁。通过分离读锁和写锁，使得读多写少的场景下效率大大提高。使用读写锁时，在写线程启动时，读线程和其他的写线程均被阻塞。

JDK中关于锁的接口和类

抽象类AQS/AQLS/AOS

AQS，抽象队列同步器，是JDK提供的一个“队列同步器”的基本功能实现。

AQS中的资源使用一个int类型的数据表示的，如果我们的资源数量超出了int的范围，就可以使用AQLS。AQLS与AQS几乎一样，只是把资源的类型变成了long类型。

AQS和AQLS都继承了一个类AOS：AbstractOwnableSynchronizer，用于表示锁与持有者的关系(独占模式)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public abstract class AbstractOwnableSynchronizer implements Serializable {
    private static final long serialVersionUID = 3737899427754241961L;
    //独占模式，锁的持有者
    private transient Thread exclusiveOwnerThread;

    protected AbstractOwnableSynchronizer() {
    }
    //设置锁持有者
    protected final void setExclusiveOwnerThread(Thread thread) {
        this.exclusiveOwnerThread = thread;
    }
    //获取锁的持有线程
    protected final Thread getExclusiveOwnerThread() {
        return this.exclusiveOwnerThread;
    }
}

接口Condition/Lock/ReadWriteLock

java.util.concurrent包下有三个接口：Condition、Lock、ReaderWriteLock。其中，Lock和ReadWriteLock分别是锁和读写锁。

ReadWriteLock只有两个方法，分别返回读锁和写锁。

1
2
3
4
5
public interface ReadWriteLock {
    Lock readLock();

    Lock writeLock();
}

Lock接口的方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Lock {
    //获得锁，如果锁被其他线程获取，则等待
    void lock();
    //通过这个方法获取锁时，如果这个线程正在等待获取锁，则这个线程能够中断等待状态。
    void lockInterruptibly() throws InterruptedException;
    //尝试获得锁，成功返回true，失败返回false。立即返回，拿不到锁时不会一直等待
    boolean tryLock();
    //与tryLock大体相同，但拿不到锁时会等待指定时间
    boolean tryLock(long var1, TimeUnit var3) throws InterruptedException;
    //释放锁，与synchronized不同，Lock必须手动释放锁，否则会可能陷入死锁
    void unlock();
    //实现类似于Object的wait/notify等待/通知机制
    Condition newCondition();
}

Lock接口中有一个方法可以获得Condition。每个对象都可以利用继承自Object的wait/notify方法来实现等待/通知机制。Condition也提供了类似的方法，通过与Lock的配合来实现等待/通知机制。

对比项 Object监视器 Condition
前置条件 获取对象的锁 调用Lock.lock获取锁，调用Lock.newCondition()获取Condition对象
调用方式 直接调用，如object.notify() 直接调用，如condition.await()
等待队列的个数 一个 多个
当前线程释放锁进入等待状态 支持 支持
当前线程释放锁进入等待状态，在等待状态中断 不支持 支持
当前线程释放锁并进入超市等待状态 支持 支持
当前线程释放锁进入等待状态直到将来的某个时间 不支持 支持
唤醒等待队列中的一个线程 支持 支持
唤醒等待队列中的全部线程 支持 支持

Condition与Object的wait/notify基本相似。Condition.await()对应Object.wait()，Condition.signal/signalAll对应Object.notify/notifyAll。

ReentrantLock

ReentrantLock是JDK提供的Lock接口的默认实现，实现了锁的基本功能。其是一个可重入锁，内部有一个抽象类abstract static class Sync extends AbstractQueuedSynchronizer继承了AQS，是自己实现的一个同步器，有两个非抽象类static final class FairSync extends ReentrantLock.Sync和static final class NonfairSync extends ReentrantLock.Sync，分别是公平同步器和非公平同步器，代表着ReentrantLock支持公平锁与非公平锁。

这两个同步器都调用了AOS的setExclusiveOwnerThread(current);方法，所以ReentrantLock的锁是独占的，也就是说是排他锁，不能共享。

1
2
3
public ReentrantLock(boolean fair) {
    this.sync = (ReentrantLock.Sync)(fair ? new ReentrantLock.FairSync() : new ReentrantLock.NonfairSync());
}

在ReentrantLock的构造方法中，可以传入一个布尔类型的参数fair来指定其是否是公平锁，默认是非公平锁。

ReentrantReadWriteLock

ReentrantReadWriteLock类是ReadWriteLock接口的默认实现。与ReentrantLock类似，都是可重入的，支持公平锁与非公平锁。不同的是其还支持读写锁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class ReentrantReadWriteLock implements ReadWriteLock, Serializable {
    //省略部分代码
    private final ReentrantReadWriteLock.ReadLock readerLock;
    private final ReentrantReadWriteLock.WriteLock writerLock;
    final ReentrantReadWriteLock.Sync sync;
    
    //构造方法，默认是非公平锁
     public ReentrantReadWriteLock() {
        this(false);
    }
    public ReentrantReadWriteLock(boolean fair) {
        this.sync = (ReentrantReadWriteLock.Sync)(fair ? new ReentrantReadWriteLock.FairSync() : new ReentrantReadWriteLock.NonfairSync());
        this.readerLock = new ReentrantReadWriteLock.ReadLock(this);
        this.writerLock = new ReentrantReadWriteLock.WriteLock(this);
    }
    
    //获取读锁与写锁的方法
    public ReentrantReadWriteLock.WriteLock writeLock() {
        return this.writerLock;
    }
    public ReentrantReadWriteLock.ReadLock readLock() {
        return this.readerLock;
    }
    
    static final class FairSync extends ReentrantReadWriteLock.Sync {
        //省略实现
    }
    static final class NonfairSync extends ReentrantReadWriteLock.Sync {
        //省略实现
    }
    abstract static class Sync extends AbstractQueuedSynchronizer{
        //省略实现
    }
    
    //读锁与写锁
    public static class ReadLock implements Lock, Serializable {
        private final ReentrantReadWriteLock.Sync sync;
        protected ReadLock(ReentrantReadWriteLock lock) {
            this.sync = lock.sync;
        }
        ...
    }
    public static class WriteLock implements Lock, Serializable {
        private final ReentrantReadWriteLock.Sync sync;
        protected WriteLock(ReentrantReadWriteLock lock) {
            this.sync = lock.sync;
        }
        ...
    }
}

可以看到，ReentrantReadWriteLock内部维护了两个同步器和两个Lock的实现类ReadLock和WriteLock。

实现了读写锁，但在写操作时，其他线程不能读也不能写，存在“写饥饿”。

StampedLock

public class StampedLock implements Serializable可以看到，StampedLock并没有实现Lock接口和ReadWriteLock接口，但其实现了“读写锁”的功能，并且性能更好。StampedLock把读锁和写锁分为乐观读锁和悲观读锁两种。

StampedLock避免了写饥饿现象，它的核心思想在于，在读的时候如果发生了写，应该通过重试的方法来获取新的值，而不应该阻塞写操作。这种模式也是典型的无锁编程思想，与CAS自旋的思想一样。StampedLock适合在读多写少的场景下使用，同时避免了写饥饿的产生。官方使用实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Point {
	private double x, y;	
	private final StampedLock stampedLock = new StampedLock();
	//写锁的使用
	void move(double deltaX, double deltaY){
		long stamp = stampedLock.writeLock(); //获取写锁
		try {
			x += deltaX;
			y += deltaY;
		} finally {
			stampedLock.unlockWrite(stamp); //释放写锁
		}
	}
	
	//乐观读锁的使用
	double distanceFromOrigin() {
		long stamp = stampedLock.tryOptimisticRead(); //获得一个乐观读锁
		double currentX = x;
		double currentY = y;
		if (!stampedLock.validate(stamp)) { //检查乐观读锁后是否有其他写锁发生，有则返回false
			stamp = stampedLock.readLock(); //获取一个悲观读锁
			try {
				currentX = x;
			} finally {
				stampedLock.unlockRead(stamp); //释放悲观读锁
			}
		} 
		return Math.sqrt(currentX*currentX + currentY*currentY);
	}
	
	//悲观读锁以及读锁升级写锁的使用
	void moveIfAtOrigin(double newX,double newY) {
		long stamp = stampedLock.readLock(); //悲观读锁
		try {
			while (x == 0.0 && y == 0.0) {
				long ws = stampedLock.tryConvertToWriteLock(stamp); //读锁转换为写锁
				if (ws != 0L) { //转换成功
					stamp = ws; //票据更新为写锁的
					x = newX;
					y = newY;
					break;
				} else {
					stampedLock.unlockRead(stamp); //转换失败释放读锁
					stamp = stampedLock.writeLock(); //强制获取写锁
				}
			}
		} finally {
			stampedLock.unlock(stamp); //释放所有锁
		}
	}
}

乐观读锁的意思是假定在这个锁获取期间，共享变量不会被改变。在获取乐观读锁后进行了一些操作，然后调用validate方法，这个方法是验证是否有写操作执行过，如果有，则获取一个悲观读锁。

StampedLock获取锁时会返回一个long类型的变量，释放锁时再把这个变量传进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   //用于操作state后获取stamp的值
   private static final int LG_READERS = 7;
   private static final long RUNIT = 1L;
   private static final long WBIT = 128L;
   private static final long RBITS = 127L;
   private static final long RFULL = 126L;
   private static final long ABITS = 255L;
   private static final long SBITS = -128L;
//初始化state的值
   private static final long ORIGIN = 256L;
//锁共享变量state
   private transient volatile long state = 256L;
//读锁溢出时用来存储多出的读锁
   private transient int readerOverflow;

StampedLock用long类型变量的前7位(LG_READERS)来表示读锁，每获得一个悲观读锁，就加一(RUNIT)，每释放一个悲观读锁，就减一。而悲观读锁最多只能存储128个（7位限制），所以用一个int类型的变量来存储溢出的悲观读锁。

写锁用state变量剩下的位来表示，每次获得一个写锁，就加 0000 1000 0000(WBIT)。每次释放一个写锁，并不是减WBIT，而是再加上WBIT，这样做的目的是让每次写锁都留下痕迹，解决CAS的ABA问题，也为乐观锁见检查变化validate方法提供基础。

乐观读锁并没有改变state的值，而是在获取锁的时候记录state的状态，在操作完成后检查state的写状态部分是否发生变化，因为每次写锁都会留下痕迹。

发表于 | 分类于

线程池原理

线程池的优势

  1. 创建/销毁线程会消耗系统资源，线程池可以复用已创建的线程。
  2. 控制并发的数量。线程并发数量过多，会抢占系统资源并造成阻塞。
  3. 可以对线程做一些简单的管理。

ThreadPoolExecutor的原理

Java中线程池顶层接口为Executor，ThreadPoolExecutor是其一个具体实现类。

阅读全文 »

发表于 | 分类于

1. @SpringBootApplication

这个注解是SpringBoot项目的基石，所有创建的SpringBoot项目都会默认在主类上加上这个注解。

SpringBoot注解@SpringBootApplication.PNG

我们可以把@SpringBootApplication看成是@Configuration、@EnableAutoConfiguration和@ComponentScan注解的集合。

这三个注解的作用分别如下：

  • @EnableAutoConfiguration：启动SpringBoot的自动配置机制。
  • @ComponentScan：扫描被@Component(@Service、@Controller)注解的Bean，注解会默认扫描该类所在包下的所有类。
  • @Configuration：允许在Spring上下文中注册额外的Bean或导入其他配置类。
阅读全文 »

发表于 | 分类于

synchronized关键字

synchronized翻译成中文就是同步的意思。我们通常使用synchronized关键字来给一段代码或一个方法上锁。其主要有以下三种方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  //关键字在实例方法上，锁为当前实例
   public synchronized void instanceLock(){
       //code
   }
//关键字在静态方法上，锁为当前Class对象
   public static synchronized void classLock(){
       //code
   }
//关键字在代码块上，锁为括号里面对象
   public void blockLock(){
       Object o = new Object();
       synchronized (o){
           //code
       }
   }

java中的锁都是对象锁，我们常说的类锁也是对象锁。Java类只要一个Class对象，多个实例对象共享这一个Class对象。类锁就是Class对象的锁。

阅读全文 »

发表于 | 分类于

基本概念

内存可见性

JMM有一个主内存，每个线程都有自己私有的工作线程，工作内存中保留了一些变量在主内存的拷贝。

内存可见性，指的是线程之间的可见性，当一个线程修改了共享变量后，另一个线程可以读取到这个更改后的值。

重排序

为了优化程序性能，对原有的指令执行顺序进行优化重新排序。重排序可能发生在多个阶段，比如编译重排序、CPU重排序。

happens-before原则

是一个给程序员使用的规则，只要遵守happens-before原则，JVM就能保证指令在多线程之间的顺序性符合预期。

阅读全文 »

发表于 | 分类于

共享内存并发模型

并发编程模型有两个关键问题，即线程间如何通信，即线程间以何种机制来交换信息；线程间如何同步，即线程以何种机制来控制不同线程间操作发生的相对顺序。

有两个并发模型

  • 消息传递并发模型
  • 共享内存并发模型
如何通信 如何同步
消息传递并发模型 线程间没有公共状态，必须通过发送消息显示地进行通信 发送消息总在接受消息之前，同步是隐式的
共享内存并发模型 线程间共享程序的公共状态，通过读-写内存中的公共状态进行隐式通信 必须显示指定某段代码需要在线程之间互斥执行，同步是显示的。

Java中使用的是共享内存并发模型。

阅读全文 »