[数据结构与算法] 队列
我们知道，CPU 资源是有限的，任务的处理速度与线程个数并不不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。
当我们向一个固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程如何处理这个请求？是拒绝请求还是排队请求？各种策略又是怎么实现的呢？
实际上这些问题并不复杂，其底层的数据结构就是队列。
如何理解队列？
队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。
我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。
所以，队列跟栈一样，也是一种操作受限的线性表数据结构。
队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
顺序队列和链式队列
我们知道了，队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那究竟该如何实现一个队列呢？
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。+我们先来看下基于数组的实现方法。我用 Java 语言实现了一下，不过并不包含 Java 语言的高级语法，而且我做了比较详细的注释，你应该可以看懂。
// 用数组实现的队列
public class ArrayQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head 表示队头下标，tail 表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为 capacity 的数组
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 如果 tail == n 表示队列已经满了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出队
public String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
// 为了让其他语言的同学看的更加明确，把 -- 操作放到单独一行来写了
String ret = items[head];
++head;
return ret;
}
}比起栈的数组实现，队列的数组实现稍微有点儿复杂，但是没关系。我稍微解释一下实现思路，你很容易就能明白了。
对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。
你可以结合下面这幅图来理解。当 a、b、c、d+依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 的位置。
当我们调用两次出队操作之后，队列中 head 指针指向下标为 2 的位置，tail 指针仍然指向下标为 4 的位置。
你肯定已经发现了，随着不停地进行入队、出队操作，head 和 tail 都会持续往后移动。当 tail 移动到最右边，即使数组中还有空闲空间，也无法继续往队列中添加数据了。这个问题该如何解决呢？
你是否还记得，在数组那一节，我们也遇到过类似的问题，就是数组的删除操作会导致数组中的数据不连续。你还记得我们当时是怎么解决的吗？对，用数据搬移！但是，每次进行出队操作都相当于删除数组下标为 0 的数据，要搬移整个队列中的数据，这样出队操作的时间复杂度就会从原来的 O(1) 变为 O(n)。能不能优化一下呢？
实际上，我们在出队时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现，就可以轻松解决刚才的问题了。下面是具体的代码：
// 入队操作，将 item 放入队尾
public boolean enqueue(String item) {
// tail == n 表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0，表示整个队列都占满了
if (head == 0) return false;
// 数据搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新 head 和 tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
从代码中我们看到，当队列的 tail 指针移动到数组的最右边后，如果有新的数据入队，我们可以将 head 到 tail 之间的数据，整体搬移到数组中 0 到 tail-head 的位置。
这种实现思路中，出队操作的时间复杂度仍然是 O(1)，但入队操作的时间复杂度还是 O(1) 吗？你可以用我们第 3 节、第 4 节讲的算法复杂度分析方法，自己试着分析一下。
接下来，我们再来看下基于链表的队列实现方法。
基于链表的实现，我们同样需要两个指针：head指针和+tail指针。它们分别指向链表的第一个结点和最后一个结点。如图所示，入队时，tail->=new_node，tail=ail->next；出队时，head=head->next。
循环队列
我们刚才用数组来实现队列的时候，在 tail==n 时，会有数据搬移操作，这样入队操作性能就会受到影响。那有没有办法能够避免数据搬移呢？我们来看看循环队列的解决思路。
循环队列，顾名思义，它长得像一个环。原本数组是有头有尾的，是一条直线。现在我们把首尾相连，扳成了一个环。我画了一张图，你可以直观地感受一下。
我们可以看到，图中这个队列的大小为8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：
通过这样的方法，我们成功避免了数据搬移操作。看起来不难理解，但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有 bug 的循环队列的实现代码，我个人觉得，最关键的是，确定好队空和队满的判定条件。
在用数组实现的非循环队列中，队满的判断条件是 tail==n，队空的判断条件是 head==tail。那针对循环队列，如何判断队空和队满呢？
队列为空的判断条件仍然是 head==tail。但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图，你可以看一下，试着总结一下规律。
就像我图中画的队满的情况，tail=3，head=4，n=8，所以总结一下规律就是：(3+1)%8=4。多画几张队满的图，你就会发现，当队满时，(tail+1)%n=head。
你有没有发现，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。 Talk is cheap，如果还是没怎么理解，那就 show you code 吧。
public class CircularQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head 表示队头下标，tail 表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为 capacity 的数组
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 队列满了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出队
public String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
阻塞队列和并发队列
前面讲的内容理论比较多，看起来很难跟实际的项目开发扯上关系。确实，队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
你应该已经发现了，上述的定义就是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 消费者模型”！
这种基于阻塞队列实现的“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。+而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应对一个“生产者”。
前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？
线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。在实战篇讲 Disruptor 的时候，我会再详细讲并发队列的应用。
解答开篇
队列的知识就讲完了，我们现在回过来看下开篇的问题。线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？
我们一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。我们前面说过，队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢？
基于链表的实现方式，可以实现一个支持无限排队的*队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
内容小结
今天我们讲了一种跟栈很相似的数据结构，队列。关于队列，你能掌握下面的内容，这节就没问题了。
队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。
循环队列是我们这节的重点。要想写出没有 bug 的循环队列实现代码，关键要确定好队空和队满的判定条件，具体的代码你要能写出来。
除此之外，我们还讲了几种高级的队列结构，阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全。
思考
除了线程池这种池结构会用到队列排队请求，你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢？
队列有哪些常见的应用？
1.阻塞队列
1）在队列的基础上增加阻塞操作，就成了阻塞队列。
2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
2.并发队列
1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
3.线程池资源枯竭时的处理
在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
阻塞队列
#ifndef QUEUE_BLOCK_QUEUE_HPP_
#define QUEUE_BLOCK_QUEUE_HPP_
#include <queue>
#include <mutex>
#include <condition_variable>
template <typename T>
class BlockQueue {
public:
using value_type = T;
using container_type = std::queue<value_type>;
using size_type = typename container_type::size_type;
private:
size_type capacity_ = 0;
container_type container_;
mutable std::mutex mutex_;
mutable std::condition_variable not_empty_;
mutable std::condition_variable not_full_;
public:
BlockQueue() = delete;
BlockQueue(const size_type capacity) : capacity_(capacity) {}
BlockQueue(const BlockQueue&) = default;
BlockQueue(BlockQueue&&) = default;
BlockQueue& operator=(const BlockQueue&) = default;
BlockQueue& operator=(BlockQueue&&) = default;
private:
bool empty() const { return container_.empty(); }
bool full() const { return not(container_.size() < capacity_); }
public:
void put(const value_type& item) {
std::unqiue_lock<std::mutex> lock(mutex_);
while (full()) {
not_full_.wait(lock);
}
container_.push(item);
not_empty_.notify_one();
}
void take(value_type& out) {
std::unique_lock<std::mutex> lock(mutex_);
while (empty()) {
not_empty_.wait(lock);
}
out = container_.front();
container_.pop();
not_full_.notify_one();
}
template <typename Duration>
bool put_for(const value_type& item, const Duration& d) {
std::unqiue_lock<std::mutex> lock(mutex_);
if (not_full_.wait_for(lock, d, [&](){ return not full(); })) {
container_.push(item);
not_empty_.notify_one();
return true;
} else {
return false;
}
}
template <typename Duration>
bool take_for(const Duration& d, value_type& out) {
std::unique_lock<std::mutex> lock(mutex_);
if (not_empty_.wait_for(lock, d, [&](){ return not empty(); })) {
out = container_.front();
container_.pop();
not_full_.notify_one();
return true;
} else {
return false;
}
}
};
#endif // QUEUE_BLOCK_QUEUE_HPP_
并发队列
#ifndef QUEUE_CONCURRENCY_QUEUE_HPP_
#define QUEUE_CONCURRENCY_QUEUE_HPP_
#include <queue>
#include <mutex>
#include <condition_variable>
#include <memory>
template <typename T>
class ConcurrencyQueue {
public:
using value_type = T;
using container_type = std::queue<value_type>;
using size_type = typename container_type::size_type;
private:
container_type container_;
mutable std::mutex mutex_;
std::condition_variable container_cond_;
public:
ConcurrencyQueue() = default;
ConcurrencyQueue(const ConcurrencyQueue&) = default;
ConcurrencyQueue(ConcurrencyQueue&&) = default;
ConcurrencyQueue& operator=(const ConcurrencyQueue&) = default;
ConcurrencyQueue& operator=(ConcurrencyQueue&&) = default;
private:
bool empty_() const { return container_.empty(); }
public:
bool empty() const {
std::lock_guard<std::mutex> lg(mutex_);
return container_.empty();
}
void push(value_type item) {
std::lock_guard<std::mutex> lg(mutex_);
container_.push(std::move(item));
container_cond_.notify_one();
}
void wait_and_pop(value_type& out) {
std::unique_lock<std::mutex> lk(mutex_);
while (empty_()) {
container_cond_.wait(lk)
}
out = std::move(container_.front());
container_.pop();
}
std::shared_ptr<value_type> wait_and_pop() {
std::unique_lock<std::mutex> lk(mutex_);
while (empty_()) {
container_cond_.wait(lk)
}
auto res = std::make_shared<value_type>(std::move(container_.front()));
container_.pop();
return res;
}
bool try_pop(value_type& out) {
std::lock_guard<std::mutex> lg(mutex_);
if (empty_()) {
return false;
} else {
out = std::move(container_.front());
container_.pop();
return true;
}
}
std::shared_ptr<value_type> try_pop() {
std::lock_guard<std::mutex> lg(mutex_);
if (empty_()) {
return nullptr;
} else {
auto res = std::make_shared<value_type>(std::move(container_.front()));
container_.pop();
return res;
}
}
};循环队列
#ifndef QUEUE_CIRCULAR_QUEUE_HPP_
#define QUEUE_CIRCULAR_QUEUE_HPP_
template <typename T>
class CircularQueue {
private:
T* items_ = nullptr;
size_t capacity_ = 0;
size_t head_ = 0;
size_t tail_ = 0;
public:
CircularQueue() = delete;
CircularQueue(const size_t capacity) : capacity_(capacity) {
items_ = new T[capacity_];
}
~CircularQueue() {
if (nullptr != items_) {
delete[] items_;
items_ = nullptr;
}
}
CircularQueue(const CircularQueue& other) : capacity_(other.capacity_) {
items_ = new T[capacity_];
for (size_t i = other.head_; i != other.tail_; ++i) {
enqueue(other.items_[i]);
}
}
CircularQueue& operator=(const CircularQueue& rhs) {
delete[] items_;
head_ = 0;
tail_ = 0;
capacity_ = rhs.capacity_;
items_ = new T[capacity_];
for (size_t i = rhs.head_; i != rhs.tail_; ++i) {
enqueue(rhs.items_[i]);
}
return *this;
}
CircularQueue(CircularQueue&& other) : items_(other.items_),
capacity_(other.capacity_),
head_(other.head_),
tail_(other.tail_) {
other.items_ = nullptr;
other.capacity_ = 0;
other.head_ = 0;
other.tail_ = 0;
}
CircularQueue& operator=(CircularQueue&& rhs) {
delete[] items_;
items_ = rhs.items_;
capacity_ = rhs.capacity_;
head_ = rhs.head_;
tail_ = rhs.tail_;
rhs.items_ = nullptr;
rhs.capacity_ = 0;
rhs.head_ = 0;
rhs.tail_ = 0;
return *this;
}
public:
void enqueue(T item) {
if ((tail_ + 1) % capacity_ == head_) {
throw "Push data into a full queue!";
}
items_[tail_] = item;
tail_ = (tail_ + 1) % capacity_;
}
T head() const {
if (head_ != tail_) {
return items_[head_];
} else {
throw "Fetch data from an empty queue!";
}
}
void dequeue() {
if (head_ != tail_) {
head_ = (head_ + 1) % capacity_;
} else {
throw "Pop data from an empty queue!";
}
}
public:
template <typename UnaryFunc>
void traverse(UnaryFunc do_traverse) {
if (0 == capacity_) return;
for (size_t i = head_; i % capacity_ != tail_; ++i) {
do_traverse(items_[i % capacity_]);
}
}
};
动态队列
#ifndef QUEUE_DYNAMIC_ARRAY_QUEUE_HPP_
#define QUEUE_DYNAMIC_ARRAY_QUEUE_HPP_
template <typename T>
class DynamicArrayQueue {
private:
T* items_ = nullptr;
size_t capacity_ = 0;
size_t head_ = 0;
size_t tail_ = 0;
public:
DynamicArrayQueue() = delete;
DynamicArrayQueue(const size_t capacity) : capacity_(capacity) {
items_ = new T[capacity_];
}
~DynamicArrayQueue() {
if (nullptr != items_) {
delete[] items_;
items_ = nullptr;
}
}
DynamicArrayQueue(const DynamicArrayQueue& other) : capacity_(other.capacity_) {
items_ = new T[capacity_];
for (size_t i = other.head_; i != other.tail_; ++i) {
enqueue(other.items_[i]);
}
}
DynamicArrayQueue& operator=(const DynamicArrayQueue& rhs) {
delete[] items_;
head_ = 0;
tail_ = 0;
capacity_ = rhs.capacity_;
items_ = new T[capacity_];
for (size_t i = rhs.head_; i != rhs.tail_; ++i) {
enqueue(rhs.items_[i]);
}
return *this;
}
DynamicArrayQueue(DynamicArrayQueue&& other) : items_(other.items_),
capacity_(other.capacity_),
head_(other.head_),
tail_(other.tail_) {
other.items_ = nullptr;
other.capacity_ = 0;
other.head_ = 0;
other.tail_ = 0;
}
DynamicArrayQueue& operator=(DynamicArrayQueue&& rhs) {
delete[] items_;
items_ = rhs.items_;
capacity_ = rhs.capacity_;
head_ = rhs.head_;
tail_ = rhs.tail_;
rhs.items_ = nullptr;
rhs.capacity_ = 0;
rhs.head_ = 0;
rhs.tail_ = 0;
return *this;
}
public:
void enqueue(T item) {
if (capacity_ == tail_ - head_) {
throw "Push data into a full queue!";
}
if (capacity_ == tail_) {
// item transport
for (size_t i = head_; i != tail_; ++i) {
items_[i - head_] = items_[i];
}
tail_ = tail_ - head_;
head_ = 0;
}
items_[tail_++] = item;
}
T head() const {
if (head_ != tail_) {
return items_[head_];
} else {
throw "Fetch data from an empty queue!";
}
}
void dequeue() {
if (head_ != tail_) {
++head_;
} else {
throw "Pop data from an empty queue!";
}
}
public:
template <typename UnaryFunc>
void traverse(UnaryFunc do_traverse) {
for (size_t i = head_; i != tail_; ++i) {
do_traverse(items_[i]);
}
}
};
#endif // QUEUE_DYNAMIC_ARRAY_QUEUE_HPP_
乐观锁与悲观锁
我们都知道，cpu是时分复用的，也就是把cpu的时间片，分配给不同的thread/process轮流执行，时间片与时间片之间，需要进行cpu切换，也就是会发生进程的切换。切换涉及到清空寄存器，缓存数据。然后重新加载新的thread所需数据。当一个线程被挂起时，加入到阻塞队列，在一定的时间或条件下，在通过notify()，notifyAll()唤醒回来。 在某个资源不可用的时候，就将cpu让出，把当前等待线程切换为阻塞状态。等到资源(比如一个共享数据）可用了，那么就将线程唤醒，让他进入runnable状态等待cpu调度。这就是典型的悲观锁的实现。 独占锁是一种悲观锁，synchronized就是一种独占锁，它假设最坏的情况，认为一个线程修改共享数据的时候其他线程也会修改该数据，因此只在确保其它线程不会造成干扰的情况下执行，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。
但是，由于在进程挂起和恢复执行过程中存在着很大的开销。当一个线程正在等待锁时，它不能做任何事，所以悲观锁有很大的缺点。举个例子，如果一个线程需要某个资源，但是这个资源的占用时间很短，当线程第一次抢占这个资源时，可能这个资源被占用，如果此时挂起这个线程，可能立刻就发现资源可用，然后又需要花费很长的时间重新抢占锁，时间代价就会非常的高。
所以就有了乐观锁的概念，他的核心思路就是，每次不加锁而是假设修改数据之前其他线程一定不会修改，如果因为修改过产生冲突就失败就重试，直到成功为止。 在上面的例子中，某个线程可以不让出cpu，而是一直while循环，如果失败就重试，直到成功为止。所以，当数据争用不严重时，乐观锁效果更好。比如CAS就是一种乐观锁思想的应用。
CAS
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。执行CAS操作的时候，将内存位置的值与预期原值比较，如果相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。
举个CAS操作的应用场景的一个例子，当一个线程需要修改共享变量的值。完成这个操作，先取出共享变量的值赋给A，然后基于A的基础进行计算，得到新值B，完了需要更新共享变量的值了，这个时候就可以调用CAS方法更新变量值了。
在java中可以通过锁和循环CAS的方式来实现原子操作。Java中java.util.concurrent.atomic包相关类就是 CAS的实现，atomic包里包括以下类：
下面我们来已AtomicIneger的源码为例来看看CAS操作：
public final int getAndAdd(int delta) {
for (; ; ) {
int current = get();
int next = current + delta;
if (compareAndSet(current, next))
return current;
}
}这里很显然使用CAS操作（for(;;)里面），他每次都从内存中读取数据，+1操作，然后两个值进行CAS操作。如果成功则返回，否则失败重试，直到修改成功为止。上面源码最关键的地方有两个，一个for循环，它代表着一种宁死不屈的精神，不成功誓不罢休。还有就是compareAndSet：
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}compareAndSet方法内部是调用Java本地方法compareAndSwapInt来实现的，而compareAndSwapInt方法内部又是借助C来调用CPU的底层指令来保证在硬件层面上实现原子操作的。在intel处理器中，CAS是通过调用cmpxchg指令完成的。这就是我们常说的CAS操作（compare and swap）。
CAS的问题
CAS虽然很高效的解决原子操作，但是CAS仍然存在三大问题。ABA问题，循环时间长开销大和只能保证一个共享变量的原子操作。
- ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
- 循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
- 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。
参考：https://www.jianshu.com/p/42989f93105d