Comment permettre à certains threads d'avoir la priorité pour verrouiller un mutex en utilisant PTHREADS

Question

Supposons que le code suivant soit exécuté par 10 threads.

pthread_mutex_lock(&lock)
Some trivial code
pthread_mutex_unlock(&lock)

Pour les besoins de l'explication, disons que les fils sont T1, T2, T3.....T10. Mon exigence est que tant que T1 ou T2 ou T3 (c'est-à-dire n'importe lequel de T1, T2 ou T3) attende pour acquérir un verrou, les autres threads, c'est-à-dire T4, T5, T6.....T10, ne puissent pas acquérir le verrou, c'est-à-dire que T1, T2 et T3 aient la priorité pour acquérir le verrou par rapport aux autres threads.

Je suppose que cela peut être fait en augmentant la priorité des threads T1, T2 et T3.

Voici le pseudo-code

if this thread is T1 or T2 or T3
increase its priority 
pthread_mutex_lock(&lock)
Some trivial code
pthread_mutex_unlock(&lock)
if this thread is T1 or T2 or T3 decrease it priority to normal

Veuillez noter que je veux une solution qui fonctionne pour la plateforme Linux et qui doit utiliser pthreads. Je ne me soucie pas vraiment des autres plateformes.

Notez également que je ne veux pas vraiment que ces 3 threads soient en temps réel, je veux qu'ils aient leur comportement habituel (ordonnancement et priorité) sauf que dans le petit morceau de code mentionné ci-dessus, je veux qu'ils aient toujours la priorité pour acquérir un verrou.

