深入理解多线程概念、同步与无锁机制

admin管理员组

文章数量:1547080

目录

一、线程概念

（一）基本概念理解

（二）逻辑线程 vs 硬件线程

逻辑线程（Logical Thread）

硬件线程（Hardware Thread）

理解示例分析

（三）线程、核心、函数

核心（Core）

线程（Thread）

函数（Function）

示例理解分析

（四）程序、进程、线程、协程

程序（Program）

进程（Process）

线程（Thread）

协程（Coroutine）

二、多线程理念引入

（一）相关概念

时间分片

上下文切换

线程安全函数（Thread-Safe Functions）

可重入函数（Reentrant Functions）

线程私有数据

阻塞和非阻塞

（二）多线程基本必要性分析

（三）多线程应用案例分析

通过多线程并发提升处理能力

通过多线程改变程序编写方式

三、多线程同步

（一）总体概述

为什么需要多线程同步

哪些情况需要同步

多线程同步的方式

（二）串行化

（三）原子操作和原子变量

（四）锁

互斥锁

读写锁

自旋锁

锁的粒度

粗粒度锁

中粒度锁

细粒度锁

锁的范围

死锁

（五）条件变量

（六）非阻塞的lock-free同步机制

CAS loop实现lock-free

无锁数据结构：lock-free stack

非锁实现线程安全或者部分线程安全的常见做法

（七）理解程序序、内存序和乱序执行

（八）理解Store Buffer

（九）理解Invalidate Queue

（十）内存屏障

---

干货分享，感谢您的阅读！

一、线程概念

（一）基本概念理解

线程是计算机程序执行的最小单位，它是进程内的一个独立执行序列。线程是操作系统调度的基本单位，可以并发执行，共享同一进程的资源，如内存空间、文件句柄等。线程通常由操作系统内核进行管理和调度，不同线程之间可以协同工作，实现并发执行，从而提高程序的性能和响应能力。

在多线程编程中，程序可以同时执行多个线程，这些线程可以独立运行，执行不同的任务，或者协同工作以完成一个复杂的任务。每个线程都有自己的执行上下文，包括程序计数器、寄存器、栈等，以便它们能够独立执行，并且可以共享进程的资源，例如全局变量、堆内存等。

线程和进程的主要区别在于，进程是独立的执行环境，拥有自己的内存空间，而线程共享同一进程的内存空间。这意味着线程之间可以更方便地进行数据共享，但也需要更加小心地处理同步和互斥，以避免数据竞争和其他并发问题。

多线程编程在多核处理器上特别有用，因为不同线程可以在不同的核上并行执行，从而充分利用硬件资源。多线程编程也可以提高程序的响应能力，因为它允许程序在执行耗时操作时仍能响应用户输入或其他事件。

总之，线程是程序执行的基本单位，多线程编程已经成为编程领域的标准，有助于提高程序的性能、并发性和响应能力。在多核处理器和现代操作系统的支持下，多线程编程变得更加重要。

（二）逻辑线程 vs 硬件线程

逻辑线程和硬件线程是两个相关但不同的概念，它们在多核处理器中有着不同的作用和功能。

逻辑线程（Logical Thread）

• 逻辑线程是在软件层面模拟出来的线程，通常由操作系统和应用程序共同管理。
• 逻辑线程是程序中执行代码的抽象表示，可以通过多线程编程模型实现。
• 它们允许程序并发执行，但实际的并发性取决于硬件支持和操作系统的调度。
• 逻辑线程之间可以共享同一进程的资源，如内存，文件句柄等。

硬件线程（Hardware Thread）

• 硬件线程是物理处理器核心上的执行单元，通常由多核处理器提供支持。
• 每个硬件线程拥有自己的寄存器、执行单元等硬件资源。
• 硬件线程可以同时执行不同的指令流，从而实现真正的并行处理。

理解示例分析

假设有一台四核的多核处理器，每个核心支持两个硬件线程（具有超线程技术的Intel处理器通常具有这种配置）。这意味着系统有8个硬件线程可供使用。现在，让我们考虑一个运行在这个系统上的图像处理应用程序。

• 逻辑线程示例： 图像处理应用程序是多线程的，具有多个逻辑线程。这些逻辑线程可以并发执行，但由于系统只有4个核心，所以在任何给定时刻只能有4个逻辑线程实际上在硬件上并行运行。操作系统将负责调度这些逻辑线程，以便它们共享CPU时间片，并实现并发性。

• 硬件线程示例： 在这种情况下，系统具有8个硬件线程。如果图像处理应用程序经过适当的优化，可以充分利用这些硬件线程。这意味着在同一时刻，可以有多个图像处理任务同时在硬件上并行执行，而不需要依赖操作系统的调度。

总之，逻辑线程是在软件层面模拟的线程，而硬件线程是在物理硬件上的执行单元。多核处理器通常支持多个硬件线程，这使得并行计算更加高效，但要充分利用这些硬件线程，需要适当地设计和优化多线程应用程序。

（三）线程、核心、函数

线程、核心和函数之间有密切的关系，特别在多核处理器上执行多线程应用程序时，这些概念之间的互动非常重要。

核心（Core）

• 核心是多核处理器的物理处理单元，每个核心有自己的处理器、缓存和执行单元。
• 多核处理器可以同时执行多个硬件线程，每个核心可以执行一个或多个硬件线程。

线程（Thread）

• 线程是程序执行的最小单位，是操作系统调度的基本单元。
• 在多核处理器上，多个线程可以并行执行，共享处理器核心的执行资源。
• 一个核心可以执行多个线程，但线程之间需要共享核心的处理资源，并且操作系统会负责线程之间的调度。

函数（Function）

• 函数是程序中的代码单元，它包含一系列指令，执行特定的任务。
• 函数通常由线程执行，它们是程序的逻辑构建块，可以完成各种任务。

示例理解分析

假设有一台四核的多核处理器，每个核心支持两个硬件线程。现在，考虑一个多线程应用程序，该程序处理图像编辑任务，其中有多个函数需要并行执行。这些函数可能包括图像加载、滤镜应用、图像保存等操作。

在这个示例中，线程、核心和函数之间的关系如下：

核心与线程的关系：

• 有四个核心，每个核心可以同时执行两个线程（总共8个硬件线程）。
• 多线程应用程序可以创建多个线程，这些线程可以在四个核心上并行执行，共享核心的处理资源。

线程与函数的关系：

• 每个线程执行应用程序的不同函数，如图像加载、滤镜应用等。
• 每个函数代表了应用程序的不同任务，可以并行执行，以提高整体性能。

例如，在图像编辑应用程序中，一个线程可以负责图像加载，另一个线程可以负责应用滤镜，第三个线程可以负责图像保存。这些线程可以在四个核心上并行执行，从而加速整个图像编辑过程，提高程序的性能和响应能力。

总之，在多核处理器上，线程和函数之间的关系由操作系统和应用程序的多线程编程来管理，充分利用核心的并行性可以提高应用程序的性能。

（四）程序、进程、线程、协程

程序、进程、线程和协程是计算机编程和操作系统中的不同概念，它们在程序执行、资源管理和并发处理方面有着不同的作用和特点。

程序（Program）

• 示例：一个文本编辑器的安装文件是一个程序。它只是一个二进制文件，等待用户执行。当用户启动它时，它会创建一个进程来执行。
• 程序是一组指令或代码的集合，它们被编写成源代码，并用编程语言编译或解释成可执行文件。
• 程序是静态的，它只是存储在磁盘上的代码，不执行任何操作。

进程（Process）

