Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Szymański's algorithm
Résumé
Szymański's Mutual Exclusion Algorithm is a mutual exclusion algorithm devised by computer scientist Dr. Bolesław Szymański, which has many favorable properties including linear wait, and which extension solved the open problem posted by Leslie Lamport whether there is an algorithm with a constant number of communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that Lamport conceived of (Lamport's solution used n factorial communication variables vs. Szymański's 5).
The algorithm is modeled on a waiting room with an entry and exit doorway. Initially the entry door is open and the exit door is closed. All processes which request entry into the critical section at roughly the same time enter the waiting room; the last of them closes the entry door and opens the exit door. The processes then enter the critical section one by one (or in larger groups if the critical section permits this). The last process to leave the critical section closes the exit door and reopens the entry door, so the next batch of processes may enter.
The implementation consists of each process having a flag variable which is written by that process and read by all others (this single-writer property is desirable for efficient cache usage).
The flag variable assumes one of the following five values/states:
0 denoting that the process is in the noncritical section.
1 indicating that the process wants to enter its critical section (declaration of intention).
2 showing that the process waits for other processes to get through the door_in.
3 denoting that the process has just entered the waiting room.
4 indicating that the process has crossed the door_out and entered the critical section.
The status of the entry door is computed by reading the flags of all processes. Pseudo-code is given below:
Entry protocol
flag[self] ← 1 # Standing outside waiting room await(all flag[1..N] ∈ {0, 1, 2}) # Wait for open door flag[self] ← 3 # Standing in doorway if any flag[1..Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.