Thuật toán hẹn giờ hiệu quả

Question

Thuật toán tốt nhất để triển khai thư viện hẹn giờ đơn giản là gì. Thư viện nên cho phép như sau:

1. Timers được bắt đầu
2. Timers để được dừng lại
3. Timers để được kiểm tra cho dù họ vẫn đang chạy

On Hẹn giờ hết hạn một hàm callback sẽ gọi là.

Mô-đun hẹn giờ sẽ cho phép bộ hẹn giờ có độ phân giải thời gian của N và mô-đun sẽ được cung cấp một cú đá mỗi N để nhắc mô-đun kiểm tra các bộ hẹn giờ đã hết hạn.

Nhiều bộ hẹn giờ có thể hoạt động đồng thời.

Các thuật toán tốt nhất cần phải đáp ứng được các mục tiêu sau đây

1. Hãy mạnh mẽ để tính giờ được bắt đầu/dừng lại khi xử lý một bộ đếm thời gian gọi lại hết
2. phép tính giờ được bắt đầu, dừng lại và kiểm tra một cách nhanh chóng
3. Có một bộ nhớ nhỏ dấu chân

Trân

Answer 1

thuật toán tốt nhất mà tôi đã thấy cho giờ là một bánh xe hẹn giờ tìm thấy trong các tài liệu nghiên cứu Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

Tôi biết trong Java có một thực hiện với Netty, JBoss và tôi chắc chắn ở đâu đó quá mà bạn có thể sử dụng, nếu bạn đang viết bằng Java.

Answer 2

O Các hệ thống POSIX-ish, bạn có thể sử dụng các chức năng của timer_create/timer_settime để cung cấp rất nhiều điều này "miễn phí".

Answer 3

Bộ định thời thường được triển khai tốt nhất trong hạt nhân hệ điều hành, ở cấp độ lắp ráp/C, sử dụng các tính năng dành riêng cho nền tảng như bộ hẹn giờ APIC bất cứ khi nào có thể.

Bạn có thể muốn xem http://lwn.net/Articles/167897/ để biết chi tiết về triển khai Linux và tìm hiểu mã nguồn Linux để xem triển khai thực hiện.