• 示例：当运行多个应用程序，如浏览器、文本编辑器和音乐播放器，每个应用程序都是一个独立的进程。它们在操作系统中并行运行，互相独立。
• 进程是程序的运行实例，它包括程序的执行代码、数据、内存空间和系统资源。
• 进程是操作系统的基本执行单位，每个进程有独立的内存空间，不能直接访问其他进程的内存。
• 进程之间需要进行通信，通常通过进程间通信（IPC）机制实现。

线程（Thread）

• 示例：一个多线程的文本编辑器可以使用一个线程来处理用户界面的输入和输出，另一个线程来执行文本处理操作，这样可以提高编辑器的响应速度。
• 线程是进程内的执行单元，多个线程共享同一个进程的内存空间和资源。
• 线程之间可以协同工作，实现并发执行，但也需要小心处理同步和互斥问题，以避免数据竞争。
• 线程通常更轻量级，创建和销毁线程的开销较小。

协程（Coroutine）

• 示例：一个网络服务器可以使用协程来同时处理多个客户端请求，而不需要为每个请求创建一个新的线程。这提高了服务器的性能和资源利用率。
• 协程是一种轻量级的并发处理单元，不是由操作系统进行调度，而是由程序自身进行控制。
• 协程可以在一个线程内并行执行，通过协作式多任务处理来实现并发。
• 协程通常用于处理异步任务、事件循环和高度交互式的应用程序。

总之，程序是代码的集合，进程是程序的执行实例，线程是进程内的执行单元，而协程是一种轻量级的并发处理机制。它们在不同的情境下用于实现并发和并行处理，根据需求选择适当的技术有助于提高程序的性能和响应能力。

二、多线程理念引入

（一）相关概念

时间分片

时间分片是操作系统中的一种调度策略，它用于分配处理器时间给多个线程或进程，以使它们能够交替执行，实现多任务并发。基本思想是将CPU时间分成小的时间片，每个时间片分配给一个线程或进程，然后在时间片结束后，将处理器切换到另一个线程或进程，以便它们能够交替执行。这种方式使得每个线程都有机会获得CPU时间，即使有多个线程在运行，也能够有效地共享处理器资源。理解时间分片的方式：

• 轮转调度：时间分片通常与轮转调度算法一起使用。在轮转调度中，每个线程或进程按照轮流的方式获得CPU时间，每个时间片结束后，处理器切换到下一个线程，依此类推。这种方式确保了公平分配CPU时间。

• 公平性：时间分片的一个关键目标是提供公平性，每个线程都有相同的机会来执行。如果一个线程耗尽了其时间片，它将被放到队列的末尾，等待下一轮时间片。

• 防止饥饿：时间分片也有助于防止饥饿现象。饥饿指的是某个线程或进程永远无法获得CPU时间，因为其他线程或进程一直占用CPU。通过时间分片，即使有高优先级的线程，低优先级的线程也会获得一定的CPU时间，以免其饥饿。

举例分析：假设有两个线程A和B，它们需要共享一个单核处理器。如果没有时间分片，线程A可能会一直执行，而线程B永远无法获得CPU时间，导致线程B饥饿。

使用时间分片，处理器将被划分为小的时间片，例如10毫秒。线程A和线程B分别被分配一半的时间片，例如5毫秒。处理器会按照轮转调度的方式，首先执行线程A的5毫秒，然后切换到线程B的5毫秒。这种方式保证了线程A和线程B都有机会执行，而不会出现饥饿现象。

时间分片是多任务处理的基础，它允许多个线程或进程在单个处理器上交替执行，从而实现并发性和公平性。

上下文切换

上下文切换是操作系统中的一个关键概念，它表示在多任务操作系统中，切换正在运行的任务（线程或进程）以执行另一个任务的过程。上下文切换包括保存当前任务的状态（上下文），以便稍后可以恢复该任务的执行，然后切换到另一个任务执行。理解上下文切换的方式：

• 任务切换：上下文切换是任务切换的一部分，任务可以是进程（进程切换）或线程（线程切换）。当操作系统决定切换到另一个任务时，它需要保存当前任务的上下文，包括寄存器值、程序计数器、栈指针等。

• 原因：上下文切换的原因通常有多种，包括任务的时间片用完、任务主动让出CPU、外部中断（如I/O完成）等。上下文切换是为了确保多个任务都有机会执行，并防止其中一个任务占用CPU太长时间。

• 开销：上下文切换不是免费的，它需要一定的CPU时间来保存和恢复任务的上下文。因此，减少不必要的上下文切换对于提高系统性能非常重要。

举例分析：考虑一个多任务操作系统上运行的两个进程：进程A和进程B。这两个进程共享同一个CPU。

• 初始状态：CPU正在执行进程A，进程A的上下文（包括寄存器、程序计数器、栈等）存储在内存中。

• 上下文切换发生：操作系统决定将CPU的执行权从进程A切换到进程B，因为进程A的时间片用完了。在上下文切换过程中，操作系统会保存进程A的上下文到内存，包括当前CPU寄存器的值、程序计数器指向的位置等。

• 切换到进程B：操作系统会从内存中恢复进程B的上下文，包括之前保存的寄存器值、程序计数器的位置。现在CPU开始执行进程B的代码。

• 结束状态：进程B执行完或者时间片用完后，可能会触发下一次上下文切换，切换回进程A，以此类推。

上下文切换是确保多任务操作系统能够有效运行的必要机制，但它也会引入一定的开销。因此，操作系统的调度策略和上下文切换的频率需要合理调整，以平衡系统性能和响应时间。

线程安全函数（Thread-Safe Functions）

线程安全函数是指在多线程环境下，多个线程可以同时调用该函数而不会导致数据竞争或不稳定行为。线程安全函数通常满足以下特点：

• 不使用共享数据：线程安全函数不访问或修改共享数据，如全局变量、静态局部变量、类成员变量等。它们只使用局部变量、参数和线程私有数据。

• 无副作用：线程安全函数不会产生副作用，即不会改变系统状态或共享数据状态。它们的执行只影响函数内部的局部状态。

• 不需要额外同步：线程安全函数不需要额外的同步机制，如互斥锁或信号量，来保护共享数据。

理解线程安全函数的方式是，它们在执行期间不会影响其他线程或共享数据。例如，标准C库函数sqrt(x)是线程安全的，因为它只操作参数x，不修改共享状态。

可重入函数（Reentrant Functions）

可重入函数是线程安全函数的一个更严格子集。可重入函数除了满足线程安全函数的要求外，还具备以下特点：

• 可以被多个线程同时调用：可重入函数不仅是线程安全的，还可以在同一时间被多个线程同时调用，而不会相互干扰。

• 本身是线程安全的：可重入函数内部没有全局状态或静态局部状态，它们只依赖于函数参数和局部变量。

• 适合递归调用：可重入函数可以安全地递归调用自身，因为它们的局部状态不会被递归调用的其他线程干扰。

可重入函数是更加严格的线程安全函数。一个经典的示例是C语言的标准库函数strtok()，它是可重入的。即使多个线程同时调用strtok()来分解不同的字符串，它们之间不会相互干扰。

#include <stdio.h>
#include <string.h>
#include <pthread.h>

