面试题：C++链表指针在多线程环境下的优化与同步

Question

假设你在多线程环境下使用C++链表结构，多个线程可能同时对链表进行插入、删除和遍历操作。请设计一种方案，使用指针实现链表操作的线程安全，同时尽可能优化性能，减少锁争用。详细描述设计思路、数据结构以及关键代码片段，并分析其在不同场景下的性能表现。

Answer 1

设计思路

1. 细粒度锁：为每个链表节点分配一把锁，这样不同线程对不同节点操作时不会产生锁争用，相比对整个链表加锁大大提高并发性能。
2. 读写锁：对于遍历操作，由于其不修改链表结构，可以允许多个线程同时进行，因此使用读写锁。读操作时，只要没有写操作在进行，多个线程可以同时获取读锁进行遍历；写操作（插入、删除）则需要获取写锁，独占链表节点的访问权。

数据结构

#include <mutex>
#include <shared_mutex>

template <typename T>
struct ListNode {
    T data;
    ListNode* next;
    std::mutex nodeMutex;  // 每个节点自己的互斥锁
    std::shared_mutex readWriteMutex;  // 读写锁
    ListNode(const T& value) : data(value), next(nullptr) {}
};

template <typename T>
class ThreadSafeList {
private:
    ListNode<T>* head;
public:
    ThreadSafeList() : head(nullptr) {}
    ~ThreadSafeList() {
        while (head != nullptr) {
            ListNode<T>* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

关键代码片段

1. 插入操作

void insert(const T& value) {
    std::unique_lock<std::mutex> lock(head->nodeMutex);
    ListNode<T>* newNode = new ListNode<T>(value);
    if (head == nullptr) {
        head = newNode;
    } else {
        ListNode<T>* current = head;
        while (current->next != nullptr) {
            current = current->next;
            std::unique_lock<std::mutex> innerLock(current->nodeMutex);
        }
        current->next = newNode;
    }
}

2. 删除操作

void remove(const T& value) {
    std::unique_lock<std::mutex> lock(head->nodeMutex);
    if (head != nullptr && head->data == value) {
        ListNode<T>* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    ListNode<T>* current = head;
    while (current != nullptr && current->next != nullptr) {
        std::unique_lock<std::mutex> innerLock(current->next->nodeMutex);
        if (current->next->data == value) {
            ListNode<T>* temp = current->next;
            current->next = current->next->next;
            delete temp;
            return;
        }
        current = current->next;
    }
}

3. 遍历操作

void traverse() const {
    std::shared_lock<std::shared_mutex> lock(head->readWriteMutex);
    ListNode<T>* current = head;
    while (current != nullptr) {
        std::cout << current->data << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

性能表现分析

1. 插入和删除操作：由于采用细粒度锁，当链表较长时，不同线程对链表不同位置进行插入或删除操作时，锁争用情况大大减少，相比对整个链表加锁，性能会有显著提升。但每个节点都有锁，会增加一定的内存开销。
2. 遍历操作：使用读写锁，读操作可以并发进行，只要没有写操作在进行，多个线程可以同时遍历链表，提高了遍历的效率。然而，如果频繁有写操作，读操作可能会被阻塞等待写操作完成，导致读操作的延迟增加。