为什么需要内存模型?

我们知道在并发编程中需要处理两个关键问题：线程之间的通信，以及线程之间的同步。线程之间的通信机制有两种：共享信息和消息传递。共享信息是指某个线程改变了共享信息，之后另外一个线程读取这个共享信息，这就完成了一次通信。从中我们可以看到这种通信是隐式进行的。但是在消息传递并发模式中，线程之间没有公共状态，它们之间必须通过发送消息来进行显示式通信。Java的并发采取的是共享信息的模式，线程之间的通信总是隐式进行，通信过程对程序员不透明，如果编码时候不理解这种隐式通信机制，就会遇到各种内存可见性的问题。

现代处理器为了提升数据存取的效率在CPU内部都加了L1,L2,L3这样的三级缓存(Cache)：

我们上文中提到的共享信息其实就是放到了主内存中的。线程A执行操作的时候如果发现Cache中没有就会从主存中拷贝一份副本，存储到本地，线程B需要数据的时候也从主存中拷贝一份副本到本地缓存中。如果线程A的操作完成之后将操作结果在线程B执行之前就刷新到主存中，那么线程B就可以看见最新的数值：

但是既然Cache的存在是为了减少访问主存的次数，那么如果每次都这样先更新本地缓存，然后立即刷新到主存，那么使用Cache就不能带来性能的提升了。所以这里就是有一个问题，什么时候A线程对共享变量的操作对线程B是可见的？

什么是Java内存模型？

针对上文中提出的问题，我们引入内存模型(JMM)的概念。内存模型其实就是一套规则，这套规则决定了一个线程对共享变量的写入何时对另一个线程可见。它的抽象结构示意图如下：

指令重排优点和缺点

指令重排是编译器和处理器在为了提升程序的执行效率而对代码所做的优化，这种优化在单线程中没有问题，但是在多线程中，就可能违背了JMM对内存可见性的约束，关于这方面的内容，请参考我的另外一篇文章:计算机基础知识。所以编译器为了满足JMM的要求，就需要在合适的位置给其所编译的代码加上内存屏障来禁止特定类型的重构排序，这种内存屏障还可以确保某个操作是否立即刷新到主存，以保证对之后的操作是可见的。内存屏障有四种类型：LoadLoad，LoadStore，StoreStore，StoreLoad。它们分别插在：读读，读写，写写，写读之间用来确保之后和之前的操作不能进行指令重排，与此同时如果前面的操作是写操作，还要保证它对于后面的操作是可见的。

volatile同步原语

上面说了JMM的相关概念，下面就用volatile来举例说明，JMM是如何确保它的可见性和原子性的内存语义的。
volatile也被称为轻量级锁，如果某个变量被声明为volatile，那么对它的读操作和写操作就具有原子性，但是如果是复合操作，那么就不具有原子性，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class VolatileFeaturesExample {
    volatile long v1 = 0L;
    public void set(long l){
        v1 = l;
    }

    public long get(){
        returen v1;
    }

    public void getAndIncrement(){
        v1 ++;
    }
}

在这里set和get方法的语义和加了锁是一样的，其中getAndIncrement其实可以分为以下三个部分：

1
2
3
4
5

public void getAndIncrement(){
    long tempt = get();
    temp += 1L;
    set(tempt);
}

这其中get和set方法是加锁的，但是tempt += 1L;在执行的时候可以有多个线程同时操作（比如两个线程同时判断了get()的值，然后在线程A对其进行改变的过程中，线程B也对其进行修改），所以不具有原子性，也就是说volatile让单个读和写操作具有原子性，但是对于复合操作是没有原子性的。

volatile变量读写的内存语义

什么是内存语义？内存语义就是说某段代码，在进行内存实际操作的时候是怎样的。 对volatile变量执行写操作，会将线程的本地内存值刷新到主存中；对volatile变量执行读操作，操作系统会将变量所在线程的本地内存置为无效，然后该线程就会从主内存中读取该volatile变量。这样就保证了写线程的操作对读线程是可见的了。这个过程其实就是两个线程之间进行通信的过程。

也就是说避免指令重排是实现可见性的基础，如果不限制相应的指令重排就不会具有可见性，而避免指令重排就需要插入相关的内存屏障，内存屏障不仅保证了内存不被重拍，同时保证了内存的可见性。比如StoreStore屏障，它可以保证前一个写操作的数据可以刷新到主存，也就是说对下一个操作是可见的。

volatile内存语义的实现原理

从上文可以看出，要确保volatile变量可见性的实现就必须要避免其前后的相关操作不进行指令重排，下面是JMM对编译器规定的指令重排规则：

1. 当第二个操作是volatile写的时候，不管第一个操作是不是volatile操作，都不能将两个操作重排序。
2. 当第一个操作是volatile读的时候，不管第二个操作是不是volatile操作，都不能将两个操作重排序。
3. 第一个操作是volatile写，第二个操作是volatile读的时候不能，不能将两个操作重排序。

为了实现这个规则，编译器必须在volatile的前后插入内存屏障来做保证：

• 在每个volatile写的前面加上StoreStore屏障。
• 在每个volatile写的后面加上StoreLoad屏障。
• 在每个volatile读的后面插入一个LoadLoad屏障。
• 在每个volatile读的后面插入一个LoadStore屏障。

因为上文中JMM规定第一个volatile读操作后面的任意操作都不能重排序，所以加入了两个屏障。又因为volatile写操作的要避免和之前的指令以及之后的voloaile读操作指令重拍，所以要在其后面加上StoreLoad屏障，其前面加上StoreStore屏障可以避免之前的写操作和volatile写做指令重排。如下图所示：

在上面volatile写后面加入StoreLoad屏障是为了防止和下面可能出现的volatile读/写重排序，为什么是可能出现呢？因为编译器有时没有办法确定其后面是否有必要插入StoreLoad屏障，因为如果volatile在方法的最后一行，然后就return了，这时就没有必要了，但是为了防止少插入的情况，编译器就在volatile写的后面都加上了LoadStore屏障，这是一种保守的做法。从上面我们可以看到volatile读和写的内存屏障插入策略是非常保守的，然而再实际情况下，编译器可以根据代码的实际情况，在不影响内存语义的情况下，减少某些不必要的屏障插入（这些优化也跟处理器类型有关）。

内置锁和显示锁

在Java5中ReentrantLock相比内置锁有很大的性能提升，但是在Java6中内置锁的性能有了很大的提升，他们的性能相差不大。并且由于synchronized是JVM的内置属性，所以它在未来可以进行更深层次的优化。
内置锁相比显式锁拥有以下的优势：

• 结构更加紧凑
• 使用内置锁不用手动进行解锁，所以具有更低的危险性
• 在线程转储(thread dumps)过程中能给出哪些帧获取了哪些锁(ReentrantLock在Java6之后也支持)
• 可以检测和识别反生死锁的线程

当使用某些内置锁不能满足的高级功能时，比如：可定时的，可轮询的，可中断的锁，公平队列，以及非结构的锁时。则需要考虑使用ReentrantLock。

公平锁和非公平锁

公平锁就是说每个请求锁的线程按照先到先得的顺序获得锁，后到的线程在它前一个线程没有释放锁时是不能获取锁的，没有获取的锁的线程就被放到队列里挂起。非公平锁就是说每个请求锁的线程，如果发现该锁没有被占用就去请求锁，而不管其前面有没有线程在等待，这将提升吞吐量。由于线程的挂起和重新唤醒，线程的调度会带来很大的性能损耗，所以，如果请求锁的平均时间间隔非常短，那么最好使用非公平锁。反之，如果持有锁的时间较长，或者请求锁的时间间隔较长，那么性能的瓶颈就不在切换线程上了，这时就应该使用公平锁，使用非公平锁”插队”的方式所带来吞吐量的提升将会是非常微弱的。内置锁和ReentrantLock都没有提供确定的公平性保证，因为一般来说实现总体的公平性已经足够了。

条件队列

首先为什么会出现条件队列呢？我们知道要保证某个多线程的方法被调用成功可以使用线程休眠的方式，但是这种方式会有问题：如果休眠的时间过短，那么会导致CPU的资源消耗过高，如果休眠的时间很长，这时如果其它某个线程修改了判断条件，这时休眠的线程不能及时响应，只有在休眠之后才会响应。比如：

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

@ThreadSafe
public class SleepyBoundedBuffer<V> extends BaseBoundedBuffer<V> {
public SleepyBoundedBuffer(int size) {
    super(size);
}
public void put(V v) throws InterruptedException {
    while (true) {
    synchronized (this) {
        if (!isFull()) {
            doPut(v);
            return;
        }
    }
     Thread.sleep( SLEEP_GRANULARITY );
  }
}
public V take() throws InterruptedException {
    while (true) {
    synchronized (this) {
        if (!isEmpty())
            return doTake();
    }
     Thread.sleep( SLEEP_GRANULARITY ); }
  }
 }

使用条件队列就可以解决这种问题：条件队列就是说在条件不满足时候线程休眠(调用wait方法)，当条件满足的时候线程会收到通知并且被唤醒(调用notify方法)，这样就不会产生多余的开销。

调用wait方法之后会发生以下事情：

1. 释放锁
2. 阻塞当前线程并等待直到超时
3. 线程被终端或者被一个通知唤醒
4. 唤醒后，wait在返回前还要重新获取锁

在步骤3和步骤4之间可能有另外一个线程获取了锁，并且改变了对象的标志，这个时候其实条件已经变成假的了。或者这个被唤醒的原因并不是条件变成了真，而是其它的线程的某个条件变成了真，那个线程调用了notify或者notifyAll方法。所以说即使线程被notify唤醒了，并不一定是因为条件满足了，所以在唤醒之后还要继续检查条件，这时要将wati放在一个。如下所示：

1
2
3
4
5
6
7
8

