Résoudre l'exclusion mutuelle

Masquage des interruptions

Ce type de solution est inefficace dans le cas où plusieurs processus sont en exécution sur plusieurs processeurs en parallèle. De plus, même si le noyaux utilise le masquage des interruptions pour effectuer des tâches critiques, il serait sucidaire pour un système d'exploitation de laisser la possibilité de masquer des interruptions en mode utilisateur. Le processus ne risquerait plus d'être interrompu dans sa section critique, mais il serait par contre impossible de reprendre la main sur ce processus en cas de problème.

 

Exclusion mutuelle par attente active

L'attente active devrait nous permettre de gérer les accès concurrents sans solliciter le système d'exploitation.

Reprenons notre exemple du chargeur et du chauffeur de brouettes.

Occupé

Si nous tentons d'expliquer le problème, nous pouvons penser que nous ne pouvons utiliser le chargeur de brouette que si ce dernier est disponible (s'il n'est pas occupé à charger une autre brouette). La section critique est donc le chargement.

Nous pouvons donc utiliser un booléen "occupé" qui sera initialisé à false.

Si le chauffeur1 tente d'entrer en section critique (chargement de sa brouette) alors que le chauffeur2 ne l'utilise pas, occupé possède la valeur false, il peut donc y entrer.
Il modifie ensuite la valeur occupé à true, et peut alors utiliser la section critique tant qu'il le désire.
A sa sortie de la section critique, il affecte la valeur false au booléen occupé, signalant que la ressource critique est libre.

Une seule variable contrôle donc l'accès à la section critique.

L'état de cette variable doit être le même à la sortie de la section critique qu'à son entrée.

Attention : dans le cas où les deux chauffeurs demandent simultanément l'accès à la section critique, il existe un cas exceptionnel qui met en défaut ce genre d'analyse (interruption d'un des 2 processus en un point bien précis).

 

Autorisé

Nous pouvons utiliser un booléen "autorisé", initialisé à true, au lieu de "occupé".

Ce type de raisonnement permet d'éviter le cas qui met en défaut l'analyse, et de diminuer le nombre d'instructions nécessaires pour entrer en section critique.

Alternance

Ce type de solution simpliste repose sur un cas de figure théorique pour lequel les processus désirant accéder aux sections critiques possèdent tous une vitesse d'exécution identique.

Au lieu d'utiliser un booléen pour autoriser l'accès, nous allons utiliser une variable numérique "process_number" pour indiquer quel est le processus qui peut accéder à la section critique.

Lorsqu'un processus quitte la section critique, il affecte à process_number la valeur du processus suivant, qui pourra donc accéder à son tour au code de la section critique.

Lorsqu'un processus est en attente d'accès à la section critique (il attend l'allocation de la ressource partagée) il effectue une boucle infinie (infini = dont le nombre d'exécution ne peut être déterminé à l'avance) jusqu'au moment de la libération de la ressource.


Code Java (Process) (18 lignes) :
  1. // process one
  2. while(true){
  3.   while(process_number!=1){
  4.     // wait
  5.   }
  6.   critical_section();
  7.   process_number=2;
  8.   non_critical_section();
  9. }
  10. // process two
  11. while(true){
  12.   while(process_number!=2){
  13.     // wait
  14.   }
  15.   critical_section();
  16.   process_number=1;
  17.   non_critical_section();
  18. }

 

Algorithme de Dekker

En 1965, T. Dekker présente une solution formelle au problème des exclusions mutuelles.

L'idée est d'utiliser notre booléen "occupé", mais comme cette méthode présente des failles lorsque plusieurs processus tentent simultanément d'accéder à la section critique, nous devons utiliser une variable numérique "tour", qui nous permettra de déterminer quel processus accèdera à la section critique en premier.

  1. PROCEDURE dekker_s_algorithm IS
  2. TYPE process_enumeration IS(first,second);
  3. favored_process : process_enumeration;
  4. p1_wants_to_enter,
  5. p2_wants_to_enter : boolean;
  6.  
  7. PROCEDURE process_one IS
  8. BEGIN
  9. LOOP
  10. p1_wants_to_enter := true;
  11. WHILE p2_wants_to_enter LOOP
  12. IF favored_process = second THEN
  13. p1_wants_to_enter := false;
  14. WHILE favored_process = second LOOP
  15. NULL;
  16. END LOOP;
  17. p1_wants_to_enter := true;
  18. END IF;
  19. END LOOP;
  20. critical_section_one;
  21. favored_process := second;
  22. p1_wants_to_enter := false;
  23. other_stuff_one;
  24. END LOOP;
  25. END process_one;
  26. PROCEDURE process_two IS
  27. BEGIN
  28. LOOP
  29. p2_wants_to_enter := true;
  30. WHILE p1_wants_to_enter LOOP
  31. IF favored_process = first THEN
  32. p2_wants_to_enter := false;
  33. WHILE favored_process = first LOOP
  34. NULL;
  35. END LOOP;
  36. p2_wants_to_enter := true;
  37. END IF;
  38. END LOOP;
  39. critical_section_two;
  40. favored_process := first;
  41. p2_wants_to_enter := false;
  42. other_stuff_two;
  43. END LOOP;
  44. END process_two;
  45.  
  46. BEGIN
  47. p1_wants_to_enter := false;
  48. p2_wants_to_enter := false;
  49. favored_process := first;
  50. PARBEGIN
  51. process_one;
  52. process_two;
  53. PAREND;
  54. END dekker_s_algorithm;

Nos super chauffeurs de brouettes porteront ici les noms process_one et process_two.

Si le process_two n'est pas présent au moment où le process_one demande à charger sa brouette, il n'y a pas de problème de concurence. Le process_one peut donc accéder à la section critique (chargement).

Dans le cas où les deux chauffeurs de brouettes se présentent en même temps au chargement, les deux processus n'effectuent plus des boucles d'attentes différentes, mais utilisent un ordre de priorité défini par favored_process.

Si process_one désire accèder à la section critique(le chargement), mais que cette dernière est occupée par process_two, deux possibilités s'offrent à lui :

  • soit favored_process est égal à second, et il doit donc attendre son tour avec sa brouette :
    • il passe p1_wants_to_enter à false
    • il boucle tant que process_two occupe la section critique
    • quand process_two libère la section critique, il passe p1_wants_to_enter à true et entre dans la section critique.
  • soit favored_process est égal à first, il ne doit donc pas attendre.

Dans tous les cas, quand process_one a bénéficié de la ressource critique, c'est process_two qui devient prioritaire.

 

Algorithme de Peterson

La mise en œuvre de la solution proposée par T. Dekker était fort complexe.

En 1981, Peterson présente une solution plus simple.

 

Algorithme de Lamport

 

Document créé le 02/06/05 02:12, dernière modification le 28/06/17 14:26
Source du document imprimé : https://www.gaudry.be/systeme-exploitation-exclusion-mutuelle.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.