| Version 19 (modified by , 2 years ago) (diff) |
|---|
Mécanismes de synchronisation
Vous pouvez lire les slides de cours pour voir les détails, mais voici le résumé des principes en quelques lignes.
- 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.
(à compléter)
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 etmalloc()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()etthread_exit()fonctionnent de manière coordonnée,thread_join()permet à un thread de se mettre en attente de l'exécution dethread_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 ? - Le contenu de la structure
struct thread_s(c'est-à-dire les champs qui la compose) est définie dans le fichierkernel/kthread.c. En conséquence cette structure n'est utilisable que par les fonctions de ce même fichierkernel/kthread.c. A l'extérieur, les fonctions ne manipulent que des pointeurs sur la structure de typethread_t(défnis par untypedef struct thread_s * thread_t. Pourquoi ce choix, pourquoi n'avoir pas définie la structurethread_sdans le fichierkernel/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 avecerrnodans le cas des applications multi-thread ? - Le système définit
errnode la façon suivante :#define errno *__errno_location(), que fait la fonctionerrno_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)
En préalable de tous les exercices, quelques questions sur le code. 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.
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
│ ├── Makefile
│ └── main.c
└── ulib
├── Makefile
├── crt0.c
├── libc.c
├── libc.h
├── memory.c
├── memory.h
├── thread.c
├── thread.h
└── user.ld
B.1.
B.2.
B.3. 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 FEALURE */ 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 voue allez devoir répondre à quelques questions
#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_lock (&b->lock); // release the ownership return EBUSY; // return an error } b->expected = count; // set the number of expected threads spin_lock (&b->lock); // release the ownership return SUCCESS; // it's fine } int thread_barrier_wait (thread_barrier_t * barrier) { thread_barrier_t b = *barrier; // get the barrier pointer if (b == NULL) return EINVAL; // b is not created if (b && (b->magic != MAGIC_BARRIER)) return EINVAL; // check that it is barrier (MAGIC) spin_lock (&b->lock); // get the ownership b->waiting++; // the current thread is the newcomer if (b->waiting == b->expected) { // list_foreach (&b->wait, waiting_item) { // list_unlink (waiting_item); // thread_t t = thread_item (waiting_item); // get the pointer of a waiting thread thread_notify (t); // } b->waiting = 0; // spin_unlock (&b->lock); // } else { thread_addlast (&b->wait, ThreadCurrent); // the current thread in the wait. list spin_unlock (&b->lock); // thread_wait (); // return SUCCESS; // it's fine } == B.4. Ajout de l'API des sémaphores