void stateDependentMethod() throws InterruptedException {
// condition predicate must be guarded by lock
synchronized(lock) {
while (!conditionPredicate()){
    lock.wait();
    // object is now in desired state
  }
}

并发的目的就是提高系统的性能和响应速度，但是这些都要建立在安全性的基础之上的，也就是说先要保证系统能够正常的运行，满足现有的业务需求，然后再考虑性能。并且在提升性能的同时往往会增加系统的复杂性，因为很多性能的优化需要牺牲掉代码的可理解性和面向对象的原则（同时可能会出现活跃性的问题），增加系统的维护成本，并且有时不会增加系统的性能反而会降低系统的性能。

多线程带来的开销

多线程的引入会造成一些额外的开销，比如：线程的创建和销毁，线程的调度，上下文的切换，线程之间的协调（例如加锁，触发信号以及内存同步）。如果这些性能开销大于吞吐量，响应性所带来的性能提升那么就会得不偿失。

可伸缩性

什么是可伸缩性？可伸缩性指的是通过增加计算机的资源（例如CPU，内存，存储容量或IO带宽），程序的吞吐量或者处理能力能相应的增加。但是这种伸缩性往往是有极限的，比如下面提到的Amdahl定律。

Amdahl定律

增加CPU的个数也不能一直提高性能。Amdahl定律就指明了这一点：

在这个公式中：F表示串行执行的部分占所有部分的比重，N代处理器的个数，最后的结果代表和单一处理器时速度的比例。我们假设两个极限：

• 在处理器个数等于一时，其数值是1，也就是说它的速度没有提升。
• 在处理器个数为正无穷的时候，其数值为1/F。

所以只提高处理器的个数是不不能一直提高执行速度的。我们来举个例子：

放假了班主任给小明同学布置了两份作业：

一、9张英语作业：将英语单词第一单元抄写九遍
二、数学第二单元的课后习题做完

假设做数学习题所用的时间是1小时，写英语单词的时间为每单元1小时，所以说如果有小明一个人来做需要10个小时才能完成。小明很贪玩，到了周日晚上才发现自己作业没有写，小明急了，于是就找同学帮他写英语单词，因为英语单词是抄写9份，所以他找了9个小伙伴给他抄，他自己做数学习题（假设数学题不能多个人来做），这样本来是个小时完成的任务，小明最后用了2小时完成了，按照Amdahl定律，其F是0.1，N是10，所以最后的数值是5.26倍。然后我们假设小明有无数个小伙伴都来帮他抄写英语单词，那么最后他需要的时间就接近于1小时，做以按照Amdahl定律，其F实0.1，N是正无穷，所以最后数值是10，也就是说他的速度是原来的10倍。也就是说无论他找多少个小伙伴都不能突破一小时的时间，因为这一小时只能是串行执行的，不能由其他的处理器来协助完成。

然而要能够使用Amdahl定律需要首先估算出串行执行的部分所占的比例。
同时如果增加了处理器的个数，那么每个处理器的利用率都会下降，其中串行所占比例越重的系统，其利用率下降的越厉害。

内存的同步

在使用synchronized和volatile以提供可见性的同时也引入了需要内存同步的问题，因为其使用了内存栅栏（Memory Barrier），使用内存栅栏是可以刷新缓存，使得缓存无效的。某个线程的同步会影响到其它线程的性能，因为同不会增加内存总线上的通信量，总线的带宽是有限的，并且所有处理器都共享这个带宽。但是现在的JVM会对代码做相应的优化，比如下面两段代码：

1
2
3

synchronized (new Object()) {
           // do something
}

这里永远不会有任何两个线程会去竞争这个锁的，因为每次进入这个方法都会新建一把锁。

1
2
3
4
5
6
7

public String getStoogeNames() {
List<String> stooges = new Vector<String>();
stooges.add("Moe");
stooges.add("Larry");
stooges.add("Curly");
return stooges.toString();
}

这里使用Vector可能会进行四次获取锁和释放锁的操作，但是由于这个stooges是一个局部变量，局部变量是属于线程栈的，每个线程中的不一样，所以没有必要加锁。在这两种情况下，如果编译器够智能，就会进行优化从而去掉锁。并且如果编译器没有进行逸出分析，那么也可能进行锁的粒度粗化。也就是说将原来需要加四次锁的地方改为加一次锁。也就是说再非竞争同步的时候，我们就不必担心，JVM已经帮我们做了优化，我们需要关心的就是可能引发竞争的地方。

在并发程序中，对可伸缩性的最主要威胁就是独占方式的资源锁。

锁分段和减少锁的粒度

锁分段的意思是有一个数据集合A,B,C,D,那么线程T1和线程T2一般情况不会同时访问A，而是访问不同的数据，所以在T1和T2访问不同的数据时就是没有必要加锁的，这时可以根据数据集合的量配置若干个锁，比如ConcurrentHashMap中使用的是16个锁来增大吞吐量。而减少锁的粒度是如果之前很多个资源都用同一个锁，并且各个资源之间没有相互的依赖，那么可以将原来的一个锁变为多个锁。锁分段往往将锁放入Collection中，而减少锁的粒度往往是声明若干个锁。其实锁分段也是一种减少锁粒度的方式。

不能滥用对象池

有时候某个对象会重复的使用，我们为了不重新new对象（事实上Java的分配操作要比C语言的malloc的调用速度还要快）以及垃圾回收带来的开销，常常会建一个池子将已经创建的对象保存进池子以备后用。但是这样做需要考虑以下几点：对象池的大小很重要，如果对象池很小，那么将不会起到相应的作用；如果对象池很大，那么将会占用很多内存资源，这会对垃圾回收器带来压力。如果用在多线程，那么会造成更加严重的性能问题，因为如果不用线程池，那么每个新建的对象就会在线程本地的内存块中。如果使用多线程，那么情况会更加糟糕，因为需要协调每个线程之间的调用，在协调的过程中可能导致某个线程的死锁。并且多个线程之间的同步，如果使用锁，那么及时没有竞争，只是加锁和解锁所带来的性能损耗要比new对象带来的损耗大得多。这看似一个性能优化的技术点，但实际上会导致可伸缩性的问题。

同步的开销要比new对象的开销少的得多。

上下文切换

上下文切换是什么？
锁竞争的过程中会发生上下文切换，越多的上下文切换将会造成越低的吞吐量。如果某个执行IO操作的线程被阻塞了，同时这个线程还持有一把锁，那么如果有越来越多的线程来请求这个锁，也将被阻塞而挂起，这就会增加上下文切换的次数。所以要尽量减少持有锁的时间来减少上下文切换。

参考资料：

1. 线程上下文切换和进程上下文

2. 上下文切换的定义

在多线程开发中，我们往往为了安全性而去加锁，如果锁过多，就可能出现顺序死锁。如果不适用锁，使用信号量和线程池来限制对资源的访问，那么又可能出现资源死锁。那么究竟怎样判断死锁？死锁的种类都有哪些？怎样避免死锁呢?

死锁

我们如果把每个线程都想像成有向图中的一个点，如果线程A等待线程B所占用的资源，那么就从A向B画一条直线，如果最终这个图形成了一个环形，那么就出现了资源的相互依赖，就造成了死锁。

死锁之后的处理形式

死锁之后该怎么处理分为两种方式，第一种方式就是什么都不做不了，应用程序将到此结束（也可能是某个子系统停止或者性能降低），直到重新启动，才会解除本次死锁。第二种方式就是干涉死锁。比如数据库操作在两个事务之间出现了死锁，那么数据库服务器会选择一个牺牲者并且放弃这个事务。作为牺牲者的事务将放弃它的所有资源，从而使其它事务继续进行。让后等待其它任务执行完成之后再去执行这个被牺牲了的任务。

顺序死锁

如果有left和right两把锁，同时有A线程和B线程去访问，如果按照下面的顺序就可能造成死锁。

线程A持有了left锁，再获取了right锁的时候才可以进行下一步的执行，并且只有获得了right锁才可以释放掉left锁。线程B已经获取了right锁，在获取了left锁的时候才可以进行下一步的执行，也只有获取了right锁才可能释放掉right锁。所以就造成了最后的死锁。这个死锁引起的原因就是锁的顺序不一致，也就是说在使用锁进行同步的过程中如果有两把锁，那么锁的顺序需要保持一致，否则就可能造成死锁。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class LeftRightDeadLock {

    private final Object left = new Object();
    private final Object right = new Object();

    public void leftRight() {
        synchronized(left) {
            synchronized(right) {
                doSomething();
            }

        }
    }

    public void rightLeft() {
        synchronized(right) {
            synchronized(left) {
                doSomethingElse();
            }
        }
    }
}

动态的锁顺序死锁

有些时候我们没有很明确的在两个不同的方法中使用两把锁，但是仍然可能造成死锁，这种死锁往往不容易被发现，比如我们要给将账户A的钱转给账户B，那么我们可以使用下面的方法来确保转账的原子性，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public void transferMoney(Account fromAccount, Account toAccount,
DollarAmount amount) throws InsufficientFundsException {
synchronized (fromAccount) {
    synchronized (toAccount) {
if (fromAccount.getBalance().compareTo(amount) < 0) {
    throw new InsufficientFundsException();
    }
else {
    fromAccount.debit(amount); toAccount.credit(amount);
        }
     }
  }
}

这个死锁的原因就是可能调用方在两个线程中使用的参数顺序可能相反，这就造成死锁，因为我们不能确定调用方是怎么调用我们写的接口的。比如下面的调用：

1
2

A: transferMoney(myAccount, yourAccount,10);
B: transferMoney(yourAccount, myAccount,20);

这时就造成了死锁，并且这种死锁是在一般情况下是不会发生的，这就造成了难以排查的错误。这时该如何去做呢？我们的目的是想让外界两个参数的改变不会影响到内部锁的顺序，所以，我们可以拿两个入参的identityHashCode去作为判断条件，根据hash值的大小来改变加锁的顺序。当然，这里面可能有哈希碰撞的情况（这种情况发生的几率是非常低的），如果有这种情况的出现，那么就给这两个同步操作外部再加一个锁，这样来确保这个操作的原子性，就不会有死锁的情况了。这里面如果加锁的两个对象有唯一的键值，那么就可以直接用其键值，这样就不必再使用额外的锁了。

协作对象之间发生的死锁

比如下面的Taxi和Dispatcher对象都使用了锁，并且它们之前是相互协作的。

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

class Taxi {
@GuardedBy("this") private Point location, destination; private final Dispatcher dispatcher;
public Taxi(Dispatcher dispatcher) {
    this.dispatcher = dispatcher;
    }
public synchronized Point getLocation() {
    return location;
   }
public synchronized void setLocation(Point location) {
    this.location = location;
if (location.equals(destination)) {
    dispatcher .notifyAvailable (this );
 }

   }
}
class Dispatcher {
@GuardedBy("this") private final Set<Taxi> taxis; @GuardedBy("this") private final Set<Taxi> availableTaxis;
public Dispatcher() {
       taxis = new HashSet<Taxi>(); availableTaxis = new HashSet<Taxi>();
    }
public synchronized void notifyAvailable(Taxi taxi) {
        availableTaxis .add(taxi);
    }
public synchronized Image getImage() {
    Image image = new Image();
    for (Taxi t : taxis) {
     image.drawMarker(t.getLocation()); return image;
  }

   }
}

在这里面setLocation方法需要先获取Taxi的锁，再获取Dispatcher的锁。而getImage方法需要先获取Dispatcher的锁，然后再获取Taxi的锁，这样就可能造成上文中所说的顺序锁的问题。并且这种锁是更加难以排查的。所以最好不要使用synchronize(管程)。

在持有锁的过程中调用某个外部方法，那么将可能会出现活跃性的问题。

丢失信号死锁

多线程访问某个资源，在有条件谓词作为前置条件，如果条件为假，那么我们会调用wait方法将线程阻塞。如果某个线程将条件变为了真，并且这个wait的线程没有收到这个信号。那么原来wait的线程将会永远等待下去，进而导致死锁。也就是说，线程A通知了一个条件队列，而线程B随后进入这个条件队列，但是线程B将被阻塞而不能执行，因为其需要等待另外一个通知的到来。

开放调用

之所以出现上述协作对象之间发生的死锁，是因为在调用另外一个对象的方法的过程中，已经持有了一把锁。这种调用称作不开放，所谓的开放调用就是指：在调用某个方法的时候不需要持有锁。通常来说开放调用要比非开放调用更加安全，更加不容易产生死锁，所以我们要尽可能地使用开放调用。我们可以使用开放调用的方法来解决上述遇到的问题：

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

@ThreadSafe
class Taxi {
@GuardedBy("this")
private Point location, destination; private final Dispatcher dispatcher;
public synchronized Point getLocation() {
        return location;
    }
public void setLocation(Point location) {
    boolean reachedDestination; synchronized (this) {
    }
}
    this.location = location;
    reachedDestination = location.equals(destination);
}
if (reachedDestination) {
    dispatcher .notifyAvailable (this );
}

@ThreadSafe
class Dispatcher {
@GuardedBy("this") private final Set<Taxi> taxis;
@GuardedBy("this") private final Set<Taxi> availableTaxis;
public synchronized void notifyAvailable(Taxi taxi) {
availableTaxis .add(taxi); }
public Image getImage() {
    Set<Taxi> copy;
  }
}
synchronized (this) {
copy = new HashSet<Taxi>(taxis);
}
Image image = new Image(); for (Taxi t : copy)
image.drawMarker(t.getLocation()); return image;

这样就可以将多个锁区分开来，从而在多个对象调用的时候就不会死锁了。

资源死锁

资源死锁的起因也是由于访问资源的原子性和访问资源的顺序所造成的互相牵制。比如：线程A已经建立了和数据库D1的链接，正在尝试连接数据库D2；与此同时，线程B已经建立了和数据库D2的连接，正在尝试连接数据库D1。这时就造成了资源死锁。（当然这和数据库同时连接的个数，以及资源的大小有关。资源越大，连接的个数越多，那么出现死锁的可能性就越少。）
在资源死锁中，还有一种线程饥饿死锁的情况，比如下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public class ThreadDeadlock {
ExecutorService exec = Executors.newSingleThreadExecutor();
public class RenderPageTask implements Callable<String> {
    public String call() throws Exception {
        Future<String> header, footer;
        header = exec.submit(new LoadFileTask("header.html"));
        footer = exec.submit(new LoadFileTask("footer.html"));
        String page = renderBody();
        // Will deadlock -- task waiting for result of subtask
        return header.get() + page + footer.get();
   }
 }
}

这会出现死锁，因为header.get()和fotter.get()是阻塞的，它将会等待exec执行完毕，而exec想要执行必须要等到header.get() + page + footer.get();执行完毕，这样就造成了线程饥饿死锁。(RenderPageTask是任务1，header.get() + page + footer.get()是任务2)。

饥饿

饥饿就是指某个线程始终不能获取其所需要的资源，导致它不能继续执行，引起饥饿的最常见资源就是CPU的时钟周期。Java中提供了10中线程的优先级，然而对应到操作系统中，可能某些优先级会重合（因为操作系统可能没有这么多的优先级）。并且设置线程的优先级可能不会起到明显的效果，反而可能因为优先级翻转而造成死锁，所以我们尽量不要去改动线程的优先级。但是这种情况也不是绝对的，比如有一个CPU密集的后台任务在执行，那么这个任务很可能会和主线程去抢占CPU资源，从而导致主线程响应性降低，为了解决这个问题，我们可以将后台线程的优先级降低，从而提高主线程的响应性。

尽量避免使用线程优先级，因为这会增加平台依赖性，并且可能会导致活跃性问题。在大多数并发应用程序中，都应该使用默认的线程优先级。

活锁

活锁是指没有发生死锁，但是程序一直在重试，并且重试一直错误，导致程序不能正常往下执行。（产生这种情况的原因是对错误的估计不对：本来是不能解决的错误，却以为可以通过重试解决）。
同时，多个线程之间的协作也可能造成死锁，因为可能两个协作的线程都对彼此进行响应，响应完之后使得任何一个线程都不能继续执行，解决这种活锁的问题可以通过在重试机制中引入随机性，也就是说某个重试完之后，另一个线程在随机的时间段之后再进行重试，从而避免了和之前线程的碰撞。

Java结构化并发应用程序

线程池和队列的关系

线程池和队列之间的关系是很紧密的。队列是用来放任务的，它有并行和串行之分。其中并行队列中的任务可以并发的执行；串行队列中的任务只能按照顺序一个一个执行，正是因为这个原因，串行队列也可以实现线程安全，也可以作为锁来用。而线程池就是很多的线程的容器，这些线程负责从队列中取出任务执行任务并且返回线程池以等待下个任务的到来。
在Java中通常会有如下几种创建线程池的方法：

1
2
3
4
5
6

public static ExecutorService newFixedThreadPool(int nThreads) // 创建的线程数量是固定的
public static ExecutorService newWorkStealingPool(int parallelism) // 利用所有可用的处理器资源创建一个'工作密取'的线程池
public static ExecutorService newSingleThreadExecutor() // 创建一个单线程的线程池，放入线程池中的任务顺序执行
public static ExecutorService newCachedThreadPool() // 创建一个缓存的线程池，如果之前有可用的线程就用，如果没有就重新创建，如果执行的任务量小并且多的时候用这个线程池会提高性能。如果一个线程在60s之内没有被使用，那么这个线程将会被中断并且被移除线程池。所以说如果这个线程池如果一直是idel状态的时候，那么它不会消耗任何的资源
public static ScheduledExecutorService newScheduledExecutor() // 创建一个具有定时功能的线程池
//...

在IOS开发中GCD就是典型的例子：

1

dispatch_async(dispatch_queue_t queue, dispatch_block_t block);

这个函数调用时候是这样子的：

1
2
3
4
5
6

dispatch_queue_t concruntQueue = dispatch_queue_create("come.mike.fighting0.com", DISPATCH_QUEUE_CONCURRENT);
    dispatch_async(concruntQueue, ^{

        NSLog(@"我正在做一项耗时的任务");

    });

这段代码就是说吧一个耗时的任务放到了一个并行的队列中，然后调用dispatch_async，在调用这个方法时系统会自动的给我们创建好一个线程池并且从其中取出一个线程，来执行我们的任务。这样，我们就不用自己再去创建并管理线程了，避免了不必要的错误并且避免了频繁创建线程所带来的开销，同时避免了任务到来的时候再去创建线程从而造成一定程度的响应延迟。

Executor的生命周期

Executor的创建在上文中已经说明了，下面说下它的关闭。Executor的终止方式有以下两种：

• 缓慢关闭，让已经执行的任务执行完毕，然后不再接受正在等待的任务或者新来的其它任务(shutdown方法)
• 暴力关闭，直接关闭线程池，不管已经执行的任务(shutdownNow方法)

Timer和SecheduledThreadPoolExecutor的对比

因为Timer的调度机制是基于绝对时间而不是相对时间的，因此任务的执行对系统的时钟很敏感，而SecheduledThreadPoolExecutor是基于相对时间调度的，所以更加准确。

• Timer会将所有的定时任务都放到一个线程中去执行，所以如果某个任务的执行时间长于所设定的时间间隔那么这个Timer就会不准确。而线程池就能很好的解决这个问题，因为它是在多个线程中执行不同的任务的，所以各个任务之间彼此没有影响。
• TimerTask如果抛出一个异常，那么Timer不会处理它，反而会终止所有的任务，包括正在执行的任务和将要执行的任务。在这之后也没有可以恢复Timer的方式。

那么问题来了，在Java中如果要实现自己的调度任务不使用Timer，该使用什么呢？应该使用DelayQueue，它内部的每个对象都有一个延迟时间的方法。

任务和线程处理中断的方式

虽然每个任务都在一个线程中执行，但是这个线程并不被这个任务所拥有。拥有这个线程和管理这个线程的主人是线程池，所以在遇到中断的时候，通常会将其抛出，然后让上层的代码来处理中断。举个例子：你在一个朋友家玩耍，这时忽然来了一个收租金的人大吵大闹要交房租（中断），这时你不应该处理，而是应该保留这个现场，并且把问题抛给你的朋友，因为这是他的家。这也就是什么很多阻塞库框架都会在遇到中断的时候抛出来InterruptedException，以便上层代码进行处理（尽快的退出，并且将中断尽快的传递给上层也是最温和的响应策略）。也就是说任务本身对中断不应该做任何的处理，不应该对中断策略做任何的假想，除非这个框架的中断处理策略已经定了，不需要再将中断抛给上层代码了。除了将中断传递给上层的调用者之外，任务还需要保存中断的状态，以备后续上层代码的处理，保存状态的方式为：

1

Thread.currentThread().interrupt();

调用之后就会保持线程的中断状态，恢复中断状态的目的就是让调用栈中更高层的代码看到引发了一个中断，并且这个线程的状态是interrupted的。

1
2
3
4
5
6
7
8
9
10
11
12
13

Thread myThread =  new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    throw  new InterruptedException();
                } catch (Exception e) {
                    Thread.currentThread().interrupt();
                    System.out.println("thread status:" + Thread.currentThread().isInterrupted());
                    e.printStackTrace();
                }
            }
        });
