Gestion des Processus.

Un processus.

Définition.

Processus = programme + contexte.

Modèle d'un processus.

 

L'ordonnancement de processus.

Les types d'ordonnancements.

Ils sont distingués suivant les transitions permises dans le graphe d'état d'un processus.

transition "interrompu" interdite

sans réquisition (multiprogrammation).

transition "interrompu" autorisée

avec réquisition (temps partagé).

Les différentes phases de l'ordonnancement.

• le changement de contexte.
• la table des processus.
• le bloc de contrôle d'un processus.

Les critères d'ordonnancement.

• l'utilisation maximale de l'UC.
• la capacité de traitement maximale.
• l'utilisation maximale des périphériques.
• la diminution du temps moyen de restitution.
• la diminution du temps moyen d'attente.
• la diminution du temps moyen de réponse.
• l'équité.

Les objectifs sont contradictoires, il faut des compromis.

Les algorithmes d'ordonnancement.

FIFO.

Utilisation maximale de l'UC. Equitable.

Tourniquet (Round Robin).

Equitable. Utilisation de l'UC et temps moyen de réponse dépendent du quantum, ce choix favorise soit les calculs, soit les E/S.

Tourniquet avec priorités statiques.

Non équitable. Utilisation de l'UC et temps moyen de réponse peuvent être bons.

Tourniquet avec priorités dynamiques.

Equitable. Utilisation de l'UC et temps moyen de réponse sont bons. Diverses stratégies pour la gestion des priorités.

PCTE (Plus Court Temps d'Exécution).

Non équitable. Temps moyen de restitution optimal. (analogie avec la file d'attente à une caisse de grande surface, où une règle de politesse est de laisser passer quelqu'un qui a peu d'objets si l'on a un plein caddie).

Implémentable dans les SGBD, mais pas dans un SE généraliste, car le temps du prochain cycle d'exécution n'est pas connu.

Une implémentation est possible en utilisant une fonction d'estimation du temps du prochain cycle. Par exemple t= a * t + b * te.

PCTER (Plus Court Temps d'Exécution Restant).

Une variante du précédent.

L'ordonnancement à plusieurs niveaux.

L'ensemble des processus prêts est souvent trop important pour tenir en RAM. Certains sont donc sur disque. Un processus élu qui est sur disque prend beaucoup plus de temps qu'un processus en RAM pour être chargé dans l'UC.

Le processus élu est donc toujours pris parmi ceux en RAM. L'algorithme est alors non équitable.

La solution consiste à utiliser un deuxième algorithme d'ordonnancement pour gérer les déplacements des processus prêts entre le disque et la RAM.

La synchronisation (communication) de processus.

La mémoire est partagée entre plusieurs processus (exemple BD), il y a donc des risques de comportements bizarres.

Exemple d'une variable compte modifiée par deux processus, le résultat dépend de l'entrelacement des actions, donc de l'ordonnancement des processus.

Il y a donc un besoin de contrôler le déroulement d'un processus.

 

Le problème de la section critique.

N processus exécutent le programme suivant :

debut
tant que vrai faire debut
        "entrer en section critique"
        Section Critique
        "sortir de section critique"
        Section Non Critique
        fin
fin

Les objectifs :

• pas 2 processus en S.C en même temps.
• pas d'attente infinie.
• pas d'attente s'il n'y a pas de compétition.
• équitable si possible.

Les solutions logicielles.

Première idée pour 2 processus: un feu vert/rouge.

le feu est initialisé à vert.

debut
tant que vrai faire debut
        tant que feu = rouge faire rien;
        feu := rouge;
        Section Critique;
        feu := vert;
        Section Non Critique
        fin
fin

Les 2 processus peuvent être ensemble en S.C

Deuxième idée : Deux drapeaux

Flag[i] signifie que Pi veut entrer et les drapeaux sont initialisés à faux.

debut
tant que vrai faire debut
        Flag[i] := true;
        tant que Flag[j] faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin

Les 2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente s'il n'y a pas de compétition.

Il y a possibilité d'attente infinie (famine).

la preuve est faite par la construction du graphe du comportement des deux processus.

Troisième idée : une variable qui indique "A qui le tour".

debut
tant que vrai faire debut
        tant que tour = j faire rien;
        Section Critique;
        tour := j ;
        Section Non Critique
        fin
fin

2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente infinie.

Il peut y avoir attente s'il n'y a pas de compétition. C'est un algorithme d'alternance (jeton).

Algorithme de Peterson pour 2 processus.

Combiner les deuxième et troisième idées.

debut
tant que vrai faire debut
        Flag[i] := true;
        tour := i ;
        tant que (Flag[j] et tour = i) faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin

La preuve sera faite en TD

Section critique pour N processus.

Solutions complexes et difficiles à prouver.

Le SE doit fournir des primitives pour synchroniser des processus.

Les primitives matérielles de synchronisation.

Les solutions logicielles font les hypothèses suivantes :

• Interruption toujours possibles.
• Actions atomiques = Lecture, Ecriture.

Le problème devient plus simple si on les change.

• Permettre à l'utilisateur d'interdire momentanement les interruptions (difficile et dangereux).
• Augmenter l'ensemble des actions atomiques (le jeu d'instructions).

  fonction TestAndSet

  permet de modifier un booléen s'il vaut false.

  fonction TestAndSet(var but : booleen) : booleen
  debut TestAndSet := but; but := true; fin

  Une solution non équitable pour N processus au problème de la section critique avec un booléen lock initialise à false.

  debut
  tant que vrai faire debut
          tant que TestAndSet(lock) faire rien
          Section Critique
          lock := false
          Section Non Critique
          fin
  fin

  Certains processeurs possèdent une instruction TestAndSet.

  procedure swap

  permet l'échange de deux booléens.

  procedure swap(var a, b : booleen)
  debut aux := a; a := b; b := aux fin

  Une solution non équitable pour N processus au problème de la section critique avec un booléen lock et N booléens key[i] initialises à false.

  debut
  tant que vrai faire debut
          key[i] := true;
          tant que key[i] faire
          swap(lock,key[i]);
          Section Critique;
          lock := false
          Section Non Critique
          fin
  fin

  Certains processeurs possèdent une instruction swap.

  les procedures wait et signal

  manipulent des entiers.

  procedure wait(var S : entier)         procedure signal(var S : entier)
  debut                                  debut
  tant que (S <= 0) faire rien;          S := S + 1
  S := S - 1; f                          fin
  fin

  Une solution non équitable pour N processus au problème de la section critique avec un entier mutex initialisé à 1.

  debut
  tant que vrai faire debut
          wait(mutex);
          Section Critique;
          signal(mutex);
          Section Non Critique
          fin
  fin

  Aucun processeur ne possède ces instructions.

  Il existe des solutions équitables.

Le défaut commun à ces solutions est l'attente active (gaspillage de l'UC).

