Context Navigation

INDEX

1. Résumé des concepts et des mécanismes du cours
A. Questions de cours
B. Travaux pratiques

DOCS → [Config] [MIPS U] [MIPS K] [markdown] [CR.md]
COURS → [1 (+code) (+outils)] [2] [3] [4] [5] [6] [7] [8] [9]
TME → [1] [2] [3] [4] [5] [6] [7] [8] [9]
CODE → [gcc + soc] [1] [2] [3] [4] [5] [6] [7] [8] [9]

7 - Mécanismes de synchronisation

Résumé des concepts et des mécanismes du cours

Il est nécessaire d'avoir des mécanismes de synchronisation
- Dès lors que plusieurs threads se partagent le processeur et que ces threads peuvent utiliser les mêmes ressources, il est nécessaire d'avoir des mécanismes de synchronisation afin de décider de la propriété des ressources.
- Plus généralement, la propriété d'une ressource c'est le droit de la modifier, c'est à dire le droit de faire des écritures aux adresses où est mappée la ressource dans l'espace d'adressage.

Le mécanisme de base est le verrou
- Les mécanismes de synchronisation s'appuient un mécanisme élémentaire, le verrou binaire, un objet à deux états : busy/free. busy signifie que le verrou est fermé que l'on ne peut pas avancer au delà dans le programme. freesignifie que le verrou est ouvert et que l'on peut passer.
- Il y a deux opérations de base: lock/unlock. L'opération lock signifie le souhait de fermer le verrou (pour interdire aux autres de passer, on dit aussi prendre le verrou), donc de passer l'état à busy, ce qui n'est possible que s'il est free. lock est donc bloquant si verrou est déjà busy et c'est une attente active (une boucle jusqu'à réussite). unlock signifie ouvrir le verrou ou lâcher le verrou. Ce n'est pas bloquant.
- Le mécanisme de base des verrous utilise la possibilité de réaliser une séquence atomique d'instructions read-modify-write qui permet de lire l'état du verrou, de le tester et de le modifier s'il est libre avec la garantie que si on y parvient on est le seul.
- Il existe plusieurs solutions matérielles pour implémenter les verrous avec des instructions permettant de créer des séquences atomiques d'instructions : mémoire de verrous, instructions CAS, TAS ou couples d'instruction LL/SC.
- Il existe plusieurs type de verrous : simples, à tickets, avec timeout, etc.

Les threads ont désormais 5 états
- READY : état d'attente du processeur
- RUNNING : état en exécution
- WAIT : état d'attente d'une ressource
- ZOMBIE : état terminé mais valeur de retour non lue (donc non effaçable)
- DEAD : état terminé et valeur de retour lue (donc effaçable)