myThread.run();

这段代码如果不加Thread.currentThread().interrupt();，那么下面的Thread.currentThread().isInterrupted()就将会返回false。如果没有确定上层代码是否要处理异常，那么切记不能catch中这个中止的异常而不做任何的事情。

Executor的作用

既然已经有了线程，那么Executor的作用是什么呢？它是将任务的提交和任务的执行分离开了。也就是说把复杂的业务过程分割开了，这样就更加便于我们修改执行策略。

多个线程安全类的方法在一起一定是线程安全的吗？

尽管线程安全类的每个方法都是原子的，但是当很多原子操作合并为一个复合操作的时候，需要额外加锁，否则就会出现竞态条件（race condition）造成线程不安全。但是这里额外的加锁可能会导致性能损耗并且可能引起死锁。如：

1
2

if (!vector.contains(element))
    vector.add(element);

这里contains方法和add方法都是线程安全的，但是综合起来就是非线程安全的了。

方法的局部变量无需加锁

某个线程进入一个方法就会创建一个栈，这个栈中存储了某个局部变量，这个局部变量是每个线程所独有，不是共享的，他们之间互不影响，没有必要加锁。

加锁时所发生的事情

• 操作互斥，很多个线程不能同时对一个代码块进行操作
• 加锁之后可以保证变量的可见性
• 抑制了编译器优化，导致指令不会被重排序
• 使用内存栅栏（Memory Barrier）从而使缓存无效
• 由于锁竞争而导致阻塞时，持有锁的线程在释放锁的时候需要告诉操作系统，这个锁可以用了，进而操作系统会唤醒其它被挂起的线程

