Plan

Mémoire partagée

Conditions et moniteurs

Sémantique des conditions

Et si on faisait de la recherche?

Problèmes non traités dans le cours

Terminaux, Pseudo ttys, Streams

Communication par mémoire partagée

Protocoles réseaux

Sécurité sur le réseau: capacités, RSA

Remote procedure calls

Multi processeurs

ATM

Multicast

Transactions atomiques

Mémoire partagée distribuée

Micro noyaux

Communication entre processus par mémoire partagée

shmget, shmat opérations Système V.

Une mémoire partagée 2 fois dans un même processus

int shmid;

main()
{
    int i, *pint;
    char *addr1, *addr2;
    extern char *shmat();

    shmid = shmget(75, 128*1024, 0777|IPC_CREAT);
    addr1 = shmat(shmid, 0, 0);
    addr2 = shmat(shmid, 0, 0);
    printf ("addr1 0x%x, addr2 0x%x\n", addr1, addr2);

    pint = (int *) addr1;
    for (i = 0; i < 256; i++)
        *pint++ = i;
    *pint = 256;

    pint = (int *) addr2;
    for (i = 0; i < 256; i++)
        print ("index %d, value %d\n", i, *pint++);

    pause();
}

Communication entre processus par mémoire partagée

shmget, shmat opérations Système V.

Une mémoire partagée 2 fois dans un même processus

int shmid;

main()
{
    int i, *pint;
    char *addr;
    extern char *shmat();

    shmid = shmget(75, 64*1024, 0777);
    addr = shmat(shmid, 0, 0)

    pint= (int *) addr;
    while (*pint == 0)
        ;
    for (i = 0; i < 256; i++)
        printf ("%d\n", *pint++):
}

Communication par mémoire partagée en Modula-3

INTERFACE Thread;

TYPE
  T <: ROOT;          (* A handle on a thread *)
  Mutex = MUTEX;      (* Locked by some thread, or unlocked *)
  Condition <: ROOT;  (* A set of waiting threads *)

(* Initially a Mutex in unlocked and a Condition is empty.
   It is a checked runtime error to pass the NIL Mutex,
   Condition, or T to any procedure in this interface *)

  Closure = OBJECT METHODS apply (): REFANY RAISES {} END;

PROCEDURE NewMutex (): Mutex;
(* A newly-allocated, unlocked mutex. *)

PROCEDURE NewCondition (): Condition;
(* A newly-allocated condition with no threads waiting on it. *)

PROCEDURE Fork (cl: Closure): T;
(* A handle on a newly-created thread that executes cl.apply(). *)

PROCEDURE Join (t: T): REFANY;
(* Wait until t has terminated and return its result. It is a 
   checked runtime error to call this more than once for any t. *)

PROCEDURE Wait (m: Mutex; c: Condition);
(* The calling thread must have m locked. Atomically unlocks 
   m and waits on c. Then relocks m and returns. *)

PROCEDURE Acquire (m: Mutex);
(* Wait until m is unlocked and then lock it. *)

PROCEDURE Release (m: Mutex);
(* The calling thread must have m locked.  Unlocks m. *)

PROCEDURE Broadcast (c: Condition);
(* All threads waiting on c become eligible to run. *)

PROCEDURE Signal (c: Condition);
(* One or more threads waiting on c become eligible to run. *)

PROCEDURE Self (): T;
(* Return the handle of the calling thread. *)

EXCEPTION Alerted; (* Approximate asynchronous interrupts *)

PROCEDURE Alert (t: T);
(* Mark t as an alerted thread. *)

PROCEDURE TestAlert (): BOOLEAN;
(* TRUE if the calling thread has been marked alerted. *)

PROCEDURE AlertWait (m: Mutex; c: Condition) RAISES {Alerted};
(* Like Wait, but if the thread is marked alerted at the time of 
   call or sometime during the wait, lock m and raise Alerted. 
   Implementations may raise additional exceptions. *)

PROCEDURE AlertJoin (t: T): REFANY RAISES {Alerted};
(* Like Join, but if the thread is marked alerted at the time of 
   call or sometime during the wait, raise Alerted. 
   Implementations may raise additional exceptions. *)

END Thread.

TIT     .Systems programmin with MODULA-3
SLA     .ed. Greg Nelson. - Englewood Cliffs, NJ : Prentice Hall,
        .1991. -IX-267 p.; 24 cm. - (Prentice Hall series in 
        . innotative technology).

Pile concurrente

Dépilage

VAR nonEmpty := NEW(Thread.Condition);

LOCK m DO
    WHILE head = NIL DO Thread.Wait(m, nonEmpty) END;
    topElement := head;
    head := head.next;
END;

LOCK m DO
    newElement.next := head;
    head := newElement;
    Thread.Signal (nonEmpty);
END;

Caution: WHILE is safer than IF in Pop.

Table concurrente

VAR table := ARRAY [0..999] of REFANY {NIL, ...};
VAR i:[0..1000] := 0;

PROCEDURE Insert (r: REFANY) =
  BEGIN
    IF r <> NIL THEN

        table[i] := r;
        i := i+1;

  END;
END Insert;

Caution: how not to loose values?

Interblocage (Deadlocks)

Thread A locks mutex m_1
Thread B locks mutex m_2
Thread A trying to lock m_2
Thread B trying to lock m_1

Simple technique

Respect a partial order between semaphores. For example, A and B uses m_1 and m_2 in same order.

Les 5 philosophes

/* nombre de fourchettes disponibles pour chaque philosophe */
int fork[5] = {2, 2, 2, 2, 2};

