数据结构

Java HashMap原理：

https://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/

4、建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

Rehash和负载因子

负载因子表示一个散列表的空间的使用程度，有这样一个公式：initailCapacity*loadFactor=HashMap的容量。

所以负载因子越大则散列表的装填程度越高，也就是能容纳更多的元素，元素多了，链表大了，所以此时索引效率就会降低。

反之，负载因子越小则链表中的数据量就越稀疏，此时会对空间造成烂费，但是此时索引效率高。

HashMap有三个构造函数，可以选用无参构造函数，不进行设置。默认值分别是16和0.75.

官方的建议是initailCapacity设置成2的n次幂，laodFactor根据业务需求，如果迭代性能不是很重要，可以设置大一下。

当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用

initailCapacity，loadFactor会影响到HashMap扩容。

HashMap每次put操作是都会检查一遍
size（hashmap中元素个数）>initailCapacity*loadFactor
是否成立。如果不成立则HashMap扩容为以前的两倍（数组扩成两倍），

然后重新计算每个元素在数组中的位置，然后再进行存储。这是一个十分消耗性能的操作。

所以如果能根据业务预估出HashMap的容量，应该在创建的时候指定容量，那么可以避免resize().

参考：https://www.cnblogs.com/yuanblog/p/4441017.html

Go Map原理

如下图所示，当往map中存储一个kv对时，通过k获取hash值，hash值的低八位和bucket数组长度取余，定位到在数组中的那个下标，hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在，key和value的具体值则通过指针运算存储，当一个bucket满时，通过overfolw指针链接到下一个bucket。

红黑树与B+树区别

参考：https://www.cnblogs.com/tiancai/p/9024351.html

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+ Tree
作为索引结构，这是因为使用 B+ 树访问磁盘数据有更高的性能。

（一）B+ 树有更低的树高

平衡树的树高 O(h)=O(logdN)，其中 d 为每个节点的出度。红黑树的出度为 2，而 B+
Tree 的出度一般都非常大，所以红黑树的树高 h 很明显比 B+ Tree 大非常多。

（二）磁盘访问原理（还有范围访问）

操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次
I/O 就能完全载入一个节点。

如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+
树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以
B+ 树更适合磁盘数据的读取。

（三）磁盘预读特性

为了减少磁盘 I/O
操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入。

二叉 ALV 红黑树的区别

AVL树是最先发明的自平衡二叉查找树：就是平衡二叉树空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

由于维护ALV这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。

红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。

2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

RB-Tree是功能、性能、空间开销的折中结果

AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

基本上主要的几种平衡树看来，红黑树有着良好的稳定性和完整的功能，性能表现也很不错，综合实力强，在诸如STL的场景中需要稳定表现。

前缀树

下面我们来讲一下对于给定的字符串集合{W1, W2, W3, …
WN}如何创建对应的Trie树。其实上Trie树的创建是从只有根节点开始，通过依次将W1, W2,
W3, … WN插入Trie中实现的。所以关键就是之前提到的Trie的插入操作。

具体来说，Trie一般支持两个操作：

1. Trie.insert(W)：第一个操作是插入操作，就是将一个字符串W加入到集合中。

2. Trie.search(S)：第二个操作是查询操作，就是查询一个字符串S是不是在集合中。

参考：https://www.cnblogs.com/vincent1997/p/11237389.html

经典问题：海量数据处理 – 10亿个数中找出最大的10000个数（top K问题）

海量数据处理参考：https://www.cnblogs.com/linguanh/p/8532641.html

https://blog.csdn.net/djrm11/article/details/87924616

去重：

https://www.jianshu.com/p/f6042288a6e3

topK最大数解决方案：

分治+去重（set/hash/位图bitmap/布隆过滤器）

+ 1.最小最大堆（数据流）

2. Quick Select (当然如果不是数据流的话，使用QuickSelect效率更高
平均时间复杂度降为 O(N))

+合并排序（或quick或堆）

（位图bitmap直接排序了）

topK最大频率：

分治+去重（set/hash/位图bitmap/布隆过滤器）+ HashMap排序遍历后+大小堆

+合并排序（或quick或堆）

（内存受限原数据文件切割成一个一个小文件，如次啊用hash(x)%M）

top K问题很适合采用MapReduce框架解决，用户只需编写一个Map函数和两个Reduce
函数，然后提交到Hadoop（采用Mapchain和Reducechain）上即可解决该问题。具体而言，就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce
task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce
函数，统计所有Reduce task，输出数据中的top K即可。