锁的粒度该怎样控制

代码块加锁的粒度应该越小越好，但是如果代码块中加锁的粒度很小（代码中相互竞争的临界资源没有相互的依赖性，可以将每种资源加一把锁），频繁的加锁和开锁也会造成性能的开销，降低CPU的利用率，所以并不是加锁越多越好。同时加锁也会造成代码的复杂性，这就是简单性和性能之间存在的互相制约。当我们实现某个同步策略时，一定不要盲目的为了性能而牺牲简单性。

可见性和原子性

volatile保证了属性的可见性，但是不能保证某个操作的原子性。如下所示：

1
2
3
4
5

volatile long number;
//...
public void addMethod() {
 number++;
}

这里的number就是可见的，但是addMethod这个方法不是线程安全的，也就是说number++这个操作不是原子操作，因为它只是保证了，线程A对number的操作对线程B是可见的，但是不能保证在线程A对number操作的时候，线程B也可以对number进行操作。比如线程A和B同时读取了number的数值，发现它是12，这时线程A和线程B

当执行时间较长的计算或者可能无法快速完成的操作时一定不要加锁，比如：网络IO或者控制台IO。

如何正确地发布对象

这里的发布指的是将某个类的属性值公开。这里如果没有正确的公开，那么就会造成线程不安全。比如：

1
2
3
4
5
6
7
8

   public class Holder {
      private int n;
      public Holder (int n ) {this.n = n;}
      public void assertSanity() {
       if(n != n)
       throw new AssertionError("This statement is false.");
      }
   }

这里如果在线程A中创建对象，这时线程B调用这个对象的assertSanity方法，那么这个方法就可能会触发断言，也就是说在对象的创建过程中，它的属性n的值可能还没有确定，this.n = n;。这个代码还没有被执行，而在执行n != n的过程中执行了。

对象的可见性

对象的引用对另外的线程可见，并不意味着对象的状态对另外的线程可见。
As we’ve seen, that an object reference becomes visible to another thread does not necessarily mean that the state of that object is visible to the consuming thread。

不可变对象的线程安全性

不可变对象在正确的初始化之后是线程安全的，所以发布的时候就不必使用锁机制。但是如果某个引用是不可见的，并且引用的对象是可变的，那么在这个不可变的引用在发布的时候也需要加锁。

哪些操作必须是原子的？

如果有两个变量，其中一个变量值的更改会影响另外一个变量的，那么如果要同时改变这两个变量，那么它们需要是原子的，否则其中一个变量改变，而另外的一个变量没有变，那么从这个没有变化的变量中取到的值就有可能是过期的值。比如：

• 我们给每个请求都做一个标记，如果某个请求和上一个请求的标记相同，那么就从缓存去取这个结果。在这里，这个标记和这个结果是一体的，所以对它们两个的操作必须是原子操作，否则就不能保证取出的结果就是正确的。因为有可能标记变了，但是缓存还没有变。
• 我们有一个Range这样的对象，它有一个下界和一个上界，上界要大于下界，所以对上下界的操作就必须保证是原子的，否则如果一个线程改变了下界，这时上界没有跟着变化，就可能会造成下界大于上界的情况。

也就是说：

是规则和限制产生了必须要原子操作的需要，这就是线程安全的需要。

线程安全是有粒度的

某个类不是线程安全的，但是如果封装它的类做了线程安全的处理，那么使用它的时候也就是线程安全的了：

1
2
3
4
5
6
7
8
9
10

public class PersonSet {
   @GuardedBy("this")
   private final Set<Person> mySet = new HashSet<Person>();
   public synchronized void addPerson(Person p) {
        mySet.add(p);
    }
    public synchronized boolean containsPerson(Person p) {
        return mySet.contains(p);
    }
}

如果某个类包含了一个线程安全的类，那么它不一定是线程安全，比如：

两个AtomicLong类型的变量，这两个变量有关联，那么就必须让对这两个变量的操作变为原子化之后才可以是线程安全的，否则仍然不是线程安全的。

给线程安全的类添加线程安全的方法

如果要给线程安全的类添加线程安全的方法，那么最好不要使用类扩展，因为如果使用类扩展，那么原来类的线程安全策略做了改动，那么被扩展的类就失效了，比如改了线程安全所用的锁，有些时候这些错误还很难被发现。同时需要特别注意多个线程对线程安全类的同时操作，例如：

1
2
3
4
5
6
7
8

public static Object getLast(Vector list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex);
}
public static void deleteLast(Vector list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
}

上面两个方法都是针对于线程安全的Vector所做的，那么它们是线程安全的吗？答案是否定的。
比如在getLast方法中，如果线程A在执行完int lastIndex = list.size() - 1;之后恰巧有线程B也对这个Vector做了deleteLast操作，那么就可能引起list.get越界的情况。也就是说，所有针对同一个Vector的操作都应该是原子的。所以正确的做法应该是这样子的：

1
2
3
4
5
6
7
8
9
10
11

public static Object getLast(Vector list) {
synchronized (list) {
int lastIndex = list.size() - 1;
return list.get(lastIndex); }
}
public static void deleteLast(Vector list) {
synchronized (list) {
int lastIndex = list.size() - 1;
list.remove(lastIndex);
          }
}

这样通过给Vector加锁就确保了这些方法的操作是线程安全的。下面还有个很类似的问题：

1
2
3

for (int i = 0; i < vector.size(); i++) {
    doSomething(vector.get(i));
}

这里也是非线程安全的，因为不能保证在执行vector.size()和vector.get(i)之间不会有另外一个线程对vector做其它的操作。这个问题的解决思路和上面是一样的：

1
2
3
4
5

synchronized(vector) {
for (int i = 0; i < vector.size(); i++) {
doSomething(vector.get(i));
     }
}

加锁之后，就可以保证vector.size()和vector.get(i)的操作是原子的，中间不会有其它的线程会对Vector做响应的操作。

某个方法加了同步锁就一定是线程安全的吗？

答案是否定的。因为加锁实现的互斥是基于锁的，多个线程必须使用同一把锁才可以实现互斥。，比如：

1
2
3
4
5
6
7
8

@NotThreadSafe   public class ListHelper<E> {
public List<E> list = Collections.synchronizedList(new ArrayList<E>());
...  public synchronized boolean putIfAbsent(E x) {
boolean absent = !list.contains(x); if(absent)
    list.add(x);
    return absent;
  }
}

这个putIfAbsent中的加锁并不能保证ListHelper的线程安全，因为这个锁是对象锁，锁住的是ListHelper，而并没有锁住真正需要锁的list上。客户端如果有多个线程同时对list做其它的操作，那么就不能保证线程的安全性。这时争取的做法是：

1
2
3
4
5
6
7
8
9
10
11
12
13

@ThreadSafe 
public class ListHelper<E> {
public List<E> list = Collections.synchronizedList(newArrayList<E>()); 
...public boolean putIfAbsent(E x) {
synchronized (list) {
    boolean absent = !list.contains(x);
       if (absent) {
          list.add(x);
         }
      return absent;
    }
  }
}

