面试题：C语言多线程数据共享下的无锁数据结构应用

无锁数据结构原理

原理基于原子操作：无锁数据结构主要利用处理器提供的原子操作指令，比如比较并交换（Compare - And - Swap，CAS）。以无锁队列为例，在入队和出队操作时，通过CAS操作来更新队列的指针，避免使用传统锁机制。例如，当一个线程尝试入队一个新元素时，它首先读取队列尾指针，然后使用CAS尝试将新元素链接到队列尾部并更新尾指针。只有当CAS操作成功时，入队才完成，若失败则说明其他线程同时在修改队列，该线程需要重试。
多线程协作：多个线程可以同时尝试对无锁数据结构进行操作，它们通过原子操作和内存屏障来确保操作的正确性和数据的一致性。不同线程间的操作不会因为锁的竞争而阻塞，从而提高了并发性能。

无锁数据结构优势

提高并发性能：由于没有锁的争用，线程不会因为等待锁而被阻塞，减少了线程上下文切换的开销，使得在高并发场景下能够更高效地处理任务。多个线程可以并行地对数据结构进行操作，提高了系统整体的吞吐量。
避免死锁：传统锁机制容易引发死锁问题，例如多个线程互相持有对方需要的锁且都不释放。无锁数据结构不存在锁的持有和等待关系，从根本上避免了死锁的产生，增强了系统的稳定性。
更好的扩展性：随着线程数量的增加，传统锁机制的性能会急剧下降，而无锁数据结构能够更好地适应多线程环境，在多核处理器上充分发挥并行计算的优势，具有更好的扩展性。

实现简单无锁队列思路

数据结构定义：定义一个结构体表示队列节点，包含数据域和指向下一个节点的指针。再定义一个结构体表示队列，包含头指针和尾指针。

typedef struct Node {
    void* data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* head;
    Node* tail;
} Queue;

初始化操作：初始化队列时，头指针和尾指针都指向一个空节点（哨兵节点）。

Queue* initQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    Node* sentinel = (Node*)malloc(sizeof(Node));
    sentinel->next = NULL;
    queue->head = queue->tail = sentinel;
    return queue;
}

入队操作：
- 创建新节点并填充数据。
- 使用CAS操作尝试将新节点链接到队列尾部并更新尾指针。

void enqueue(Queue* queue, void* data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    while (1) {
        Node* tail = queue->tail;
        Node* next = tail->next;
        if (tail == queue->tail) {
            if (next == NULL) {
                if (__sync_bool_compare_and_swap(&(tail->next), NULL, newNode)) {
                    __sync_bool_compare_and_swap(&(queue->tail), tail, newNode);
                    return;
                }
            } else {
                __sync_bool_compare_and_swap(&(queue->tail), tail, next);
            }
        }
    }
}

出队操作：
- 检查队列是否为空（头指针和尾指针是否相同且头指针的下一个节点为空）。
- 使用CAS操作尝试更新头指针并获取要出队的节点数据。

void* dequeue(Queue* queue) {
    while (1) {
        Node* head = queue->head;
        Node* tail = queue->tail;
        Node* next = head->next;
        if (head == queue->head) {
            if (head == tail) {
                if (next == NULL) {
                    return NULL;
                }
                __sync_bool_compare_and_swap(&(queue->tail), tail, next);
            } else {
                void* data = next->data;
                if (__sync_bool_compare_and_swap(&(queue->head), head, next)) {
                    free(head);
                    return data;
                }
            }
        }
    }
}

内存屏障问题及解决

内存屏障作用：在无锁数据结构中，内存屏障用于确保不同线程对内存的访问顺序符合预期，避免编译器和处理器的优化导致数据不一致。例如，在入队操作中，先将新节点的数据写入内存，然后使用CAS更新指针。如果没有内存屏障，编译器或处理器可能会将这两个操作重排序，导致其他线程看到一个未完全初始化的节点。
解决方法：在GCC中，可以使用__sync_synchronize()来插入一个全内存屏障。在上述代码中，__sync_bool_compare_and_swap本身是一个带有内存屏障语义的原子操作，能够保证在其前后的内存访问不会被重排序。但对于一些复杂的无锁数据结构操作，可能需要额外使用__sync_synchronize()来确保内存一致性。例如，如果在入队和出队操作中有更复杂的逻辑，在关键操作前后插入__sync_synchronize()，以保证数据的正确可见性和操作顺序。

// 示例：在入队操作更复杂时添加内存屏障
void enqueue(Queue* queue, void* data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    while (1) {
        Node* tail = queue->tail;
        Node* next = tail->next;
        if (tail == queue->tail) {
            if (next == NULL) {
                __sync_synchronize();
                if (__sync_bool_compare_and_swap(&(tail->next), NULL, newNode)) {
                    __sync_synchronize();
                    __sync_bool_compare_and_swap(&(queue->tail), tail, newNode);
                    return;
                }
            } else {
                __sync_bool_compare_and_swap(&(queue->tail), tail, next);
            }
        }
    }
}

星途面试题库

面试题：C语言多线程数据共享下的无锁数据结构应用

知识考点

面试题答案

无锁数据结构原理

无锁数据结构优势

实现简单无锁队列思路

内存屏障问题及解决