面试题：C语言Linux复杂定时器场景下定时任务取消的优化

设计思路

数据结构设计：
- 使用优先级队列（如堆）来存储定时任务，这样可以高效地根据优先级取出任务。每个定时任务可以封装成一个结构体，包含任务的优先级、执行时间、任务函数指针等信息。
- 为了方便取消特定优先级的所有任务，我们可以使用一个哈希表，以优先级为键，该优先级对应的所有任务在优先级队列中的索引为值。这样在取消任务时，可以快速定位到特定优先级的任务。
算法设计：
- 添加任务：将任务插入优先级队列，并更新哈希表中对应优先级的任务索引。
- 取消任务：根据优先级从哈希表中获取该优先级任务在优先级队列中的索引，然后从优先级队列中删除这些任务，并更新哈希表。
多线程同步：
- 使用互斥锁（pthread_mutex_t）来保护对优先级队列和哈希表的操作，确保在多线程环境下数据结构的一致性。
- 使用条件变量（pthread_cond_t）来通知等待任务的线程有新任务或任务被取消。

核心代码框架

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>
#include <unordered_map>
#include <vector>

// 定时任务结构体
typedef struct {
    int priority;
    struct timespec execute_time;
    void (*task_func)();
} Task;

// 优先级队列比较函数，用于小顶堆
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority > b.priority;
    }
};

// 全局变量
std::vector<Task> task_queue;
std::unordered_map<int, std::vector<int>> priority_index_map;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

// 调整堆，保持堆的性质
void heapify(int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < task_queue.size() && CompareTask()(task_queue[left], task_queue[smallest])) {
        smallest = left;
    }

    if (right < task_queue.size() && CompareTask()(task_queue[right], task_queue[smallest])) {
        smallest = right;
    }

    if (smallest != index) {
        // 更新哈希表中的索引
        priority_index_map[task_queue[index].priority][index] = smallest;
        priority_index_map[task_queue[smallest].priority][smallest] = index;

        std::swap(task_queue[index], task_queue[smallest]);
        heapify(smallest);
    }
}

// 添加任务到优先级队列
void add_task(Task task) {
    pthread_mutex_lock(&mutex);
    task_queue.push_back(task);
    int index = task_queue.size() - 1;
    if (priority_index_map.find(task.priority) == priority_index_map.end()) {
        priority_index_map[task.priority] = std::vector<int>();
    }
    priority_index_map[task.priority].push_back(index);

    // 向上调整堆
    while (index > 0 && CompareTask()(task_queue[index], task_queue[(index - 1) / 2])) {
        // 更新哈希表中的索引
        priority_index_map[task_queue[index].priority][index] = (index - 1) / 2;
        priority_index_map[task_queue[(index - 1) / 2].priority][(index - 1) / 2] = index;

        std::swap(task_queue[index], task_queue[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
    pthread_cond_signal(&cond);
    pthread_mutex_unlock(&mutex);
}

// 取消特定优先级的所有任务
void cancel_tasks_by_priority(int priority) {
    pthread_mutex_lock(&mutex);
    if (priority_index_map.find(priority) != priority_index_map.end()) {
        for (int index : priority_index_map[priority]) {
            // 将最后一个任务移到要删除的位置
            int last_index = task_queue.size() - 1;
            task_queue[index] = task_queue[last_index];

            // 更新哈希表中的索引
            priority_index_map[task_queue[index].priority][index] = index;
            priority_index_map[task_queue[last_index].priority].pop_back();

            task_queue.pop_back();
            // 调整堆
            if (index < task_queue.size()) {
                heapify(index);
            }
        }
        priority_index_map.erase(priority);
    }
    pthread_mutex_unlock(&mutex);
}

// 模拟任务函数
void sample_task() {
    printf("Task executed\n");
}

// 线程函数，用于执行任务
void* execute_tasks(void* arg) {
    while (1) {
        Task current_task;
        pthread_mutex_lock(&mutex);
        while (task_queue.empty()) {
            pthread_cond_wait(&cond, &mutex);
        }
        current_task = task_queue[0];
        task_queue.erase(task_queue.begin());
        // 更新哈希表中的索引
        priority_index_map[current_task.priority].erase(priority_index_map[current_task.priority].begin());
        pthread_mutex_unlock(&mutex);

        struct timespec now;
        clock_gettime(CLOCK_REALTIME, &now);
        if (now.tv_sec >= current_task.execute_time.tv_sec && now.tv_nsec >= current_task.execute_time.tv_nsec) {
            current_task.task_func();
        }
    }
    return NULL;
}

int main() {
    pthread_t thread;
    pthread_create(&thread, NULL, execute_tasks, NULL);

    // 添加任务示例
    Task task1 = {1, {time(NULL) + 2, 0}, sample_task};
    Task task2 = {2, {time(NULL) + 1, 0}, sample_task};
    add_task(task1);
    add_task(task2);

    // 取消优先级为2的任务
    cancel_tasks_by_priority(2);

    pthread_join(thread, NULL);
    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);
    return 0;
}

上述代码框架实现了在多线程环境下管理不同优先级定时任务，并提供了添加任务和取消特定优先级任务的功能。实际应用中，还可以根据具体需求对代码进行优化和扩展。

星途面试题库

面试题：C语言Linux复杂定时器场景下定时任务取消的优化

知识考点

面试题答案

设计思路

核心代码框架