面试准备-知识储备
数据结构
一、优先级队列
Java中：PriorityQueue
- 特性？：
是一种特殊的队列。每一个元素都有一个优先级。当出队操作时，队列会按照元素优先级的高低顺序从队列中取出一个元素并删除。 - 实现原理？：
堆（如二叉堆）等数据结构来实现。 - 使用场景？：
任务调度、事件处理等场景。（确保优先级高的任务或事件先被处理，从而提高系统的响应速度和效率。）
点击查看代码
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return b-a;//此时是大根堆，默认是小根堆
}
});
二、堆和树
-
堆和树的关系？
堆总是一颗完全二叉树。（因此可以层序的规则采用顺序的方式来高效存储）（也就是说，完全二叉树适合使用数组进行存储，层序遍历。一般二叉树不适合顺序方式进行存储，浪费存储空节点的空间）（左孩子2i+1，右孩子2i+2） -
堆的左旋和右旋？（错了吧，下面是AVL树的左右旋）
平衡二叉树不平衡时：左左-右旋。右右-左旋。左右-左旋再右旋。右左-右旋再左旋。 -
堆的调整？
如果parent比chi1和chi2都小，循环结束。否则进入循环（parent与chi1和chi2较小者进行交换->继续向下调整parent）OlogN -
堆的插入？
插入到最后，然后慢慢进行，向上调整（如果新节点小于它的父节点，则交换，继续向上遍历） -
堆的删除？
根节点和最后一个元素交换，弹出根节点。（交换上去的节点循环向下调整，即可） -
除了红黑树还有什么平衡树？
AVL树（二叉搜索树的基础上加伤平衡的限制）。2-3tree（2种节点：2节点有1个key2条边，左小于根右大于根。3节点有2个key3条边，左小于key1中在key1和key2之间右大于key2）。B树，B+树。 -
红黑树为什么是平衡树？
红黑树是一种自平衡的二叉搜索树，它的每一个节点有一个存储位标示颜色，通过对路径上的颜色约束，红黑树保证没有一条路径比其它路径长2倍，因此是接近平衡的。 -
红黑树的5条规则：
- 每一个节点非红即黑
- 根节点是黑色的
- null节点是黑色。（所有叶子节点都是黑色的）
- 红色节点不相邻
- 从任意一个节点到叶子节点（不包括这个节点），黑色节点数量相同。（这个规则也叫红黑树的黑高）
红黑树通过变色、左旋、右旋来修复规则被破坏的情况。
- 红黑树的插入和删除（还不太了解）？？？
插入：
- 插入位置是根节点：直接把这个节点变成黑色
- 插入位置的父亲节点是黑色，直接插入新节点即可（默认红色）
- 插入位置的父节点是红色：
- 节点的叔叔节点是红色：父和叔变黑色，爷变红色
- 节点的叔叔节点是黑色：1以爷为中心左旋，2新的爷变黑新的兄弟变红
删除：
用后继节点替换删除节点，只会影响后继节点所在的子树。
然后对后继节点所在的子树进行变色操作。
使用：增offer，删poll
操作系统
一、进程、线程、协程
- 进程和线程的区别？
- 进程是资源调度的最小单位，线程是CPU调度（运行调度）的最小单位。
- 进程作为程序独立运行的载体保障程序正常执行。
- 进程的存在使得操作系统资源利用率大幅提升。
- 进程目的：方便操作系统管理
- 线程，比进程更小的独立运行的基本单位。
- 线程包含在进程之中，是进程中实际运行工作的单位
- 一个进程可以并发多个线程，每个线程执行不同的任务。
- 进程控制块PCB，线程控制块TCB
- 线程目的：提高并发量、吞吐量。
- 关系：进程的线程共享进程资源。
- 线程和协程的区别？
Coroutines协程
问题：在多核场景下，如果是IO密集型场景，就算有多个线程来处理，也未必能提升CPU的利用率，反而会增加线程切换的开销。另外，多线程之间假如存在临界区或者共享内存，那么同步的开销也是不可忽视的。
协程：轻量级的线程。
- 协程是一种用户态的轻量级线程，协程的调度完全由用户控制。
- 一个线程可以拥有多个协程，协程不是被操作系统内核所管理，而是完全由程序所控制。
- 与其让操作系统调度，不如让我来，这就是协程。
- 比线程更小的粒度，运行效率更高，可以支持更高的并发。
- 优缺点：可以减少上下文切换的成本，无法发挥CPU的多核优势，协程主要运用在多IO的场景。
重要的是，协程不是被操作系统内核所管理，而是完全由程序所控制（也就是在用户态执行）
好处：性能得到很大的提升，不会像线程切换那样消耗资源。
协程和线程的主要区别是它将不再被内核调度，而是交给程序自己，二线程是将自己交给内核调度，所以也不难理解golang中调度器的存在。
总结：为了提升用户线程的最大利用效率，提出了协程的概念。
- 线程间通信？
- 互斥量（锁）
- 条件变量
- 事件：事件机制，允许一个线程在处理完一个任务后，主动唤醒另一个线程执行任务。
- 进程间通信？
- 管道：半双工，只能在一个方向上流动，有固定的读端和写端。
- 信号：通知接收进程某个事件已经发生。
- 消息队列：消息的链表，是一系列保存在内核中消息的列表。
- 共享内存：多个进程将同一块物理内存（用户空间）映射到自己的虚拟地址空间当中。
- 套接字：此方法主要用于在客户端和服务器之间通过网络进行通信。
- 为什么线程更高效？（错了吧，切换更高效吧？）
- 每个进程都有自己的虚拟地址空间，把虚拟地址转化为物理地址需要查找页表，页表查找是一个很慢的过程，因此通常使用Cache来缓存常用的地址映射，这里叫TLB。每个进程都有自己的页表，当进程切换时，页表也要切换，页表切换后缓存TLB就失效了，导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来就是程序运行会变慢。
而线程切换不会导致TLB失效，因为线程无需切换地址空间。因此我们通常说线程切换比进程切换快，原因就在这里。
虚拟内存技术：
虚拟内存是操作系统为每一个进程提供的一种抽象，每个进程都有属于自己的、私有的、地址连续的虚拟内存。当然我们知道最终进程的数据及代码必然要放到物理内存上，那么必须有某种机制能记住虚拟内存对物理内存的地址空间映射。操作系统通过页表记住这种映射关系。有了页表就可以将虚拟内存地址转换为物理内存地址了，这种机制就是虚拟内存。
-
线程的生命周期：创建，就绪，运行，阻塞，终止。
-
进程调度算法：
- 先到先服务
- 短作业优先
- 时间片轮转
- 优先级
- 多级反馈队列
- 为什么多线程有线程安全问题？如何解决？
原因：
- 修改共享内存。
- 事务不保证原子性。一个线程对变量的操作过程中可能被其它线程打断。
- 内存可见性：每个线程都有自己的工作内存（私有），同步回主内存中存在延迟。
- 多线程中的指令集重排
解决：
- 加锁，synchronized
- 引入volatile关键字，保证内存可见性。（但volatile不保证原子性，适用一读一写，多写的情况还是会出错）能够防止指令集重排
- 引入wait和notify。wait需要搭配synchronized来使用。
wait和sleep的区别：
- wait是用于线程间通信的，sleep是让线程阻塞一段时间
- wait需要搭配synchronized使用，sleep不需要
- wait是object方法，sleep是thread的静态方法。
相同：都可以让线程放弃执行一段时间。
- 什么是僵尸进程？会占用CPU吗？孤儿进程？
不占用cpu。
子进程的结束和父进程的运行是一个异步过程，即父进程永远无法预测子进程到底什么时候结束。
- 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
- 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init（进程号为1）所收养，并由init进程对它们完成状态收集工作。
孤儿进程并不会有危害：init接管其原父进程的作用，init进程会循环的wait，给孤儿进程善后。
任何一个子进程（init除外）在exit之后，并非马上就消失掉，而是留下一个称为僵尸进程（Zombie）的数据结构，等待父进程处理。（包括进程号，退出状态，运行时间等）如果用ps命令查看的话，会有很多状态为Z的进程。如果不调用wait/waitpid的话，进程号一直不释放，但系统所能使用的进程号是有限的，可能导致没有可用的进程号而使得系统不能产生新的进程。
解决：僵死进程不是问题的根源。罪魁祸首是他们的父进程，我们把产生大量僵死进程的父进程毙掉（通过kill发送SIGTERM或者SIGKILL信号）。它的僵死进程就变成了孤儿进程，被init进程接管，init给它们善后。
二、锁
- 说说你对锁的了解？
- java中：synchronized关键字，Lock接口的实现类（ReentrantLock可重入锁，ReadLock读锁，WriteLock写锁）（ReadWriteLock其实是一个工厂接口，ReentrantReadWriteLock是ReadWriteLock的实现类，它包含2个静态内部类，ReadLock和WriteLock，这两个类又分别实现了Lock接口）
- 乐观锁和悲观锁：并不是特指某个锁，而是在并发情况下的2种策略。悲观锁阻塞事务，乐观锁回滚重试。
- 唯一的乐观锁-CAS：CAS是实现自旋锁的基础。CAS利用CPU指令，从硬件层面保证了操作的原子性。（java.util.concurrent.atomic包里的原子类）（乐观锁根本不是锁，它根本没锁住对象，而是一个无限充实的算法而已）（乐观锁==自旋锁）（ABA问题-在栈中可能带来问题，引入版本号）
- synchronized锁升级：无锁-偏向锁（第一个线程）-轻量级锁（2个线程竞争，另1个忙等）-重量级锁（忙等太久了，挂起等待唤醒）
- 可重入锁（java中reentrant开头命名的锁）
- 公平锁、非公平锁。（synchronized是非公平锁，且不能变成公平锁）
- 可中断锁：java中只是发送中断信号，何时中断、是否中断取决于获取锁的线程。
- 读写锁、共享锁（读锁）、互斥锁（写锁）
- 死锁条件？
四个：
- 互斥条件：每个资源只能被一个进程使用
- 占有等待：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
- 不可抢占：进程已经获得的资源，未使用完，不能强行剥夺。
- 循环等待：若干进程之间形成一条头尾相接的循环等待资源关系。（根本条件）
三、操作系统杂项
- while 1这个语句操作系统层面让它停止？Java层面让它停止？
- 通过kill命令，首先使用ps命令查找正在执行的命令的进程ID（PID），然后使用kill PID命令终止该进程的执行。
- 通过任务管理器，图形化界面，选择结束任务或终止进程选项。
- 虚拟内存？（对物理内存的补充，速度接近于内存，成本接近于辅存）（上面有详细的虚拟内存介绍）
- 页表，段页？
- 用户态、内核态？