定时器

定时器

workflow：workflow/README_cn.md at master · sogou/workflow

C++高并发异步定时器的实现 - 个人文章 - SegmentFault 思否

基于C\C++的多种定时器实现与分析 - 知乎

如何实现一个定时器？看这一篇就够了-CSDN博客

Linux定时器：

深入解析Linux C/C++ Timer定时器的实现核心原理 - 知乎

linux 内核 定时器（timer）实现机制_linux内核定时器-CSDN博客

原理

1.定时器实现

  • 存储定时任务结构
  • 处理定时任务线程

2.定时器数据结构

  • 有序
  • 三种操作：过期执行、插入定时任务、取消定时任务

编程实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 定时任务类，封装任务的所有信息
 */
class TimerTask {
    private final String taskId;
    private long execTime;
    private final Runnable runnable;
    private final boolean isRepeating;
    private final long interval;
    private volatile boolean isCancelled;

    public TimerTask(String taskId, long delay, Runnable runnable, boolean isRepeating, long interval) {
        this.taskId = taskId;
        this.execTime = System.currentTimeMillis() + delay;
        this.runnable = runnable;
        this.isRepeating = isRepeating;
        this.interval = interval;
        this.isCancelled = false;
    }

    public String getTaskId() {
        return taskId;
    }

    public long getExecTime() {
        return execTime;
    }

    public Runnable getRunnable() {
        return runnable;
    }

    public boolean isRepeating() {
        return isRepeating;
    }

    public long getInterval() {
        return interval;
    }

    public boolean isCancelled() {
        return isCancelled;
    }

    public void setCancelled(boolean cancelled) {
        isCancelled = cancelled;
    }

    public void updateNextExecTime() {
        this.execTime = System.currentTimeMillis() + interval;
    }
}

/**
 * 定时器类，管理所有定时任务的执行
 */
public class Timer {
    // 优先队列（最小堆）存储任务，按执行时间排序
    private final PriorityQueue<TimerTask> taskQueue;
    // 线程安全锁
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();
    // 定时器是否运行
    private volatile boolean isRunning;
    // 执行任务的线程
    private Thread workerThread;
    // 线程池用于执行任务，避免任务执行阻塞定时器
    private final ExecutorService executorService;

    public Timer() {
        // 初始化优先队列，按执行时间排序
        this.taskQueue = new PriorityQueue<>(Comparator.comparingLong(TimerTask::getExecTime));
        this.executorService = Executors.newCachedThreadPool();
        this.isRunning = false;
    }

    /**
     * 启动定时器
     */
    public void start() {
        if (isRunning) {
            return;
        }
        isRunning = true;
        workerThread = new Thread(this::runLoop, "Timer-Worker");
        workerThread.start();
    }

