[[PageOutline]]
**
{{{#!html
Mécanismes de synchronisation
}}}
Vous pouvez lire les [htdocs:cours/Archi-2-B7-synchro-2p.pdf 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.
1. 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.
{{{#!protected ------------------------------------------------------------------
'''
* Dès lors que les allocations peuvent être demandées en parallèle et qu'elles ont besoin d'accéder en écriture à des structures partagées, il faut garantir que plusieurs modifications n'arrivent pas en même temps.
* Dans kO6, les appels systèmes ne sont pas interruptibles. Cela signifie que, lorsque vous demandez au système de créer un objet (un thread par exemple) et qu'il utilise ses allocateurs de mémoire (`malloc_ustack()` et `kmalloc()`), il n'y a pas de risque de compétition avec d'autres threads sur le même core, parce que si le tick courant s'achève, l'IRQ du timer sera masquée et donc ne sera traitée que lorsque les allocations seront terminées. Mais il y a un risque s'il y a deux cores, parce qu'ils seront en vrai parallélisme. Pour le moment, il n'y a qu'un core parce qu'avec deux cores, il y a le problème de la cohérence des caches non traitée dans cette version du SoC. Il n'y a donc pas de risque pour les allocations du noyau, mais nous mettrons quand même les protections pour le futur.
* Pour les allocations de l'utilisateur, il y a un vrai problème. Un malloc peut parfaitement être interrompu par une IRQ du timer provoquant un changement de thread, lequel peut aussi demander une allocation.
'''
}}}
1. Un verrou est une mémoire à deux états, quelles sont les deux opérations de l'API de gestion vu en cours ?
{{{#!protected ------------------------------------------------------------------
'''
* Une opération de verrouillage pour mettre à 1 le verrou s'il est à 0 : `spin_lock(lock)`
* Une opération de déverrouillage pour le mettre à 0 : `spin_unlock(lock)`
* Parfois, on a des API où `spin_lock()` est nommée `lock_acquire()` et `spin_unlock()` est nommée `lock_release()`, mais c'est la même idée. `spin` fait bien pensée que c'est une attente active, c'est mieux je trouve.
* Il y a des implémentations avec des timeouts, ou avec distribution de tickets pour un traitement dans l'ordre,...
'''
}}}
1. Nous avons vu 4 mécanismes permettant de réaliser une "séquence atomique" pour les opérations read-modify-write. Que signifie "séquence atomique"? Est-ce que cela a un rapport avec les interruptions ? Parmi les 4 solutions, laquelle allons-nous utiliser et pourquoi ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. Un thread passe de l'état RUNNING à l'état ZOMBIE lorsqu'il appelle `thread_exit()`. Quand passe-t-il à l'état DEAD ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. Le contenu de la structure `struct thread_s` (c'est-à-dire les champs qui la compose) 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éfnis par un `typedef struct thread_s * thread_t`. Pourquoi ce choix, pourquoi n'avoir pas définie la structure `thread_s` dans le fichier `kernel/kthread.h` ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
*
'''
}}}
==
= B. Travaux pratiques
Commencez par récupérer le code de source de la séance [attachment:s7.tgz 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).
{{{#!c
//--------------------------------------------------------------------------------------------------
// 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 ?
{{{#!c
#include
#include
#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
{{{#!c
#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