Algorithme de minuterie efficace

Question

Quel est le meilleur algorithme pour implémenter une bibliothèque de minuteur simple. La bibliothèque devrait permettre aux suivantes:

1. minuteries à commencé
2. Timers être arrêté
3. minuteries à vérifier si elles sont toujours en cours d'exécution

On Timer expiration d'une fonction de rappel sera appelé.

Le module de temporisation permettra aux temporisateurs d'avoir une résolution temporelle de Ns et le module recevra un coup de pied toutes les Ns pour inviter le module à vérifier les temporisateurs expirés.

De nombreuses minuteries peuvent être actives simultanément.

Le meilleur algorithme doit atteindre les objectifs suivants

1. robuste à minuteries en cours de démarrage/arrêt pendant le traitement d'une minuterie de rappel d'expiration
2. Autoriser minuteries à lancer, arrêté et vérifié rapidement
3. Avez un faible encombrement mémoire

salutations

Answer 1

meilleur algorithme que je l'ai vu pour minuteries est une roue de minuterie trouve dans le document de recherche Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility

Je sais en Java il y a une implémentation avec Netty, JBoss et je suis sûr d'ailleurs aussi que vous pouvez utiliser, si vous écrivons en Java.

Answer 2

O n Les systèmes POSIX-ish, vous pouvez utiliser la famille de fonctions timer_create/timer_settime pour fournir beaucoup de ceci "gratuitement".

Answer 3

Les minuteurs sont généralement mieux implémentés dans un noyau de système d'exploitation, au niveau de l'assemblage/C, en utilisant des fonctionnalités spécifiques à la plate-forme telles que les minuteurs APIC dans la mesure du possible.

Vous pouvez consulter http://lwn.net/Articles/167897/ pour plus de détails sur l'implémentation de Linux et parcourir le code source Linux pour voir les implémentations fonctionnelles.