Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Pr. Safae DAHMANI @: dahmani@inpt.ac.ma Bureau 111 Systèmes temps réel et criti

Pr. Safae DAHMANI @: dahmani@inpt.ac.ma Bureau 111 Systèmes temps réel et critiques (INE2) 21/04/2022 Chapitre II Partage des ressources et Synchronisation 21/04/2022 Synchronisation • Définition • Objets de synchronisation • Interblocage 21/04/2022 Synchronisation ●Les processus ne sont pas toujours indépendants : ○ Accès partagés aux ressources (mémoire partagée, périphérique, bus de communication, .. ) ○ Communications: échange de données Y Y = Y + 2 Y = Y ^ 2 X = Y + 2 Y = A ^ 2 Y Synchronisation ●Synchronisation: c’est le mécanisme qui permet de: ○ Garantir la cohérence des données partagées ○ Contrôler l’échange d’informations entre processus selon un protocole défini ●Synchronisation et temps réel: La synchronisation engendre la mise en attente des processus. ○ Attendre la fin d’un traitement, attendre la libération d’une ressource, respect de l’ordre d’exécution (notion de précédence) ■ A prendre en considération dans l’ordonnancement Synchronisation ●Section critique: un ensemble d’instructions manipulant une ou plusieurs ressources partagée ○ Plusieurs tâches peuvent accéder en concurrence à une ressource partagée (Ex. variable globale) Task_1 : count = count + 1 Task_2: count = count - 1 Task_1 Count = 5 Task_2 Read count = 5 Changement de contexte Read count = 5 Changement de contexte count = count – 1 count = 4 count = count + 1 count = 6 !! count vaut 6 pas 5 Synchronisation ●Section critique: ○ Maintenir un statut cohérent des ressources partagées par le biais de mécanisme d’exclusion mutuelle. Utilisation d’un objet de synchronisation Synchronisation ●La synchronisation entre les tâches nécessite un objet particulier qui permet de gérer cette synchronisation. ○ L’objet de synchronisation est partagé entre les tâches nécessitant la synchronisation ○ Il permet de réveiller/réactiver les tâches mises en attente ●Parmi les objets de synchronisation : ○ Mutex, ○ Sémaphore ○ Variable condition Ready Blocked Synchronisation ●Mutex (Mutual Exclusion) : Mécanisme de verrou pour la protection d’une section critique ●Lorsqu'une tâche souhaite accéder à une section critique elle doit d’abord acquérir le verrou: ○ Le verrou doit être libre/ouvert; aucune autre tâche n’est dans la section critique ○ La tâche devient momentanément propriétaire du verrou ○ Le verrou est ouvert de nouveau a la fin du traitement ○ Si le verrou est fermé au moment de l’acquisition, la tâche est suspendue jusqu’à réouverture du verrou Synchronisation ●Mutex (Mutual Exclusion) : ○ Variable Booléenne ○ Possède une liste d’attente ○ Manipulée par deux opérations atomiques: ■ Acquire (V) : ■ Release (V): void acquire(verrou v) { if (v) v = false else // Ajouter la tâche à la liste d’attente de v } void release(verrou v){ if (file_attente(v) != vide) // Débloquer une tâche en attente dans file else v = true} Synchronisation ●Mutex (Mutual Exclusion) : Initialiser(verrou) acquire(verrou) ... // Section critique ... release(verrou) Synchronisation ●Mutex (Mutual Exclusion) : Exemple POSIX #include <pthread.h> int pthread_mutex_init(pthread_mutex_t *mutex, pthread_mutexattr_t *attr); int pthread_mutex_destroy(pthread_mutex_t *mutex); int pthread_mutex_lock(pthread_mutex_t *mutex); int pthread_mutex_trylock(pthread_mutex_t *mutex); int pthread_mutex_unlock(pthread_mutex_t *mutex); Synchronisation ●Mutex (Mutual Exclusion) : Quand utiliser les Mutex ? ○ Lorsque plusieurs tâches accèdent à une variable partagée non seulement en lecture ○ Pour protéger l’accès à une ressource matérielle (Ex. Port de communication) Synchronisation ●Sémaphore (Dijkstra) : une généralisation de la notion de verrou ○ Variable entière au lieu d’une variable booléenne ●Le sémaphore est un objet sur lequel seulement 2 opérations sont possibles : ○ P(s) et V(s), toutes 2 atomiques. Synchronisation ●Sémaphore (Dijkstra) : une généralisation de la notion de verrou ○ Variable entière au lieu d’une variable booléenne ●Le sémaphore est un objet sur lequel seulement 2 opérations sont possibles : ○ P(s) et V(s), toutes 2 atomiques. ●P(s) décrémente la valeur du sémaphore et entraine le blocage du processus appelant si la valeur est devenue < 0 ●V(s) incrémente la valeur du sémaphore pouvant entrainer le déblocage d’un processus bloqué par P. Note: P signifie prendre et V libérer. Synchronisation ●Sémaphore (Dijkstra) : void P(sémaphore s) { s -= 1; if (s < 0) // Suspendre la tâche appelante dans la file associée à s } void V(sémaphore s) { s += 1; if (s <= 0) // Débloquer une des tâches de la file associée à s } Synchronisation ●A la différence d’un Mutex, un sémaphore permet à plusieurs tâches de rentrer dans une section critique commune ○ Un périphérique pourrait accepter un nombre limité de requêtes simultanées. ●Un sémaphore n’est pas détenu par une tâche ○ En effet, plusieurs tâches peuvent entrer dans la section critique, en utilisant le même sémaphore Synchronisation #include <semaphore.h> int sem_init(sem_t *semaphore, int pshared, unsigned int initial_value); int sem_destroy(sem_t *semaphore); int sem_wait(sem_t *semaphore); int sem_trywait(sem_t *semaphore); int sem_post(sem_t *semaphore); • Sémaphore: Exemple POSIX Synchronisation ●Exercice: Exclusion mutuelle ○ Tâche1 Tâche2: signifie que Tâche1 doit être exécutée avant tâche2. ○ Tâche numéro « i » exécute la section numéro « i » (Si) ●Utilisez des sémaphores pour synchroniser les processus de manière à respecter les contraintes du graphe de préséance ci-dessus. T1 T3 T2 T4 Synchronisation ●Variable condition : ○ Concept de moniteurs (synchronisation dans la programmation orientée objet): ■ Constructeur encapsulant un type de donnée et les opérateurs qui le manipulent ■ L’exécution dans un moniteur permet de garantir l’exclusion mutuelle entre les opérations ○ Méthode de synchronisation utilisée dans Java Synchronisation ●Variable condition : ○ Concept de moniteurs (synchronisation dans la programmation orientée objet): ■ Constructeur encapsulant un type de donnée et les opérateurs qui le manipulent ■ L’exécution dans un moniteur permet de garantir l’exclusion mutuelle entre les opérations ○ Méthode de synchronisation utilisée dans Java Les variables condition sont utilisée pour bloquer un processus dans un moniteur Synchronisation ●Variable condition : ○ Deux opérations possibles sur une variable condition C : ■ Wait : assure le blocage du processus appelant et la libération de l’accès au moniteur ■ Signal: est une opération vide si aucun processus n’est bloqué sur cette condition. Sinon, le processus “signaleur” est suspendu et un processus bloqué sur C est réactivé. ● Le processus signaleur ne reprend le contrôle du moniteur qu’après la fin de la dernière opération en cours sur celui-ci. Synchronisation ●Variable condition : ○ Concept de moniteurs (synchronisation dans la programmation orientée objet): ■ Constructeur encapsulant un type de donnée et les opérateurs qui le manipulent ■ L’exécution dans un moniteurs permet de garantir l’exclusion mutuelle entre les opérations les variables condition sont utilisée pour bloquer un processus dans un moniteur Synchronisation #include <pthread.h> int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *attributes); int pthread_cond_destroy(pthread_cond_t *cond); int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); int pthread_cond_timedwait(pthread_cond_t *cond, pthread_mutex_t *mutex, struct timespec *expiration); int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_broadcast(pthread_cond_t *cond); • Variable condition: Exemple POSIX Synchronisation ●Tickets Lock: A la différence du sémaphore classique (l’ordre de déblocage après un V n’est pas défini), le mécanisme de ticket permet une gestion explicite de la file d’attente. VAR courant : entier = 0, suivant : entier = 0, c : condition MONITEUR prendre_ticket mon_ticket ← suivant suivant ← suivant + 1 TANT QUE courant 6 = mon_ticket WAIT(c) FIN TANT QUE FIN MONITEUR libérer_ticket courant ← courant + 1 COND_BROADCAST(c) FIN Synchronisation ● Synchronisation par message: Un processus peut attendre qu’un autre lui envoie un message. Un Object unique est utilisé à la fois pour la synchronisation et l’échange de données. ○ Utilisée entre processus sans mémoire partagée • Message synchrone: • Message asynchrone (sans attente): • L'émetteur attend que le récepteur ait lu le message • Le récepteur qui attend un message est bloqué jusqu'à son arrivée • L'émetteur n'est pas bloqué en attente de la réception • Le récepteur a un rythme autonome de réception, avec deux modes : • Réception bloquante si pas de message • Réception non bloquante, avec un témoin de réception • Acquittement explicite Synchronisation ●Interblocage (Dead Lock): Un processus est en état d’interblocage s’il est bloqué en attente d’une condition qui ne se produira jamais. ●Conditions nécessaires : 1. Les processus accèdent en exclusion mutuelle à des ressources critiques. 2. Les processus gardent les ressources acquises pendant qu’ils sont bloqués en attente d’une autre ressource. 3. Les ressources acquises par un processus ne peuvent lui être retirées de l’extérieur. 4. Il existe un cycle de processus où chacun attend une ressource acquise par un autre. Synchronisation ●Interblocage (Dead Lock): Un processus est en état d’interblocage s’il est bloqué en attente d’une condition qui ne se produira jamais. T1 T2 R1 R2 Synchronisation ●Interblocage (Dead Lock): Un processus est en état d’interblocage s’il est bloqué en attente d’une condition qui ne se produira jamais. ○ Prévenir: ■ Prévenir statiquement en empêchant l’arrivée du deadlock ■ Esquiver dynamiquement l’arrivée du deadlock ○ Guérir ■ Détection ■ Récupération Synchronisation ●Prévention statique: ○ Il suffit qu’une seule des 4 conditions nécessaires précédentes soit fausse : ■ Pas de partage de ressources (pas intéressant) ■ Allocation globale des ressources en une seule fois ■ Libération des ressources acquises avant blocage (allocation conditionnelle) Ordonnancement de l’allocation des ressources Synchronisation ●Prévention dynamique (esquive): ○ Algorithme du banquier : (Dijkstra) ■ Chaque processus annonce le nombre max de ressources de chaque type qu’il allouera. uploads/Industriel/ synchronisation.pdf