# 蚂蚁一面需要补足的点

面试时间：54min

## ReentrantLock、Synchronized、AQS、ConcurrentLinkedQueue

难怪Synchronized是重量级操作，重量级的来源是系统状态的切换，将线程从RUNNING和BLOCKING状态相互转换是需要切换系统状态的，这时候应该是通过系统调用来实现的，从而造成大量的消耗。

synchronized锁升级过程的一个实现：

无锁：感觉很抽象哦，适用场景感觉非常的少，只有在修改操作在循环内进行的时候，线程会不断尝试修改共享资源，如果没有冲突就修改成功，否则继续尝试（很有CAS的味道了，但是这个循环过程是由代码自己实现的）。

偏向锁：同步代码块偏向一个线程，被锁定的对象的对象头里面的Mark Word当中存放的是了偏向锁的线程ID，这时候进入代码块是不会执行CAS和MonitorEnter操作的，仅仅只是会比对当前线程ID与锁定对象的对象头ID是否相等，如果相等就直接过了，如果不等说明发生了线程的竞争，进入轻量级锁状态。

轻量级锁：实现是通过让当前线程创建一个Lock Record对象，然后通过CAS操作取修改锁定对象的MarkWord字段中的owner，让owner指向这个Lock Record对象。如果没有修改成功就自旋操作嘛，升级成重量级锁的条件是自旋超过一定次数（因为JVM进行了优化，以前默认是10次，现在具有自适应性，可以通过这个对象以前自旋的操作成功率来就行自旋次数和时间的调整），或者是一共有三个线程（一个持有、一个自旋、又来了一个）。

重量级锁：也就是常见的monitor enter和monitor exit

ReentrantLock没有获得资源的线程所处的状态不一定都是RUNNING，如果该线程一次都没有获取到应该是BLOCKING。

测试代码：

```java
ExecutorService pool = Executors.newFixedThreadPool(10);
ReentrantLock lock = new ReentrantLock();
for (int i = 0; i < 10; i++) {
    pool.submit(() -> {
        lock.lock();
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    });
}
```

测试结果：

