Comment mettre en œuvre une minuterie asynchrone sur un système * nix en utilisant pthreads

Question

J'ai 2 questions:

Q1) Puis-je mettre en œuvre une minuterie asynchrone dans un i.e. d'application unique filetée je veux une fonctionnalité comme celui-ci. Dans la mesure où je peux penser que cela ne peut pas être fait pour une seule application filetée (corrigez-moi si je me trompe). Je ne sais pas si cela peut être fait en utilisant select comme démultiplexeur, mais même si select pourrait être utilisé, la boucle d'événement nécessiterait un thread? N'est-ce pas?

Je veux aussi savoir si je peux mettre en œuvre une minuterie (pas timeout) en utilisant select. Sélectionnez uniquement les attentes sur l'ensemble des descripteurs de fichiers, mais je veux avoir une liste de temporisateurs dans l'ordre croissant de leurs délais d'expiration et que vous voulez sélectionner pour me dire quand le premier temporisateur expire et ainsi de suite. Donc la question se résume à peut-on mettre en œuvre un temporisateur asynchrone en utilisant select/poll ou un autre démultiplexeur d'événements? Q2) Passons maintenant à ma deuxième question. Ceci est ma question principale. Maintenant, j'utilise un thread dédié pour vérifier les délais d'attente, c'est-à-dire que j'ai un min tas de temporisateurs (temps d'expiration) et ce thread dort jusqu'à ce que le premier temporisateur expire, puis invoque le rappel. -à-dire le code ressemble à ceci

1. verrouiller le mutex
2. vérifier le temps de la première minuterie
3. état chronométré attente pour ce moment-là (et se réveiller si un autre thread insère une minuterie avec le temps d'expiration moins que le premier temporisateur) L'attente de condition déverrouille le verrou.
4. Une fois la condition d'attente terminée, nous avons le verrou. Alors, déverrouillez-le, supprimez la minuterie du tas et appelez la fonction de rappel.
5. aller à 1

Je veux que la complexité temporelle de cette horloge asynchrone. D'après ce que je vois

1. insertion est lg (n)
2. expiration est lg (n)
3. Annulation

:(c'est ce qui me donne le vertige), le problème est que j'ai un min tas de minuteries en fonction de leur temps et quand j'insère une minuterie je reçois un identifiant unique. Donc, quand j'ai besoin d'annuler la minuterie, je dois fournir cette identification de la minuterie et la recherche de cet identifiant dans le tas prendrait dans le pire des cas O (n)

Ai-je tort?

Peut-annulation se faire en O (logn)

S'il vous plaît ne prenez pas soin de certains problèmes de multithreading. Je voudrais préciser ce que je veux dire par ma phrase précédente une fois que j'obtiens des réponses.

Answer 1

Si vous êtes une application Windows, vous pouvez déclencher l'envoi d'un message WM_TIMER à un moment ultérieur, qui fonctionnera même si votre application est à un seul thread. Cependant, l'exactitude de la synchronisation ne sera pas grande.Si votre application s'exécute dans une boucle constante (comme un jeu, avec un rendu à 60Hz), vous pouvez simplement vérifier à chaque fois autour de la boucle si les événements déclenchés doivent être appelés.

Si vous voulez que votre application soit fondamentalement interrompue, que votre fonction soit appelée, puis que vous l'exécutiez pour retourner à l'endroit où elle se trouvait, vous pourriez ne pas avoir de chance.

Answer 2

Si vous utilisez C#, System.Timers.Timer fera ce que vous voulez. Vous spécifiez une méthode de gestionnaire d'événements que le temporisateur appelle lorsqu'il expire, ce qui peut être dans la classe dont vous appelez le temporisateur. Notez que lorsque le temporisateur appelle le gestionnaire d'événements, il le fait sur un thread distinct, que vous devez prendre en compte si vous mettez à jour l'interface utilisateur, ou utilisez sa propriété SynchronizingObject pour l'exécuter sur le thread d'interface utilisateur.

Answer 3

Il est certainement possible (et généralement préférable) d'implémenter des temporisations en utilisant un seul thread, si l'on peut supposer que le thread passera le plus clair de son temps à select(). Vous pouvez vérifier en utilisant signal() et SIGALRM pour implémenter la fonctionnalité sous POSIX, mais je le déconseille (les signaux Unix sont des hacks moche, et quand la fonction de rappel de signal fonctionne, il y a très peu de choses que vous pouvez faire à l'intérieur en toute sécurité, car il fonctionne de façon asynchrone sur votre thread d'application)

Votre idée sur l'utilisation de timeout de select() pour implémenter votre fonctionnalité de minuterie est une bonne technique très courante et qui fonctionne bien. Fondamentalement, vous gardez une liste des événements en attente/à venir qui sont triés par horodatage, et juste avant d'appeler select() vous soustrayez l'heure actuelle du premier horodatage dans la liste, et passez ce delta temporel comme valeur de délai pour sélectionner(). (note: si le delta temporel est négatif, passez le zéro comme valeur du délai!) Lorsque select() revient, vous comparez l'heure actuelle avec l'heure du premier élément de la liste; si l'heure actuelle est supérieure ou égale à l'heure de l'événement, manipulez l'événement timer, déposez le premier élément en tête de la liste et répétez. En ce qui concerne l'efficacité, votre temps big-O dépendra entièrement de la structure de données que vous utilisez pour stocker votre liste de minuteries ordonnée. Si vous utilisez une file d'attente prioritaire (ou une structure arborescente ordonnée similaire), vous pouvez avoir des heures O (log N) pour toutes vos opérations. Vous pouvez même aller plus loin et stocker la liste des événements dans une table de hachage (saisie sur les ID d'événement) et une liste liée (triée par horodatage), et qui peut vous donner O (1) fois pour toutes les opérations. O (log N) est probablement suffisamment efficace, sauf si vous prévoyez d'avoir un très grand nombre d'événements en attente à la fois.

Answer 4

man pthread_cond_timedwait 

man pthread_cond_signal