void* tokenize(void* str) {
    char* token;
    char* input = (char*)str;
    token = strtok(input, " ");
    while (token != NULL) {
        printf("Token: %s\n", token);
        token = strtok(NULL, " ");
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t thread1, thread2;
    char str1[] = "This is a test";
    char str2[] = "Another example";

    pthread_create(&thread1, NULL, tokenize, (void*)str1);
    pthread_create(&thread2, NULL, tokenize, (void*)str2);

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    return 0;
}

在上面的示例中，strtok()函数被两个线程同时调用来分解不同的字符串，因为strtok()是可重入的，所以它们可以安全地并行执行，不会相互干扰。

线程私有数据

线程私有数据（Thread-Specific Data，TSD）是一种机制，允许在多线程应用程序中为每个线程分配独立的数据存储，以便在不同线程之间共享相同的变量名称，但各线程拥有独立的实例。这可以在多线程编程中非常有用，因为它允许每个线程维护自己的状态，而不会与其他线程产生冲突。以下是一些关于线程私有数据的更清晰的解释：

• 独立存储：线程私有数据允许每个线程拥有独立的存储，这意味着不同线程可以使用相同的变量名，但它们实际上操作的是不同的数据。

• 线程局部存储：线程私有数据提供了一种线程局部存储的机制，使每个线程可以在其中保存自己的数据，而不会干扰其他线程。

• 线程安全：线程私有数据的使用可以帮助确保线程安全，因为每个线程都可以独立管理自己的数据，而不需要额外的同步机制。

在C/C++中，可以使用 thread_local 关键字来定义线程私有数据。以下是一个示例，演示如何使用 thread_local 定义线程私有变量：

#include <iostream>

thread_local int thread_specific_data = 0;

void thread_function() {
    thread_specific_data++;
    std::cout << "Thread-specific data in thread_function: " << thread_specific_data << std::endl;
}

int main() {
    std::thread thread1(thread_function);
    std::thread thread2(thread_function);

    thread1.join();
    thread2.join();

    std::cout << "Thread-specific data in main: " << thread_specific_data << std::endl;

    return 0;
}

示例中，thread_specific_data 是一个线程私有变量，每个线程都有自己独立的 thread_specific_data 副本。当不同线程调用 thread_function 时，它们会分别增加自己的 thread_specific_data 值，而不会影响其他线程。最后在 main 函数中，我们访问了线程私有数据的值，发现它们是各自独立的。这是线程私有数据的典型用例。

阻塞和非阻塞

阻塞和非阻塞是多线程和多进程编程中的两个关键概念，它们描述了线程或进程在执行时如何处理等待某些事件的情况。

阻塞是指线程或进程在等待某个事件发生时，会挂起其执行，暂停等待事件的到来。阻塞通常发生在以下情况：

1. 等待输入/输出（I/O）操作：当线程需要等待某个I/O操作完成（例如从磁盘读取文件或从网络接收数据）时，它可能会被阻塞。

2. 等待锁或信号量：当线程尝试获取一个已被其他线程占用的锁或信号量时，它会被阻塞，直到锁或信号量可用。

3. 等待事件或条件：线程有时需要等待特定事件的发生或某个条件满足，例如等待消息队列中有消息。

理解阻塞的方式是，线程或进程在等待事件发生时会停止执行，直到事件发生才能继续。例如，一个线程在等待从网络接收数据时，它会一直等待直到数据到达，期间不会执行其他任务。案例代码如下：

package org.zyf.javabasic.test.thread;

/**
 * @program: zyfboot-javabasic
 * @description: 阻塞
 * @author: zhangyanfeng
 * @create: 2023-10-21 21:47
 **/
public class BlockingExample {
    public static void main(String[] args) {
        Runnable blockingTask = () -> {
            System.out.println("Blocking task is waiting for 3 seconds...");
            try {
                Thread.sleep(3000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("Blocking task is done!");
        };

        Thread thread = new Thread(blockingTask);
        thread.start();

        try {
            thread.join(); // 主线程等待子线程完成
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Main thread continues.");
    }
}

非阻塞是指线程或进程在等待某个事件发生时，会继续执行其他任务，而不挂起。非阻塞通常发生在以下情况：

1. 轮询：线程或进程可以通过轮询的方式检查事件是否发生，而不是等待事件的到来。这使得线程能够继续执行其他任务。

2. 超时：线程可以设置一个超时时间，在等待事件时，如果超过了这个时间还没有发生事件，线程会继续执行其他任务。

3. 回调函数：线程可以注册回调函数，当事件发生时，系统会调用该回调函数，而线程不需要主动等待事件。

非阻塞允许线程或进程在等待事件时继续执行其他任务。例如，一个线程可以在等待网络数据的同时，继续执行其他计算任务，而不必一直等待。案例代码如下：

package org.zyf.javabasic.test.thread;

/**
 * @program: zyfboot-javabasic
 * @description: 非阻塞
 * @author: zhangyanfeng
 * @create: 2023-10-21 21:48
 **/
public class NonBlockingExample {
    public static void main(String[] args) {
        Runnable nonBlockingTask = () -> {
            System.out.println("Non-blocking task is checking for data...");
            String data = checkForData();
            if (data == null) {
                System.out.println("No data available yet.");
            } else {
                System.out.println("Data received: " + data);
            }
        };

        Thread thread = new Thread(nonBlockingTask);
        thread.start();

        System.out.println("Main thread continues.");
    }

    private static String checkForData() {
        long startTime = System.currentTimeMillis();
        while (System.currentTimeMillis() - startTime < 3000) {
            // 模拟数据到达
            if (System.currentTimeMillis() - startTime >= 2000) {
                return "Sample data";
            }
        }
        return null;
    }
}

（二）多线程基本必要性分析

多线程是一种编程模型，允许一个进程内的多个线程并发执行。每个线程是一个独立的执行流，它可以独立执行不同的任务，共享进程的资源，如内存空间和文件句柄。多线程编程有许多用途，其中一些原因包括：

• 并行计算：多线程允许利用多核处理器来执行多个任务，从而提高整体性能。这对于需要高度计算密集型操作的应用程序非常有用。

• 后台任务处理：将后台任务与主线程分离，以确保主线程保持响应性，这在需要实时响应用户输入的应用程序中非常重要。例如，实现响应式用户界面和实时系统时，多线程可以用于后台数据处理、网络通信等任务，以避免阻塞主线程。

总之，多线程是一种重要的编程工具，它可以提高程序的性能、并发性和响应能力，特别在多核处理器普及的今天，多线程编程已成为编程领域的事实标准。

（三）多线程应用案例分析

通过多线程并发提升处理能力

假设需要编写一个程序，该程序的任务是统计一批文本文件中各单词的出现次数。程序的输入是文件名列表，输出是一个单词到次数的映射。要提高处理能力，打算使用多线程并发处理文件。分析如下：

1. 任务拆分：你可以将文件名列表分为多个子任务，每个子任务负责处理一个或多个文件。这将确保文件的处理被有效地分布到多个线程中。

2. 并行处理：每个线程将独立处理其分配的文件子集，统计单词出现次数，并构建部分结果。这将显著提高处理速度，因为多个文件可以同时被处理。

3. 结果合并：最后，将各个线程生成的部分结果合并成一个最终的单词到次数的映射。这确保了每个单词的总次数正确计算。

Java示例代码：

package org.zyf.javabasic.test.thread;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @program: zyfboot-javabasic
 * @description: 编写一个程序，用于统计一批文本文件的单词出现次数，程序的输入是文件名列表，输出一个单词到次数的映射。
 * @author: zhangyanfeng
 * @create: 2023-10-21 20:56
 **/
public class WordCountMultiThread {
    public static void main(String[] args) {
        String[] fileNames = {"file1.txt", "file2.txt", "file3.txt", "file4.txt"};
        AtomicInteger filesProcessed = new AtomicInteger(0);
        Map<String, AtomicInteger> wordCount = new ConcurrentHashMap<>();

        for (String fileName : fileNames) {
            new Thread(() -> {
                Map<String, AtomicInteger> localWordCount = new ConcurrentHashMap<>();
                try (BufferedReader reader = new BufferedReader(new FileReader(fileName))) {
                    String line;
                    while ((line = reader.readLine()) != null) {
                        String[] words = line.split("\\s+");
                        for (String word : words) {
                            localWordCountputeIfAbsent(word, k -> new AtomicInteger(0)).incrementAndGet();
                        }
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                }
                for (Map.Entry<String, AtomicInteger> entry : localWordCount.entrySet()) {
                    wordCount.merge(entry.getKey(), entry.getValue(), (v1, v2) -> new AtomicInteger(v1.get() + v2.get()));
                }
                if (filesProcessed.incrementAndGet() == fileNames.length) {
                    // All threads have processed their files, print the final word count
                    wordCount.forEach((key, value) -> System.out.println(key + ": " + value));
                }
            }).start();
        }
    }
}

示例代码展示了如何使用多线程并发处理文本文件以统计单词出现次数。每个线程处理一个文件，并使用ConcurrentHashMap来保存各个线程的部分结果。最后，所有部分结果会被合并到一个最终的单词到次数的映射中，并输出结果。这种多线程的实现方式可以大大提高处理大量文件的效率。

通过多线程改变程序编写方式

需要编写一个程序，该程序在执行密集计算的同时，需要监控标准输入（键盘）以接收用户的输入命令。但如果获取键盘输入的调用是阻塞的，当没有输入时，它会导致其他逻辑无法执行。想通过多线程的方式来处理这个问题，以确保密集计算和键盘输入的监控能够同时进行。

分析：

为了同时执行密集计算和监控键盘输入，可以使用多线程。一个线程可以负责执行密集计算，而另一个线程可以负责监控键盘输入。这可以避免键盘输入的阻塞对程序的影响，因为监控输入的线程可以定期检查输入，而不会阻塞程序的其他部分。

Java示例代码：

package org.zyf.javabasic.test.thread;

import java.util.Scanner;

/**
 * @program: zyfboot-javabasic
 * @description: 需要编写一个程序，该程序在执行密集计算的同时，需要监控标准输入（键盘）以接收用户的输入命令。
 * 但如果获取键盘输入的调用是阻塞的，当没有输入时，它会导致其他逻辑无法执行。
 * 通过多线程的方式来处理这个问题，以确保密集计算和键盘输入的监控能够同时进行。
 * @author: zhangyanfeng
 * @create: 2023-10-21 21:05
 **/
public class ConcurrentInputAndCompute {
    public static void main(String[] args) {
        Thread inputThread = new Thread(() -> {
            Scanner scanner = new Scanner(System.in);
            while (true) {
                if (scanner.hasNextLine()) {
                    String input = scanner.nextLine();
                    // 在这里解析和执行用户输入的命令
                    System.out.println("Command received: " + input);
                }
            }
        });

        Thread computeThread = new Thread(() -> {
            // 这里执行密集计算任务
            for (int i = 0; i < 1000000; i++) {
                // 模拟密集计算
            }
        });

        inputThread.start();
        computeThread.start();

        try {
            inputThread.join();
            computeThread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

这个示例中，inputThread 负责监控键盘输入，它会定期检查是否有输入，并解析执行用户的命令。computeThread 负责执行密集计算任务。通过使用多线程，这两个任务可以并行执行，而不会相互阻塞。此外，使用 Scanner 类来监控键盘输入的方式是非阻塞的，它不会导致程序阻塞在等待用户输入的调用上。

三、多线程同步

（一）总体概述

多线程同步是多线程编程中的一个关键概念，它用于确保在多个线程同时访问共享资源或执行任务时，能够协调线程之间的操作，避免数据不一致、竞争条件、死锁等问题的发生。

为什么需要多线程同步

在多线程编程中，有多个线程并发执行，它们可以同时访问和修改共享数据或共享资源。这种并发访问可能导致以下问题：

• 竞争条件（Race Condition）：当多个线程同时尝试读取或写入共享数据时，由于执行顺序不确定，可能导致不一致的数据状态。

• 数据不一致性：如果一个线程正在修改共享数据，而另一个线程同时访问相同的数据，可能导致数据不一致，这对某些应用程序可能是严重问题。

• 死锁：当多个线程相互等待对方释放资源时，可能导致死锁，使所有线程无法继续执行。

哪些情况需要同步

• 多个线程访问共享数据：当多个线程需要同时访问和修改共享数据时，需要同步以防止竞争条件。

• 协作：在某些情况下，多个线程需要协调它们的执行顺序，以确保在正确的时间点进行同步操作，例如生产者-消费者问题。

• 临界区：某些代码段（临界区）必须在任何时刻只能由一个线程执行，以避免数据损坏或竞争条件。

多线程同步的方式

• 互斥锁：使用互斥锁来保护共享数据，只有获得锁的线程可以访问数据。

• 信号量：信号量是一种用于控制同时访问共享资源的方法，可以用于控制并发线程的数量。

• 条件变量：条件变量允许线程等待某个条件的发生，直到满足条件时才继续执行。

• 读写锁：读写锁允许多个线程同时读取共享数据，但只有一个线程可以写入数据。

• 原子操作：使用原子操作可以确保某些操作是不可中断的，防止竞争条件。

多线程同步是多线程编程的复杂但重要部分，它有助于确保多线程应用程序的正确性和稳定性。

（二）串行化

串行化是一种约束，它确保在多线程编程中，共享资源或临界区的访问是按照某种顺序进行的，而不是并发进行。这个概念非常关键，因为它有助于避免竞争条件和数据不一致问题。

串行化实际上是一种顺序执行的机制，它确保在任何时刻只有一个线程能够访问共享资源，直到该线程完成对资源的访问。其他线程必须等待，直到资源变得可用。这样，可以避免竞争条件，确保数据的一致性。

让我们以一个简单的例子来说明串行化的概念。假设有一个共享的计数器，多个线程都希望递增它。如果没有串行化，多个线程可以同时递增计数器，导致竞争条件。通过串行化，我们可以确保每个线程按顺序访问计数器，而不会出现竞争条件。

package org.zyf.javabasic.test.thread;

/**
 * @program: zyfboot-javabasic
 * @description: 串行化的概念
 * @author: zhangyanfeng
 * @create: 2023-10-21 22:03
 **/
public class SerializationExample {
    private int counter = 0;

    // 串行化访问计数器的方法
    public synchronized void incrementCounter() {
        counter++;
    }

    public int getCounter() {
        return counter;
    }

    public static void main(String[] args) {
        SerializationExample example = new SerializationExample();
        Runnable incrementTask = () -> {
            for (int i = 0; i < 1000; i++) {
                example.incrementCounter();
            }
        };

        Thread thread1 = new Thread(incrementTask);
        Thread thread2 = new Thread(incrementTask);

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final counter value: " + example.getCounter());
    }
}

incrementCounter 方法使用 synchronized 修饰符，确保了对计数器的访问是串行化的。即使有多个线程同时尝试递增计数器，它们也会按顺序进行，不会导致竞争条件。最后，我们得到了正确的计数器值，这是串行化的结果。

（三）原子操作和原子变量

原子操作和原子变量是多线程编程中的关键概念，它们用于确保某些操作是不可分割的，从而避免竞争条件和数据不一致问题。

原子操作：原子操作是不可分割的操作，要么完全执行，要么不执行，没有中间状态。在多线程环境中，原子操作通常由硬件或操作系统提供支持，以确保线程之间不会相互干扰。

原子操作的示例包括递增和递减操作，比如 x++ 和 x--，这些操作在实际执行时是不可分割的。即使多个线程同时尝试执行这些操作，也不会导致竞争条件。

原子变量：原子变量是一种数据结构，它允许多个线程同时访问该变量，而不需要额外的同步机制。原子变量通常是由硬件或操作系统提供的，并支持原子操作。Java中的 AtomicInteger、C/C++中的 std::atomic 就是原子变量的例子。

原子变量的使用非常适合那些需要在多线程环境中进行递增、递减、比较和交换等操作的应用场景。

增加以下理解方式：

• 不可分割性：原子操作是不可分割的，线程不能在操作的中间状态中被中断或切换到其他线程，确保了操作的完整性。

• 竞争条件：原子操作用于避免竞争条件，多个线程可以安全地执行原子操作而不必担心数据不一致。

• 并发访问：原子变量允许多个线程同时访问同一变量，而不需要额外的锁或同步机制。

以下是一个Java示例，演示了如何使用 AtomicInteger 进行原子递增操作：

package org.zyf.javabasic.test.thread;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @program: zyfboot-javabasic
 * @description: 演示了如何使用 AtomicInteger 进行原子递增操作
 * @author: zhangyanfeng
 * @create: 2023-10-21 22:08
 **/
public class AtomicExample {
    public static void main(String[] args) {
        AtomicInteger counter = new AtomicInteger(0);

        Runnable incrementTask = () -> {
            for (int i = 0; i < 1000; i++) {
                counter.incrementAndGet();
            }
        };

        Thread thread1 = new Thread(incrementTask);
        Thread thread2 = new Thread(incrementTask);

        thread1.start();
        thread2.start();

        try {
            thread1.join();
            thread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Final counter value: " + counter.get());
    }
}

AtomicInteger 允许多个线程同时递增计数器，而不需要额外的同步。最后，我们得到了正确的计数器值，这是原子操作和原子变量的结果。

（四）锁

互斥锁

互斥锁是一种用于确保多线程访问共享资源的同步机制，它具有两种状态：已加锁（locked）状态和未加锁（unlocked）状态。互斥锁提供了加锁（acquire）和解锁（release）接口，用于控制对共享资源的访问。

• 加锁（acquire）：当一个线程尝试获取互斥锁时，它会检查互斥锁的状态。如果互斥锁处于未加锁状态，那么该线程可以成功获取锁（将锁设置为已加锁状态），然后继续执行。如果互斥锁处于已加锁状态，那么尝试获取锁的线程将被阻塞，直到互斥锁被解锁。
• 解锁（release）：通过解锁操作，互斥锁的状态从已加锁改变为未加锁。这允许其他线程尝试获取锁。如果有多个线程等待锁，只有一个线程会成功获取锁，然后继续执行，其他等待线程将继续等待。

线程同步流程：

1. 线程A尝试获取互斥锁，如果锁处于未加锁状态，线程A成功获取锁，然后执行它的临界区代码。
2. 其他线程尝试获取锁，但由于锁已被线程A获取，它们被阻塞。
3. 线程A完成了对共享资源的访问，然后释放锁，将其状态改为未加锁。
4. 一个等待的线程B成功获取锁，然后执行它的临界区代码。
5. 如果还有其他等待的线程，它们继续尝试获取锁，只有一个会成功。

这个过程确保了对共享资源的访问是串行化的，避免了竞争条件和数据不一致。互斥锁是多线程编程中的重要工具，用于实现线程同步。

读写锁

读写锁（Read-Write Lock）是一种多线程同步机制，与互斥锁类似，但它提供了更灵活的锁定策略，以优化对共享资源的访问。读写锁具有三种状态：已加读锁状态、已加写锁状态和未加锁状态。对应这三种状态，读写锁提供了三个接口：加读锁、加写锁和解锁。

• 加读锁：如果读写锁处于未加锁状态，线程可以成功获取读锁（将锁设置为已加读锁状态）并继续执行。多个读线程可以同时持有读锁，因为读操作是共享的，不会影响其他读线程。
• 加写锁：如果读写锁处于未加锁状态，线程可以成功获取写锁（将锁设置为已加写锁状态）并继续执行。写锁是互斥的，只有一个线程可以持有写锁，而且当有线程持有写锁时，其他线程无法获取读锁或写锁。
• 解锁：通过解锁操作，读写锁的状态从已加锁状态（无论是读锁还是写锁）变为未加锁状态，从而允许其他线程获取锁。

读写锁的主要优点是它允许多个读线程同时访问共享资源，这提高了并行度，尤其在“读多写少”的场景下，读写锁能显著提高性能。同时，它确保写操作的互斥性，防止多个写线程同时修改资源，避免了数据不一致的问题。

在读写锁的实现中，通常写线程会被优先考虑，以避免读线程饿死写线程的情况。这意味着如果有写线程在等待写锁，后续的读线程可能需要等待。这是为了确保写操作的及时完成，以避免数据不一致。

自旋锁

自旋锁（Spinlock）是一种多线程同步机制，它允许线程在获取锁时忙等待，而不是进入睡眠状态。自旋锁通常在多核或多处理器系统中使用，因为在单核系统中，忙等待可能会导致浪费CPU资源，而在多核系统中，它可以有效地减少线程上下文切换的开销。

自旋锁的核心思想是，在尝试获取锁时，线程会反复检查锁的状态，如果锁是可用的（未被其他线程占用），则线程会获取锁并继续执行，否则线程将一直循环（自旋）等待，直到锁变为可用。

自旋锁通常适用于以下情况：

1. 临界区代码执行时间非常短，线程不愿意进入睡眠状态，以避免睡眠唤醒开销。

2. 线程争夺锁的竞争是短暂的，锁的持有时间不会太长。

3. 在多核或多处理器系统中，自旋锁可以减少线程上下文切换的开销。

4. 自旋锁不适用于单核系统或者临界区代码执行时间较长的情况，因为在这些情况下，忙等待可能会浪费大量CPU资源。

在实际应用中，通常会使用现成的库或标准库中提供的自旋锁实现，而不是手动实现。

锁的粒度

锁的粒度是指对共享资源进行加锁的粒度，它决定了锁的范围，从粗粒度到细粒度不同的锁粒度有不同的优缺点。

粗粒度锁

粗粒度锁是锁住整个共享资源，这意味着只有一个线程可以同时访问整个资源。粗粒度锁适用于以下情况：

• 共享资源的操作非常复杂，无法细分成小的临界区。
• 临界区操作时间很长，锁开销相对较小。
• 锁的管理相对简单。

缺点是粗粒度锁可能会导致性能瓶颈，因为只有一个线程能够访问整个资源，其他线程需要等待。

中粒度锁

中粒度锁是介于粗粒度锁和细粒度锁之间的一种选择，它将共享资源分成多个较小的部分，每个部分可以独立加锁。中粒度锁适用于以下情况：

• 中粒度锁能够减小锁的争用，提高并发性，但需要管理多个锁。
• 共享资源可以分成多个独立的部分，每部分可以被不同的线程访问。
• 部分操作较复杂，需要独占资源，而其他部分可以并发访问。

细粒度锁

细粒度锁是将共享资源划分为更小的粒度，每个粒度可以独立加锁。细粒度锁适用于以下情况：

• 细粒度锁可以最大程度地提高并发性，但需要谨慎管理多个锁，避免死锁等问题。
• 共享资源可以细分成多个小的临界区，每个临界区有独立的锁。
• 并发度要求很高，多个线程可以并发访问不同的临界区。

选择锁的粒度需要根据具体应用场景来决定，通常需要综合考虑性能、并发性、代码复杂性等因素。如果粒度太大，可能会导致性能问题；如果粒度太小，可能会增加代码的复杂性，同时也需要注意锁的管理和锁冲突问题。

锁的范围

确保锁的范围尽量小，最小化持有锁的时间，是一种优化多线程应用程序的关键策略。这有助于减少竞争和锁争用，提高并发性和降低系统的复杂性。以下是一些关于锁的范围和持有时间的最佳实践：

1. 最小化锁的范围：只在必要时锁住共享资源或临界区。避免在整个函数或方法中持有锁，而是将锁的范围限制在真正需要同步的部分。

2. 使用局部变量：如果可能，使用局部变量代替共享变量。局部变量不需要同步，因此可以避免锁的使用。

3. 减小临界区的大小：将共享资源划分为更小的临界区，以便多个线程可以并发访问不同的部分。这有助于减小每个临界区的持有时间。

4. 使用读写锁：对于读多写少的场景，使用读写锁可以允许多个线程并发读取，从而减小写操作的锁范围和持有时间。

5. 避免嵌套锁：尽量避免在一个锁内部获取另一个锁，因为这可能导致死锁。如果需要多个锁，使用适当的锁顺序来减小死锁的风险。

6. 使用无锁数据结构：某些情况下，可以使用无锁的数据结构，如CAS（Compare and Swap）操作，来避免锁的使用，从而降低锁范围和持有时间。

7. 考虑并发性和性能：在设计和编写多线程应用程序时，考虑并发性和性能需求，以确定何时需要锁，何时可以避免锁，以及如何最小化锁的范围和持有时间。

8. 使用工具和分析：使用工具和分析技术来识别潜在的锁竞争和性能问题，以便优化应用程序的多线程性能。

通过最小化锁的范围和持有时间，可以提高多线程应用程序的性能、可伸缩性和可维护性，同时减少潜在的并发性问题。这需要谨慎的设计和编码，以确保线程安全性并充分利用多核和多处理器系统的潜力。

死锁

死锁是多线程编程中一种常见的问题，它发生时，两个或多个线程相互等待对方释放资源或锁，导致程序无法继续执行。死锁通常由两种经典原因引起：

1. ABBA锁（资源互锁）：

   这种情况涉及两个或多个资源和对应的锁。线程1获得了锁A，然后尝试获得锁B，而线程2获得了锁B，然后尝试获得锁A。由于线程1持有锁A且等待锁B，线程2持有锁B且等待锁A，它们相互阻塞，无法继续执行。这种情况需要谨慎设计锁的顺序或使用尝试锁定来避免。

2. 自死锁（自己等待自己）：

   在某些情况下，线程可能尝试多次获得同一个锁，而在第二次尝试时，它已经持有了该锁。这种情况下，线程将永远等待自己释放锁，导致死锁。这种情况通常发生在递归函数中，如果不小心编写了无限递归的代码，可能会导致自死锁。

解决死锁的方法包括：

• 锁排序：确保线程按照相同的顺序获得锁，以避免ABBA锁。

• 超时：为尝试获得锁设置超时，如果超过一定时间仍然无法获得锁，线程可以执行回退操作。

• 死锁检测和恢复：实现机制来检测死锁，一旦检测到死锁，可以释放某些锁以解除死锁。

• 减小锁的范围和持有时间：尽量减小锁的范围和持有时间，以减少发生死锁的机会。

• 使用无锁数据结构：无锁数据结构可以完全避免锁的使用，从而避免死锁。

死锁是一个复杂的问题，需要细心的设计和分析多线程代码以避免。在多线程编程中，了解死锁的原因和如何预防它是非常重要的。

（五）条件变量

条件变量是一种用于线程间同步的机制，通常与互斥锁一起使用。它允许一个或多个线程等待某个条件为真的事件发生，而不是忙等待。条件变量通常用于生产者-消费者模式等场景，其中一组线程等待某个条件成立，而另一组线程负责发出条件变化的信号。

假设你要编写一个网络处理程序，I/O线程从套接字接收字节流，反序列化后产生一个个消息（自定义协议），然后投递到一个消息队列，一组工作线程负责从消息队列取出并处理消息。这是典型的生产者-消费者模式，I/O线程生产消息（往队列put），Work线程消费消息（从队列get），I/O线程和Work线程并发访问消息队列，显然，消息队列是竞争资源，需要同步。

在描述的网络处理程序中，条件变量可以用于实现以下逻辑：

1. 创建一个互斥锁（Mutex）来保护消息队列，确保多个线程不会同时访问队列。

2. 创建一个条件变量，用于等待消息队列非空的条件。

3. I/O线程：当消息准备好后，获取互斥锁，将消息放入队列，然后通过条件变量通知等待的工作线程。

4. 工作线程：当要处理消息时，获取互斥锁，检查消息队列是否为空，如果为空，等待条件变量的信号。一旦收到信号，表示队列非空，获取消息并处理。

// 定义互斥锁和条件变量
Mutex mutex;
CondVar condition;

// 消息队列
Queue<Message> messageQueue;

// I/O线程
void IOTask() {
    while (true) {
        Message message = ReceiveMessageFromSocket();
        LockMutex(&mutex);
        messageQueue.push(message);
        SignalCondition(&condition); // 通知等待的工作线程
        UnlockMutex(&mutex);
    }
}

// 工作线程
void WorkerTask() {
    while (true) {
        LockMutex(&mutex);
        while (messageQueue.empty()) {
            WaitCondition(&condition, &mutex); // 等待条件变量，直到队列非空
        }
        Message message = messageQueue.front();
        messageQueue.pop();
        UnlockMutex(&mutex);
        ProcessMessage(message);
    }
}

这样，工作线程可以在队列为空时进入等待状态，不会消耗 CPU 资源，只有在有新消息时才被唤醒。条件变量的使用可以有效降低系统的 CPU 占用率，因为它允许线程在等待条件满足时进入休眠状态，而不是忙等待。

（六）非阻塞的lock-free同步机制

非阻塞的lock-free同步机制是一种并发编程技术，允许多个线程在争用共享资源时不会被阻塞，而是通过特定算法和原子操作来实现同步。这有助于减少死锁风险、提高并发性能，以及确保线程不会无限等待。关键概念和机制包括：

1. 原子操作：原子操作是不可中断的操作，要么全部执行成功，要么全部失败。它们通常由硬件提供支持，可以用于执行关键的同步操作，如CAS（比较并交换）。

2. CAS（Compare-And-Swap）：CAS是一种原子操作，它比较内存位置的当前值与预期值，如果它们相等，则将新值写入该位置。CAS可用于实现非阻塞的数据结构和算法。

3. 非阻塞数据结构：这些数据结构设计成允许多个线程并发访问而不需要锁定。常见的非阻塞数据结构包括非阻塞队列、非阻塞栈和非阻塞哈希表。

4. 无锁算法：这些算法通过CAS和其他原子操作来实现非阻塞同步。无锁算法是lock-free编程的基础，用于解决复杂的并发问题。

优势：

• 避免了死锁问题，因为线程不会相互阻塞。
• 提高了并发性能，允许更多线程同时执行。
• 适用于高并发和低延迟需求的应用程序。

挑战：

• 编写和理解非阻塞算法通常更复杂。
• 可能需要处理ABA问题，即在执行CAS时值可能被改变两次，但线程不知道。
• 性能高度依赖于硬件和操作系统支持。

非阻塞的lock-free同步机制在需要高性能和低延迟的多线程应用中发挥重要作用，但要小心避免复杂性和潜在的ABA问题。在Java中，可以使用java.util.concurrent包提供的一些非阻塞数据结构和原子操作来支持lock-free编程。

CAS loop实现lock-free

CAS（Compare-And-Swap）是一种常用于实现lock-free算法的原子操作。CAS操作是基于硬件的原子性指令，通常由处理器提供支持，用于在多线程环境中进行无锁同步。CAS操作有助于避免锁的使用，提高并发性能。下面我将详细讲解CAS loop的实现，并提供Java代码示例。

CAS操作的一般形式是：CAS(V, E, N)，其中 V 是要更新的变量，E 是预期值，N 是新值。CAS操作的含义是，如果变量 V 的当前值等于 E，则将 V 的值更新为 N；否则，不执行更新。

CAS loop的基本思想是，不断重复CAS操作，直到操作成功为止，确保只有一个线程能够成功更新共享变量。这可以用于实现各种lock-free数据结构和算法。

下面是一个简单的示例，演示了如何使用CAS loop来实现一个简单的无锁计数器：

package org.zyf.javabasic.test.thread;

import java.util.concurrent.atomic.AtomicInteger;

/**
 * @program: zyfboot-javabasic
 * @description: 如何使用CAS loop来实现一个简单的无锁计数器
 * @author: zhangyanfeng
 * @create: 2023-10-21 22:50
 **/
public class LockFreeCounter {
    private AtomicInteger counter = new AtomicInteger(0);

    public void increment() {
        int expected, newValue;
        do {
            // 读取当前值
            expected = counter.get();
            // 计算新值
            newValue = expected + 1;
        } while (!counterpareAndSet(expected, newValue)); // CAS操作
    }

    public int getValue() {
        return counter.get();
    }

    public static void main(String[] args) {
        LockFreeCounter counter = new LockFreeCounter();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    counter.increment();
                }
            }).start();
        }
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Counter value: " + counter.getValue());
    }
}

在这个示例中，LockFreeCounter类包含一个使用AtomicInteger的计数器，increment方法使用CAS loop来更新计数器的值，确保线程安全。各个线程会并发地执行increment方法，而无需使用锁。

CAS loop的核心思想是通过不断尝试CAS操作，只有一个线程能够成功，从而实现无锁同步。这种方法通常适用于简单的共享变量更新，但要注意避免复杂的ABA问题，确保线程安全。

无锁数据结构：lock-free stack

无锁数据结构，如lock-free stack（无锁栈），是在多线程环境中实现数据结构，无需使用锁进行同步，以确保并发性能和线程安全。下面将详细讲解和分析lock-free stack的实现方式。

Lock-free stack是一个基于链表的数据结构，支持以下操作：

1. push(item): 将元素添加到栈中。
2. pop(): 从栈中弹出元素并返回。
3. isEmpty(): 检查栈是否为空。

Lock-free stack的实现基于CAS（Compare-And-Swap）操作，典型的实现方式是通过原子操作来维护栈的结构。以下是lock-free stack的一种可能实现方式：

package org.zyf.javabasic.test.thread;

import java.util.concurrent.atomic.AtomicReference;

/**
 * @program: zyfboot-javabasic
 * @description: lock-free stack的一种可能实现方式
 * @author: zhangyanfeng
 * @create: 2023-10-21 22:52
 **/
public class LockFreeStack<T> {
    private AtomicReference<Node<T>> head = new AtomicReference<>();

    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        while (true) {
            Node<T> currentHead = head.get();
            newNode.next = currentHead;
            if (headpareAndSet(currentHead, newNode)) {
                return;
            }
        }
    }

    public T pop() {
        while (true) {
            Node<T> currentHead = head.get();
            if (currentHead == null) {
                return null; // 栈为空
            }
            Node<T> newHead = currentHead.next;
            if (headpareAndSet(currentHead, newHead)) {
                return currentHead.data;
            }
        }
    }

    public boolean isEmpty() {
        return head.get() == null;
    }

    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }
}

这个lock-free stack的实现基于CAS操作，push操作通过原子更新head引用来添加元素，pop操作也使用CAS来弹出元素。这确保多线程环境下，栈操作不会发生冲突或竞争条件。即使多个线程同时调用push或pop，只有一个线程会成功，其他线程会不断重试。

这种lock-free stack的实现方式具有无锁的特性，允许多个线程并发执行栈操作而不需要使用锁，提高了并发性能。然而，需要注意的是，lock-free算法的实现相对复杂，需要仔细考虑ABA问题和内存回收等细节。

总的来说，lock-free stack是一种强大的数据结构，适用于需要高度并发的场景，如并发编程和多线程应用程序。

非锁实现线程安全或者部分线程安全的常见做法

名称	简介	常见应用场景	备注
原子赋值	简单类型的对齐读取和写入通常是原子的。 比如 int32、int64	双buffer切换时候的指针赋值； 共享内存中简单类型之间修改	本质上单条处理器指令是原子的 并非所有处理器架构都保证是原子的
简单原子变量(atomic)	通过编译器、语言等实现原子的CPU指令	原生类型的自增自减和立即数赋值等、不强调先后只追求最终结果的正确	gcc、C、C++、Java等都有实现 所有原子类型都不支持拷贝 没有浮点类型的原子变量
CAS(简单原子变量就是一种weak的CAS)	内存屏障	对执行的先后顺序有严格要求	在竞争严重的时候，自旋可能非常浪费CPU
双buffer	在内存中保存两份	更新不频繁的数据	只适用于一写多读的场景
延迟删除双buffer（Double Buffering with Deferred Deletion）	在更新后短期内双buffer，而后删除旧版本，通过指针赋值的原子性切换到新数据	更新不频繁的数据 读多写少的场景	只适用于一写多读的场景
thread_local	每个线程持有一份数据，彻底摆脱线程同步	线程间无需实时交互
per-cpu变量	每个处理器都分配了该变量的副本	绑核后无锁读写	参考：DEFINE_PER_CPU，get_cpu_var等
RCU（Read-Copy-Update）	需要修改时候创建副本，然后切换副本，	读多写少的场景	参见：rcu_read_lock，Userspace RCU​​

可以看到，上面很多做法都是采用了副本，尽量避免在 thread 中间共享数据。最快的同步就是没同步(The fastest synchronization of all is the kind that never takes place)，share nothing is best。

（七）理解程序序、内存序和乱序执行

程序序（Program Order）、内存序（Memory Order）以及乱序执行（Out-of-order Execution）是与多线程和并发编程相关的重要概念，它们有助于理解多线程环境中的指令执行顺序和内存访问规则。

程序序（Program Order）：

程序序是指在源代码中编写的指令的顺序。程序序规定了代码在单线程执行时的顺序，也就是按照代码的编写顺序一个接一个执行。

内存序（Memory Order）：

内存序是多线程环境下的执行顺序。它规定了多线程程序中各个线程对内存的读写操作应当以怎样的顺序呈现给其他线程。内存序定义了各个线程之间的协作和同步方式，以确保多线程程序的正确性。

内存序规定了各个线程访问共享内存时的顺序和一致性，以避免数据竞争和不确定行为。

乱序执行（Out-of-order Execution）：

乱序执行是现代处理器的一种特性，它允许处理器在不改变程序结果的前提下，对指令的执行顺序进行一定的优化。处理器可以根据数据依赖性等因素来重新排列指令的执行顺序，以提高性能。

乱序执行通常与内存序有关，处理器需要确保指令乱序执行的结果对于外部观察者是与程序序和内存序一致的。

在多线程环境中，理解程序序、内存序和乱序执行是非常重要的，因为不遵守正确的内存序规则可能导致数据竞争、死锁等问题。开发者需要使用适当的同步机制，如互斥量、原子操作、条件变量等，来控制程序中各个线程的执行顺序，以确保多线程程序的正确性。此外，了解乱序执行是如何影响程序性能和行为的，有助于编写更高效的代码。

（八）理解Store Buffer

Store Buffer（写缓冲区）是现代处理器架构中的一种关键组件，用于提高内存系统的性能和效率。它是一种硬件机制，用于处理写操作，特别是写内存的操作。

Store Buffer 主要用于解决乱序执行（Out-of-Order Execution）带来的问题。在乱序执行中，处理器会以不同的顺序执行指令，然后将结果重新排序以保持程序的正确性。这可能导致写操作的结果在内存中的顺序与程序中的顺序不同。

Store Buffer 具有以下特征和作用：

1. 缓冲写操作：当处理器执行写操作时，数据被先写入 Store Buffer，而不是立即写入内存。这允许处理器继续执行后续的指令，而不必等待写操作完成。

2. 乱序执行支持：Store Buffer 允许处理器以乱序的方式执行指令，同时确保最终的写入操作按照程序顺序提交到内存。

3. 写合并：如果多个写操作对相同的内存位置进行写入，Store Buffer 可能会合并它们，减少对内存的访问次数。

4. 写序列化：在需要时，Store Buffer 可以保证写操作按程序顺序提交到内存。这是通过将写操作从 Store Buffer 刷新到内存来实现的。

下面是一个伪代码示例，演示 Store Buffer 的作用：

# 线程1执行
WriteValueToMemory(100)   # 将值 100 写入内存

# 线程2执行
WriteValueToMemory(200)   # 将值 200 写入内存

# 线程1执行
ReadValueFromMemory()    # 从内存中读取值

# 线程2执行
ReadValueFromMemory()    # 从内存中读取值

在上述示例中，如果没有 Store Buffer，线程1和线程2的写操作会立即写入内存，可能导致竞争条件。然而，Store Buffer 允许线程1和线程2将写操作缓冲在其中，继续执行后续的读操作。然后，写操作按照程序的顺序（WriteValueToMemory(100) 先于 WriteValueToMemory(200)）提交到内存。

这个示例说明了 Store Buffer 如何支持乱序执行，同时确保最终的内存操作按照程序顺序。在现代处理器中，Store Buffer 是一种关键的性能优化机制，有助于减少内存访问的延迟，并提高程序执行效率。

（九）理解Invalidate Queue

Invalidate Queue（失效队列）是计算机体系结构中一个用于处理缓存一致性（cache coherence）的关键组件。它主要用于多核或多处理器系统中，确保各个核心或处理器的缓存数据与共享内存的一致性。失效队列有助于处理缓存中的数据失效（invalidation）操作，以确保多个处理器对共享数据的修改不会导致数据的不一致性。

失效队列的工作原理和作用如下：

1. 失效通知：当一个处理器核心（或处理器）对某个内存地址的数据进行了修改，它需要通知其他核心或处理器，以便它们更新其缓存中的相同数据。这个通知就是失效通知，它告诉其他核心：它们的缓存中的数据无效或过时了。

2. 失效队列维护：每个核心或处理器都维护一个失效队列，用于跟踪需要失效的缓存数据。当一个核心发出失效通知时，它将通知发送到其他核心的失效队列中，这些核心稍后会处理这些失效通知。

3. 处理失效通知：当一个核心或处理器接收到失效通知时，它检查自己的缓存，标记相应的缓存行为失效状态。如果后续访问了这些数据，该核心将从主存（或其他核心的缓存）重新加载该数据。

失效队列通常包括以下操作：

• 插入：将新的失效通知插入队列中。

• 处理：核心周期性地或在需要时检查队列，并处理队列中的失效通知。处理失效通知可能包括标记缓存中的数据为失效，从主存加载新数据等操作。

• 删除：当队列中的失效通知被处理后，它们可以从队列中删除。

下面是一个简化的伪代码示例，用于说明失效队列的基本工作原理：

# 核心1
InvalidateQueue core1InvalidateQueue

# 核心2
InvalidateQueue core2InvalidateQueue

# 核心1修改了内存地址A的数据
ModifyMemoryAddressA(data)

# 核心1发送失效通知给核心2
core2InvalidateQueue.InsertInvalidateNotice(AddressA)

# 核心2周期性检查失效队列
while not core2InvalidateQueue.IsEmpty():
    invalidatedAddress = core2InvalidateQueue.GetNextInvalidation()
    if invalidatedAddress in core2Cache:
        core2Cache.MarkDataInvalid(invalidatedAddress)

在上述示例中，核心1修改了内存地址A的数据，并发送失效通知给核心2。核心2周期性地检查它的失效队列，当它发现失效通知时，它标记其缓存中的相应数据为失效，以确保后续访问该数据时能够重新加载最新的数据。

失效队列是缓存一致性协议的一部分，它有助于确保多个核心或处理器之间的数据一致性，以避免不一致的缓存访问。这对于多核或多处理器系统中的并发编程至关重要。

（十）内存屏障

内存屏障（Memory Barrier），也称为内存栅栏或内存栅障，是一种编程工具，用于控制内存操作的执行顺序和可见性。内存屏障的作用是确保特定内存操作以期望的方式执行，以避免不正确的并发行为。

内存屏障的主要功能包括：

1. 禁止指令重排序：内存屏障可以阻止编译器和处理器对指令进行重排序。在多线程编程中，正确的指令执行顺序对于共享数据的一致性非常重要。内存屏障确保在内存访问操作之间的指令不会被重新排序。

2. 确保内存可见性：内存屏障可以确保一个线程对共享变量的修改在其他线程中可见。这是通过刷新缓存或禁止缓存操作来实现的，从而确保共享数据的一致性。

内存屏障通常分为以下几种类型：

• 读屏障（Read Barrier）：确保在读取操作之后，之前的写入操作对其他线程可见。

• 写屏障（Write Barrier）：确保在写入操作之后，之后的写入操作对其他线程可见。

• 全屏障（Full Barrier）：同时包括读屏障和写屏障，确保在全屏障之前和之后的操作都不会被重排序。

内存屏障的使用取决于编程语言和硬件架构，不同的编程语言和硬件平台可能提供不同的内存屏障指令或内置函数。

下面是一个简单的伪代码示例，用于说明内存屏障的作用。这里使用了读屏障和写屏障：

# 写操作
def write_operation(data):
    # 写入共享数据
    shared_data = data

    # 写入操作完成后，插入写屏障
    write_barrier()

# 读操作
def read_operation():
    # 读取共享数据
    data = shared_data

    # 读取操作完成后，插入读屏障
    read_barrier()

    # 对共享数据进行处理
    process_data(data)

在上述示例中，write_barrier 和 read_barrier 分别用于确保写操作和读操作的内存可见性和执行顺序。这有助于确保共享数据的正确同步和一致性。

内存屏障在并发编程中扮演着重要的角色，它们帮助开发人员控制内存操作的行为，以避免竞态条件和数据不一致性。在不同的编程语言和平台上，内存屏障的语法和使用方式可能有所不同。因此，在实际编程中，需要根据特定的环境和需求来选择合适的内存屏障类型和使用方式。

本文标签： 多线程机制概念