MapReduce:

参考：https://blog.51cto.com/12445535/2351469

Hadoop分布式文件系统(HDFS)

终极参考：https://www.cnblogs.com/futurehau/p/6041022.html

操作系统

操作系统（Operating
System，简称OS）是管理和控制计算机硬件与软件资源的计算机程序，是直接运行在“裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行，操作系统能有效组织和管理系统中的各种软，硬件资源，合理组织计算机系统的工作流程，又控制程序的执行，为用户提供一个良好的操作环境。

作用

通过资源管理，提高计算机系统的效率。

改善人机界面，向用户提供友好的工作环境。

8bit(位)=1Byte(字节)

CPU

（Central Processing
Unit）是一块超大规模的集成电路，主要解释计算机指令以及处理计算机软件中的数据，包括

运算器(算术逻辑运算单元，ALU，Arithmetic Logic Unit)

高速缓冲存储器(Cache)

数据(Data)

总线(Bus)

存储器

存储程序和各种数据，它采用具有两种稳定状态的物理器件来存储信息，日常使用的十进制数必须转换成等值的二进制数才能存入存储器中。计算机中处理的各种字符，例如英文字母、运算符等，也要转换成二进制代码才能存储和操作。

输入输出设备

向计算机输入和输出数据和信息的设备，能够接收各种各样的数据，既可以是数值型的数据，也可以是各种非数值型的数据。

系统软件和应用软件

系统软件是指控制和协调计算机以及外部设备，支持应用软件开发和运行的系统，是无需用户干预的各种程序的集合，主要功能是调度，监控和维护计算机系统。例如：操作系统和一系列基本工具(比如：编译器，数据库管理，存储器格式化，用户身份验证，络连接)

应用软件是和系统软件相对的，是用户可以使用的各种程序设计语言，以及用各种程序设计语言编制的应用程序的集合，分为应用软件包和用户程序。例如：办公室软件，互联软件，多媒体软件，分析软件，协作软件。

并发（concurrency）和并行（parallelism）

互斥：mutex 同时共享：shared memory

一次仅允许一个进程使用的资源称为临界资源：critical section

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

内存结构：

上图为线程状态机

例：线程所请求的I/O完成，故被唤醒，即从阻塞态到就绪态。

协程是一种轻量级的线程

本质上协程就是用户空间下的线程

协程拥有自己的寄存器register上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈。因此：

协程能保留上一次调用时的状态（即所有局部状态的一个特定组合），每次过程重入时，就相当于进入上一次调用的状态，换种说法：进入上一次离开时所处逻辑流的位置。

协程不是被操作系统内核所管理的，而是完全由程序所控制，也就是在用户态执行。这样带来的好处是性能大幅度的提升，因为不会像线程切换那样消耗资源。

如果把线程/进程当作虚拟“CPU”，协程即跑在这个“CPU”上的线程。

协程的特点：

占用的资源更少。

所有的切换和调度都发生在用户态。

不管是进程还是线程，每次阻塞、切换都需要陷入系统调用，先让CPU跑操作系统的调度程序，然后再由调度程序决定该跑哪一个线程。而且由于抢占式调度执行顺序无法确定的特点，使用线程时需要非常小心地处理同步问题，而协程完全不存在这个问题。

因为协程可以在用户态显示控制切换

协程的优点是可以用同步的处理方式实现异步回调的性能

一个线程的多个协程的运行是串行的。如果是多核CPU，多个进程或一个进程内的多个线程是可以并行运行的，但是一个线程内协程却绝对是串行的，无论CPU有多少个核。毕竟协程虽然是一个特殊的函数，但仍然是一个函数。一个线程内可以运行多个函数，但这些函数都是串行运行的。当一个协程运行时，其它协程必须挂起。

进程、线程、协程的对比

协程既不是进程也不是线程，协程仅仅是一个特殊的函数，协程它进程和线程不是一个维度的。

一个进程可以包含多个线程，一个线程可以包含多个协程。

一个线程内的多个协程虽然可以切换，但是多个协程是串行执行的，只能在一个线程内运行，没法利用CPU多核能力。

协程与进程一样，切换是存在上下文切换问题的。

上下文切换

进程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户是无感知的。进程的切换内容包括页全局目录、内核栈、硬件上下文，切换内容保存在内存中。进程切换过程是由“用户态到内核态到用户态”的方式，切换效率低。