这样就保证了putIfAbsent的线程安全性。但是这种通过客户端加锁的方法不是很可靠，因为你不能确定客户端做怎样的操作，有时候会造成死锁。

最理想的并发是什么样的？

The best way to implement concurrency is to reduce the interactions and inter-dependencies between your concurrent tasks。实现并发最好的方式就是避免并发任务之间的交互和相互之间的依赖。

容易被忽略的线程安全问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class HiddenIterator {
@GuardedBy("this")
private final Set<Integer> set = new HashSet<Integer>();
public synchronized void add(Integer i) {
    set.add(i);
}
public synchronized void remove(Integer i) {
    set.remove(i);
}
public void addTenThings() {
    Random r = new Random()
    for (int i = 0; i < 10; i++)
    add(r.nextInt());
    System.out.println("DEBUG: added ten elements to " + set);
} }

这里同样是非线程安全的，因为在执行

1

System.out.println("DEBUG: added ten elements to " + set);

的时候，系统会默认调用StringBuilder.append(Object)方法，在这个方法里面会再次调用Object的toString方法，在这个toString方法内部将会调用迭代器方法并且生成相应的字符串（容器的hashCode和equals方法也有相似的问题）。所以这里是非线程安全的，可能会抛出ConcurrentModificationException方法。也就是说如果一个状态和保护这个状态的同步代码之间相隔越远，那么开发人员就越容易忘记在访问这个状态时使用正确的同步。这时如果将HashSet用synchronizedSet来封装一下，那么就不会忘记了。

封装对象的状态有助于维持不变形条件；封装对象的同步机制有助于确保实施同步策略。

ConcurrentHashMap

ConcurrentHashMap的出现就是为了解决同步容器性能差的问题。在一些操作中，比如HashMap.get或者List.contains，可能会包含大量的工作，在执行这些大量工作的时间段内，其它的线程都是被阻塞的，这极大的影响了并发的性能。虽然ConcurrentHashMap和HashMap一样是基于散列的Map，但是它们使用不同的加锁策略来提供更高的并发性和伸缩性，从而使用一种粒度更细的加锁机制来实现更大程度的共享，这种机制成为分段锁（Lock Striping）。

什么是工作密取(work stealing)方法，它有什么优点？

在生产者-消费者模型中所有的消费者有一个共享的工作队列。工作密取的每个消费者都含有一个双端队列。如果一个消费者完成了自己工作队列中的所有问题，那么其它就可以从其它的队列末尾秘密的获取工作。密取的工作模式比传统的消费者-生产者模式具有更好的可伸缩性，因为工作者线程不会在单个共享的任务队列上发生竞争。在大多数情况下他们都只访问自己的双端队列，从而极大地减少了竞争。当工作者线程要访问另外一个工作者线程的队列时它将从队列的末尾获取工作，因此进一步降低了队列的竞争程度。

为什么需要泛型？

在Java1.5版本之前是没有泛型的。这时如果我们要实现一个Array类，它里面可以存储任何的对象，我们该怎样做呢？显然，我们可以通过多态来实现：

1
2
3
4
5

class Array {
void add(Object e);
// ....
Object get(int i);
}

因为Java中的对象都继承自Object，所以就可以往这个Array中添加任何的对象，并且取出任何的对象了。但是这样做会有很大的风险：

• 我们取出的对象都是Object类型的，所以如果要使用这个对象就必须做一次强制转换，因为我们使用Collection框架的频率是很高的，所以这种转换就显得比较麻烦
• 不安全，因为是Object，所以我们可以往里面放任何的对象，比如Animal对象，Plant对象，Plane对象，这样如果我们在调用Array中对象的方法时就可能Crash

第二点对于Java这种追求安全性的语言来说，显然是不可以接受的，所以就出现了泛型。

泛型的基本用法

泛型类

我们可以定义一个泛型的类，具体的方法如下：

1
2
3
4
5

class Pair<T> {
   T first;
   T second;
   // ....
}

这样在我们创建对象的时候就可以使用Pair<Integer> pair = new Pair<Integer>()，这样我们就可以明确的指出这里的Pair中存放的就是Integer类型的对象，其它对象如果要放到Pair中编译器就会报错，这样就在很大程度上增加了安全性。并且在取出的时候也不必再进行一次强制转换了。
如果某个类中有多个泛型，那么这些泛型用,好分割开就好了。public class Pair<T, U> { . . . }。一般我们会用大写字母来表示泛型的元素，在Java框架中E用来表示一个元素，K和V用来表示一个table的key value值。

同样，我们可以定义一个泛型的方法，比如：

1
2
3
4
5

class ArrayAlg {
public static <T> T getMiddle(T... a) {
  return a[a.length / 2];

}

注意这个泛型的方法并不是在泛型类中的，而是在普通的Java类中的，当然，它也可以被定义在泛型类中。

调用的时候不需要进行强制转换：

1
2

String middle = ArrayAlg.getMiddle("John", "Q.", "Public");
double middle = ArrayAlg.getMiddle(3.14, 1729, 0);

在第二个例子中我们传入的参数是原始数据类型，这时编译器会给我们自动打包，在从类中取出的时候编译器会给我们自动的拆包。

泛型的界

有时候我们需要对输入的参数做一些限制，比如说要好处两个数值中较小的一个，那么我们就要求进入方法的参数是实现了Comparable接口的，或者是某个类的子类，这样我们就可以做如下的限制，来让泛型有界：

1

public static <T extends Comparable> T min(T[] a) . . .

如果某个类型没有实现Comparable接口的话，让它作为参数会产生一个编译期的警告，在运行时就会Crash。如果一个泛型需要限制很多个接口的话，那么很多个接口之间用,隔开（但是这其中只能有一个是对类的限制，并且如果有对类的限制，那么这个限制一定要写在第一个的位置）。

泛型和JVM

在Java虚拟机中是没有任何泛型类的，所有的对象都是普通的Java类。其实泛型只是一种给程序员的一个假象，用来方便程序员写出安全语言的一种手段，在编译完之后编译器会对泛型实行一次擦除的过程。也就是说，当你定义一个泛型的时候，系统会自动给你创建一个原始类型给你。原始类型变量的名字和泛型时候取的名字是一样的，但是泛型类型的参数类型被移除了。这些类型被移除之后，取而代之的是它们的边界类型（如果没有边界，那么它的边界就是Object，这也是为了和Java之前的版本做兼容。这也就是上文提到的，为什么对于原始数据类型有一个装包和拆包的过程）。比如，如果你创建上文中的Pair<T>，在编译之后Pair类就成了下面的样子：

1
2
3
4
5
6
7
8
9

public class Pair {
private Object first; private Object second;
public Pair(Object first, Object second) {
this.first = first;
this.second = second; }
public Object getFirst() { return first; }
public Object getSecond() { return second; }
public void setFirst(Object newValue) { first = newValue; }
public void setSecond(Object newValue) { second = newValue; } }

这其实和没有泛型时候创建的类是一样的了。

这里有一个特殊情况，如果有两个限制，那么会以第一个限制为准：

1
2
3
4
5
6
7
8

public class Interval<T extends Comparable & Serializable> implements Serializable {
private T lower;
private T upper;
...
public Interval(T first, T second) {
if (first.compareTo(second) <= 0) { lower = first; upper = second; }
else { lower = second; upper = first; } }
}

这时Interval的基本类型就是：

1
2
3
4
5
6

public class Interval implements Serializable {
private Comparable lower;
private Comparable upper;
...
public Interval(Comparable first, Comparable second) { . . . }
}

这种情况下，如果第一种类型要转化为第二种类型的时候编译器会自动的加上强制转换。

例如：

1
2

Pair<Employee> buddies = . . .;
Employee buddy = buddies.getFirst();

因为在编译期进行了类型擦除，所以在调用buddies.getFirst()的时候返回的是一个Object，所以编译器就自动添加了一层强制转换。

泛型方法的翻译

上文提到过泛型会被编译器在编译的阶段进行擦除，并且将边界替换为泛型的类型。这种泛型的擦除同时也带来了复杂性，比如下面的例子：

1
2
3
4
5
6

class DateInterval extends Pair<LocalDate> {
public void setSecond(LocalDate second) {
if (second.compareTo(getFirst()) >= 0) super.setSecond(second);
}
//...
}

因为我们要保证Pair中的第二个元素要始终不小于第一个元素，所以我们就继承了Pair，并且重写了其setSecond方法，这样经过泛型的擦除，最后将会变为：

1
2
3
4
5

class DateInterval extends Pair // after erasure 
{
public void setSecond(LocalDate second) { . . . }
//...
}

而原来的Pair类中的setSecond方法是这样子的：

1

public void setSecond(Object second)

很显然，这是两个不同的方法，然而我们不想让它们是不同的方法，我们想让它走我们新写的方法，因为我们在这里面新增加了我们自己的业务逻辑，比如下面的方法：

1
2

DateInterval interval = new DateInterval(. . .); Pair<LocalDate> pair = interval; // OK--assignment to superclass
pair.setSecond(aDate);

在这里很显然，我们想走我们新的方法，这时编译器其实会在我们的参数为Object的方法里面重新调用我们新写的方法：

1
2
3

public void setSecond(Object second) {
    setSecond((Date) second);
    }

也就是这种转换让系统调用到了我们新写的方法。这样就可以始终调用到我们自己的方法里面了。

Java泛型中需要注意的问题

不能使用基本数据类型作为泛型类的初始化参数

因为Java泛型在编译完之后就被擦除了，泛型类的属性都会变成Object类型，所以就不能传入基本数据类型作为参数，必须使用与基本数据类型所对应的Java类。还好Java中只有八中类型的基本数据类型。

Runtime类型检查不起作用

1
2
3
4
5
6
7
8

if (stringPair instanceof Pair<String>){

    //....
}
if (stringPair instanceof Pair<T>){
    //...

}

上面的两种运行时的类型检查会报错，因为在编译完之后Pair<String>就不存在了，Pair就变成了属性为String类型的类，所以这种判断错误的，也不能通过编译。但是如果使用泛型类创建了一个对象，然后再判断对象的类型，那么就是可行的。比如：

1
2
3
4
5
6

Pair<String> stringPair = new Pair<>();
Pair<Double> doublePair = new Pair<>();
if (stringPair.getClass() == doublePair.getClass()){

    System.out.println("StringPair and DoublePair is equal");
}

这时是可以判断成功的，他们都是一个Pair类，只不过这个类属性的类型不一样。

不能使用参数类型来创建Array

泛型引入就是为了增加语言的安全性，如果没有泛型，那么对于Collection框架，在进行类型转化的时候很容易出现java.lang.ClassCastException这种类型的异常。泛型在设计的时候有一条原则：

如果一段代码在编译时没有提出“[unchecked] 未经检查的转换”警告，则程序在运行时不会引发ClasscastException异常

所以，如果

1
2

Pair<String>[] p=new Pair<String>[10]; //1 这段代码实际是不能通过编译的
Object[] objs=p; //2

这里，如果第一行的代码被允许，那么根据数组的特性，第二行的代码也是被允许的，并且不会有警告。这样一来我们就可以给objs数组里面添加任意的对象了，并且不会有任何警告，这显然是与泛型的设计原则相违背的。如果这时非要使用数组来存储泛型，那么可以使用ArrayList：

1

ArrayList<Pair<String>> myArrayList = new ArrayList<>();

为什么ArrayList可以呢？因为将Pair<String>类型的ArrayList转换为Object类型的ArrayList在编译期就会报错，这就保证了安全性。

可变参数警告

如果一个方法是可变参数的，并且其类型是泛型，那么Java虚拟机就不得不创建一个泛型数组，这与上一条约定是矛盾的，但这时JVM会放松对泛型的限制，只不过会抛出一个警告uncheck的警告：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private static void testFour(){

      Collection<Pair<String>> table = null;
      Pair<String> pair1 = new Pair<>();
      Pair<String> pair2 = new Pair<>();
      addAll(table,pair1,pair2);
  }