    /**
     * 停止定时器
     */
    public void stop() {
        isRunning = false;
        // 唤醒可能在等待的工作线程
        lock.lock();
        try {
            condition.signalAll();
        } finally {
            lock.unlock();
        }
        // 等待工作线程结束
        if (workerThread != null) {
            try {
                workerThread.join();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        // 关闭线程池
        executorService.shutdown();
    }

    /**
     * 添加一次性任务
     * @param delay 延迟时间（毫秒）
     * @param runnable 要执行的任务
     * @return 任务ID
     */
    public String addTask(long delay, Runnable runnable) {
        return addTask(delay, runnable, false, 0);
    }

    /**
     * 添加重复任务
     * @param delay 首次执行延迟时间（毫秒）
     * @param runnable 要执行的任务
     * @param interval 重复执行间隔（毫秒）
     * @return 任务ID
     */
    public String addRepeatingTask(long delay, Runnable runnable, long interval) {
        return addTask(delay, runnable, true, interval);
    }

    /**
     * 添加任务的通用方法
     */
    private String addTask(long delay, Runnable runnable, boolean isRepeating, long interval) {
        if (delay < 0 || (isRepeating && interval <= 0)) {
            throw new IllegalArgumentException("无效的时间参数");
        }
        if (!isRunning) {
            throw new IllegalStateException("定时器未启动");
        }

        String taskId = UUID.randomUUID().toString();
        TimerTask task = new TimerTask(taskId, delay, runnable, isRepeating, interval);

        lock.lock();
        try {
            taskQueue.add(task);
            // 通知工作线程有新任务添加
            condition.signal();
        } finally {
            lock.unlock();
        }

        return taskId;
    }

    /**
     * 取消指定任务
     * @param taskId 任务ID
     * @return 是否取消成功
     */
    public boolean cancelTask(String taskId) {
        lock.lock();
        try {
            // 使用迭代器查找并标记取消的任务
            Iterator<TimerTask> iterator = taskQueue.iterator();
            while (iterator.hasNext()) {
                TimerTask task = iterator.next();
                if (task.getTaskId().equals(taskId)) {
                    task.setCancelled(true);
                    // 从队列中移除已取消的任务
                    iterator.remove();
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 定时器主循环
     */
    private void runLoop() {
        while (isRunning) {
            TimerTask task = null;
            lock.lock();
            try {
                // 清理已取消的任务并获取下一个有效任务
                while (isRunning) {
                    if (taskQueue.isEmpty()) {
                        // 队列空，等待新任务
                        condition.await();
                    } else {
                        task = taskQueue.peek();
                        if (task.isCancelled()) {
                            // 移除已取消的任务
                            taskQueue.poll();
                            task = null;
                        } else {
                            break; // 找到有效任务
                        }
                    }
                }

                if (!isRunning || task == null) {
                    break;
                }

                // 计算需要等待的时间
                long currentTime = System.currentTimeMillis();
                long waitTime = task.getExecTime() - currentTime;

                if (waitTime > 0) {
                    // 等待到任务执行时间或被新任务唤醒
                    condition.await(waitTime, TimeUnit.MILLISECONDS);
                    // 等待结束后需要重新检查任务状态
                    continue;
                } else {
                    // 任务已到执行时间，移除并执行
                    task = taskQueue.poll();
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            } finally {
                lock.unlock();
            }

            // 执行任务
            if (task != null && !task.isCancelled()) {
                executeTask(task);
            }
        }
    }

    /**
     * 执行任务，并处理重复任务
     */
    private void executeTask(TimerTask task) {
        // 在线程池中执行任务，避免阻塞定时器
        executorService.execute(() -> {
            try {
                task.getRunnable().run();
            } catch (Exception e) {
                System.err.println("任务执行出错: " + e.getMessage());
            }
        });

        // 只有重复任务才需要重新加入队列
        if (task.isRepeating() && !task.isCancelled()) {
            task.updateNextExecTime();
            lock.lock();
            try {
                taskQueue.add(task);
                condition.signal();
            } finally {
                lock.unlock();
            }
        }
    }

    // 示例用法
    public static void main(String[] args) throws InterruptedException {
        Timer timer = new Timer();
        timer.start();

        System.out.println("开始执行时间：" + new Date());

        // 添加一次性任务（3秒后执行）
        String oneTimeTaskId = timer.addTask(2000, () ->
                System.out.println("[" + new Date() + "] 执行一次性任务")
        );

        // 添加重复任务（1秒后开始，每2秒执行一次）
        String repeatingTaskId = timer.addRepeatingTask(1000, () ->
                System.out.println("[" + new Date() + "] 执行重复任务"), 2000
        );

        // 运行10秒
        Thread.sleep(10000);

        // 取消重复任务
        boolean cancelled = timer.cancelTask(repeatingTaskId);
        System.out.println("重复任务是否取消成功: " + cancelled);

        // 再运行3秒
        Thread.sleep(3000);

        // 停止定时器
        timer.stop();
    }
}
/**
执行结果：
开始执行时间：Mon Oct 06 21:59:16 CST 2025
[Mon Oct 06 21:59:17 CST 2025] 执行重复任务
[Mon Oct 06 21:59:18 CST 2025] 执行一次性任务
[Mon Oct 06 21:59:19 CST 2025] 执行重复任务
[Mon Oct 06 21:59:21 CST 2025] 执行重复任务
[Mon Oct 06 21:59:23 CST 2025] 执行重复任务
[Mon Oct 06 21:59:25 CST 2025] 执行重复任务
重复任务是否取消成功: true
*/

题目

题目 1：基础定时器

某游戏需要实现战场刷新机制：

  • 每隔 30 秒刷新一波小怪（循环任务）
  • 战斗开始后 5 分钟刷新 boss（单次任务）
  • 支持随时取消未触发的 boss 刷新

请根据以下要求进行作答：

  1. 设计定时器节点的数据结构（包含关键字段）
  2. 选择有序数组或最小堆实现定时器模块，说明选择原因以及时间复杂度
  3. 实现添加定时器逻辑（也可以伪代码，需要处理时间戳排序）

解决：

我将为您实现一个完整的定时器系统，使用最小堆作为底层数据结构。

1. 定时器节点数据结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class TimerTask {
    long executeTime;    // 执行时间戳（毫秒）
    long period;         // 循环间隔（毫秒），0表示单次任务
    Runnable task;       // 任务逻辑
    boolean canceled;    // 是否已取消
    String id;           // 任务ID，用于取消任务
    
    public TimerTask(long executeTime, long period, Runnable task, String id) {
        this.executeTime = executeTime;
        this.period = period;
        this.task = task;
        this.canceled = false;
        this.id = id;
    }
}
2. 数据结构选择及时间复杂度分析

选择：最小堆

原因：

  • 插入效率：最小堆插入为 O(log n)，比有序数组的 O(n) 更高效
  • 获取最近任务：堆顶即为最近要执行的任务，O(1) 时间获取
  • 删除效率：虽然删除任意节点需要 O(n)，但我们可以使用标记删除+延迟清理策略
  • 内存效率：不需要像有序数组那样频繁移动元素

时间复杂度对比：

操作 最小堆 有序数组
插入任务 O(log n) O(n)
获取最近任务 O(1) O(1)
删除任务 O(n) O(n)
执行任务 O(log n) O(n)
3. 完整的定时器实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
import java.util.*;
import java.util.concurrent.*;

public class BattleTimer {
    // 最小堆，按执行时间排序
    private final PriorityQueue<TimerTask> minHeap;
    // 任务映射，用于快速查找和取消
    private final Map<String, TimerTask> taskMap;
    // 工作线程
    private final Thread workerThread;
    private volatile boolean running;
    
    public BattleTimer() {
        // 最小堆，按执行时间排序
        this.minHeap = new PriorityQueue<>(Comparator.comparingLong(task -> task.executeTime));
        this.taskMap = new ConcurrentHashMap<>();
        this.running = true;
        
        // 启动工作线程
        this.workerThread = new Thread(this::run);
        this.workerThread.setDaemon(true);
        this.workerThread.start();
    }
    
    /**
     * 添加定时器任务
     */
    public void addTimer(long delayMs, long periodMs, Runnable task, String taskId) {
        long executeTime = System.currentTimeMillis() + delayMs;
        TimerTask timerTask = new TimerTask(executeTime, periodMs, task, taskId);
        
        synchronized (minHeap) {
            minHeap.offer(timerTask);
            taskMap.put(taskId, timerTask);
            minHeap.notify(); // 通知工作线程有新任务
        }
    }
    
    /**
     * 取消定时器任务
     */
    public boolean cancelTimer(String taskId) {
        synchronized (minHeap) {
            TimerTask task = taskMap.get(taskId);
            if (task != null) {
                task.canceled = true;
                taskMap.remove(taskId);
                return true;
            }
            return false;
        }
    }
    
    /**
     * 工作线程主循环
     */
    private void run() {
        while (running) {
            try {
                TimerTask task = null;
                long currentTime = System.currentTimeMillis();
                long waitTime = 0;
                
                synchronized (minHeap) {
                    // 清理已取消的任务
                    cleanCanceledTasks();
                    
                    // 获取最近的任务
                    while (!minHeap.isEmpty() && minHeap.peek().canceled) {
                        minHeap.poll();
                    }
                    
                    if (minHeap.isEmpty()) {
                        // 没有任务，等待
                        minHeap.wait();
                    } else {
                        task = minHeap.peek();
                        waitTime = task.executeTime - currentTime;
                        
                        if (waitTime <= 0) {
                            // 任务到期，移除并执行
                            task = minHeap.poll();
                            taskMap.remove(task.id);
                        }
                    }
                }
                
                if (waitTime > 0) {
                    // 等待到下一个任务执行时间
                    Thread.sleep(Math.min(waitTime, 1000)); // 最多睡1秒，避免长时间阻塞
                } else if (task != null && !task.canceled) {
                    // 执行任务
                    executeTask(task);
                }
                
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    
    /**
     * 执行任务并处理循环任务
     */
    private void executeTask(TimerTask task) {
        try {
            // 执行任务
            task.task.run();
            
            // 如果是循环任务，重新加入队列
            if (task.period > 0 && !task.canceled) {
                long nextExecuteTime = System.currentTimeMillis() + task.period;
                TimerTask nextTask = new TimerTask(nextExecuteTime, task.period, task.task, task.id);
                
                synchronized (minHeap) {
                    minHeap.offer(nextTask);
                    taskMap.put(task.id, nextTask);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    /**
     * 清理已取消的任务
     */
    private void cleanCanceledTasks() {
        Iterator<TimerTask> iterator = minHeap.iterator();
        while (iterator.hasNext()) {
            TimerTask task = iterator.next();
            if (task.canceled) {
                iterator.remove();
                taskMap.remove(task.id);
            }
        }
    }
    
    /**
     * 停止定时器
     */
    public void stop() {
        running = false;
        workerThread.interrupt();
    }
    
    /**
     * 获取待执行任务数量
     */
    public int getPendingTaskCount() {
        synchronized (minHeap) {
            return minHeap.size();
        }
    }
}
4. 战场刷新机制实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class BattleField {
    private final BattleTimer timer;
    private int waveCount = 0;
    private int bossCount = 0;
    
    public BattleField() {
        this.timer = new BattleTimer();
    }
    
    /**
     * 开始战斗
     */
    public void startBattle() {
        System.out.println("战斗开始！");
        
        // 每隔30秒刷新小怪（循环任务）
        timer.addTimer(0, 30 * 1000, this::refreshMinions, "minion_refresh");
        
        // 5分钟后刷新boss（单次任务）
        timer.addTimer(5 * 60 * 1000, 0, this::refreshBoss, "boss_refresh");
        
        System.out.println("定时器已启动：30秒刷新小怪，5分钟刷新BOSS");
    }
    
    /**
     * 刷新小怪
     */
    private void refreshMinions() {
        waveCount++;
        System.out.println("=== 第 " + waveCount + " 波小怪刷新 ===");
        // 实际的刷新逻辑...
    }
    
    /**
     * 刷新BOSS
     */
    private void refreshBoss() {
        bossCount++;
        System.out.println("!!! BOSS 第 " + bossCount + " 阶段刷新 !!!");
        // 实际的BOSS刷新逻辑...
    }
    
    /**
     * 取消BOSS刷新
     */
    public void cancelBossRefresh() {
        if (timer.cancelTimer("boss_refresh")) {
            System.out.println("BOSS刷新已取消");
        } else {
            System.out.println("BOSS刷新任务不存在或已触发");
        }
    }
    
    /**
     * 停止战斗
     */
    public void stopBattle() {
        timer.stop();
        System.out.println("战斗结束");
    }
    
    /**
     * 测试方法
     */
    public static void main(String[] args) throws InterruptedException {
        BattleField battleField = new BattleField();
        battleField.startBattle();
        
        // 模拟战斗过程
        Thread.sleep(60 * 1000); // 1分钟后
        
        // 测试取消BOSS刷新
        battleField.cancelBossRefresh();
        
        // 继续运行一段时间观察效果
        Thread.sleep(120 * 1000);
        
        battleField.stopBattle();
    }
}
设计要点总结

  1. 最小堆优势：在频繁添加定时任务的场景下，O(log n) 的插入效率明显优于有序数组的 O(n)

  2. 延迟清理策略：通过标记取消+定期清理的方式，避免了在最小堆中直接删除的复杂度问题

  3. 线程安全：使用 synchronized 保证并发安全，合理使用 wait/notify 机制减少CPU占用

  4. 资源管理：提供完整的启动、停止机制，防止内存泄漏

  5. 任务标识：通过任务ID支持精确的任务取消功能

这个实现能够高效地处理战场刷新需求，支持循环任务和单次任务，并提供灵活的任务取消机制。

题目 2：高精度定时器

基于 Linux 开发的战斗服务器中，会需要一些高精度定时器，要求：

  1. 使用 timerfd + epoll 实现高精度定时器（误差 < 1ms）
  2. 定时事件和网络事件在同一线程处理
  3. 支持动态添加 / 删除定时器

请根据以下要求，补全相关编码：

  1. 初始化定时器
1
2
3
4
5
int init_timer(){
    int tfd = timerfd_create(CLOCK_MONOTONIC, TFD_NONBLOCK);
    // 补全：设置30ms周期定时器（itimerspec结构体配置）
    // 补全：将tfd加入epoll实例（EPOLLIN事件）
}
  1. 在epoll事件循环中处理定时器触发：
1
2
3
4
5
6
7
8
9
10
11
void event_loop(){
    while (true){
        int n = epoll_wait(epfd, events, MAX_EVENTS, -1);
        for (int i = 0; i < n; i++){
            if (events[i].data.fd == tfd){
                // 补全：读取tfd计数避免多次触发
                // 补全：执行所有到期定时器回调
            }
        }
    }
}

解决：

完整实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <sys/timerfd.h>
#include <sys/epoll.h>
#include <unistd.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 定时器回调函数类型
typedef void (*timer_callback_t)(void* arg);

// 定时器节点结构
typedef struct timer_node {
    int id;                     // 定时器ID
    long long expire_time;      // 到期时间(毫秒)
    long long interval;         // 间隔时间(毫秒)
    timer_callback_t callback;  // 回调函数
    void* arg;                  // 回调参数
    struct timer_node* next;    // 下一个节点
} timer_node_t;

// 全局变量
static int epfd = -1;
static int tfd = -1;
static timer_node_t* timer_list = NULL;
static int next_timer_id = 1;

// 获取当前时间戳(毫秒)
static long long get_current_time_ms() {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (long long)ts.tv_sec * 1000 + ts.tv_nsec / 1000000;
}

// 初始化定时器
int init_timer() {
    // 创建timerfd
    tfd = timerfd_create(CLOCK_MONOTONIC, TFD_NONBLOCK);
    if (tfd == -1) {
        perror("timerfd_create");
        return -1;
    }

    // 设置30ms周期定时器
    struct itimerspec its;
    its.it_value.tv_sec = 0;
    its.it_value.tv_nsec = 30 * 1000000;  // 30ms
    its.it_interval.tv_sec = 0;
    its.it_interval.tv_nsec = 30 * 1000000;  // 30ms周期

    if (timerfd_settime(tfd, 0, &its, NULL) == -1) {
        perror("timerfd_settime");
        close(tfd);
        return -1;
    }

    // 创建epoll实例
    epfd = epoll_create1(0);
    if (epfd == -1) {
        perror("epoll_create1");
        close(tfd);
        return -1;
    }

    // 将tfd加入epoll实例
    struct epoll_event ev;
    ev.events = EPOLLIN;
    ev.data.fd = tfd;
    if (epoll_ctl(epfd, EPOLL_CTL_ADD, tfd, &ev) == -1) {
        perror("epoll_ctl");
        close(tfd);
        close(epfd);
        return -1;
    }

    printf("定时器初始化成功: timerfd=%d, epollfd=%d, 周期=30ms\n", tfd, epfd);
    return 0;
}

// 添加定时器
int add_timer(long long delay_ms, long long interval_ms, timer_callback_t callback, void* arg) {
    timer_node_t* new_timer = malloc(sizeof(timer_node_t));
    if (!new_timer) {
        return -1;
    }

    new_timer->id = next_timer_id++;
    new_timer->expire_time = get_current_time_ms() + delay_ms;
    new_timer->interval = interval_ms;
    new_timer->callback = callback;
    new_timer->arg = arg;
    new_timer->next = NULL;

    // 按到期时间排序插入链表
    timer_node_t** pp = &timer_list;
    while (*pp && (*pp)->expire_time <= new_timer->expire_time) {
        pp = &(*pp)->next;
    }
    new_timer->next = *pp;
    *pp = new_timer;

    printf("添加定时器: id=%d, delay=%lldms, interval=%lldms\n", 
           new_timer->id, delay_ms, interval_ms);
    return new_timer->id;
}

// 删除定时器
int delete_timer(int timer_id) {
    timer_node_t** pp = &timer_list;
    while (*pp) {
        if ((*pp)->id == timer_id) {
            timer_node_t* to_delete = *pp;
            *pp = to_delete->next;
            free(to_delete);
            printf("删除定时器: id=%d\n", timer_id);
            return 0;
        }
        pp = &(*pp)->next;
    }
    printf("定时器不存在: id=%d\n", timer_id);
    return -1;
}

// 处理到期定时器
static void process_expired_timers() {
    long long current_time = get_current_time_ms();
    
    while (timer_list && timer_list->expire_time <= current_time) {
        timer_node_t* expired = timer_list;
        timer_list = timer_list->next;
        
        // 执行回调
        if (expired->callback) {
            expired->callback(expired->arg);
        }
        
        // 如果是周期定时器，重新插入
        if (expired->interval > 0) {
            expired->expire_time = current_time + expired->interval;
            
            // 按到期时间排序插入
            timer_node_t** pp = &timer_list;
            while (*pp && (*pp)->expire_time <= expired->expire_time) {
                pp = &(*pp)->next;
            }
            expired->next = *pp;
            *pp = expired;
        } else {
            // 单次定时器，释放内存
            free(expired);
        }
    }
}

// 事件循环
void event_loop() {
    struct epoll_event events[10];
    
    printf("开始事件循环...\n");
    
    while (1) {
        int n = epoll_wait(epfd, events, 10, -1);
        if (n == -1) {
            perror("epoll_wait");
            break;
        }
        
        for (int i = 0; i < n; i++) {
            if (events[i].data.fd == tfd) {
                // 读取tfd计数避免多次触发
                uint64_t expirations;
                ssize_t s = read(tfd, &expirations, sizeof(expirations));
                if (s != sizeof(expirations)) {
                    perror("read timerfd");
                    continue;
                }
                
                if (expirations > 0) {
                    // 执行所有到期定时器回调
                    process_expired_timers();
                }
            }
        }
    }
}

// 清理资源
void cleanup_timer() {
    if (tfd != -1) {
        close(tfd);
        tfd = -1;
    }
    if (epfd != -1) {
        close(epfd);
        epfd = -1;
    }
    
    // 清理定时器链表
    while (timer_list) {
        timer_node_t* next = timer_list->next;
        free(timer_list);
        timer_list = next;
    }
    
    printf("定时器资源已清理\n");
}
使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 示例回调函数
void minion_refresh_callback(void* arg) {
    static int wave_count = 0;
    wave_count++;
    printf("=== 第 %d 波小怪刷新 ===\n", wave_count);
}

void boss_refresh_callback(void* arg) {
    printf("!!! BOSS 刷新 !!!\n");
}

void network_event_callback(void* arg) {
    printf("处理网络事件\n");
}

// 测试主函数
int main() {
    // 初始化定时器
    if (init_timer() != 0) {
        return -1;
    }
    
    // 添加定时器
    int minion_timer = add_timer(0, 30000, minion_refresh_callback, NULL);  // 30秒刷新小怪
    int boss_timer = add_timer(300000, 0, boss_refresh_callback, NULL);     // 5分钟刷新boss
    
    // 模拟5秒后取消BOSS刷新
    sleep(5);
    delete_timer(boss_timer);
    
    // 运行事件循环
    event_loop();
    
    // 清理资源
    cleanup_timer();
    return 0;
}
编译命令
1
2
gcc -o timer_demo timer_demo.c -O2
./timer_demo
设计要点说明
  1. 高精度实现原理
  • 使用 CLOCK_MONOTONIC 单调时钟，避免系统时间调整影响
  • timerfd 提供纳秒级精度，实际误差 < 1ms
  • 30ms 周期检查确保及时处理到期任务
  1. 数据结构选择
  • 有序链表：按到期时间排序，便于快速获取最近任务
  • 插入复杂度：O(n)，但定时器数量通常不多，性能可接受
  • 删除复杂度：O(n)，支持动态删除
  1. 关键机制
  • 避免重复触发：每次读取 timerfd 的到期计数
  • 周期任务处理：执行后重新计算下次到期时间
  • 资源管理：单次任务自动释放，周期任务重新插入
  1. 性能优势
  • 零拷贝：timerfd 通过文件描述符通知，无内存拷贝
  • 事件统一：定时事件和网络事件在同一 epoll 实例处理
  • 低延迟：内核直接通知，无需轮询检查

这个实现能够满足高精度定时器需求，误差控制在 1ms 以内，同时支持动态添加和删除定时器。

题目 3：定时器性能优化

问题：当定时器数量超过 10 万时，传统最小堆插入效率下降。现有方案：

  1. 时间轮（Timing Wheel）分层：秒级轮（512 槽）+ 毫秒级轮（1024 槽）
  2. 惰性删除：标记取消的定时器，执行时跳过

请根据以下要求进行作答：

  1. 解决 “秒级轮定时器到期后迁移至毫秒级轮” 的伪代码
  2. 设计取消定时器的数据结构（要求 O (1) 时间复杂度删除）
  3. 计算时间轮定位槽位的哈希函数（输入：时间戳，输出：秒级槽位 + 毫秒级槽位）

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;

public class TimingWheelTimer {
    // 时间轮配置 - 使用1000个毫秒槽位，每个槽位1ms
    private static final int SECOND_WHEEL_SIZE = 512;    // 秒级轮槽位数
    private static final int MS_WHEEL_SIZE = 1000;       // 毫秒级轮槽位数
    private static final int MS_PER_SLOT = 1;            // 每个毫秒槽代表1ms

    // 时间轮结构
    private final List<Set<TimerTask>> secondWheel;      // 秒级轮 (512槽，每槽1秒)
    private final List<Set<TimerTask>> msWheel;          // 毫秒级轮 (1000槽，每槽1ms)

    // 取消任务集合 (O(1)删除)
    private final Set<Long> canceledTasks;

    // 指针和状态
    private int currentSecondSlot;      // 当前秒级槽位
    private int currentMsSlot;          // 当前毫秒级槽位
    private volatile long currentTime;  // 当前时间戳(毫秒)
    private volatile boolean running;

    // 工作线程
    private final Thread workerThread;

    // ID生成器
    private final AtomicLong idGenerator;

    public TimingWheelTimer() {
        this.secondWheel = new ArrayList<>(SECOND_WHEEL_SIZE);
        this.msWheel = new ArrayList<>(MS_WHEEL_SIZE);

        // 初始化时间轮槽位
        for (int i = 0; i < SECOND_WHEEL_SIZE; i++) {
            secondWheel.add(Collections.synchronizedSet(new HashSet<>()));
        }
        for (int i = 0; i < MS_WHEEL_SIZE; i++) {
            msWheel.add(Collections.synchronizedSet(new HashSet<>()));
        }

        this.canceledTasks = Collections.synchronizedSet(new HashSet<>());
        this.currentSecondSlot = 0;
        this.currentMsSlot = 0;
        this.currentTime = System.currentTimeMillis();
        this.running = true;
        this.idGenerator = new AtomicLong(1);

        // 启动工作线程
        this.workerThread = new Thread(this::run);
        this.workerThread.setDaemon(true);
        this.workerThread.start();
    }

    /**
     * 定时器任务类
     */
    private static class TimerTask {
        final long id;
        final long expireTime;     // 到期时间戳
        final long interval;       // 间隔时间，0表示单次任务
        final Runnable task;       // 任务逻辑
        final boolean isRepeating; // 是否重复任务

        TimerTask(long id, long expireTime, long interval, Runnable task, boolean isRepeating) {
            this.id = id;
            this.expireTime = expireTime;
            this.interval = interval;
            this.task = task;
            this.isRepeating = isRepeating;
        }
    }

    /**
     * 哈希函数：计算时间轮槽位
     * @param timestamp 时间戳(毫秒)
     * @return [秒级槽位, 毫秒级槽位]
     */
    private int[] calculateSlots(long timestamp) {
        long delta = timestamp - currentTime;

        if (delta < MS_WHEEL_SIZE * MS_PER_SLOT) {
            // 在毫秒级轮范围内 (1000ms以内)
            int msSlot = (currentMsSlot + (int)(delta / MS_PER_SLOT)) % MS_WHEEL_SIZE;
            return new int[]{-1, msSlot};
        } else {
            // 需要秒级轮 (1000ms以上)
            int secondDelta = (int)(delta / 1000);  // 直接计算秒数
            int secondSlot = (currentSecondSlot + secondDelta) % SECOND_WHEEL_SIZE;
            return new int[]{secondSlot, -1};
        }
    }

    /**
     * 添加一次性任务
     */
    public long addTask(long delayMs, Runnable task) {
        long id = idGenerator.getAndIncrement();
        long expireTime = currentTime + delayMs;
        TimerTask timerTask = new TimerTask(id, expireTime, 0, task, false);

        int[] slots = calculateSlots(expireTime);
        if (slots[0] == -1) {
            // 直接放入毫秒级轮
            msWheel.get(slots[1]).add(timerTask);
        } else {
            // 放入秒级轮
            secondWheel.get(slots[0]).add(timerTask);
        }

        return id;
    }

    /**
     * 添加重复任务
     */
    public long addRepeatingTask(long delayMs, Runnable task, long intervalMs) {
        long id = idGenerator.getAndIncrement();
        long expireTime = currentTime + delayMs;
        TimerTask timerTask = new TimerTask(id, expireTime, intervalMs, task, true);

        int[] slots = calculateSlots(expireTime);
        if (slots[0] == -1) {
            msWheel.get(slots[1]).add(timerTask);
        } else {
            secondWheel.get(slots[0]).add(timerTask);
        }

        return id;
    }

    /**
     * 取消定时器 (O(1)时间复杂度)
     */
    public boolean cancelTask(long taskId) {
        return canceledTasks.add(taskId);
    }

    /**
     * 秒级轮任务迁移到毫秒级轮
     */
    private void migrateSecondWheelTasks() {
        Set<TimerTask> tasks = secondWheel.get(currentSecondSlot);
        if (tasks.isEmpty()) {
            return;
        }

        Set<TimerTask> toRemove = new HashSet<>();
        Set<TimerTask> toAddMsWheel = new HashSet<>();

        synchronized (tasks) {
            Iterator<TimerTask> iterator = tasks.iterator();
            while (iterator.hasNext()) {
                TimerTask task = iterator.next();
                if (canceledTasks.contains(task.id)) {
                    toRemove.add(task);
                    iterator.remove();
                    continue;
                }

                // 重新计算剩余时间
                long remaining = task.expireTime - currentTime;
                if (remaining <= 0) {
                    // 立即执行
                    executeTask(task);
                    toRemove.add(task);
                    iterator.remove();
                } else if (remaining < MS_WHEEL_SIZE * MS_PER_SLOT) {
                    // 迁移到毫秒级轮
                    int msSlot = (currentMsSlot + (int)(remaining / MS_PER_SLOT)) % MS_WHEEL_SIZE;
                    toAddMsWheel.add(task);
                    toRemove.add(task);
                    iterator.remove();
                }
                // 如果剩余时间仍然很长，继续留在秒级轮
            }
        }

        // 批量添加到毫秒级轮
        for (TimerTask task : toAddMsWheel) {
            long remaining = task.expireTime - currentTime;
            int msSlot = (currentMsSlot + (int)(remaining / MS_PER_SLOT)) % MS_WHEEL_SIZE;
            msWheel.get(msSlot).add(task);
        }

        // 清理取消的任务ID
        for (TimerTask task : toRemove) {
            canceledTasks.remove(task.id);
        }
    }

    /**
     * 执行任务
     */
    private void executeTask(TimerTask task) {
        if (canceledTasks.contains(task.id)) {
            canceledTasks.remove(task.id);
            return;
        }

        try {
            task.task.run();
        } catch (Exception e) {
            e.printStackTrace();
        }

        // 如果是重复任务，重新添加
        if (task.isRepeating && !canceledTasks.contains(task.id)) {
            long newExpireTime = currentTime + task.interval;
            TimerTask newTask = new TimerTask(task.id, newExpireTime, task.interval, task.task, true);

            int[] slots = calculateSlots(newExpireTime);
            if (slots[0] == -1) {
                msWheel.get(slots[1]).add(newTask);
            } else {
                secondWheel.get(slots[0]).add(newTask);
            }
        } else {
            canceledTasks.remove(task.id);
        }
    }

    /**
     * 工作线程主循环
     */
    private void run() {
        long lastTickTime = System.currentTimeMillis();

        while (running) {
            try {
                long currentTickTime = System.currentTimeMillis();
                long elapsed = currentTickTime - lastTickTime;

                if (elapsed > 0) {
                    // 更新当前时间
                    currentTime = currentTickTime;

                    // 推进毫秒级轮指针
                    int ticks = Math.min((int)elapsed, MS_WHEEL_SIZE); // 防止溢出
                    for (int i = 0; i < ticks; i++) {
                        advanceMsWheel();
                    }

                    lastTickTime = currentTickTime;
                }

                // 短暂休眠，避免CPU占用过高
                Thread.sleep(1);

            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 推进毫秒级轮
     */
    private void advanceMsWheel() {
        // 处理当前槽位的任务
        Set<TimerTask> tasks = msWheel.get(currentMsSlot);
        if (!tasks.isEmpty()) {
            Set<TimerTask> toExecute = new HashSet<>();
            Set<TimerTask> toRemove = new HashSet<>();

            synchronized (tasks) {
                Iterator<TimerTask> iterator = tasks.iterator();
                while (iterator.hasNext()) {
                    TimerTask task = iterator.next();
                    if (canceledTasks.contains(task.id)) {
                        toRemove.add(task);
                        iterator.remove();
                    } else if (task.expireTime <= currentTime) {
                        toExecute.add(task);
                        toRemove.add(task);
                        iterator.remove();
                    }
                }
            }

            // 执行任务
            for (TimerTask task : toExecute) {
                executeTask(task);
            }

            // 清理取消的任务ID
            for (TimerTask task : toRemove) {
                canceledTasks.remove(task.id);
            }
        }

        // 推进指针
        currentMsSlot = (currentMsSlot + 1) % MS_WHEEL_SIZE;

        // 如果毫秒级轮完成一圈（1000ms），推进秒级轮
        if (currentMsSlot == 0) {
            advanceSecondWheel();
        }
    }

    /**
     * 推进秒级轮
     */
    private void advanceSecondWheel() {
        // 迁移秒级轮任务到毫秒级轮
        migrateSecondWheelTasks();

        // 推进秒级轮指针
        currentSecondSlot = (currentSecondSlot + 1) % SECOND_WHEEL_SIZE;
    }

    /**
     * 停止定时器
     */
    public void stop() {
        running = false;
        workerThread.interrupt();
    }

    /**
     * 获取统计信息
     */
    public void printStats() {
        int secondWheelCount = secondWheel.stream().mapToInt(Set::size).sum();
        int msWheelCount = msWheel.stream().mapToInt(Set::size).sum();
        int canceledCount = canceledTasks.size();

        System.out.printf("时间轮统计: 秒级轮=%d, 毫秒级轮=%d, 取消任务=%d, 总任务=%d%n",
                secondWheelCount, msWheelCount, canceledCount,
                secondWheelCount + msWheelCount + canceledCount);
    }

    public static void main(String[] args) throws Exception {
        TimingWheelTimer timer = new TimingWheelTimer();

        System.out.println("开始时间：" + new Date());

        // 测试1: 一次性任务 (6秒后执行)
        long oneTimeTaskId = timer.addTask(6000, () ->
                System.out.println("[" + new Date() + "] 执行一次性任务")
        );
        System.out.println("添加一次性任务, ID: " + oneTimeTaskId);

        // 测试2: 重复任务 (1秒后开始，每2秒执行一次)
        long repeatingTaskId = timer.addRepeatingTask(1000, () ->
                System.out.println("[" + new Date() + "] 执行重复任务"), 2000
        );
        System.out.println("添加重复任务, ID: " + repeatingTaskId);

        // 测试3: 精确到毫秒的任务
        long preciseTaskId = timer.addTask(1500, () ->
                System.out.println("[" + new Date() + "] 执行精确到毫秒的任务 (1500ms)")
        );
        System.out.println("添加精确毫秒任务, ID: " + preciseTaskId);

        long task = timer.addTask(3000, ()->
                System.out.println("[" + new Date() + "] 3s后执行"));

        // 等待足够时间让所有任务执行
        Thread.sleep(25000);

        System.out.println("取消重复任务: " + repeatingTaskId);
        timer.cancelTask(repeatingTaskId);

        // 打印统计信息
        timer.printStats();

        timer.stop();
    }
}
其他
#定时器
定时器
http://surourou8.github.io/2025/10/07/定时器/
作者
Su Rourou
发布于
2025年10月7日
许可协议