线程的切换者是操作系统，切换时机是根据操作系统自己的切换策略，用户无感知。线程的切换内容包括内核栈和硬件上下文。线程切换内容保存在内核栈中。线程切换过程是由“用户态到内核态到用户态”，
切换效率中等。

协程的切换者是用户（编程者或应用程序），切换时机是用户自己的程序所决定的。协程的切换内容是硬件上下文，切换内存保存在用户自己的变量（用户栈或堆）中。协程的切换过程只有用户态，即没有陷入内核态，因此切换效率高。

不需要进程/线程上下文切换的“线程”，协程

所以协程的开销远远小于线程的开销因为不需要上下文切换

Goroutine

参考：https://segmentfault.com/a/1190000018150987

Goroutines和线程详解：http://shouce.jb51.net/gopl-zh/ch9/ch9-08.html

Go语言最大的特色就是从语言层面支持并发（Goroutine），Goroutine是Go中最基本的执行单元。事实上每一个Go程序至少有一个Goroutine：主Goroutine。当程序启动时，它会自动创建。

协程不是并发的，而Goroutine支持并发的。因此Goroutine可以理解为一种Go语言的协程。同时它可以运行在一个或多个线程上。

Go实现了两种并发形式。第一种是大家普遍认知的：多线程共享内存。其实就是Java或者C++等语言中的多线程开发。另外一种是Go语言特有的，也是Go语言推荐的：CSP（communicating
sequential processes）并发模型。

CSP讲究的是“以通信的方式来共享内存”。

请记住下面这句话：

DO NOT COMMUNICATE BY SHARING MEMORY; INSTEAD, SHARE MEMORY BY COMMUNICATING.

“不要以共享内存的方式来通信，相反，要通过通信来共享内存。”

Go的CSP并发模型，是通过goroutine和channel来实现的：

goroutine
是Go语言中并发的执行单位。有点抽象，其实就是和传统概念上的”线程“类似，可以理解为”线程“。

channel是Go语言中各个并发结构体(goroutine)之前的通信机制。
通俗的讲，就是各个goroutine之间通信的”管道“，有点类似于Linux中的管道。

在通信过程中，传数据channel <-
data和取数据<-channel必然会成对出现，因为这边传，那边取，两个goroutine之间才会实现通信。

而且不管传还是取，必阻塞，直到另外的goroutine传或者取为止。

（每一个OS线程都有一个固定大小的内存块(一般会是2MB)来做栈，这个栈会用来存储当前正在被调用或挂起(指在调用其它函数时)的函数的内部变量。这个固定大小的栈同时很大又很小。因为2MB的栈对于一个小小的goroutine来说是很大的内存浪费，比如对于我们用到的，一个只是用来WaitGroup之后关闭channel的goroutine来说。而对于go程序来说，同时创建成百上千个goroutine是非常普遍的，如果每一个goroutine都需要这么大的栈的话，那这么多的goroutine就不太可能了。除去大小的问题之外，固定大小的栈对于更复杂或者更深层次的递归函数调用来说显然是不够的。修改固定的大小可以提升空间的利用率允许创建更多的线程，并且可以允许更深的递归调用，不过这两者是没法同时兼备的。

相反，一个goroutine会以一个很小的栈开始其生命周期，一般只需要2KB。一个goroutine的栈，和操作系统线程一样，会保存其活跃或挂起的函数调用的本地变量，但是和OS线程不太一样的是一个goroutine的栈大小并不是固定的；栈的大小会根据需要动态地伸缩。而goroutine的栈的最大值有1GB，比传统的固定大小的线程栈要大得多，尽管一般情况下，大多goroutine都不需要这么大的栈。）

我们先从线程讲起，无论语言层面何种并发模型，到了操作系统层面，一定是以线程的形态存在的。而操作系统根据资源访问权限的不同，体系架构可分为用户空间和内核空间；内核空间主要操作访问CPU资源、I/O资源、内存资源等硬件资源，为上层应用程序提供最基本的基础资源，用户空间呢就是上层应用程序的固定活动空间，用户空间不可以直接访问资源，必须通过“系统调用”、“库函数”或“Shell脚本”来调用内核空间提供的资源。

我们现在的计算机语言，可以狭义的认为是一种“软件”，它们中所谓的“线程”，往往是用户态的线程，和操作系统本身内核态的线程（简称KSE），还是有区别的。

线程模型：

用户级线程模型

内核级线程模型

两级线程模型

Go线程实现模型MPG

（M (thread)也可指内核线程）

M指的是Machine，一个M直接关联了一个内核线程。由操作系统管理。