Les ressources partagées gèrent des listes d'attente de threads
- Quand une ressource est partagée, il existe une API permettant de prendre la ressource (ici prendre est très général, le nom de la fonction dépend du type de ressource.
- Si la ressource n'est pas disponible, le thread demandeur est mis en attente dans une liste d'attente de thread dans l'état WAIT. Cette liste est propre à chaque ressource.
- Un thread sort de la liste d'attente lorsque le propriétaire actuel rend la ressource et le choisit parmi tous ceux en train d'attendre. Il repasse à l'état READY donc éligible par l'ordonnanceur.

Les deux nouvelles fonctions de transition d'états pour les threads
- thread_wait() : qui passe le thread courant de RUNNING à WAIT
- thread_notify() : qui passe le thread en argument de WAIT à READY
- Ces deux fonctions sont utilisées par les fonctions du noyau qui gère l'attribution des ressources partagée.
- Quand un thread veut prendre une ressource indisponible, il s'accroche à la liste d'attente de la la ressource et il appelle thread_wait().
- Quand un thread libère une ressource et que celle-ci est attendue, le libérateur choisit un thread de la liste d'attente, il le décroche et il appelle thread_notify().
- Le choix du thread parmi tous ceux en attente est une opération d'ordonnancement, ici c'est l'ordre premier-arrivé-premier-servi.

"Race Condition" ou "Condition de Compétition"
- On est en présence d'une race condition lorsque deux séquences d'instructions s'exécutant en même temps, donnent un résultat différent suivant l'ordre relatif des instructions.
- Par exemple thread_wait() et thread_notify() peuvent être appelées en même temps, wait par le thread demandeur d'une ressource occupée et notify par le thread libérateur de la ressource. L'issue doit être que le thread demandeur soit en possession de la ressource et dans l'état READY. Mais, il y a un risque qu'il soit en possession de la ressource dans l'état WAIT.
- La résolution des race condition passent par l'usage des verrous afin de garantir des séquences atomiques d'instruction (le test d'une condition et la décision ne doivent pas être séparés).

Le Mutex est un verrou avec liste d'attente utilisable par l'application
- On peut utiliser des spinlocks en mode utilisateur, mais ce sont des attentes actives ce qui signifie qu'un thread peut passer tout son quantum de temps processeur à attendre.
- Les mutex permettent d'éviter cette attente inutile en mettant explicitement les threads demandeur dans une liste d'attente, dans un état inéligible par l'ordonnanceur.
- Les threads sortent de la liste d'attente dès que le mutex est libéré.
- Les opérations de bases sont lock/unlock comme pour le spinlock.
- Seul le thread ayant verrouillé lock un mutex a le droit de le déverrouiller unlock.

thread_join() permet à un thread d'attendre le thread_join() d'un autre
- Un thread rend un pointeur générique void * lors de sa terminaison. Ce pointeur void * ne peut être récupérer que par un appel à la fonction thread_join(thread_t th, void **retval) avec comme arguments: le thread attendu th et un pointeur sur une variable pouvant contenir un pointeur générique void * (void **retval).
- thread_join() permet donc de se mettre en attente de la terminaison d'un thread.
- thread_join() est une fonction bloquante pour le thread qui fait le join, sauf si le thread attendu est déjà terminé.
- C'est thread_join() qui fait passer l'état du thread attendu de ZOMBIE à DEAD.

Les codes d'erreur des appels systèmes sont dans la variable globale errno
- La variable errno est globale parce qu'elle est connue et utilisable par toutes les fonctions de l'application, mais chaque thread dispose de sa propre valeur.
- Les variables globales mais locales aux threads font partie du thread local storage
- Pour ko6, cette variable globale est placé en haut de chaque pile utilisateur, il y a donc autant de valeurs possibles de cette variable qu'il y a de threads.
- On obtient l'adresse de la variable par un syscall.

A. Questions de cours

La majorité des réponses aux questions sont dans le cours ou dans le rappel du cours donné au début de cette page, c'est voulu. Les questions suivent à peu près l'ordre du cours, elles sont simples, mais vous avez besoin de comprendre le cours pour y répondre :-) Quand une question vous demande si quelque chose est vrai ou faux, ne répondez pas juste "oui" ou "non », mais justifiez vos réponses avec une petite phrase. Le but de ces questions est d'évaluer vos connaissances, donc plus vous êtes précis, mieux c'est.

Lors de la précédente séance, nous avons ajouté 3 allocateurs de mémoire dynamique : malloc_ustack() pour les piles user des threads, kmalloc() pour les objets du noyau et malloc() pour les segments de l'application. Est-ce que les 3 opérations d'allocation citées sont concernées par les synchros ? Justifiez.
Un verrou est une mémoire à deux états, quelles sont les deux opérations de l'API de gestion vu en cours ?
Nous avons vu 4 mécanismes permettant de réaliser une "séquence atomique" pour les opérations read-modify-write. Que signifie ici "séquence atomique"? Est-ce que cela a un rapport avec les interruptions ? Parmi les 4 solutions, laquelle allons-nous utiliser et pourquoi ?
Si deux threads A et B veulent prendre un verrou libre V et effectue la séquence LL/SC sur le verrou V : A exécute LL en premier et voit le verrou libre, puis B exécute à son LL et voit aussi le verrou libre. Les deux threads vont faire un SC. En fonction de l'ordre des SC, qui va pouvoir prendre le verrou ?
Nous avons vu le problème ABA, est-ce que la solution proposée par le MIPS pour gérer les sections-critiques à ce problème ? Si non, est-ce que cela a un coût matériel ?
Les threads avaient 3 états différents : READY (en attente du processeur), RUNNING (en cours d'exécution) et DEAD (définitivement stoppé et effaçable). Ils ont désormais 2 nouveaux états : WAIT (en attente d'une ressource) et ZOMBIE (définitivement stoppé, mais en attente qu'un autre thread récupère la valeur de retour). Quelles sont les deux nouvelles fonctions de l'API kernel des threads permettant respectivement de passer de l'état RUNNING à l'état WAIT et de l'état WAIT à l'état READY ? Est-ce que ces fonctions sont utilisables par l'application ?
Les fonctions thread_join() et thread_exit() fonctionnent de manière coordonnée, thread_join() permet à un thread de se mettre en attente de l'exécution de thread_exit() par un autre. Est-ce qu'un thread peut attendre simultanément plusieurs threads en même temps ?
Un thread passe de l'état RUNNING à l'état ZOMBIE lorsqu'il appelle thread_exit(). Quand passe-t-il à l'état DEAD ? Quand est-ce qu'on efface la pile et les structures utilisées par un thread, est-ce qu'un thread peut s'effacer lui-même ?
Le contenu de la structure struct thread_s (c'est-à-dire les champs qui la composent) est définie dans le fichier kernel/kthread.c. En conséquence cette structure n'est utilisable que par les fonctions de ce même fichier kernel/kthread.c. A l'extérieur, les fonctions ne manipulent que des pointeurs sur la structure de type thread_t (définis par un typedef struct thread_s * thread_t. Pourquoi ce choix, pourquoi n'avoir pas défini la structure thread_s dans le fichier kernel/kthread.h ?
Qu'est qu'une race condition (en français c'est traduit par "condition de compétition") ? Est-ce que c'est vraiment un problème ou seulement un problème d'optimisation de code ? Donnez un exemple de cas où cela se produit ?
Les spinlocks et les mutex sont deux mécanismes permettant d'implémenter les verrous. Qu'est-ce qui les distingue ? Lequel s'appuie sur l'autre ?
Les appels système peuvent ne pas pouvoir rendre les services qu'on leur demande, soit parce que les ressources ne sont pas disponibles, soit parce que les arguments sont erronés. Pour informer l'utilisateur de l'échec, ils rendent souvent un code d'erreur, lequel est aussi présent dans une variable globale nommée errno. Pourquoi, est-ce qu'il y a un problème avec errno dans le cas des applications multi-thread ?
Le système définit errno de la façon suivante : #define errno *__errno_location(), que fait la fonction __errno_location() ? Comment cela peut régler le problème ?

B. Travaux pratiques

Commencez par récupérer le code de source de la séance s7.tgz

Pour la partie pratique, vous allez devoir programmer un peu. Les premières questions sont assez faciles, les dernières un peu moins, faites ce que vous pouvez. Je ne vous demande pas de faire tous les exercices, d'autant qu'il n'y aura pas de correction pour le moment (faute de temps). Le but est de vous «forcer» à entrer dans le code et même des petites modifications suffisent. Les exercices sont classés par niveau de difficultés supposées (on est jamais à l'abri de surprise)

Dans le répertoire s7 vous trouvez le répertoire 01_synchro qui contient le code complet des nouveaux mécanismes de synchro. Cela a un impact sur hcpua.S pour les spinlocks, kthread.[ch] pour la gestion des deux nouveaux états WAIT et ZOMBIE, en particulier les fonctions thread_wait et thread_notify, et évidemment thread.[ch] pour l'ajout des appels systèmes.

Il y a trois répertoires d'application : app0, app1 et app2. Quand vous exécutez make exec, c'est l'application app0 qui est utilisée, c'est celle par défaut. Pour les autres, vous devez utilisez la commande make APP=1 exec ou make APP=2 exec. Vous pouvez changer l'application par défaut si vous changez la valeur par défaut de la variable APP dans le makefile.

01_synchro
├── Makefile
├── common
│   ├── debug_off.h
│   ├── debug_on.h
│   ├── errno.h          // codes d'erreur des appels système
│   ├── esc_code.h       // séquence d'échappement ASCII 
│   ├── list.h
│   ├── syscalls.h
│   └── usermem.h
├── kernel
│   ├── Makefile
│   ├── harch.c
│   ├── harch.h
│   ├── hcpu.h
│   ├── hcpua.S
│   ├── hcpuc.c
│   ├── kernel.ld
│   ├── kinit.c
│   ├── klibc.c
│   ├── klibc.h
│   ├── kmemory.c
│   ├── kmemory.h
│   ├── ksynchro.c       // mutex et autres implémentation
│   ├── ksynchro.h       // mutex et autres protopypes
│   ├── ksyscalls.c
│   ├── kthread.c
│   └── kthread.h
├── uapp[012]            // Il y a 3 répertoires d'application
│   ├── Makefile
│   └── main.c
└── ulib
    ├── Makefile
    ├── crt0.c
    ├── libc.c
    ├── libc.h
    ├── memory.c
    ├── memory.h
    ├── thread.c
    ├── thread.h
    └── user.ld

B.1. `uapp0` et `uapp1`

Les deux programmes testent respectivement, l'API exit/join et mutex.

décrivez les programmes...

B.2. `uapp2` : Mécanisme des barrières

En cours, nous avons vu le mécanisme de base, le spinlock (ou busylock) réalisant une prise de verrou par attente active. Nous avons aussi vu le mutex ayant aussi comme finalité de prendre un verrou, mais cette fois sans attente active, en organisant une liste d'attente des threads. Notez que nous avons présenté les spinlocks pour le noyau et les mutex pour l'utilisateur, mais il est parfaitement possible d'avoir des spinlocks en mode utilisateur (LL et SC n'étant pas des instructions privilégiées) et des mutex en mode noyau.

Il existe plein d'autres mécanismes de synchronisation, par exemple, les sémaphores, les variables de conditions, les read-write lock, ou les barrières de synchronisation. Nous allons, ici nous intéresser aux barrières.

Les barrières de synchronisation sont utilisées pour synchroniser les étapes de calculs réalisés par plusieurs threads. Supposons que l'on souhaite exécuter deux threads en parallèle et que l'on veuille attendre que les deux aient terminé leur travail avant de recommencer un travail. Il faut que les deux threads se donnent rendez-vous à la fin de leur calcul.

L'API des barrières est composée de trois functions (prototypes définis dans ulib/thread.h pour les appels systèmes coté utilisateur et dans kernel/ksynchro.h pour les prototypes de fonctions implémentées) c'est évidemment les mêmes prototypes (si vous ne comprenez pas pourquoi, demandez le moi).

//--------------------------------------------------------------------------------------------------
// Barrier API 
//--------------------------------------------------------------------------------------------------

/**
 * \brief   hidden barrier type, the user do not what is in the barrier structure
 */
typedef struct thread_barrier_s * thread_barrier_t;

/**
 * \brief   creates or initialize a barrier depending the value of barrier parameter
 * \param   barrier a pointer referencing the barrier, there are two cases
 *                  1) if *barrier == NULL then allocate a new barrier, then initialize count
 *                  2) if *barrier != NULL it the barrier already exists, just initialize count 
 * \param   count   number of expected threads for this barrier
 * \return  SUCCESS if it all goes fine or
 *          EINVAL  The value specified by count is equal to zero.
 *          ENOMEM  Insufficient memory exists to initialize the barrier
 *          EBUSY   The implementation has detected an attempt to reinitialize a barrier 
 *                  while it is in use (for example, while being used in a  thread_barrier_wait()  
 *                  call) by  another thread.
 */
extern int thread_barrier_init (thread_barrier_t * barrier, size_t count);

/**
 * \brief   wait to the referenced barrier, it is a blocking operation for all thread but the last
 *          the last arrived thread doesn't wait and notifies the other threads which becomes READY 
 * \param   barrier a pointer referencing a barrier 
 * \return  SUCCESS or FAiLURE
 */
extern int thread_barrier_wait (thread_barrier_t * barrier);

/**
 * \brief   destroy the referenced barrier
 *          If a thread is waiting at the barrier, then the destruction is not done, it is an error
 * \param   barrier a pointer referencing a barrier 
 * \return  SUCCESS if it all goes fine or
 *          EINVAL  wrong argument
 *          EBUSY   The implementation has detected an attempt to destroy a barrier 
 *                  while it is in use (for example, while being used in a  thread_barrier_wait()  
 *                  call) by  another thread.
 */
extern int thread_barrier_destroy (thread_barrier_t * barrier);

Voici, un exemple d'utilisation. Dans le code, fourni, l'attente à la barrière est mise en commentaire;

Exécutez, ce programme make APP=2 exec : qu'observez-vous ?
Retirez le commentaire devant thread_barrier_wait (&barrier), réexécutez, qu'observez-vous ?
Modifiez un peu le code pour synchroniser aussi les itérations de la fonction main(), il y a donc 3 threads. qu'observez-vous ?

#include <libc.h>
#include <thread.h>

#define DELAY(n) for(int i=n;i--;) __asm__("nop"); 

struct arg_s {                 // structure pour passer des args aux threads
    int delay;                 // délai qui simule une durée de calcul 
    char *message;             // chaine de caractères
};

thread_t t0, t1;               // 2 threads
struct arg_s a0, a1;           // les arguments des threads      
thread_barrier_t barrier;      // 1 barrière

void * t0_fun (void * arg)     // thread qui sera instantié deux fois
{
    struct arg_s * a = arg;
    for (int i=0;1;i++) {                         // faire toujours
        fprintf (1, "[%d] %s\n", i, a->message);  //   afficher un message
        DELAY ((a->delay) * (1 + rand()%2));      //   delay aléatoire
//      thread_barrier_wait (&barrier);           //   attendre les autres
    };
}

int main (void)
{
    thread_barrier_init (&barrier, 2);       // Créer une barrière pour 2

    a0.delay = 500000;                       // args premier thread
    a0.message = "bonjour";

    a1.delay = 2000000;                      // args deuxième thread
    a1.message = "salut";

    thread_create (&t0, t0_fun, &a0);        // démarrer premier thread
    thread_create (&t0, t0_fun, &a1);        // démarrer deuxième thread

    for (int i=0;1;i++) {
        fprintf (0, "[%d] main alive\n", i); // message
        DELAY(100000);                       // delay
    }

    void * trash;                            // attendre la fin mais
    thread_join (t1, &trash);                // on jette le résultat
    thread_join (t0, &trash);                // et on arrivera jamais
    return 0;                                // ici en réalité
}

Maintenant, vous n'allez pas avoir à écrire le code des barrières mais je vous demande de commenter la fonction barrier_wait() avec vos propres mots. Commencez sans regarder le code et après ouvrez le code et lisez les commentaires.

#define MAGIC_BARRIER   0xDEADBABA

struct thread_barrier_s {
    int         magic;          ///< magic number to check the validity of the barrier
    spinlock_t  lock;           ///< protection against parallel modifications
    size_t      expected;       ///< number of expected threads
    size_t      waiting;        ///< number of threads waiting
    list_t      wait;           ///< list element to chain threads that are wainting for the mutex
};

int thread_barrier_init (thread_barrier_t * barrier, size_t count)
{
    thread_barrier_t b = *barrier;                          // get the barrier pointer

    if (count == 0) return EINVAL;                          // count must be > 0

    if (b == NULL) {                                        // if we need a new barrier
        b = kmalloc (sizeof (struct thread_barrier_s));     // allocates a new barrier
        if (b == NULL) return ENOMEM;                       // test if there is enough memory
        b->magic = MAGIC_BARRIER;                           // tell it is a BARRIER
        b->lock = 0;                                        // free the lock
        b->expected = count;                                // init the expected threads
        b->waiting = 0;                                     // init the counter of waiting threads
        list_init (&b->wait);                               // init the waiting list
        *barrier = b;                                       // at last, init. the return variable
        return SUCCESS;                                     // it's fine
    }

    if (b && (b->magic != MAGIC_BARRIER)) return EINVAL;    // it is not an old barrier

    spin_lock (&b->lock);                                   // get the ownership
    if (b->waiting != 0) {                                  // if someone is waiting
        spin_unlock (&b->lock);                             // release the ownership
        return EBUSY;                                       // return an error
    }

    b->expected = count;                                    // set the number of expected threads
    spin_unlock (&b->lock);                                 // release the ownership

    return SUCCESS;                                         // it's fine
}

int thread_barrier_wait (thread_barrier_t * barrier)
{
    thread_barrier_t b = *barrier;                          // 

    if (b == NULL) return EINVAL;                           // 
    if (b && (b->magic != MAGIC_BARRIER)) return EINVAL;    // 

    spin_lock (&b->lock);                                   // 
    b->waiting++;                                           // 
    if (b->waiting == b->expected) {                        // 
        list_foreach (&b->wait, waiting_item) {             // 
            list_unlink (waiting_item);                     // 
            thread_t t = thread_item (waiting_item);        // 
            thread_notify (t);                              // 
        }
        b->waiting = 0;                                     // 
        spin_unlock (&b->lock);                             // 
    } else {
        thread_addlast (&b->wait, ThreadCurrent);           // 
        spin_unlock (&b->lock);                             // 
        thread_wait ();                                     // 

    return SUCCESS;                                         // 
}

B.3. Ajout de l'API des sémaphores

Les sémaphores sont un mécanisme de synchronisation permettant de synchroniser des threads ou des processus. Nous n'avons qu'un seul processus, alors nous n'allons l'utiliser que pour les threads.

Je vous propose l'API suivante:

typedef struct sem_s * sem_t;
sem_init (sem_t * sem, int value);
- pour créer et initialiser un sémaphore sem à la valeur value
- vous pouvez traiter les erreurs ou pas...
sem_wait (sem_t);
- si la valeur du sémaphore est nul, le thread se met en attente
- sinon décremente le sémaphore et continue
sem_post (sem_t * sem);
- s'il y a un thread en attente, le notifier
- sinon incrémenter la valeur du sémaphore
sem_destroy (sem_t);
- détruire le sémaphore
- vous pouvez traiter les cas d'erreur.

Vous allez devoir modifier les fichiers (commenter votre code).

ulib/thread.h
ulib/thread.c
common/syscall.h
kernel/ksyscall.c
kernel/ksynchro.h
kernel/ksynchro.c

Last modified 7 weeks ago Last modified on Apr 3, 2024, 7:26:27 AM

Download in other formats:

Plain Text