Conditions c[5] = {True, True, True, True, True};

Mutex s = 1;


philosopher(int i)
{
    for (;;) {
        think();
        Acquire (s);
            while (forks[i] != 2)
                Wait (s, c[i]);
            --forks[(i+1) % 5];
            --forks[(i-1) % 5];
        Release (s);
        eat();
        Acquire (s);
            ++forks[(i+1) % 5];
            ++forks[(i-1) % 5];
        Release (s);
        Signal (c[(i-1) % 5]);
        Signal (c[(i+1) % 5]);
    }
}

Communication en mémoire partagée

Signal() ne garantie pas que le prédicat sur lequel on attend est vrai (c'est différent des conditions de Hoare). Signal() relache la condition, mais un autre processus peut renter en section critique, et invalider le prédicat. Donc quand on revient de Wait(), on reteste le prédicat. (plus facile à implémenter)

Wait() fait atomiquement l'abandon de la section critique et la suspension du processus. Sinon, il peut y avoir une course au réveil: le processus qui fait Wait() abandonne la section critique, un autre processus s'exécute très vite et fait Signal(), le 1er processus se suspend, et ne sera jamais réveillé, car le signal s'est perdu.

TIT     .Synchronization Primitives for a Multiprocessor:
        .A Formal Specification
SLA     .Digital, Systems Research Center, tech. report 20
        .1997.
AUT     .A.D. Birell, J.V. Guttag, J.J Horning, R. Levin

2 exemples de DEA

1. Algorithmique et combinatoire des mots, [J. Berstel]
2. Géométrie computationnelle, [J.-D. Boissonnat]
3. Introduction au calcul parallèle et distribué, [M. Morvan]
4. Algorithmes probabilistes, [J.-M. Steyaert]
*. Pratique du calcul formel.

Filières, responsables et cours

1. Analyse d'algorithmes [J.-M. Steyaert]
2. Automates et mots [J.-E. Pin]
3. Calcul formel [D. Lazard]
4. Combinatoire [R. Cori]
5. Complexité, codage et cryptographie [J. Stern]
6. Géométrie, images et robotique [O. Faugeras]
7. Parallélisme et concurrence [A. Petit]
*. Conception de circuits, [P. Bertin, J. Vuillemin]

2 exemples de DEA --bis--

1. Structures syntaxiques du lambda calcul, [T. Hardin]
2. Preuves constructives, [G. Dowek]
3. Théories équationnelles, [H. Comon]
4. Récursivité et théorie des domaines, [G. Longo]
5. Sémantique dénotationnelle, [R. Dicosmo]
6. Types et programmation, [D. Rémy - M. Mauny]

Filières, responsables et cours

1. Langages, [G. Cousineau]
(Interprétation abstraite, A. Deutsch;
Sous-typage et langages objets, G. Catagna;
Compilation, X. Leroy; Programmation logique, F. Fages;
Contraintes, L. Puel;)

2. Sémantique, [P.-L. Curien]
(Séquentialité, P.-L. Curien;
Logique linéaire, R. Dicosmo;
Synchrone, N. Halbwachs;
Asynchrone et distribution, J.-J. Lévy)

3. Preuves et spécifications, [J.-P. Jouannaud]
(Constructions, G. Huet;
Démonstration automatique, J. Goubault;
La méthode B, J.-R. Abrial;
Spécifications algébriques, M. Bidoit - V. Donzeau-Gouge)

Quelques laboratoires de recherche

laboratoires publics en France:

• CNET Lannion
• CNRS
• INRIA, 5 Unités de recherche

écoles d'ingénieurs:

• ENS
• ENS Fontenay
• ENS Lyon
• ENPC
• ENSMP
• ENST
• LIX

universités:

• Labri Bordeaux
• Imag Grenoble
• Marseille Lumigny
• Paris 6
• Paris 7, Logique
• Marne la Vallée
• ORSAY
• Saint Denis
• Léonard de Vinci
• CNAM

laboratoires privés:

• Thomson LCR
• Alcatel Marcoussis
• GENSET
• ILOG
• O2 Technology
• Chorus Systèmes
• Xerox Grenoble
• AT&T Bell labs
• Bellcore
• Digital SRC, WRL
• IBM Almaden, Yorktown Heights
• Microsoft Research
• Xerox PARC

• HP labs
• Sun microsystems
• Apple
• NeXT
• Silicon Graphics

Une présentation générale des métiers scientifiques est maintenue par l'Association Bernard Grégory.

---

Domaines de recherche (exemple de l'INRIA)

Les activités de recherche

Les activités de l'INRIA comprennent la réalisation de systèmes expérimentaux, la recherche fondamentale et appliquée, le transfert de technologie, l'organisation d'échanges scientifiques internationaux et la diffusion des connaissances et du savoir-faire.

Ces activités associent informaticiens, automaticiens, mathématiciens dans le cadre de projets de recherche regroupés dans quatre thèmes :

• Thème 1 : Réseaux et systèmes
• Thème 2 : Génie logiciel et calcul symbolique
• Thème 3 : Interaction homme-machine, images, données, connaissances
• Thème 4 : Simulation et optimisation de systèmes complexes

Vous pouvez aussi accéder aux annexes scientifiques du rapport d'activité (1995).

Les activités de développement

Parallèlement à ses activités de recherche, l'INRIA a pour mission de réaliser des systèmes expérimentaux et d'assurer le transfert technologique vers l'industrie. Les actions de développement représentent un cadre privilégié pour mener à bien cette mission.

---

---

INRIA Ucis

---