面试题：C语言高性能队列设计

设计思路

数据结构选择：使用链表作为底层数据结构，因为链表在插入和删除操作上具有高效性，适合队列的特点。
内存管理：使用malloc和free进行动态内存分配和释放。为了避免频繁的内存分配和释放带来的性能开销，可以考虑使用内存池技术。
线程安全：采用无锁数据结构来实现线程安全。在无锁队列中，通常使用原子操作来确保对共享资源的安全访问。在C语言中，可以使用<stdatomic.h>头文件提供的原子操作函数。
避免ABA问题：ABA问题是指一个内存位置的值从A变为B，再变回A，在多线程环境下可能导致错误的判断。可以通过引入版本号（epoch）来解决ABA问题。每次对队列进行修改时，版本号加1。

关键代码片段及注释

#include <stdio.h>
#include <stdlib.h>
#include <stdatomic.h>
#include <pthread.h>

// 定义队列节点结构
typedef struct Node {
    int data;
    struct Node *next;
    atomic_int epoch; // 版本号
} Node;

// 定义队列结构
typedef struct Queue {
    atomic_struct Node *head;
    atomic_struct Node *tail;
} Queue;

// 创建新节点
Node* createNode(int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    atomic_store(&newNode->epoch, 0);
    return newNode;
}

// 初始化队列
void initQueue(Queue *queue) {
    Node *sentinel = createNode(-1); // 哨兵节点
    atomic_store(&queue->head, sentinel);
    atomic_store(&queue->tail, sentinel);
}

// 入队操作
void enqueue(Queue *queue, int value) {
    Node *newNode = createNode(value);
    while (1) {
        Node *tail = atomic_load(&queue->tail);
        Node *next = atomic_load(&tail->next);
        if (tail == atomic_load(&queue->tail)) {
            if (next == NULL) {
                if (atomic_compare_exchange_weak(&tail->next, &next, newNode)) {
                    atomic_fetch_add(&newNode->epoch, 1);
                    atomic_compare_exchange_weak(&queue->tail, &tail, newNode);
                    return;
                }
            } else {
                atomic_compare_exchange_weak(&queue->tail, &tail, next);
            }
        }
    }
}

// 出队操作
int dequeue(Queue *queue) {
    while (1) {
        Node *head = atomic_load(&queue->head);
        Node *tail = atomic_load(&queue->tail);
        Node *next = atomic_load(&head->next);
        if (head == atomic_load(&queue->head)) {
            if (head == tail) {
                if (next == NULL) {
                    return -1; // 队列为空
                }
                atomic_compare_exchange_weak(&queue->tail, &tail, next);
            } else {
                int value = next->data;
                if (atomic_compare_exchange_weak(&queue->head, &head, next)) {
                    atomic_fetch_add(&next->epoch, 1);
                    free(head);
                    return value;
                }
            }
        }
    }
}

代码说明

Node结构：包含数据data、指向下一个节点的指针next和版本号epoch。
Queue结构：包含头指针head和尾指针tail，均为原子类型。
createNode函数：创建新节点并初始化数据和版本号。
initQueue函数：初始化队列，创建哨兵节点并将头指针和尾指针指向哨兵节点。
enqueue函数：通过循环和原子操作将新节点添加到队列尾部，并更新版本号。
dequeue函数：通过循环和原子操作从队列头部移除节点，并更新版本号，返回节点中的数据。如果队列为空，返回 -1。

这样设计的无锁队列能够在多线程环境下高效运行，并有效避免ABA问题。

面试题：C语言高性能队列设计

知识考点

面试题答案

设计思路

关键代码片段及注释

代码说明