C++11并发算法

# 1. C++11并发编程的理论基础

C++11引入了对并发编程的支持，这是现代编程语言中不可或缺的一部分。在深入了解C++11并发编程的实践之前，我们必须首先掌握其理论基础。

## 1.1 并发与并行的概念

并发（Concurrency）指的是两个或更多的任务能在重叠的时间段内执行。而并行（Parallelism）则是在同一时刻实际同时执行多个计算任务。在多核心处理器的硬件架构下，实现并行是可能的，但并发可以在单核处理器上通过任务切换实现。

## 1.2 C++11并发编程的优势

使用C++11并发编程的主要优势在于能够更有效地利用多核处理器，减少等待I/O操作的时间，并提供更加流畅的用户体验。此外，C++11的线程库提供了比以往更低的线程创建和管理开销，更精细的控制，以及更安全的内存访问方式。

## 1.3 C++11对并发的支持

C++11通过引入关键字`thread`, `mutex`, `lock_guard`等来支持并发编程。这些关键字与库如`<thread>`, `<mutex>`, `<future>`等结合使用，允许程序员编写安全且高效的并发程序。接下来的章节，我们将深入探讨这些特性的具体应用和实现方式。

# 2. C++11线程管理

## 2.1 创建和控制线程

### 2.1.1 std::thread的使用方法

`std::thread`是C++11中用于创建和管理线程的工具。在C++11之前，C++标准库中没有直接支持多线程的类。`std::thread`提供了一种创建线程并传递参数给线程函数的方法。

要使用`std::thread`，首先需要包含头文件`<thread>`。创建一个`std::thread`对象时，可以传递一个函数和一系列参数给这个线程。下面是一个简单的例子：

#include <iostream>
#include <thread>

void printHello(int number) {
    std::cout << "Hello from thread " << number << std::endl;
}

int main() {
    std::thread t(printHello, 1); // 创建一个线程，执行printHello函数，并传递参数1
    t.join(); // 等待线程t结束
    return 0;
}

在上述代码中，`printHello`函数定义了线程要执行的任务，其中`number`参数用于标识线程。在`main`函数中，我们创建了一个`std::thread`对象`t`，将`printHello`函数和一个整数`1`传递给它。调用`t.join()`是为了确保主函数等待线程`t`完成执行后再继续执行，这在实际应用中是非常重要的，特别是在有资源分配和需要保证线程同步时。

### 2.1.2 线程的启动和.join()的原理

`std::thread`的`join()`方法会阻塞调用它的线程（在本例中是主线程），直到它所加入的线程结束。这个机制对于资源的释放和确保程序的顺序执行至关重要。不调用`join()`或`detach()`可能导致程序异常终止或资源泄露，因为线程对象在`join()`或`detach()`调用之前不会被销毁。

当`join()`被调用时，它实际上做了以下几件事：

- 阻塞当前线程（此处是主线程）直到关联的线程结束。
- 清除线程对象中的线程句柄，使其不再指向任何底层的线程资源。
- 允许线程对象的析构函数安全地执行，因为没有线程仍在运行。

**示例：**

std::thread threadObject(someFunction); // 创建线程
// 执行一些操作，可能需要等待线程完成
threadObject.join(); // 等待线程结束

在多线程程序中，正确地使用`join()`方法可以保证程序的稳定性和效率。需要注意的是，过度使用`join()`可能会降低程序的并发性，因为它阻止了其他任务的并行执行。在决定何时以及如何使用`join()`时，需要权衡程序的同步需求和性能要求。

## 2.2 同步机制

### 2.2.1 互斥锁mutex和lock_guard

在多线程编程中，数据的保护是至关重要的。当多个线程访问同一数据时，如果不能正确同步它们的访问，会导致数据竞争和不一致。为了解决这一问题，C++11引入了互斥锁（`std::mutex`）和互斥锁包装器（`std::lock_guard`）。

`std::mutex`是一种基本的线程同步机制，提供互斥锁定的手段。当一个线程获得一个`std::mutex`对象时，它会锁定该对象，其他尝试锁定同一个`std::mutex`对象的线程将被阻塞，直到该锁被释放。`std::lock_guard`是一个RAII（Resource Acquisition Is Initialization）包装器，它在构造时自动获取指定的互斥锁，在析构时自动释放互斥锁。

以下是使用`std::lock_guard`的示例：

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void printNumber(int number) {
    std::lock_guard<std::mutex> lock(mtx); // lock_guard自动管理互斥锁
    std::cout << "Number: " << number << std::endl;
}

int main() {
    std::thread t1(printNumber, 1);
    std::thread t2(printNumber, 2);

    t1.join();
    t2.join();
    return 0;
}

在这个示例中，我们定义了一个全局的`std::mutex`对象`mtx`。`printNumber`函数通过`std::lock_guard`自动获取和释放互斥锁。这样可以确保每次只有一个线程能够执行`std::cout`操作。因此，即使`printNumber`函数被多个线程调用，输出的数字也不会交错混合。

### 2.2.2 条件变量condition_variable

条件变量是另一种线程同步机制，主要用于协调线程之间的合作关系。在多线程编程中，条件变量允许一个线程等待直到某个条件成立，而其他线程在适当的时候通知该条件成立。

`std::condition_variable`是C++11中处理条件变量的工具。它通常与互斥锁一起使用，互斥锁用于保护共享数据和条件变量本身。

**示例：**

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>

std::queue<int> q;
std::mutex mtx;
std::condition_variable cv;
bool ready = false;

void producer() {
    while (true) {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        std::lock_guard<std::mutex> lock(mtx);
        q.push(1);
        ready = true;
        cv.notify_one();
    }
}