Le SE doit fournir des appels systèmes pour endormir et réveiller des processus.

Les appels systèmes de synchronisation.

On suppose l'existance de deux appels systèmes: d'une part block qui permet à un processus de se mettre en état d'attente; d'autre part wakeup(P) qui permet de mettre l'état du processus P à prêt.

Avec ces hypothèses, il est assez facile d'éliminer l'attente active. Il suffit de remplacer faire rien par block, puis ajouter en fin de la phase de sortie une boucle pour reveiller tous les processus "en attente" grâce à un wakeup(P)

Cette solution est moyennement satisfaisante, car en fait un seul proceesus doit être reveillé, les autres feront en effet un nouveau block.

Les sémaphores : Dijkstra - 1965

L'idée est de combiner les appels block et wakeup avec les procédures wait et signal.

Définition

Une structure de données

type semaphore = (n : entier; l : liste de processus);

manipulée uniquement par les actions atomiques wait et signal.

procedure wait(var S : semaphore)         procedure signal(var S : semaphore)
debut                                     debut
S.n := S.n - 1;                           S.n := S.n + 1;
si (S.n < 0) alors debut                  si (S.n <= 0) alors debut
        ajouter(moi,S.l);                         enlever(P,S.l);
        block;                                    wakeup(P);
        fin                                       fin
fin                                       fin

Une solution au problème de la section critique

Une solution équitable pour N processus au problème de la section critique avec un sémaphore mutex initialisé à (1,vide).

debut
tant que vrai faire debut
        wait(mutex);
        Section Critique;
        signal(mutex);
        Section Non Critique
        fin
fin

La solution est équitable si la liste de processus est une FIFO.

Implémentation

Les sémaphores peuvent être implémentés de deux façons :

• Un sémaphore de taille m est implémenté à l'aide de 3 sémaphores binaires et d'un entier.

  Les opérations wait et signal des sémaphores binaires sont implémentés avec les instructions TestAndSet et/ou Swap

• Les interruptions sont interdites pendant l'exécution des wait et signal.

Utilisation