P指的是”processor”，代表了M所需的上下文环境，也是处理用户级代码逻辑的处理器。它负责衔接M和G的调度上下文，将等待执行的G与M对接。（由环境变量中的GOMAXPROCS决定，通常来说它是和核心数对应）

G指的是Goroutine，其实本质上也是一种轻量级的线程。包括了调用栈，重要的调度信息，例如channel等。

1、P 何时创建：在确定了 P 的最大数量 n 后，运行时系统会根据这个数量创建 n 个 P。

2、M 何时创建：没有足够的 M 来关联 P 并运行其中的可运行的 G。比如所有的 M
此时都阻塞住了，而 P 中还有很多就绪任务，就会去寻找空闲的
M，而没有空闲的，就会去创建新的 M。

以上这个图讲的是两个线程(内核线程)的情况。一个M会对应一个内核线程，一个M也会连接一个上下文P，一个上下文P相当于一个“处理器”，一个上下文连接一个或者多个Goroutine。为了运行goroutine，线程必须保存上下文。

需要P 上下文的目的，是让我们可以直接放开其他线程，当遇到内核线程阻塞的时候。

（全局runqueue是各个P在运行完自己的本地的Goroutine
runqueue后用来拉取新goroutine的地方。P也会周期性的检查这个全局runqueue上的goroutine，否则，全局runqueue上的goroutines可能得不到执行而饿死。）

参考：https://blog.csdn.net/chenchongg/article/details/87605203

详细参考：

http://www.topgoer.com/并发编程/GMP原理与调度.html

特殊的 M0 和 G0

M0 是启动程序后的编为 0 的主线程，这个 M 对应的实例会在全局变量 runtime.m0
中，不需要在 heap 上分配，M0 负责执行初始化操作和启动第一个 G，在之后 M0
就和其他的 M 一样了。

G0 是每次启动一个 M 都会第一个创建的 gourtine，G0 仅用于负责调度的 G，G0
不指向任何可执行的函数，每个 M 都会有一个自己的 G0。在调度或系统调用时会使用 G0
的栈空间，全局变量的 G0 是 M0 的 G0。

均衡的分配工作

按照以上的说法，上下文P会定期的检查全局的goroutine
队列中的goroutine，以便自己在消费掉自身Goroutine队列的时候有事可做。假如全局goroutine队列中的goroutine也没了呢从其他运行的中的P的runqueue里偷。

每个P中的Goroutine不同导致他们运行的效率和时间也不同，在一个有很多P和M的环境中，不能让一个P跑完自身的Goroutine就没事可做了，因为或许其他的P有很长的goroutine队列要跑，得需要均衡。

该如何解决呢/p>

Go的做法倒也直接，从其他P中偷一半！

Goroutine 小结

1、开销小

2、调度性能好

(在Golang的程序中，操作系统级别的线程调度，通常不会做出合适的调度决策。例如在GC时，内存必须要达到一个一致的状态。在Goroutine机制里，Golang可以控制Goroutine的调度，从而在一个合适的时间进行GC
垃圾回收。

在应用层模拟的线程，它避免了上下文切换的额外耗费，兼顾了多线程的优点。简化了高并发程序的复杂度。

缺点：

协程调度机制无法实现公平调度。)

Go面试问题汇总：

https://blog.csdn.net/weixin_34128839/article/details/94488565tm_medium=distribute.pc_relevant_t0.none-task-blog-searchFromBaidu-1.not_use_machine_learn_pai&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-searchFromBaidu-1.not_use_machine_learn_pai

为什么要多线程/h4>

参考：https://www.cnblogs.com/xrq730/p/5060921.html！！！

作用：

（1）发挥多核CPU的优势

（2）防止阻塞

（3）便于建模

数据竞争：

顺序一致性的问题是由于某些程序转换引起的，例如我们的例子中交换了无关变量的访问顺序，这不会改变单线程程序的意图，但是会改变多线程程序的意图（例如例子中允许r1和r2都为0）。

只有当代码允许两个线程同时访问相同的共享数据，并且是以某种冲突的方式访问时（例如当一个线程读取数据的同时另一个线程写入该数据），才有可能察觉到这种程序转换。如果程序强制以特定顺序来访问共享变量，那么我们就无法判断对独立变量的访问是否被重排序，就如同在单线程程序中也无法判断。

无限制地同时访问普通共享变量会让程序变得难以处理，一般需要避免这种情况。坚持完全的顺序一致性对我们没有好处。我们将在下文用单独的一节来讨论这个问题。

