{{{#!html
INDEX
}}}
[[PageOutline]]
**DOCS** →
[__**[wiki:Howto-TP Config]**__]
[__**[htdocs:cours/doc_MIPS32.pdf MIPS U]**__]
[__**[wiki:Doc-MIPS-Archi-Asm-kernel MIPS K]**__]
[__**[http://support.typora.io/Markdown-Reference markdown]**__]
[__**[htdocs:files/CR031_TPx_Nom1_Nom2.md.tgz CR.md]**__]
\\**COURS** →
[__**[htdocs:cours/Archi-2-B1-reboot-2p.pdf 1]**__ __([htdocs:cours/Archi-2-B1-code-2p.pdf +code]__) __([htdocs:cours/Archi-2-B1-outils-2p.pdf +outils]__)]
[__**[htdocs:cours/Archi-2-B2-interruptions-2p.pdf 2]**__]
[__**[htdocs:cours/Archi-2-B3-cache-archi-2p.pdf 3]**__]
[__**[htdocs:cours/Archi-2-B4-cache-perf-2p.pdf 4]**__]
[__**[htdocs:cours/Archi-2-B5-threads-2p.pdf 5]**__]
[__**[htdocs:cours/Archi-2-B6-alloc-2p.pdf 6]**__]
[__**[htdocs:cours/Archi-2-B7-synchro-2p.pdf 7]**__]
[__**[htdocs:cours/Archi-2-B8-initiateurs-2p.pdf 8]**__]
[__**[htdocs:cours/Archi-2-B9-ZDL-2p.pdf 9]**__]
\\**TME → **
[__**[wiki:AS6-TME-B1 1]**__]
[__**[wiki:AS6-TME-B2 2]**__]
[__**[wiki:AS6-TME-B3 3]**__]
[__**[wiki:AS6-TME-B4 4]**__]
[__**[wiki:AS6-TME-B5 5]**__]
[__**[wiki:AS6-TME-B6 6]**__]
[__**[wiki:AS6-TME-B7 7]**__]
[__**[wiki:AS6-TME-B8 8]**__]
[__**[wiki:AS6-TME-B9 9]**__]
\\**CODE → **
[__**[htdocs:files/kO6a2bin.tgz gcc + soc]**__]
[__**[htdocs:files/tp1.tgz 1]**__]
[__**[htdocs:files/tp2.tgz 2]**__]
[__**[htdocs:files/tp3.tgz 3]**__]
[__**[htdocs:files/tp4.tgz 4]**__]
[__**[htdocs:files/tp5.tgz 5]**__]
[__**[htdocs:files/tp6.tgz 6]**__]
[__**[htdocs:files/tp7.tgz 7]**__]
[__**[htdocs:files/tp8.tgz 8]**__]
[__**[htdocs:files/tp9.tgz 9]**__]
{{{#!html
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. `free`signifie 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.
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ème 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é que c'est une attente active, c'est mieux, selon moi.
* Il y a des implémentations avec des timeouts, ou avec distribution de tickets pour un traitement dans l'ordre, et d'autres.
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
* Une séquence atomique, dans notre contexte, est une séquence d'instructions qui ne peut être interrompue, ou si elle l'est on peut le savoir. Ça n'a pas de rapport direct avec les interruptions, mais en général, les séquences atomiques ne sont pas interruptibles et sont bornées dans le temps.
* On utilise les couples d'instructions LL/SC parce que le MIPS ne propose pas les instructions CAS et TAS et qu'il n'y a pas de mémoire de verrou.
'''
}}}
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 ------------------------------------------------------------------
'''
* C'est le premier qui fait SC qui emporte la mise, avec la séquence vue en cours pour le spin_lock. Puisque le suivant, on se verra refuser son SC étant donné qu'il y a eu une opération mémoire autre que LL sur ce verrou.
'''
}}}
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 ------------------------------------------------------------------
'''
* Non, le couple d'instructions LL/SC n'a pas le problème ABA. En effet, si on fait un compteur avec LL/SC. LL lit une valeur, on l'incrémente, et on tente d'écrire la valeur incrémentée avec un SC. S'il y eu des changement sur le compteur en mémoire, le SC sera refusé.
Ce qui ne serait pas le cas avec un CAS.
'''
}}}
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 ------------------------------------------------------------------
'''
* Il y a désormais la fonction `thread_wait()` qui permet à un thread (A) de passer de lui-même de l'état RUNNING à l'état WAIT, et la fonction `thread_notify()` qui permet à un thread (B) de faire passer un autre thread (A) de l'état WAIT à l'état READY.
* En cas de compétition, entre `thread_wait()` et `thread_notify()`, si `thread_notify()` s'exécute avant `thread_wait()`, il pourrait y avoir y risque que le thread (A) se mette en attente et ne soit pas notifié (puisque c'est déjà fait. Mais on sort de cette situation parce que `thread_wait()` peut savoir que `thread_notify` est déjà passé, car son propre état n'est plus RUNNING, il est READY.
* Non, ce ne sont pas des fonctions de l'API utilisateur, ces fonctions sont appelées par les services du noyau. La raison est qu'avant de passer un thread à WAIT, il doit déjà s'être enregistré dans une file d'attente d'une ressource et ce sont des structures internes du noyau. C'est pareil pour notify qui est invoqué lors d'une libération de ressource du noyau.
'''
}}}
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 ------------------------------------------------------------------
'''
* Non, un thread ne peut attendre (avec `thread_join) qu'un seul thread à la fois. Si on veut attendre plusieurs threads, il faut le faire en séquence.
'''
}}}
1. 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 ?
{{{#!protected ------------------------------------------------------------------
'''
* Un thread passe à DEAD lors de l'exécution d'un `thread_join()` par un autre thread.
* L'effacement a lieu après le passage à l'état DEAD et un thread ne peut pas s'effacer lui-même. Pour effacer, il faut exécuter du code, or pour exécuter du code, il faut une pile, et on ne peut pas effacer la pile parce qu'elle est utilisée. C'est pour ça que c'est toujours un autre thread qui fait le ménage.
* Dans le code de kO6, il n'y a pas encore de ménage, ça permet de voir les threads DEAD de l'affichage du contenu du scheduler. Mais, plus tard, cela devra être ajouté, par exemple, dans le scheduler. Quand un thread devient RUNNING, il peut regarder s'il y a eu un DEAD juste précédemment et l'effacer. On pourrait aussi, le faire au dernier moment quand le kernel n'a plus de place, alors il fait le ménage (un peu comme chez moi à certaines périodes :-)
'''
}}}
1. 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` ?
{{{#!protected ------------------------------------------------------------------
'''
* Le fait de ne pas rendre visibles les champs de la structure thread_s en dehors du fichier thread permet d'éviter des erreurs de programmation. En effet, pour modifier cette structure partagée, il faut prendre un verrou et le fait d'avoir réduit le nombre de fonctions ayant la possibilité de le faire est plus sûr.
* Dans la mesure du possible, on essaye de faire ça pour toutes les structures du kernel. Cela n'a rien d'obligatoire, c'est juste plus sûr.
'''
}}}
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 ------------------------------------------------------------------
'''
* Une condition de compétition, c'est quand on a deux séquences d'instructions indépendantes et pouvant être exécutée en parallèle et que l'état du système dépend de l'ordre d'exécution des instructions des deux séquences.
* Cela se produit par exemple entre `thread_wait(A)` et `tread_notify(A)`. Si les deux fonctions commencent en même temps, on veut que le résultat final soit que le thread A ne soit pas WAIT.
'''
}}}
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 ------------------------------------------------------------------
'''
* Fondamentalement, les spinlocks sont des verrous à attente active alors que les mutex sont des verrous à liste d'attente.
* Un Mutex utilise un spinlock pour garantir la séquence atomique d'accès à sa structure.
'''
}}}
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 ------------------------------------------------------------------
'''
* Le problème de errno, c'est qu'une application peut avoir plusieurs threads, c'est même le cas général, et chaque thread fait des appels système. Or lorsqu'un appel système sort, il doit mettre un code d'erreur dans la variable `errno`. Il soit y en avoir autant que de thread, mais toutes avec le même nom.
* `errno` est une variable globale locale au thread. Elle est dans le Thread Local Storage.
* Dans le cas de kO6, il n'y aura pas d'autres variables de cette catégorie pour le moment.
'''
}}}
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 ------------------------------------------------------------------
'''
* `__errno_location()` est une fonction qui rend l'adresse d'une case de mémoire. Si cette adresse est différente pour chaque thread, le problème est réglé/
'''
}}}
==
= 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)
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).
{{{#!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 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 ?
{{{#!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 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.
{{{#!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_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