void consumer() {
    while (true) {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, []{ return ready; }); // 等待条件变量通知
        std::cout << q.front() << " ";
        q.pop();
    }
}

int main() {
    std::thread producerThread(producer);
    std::thread consumerThread(consumer);
    producerThread.join();
    consumerThread.join();
    return 0;
}

在上面的例子中，我们创建了一个生产者线程和一个消费者线程。生产者线程在生产数据后会通知条件变量，消费者线程等待条件变量的通知。`std::condition_variable::wait`方法会阻塞调用它的线程，直到条件变量被通知，然后它会重新获取互斥锁，重新检查条件是否成立。这个例子中使用了lambda表达式作为`wait`方法的第二个参数，它是一个谓词，用于在等待之前检查条件。

### 2.2.3 信号量semaphore和futures

信号量是另一种广泛使用的同步机制，可以用来控制对共享资源的访问。C++11并没有直接提供信号量的类，但是我们可以使用`std::counting_semaphore`（在C++20中引入）来模拟传统的信号量行为。

信号量通常有一个内部计数器，当一个线程希望访问共享资源时，它会调用信号量的`wait`方法（有时称为`down`或`P`操作），如果计数器大于零，它会减少计数器并继续；如果计数器为零，则线程会阻塞，直到计数器变为非零。

**示例：**

#include <semaphore>
#include <iostream>
#include <thread>
#include <chrono>

std::counting_semaphore<3> sem(3); // 信号量初始化为3

void task(int id) {
    sem.acquire(); // 等待信号量
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "Task " << id << " running." << std::endl;
    sem.release(); // 释放信号量
}

int main() {
    std::vector<std::thread> threads;
    for (int i = 0; i < 10; ++i) {
        threads.emplace_back(task, i);
    }
    for (auto& t : threads) {
        t.join();
    }
    return 0;
}

在这个示例中，我们创建了一个`std::counting_semaphore`，并将它的最大计数初始化为3。这意味着最多允许3个线程同时进入临界区。每个线程在执行任务前会尝试获取信号量，在完成后会释放信号量。这保证了我们不会超过信号量的最大值。

对于futures，C++11中通过`std::async`和`std::future`提供了异步计算的机制。Future是一个对象，它存储了异步操作的结果，你可以查询它，等待它，或者从它获取值。你可以使用`std::async`来启动一个异步任务，并返回一个`std::future`对象，该对象可以用来查询异步操作的结果。

**示例：**

#include <future>
#include <iostream>

int computeValue() {
    // 模拟耗时操作
    std::this_thread::sleep_for(std::chrono::seconds(2));
    return 42;
}

int main() {
    std::future<int> result = std::async(std::launch::async, computeValue);
    std::cout << "Waiting for result..." << std::endl;
    std::cout << "Result: " << result.get() << std::endl; // 获取异步操作的结果
    return 0;
}

在该示例中，`computeValue`函数模拟了一个耗时的计算，而`main`函数使用`std::async`来启动一个异步任务。返回的`std::future<int>`对象`result`可以在将来某个时刻用来获取`computeValue`函数的返回值。

## 2.3 线程本地存储

### 2.3.1 thread_local关键字的使用

`thread_local`存储类说明符为每个线程分配存储空间，使得在不同线程中，即使是相同的代码段，变量也不会共享。线程本地存储是一种避免多线程竞争条件的手段，当多个线程访问一个变量时，如果该变量是`thread_local`的，那么每个线程都会拥有该变量的一个副本，因此不会有数据竞争。

在C++11中，`thread_local`可以用于全局变量、静态局部变量或静态类成员变量，它声明了一个线程本地的变量，这个变量在每个线程中都有其独立的存储空间。

**示例：**

#include <iostream>
#include <thread>

thread_local int tl_var = 100;

void threadFunc() {
    ++tl_var; // 每个线程都会增加tl_var的副本
}

int main() {
    std::thread t1(threadFunc);
    std::thread t2(threadFunc);

    t1.join();
    t2.join();

    std::cout << "Thread 1: " << tl_var << std::endl; // 输出101
    std::cout << "Thread 2: " << tl_var << std::endl; // 输出101

    return 0;
}

在这个示例中，每个线程都将`tl_var`变量增加1，但是因为`tl_var`是`thread_local`的，所以每个线程都有自己的`tl_var`副本。即使主线程中也使用了`tl_var`，每个线程对它的修改都不会影响到其他线程中的副本。

### 2.3.2 线程本地存储的应用实例

`thread_local`存储类的一个常见用途是在线程安全的日志记录中。因为日志记录通常涉及到对全局状态的更新，比如日志级别、时间戳等。如果直接使用全局变量，那么在多线程环境下可能会导致数据竞争。通过将这些全局状态声明为`thread_local`，每个线程都会有自己的日志状态副本，从而避免了竞争条件。

**示例：**

#include <iostream>
#include <thread>
#include <mutex>
#include <string>

class Logger {
public:
    Logger(const std::string& logMessage) {
        // 在构造函数中使用线程本地存储的日志信息
        std::lock_guard<std::mutex> lock(mtx); // 同步访问日志文件的代码
        std::cout << "[" << std::this_thread::get_id() << "] " << logMessage << std::endl;
    }

private:
    static thread_local std::string threadLogMessage;
    static std::mutex mtx;
};

// 初始化线程本地存储变量
thread_local std::string Logger::threadLogMessage = "Empty log message";
std::mutex Logger::mtx;

void threadFunction(int id) {
    // 设置线程特定的日志信息
    Logger::threadLogMessage = "Thread " + std::to_string(id);
    Logger log("Thread started");
}

int main() {
    std::thread t1(threadFunction, 1);
    std::th