Argument¶

Le paramètre uaddr pointe vers un mot futex. Sur toutes les plateformes, les futex sont des entiers de quatre octets qui doivent être alignés sur une limite de quatre octets. L'opération à effectuer sur le futex est indiquée dans le paramètre de op.

Opérations futex¶

Le paramètre op est en deux parties : une commande qui indique l'opération à effectuer et un bit ORed avec zéro ou plusieurs options qui changent le comportement de l'opération. Les options qui peuvent être incluses dans op sont les suivantes :

FUTEX_PRIVATE_FLAG (depuis Linux 2.6.22)

Ce bit d'option peut être utilisé avec toutes les opérations futex. Il dit au noyau que le futex est un processus privé non partagé avec d'autres processus (c'est-à-dire qu'il n'est utilisé que pour la synchronisation entre les threads du même processus). Cela permet au noyau d'effectuer des optimisations de performance supplémentaires.

Par commodité, <linux/futex.h> définit un ensemble de constantes dont le suffixe est _PRIVATE et qui sont équivalentes à toutes les opérations listées ci-dessous mais avec l'attribut FUTEX_PRIVATE_FLAG ORed dans la valeur de la constante. On trouve ainsi FUTEX_WAIT_PRIVATE, FUTEX_WAKE_PRIVATE et ainsi de suite.

FUTEX_CLOCK_REALTIME (depuis Linux 2.6.28)

Ce bit d'option ne peut être utilisé qu'avec les opérations FUTEX_WAIT_BITSET(2const), FUTEX_WAIT_REQUEUE_PI(2const) (depuis Linux 4.5), FUTEX_WAIT(2const) (depuis Linux 4.5) et FUTEX_LOCK_PI2(2const) (depuis Linux 5.14).

Si cette option est positionnée, le noyau mesure le timeout par rapport à l'horloge CLOCK_REALTIME.

Si cette option n'est pas positionnée, le noyau mesure le timeout par rapport à l'horloge CLOCK_MONOTONIC.

L'opération indiquée dans op prend une de ces valeurs :

FUTEX_WAIT(2const)

FUTEX_WAKE(2const)

FUTEX_FD(2const)

FUTEX_REQUEUE(2const)

FUTEX_CMP_REQUEUE(2const)

FUTEX_WAKE_OP(2const)

FUTEX_WAIT_BITSET(2const)

FUTEX_WAKE_BITSET(2const)

Futex et héritage de priorité¶

Linux prend en charge l'héritage de priorité (priority inheritance, PI) des futex, afin de gérer des problèmes d'inversion des priorités qu'on peut rencontrer avec des verrous futex normaux. L'inversion des priorités est un problème qui survient quand une tâche de haute priorité est bloquée en attente d'acquérir un verrou que possède une tâche de basse priorité issue du processeur. Du coup, la tâche de priorité basse ne va pas relâcher le verrou et celle de haute priorité reste bloquée.

L'héritage de priorité est un mécanisme pour gérer le problème d'inversion des priorités. Avec ce mécanisme, quand une tâche à haute priorité est bloquée par un verrou possédé par une tâche à basse priorité, la priorité de la seconde est temporairement amenée au même niveau que celle à haute priorité, de sorte qu'elle ne soit pas doublée par une tâche de niveau intermédiaire et qu'elle puisse ainsi avancer pour relâcher le verrou. Pour fonctionner, l'héritage de priorité doit être transitif, ce qui signifie que si une tâche à haute priorité bloque sur le verrou d'une tâche à priorité intermédiaire (et ainsi de suite sur des chaînes de la taille de votre choix), les deux tâches (ou plus généralement toutes les tâches de la chaîne de verrous) voient leur niveau de priorité amené à celui de la tâche à haute priorité.

Du point de vue de l'espace utilisateur, le futex a conscience d'un PI en acceptant une réglementation (décrite ci-dessous) entre l'espace utilisateur et le noyau sur la valeur du mot futex, couplé à l'utilisation d'opérations futex PI décrites ci-dessous (contrairement aux autres opérations futex décrites ci-dessus, celles PI-futex sont conçues pour l'implémentation de mécanismes IPC très spécifiques).

Les opérations PI-futex décrites ci-dessous diffèrent des autres opérations dans le sens où elles imposent des règles dans l'utilisation de la valeur du mot futex :

• Si le verrou n'est pas acquis, la valeur du mot futex doit être 0.
• Si le verrou est acquis, la valeur du mot futex doit être l'ID du thread (TID ; voir gettid(2)) du thread propriétaire.
• Si le verrou a un propriétaire et s'il y a des threads en concurrence pour le verrou, le bit FUTEX_WAITERS doit être positionné dans la valeur du mot futex ; autrement dit, cette valeur est :