  private static <T> void addAll(Collection<T> collection, T... ts){

      for(T t:ts) {
          collection.add(t);
      }
  }

这时会抛出一个Unchecked generics array creation for varargs parameters 这个警告，这时有两种解决方案。首先可以再addAll方法的上面加上@SafeVarargs的注解或者在调用方testFour的上面加上@SuppressWarnings('unchecked')注解。

不能初始化泛型变量

也就是说在泛型类中，如果一个变量是泛型的，那么不能直接对其进行初始化，比如在构造方法中：

1
2
3
4
5

public Pair() {

    first = new T();
    second = new T();
}

这样的写法是通不过编译的，因为泛型在编译完成之后泛型就被擦除了，就变成了Object，如果真的可以初始化，那么这个Pair类在初始化之后它的first和second的初始值就是Object了。这显然不是我们期望的，所以不能对泛型属性进行实例化。如果真的想在初始化时候就实例化，那么可以提供一个静态初始化方法，然后将属性的类传进来：

1
2
3
4
5
6
7
8

public static <T> Pair<T> makePair(Class<T> cl) {

    try {
        return new Pair<>(cl.newInstance(),cl.newInstance());
    }catch (Exception x) {
        return null;
    }
}

泛型类中的静态环境中不允许使用类型变量

比如下面的泛型类：

1
2
3
4
5
6
7
8
9
10

public class Singleton<T> {

