Résoudre l'exclusion mutuelle

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).

Contents Haut

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.

// process one
while(true){
	while(process_number!=1){
		// wait
	}
	critical_section();
	process_number=2;
	non_critical_section();
}
// process two
while(true){
	while(process_number!=2){
		// wait
	}
	critical_section();
	process_number=1;
	non_critical_section();
}

Contents Haut

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.

PROCEDURE dekker_s_algorithm IS
	TYPE process_enumeration IS(first,second);
	favored_process : process_enumeration;
	p1_wants_to_enter,
	p2_wants_to_enter : boolean;
 
	PROCEDURE process_one IS
	BEGIN
		LOOP
			p1_wants_to_enter := true;
			WHILE p2_wants_to_enter LOOP
				IF favored_process = second THEN
					p1_wants_to_enter := false;
					WHILE favored_process = second LOOP
						NULL;
					END LOOP;
					p1_wants_to_enter := true;
				END IF;
			END LOOP;
			critical_section_one;
			favored_process := second;
			p1_wants_to_enter := false;
			other_stuff_one;
		END LOOP;
	END process_one;
	PROCEDURE process_two IS
	BEGIN
		LOOP
			p2_wants_to_enter := true;
			WHILE p1_wants_to_enter LOOP
				IF favored_process = first THEN
					p2_wants_to_enter := false;
					WHILE favored_process = first LOOP
						NULL;
					END LOOP;
					p2_wants_to_enter := true;
				END IF;
			END LOOP;
			critical_section_two;
			favored_process := first;
			p2_wants_to_enter := false;
			other_stuff_two;
		END LOOP;
	END process_two;
 
	BEGIN
		p1_wants_to_enter := false;
		p2_wants_to_enter := false;
		favored_process := first;
		PARBEGIN
			process_one;
			process_two;
		PAREND;
	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.

Contents Haut

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.

Contents Haut

Algorithme de Lamport

U bevindt zich op de Engels versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der Englisch Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite

Vous vous trouvez sur la version anglaise du site, mais votre système indique que vous préférez utiliser la langue française.

Souhaitez-vous atteindre la page en français?
Cliquez ici pour continuer en français: Consulter la page en français