• Attention, les sémaphores permettent de synchroniser des processus, mais en aucun cas ne garantissent que cette synchronisation soit exempte de problème.

  Soient les deux sémaphores S1(1,vide) et S2(1,vide). les processus P1 et P2 suivant peuvent se bloquer mutuellement.

  processus P1                  processus P2
  debut                         debut
  wait(S1);                     wait(S2);
  wait(S2);                     wait(S1);
  ...                           ...
  fin                           fin

• Les sémpahores permettent l'ordonnancement de tâches.
• Un sémaphore S(p,vide) permet le partage de p ressources indistinguables, en utilisant l'algorithme pour l'exclusion mutuelle.

 

Autres solutions

Il existe des solutions équivalentes (en terme de puissance de synchronisation) pour la synchronisation de processus.

Les messages

Le SE propose les primitives

• emettre(message, destinataire)
• recevoir(message, source).

Les S.E. conçus autour d'un micro-noyau utilise principalement cette technique.

Les messages permettent de synchroniser des processus distants.

Il existe des variantes en fonction des sémantiques :

• emettre(message, destinataire) bloquant ou non.
• recevoir(message, source) synchrone ou non.

Une solution au problème de la section critique.

utilse un processus controleur qui délivre les autorisations d'entrée en SC.

processus Pi
debut
tant que vrai faire debut
        emettre(demande,controleur);
        recevoir(aquittement,controleur);
        Section Critique;
        emettre(fin,controleur);
        Section Non Critique
        fin
fin

processus Controleur
debut
tant que vrai faire
        cas de 
        recevoir(demande,P1); emettre(aquittement,P1); recevoir(fin,P1);
        ou 
        recevoir(demande,P2); emettre(aquittement,P2); recevoir(fin,P2);
        ou 
        ...
        ou 
        recevoir(demande,Pn); emettre(aquittement,Pn); recevoir(fin,Pn);
        sac
fin

Equivalence de modèles

Il est possible d'implémenter les messages à l'aide des sémaphores et réciproquement.

Les structures précédentes (sémaphores et messages) sont puissantes, mais encore difficiles d'utilisation. Les suivantes sont plus simples d'emploi.

Les régions critiques conditionnelles

Une variable partagée est déclarée par :

var v : shared T;

et ne peut être utilisée que de la façon suivante :

region v when B do S;

Une solution au problème de la section critique

Les variables manipulées dans la section critique sont rassemblées dans une structure v déclarée partagée.

debut
tant que vrai faire debut
        region v when true do
        Section Critique;
        Section Non Critique
        fin
fin

Le risque, pour l'utilisateur, d'erreur d'entrelacement est nettement diminué.

Equivalence

Il est possible d'implémenter une région critique conditionnelle à l'aide des sémaphores mutex(1,vide), delai1(0,vide) et delai2(0,vide), et des entiers compteur1 et compteur2 initialisés à 0.

debut
wait(mutex);
tant que non B faire debut
        compteur1 := compteur1 + 1;
        si compteur2 > 0 alors
                signal(delai2);
        sinon
                signal(mutex);
        wait(delai1);
        compteur1 := compteur1 - 1;
        compteur2 := compteur2 + 1;
        si compteur1 > 0 alors
                signal(delai1);
        sinon
                signal(delai2);
        wait(delai2);
        compteur2 := compteur2 - 1;
        fin;
S;
si compteur1 > 0 alors
        signal(delai1);
sinon
        si compteur2 > 0 alors
                signal(delai2);
        sinon
                signal(mutex);
fin

Les moniteurs

Un moniteur est déclaré ainsi :

Problèmes classiques de synchronisation

Il existe plusieurs problèmes de synchronisation de processus qui permettent de valider, et de comparer les facilités d'utilisation des différents mécanismes.

Le Producteur/Consommateur avec buffer limité

Un producteur dépose des messages dans un buffer, duquel un comsommateur les retire. La synchronisation doit satisfaire les points suivants :

• Le producteur ne peut pas déposer un message lorsque le buffer est plein.
• Le consommateur ne peut pas retirer un message lorsque le buffer est vide.

Les lecteurs/rédacteurs

Un objet est partagé par des lecteurs qui veulent connaıtre sa valeur, et des rédacteurs qui peuvent modifier sa valeur.

• Plusieurs lectures sont possibles simultanément.
• Une seule modification est permise à la fois, et seulement si aucune lecture n'est en cours.
• Une priorité soit aux lecteurs, soit aux rédacteurs.

Les philosophes mangeurs de spaghettis

N philosophes alternativement pensent et mangent. Pour manger, ils disposent d'une table circulaire ayant N assiettes et N fourchettes.

• Un philosophe ne mange que lorsqu'il a deux fourchettes.