    private static T singleInstance;
    public static T getSingleInstance() {
       if(singleInstance == null) {
           // 初始化singleInstance
       }
        return singleInstance;
    }
}

上面的公用泛型类是不能通过编译的，因为在泛型被擦除之后就变成了Object，那么这个即使这个Singleton可以使static变量，那么也只能创建一个对象，而不能作为单例的公用方法。为什么不能将泛型声明为stati呢？因为泛型是要在对象创建的时候才知道是什么类型的，而对象创建的代码执行先后顺序是：static的部分，然后才是构造函数等等。所以在对象初始化之前static的部分已经执行了，如果你在静态部分引用的泛型，那么毫无疑问虚拟机根本不知道是什么东西，因为这个时候类还没有初始化。

不能抛出或者捕获泛型类对象

泛型类不能extend Throwable，同时不能Catch住泛型，比如：

1
2
3

public class Problem<T> extends Exception {
    //...
    }

以及：

1
2
3
4
5
6
7

public static <T extends Throwable> void doWork(Class<T> t){
    try{
            doWork();
        }catch (T e){
            Logger.global.info(...);
        }
}

这些都是不能通过编译的。之所以要这样设计，我猜测是不利于异常的处理，因为我们在泛型类里已经捕获到了异常，当我们调用泛型类的时候，即使报错了，我们也不知道，因为底层的泛型类已经将错误吞掉了，这样不利于对具体的业务做相应的处理。所以，如果我们把错误抛出来，那么就会好很多，比如下面这种做法就是可行的：

1
2
3
4
5
6
7
8
9
10

public static <T extends Throwable> void doWork(T t) throw T {

    try {

        doWork();
    }catch(Throwable realCause){
      t.initCause(realCause);
      throw t;
    }
}

这样使用泛型类的Client端就可以根据业务的需要做相应的处理了。

泛型擦除之后可能引起冲突

泛型在擦除之后是Object，所以在定义某些泛型方法的时候要注意，在泛型变为Object的时候是不是会引起和原来的方法引起冲突。比如：

1
2
3
4
5
6
7

public class Pair<T> {
    public boolean equals(T value) {

        return first.equals(value) && second.equals(value);
        //...
    }
}

这样在泛型被擦除之后boolean equals(T)就变为了boolean equals(Object)，这个方法其实和Object的equals(Object)方法是一样的，所以就引起了冲突。

其它

在遗留代码中往往有非泛型的类，这时，如果用一个泛型类去接，那么往往会产生一个警告，比如：

1

Dictionary<Integer, Components> labelTable = slider.getLabelTable(); // Warning

这时如果你检查了labelTable中数据的类型，并且确定了其中的key value为Integer和Components，那么就可以使用@SuppressWarnings("unchecked")来忽略这个警告。

1
2

@SuppressWarnings("unchecked")
Dictionary<Integer, Components> labelTable = slider.getLabelTable(); // No warning

当然也可以在外层的方法上添加。

参考内容

1. https://www.zhihu.com/question/20400700
2. http://blog.csdn.net/claram/article/details/51943742
3. http://blog.csdn.net/yj_fq/article/details/44590285
4. Java核心卷1

线性表的定义：零个或者多个具有相同的特性的数据元素的有限序列。注意这里的连续不是指存储地址上的连续而是指存取逻辑上的连续。从线性表的存储结构上可以将线性表分为顺序存储和链式存储两种形式。在实际中常以栈，队列，字符串等特殊的形式来使用。

顺序存储结构

线性表的顺序存储结构是指用一段连续的存储单元依次存储线性表中的元素。它的存储形式如下：

这种顺序的存储结构必须有要有一个长度，并且这个长度是不能改变的。

为什么会这样？因为计算机内存中的存储空间是连续的，要分配一段连续的存储空间，如果没有限制大小，那么很可能其后面的空间被其它对象占用了。举个例子，会议室有100个连续的位置，这时来了A组人来了5个人（一共20个人），做到了0，1，2，3，4这五个位置。过了一段时间之后B组来了20人，他们坐到了10…19这10个位置。然后A组的其它15个人来了，这15个人不能被放到5…9这五个位置上，这样就不满足顺序存储结构的定义了。

查询

这种存储结构的存储位置很容易被计算出来，比如要计算下标为i元素的位置，这时候只需要利用下面的公式即可：
LOC(a_i) = LOC(a₁) + (i - 1) * c

其中c是每个元素所占存储单元的个数。所以根据大O阶记法，这个时间复杂度是O(1)(这种时间复杂度为1的存储结构称为随机存取结构或者直接存取结构)。

插入删除

这种顺序存储结构的插入需要将插入点之后的所有元素都向后移（如果插入点在最后一个元素之后则不需要后移）。所以比较消耗性能，其时间复杂度是O(n)，如果在某个位置同时插入1000个元素，那么它需要循环移动1000次。这种性能消耗是比较大的，Java中的ArrayList在插入大量数据的时候就会有较大的性能消耗。

顺序存储结构的优缺点

从上面的讨论中我们就可以看出来顺序存储结构的优点和缺点。

链式存储结构

为了解决线性存储结构不容易扩展，难以插入和删除的缺点。出现了链式存储的线性表，这种表的每一个元素中都有一个标识用来记录下一个元素地址。这样就不需要在内存中开辟连续的空间。它的存储形式是这样的：

它需要两个存储空间，一个数据域用来存储数据元素的信息，一个指针域用来存贮下个元素的地址，其中的每个元素又叫做结点（Node）。每个线性表都有一个指针指向它，这个指针叫做头指针（这个指针是每个链表所必须的，即使这个链表为空），这个指针指向头结点（如果存在的话），头结点的数据域是空或者可以存储表的长度等附加信息。最后一个结点是的指针域是NULL或者”^”符号。那么为啥要有这个头结点呢?不要头结点可以吗？那为啥链表的结尾不需要特殊处理呢？因为链表结尾的指针域为NULL或者”^”所以其插入操作是相同的。
答案是可以的，但是这会让链表对第一个结点之前的插入操作变得和其它元素不统一，为了解决这种不便，人为地加入了头结点。

查询

单链表的查询需要一个个遍历，因为它的存储空间不连续所以不能根据第一个元素的地址推断出第i个元素的地址，必须一个个查找，直到查找到第i个元素。因此它的时间复杂度是O(n)。

插入和删除

单链表的插入操作就比较简单，只需要改变插入点的前结点以及插入结点的指针即可。如下图所示

关键的步骤为：

1
2

s->next = p->next; 
p->next = s;

这样就可以插入结点了，注意这里的。
单链表删除元素的操作也是比较简单，只要将要删除结点之前的结点跳过删除结点，然后指向删除结点之后的结点即可。如下图所示：

关键的步骤为：

1

p->next = p->next->next

单链表和顺序存储结构的优缺点

一、时间性能

• 查找
  • 顺序存储结构为O(1)
  • 单链表O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一半的元素，时间复杂度为O(n)
  • 单链表在找出插入点的位置之后（这个过程的时间复杂度为O(n)），插入和删除的时间复杂度为O(1)

二、空间性能

• 顺序存储结构需要预先分配存储空间的大小，分大了，浪费，分小了容易发生上溢。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

静态链表

上文中提到的链表的实现是基于内存地址的，这是C语言或者其它可以操作内存的语言所容易实现。然而，对于不能操作内存的语言可以实现链表的存储结构吗？答案是可以的。实现的原理是：利用数组来代替指针，以此来描述单链表。这时数组的元素由两部分内容组成，data和cur。也就是说数组的每个元素对应一个data和cur。其中data用来存储数据，cur用来存储指针(相当于单链表中的next指针，它用来存放其后继元素在数组中的下标，我们把cur叫做游标)。这种用数组来描述的链表称为静态链表，为啥叫静态呢？因为其存储空间是顺序的，所以这也是一种顺序的存储结构，它的存储空间还是需要提前分配好的。它的结构如下所示：

静态链表的第一个和最后一个元素做了特殊处理里面不存储数据，只存储cur值。链表中申请了但是没有被利用的空间是空闲空间。第一个元素中的cur存放的是第一个空闲空间元素的下标；最后一个元素的cur值为第一个元素的下表。

静态链表的插入操作和删除操作

动态链表在插入和删除的时候需要调用malloc()和free()这两个函数来实现。但是在静态链表中操作的是存储空间已经提前申请好的数组，所以只需要利用相关的策略就可以实现。比如我们要在上述的“乙”和“丁”之间插入“丙”元素，那我们该怎么做呢？我们只需要把“丙”放到下标为7的位置，然后“乙”的cur值改为7，丙的cur值改为3即可。

静态链表的删除操作和动态链表的删除有些不太一样，被删除之后相当于并入到了空闲链表，那么我们就把第一个元素的cur值标为要删除元素的下标（表明它是第一个空闲元素），然后让被删除元素的cur值指向之前第一个空闲元素的下标。这样之后该被删除的元素就并入了空闲元素之中。

静态链表的查询操作和动态链表的几乎相同，就不赘述了。

静态链表的优缺点

循环链表

单链表有一个非常严重的问题：从链表中的一个结点出发，访问到链表中的所有结点，比如当从尾结点出发，要访问到所有的结点，必须先把指针移动头结点，然后从头开始遍历。为了解决这个问题，又引入了一种新的数据结构：循环链表。循环链表也就是说把原来单链表中终端结点的指针端由空改为指向头结点，这就使整个链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表（circular linked list）。这样虽然可以解决遍历其中任何一个结点的目的，但是还有一个问题：从头结点查找尾结点的时间复杂度为O(n)。我们可以通过将头指针移动位置来解决这个问题：不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了（时间复杂度都是O(1)）。

关于循环链表的其它操作和单链表的几乎是一样的，不再赘述。

双向链表

循环链表是解决了单链表中查找所有结点的难题，但是它还存在一个问题：如果要查找某个结点的前驱结点，那么需要的时间复杂度是O(n)，因为我们要按照单向的指针遍历一遍。为了解决这个问题提出了双向链表的概念：双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。它的结构如下：

双向链表的插入和删除

双向链表的插入相对于单链表的插入要复杂一些，因为它涉及到两个指针的操作。如下图所示：

其中的关键步骤为：

1
2
3
4

s->prior = p;  // 把p赋值给s的前驱，如①
s->next = p->next; // 把p的后继赋值给s的后继，如②
p->next->prior = s; // 把s赋值给p的后继的前驱，如③
p->next = s; // 把s赋值给p的后继，如④

相对于插入操作，删除操作相对比较简单，如下图所示：

其中的关键步骤为：

1
2
3

p->prior->next = p->next; // 将p的后继赋值给其前驱的后继，如①
p->next->prior = p->prior; // 将p的前驱赋值给p的后继的前驱，如②
free(p); // 释放p

相对于单链表其查找速度更快了，但是它多出了一位来存储指向其前继结点的指针，因此是典型的用空间换取时间的做法。另外循环链表的插入相对来说比较复杂，需要把握好每一步的顺序，否则会出错。

Java中的类型转换

兼容的自动转换

在编程中把一种类型的值赋给另一种类型的变量是合法的。如果这两种类型是兼容的，那么Java会自动对其进行类型转换。例如：把int类型的值赋给long类型的变量就可以。然而如果两种类型不兼容，那么就不会发生这种隐式的类型转换。例如，没有将double类型转化为byte类型的定义。这种不兼容的转化只能自己强制进行。
满足以下两个条件时，Java会自动给你进行类型转换：

• 这两种类型是兼容的。
• 目的类型的范围要比源类型的范围大。

数字类型，包括整数和浮点类型都是彼此兼容的，但是，数字类型和字符类型（char）或布尔类型（bollean）是不兼容的。

不兼容的强制转换

虽然自动转换很好，但是它不能满足所有的需求。例如，你需要将一个int类型的变量付给一个byte类型的变量，你就需要使用(target-type)value这种转换了。下面演示将int转换为byte，如果整数超出了byte类型的取值范围，那么它的值将会因为对byte类型的值取%而减少。

1
2
3
4

int a;
byte b;
// ...
b = (byte)a;

当把浮点数转换为整数类型时会发生一种不同的转换：截断。你知道整数没有小数部分，当你把浮点数转化为整数的时候，其小数部分将会被舍弃。例如，如果将值1.23赋给一个整数，那么其结果是1，0.23被舍弃了。如果浮点数值太而不能适合目标整数类型，那么它的值将会因为对目标类型值域取模而减少。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 // Demonstrate casts.
    class Conversion {
      public static void main(String args[]) {
       byte b;
       int i = 257;
       double d = 323.142;
       System.out.println("\nConversion of int to byte.");
       b = (byte) i;
       System.out.println("i and b " + i + " " + b);
       System.out.println("\nConversion of double to int.");
       i = (int) d;
       System.out.println("d and i " + d + " " + i);
       System.out.println("\nConversion of double to byte.");
       b = (byte) d;
       System.out.println("d and b " + d + " " + b);
} }

该程序的输出如下：

1
2
3
4
5
6

Conversion of int to byte.
i and b 257 1
Conversion of double to int.
d and i 323.142 323
Conversion of double to byte.
d and b 323.142 67

当值257被强制转换为byte变量时，其结果是257除以256(256是byte类型的变化范围)的余数。当把变量d转换为int类型时，它的小数部分被舍弃了。当吧变量d转换为byte类型时，它的小数部分被舍弃了，而且它的值减少为256的模，即67。

表达式中的类型提升

在表达式中，有时候中间值的精度会比较高，它有可能超过任何一个操作数的范围。例如，考虑下面的表达式：

1
2
3
4

byte a = 40;
byte b = 50;
byte c = 100;
int d = a * b / c;

其中间结果a*b很容易超出它的任何一个byte型操作数的范围。为了处理这种问题，当分析表达式时，Java会自动提升各个byte或者short型的操作数为int型。这意味着表达式a*b是使用整数而不是字节型来运算的。这样，尽管变量a和b都被指定为byte型，50*40的中间表达式的结果2000是合法的。

自动类型提升很好，但是有时候会引起令人疑惑的编译错误。例如，这个看起来正确的程序却会引起问题：

1
2

byte b = 50;
b = b * 2; // Error! Cannot assign an int to a byte!

这里看上去完全合法，但由于当表达式求值的时候，操作数被自动提升为了int型，所以需要强制转换才可以赋值（但是你必须考虑好溢出的情况）。

1
2

byte b = 50;
b = (byte)(b * 2);

这样就不会有编译器错误了。

类型提升的约定

除了将byte型和short型提升到int型以外，Java还定义了其它的类型提升规则。如果一个操作数是long型，那么整个表达式将被提升到long型；如果一个操作数是float型，整个表达式将被提升到float型；如果一个操作数是double型，计算结构就是double型。我们用个例子来说明：

1
2
3
4
5
6
7
8
9
10
11
12

class Promote {
      public static void main(String args[]) {
       byte b = 42;
       char c = 'a';
       short s = 1024;
       int i = 50000;
       float f = 5.67f;
       double d = .1234;
       double result = (f * b) + (i / c) - (d * s);
       System.out.println((f * b) + " + " + (i / c) + " - " + (d * s));
       System.out.println("result = " + result);
} }

我们来分析：

1

double result = (f * b) + (i / c) - (d * s);

的类型提升过程，在第一个子表达式f*b中，变量b被 升为float类型，该子表达式的结果当然是float类型。 接下来，在子表达式i/c，中，变量c被 升为int类型，该子表达式的结果当然是int类型。然 后，子表达式d*s中的变量s被 升为double类型，该子表达式的结果当然也是double类型。 最后，考虑三个中间值，float类型，int类型，和double类型。float类型加int类型的结果是float 类型。然后float类型减去 升为double类型的double类型，该表达式的最后结果是double型。

Java中的break

Java中的break除了可以用来在switch或者循环中终止某个条件或者循环，还可以作为goto语句的一种形式来使用。Java中没有goto语句，因为goto让程序流程变得非结构化，可能让程序难以理解和维护，并且可以阻止某些编译器优化。但是，有些地方使用goto语句有助于流程控制，并且是合法的。例如，从嵌套很深的循环中退出来，goto语句就很有帮助。因此，Java定义了break语句的一种扩展形式来处理这种情况。通过给某个代码块加上标签，那么其内部的break语句就可以在某些情况下跳转到该标签。这个代码块不必非要是循环或者switch，它可以是任意的代码块。标签的指定如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Using break as a civilized form of goto.
    class Break {
      public static void main(String args[]) {
       boolean t = true;
       first: {
         second: {
           third: {
            System.out.println("Before the break.");
            if(t) break second; // break out of second block
            System.out.println("This won't execute");
} 
           System.out.println("This won't execute");
         }
         System.out.println("This is after second block.");
       }
} }

改程序的输出如下：

1
2

Before the break.
This is after second block.

这个示例中有三个嵌套的代码块，每一个都有它自己的标签。break语句使得循环往外层跳转，直接跳过了second标签的的代码块，直接执行了first标签的代码块。

Java中的方法重载

方法重载就是说如果两个方法有相同的方法名字，但是其参数不同（参数个数不同或者参数类型不同），那么Java会根据调用时候不同的参数类型来匹配不同的方法来调用。然而有时候其类型匹配不是很精确：比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

