#define _POSIX_C_SOURCE 200112L #include #include #include #include #include #include #include /*------------------------------------------------------------------. | Diffère de anneau_proc.c/DKR.c par l'attribution des identités: | | dans cette version, elles sont générées aléatoirement pour ne pas | | avoir des pid consécutifs. | `------------------------------------------------------------------*/ /*-------------------------------------------------------------------. | 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) { int moi, voisin1, voisin2, x; moi = atoi (argv[1]); while(true) { write (STDOUT_FILENO, &moi, sizeof(int)); read(STDIN_FILENO, &voisin1, sizeof(int)); if (moi == voisin1) { fprintf(stderr, "Je suis leader: %d\n", getpid()); break; } else { write (STDOUT_FILENO, &voisin1, sizeof(int)); read(STDIN_FILENO, &voisin2, sizeof(int)); if ((voisin1 >= voisin2) && (voisin1 >= moi)) { fprintf(stderr, "Proc %d continue phase active\n", getpid()); moi = voisin1; } else { fprintf(stderr, "Proc %d devient passif\n", getpid()); break; } } } // phase passive while (true) { read(STDIN_FILENO, &x, sizeof(int)); write (STDOUT_FILENO, &x, sizeof(int)); } }