FUTEX_WAITERS | TID
    

(Remarquez que cela n'est pas possible pour un mot futex PI d'être sans propriétaire ni FUTEX_WAITERS défini).

Avec cette règle, une application de l'espace utilisateur peut acquérir un verrou non acquis ou en relâcher un en utilisant des instructions atomiques dans l'espace utilisateur (comme une opération compare-and-swap telle que cmpxchg sur l'architecture x86). L'acquisition d'un verrou consiste simplement dans l'utilisation de compare-and-swap pour positionner la valeur du mot futex de manière atomique sur le TID de l'appelant si sa valeur précédente était 0. Relâcher un verrou exige d'utiliser compare-and-swap pour positionner la valeur du mot futex sur 0 si la valeur précédente était le TID prévu.

Si un futex est déjà acquis (c'est-à-dire qu'il a une valeur positive), les éléments en attente doivent utiliser l'opération FUTEX_LOCK_PI(2const) ou FUTEX_LOCK_PI2(2const) pour acquérir le verrou. Si d'autres threads attendent le verrou, le bit FUTEX_WAITERS est défini dans la valeur du futex ; dans ce cas le détenteur du verrou doit utiliser l'opération FUTEX_UNLOCK_PI(2const) pour relâcher le verrou.

Dans le cas où les appelants sont bloqués dans le noyau (c'est-à-dire qu'ils doivent effectuer un appel futex()), ils traitent directement avec ce qu'on appelle un RT-mutex, un mécanisme de verrouillage du noyau qui implémente la sémantique de l'héritage de priorité requis. Après que le RT-mutex est acquis, la valeur futex est mise à jour en fonction, avant que le thread appelant ne renvoie vers l'espace utilisateur.

Il est important de remarquer que le noyau mettra à jour la valeur du mot futex avant de renvoyer vers l'espace utilisateur (cela enlève la possibilité pour la valeur d'un mot futex de se terminer dans un état non valable, par exemple en ayant un propriétaire mais en ayant la valeur 0, ou en ayant des éléments en attente mais aucun bit FUTEX_WAITERS positionné).

Si un futex a un RT-mutex associé dans le noyau (c'est-à-dire qu'il y a des éléments en attente bloqués) et si le propriétaire du futex/RT-mutex meurt de manière inattendue, le noyau nettoie le RT-mutex et passe la main au prochain élément en attente. Cela implique, en retour, que la valeur dans l'espace utilisateur soit mise à jour en fonction. Pour dire que c'est nécessaire, le noyau positionne le bit FUTEX_OWNER_DIED dans le mot futex ainsi que dans l'ID du thread du nouveau propriétaire. L'espace utilisateur peut détecter cette situation par la présence du bit FUTEX_OWNER_DIED et il est alors responsable pour nettoyer l'espace laissé par le propriétaire mort.

Les PI futex sont utilisés en indiquant une des valeurs listées ci-dessous dans op. Remarquez que les opérations de PI futex doivent être utilisées par paires et sont soumises à des exigences supplémentaires :

• FUTEX_LOCK_PI(2const), FUTEX_LOCK_PI2(2const) et FUTEX_TRYLOCK_PI(2const) vont de pair avec FUTEX_UNLOCK_PI(2const). FUTEX_UNLOCK_PI(2const) ne doit être appelé que sur un futex appartenant au thread appelant, tel que défini par les règles de la valeur, sans quoi on obtient l'erreur EPERM.
• FUTEX_WAIT_REQUEUE_PI(2const) va de pair avec FUTEX_CMP_REQUEUE_PI(2const). Elles doivent s'effectuer depuis un futex non-PI vers un PI futex distinct (sans quoi on obtient l'erreur EINVAL). De plus, le nombre d'éléments en attente à réveiller) doit être de 1 (sans quoi on obtient l'erreur EINVAL).

Les opérations PI futex sont comme suit :

FUTEX_LOCK_PI(2const)

FUTEX_LOCK_PI2(2const)

FUTEX_TRYLOCK_PI(2const)

FUTEX_UNLOCK_PI(2const)

FUTEX_CMP_REQUEUE_PI(2const)

FUTEX_WAIT_REQUEUE_PI(2const)

FUTEX_WAIT_REQUEUE_PI(2const) et FUTEX_CMP_REQUEUE_PI(2const) ont été ajoutés pour gérer un cas d'utilisation bien particulier : la prise en charge des variables conditionnelles de threads POSIX ayant connaissance de l'héritage de priorité. L'idée est que ces opérations devraient toujours aller par paires, afin de garantir que l'espace utilisateur et le noyau restent toujours synchronisés. Ainsi, dans l'opération FUTEX_WAIT_REQUEUE_PI(2const), l'application dans l'espace utilisateur pré-indique la cible de la remise en attente qui va se faire dans l'opération FUTEX_CMP_REQUEUE_PI(2const).