  // Automatic type conversions apply to overloading.
  class OverloadDemo {
    void test() {
     System.out.println("No parameters");
    } 
    // Overload test for two integer parameters. 
    void test(int a，int b) { 
      System.out.println("a and b: " + a + " " + b);
    }
    // overload test for a double parameter
    void test(double a) {
      System.out.println("Inside test(double) a: " + a);
    }
} 
 class Overload {
    public static void main(String args[]) {
      OverloadDemo ob = new OverloadDemo();
      int i = 88;
      ob.test(); ob.test(10，20); 
      ob.test(i); // this will invoke test(double)
      ob.test(123.2); // this will invoke test(double)
    }
}

输出结果是：

1
2
3
4

No parameters
a and b: 10 20
Inside test(double) a: 88
Inside test(double) a: 123.2

这里，我们的test(i)中i是int型，但是在调用时，我们发现调用test(double)类型，这是因为在调用test(int)型的时候Java找不到相应的类型，所以就将int扩大为了double，然后就调用了test(double)，如果我们这里定义了一个test(int)，那么就会调用这个test(int)而不会将int扩大为double。

super关键字

在继承中，super可以用来表示父类，可以调用父类特有的方法。还有一种应用情况是：它可以用来调用父类中被子类所隐藏的属性，比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class A {
int i; } 
    // Create a subclass by extending class A.
    class B extends A {
      int i; // this i hides the i in A
      B(int a, int b) {
       super.i = a; // i in A
       i = b; // i in B
} 
      void show() {
       System.out.println("i in superclass: " + super.i);
       System.out.println("i in subclass: " + i);
} } 
    class UseSuper {
      public static void main(String args[]) {
       B subOb = new B(1, 2);
       subOb.show();
      }
}

该程序的输出为：

1
2

i in superclass: 1
i in subclass: 2

尽管B中的实例变量i隐藏了A中的i，使用super就可以访问超类中定义的i。其实， super也可以用来调用超类中被子类隐藏的方法。

构造函数

在类的层次结构中，构造函数的调用顺序是从父类到子类。并且父类的构造方法的调用要放在子类构造方法的第一行中。如果子类中没有用到super()，那么每个父类默认的或者无参数的构造函数将执行。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Create a super class.
    class A {
      A() {
       System.out.println("Inside A's constructor.");
} } 
    // Create a subclass by extending class A.
    class B extends A {
      B() {
       System.out.println("Inside B's constructor.");
} } 
    // Create another subclass by extending B.
    class C extends B {
      C() {
       System.out.println("Inside C's constructor.");
} } 
    class CallingCons {
      public static void main(String args[]) {
C c = new C(); } 
}

该程序的输出如下：

1
2
3

Inside A’s constructor
Inside B’s constructor
Inside C’s constructor

由此可见，构造函数以派生的顺序被调用。

补码

我们先来看一个有趣的例子：

在这里我们定义了一个signed char类型的数据，将其赋值为128，然后系统给我们一个警告，意思就是说它隐式地将数值给转换成了-128，这究竟是为什么呢？

其实在计算机中数值都是以补码的形式存储的：

正数的补码是其自身，负数的补码是其对应的正数的反码加1。

我们先看一下-42在计算机中是如何表示的：
它是先将其对象的正数42，0010 1010然后取反1101 0101，然后再加1，得到1101 0110。

我们知道signed char是占八位的。其存储范围是：0000 0000到1111 1111。那么128的补码还是128，其二进制表示为：1000 0000。但是这里有个问题，因为其类型是有符号的，所以最高位是符号位，也就是说这个数不能用来表示128了，那么它表示多少呢？我们就要看看它是谁的补码就是好了。我们先将1000 0000取反，然后的到0111 1111，加一得到1000 0000，再乘以-1,得到-128。如果不太明白，我我们可以将128变大，变成129：

129为整数，其补码是其自身，1000 0001，又因为其最高位是符号位，所以其表示的是一个负数，它表示多少呢？先将其取反0111 1110，然后+1得到0111 1111，这时127，最后乘以-1得到-127。

switch语句为什么比if else快？

因为编译器在编译switch语句的时候会检查每个case常量，并且会创建出一个”跳转表”，这个表用来在表达式的基础上选择执行路径，其时间复杂度是O(1)，而if else的时间复杂度是O(n)，所以switch case要比if else快很多。

寄存器是什么？

寄存器是一种存储信息的硬件，它和内存一样可以用来存储，但是和内存不同的是，它的速度极其快（比RAM的主存要快得多，它还有一些辅助功能，它常常被用做软件和外设之间通信的桥梁，起到缓冲的作用，同时CPU中寄存器速度非常快，这就让经常需要用到的数据放到寄存器中，而不需要每次都从主存中去读取，从而提高了程序的执行速度。软件将信息写入寄存器，然后外设将信息从寄存器中读出去。如果外设有信息需要软件进行处理，那么它也需要先将信息放到寄存器中，然后有软件从中读取。寄存器的主要功能包括：

• 某些功能的配置和初始化，特别是在初始化阶段
• 缓存存储
• 不同种类的输入输出
• 状态报告，比如某个硬件的状态发生了变化

常见的寄存器包括：MAR(Memory Address Register)，这个寄存器主要用来存放下一条即将执行的指令，CPU根据MAR中指令的地址取出指令，然后放到MDR(Memory Data Register中，然后CIR(Current Instruction Regitster)将指令从MDR中拷贝一份。MBR(Memory Buffer Register)，用来存放要放入存储器的数据和从存储器中读出的数据。相关资料可以参考YouTube

CPU为什么需要三级缓存？

CPU和内存的速度不匹配是计算机领域的一个重要问题，如果内存中采用和CPU中相同型号的寄存器，那么其代价又会太高，并且根据局部性原理，这种需求是没有必要的。存储器的价格，速度，容量是人们考虑的主要因素，但是它们之间也存在这制约因素：速度越快，价格就越高；容量越大，价格越高；容量越大，速度越低。根据局部性原理(Principle of Locality)我们的程序中常用的数据又基本都是固定的。所以就在CPU和内存之间采用了三级缓存（它内部存储的）来提高获取数据的速度，如果数据能在L1，L2，L3中找到的话就直接从中取，如果没有再从内存取，如果内存没有，再从外存取，这样就会提高获取数据的速度。这里要注意每个处理器都有其自己的缓存区，最后他们共享一块内存，这就会造成数据不一致的严重问题。

上下文切换

在多任务执行的时候，上下文切换是指从一个线程或者进程切换到另外一个线程或者进程，这里的上下文是指：CPU寄存器和程序计数器中的内容。它的具体内容包含以下三个步骤：

1. 挂起当前进程，将当前的CPU状态保存至内存
2. 从内存中获取接下来将要执行进程的上下文，并且将其存入CPU寄存器中
3. 返回程序计数器指定的位置（例如进程被终止的点）并且继续执行进程

这里的切换包含进程切换和线程切换两种情况，它们之间的相同点和不同点为：

一、进程切换

虚拟内存空间不能保持相同；调用操作系统内核；寄存器内容的切入切出和内核操作的转移是最消耗性能的；

二、线程切换

虚拟内存空间保持相同；调用操作系统内核；寄存器内容的切入切出和内核操作的转移是最消耗性能的；

这其中还有一个隐含的性能消耗点是：处理器缓存系统的失效。在虚拟内存空间切换的过程中会导致处理器的Translation Lookaside Buffer (TLB) 失效，这会造成很大的内存损耗。造成上下文切换的原因有：进程自动让出其时间片，或者调度器给它分配的时间片到了，或者硬件发生了中断操作，加锁，或者其它的软件操作也会造成上下文切换。上下文切换很消耗大量的CPU时间造成较大的性能损耗。

什么是线程？

线程是寄存器的一组状态，这组状态用来规定程序的执行顺序，执行地址，以及下条指令的地址。

什么是指令重排？

指令重排就是在执行程序的过程中，在确保不影响程序输出结果的情况下，为了提升性能，编译器和处理器对指令做的重排序：

指令重排可以带来性能的提升，它在单线程的情况下是不会出问题的，这一点是由程序的顺序规则来保证的，如果是在多线程就会出现各种意想不到的问题。比如:

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

static int x = 0, y = 0;
static int a = 0, b = 0;
public static void main(String[] args) throws InterruptedException{

    Thread one = new Thread(new Runnable() {
        @Override
        public void run() {
            a = 1;  // A1
            x = b;  // A2
        }
    });
    Thread two = new Thread(new Runnable() {
        @Override
        public void run() {
            b = 2;  //B1
            y = a;  //B2
        }
    });
    one.start();
    two.start();
    one.join();
    two.join();
    System.out.println("x =" + x + ";" + "y =" + y);
}

这段代码不仅可以输出：

1
2
3

x = 0 ; y = 1
x = 2 ; y = 0
x = 2 ; y = 1

但是在A1和A2，B1和B2重排序之后还可以输出：x = 0 ; y = 0的情况。

参考资料:

1. 线程上下文切换和进程上下文

2. 上下文切换的定义

3. 线程的定义