Aperçu des sections

  • Les algorithmes distribués


           Les algorithmes distribués       

    AND | FEMTO-ST

    Réalisé par : 

    Dr. Benaboud Rohallah

    Objectifs:

    Vous devez abandonner vos objectifs pour réussir. Voici pourquoi : - Virtuose de la Vie

    Le parallélisme est présent dans la vie quotidienne des étudiants (internet, client-serveur, pair à pair, téléphonie mobile, interfaces, etc.), souvent à leur insu, et dans leur cursus antérieur (systèmes, architecture). Ce qui relève d'une manière générale les aspects algorithmiques des systèmes distribués (aussi appelés répartis).

    Concevoir une application distribuée fiable, c'est faire qu'elle tolère l'asynchronisme des calculs et des communications. S'assurer de la fiabilité d'une application existante, c'est vérifier qu'elle lui résiste. Du fait de cet asynchronisme, un univers réparti se caractérise par l'absence de temps global (et pour d'autres raisons, par l'existence de défaillances). Il apparaît non-déterministe. L'enseignement vise d'abord à faire bien prendre conscience de ces problèmes et de leur complexité, puis à présenter des algorithmes aidant à y faire face.

    Ce cours d'algorithmes distribués consiste à :

                                                                                           • Introduire le calcul distribué

                                                                                           • Concevoir et analyser des algorithmes distribués

                                                                                           • Programmer des algorithmes (c.f. TP).


    Public cible :

    Public cible images libres de droit, photos de Public cible | Depositphotos

    Ce  cours  est  orienté  vers  les  étudiants  de  première année Master , spécialité  (architectures distribuées),  Filière  ( Informatique)  et  aussi  à  toute  personne  souhaitant  d' acquérir  des  informations  sur  les algorithmes distribués.

    Plan global du contenu

    New Normal or Next Normal - Tips on Managing an Ever-Changing Environment - Have a Plan! - Aspyre

    Ce  cours  est  structuré  en  sept principaux  chapitres  et  ce  conformément au programme officiel (harmonisation de 2016-2017) :

                                                                              Chapitre 01 : Introduction aux systèmes distribués

                                                                              Chapitre 02 : Le temps logique

                                                                              Chapitre 03 : L’exclusion mutuelle en réparti

                                                                              Chapitre 04 : Allocation répartie de ressources

                                                                              Chapitre 05 : Coordination par rendez-vous

                                                                              Chapitre 06 : L’observation répartie

                                                                              Chapitre 07 : Construction d’un temps virtuelle


    Mode  d’évaluation :


    Evaluations CP/CE1 2018-2019 : mode d'emploi - SNALC06-1er degré

    Contrôle  (TD+TP)  50%  +  Examen  final  50%


    Auteur :

    Le métier d'auteur-écrivain, quelles études et compétences ?

    Dr. Benaboud Rohallah
    E-mail: r_benaboud@yahoo.fr

    Maitre  de conférence classe  A,  Faculté  des  sciences  exactes  et  des  sciences  de  la  nature  et  de  la  vie, Département  Informatique, Université  d'Oum  El  Bouaghi.

    Références :

    RéfBi

    • Modéles - Vérification
      • Robin Milner, Communication and Concurrency, Prentice Hall, 1989 (ISBN 0-131-15007-3)
      • Robin Milner, Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, 1999 (ISBN 0-521-65869-1)
      • Edmund M. Clarke, Orna Grumberg, Doron A. Peled, Model Checking, MIT Press, 2000 (ISBN-10: 0-262-03270-8 - ISBN-13: 978-0-262-03270-4)
      • Philippe Schnoebelen et al., Vérification de logiciels : techniques et outils du model-checking, Vuibert, 1999 (ISBN : 2-7117-8646-3)
      • André Arnold, Systèmes de transition et sémantique des processus communicants, Masson, 1992 (ISBN : 2-225-82746-X)
      • André Arnold, Joffroy Beauquier, Béatrice Bérard, Brigitte Rozoy, Programmes parallèles : modèles et validation, Armand Colin, 1992 (ISBN : 2-200-21080-9)

  • Cette section

    Chapitre 01: Introduction aux systèmes répartis

    Systèmes distribués : quels avantages pour votre SI ?


  • Chapitre 02: Ordre et temps logique

    Systèmes distribués : Rappel sur ordre et temps logique

    Chapitre 02: Ordre et temps logique (pdf)

  • Chapitre 03 : L’exclusion mutuelle en réparti

    Algorithmes (1) - Claire Mathieu (2017-2018) - YouTube

                                                                                     Introduction

                                                                                     1. Algorithmes fondés sur les permissions:

                                                                                        1.1 Algorithme de Riacart et Agrawala (ici)

                                                                                        1.2 Algorithme de Carvalho et Roucairol:

                                                                                            a) Principe et algorithme (ici)

                                                                                           b) Exemple (ici)

                                                                                     2. Algorithmes fondés sur l’unicité d’un jeton

                                                                                        2.1 Algorithme de Le Lann (mouvement perpétuel)

                                                                                        a) Principe et algorithme (ici)
                                                                                        b) Exemple (ici)


                                                                                         2.2 Algorithme à diffusion

                                                                                         a) Principe et algorithme (ici)
                                                                                         b) Exemple (ici)

                                                                                         

  • Chapitre 04. Allocation répartie de ressources

    Technologie, Internet, Commerce Et Marketing. Jeune Femme D'affaires écrit Un Mot: Allocation De Ressources Banque D'Images Et Photos Libres De Droits. Image 72527786.

    On distingue différents cas d’allocation de ressources selon le nombre de types de ressources, le nombre d’exemplaires (ou instances) pour chaque type et les demandes des sites.

    Si dans un système, il existe 2 imprimantes de même type (mêmes caractéristiques) tel que le site ne fait pas la distinction entre les 2 imprimantes, on dit, alors, qu’on a 1 seul type de ressource avec 2 exemplaires.

    Cas 01. Section critique

    Le système contient 1 seul type de ressource avec 1 seul exemplaire. On parle alors du problème d’exclusion mutuelle simple, vu dans le chapitre précédent, qu’on peut le résoudre par l’un des algorithmes d’exclusion mutuelle.

    Cas 02. Section critique à entrées multiples

    Le système contient 1 seul type de ressource avec plusieurs exemplaires, mais chaque site ne peut demander qu’un seul exemplaire.

    Cas 03. Problème K parmi M

    Le système contient 1 seul type de ressource avec plusieurs exemplaires, et chaque site peut demander plusieurs exemplaires.

    Cas 04. Plusieurs types de ressources en exemplaire unique

    Le système contient plusieurs types de ressource et pour chaque type, on a un seul exemplaire, et chaque site peut demander plusieurs types.

    Cas 05. Plusieurs types de ressources en plusieurs exemplaires

    Le système contient plusieurs types de ressource et que chaque type peut contenir plusieurs exemplaires, et chaque site peut demander plusieurs exemplaires pour plusieurs types.

    -----------------------------------------------------------------------------------------------------------------------------------------------------------

    1. Section critique à entrées multiples

       1.1 Algorithme de Raymond

       1.2 Exemple

    2. Problème K parmi M

       2.1 Algorithme de Raynal

       2.2 Exemple

    3. Plusieurs types de ressources en exemplaire unique

    4. Plusieurs types de ressources en plusieurs exemplaires

    5. TP 02

  • Chapitre 05 : Coordination par rendez-vous

    La gestion du temps et le multitâche ou consolider combiner plusieurs rendez -vous d'un calendrier et la date de la coordination comme un groupe de montres réunies pour former un seul garde-temps comme

    Coordination par rendez-vous

    Concept de rendez-vous et solution distribuée





  • Chapitre 06: L’observation répartie

    Tout système joue deux rôles :

    Interpréteur : Offrir un certains nombres d’opérations que peuvent utiliser les programmes (appels système)

    Observateur : Observer les programmes qu’il exécute

    Ces observations ont diverses motivations :

    - Extraction de mesures destinées à la comptabilité du programme ou à l’analyse de ses performances

    -  Détection des propriétés qui en caractérisent les exécutions ;                                                                                                                        

    La difficulté pour réaliser une observation réside dans le fait qu’il ne faut pas perturber le comportement du programme observé (celui-ci est appelé calcul sous-jacent).

    Les propriétés qui caractérisent  les exécutions :

    -  Les propriétés non-stables :

    -  Les propriétés stables : Une propriété stable est définie sur l’état du calcul sous-jacent et est caractérisée par le fait, qu’une fois vérifiée, elle le reste quelle que soit l’évolution ultérieure du calcul sous-jacent. Exemples : l’application est terminée, le nombre de message a dépassé 100 msg .

    Parmi les propriétés stables, on trouve les propriétés de repos : La terminaison et l’interblocage.

    -----------------------------------------------------------------------------------------------------------------------------------------------------------------
    1. Détection répartie de la terminaison


    2. Détection répartie de l’interblocage

  • TPs

    TP02