Source du programme¶

/* futex_demo.c


   Usage: futex_demo [nloops]


                    (Default: 5)


   Montrer l'utilisation des futex dans un programme où le parent et


   l'enfant utilisent une paire de futex située dans un tableau anonyme


   partagé pour synchroniser l'accès à une ressource partagée : le


   terminal. Les processus écrivent chacun des messages 'num-loops'


   sur le terminal et ils utilisent un protocole de synchronisation qui


   garantit qu'ils alternent l'écriture des messages.
*/
#define _GNU_SOURCE
#include <err.h>
#include <errno.h>
#include <linux/futex.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/syscall.h>
#include <sys/time.h>
#include <sys/wait.h>
#include <unistd.h>
static uint32_t *futex1, *futex2, *iaddr;
static int
futex(uint32_t *uaddr, int op, uint32_t val,


      const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3)
{


    return syscall(SYS_futex, uaddr, op, val,


                   timeout, uaddr2, val3);
}
/* Acquérir le futex vers lequel pointe 'futexp' : attendre que sa


   valeur passe à 1 puis positionner la valeur sur 0. */
static void
fwait(uint32_t *futexp)
{


    long            s;


    const uint32_t  one = 1;


    /* atomic_compare_exchange_strong(ptr, oldval, newval)


       fait atomiquement comme :


           if (*ptr == *oldval)


               *ptr = newval;


       Il renvoie true si le test a montré true et *ptr a été mis à jour. */


        for (;;) {


        /* Le futex est-il disponible ? */


        if (atomic_compare_exchange_strong(futexp, &one, 0))


            break;      /* Oui */


        /* Le futex n'est pas disponible ; attendre. */


        s = futex(futexp, FUTEX_WAIT, 0, NULL, NULL, 0);


        if (s == -1 && errno != EAGAIN)


            err(EXIT_FAILURE, "futex-FUTEX_WAIT");


    }
}
/* Relâcher le futex vers lequel pointe 'futexp' : si le futex a


  actuellement la valeur 0, positionner la valeur à 1 et réveiller tous les


  futex en attente pour que si le pair est bloqué dans fwait(), ça puisse


  continuer. */
static void
fpost(uint32_t *futexp)
{


    long            s;


    const uint32_t  zero = 0;


    /* atomic_compare_exchange_strong() a été décrit


       dans les commentaires ci-dessus. */


    if (atomic_compare_exchange_strong(futexp, &zero, 1)) {


        s = futex(futexp, FUTEX_WAKE, 1, NULL, NULL, 0);


        if (s  == -1)


            err(EXIT_FAILURE, "futex-FUTEX_WAKE");


    }
}
int
main(int argc, char *argv[])
{


    pid_t         childPid;


    unsigned int  nloops;


    setbuf(stdout, NULL);


    nloops = (argc > 1) ? atoi(argv[1]) : 5;


    /* Créer un tableau anonyme partagé qui gardera les futex.


       Comme les futex vont être partagés entre les processus, nous


        utilisons donc les opérations futex « shared » (donc pas celles


        dont le suffixe est "_PRIVATE") */


    iaddr = mmap(NULL, sizeof(*iaddr) * 2, PROT_READ | PROT_WRITE,


                 MAP_ANONYMOUS | MAP_SHARED, -1, 0);


    if (iaddr == MAP_FAILED)


        err(EXIT_FAILURE, "mmap");


    futex1 = &iaddr[0];


    futex2 = &iaddr[1];


    *futex1 = 0;        /* State: unavailable */


    *futex2 = 1;        /* State: available */


    /* Créer un processus enfant qui hérite du tableau anonyme


       partagé. */


    childPid = fork();


    if (childPid == -1)


        err(EXIT_FAILURE, "fork");


    if (childPid == 0) {        /* Child */


        for (unsigned int j = 0; j < nloops; j++) {


            fwait(futex1);


            printf("Child  (%jd) %u\n", (intmax_t) getpid(), j);


            fpost(futex2);


        }


        exit(EXIT_SUCCESS);


    }


    /* Le parent se retrouve ici. */


    for (unsigned int j = 0; j < nloops; j++) {


        fwait(futex2);


        printf("Parent (%jd) %u\n", (intmax_t) getpid(), j);


        fpost(futex1);


    }


    wait(NULL);


    exit(EXIT_SUCCESS);
}