面试题：C语言Linux定时器组的冲突处理

思路

时间轮算法：使用时间轮数据结构，将时间划分为多个槽位，每个槽位对应一定的时间间隔。定时器根据其触发时间被分配到相应的槽位中。这样，在同一时间间隔内触发的定时器会被放在同一个槽位中，方便统一处理。
优先级队列：使用优先级队列（如最小堆），以定时器的触发时间作为优先级。当定时器触发时间接近或相同时，按照优先级队列的特性，触发时间最早的定时器会优先被处理。
互斥锁：对于共享资源的访问，使用互斥锁进行保护。当一个定时器访问共享资源时，加锁防止其他定时器同时访问，避免资源竞争。

数据结构

时间轮：

struct timer_slot {
    struct timer *head;
    struct timer *tail;
};

struct time_wheel {
    struct timer_slot *slots;
    int wheel_size;
    int current_slot;
};

优先级队列（最小堆）：

struct timer {
    unsigned long expire_time;
    void (*callback)(void *);
    void *data;
    struct timer *next;
};

struct priority_queue {
    struct timer **heap;
    int size;
    int capacity;
};

互斥锁：

pthread_mutex_t mutex;

函数

时间轮相关函数：

// 初始化时间轮
struct time_wheel* init_time_wheel(int size) {
    struct time_wheel *tw = (struct time_wheel*)malloc(sizeof(struct time_wheel));
    tw->wheel_size = size;
    tw->current_slot = 0;
    tw->slots = (struct timer_slot*)malloc(size * sizeof(struct timer_slot));
    for (int i = 0; i < size; i++) {
        tw->slots[i].head = NULL;
        tw->slots[i].tail = NULL;
    }
    return tw;
}

// 添加定时器到时间轮
void add_timer_to_time_wheel(struct time_wheel *tw, struct timer *timer, unsigned long expire_time) {
    int slot = (expire_time + tw->current_slot) % tw->wheel_size;
    if (tw->slots[slot].head == NULL) {
        tw->slots[slot].head = timer;
        tw->slots[slot].tail = timer;
    } else {
        tw->slots[slot].tail->next = timer;
        tw->slots[slot].tail = timer;
    }
}

// 时间轮推进
void advance_time_wheel(struct time_wheel *tw) {
    tw->current_slot = (tw->current_slot + 1) % tw->wheel_size;
    struct timer *timer = tw->slots[tw->current_slot].head;
    while (timer != NULL) {
        struct timer *next = timer->next;
        timer->callback(timer->data);
        free(timer);
        timer = next;
    }
    tw->slots[tw->current_slot].head = NULL;
    tw->slots[tw->current_slot].tail = NULL;
}

优先级队列相关函数：

// 初始化优先级队列
struct priority_queue* init_priority_queue(int capacity) {
    struct priority_queue *pq = (struct priority_queue*)malloc(sizeof(struct priority_queue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->heap = (struct timer**)malloc(capacity * sizeof(struct timer*));
    return pq;
}

// 向优先级队列添加定时器
void add_timer_to_priority_queue(struct priority_queue *pq, struct timer *timer) {
    if (pq->size == pq->capacity) {
        // 可扩展队列大小
        return;
    }
    pq->heap[pq->size++] = timer;
    int index = pq->size - 1;
    while (index > 0 && pq->heap[(index - 1) / 2]->expire_time > pq->heap[index]->expire_time) {
        struct timer *temp = pq->heap[(index - 1) / 2];
        pq->heap[(index - 1) / 2] = pq->heap[index];
        pq->heap[index] = temp;
        index = (index - 1) / 2;
    }
}

// 从优先级队列获取并移除最早到期的定时器
struct timer* get_and_remove_timer_from_priority_queue(struct priority_queue *pq) {
    if (pq->size == 0) {
        return NULL;
    }
    struct timer *timer = pq->heap[0];
    pq->heap[0] = pq->heap[--pq->size];
    int index = 0;
    while (index * 2 + 1 < pq->size) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int smallest = index;
        if (pq->heap[left]->expire_time < pq->heap[smallest]->expire_time) {
            smallest = left;
        }
        if (right < pq->size && pq->heap[right]->expire_time < pq->heap[smallest]->expire_time) {
            smallest = right;
        }
        if (smallest != index) {
            struct timer *temp = pq->heap[index];
            pq->heap[index] = pq->heap[smallest];
            pq->heap[smallest] = temp;
            index = smallest;
        } else {
            break;
        }
    }
    return timer;
}

互斥锁相关函数：

// 初始化互斥锁
void init_mutex() {
    pthread_mutex_init(&mutex, NULL);
}

// 加锁
void lock_mutex() {
    pthread_mutex_lock(&mutex);
}

// 解锁
void unlock_mutex() {
    pthread_mutex_unlock(&mutex);
}

星途面试题库

面试题：C语言Linux定时器组的冲突处理

知识考点

面试题答案

思路

数据结构

函数