#define _POSIX_C_SOURCE 200112L #include #include #include #include #include #include #include /*------------------------------------------------------------------------------. | Algorithme Dolev-Klawe-Rodeh d'élection de leader. | | | | Chaque processus a initialement une identité, un entier qui l'identifie sur | | l'anneau. L'objectif est qu'un et un seul processus se déclare leader. | | | | On demande aussi que chaque processus exécute le même algorithme. | | | | L'algorithme DKR permet de n'échanger que O(nlog(n)) messages au pire: | | | | - Chaque processus peut fonctionner suivant deux modes : tant qu'il pense | | pouvoir être élu leader, un processus est en mode actif. Dès qu'il | | détecte qu'il ne sera pas leader, il passe en mode passif, dans lequel il | | se contente de relayer les messages qu'il reçoit. | | | | - Tous les processus sont initialement actifs. | | | | - Chaque processus maintient une variable moi valant initialement son | | identité. | | | | (a) Un processus commence par transmettre la valeur moi à son voisin | | suivant dans l'anneau, et reçoit celle de son prédécesseur, voisin1. Si | | ces valeurs sont égales, il se déclare leader. | | | | (b) Sinon, il transmet la valeur voinsin1, et reçoit la valeur voisin2 | | reçue par son prédécesseur. Si voisin1 n'est pas maximale parmi moi, | | voisin1, voisin2, il passe en mode passif. Sinon, il affecte la valeur | | voisin1 à la variable moi et reprend en (a). | `------------------------------------------------------------------------------*/ int main(int argc, char **argv) { pid_t moi, voisin1, voisin2, x; moi = getpid(); while(true) { write (STDOUT_FILENO, &moi, sizeof(pid_t)); read(STDIN_FILENO, &voisin1, sizeof(pid_t)); if (moi == voisin1) { fprintf(stderr, "Je suis leader... %d\n", moi); break; } else { write (STDOUT_FILENO, &voisin1, sizeof(pid_t)); read(STDIN_FILENO, &voisin2, sizeof(pid_t)); if ((voisin1 >= voisin2) && (voisin1 >= moi)) moi = voisin1; else break; } } // phase passive while (true) { read(STDIN_FILENO, &x, sizeof(pid_t)); write (STDOUT_FILENO, &x, sizeof(pid_t)); } }