Exercice 0 - Familiarisation avec pthreads

• Problème 0 : Utilisez man pour rechercher des informations sur:
  • pthreads
  • pthread_create()
  • pthread_join()
  • mutex_lock()
  • mutex_unlock()

Que prennent-ils comme entrée ? Que renvoient-ils en sortie ? De quelles bibliothèques C font-elles partie et quels en-têtes faut-il inclure pour les utiliser ?

Exercice 1 - Utilisation de tube pour synchroniser les processus.

• Problème 0 : Compilez le programme incr.c (trouvé dans le repo git du cours) et lancez l'exécutable résultant avec différentes entrées. Qu'observez-vous ? Proposez un moyen de résoudre le(s) problème(s) observé(s).

• Problème 1 : Étudiez le programme linkedLists.c. Que fait-il ? Pouvez-vous deviner les problèmes qu'il pourrait poser avant de le compiler et de le lancer ?

• Problème 2 : Compilez et lancez linkedLists.c. Faites-le plusieurs fois. Qu'observez-vous ? Que proposez-vous pour résoudre les problèmes observés ?

Exercise 2

• Problème 0 : En utilisant linkedLists.c comme base, modifiez la structure de la liste chaînée pour qu'elle puisse contenir une valeur de votre choix (peut-être un caractère ou un entier). Ensuite, écrivez un programme qui crée une liste chaînée composée d'un seul nœud de tête et qui lance ensuite deux threads, chacun d'entre eux effectuant les opérations suivantes :
  1. Un thread lit périodiquement une valeur aléatoire depuis dev/urandom et la convertit en une valeur du type que vous avez choisi. Il étend ensuite la liste chaînée avec un nouveau noeud dont la valeur est celle mentionnée ci-dessus.
  2. L'autre thread vérifie périodiquement la liste pour tout nouvel ajout et imprime les nœuds nouvellement ajoutés.

Devoir - à soumettre avant le 19/02/2024, 23:59 GMT+1

En utilisant l'API pthreads, implémentez une version parallèle de l'algorithme de tri pair-impair :

• Entrées : une liste d'entiers positifs. Supposons qu'elle soit de taille paire.

• Sortie : une liste contenant les mêmes entiers dans l'ordre croissant ainsi que le nombre de swaps effectués.

L'algorithme est basé sur des itérations alternées suivantes :

1. L'itération paire consiste à compare les paires d'éléments adjacents indexés pairs (c'est-à-dire les éléments avec les indices \(i\) et \(i+1\) où \(i\) est pair). Si la paire n'est pas dans le bon ordre (c'est-à-dire \(a[i] < a[i+2]\)), elle les échange.

2. L'itération impaire consiste les à compare paires indexées impaires (\(a[i], a[i+1]\)) pour \(i\) impair.

Après une itération, le thread principal vérifie que la liste est bien ordonnée. Si c'est le cas, il quitte en affichant la liste et le nombre de swaps effectués. Si ce n'est pas le cas, il recommence l'itération (en alternant pair et impair).

La taille du tableau doit être définie comme une constante globale ARRAY_SIZE et votre code doit fonctionner pour toute valeur valide de celle-ci.

Vous devez utiliser plusieurs threads par itération afin de paralléliser les comparaisons/échanges. Le nombre de threads que vous allez utiliser est à votre discrétion (entre 2 et ARRAY_SIZE / 2). Essayez d'équilibrer le coût de la création des threads avec l'accélération résultant de la concurrence.