![image-20210228003149304](https://gitee.com/LuckyCurve/img/raw/master//img/image-20210228003149304.png)

ReentrantLock的公平实现和非公平实现：

主要就是获取资源时候的不同

公平锁获取资源代码：

```java
protected final boolean tryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (!hasQueuedPredecessors() &&
            compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0)
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
```

非公平锁：

```java
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    // 尝试获取这个锁
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    // 自己持有这个锁
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}
```

主要就多了第五行的一个判断hasQueuedPredecessors，这个方法主要就是来判断这个线程是否是等待队列中的第一个线程，如果是的就继续执行，不满足条件。

可以看到保证公平性并不是去按照队列的方式去唤醒，而是去判断是否是队列中的队列头元素从而决定是否放行。

解锁过程两者都是一样的：

```java
protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    // 判断是否还持有锁
    if (c == 0) {
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}
```

AbstractQueuedSynchronizer的核心就是一个被volatile修饰的整型变量state，并且提供几个final方法来进行state的操作，其中最重要的就是`compareAndSetState(int expect, int update)`方法来实现的CAS操作，底层依然是调用CPU的机器指令实现。

其实再回头看ReentrantLock的两种实现加锁，都是使用到了compareAndSetState(0, acquires)来试图进行State状态的修改，还有就是释放过程中用到的setState来直接进行State的设置，因为释放过程就相当于是独占了这个锁嘛，所以可以直接进行不需要CAS操作。

内部队列的数据结构是CLH变体的FIFO双端队列。

ConcurrentLinkedQueue实现：

JUC包下面的安全队列实现，非阻塞的CAS和wait-free这两个算法实现，数据结构是基于单项链表的一个实现。

## 虚拟内存、多级页表

虚拟内存主要是为了解决传统的内存管理低效从而提出的一个解决方案

传统的内存管理如分块、分页、分段都需要将整个程序全部读入内存才能进行运行，但是可能存在大量的冷数据占用内存，出现大量的资源浪费情况，因此我们需要根据局部性原理（时间局部性：使用过的数据和语句可能被再次使用、空间局部性：附近的语句可能被再次执行）实现对热数据的一个读取，每次执行过程中只会先将我们认为的热数据读入到内存当中去就运行了，如果需要的数据不在内存当中就由操作系统负责将需要的信息调入内存，如果内存空间不足，操作系统就会将内存中的冷数据调入到外存。

这样就使得用户使用起来好似有一个比实际内存大得多的内存，这就是虚拟内存。

因此，虚拟内存的最大容量等于CPU寻址范围（如32位就是2的32次方=4GB）

上面使用到了虚拟内存，自然要定义虚拟地址来让上层应用来进行操控，如分配到的虚拟地址转换为物理地址进行使用，这就需要使用到页表来实现这种映射关系了，由于页表可能较大，我们需要使用如下的优化手段：

* 快表：就是将页表读入到缓存当中去，这样可以加速一个映射的过程
* 多级页表：主要是防止内存过大从而导致生成的页表也非常大，会占用内存空间，就如内存是4G，页大小是1K，一级页表需要4M，二级页表需要4K。按道理此时的内存是4M+4K，反而变大了，其实不是这样的，我们通常只会在内存当中保留高级页表，至于低级页表则是存入到磁盘当中的，需要的时候再调入内存。

## 堆排序

堆其实就是一颗完全二叉树，这其实是堆的一种逻辑结构，他的物理结构仍然是数组，只不过是对堆进行了一个编号，按照二叉树的需要来进行的，映射过程如下：

![image-20210228112920191](https://gitee.com/LuckyCurve/img/raw/master//img/image-20210228112920191.png)

可以大概分为大顶堆和小顶堆，大顶堆就相当于最大元素存放在树的根节点上，然后需要保证左右叶子节点均小于等于根节点。如果是小顶堆则需要保证根节点都小于等于叶子节点

一般升序采用大顶堆，大的放在最上面，小的放下面，这样可以保证不会取出小的元素之后一直进行数据结构的一个调整，取出最小的k个元素就可以使用大顶堆

同理，如果是降序排序则使用小顶堆，取出最大的k个元素就是用小顶堆就非常方便

这样面试问题也就迎刃而解了，如果需要取出前k个元素，问题规模为n，这时候的一个时间复杂度为`O(nlogk)`，空间复杂度为`O(k)`

堆的调整是从最底的非叶子节点开始进行调整的。

不稳定排序，最坏、最好时间复杂度均为O（nlogn）

PriorityBlockingQueue使用的是二叉堆来进行的一个元素排序，可能和堆排序有点关系？

## Thread如何检查Interrupt

看到一个Thread#join方法，如果在主线程中调用`thread1.join()`那么此时主线程会等待thread1线程执行完成然后继续执行，此时线程进入WAITING或者是TIMED\_WAITING状态。

先就这样粗浅的理解，只要Thread处于RUNNING状态就会定期检查Interrupt标志位，如果是true并且检查到了就需要抛出一个InterruptException异常进行相应。

## MySQL索引和锁的关系

其实InnoDB的行锁是通过锁索引的方式来进行实现的，就相当于如果不存在索引那么就不会使用行锁了。

如果存在索引，并且使用了where子句，那么此时会加行锁

如果不存在索引，即使存在where子句，也只会加表锁

如果没有where子句，相当于对全表进行查询，直接使用表锁

## 学到的一些东西：

使用缓存模型之所以不能先删除Redis再删除MySQL是因为可能存在以下情况：

在删除数据时候Redis数据已经删除了然而MySQL数据还没有删除，此时进行查询出现情况：缓存没有命中，去查询到了MySQL没有删除的数据，并写入到了Redis当中，后续MySQL删除数据完成，此时就会造成缓存脏了。

ReentrantLock的Condition的实现：

基于AQS来进行实现的，可以认为每一个Condition都是一个资源，需要去进行CAS操作去尝试获取，此时的线程是处在一个个等待队列当中的，一个Condition对应一个等待队列。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luckycurvec.gitbook.io/java-knowledge-architecture/mian-shi-19/mian-jing/ma-yi-jin-fu-yi-mian-mian-jing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.