---

• Mémoire partagée : shmget(), shmat(), shmdt(), shmctl() (rappel du cours)
  
• Accès concurrent à la mémoire, synchronisation
  

Exercice 1.

Ecrire un programme qui crée une mémoire partagée (un int) et qui crée un fils. Le père écrit la valeur 0 dans cette zone de mémoire partagée et attend que la valeur soit égale à 1. Quand c’est le cas, il affiche "Ok, je termine !" et il termine. Le fils attend une seconde, écrit la valeur 1 dans cette cette zone de mémoire partagée et termine. Faire attention à ce que la mémoire partagée soit bien libérée à la fin de l'exécution du programme. NB: On prendra pour clé la valeur IPC_PRIVATE puisque la mémoire partagée n'est utilisée que par le processus courant et sa descendance.

Même chose que l'exercice 1 mais avec deux programmes indépendants : Le premier programme crée une mémoire partagée (un int), écrit la valeur 0 et attend que la valeur soit égale à 1. Quand c’est le cas, il affiche "Ok, je termine !" et il termine. Le deuxième programme attend une seconde, écrit la valeur 1 et termine. Faire attention à ce que la mémoire partagée soit bien libérée à la fin de l'exécution du premier programme. NB: On utilisera la fonction ftok pour générer une clé qui identifie de manière unique la mémoire partagée.

Exercice 3.

Ecrire un programme où deux processus effectuent concurremment la somme C de deux matrices carrées A et B : Les 3 matrices seront stockés dans une zone de mémoire partagée. Si je suis le père, je remplis la matrice A, j'attends que le fils ait remplit la matrice B (important !) et je calcule la somme C[i,j] = A[i,j]+B[i,j]  pour tous les indices i pairs; si je suis le fils, je remplis la matrice B, j'attends que le père ait remplit la matrice A et je calcule la somme C[i,j] = A[i,j]+B[i,j] pour tous les indices i impairs. On fera également l’affichage de la matrice résultat C (à votre avis, dans le père ou dans le fils ?). NB: Il faut donc trouver un moyen pour que les processus s'attendent (on dit aussi "se synchronisent") : On pourra utiliser les signaux ou bien la mémoire partagée comme dans l'exercice 1.  

Même question que dans l'exercice 3 pour le produit de matrices carrées (on rappelle que C[i,j] = ∑_k A[i,k]*B[k,j]) : les processus père et fils calculent alternativement une ligne du résultat selon que l’indice des lignes dans la matrice résultat est pair ou impair. A votre avis, est-ce que votre code fait des accès concurrents en lecture à la mémoire ? Est-ce gênant ?

Soient les deux processus P1 et P2 suivants qui s'exécutent concurremment et qui accèdent à la variable commune (partagée) N :

processus P1:       processus P2: 
.....               .....  
load r1, N          load r2,N 
add r1,r1, 1        add r2,r2,1 
store r1,N          store r2, N 
exit                exit 

Vous savez qu'une instruction de type N = N+1 n'est pas atomique (l'ordonnanceur peut passer la main à un autre processus avant qu'elle se termine). Donnez deux scénarios d'exécution de P1 et P2 qui conduisent à deux valeurs distinctes pour N lorsque P1 et P2 sont terminés.

Vous pouvez construire vos scénarios en composant un programme avec les instructions de P1 et les instructions de P2; mais en préservant l'ordre interne des opérations (vous ne pouvez pas faire dans cet ordre un store r1,N puis load r1, N). En mélangeant les instructions de la sorte, combien de programmes pouvez-vous construire ?

On rappelle que la fonction log(x+1) peut être approchée par le développement suivant à l’ordre 12 :

Ecrire un programme à deux processus qui lit une valeur pour x et un ordre de grandeur k et qui calcule log(x+1) à l’ordre k avec la formule précédente : le père calcule les puissances paires et le fils les puissances impaires. Vous pouvez appliquer l’algorithme suivant :

Un autre algorithme est possible. Contrairement au précédent, la première phase (calcul des T[i]) peut être réalisée par le père et le fils sous les contraintes suivantes : le père calcule les T[i] pour i pairs, le fils les T[i] pour les i impairs. Cependant on ne peut produire T[i] que si T[i-1] a été produit en faisant T[i]=T[i-1]*x. Cela séquentialise le code et fait intervenir des synchronisations entre le père et le fils. La synchronisation entre le père et le fils peut s'implémenter par le pseudo code suivant (on initialise une variable semaphore à 1 juste avant le fork – semaphore est une variable en mémoire partagée):

Processus exécuté par le père : 
Etiq1:
  while(est_impair(semaphore)) attendre;
  T[semaphore] = T[semaphore-1]*x;
  semaphore++;
  goto Etiq1;

Processus exécuté par le fils : 
Etiq2:
  while(est_pair(semaphore)) attendre;
  T[semaphore] = T[semaphore-1]*x;
  semaphore++;
  goto Etiq2;

Note : ci-dessus les processus sont dans une boucle infinie : le contrôle sur le nombre d'itérations à effectuer n'est pas fait !

Dans l'exercice précédent, l'instruction T[semaphore] = T[semaphore-1]*x; constitue la section critique c'est-à-dire le code qui ne peut être accédé que par au plus un processus. Recoder l'exercice précédent au moyen de l'algorithme de Peterson suivant qui assure l'exclusion mutuelle :

shared boolean wantIn[2]=false,false;
shared int turn;

int myPid = 0; //pour le processus pere et init à 1 pour le fils
int otherPid = 1 – myPid;
while(true){
   wantIn[myPid] = true;
   turn = otherPid;
   while !((wantIn[otherPid] == false) || (turn == myPid)) DoNothing();
   // section critique
   wantIn[myPid] = false
}

Expliquer ensuite de manière intuitive pourquoi ce code garantit un accès exclusif à la portion de code dite « section critique ».