Laboratoire 3 - Mémoire et parallélisme

Sommaire

L’objectif de ce laboratoire est de regarder l’organisation de la mémoire dans les processus et de s’initier à la programmation multithread.

Tailles des binaires

Écrivez puis compilez :

  • un programme p0 qui retourne seulement 42: echo 'int main(int argc, char *argv[]){ return 42; }' > p0.c.
  • un programme p1 similaire à p0 mais qui include les trois fichiers d’entête standard: stdlib.h, stdio.h, unistd.h.
  • un programme p2 similaire à p0 mais en ajoutant une variable globale non initialisée char tableau[8000];.
  • un programme p3 similaire à p2 mais en initialisant le tableau char tableau[8000] = "hello";.

Questions

Comparez la taille des binaires et expliquez pourquoi il y a ou il n’y a pas de différence:

  • Entre p0 et p1
  • Entre p1 et p2
  • Entre p2 et p3

Taille mémoire des processus

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]){
	pause();
	return 42;
}

À l’aide des symboles etext, edata, end et de l’appel système sbrk, affichez les adresses de fin de segments de texte, des données initialisées, des données non initialisées et du tas (le motif « %p » de printf est très bien pour ça). Insérez les affichages avant le pause() ce qui donne quelque chose du genre:

etext 0x5621b925726d
edata 0x5621b925bfa0
end   0x5621b925bfa8
brk   0x5621bad0c000

Créez deux autres versions du programme ci-dessus en définissant une variable globale buf des façons suivantes:

  • pra.c qui contient char buf[1024*1024*4] = "Hello";
  • prb.c qui contient const char buf[1024*1024*4] = "Hello";

Créez encore deux autres versions du programme ci-dessus en définissant une variable locale buf (juste au début du main):

  • prc.c contient char *buf = malloc(1024*1024*4);
  • prd.c contient char buf[1024*1024*4] = "Hello";

Questions

  • Exécutez les différents programmes en arrière plan ./pra &. Comparez et expliquez les différences de taille en mémoire des différents programmes. Pour ce faire, utilisez ps -o vsz [pid]
  • Affichez le contenu de la mémoire associée à chaque processus avec pmap [pid]. Pour chacun des programmes, identifiez la zone de la mémoire qui est 4Mo(1024*1024*4) plus grosse dans que dans le programme initial.
  • Comparez les adresses données par pmap avec celles affichées par le programme.

Astuce : en bash « $! » désigne le PID de la dernière commande en arrière plan. Par exemple pmap $! fait la bonne chose.

Utilisation du parallélisme en C

Développez un programme p_prime qui calcule en C le nombre de nombres premiers inférieurs ou égaux au nombre passé en premier argument. Ce programme doit répartir le travail sur un nombre de threads qui est passé en second argument.

Exemple:

$ ./p_prime 5 2
3
$ ./p_prime 50 3
15
$ ./p_prime 10000000 10
664579

Pour ce faire, vous utiliserez une version modifiée du crible d’Ératosthène abordé dans le laboratoire précédent. Notons que, même si cet algorithme répartit le calcul sur différents threads, celui n’est vraiment pas le plus efficace, mais permet d’éviter de devoir faire des synchronisations.

#include <stdbool.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

// Liste de travail qui représente si un nombre est premier ou non
// work_list[i] == 1 si est seulement si i est premier.
bool *work_list = NULL;

// Chaque thread travaille sur une fraction du tableau
// Chacun commence à un indice différent puis "saute" par-dessus les autres
void *do_work(void *ptr)
{
	long int depart = (long int)ptr;
	bool is_prime= false;

	for(long int i = depart; i <= maximum; i+= NOMBRE_DE_THREAD)
	{
		is_prime = true;
		// C'est inefficace, car on parcourt tous les entiers
		// au lieu de tester seulement les nombres premiers
		// mais c'est plus simple à coder (pas de synchronisation nécessaire)
		for(long int j=2;j <= sqrt((double)i); j++)
		{
			if(i%j == 0){
				is_prime = false;
				break;
			}
		}

		if(is_prime){
			work_list[i] = true;
		}
	}
}

int main(int argc, char **argv)
{
	if (argc < 3) {
		fprintf(2, "Vous devez fournir la borne supérieure et le nombre de threads\n");
		return 1;
	}
	char* endptr = NULL;
	long maximum = strtol(argv[1], &endptr, 0); // Entier maximum à tester
	if (*endptr != '\0' || maximum <= 0) {
		fprintf(2, "La borne supérieure doit être un nombre entier supérieur à 0\n");
		return 1;
	}
	endptr = NULL;
	int nb_thread = strtol(argv[2], &endptr, 0); // Nombre de threads à utiliser
	if (*endptr != '\0' || nb_thread <= 0) {
		fprintf(2, "Le nombre de threads doit être un nombre entier supérieur à 0\n");
		return 1;
	}

	work_list = malloc(sizeof(bool) * (maximum+1)); // Allocation de la liste de travail
	if (work_list == NULL) {
		fprintf(stderr, "Erreur lors de l'allocation");
	}

	// Création de l'ensemble des threads, qui exécuteront la méthode `do_work`.
	TODO

	// Attendre que l'ensemble des threads soit terminé.
	TODO

	// Comptage du nombre de nombres premiers trouvés
	int nb=0;
	for(int i=2; i <= maximum; i++)
	{
		if(work_list[i]){
			nb++;
		}
	}

	printf("Nombre de nombres premiers trouvés : %d\n", nb) ;

	return 0;
}
  • Note: pour utiliser les threads, il est nécessaire d’inclure pthread.h et de compiler avec -pthread.
  • Fonctions utiles: pthread_create, pthread_join, strtol

Questions

  • Vérifiez bien que vous obtenez les mêmes résultats qu’avec la version monothread du lab précédent.
  • Observez les différents appels système effectués par votre proposition à l’aide de strace -f. Quels sont-ils ?
  • Regardez, avec time que le temps processeur utilisé et le pourcentage de CPU utilisé varie avec le nombre de threads.
  • Désolez-vous que la version multithread soit beaucoup plus lente que la version monothread.

Extra

Implémentez une version multithread qui soit plus efficace que la version monothread (sans changer l’algorithme de base, c’est toujours le crible d’Ératosthène qu’on veut). Attention, c’est beaucoup plus difficile qu’il n’y parait (finissez vos TP plutôt). Les détails dans INF5171 et INF7235.