J'ai lu quelques pages de manuel sur les politiques et les priorités d'ordonnancement sous Linux, mais je ne comprends pas vraiment :(

Est-ce que ça va marcher ? Pouvez-vous m'indiquer l'API pthread exacte requise pour accomplir la tâche ci-dessus ?

Salutations lali

Answer 1

Voici ma mise en œuvre. Les threads de basse priorité utilisent prio_lock_low() y prio_unlock_low() pour verrouiller et déverrouiller, les threads de haute priorité utilisent prio_lock_high() y prio_unlock_high() .

Le design est assez simple. Les threads de haute priorité sont retenus par le mutex de la section critique. ->cs_mutex les fils de basse priorité sont maintenus à la variable de condition. Le mutex de la variable de condition n'est maintenu que pour les mises à jour de la variable partagée et la signalisation de la variable de condition.

#include <pthread.h>

typedef struct prio_lock {
    pthread_cond_t cond;
    pthread_mutex_t cv_mutex; /* Condition variable mutex */
    pthread_mutex_t cs_mutex; /* Critical section mutex */
    unsigned long high_waiters;
} prio_lock_t;

#define PRIO_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER, PTHREAD_MUTEX_INITIALIZER }

void prio_lock_low(prio_lock_t *prio_lock)
{
    pthread_mutex_lock(&prio_lock->cv_mutex);
    while (prio_lock->high_waiters || pthread_mutex_trylock(&prio_lock->cs_mutex))
    {
        pthread_cond_wait(&prio_lock->cond, &prio_lock->cv_mutex);
    }
    pthread_mutex_unlock(&prio_lock->cv_mutex);
}

void prio_unlock_low(prio_lock_t *prio_lock)
{
    pthread_mutex_unlock(&prio_lock->cs_mutex);

    pthread_mutex_lock(&prio_lock->cv_mutex);
    if (!prio_lock->high_waiters)
        pthread_cond_signal(&prio_lock->cond);
    pthread_mutex_unlock(&prio_lock->cv_mutex);
}

void prio_lock_high(prio_lock_t *prio_lock)
{
    pthread_mutex_lock(&prio_lock->cv_mutex);
    prio_lock->high_waiters++;
    pthread_mutex_unlock(&prio_lock->cv_mutex);

    pthread_mutex_lock(&prio_lock->cs_mutex);
}

void prio_unlock_high(prio_lock_t *prio_lock)
{
    pthread_mutex_unlock(&prio_lock->cs_mutex);

    pthread_mutex_lock(&prio_lock->cv_mutex);
    prio_lock->high_waiters--;
    if (!prio_lock->high_waiters)
        pthread_cond_signal(&prio_lock->cond);
    pthread_mutex_unlock(&prio_lock->cv_mutex);
}

Answer 2

D'après ce que j'ai compris, la seule façon de le garantir réellement serait d'écrire vous-même un verrou qui fonctionne de cette façon. Cependant, La réponse de @xryl669 qui suggère d'utiliser la priorité des threads et l'héritage des priorités mérite certainement d'être pris en considération si cela fonctionne pour votre cas d'utilisation.

Pour l'implémenter vous-même, vous aurez besoin de variables de condition et de comptage du nombre de threads en attente de basse / haute priorité.

En termes de concepts et d'API dont vous aurez besoin, c'est relativement similaire à la mise en œuvre d'un verrou de lecture/écriture (mais la sémantique dont vous avez besoin est complètement différente, évidemment - mais si vous avez compris comment fonctionne le verrou de lecture/écriture, vous comprendrez comment mettre en œuvre ce que vous voulez).

Vous pouvez voir une mise en œuvre d'un verrou de lecture-écriture ici :

http://ptgmedia.pearsoncmg.com/images/0201633922/sourcecode/rwlock.c

Dans les threads de moindre priorité, vous devrez attendre que les threads de haute priorité se terminent, de la même manière que les lecteurs attendent que les auteurs se terminent.

(Le livre dont est tiré le code ci-dessus est également un excellent livre sur les fils posix), http://www.informit.com/store/product.aspx?isbn=0201633922 )

Answer 3

La méthode native est d'activer l'héritage de priorité pour votre mutex (avec pthread_mutex_attr), et d'utiliser la priorité du thread de pthread pour effectuer ce dont vous avez besoin. Cela ne nécessite que quelques lignes de code, et vous n'avez pas à réinventer la roue. Le bon côté des choses, c'est qu'il fonctionnera également avec un planificateur RT ou FIFO alors que votre version homebrew ne le fera pas.

Ensuite, chaque fois qu'un thread à haute priorité attend un mutex acquis par un thread à plus basse priorité, le noyau "booste" le thread à basse priorité pour qu'il puisse être planifié à la place du thread à haute priorité, lui donnant ainsi un timelice pour libérer le verrou. Dès que le verrou est libéré, le thread à haute priorité est planifié. C'est le délai le plus court que l'on puisse obtenir puisque c'est le noyau qui s'en charge.

Answer 4

Alternativement, vous pouvez simplement introduire un autre verrou pour les threads à priorité plus élevée. Considérez le pseudo-code suivant (je ne suis pas familier avec la sémantique de pthread, mais je pense que ce n'est pas difficile de faire correspondre le code aux appels nécessaires)

EDIT (merci JosephH)

introduction du sémaphore d'exécution fixé à 3 (nombre de threads à haut niveau de priorité) notez que pend(exec,3); signifie que ce pendentif va dormir jusqu'à ce que les 3 slots soient disponibles et les consommera tous.

//init
exec = semaphore(3,3);

//========================

if this is NOT thread (t1,t2,t3)
    lock(low_prio);
    sem_pend(exec,3);
else
    sem_pend(exec,1);
lock(high_prio);
//...
unlock(high_prio);
if this is NOT thread (t1,t2,t3)
    sem_release(exec,3);
    sleep(0); //yield();  //ensures that sem_pend(exec,1) is executed
    unlock(low_prio);
else
    sem_release(exec,1);

Answer 5

(Les deux premières tentatives avaient des bugs, passez à l'EDIT2)

Peut-être que ça pourrait marcher ?

if NOT this thread is T1 or T2 or T3
    pthread_mutex_lock(&lock1) // see note below
    pthread_mutex_lock(&lock2)
    Some trivial code
    pthread_mutex_unlock(&lock2)
    pthread_mutex_unlock(&lock1)
else
    pthread_mutex_lock(&lock2)
    Some trivial code
    pthread_mutex_unlock(&lock2)        
end if

Raisonnement : Certains threads seront en compétition pour deux verrous et auront donc une priorité plus faible et certains threads seront en compétition pour un seul verrou et auront donc une priorité plus élevée. Pourtant, la différence pourrait être marginale et la résolution serait alors d'introduire un certain décalage entre l'acquisition du premier verrou et la tentative du second verrou pour les threads à priorité plus élevée, pendant lequel les threads à priorité plus élevée auront une chance d'obtenir le verrou2.
(avis de non-responsabilité : je suis un novice en la matière).

EDIT : Une autre tentative/approche

if NOT (this thread is T1 or T2 or T3)  
    pthread_mutex_lock(&lock1)
    if pthread_mutex_trylock(&lock2) == 0  // low priority threads will not get queued
        Some trivial code
        pthread_mutex_unlock(&lock2)
    end if
    pthread_mutex_unlock(&lock1)
else 
    if (this thread is T1 or T2 or T3)
        pthread_mutex_lock(&lock2)
        Some trivial code
        pthread_mutex_unlock(&lock2)        
    end if
end if

EDIT2 : Une autre tentative (j'essaie d'apprendre quelque chose ici)

if NOT (this thread is T1 or T2 or T3)  
    pthread_mutex_lock(&lock1)
    while !(pthread_mutex_trylock(&lock2) == 0)
        pthread_yield()
    Some trivial code
    pthread_mutex_unlock(&lock2)
    pthread_mutex_unlock(&lock1)
else 
    if (this thread is T1 or T2 or T3)
        pthread_mutex_lock(&lock2)
        Some trivial code
        pthread_mutex_unlock(&lock2)        
    end if
end if