Mettre en œuvre une file d'attente prioritaire avec une variable de condition en C

Question

Ma compréhension actuelle des variables de condition est que tous les fils bloqués (attente) sont insérés dans une file d'attente FIFO de base, le premier élément qui est réveillé quand le signal () est appelée.

Est-il possible de modifier cette file d'attente (ou créer une nouvelle structure) pour effectuer une file d'attente prioritaire à la place? J'ai pensé à ce sujet pendant un certain temps, mais la plupart des solutions je finir par être entravée par la structure de file d'attente existante inhérente à son C.V. et mutex.

Merci!

Answer 1

Je pense que vous devriez repenser ce que vous essayez de faire. Si vous essayez d'optimiser vos performances, vous probablement aboyer le mauvais arbre.

pthread_cond_signal() est même pas garanti pour débloquer exactement un fil - il est garanti à débloquer au moins un fil, de sorte que votre code mieux être en mesure de gérer la situation où plusieurs threads sont débloquées simultanément. La façon typique de le faire est pour chaque thread de re-vérifier l'état après être devenu débloquée, et, si elle est fausse, revenir à attendre à nouveau.

Vous pouvez mettre en œuvre une sorte de système où vous conservez votre propre file d'attente prioritaire des threads en attente, et chaque fil lui-même ajouté à la file d'attente immédiatement avant qu'il ne devait commencer attente, puis il vérifieriez la file d'attente lorsque déboucheurs, mais ceci ajouter beaucoup de complexité et beaucoup de potentiel pour des problèmes graves (conditions de course, etc.), des blocages. Il a été également ajouter un montant non négligeable des frais généraux.

En outre, ce qui se passe si un thread de priorité supérieure commence en attente sur une variable d'état au même moment que variable de condition est signalée? Qui est débloquée, le fil de haute priorité nouvellement arrivés ou l'ancien fil la plus haute priorité?

L'ordre que les fils se débloquée en est entièrement dépendante du planificateur de threads du noyau, de sorte que vous êtes à sa merci. Je ne satisferaient pas même ordre FIFO, soit.

Answer 2

Étant donné que les variables de condition sont fondamentalement juste une barrière et vous avez aucun contrôle sur la file d'attente des threads en attente il n'y a aucun moyen d'appliquer les priorités. Il est incorrect de supposer threads en attente agira d'une manière FIFO.

Avec une combinaison de Atomics, variables de condition supplémentaires, et une connaissance préalable des fils / priorités implique, vous pouvez construire une solution où un fil signalé re-signaler le CV maître et puis re-bloc sur un CV prioritaire mais ne serait certainement pas une solution générique. C'est aussi du haut de ma tête alors pourrait aussi avoir un autre défaut.

Answer 3

Il est le programmateur qui détermine quel thread fonctionnera. Vous pouvez regarder pthread_setschedparam et pthread_getschedparam et jouer avec les politiques (SCHED_OTHER, SCHED_FIFO ou SCHED_RR) et les priorités. Mais il ne sera probablement pas vous arriver là où je pense que vous voulez aller.

Il semble que si vous voulez faire quelque chose prévisible de la nature non-déterministe. Comme Andrew vous pourriez remarquer pirater quelque chose mais je pense que cela conduira à un chagrin d'amour ou code de lot, vous vous détestez pour écrire en six mois (ou les deux).