惊群效应

惊群效应也有人叫做雷鸣群体效应，不过叫什么，简言之，惊群现象就是多进程（多线程）在同时阻塞等待同一个事件的时候（休眠状态），如果等待的这个事件发生，那么他就会唤醒等待的所有进程（或者线程），但是最终却只可能有一个进程（线程）获得这个时间的“控制权”，对该事件进行处理，而其他进程（线程）获取“控制权”失败，只能重新进入休眠状态，这种现象和性能浪费就叫做惊群。

2.惊群效应到底消耗了什么/p>

我想你应该也会有跟我一样的问题，那就是惊群效应到底消耗了什么/p>

（1）、系统对用户进程/线程频繁地做无效的调度，上下文切换系统性能大打折扣。

（2）、为了确保只有一个线程得到资源，用户必须对资源操作进行加锁保护，进一步加大了系统开销。

是不是还是觉得不够深入，概念化下面：

*1、上下文切换（context
switch）过高会导致cpu像个搬运工，频繁地在寄存器和运行队列之间奔波，更多的时间花在了进程（线程）切换，而不是在真正工作的进程（线程）上面。直接的消耗包括cpu寄存器要保存和加载（例如程序计数器）、系统调度器的代码需要执行。间接的消耗在于多核cache之间的共享数据。

看一下： wiki上下文切换

*2、通过锁机制解决惊群效应是一种方法，在任意时刻只让一个进程（线程）处理等待的事件。但是锁机制也会造成cpu等资源的消耗和性能损耗。目前一些常见的服务器软件有的是通过锁机制解决的，比如nginx（它的锁机制是默认开启的，可以关闭）；还有些认为惊群对系统性能影响不大，没有去处理，比如lighttpd。

解决：

历史上，Linux的accpet确实存在惊群问题，但现在的内核都解决该问题了。即，当多个进程/线程都阻塞在对同一个socket的接受调用上时，当有一个新的连接到来，内核只会唤醒一个进程，其他进程保持休眠，压根就不会被唤醒。

Epoll惊群

主进程创建socket，bind，listen后，将该socket加入到epoll中，然后fork出多个子进程，每个进程都阻塞在epoll_wait上，如果有事件到来，则判断该事件是否是该socket上的事件如果是，说明有新的连接到来了，则进行接受操作。为了简化处理，忽略后续的读写以及对接受返回的新的套接字的处理，直接断开连接。

很多博客中提到，测试表明虽然epoll_wait不会像接受那样只唤醒一个进程/线程，但也不会把所有的进程/线程都唤醒。

解决方案：

这里通常代码加锁的处理机制我就不详述了，来看一下常见软件的处理机制和linux最新的避免和解决的办法

（1）、Nginx的解决：

如上所述，如果采用epoll，则仍然存在该问题，nginx就是这种场景的一个典型，我们接下来看看其具体的处理方法。

nginx的每个worker进程都会在函数ngx_process_events_and_timers()中处理不同的事件，然后通过ngx_process_events()封装了不同的事件处理机制，在Linux上默认采用epoll_wait()。

在主要ngx_process_events_and_timers()函数中解决惊群现象。

（2）、SO_REUSEPORT

Linux内核的3.9版本带来了SO_REUSEPORT特性，该特性支持多个进程或者线程绑定到同一端口，提高服务器程序的性能，允许多个套接字bind()以及listen()同一个TCP或UDP端口，并且在内核层面实现负载均衡。

在使用SO_REUSEPORT后，多个进程可以同时监听同一个IP：端口，然后由内核决定将新链接发送给哪个进程，显然会降低每个工人接收新链接时锁竞争

锁

悲观锁

总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。Java中synchronized和ReentrantLock等独占锁就是悲观锁思想的实现。

乐观锁

总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本机制和CAS算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库提供的类似于write_condition机制，其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。

参考：https://blog.csdn.net/qq_34337272/article/details/81072874

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。

占有和等待：已经得到了某个资源的进程可以再请求新的资源。

不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。

环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

最好解决：鸵鸟策略直接忽略其余参考CSNote

产生死锁的原因主要是：

（1）因为系统资源不足。

（2）进程运行推进的顺序不合适。

（3）资源分配不当等。

产生死锁的四个必要条件：

（1）互斥条件：一个资源每次只能被一个进程使用。

（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。

（4）循环等待条件:若干进程之间形成一种

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！

超详细面试准备（10分钟打遍所有初级后端开发面试）