Table of Contents

Section critique

TD9

Références

std::unique_lock std::mutex

Question n°1

Nous supposons que nous avons deux fonctions, une première fonction calcule la valeur maximale d’un tableau numérique : 

void array_find_max(
	std::vector<int>::const_iterator begin, 
	std::vector<int>::const_iterator end, int* theMaxValue)
{
	if (begin != end)
	{
		int result = *begin;
		begin++;
		for (; begin != end; begin++)
			if (*begin > result)
				result = *begin;
		*theMaxValue = result;
	}
}

la seconde fonction modifie le tableau en multipliant chaque valeur numérique du tableau par 2 : 

void array_multiply_by(
	std::vector<int>::iterator begin,
	std::vector<int>::iterator end, int theValue)
{
	for (; begin != end; begin++)
		*begin *= theValue;
}

Implanter chacune des fonctions.

Correction

Correction

Il suffit de recopier les fonctions dans un fichier main.cpp, d'ajouter l'inclusion include<vector> et de compiler.

Question 2

Pour tester les fonctions, nous devons créer des tableaux de taille conséquente. Ces tableaux peuvent-être créés par soit de manière aléatoire soit de manière cycliques. Ci-dessous quelques exemples de fonctions générant des tableaux de taille n et ayant comme valeur des nombres entre 0 et theMaxValue. Nous souhaitons exécuter en parallèle les deux fonctions. 

void initialize_array(std::vector<int>& theArray, int theSize,
	int theMaxValue)
{
	theArray.clear();
        theArray.resise(theSize);
	int step = theMaxValue / 3;
	theArray[0] = 0;
	for (int i = 1; i < theSize; i++)
			theArray[i] = (theArray[i-1] + step) % (theMaxValue + 1);
}

Ou 

#include<random>
 
void initialize_random_array(std::vector<int>& theArray, int theSize,
	int theMaxValue)
{
	static std::mt19937 gen(1729);
	std::uniform_int_distribution<> distrib(0, theMaxValue);
	theArray.clear();
	for (int i = 0; i < theSize; i++)
		theArray[i] = distrib(gen);
}

Correction

Correction

Nous pouvons utiliser pour ce faire une fonction de test du type suivant: 

void test_valid_execution(std::vector<int>& theArray)
{
	// Get the max value of the array
	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
 
	// Execute both threads in parallel
	int maxValue;
        array_find_max(theArray.begin(), theArray.end(), &maxValue);
	if (referenceMaxValue != maxValue)
		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue 
 
	array_multiply_by(theArray.begin(), theArray.end(), 2);
        array_find_max(theArray.begin(), theArray.end(), &maxValue);
	if (2*referenceMaxValue != maxValue)
		std::cout << "Error when computing the max value: " << maxValue << " found, " << 2*referenceMaxValue 
}
 
int main()
{
	std::vector<int> array;
	initialize_array(array, 10000, 100);
	test_valid_execution(array);
}

Question n°3

Nous souhaitons exécuter les deux fonctions précédents en parallèle.

Expliquer pourquoi les résultats ne sont pas toujours cohérents ? ie. que la valeur maximale retournée est supérieure à la valeur maximale du tableau spécifiée au montant de sa création.

Correction

Correction

Nous modifions le code pour cette fois-ci exécuter les deux fonctions en parallèle. 

void test_valid_execution(std::vector<int>& theArray)
{
	 // Get the max value of the array
	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
 
	// Execute both threads in parallel
	int maxValue;
	std::thread max_proc(&array_find_max, theArray.begin(), theArray.end(), &maxValue);
	array_multiply_by(theArray.begin(), theArray.end(), 2);
	max_proc.join();
 
	int modifiedMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
	if (referenceMaxValue != maxValue)
		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue << " expected";
}
 
int main()
{
	std::vector<int> array;
	initialize_array(array, 10000, 100);
	test_valid_execution(array);
}

Cependant, nous constatons que la fonction array_find_max retourne toujours une valeur maximale plus grande que celle qui était attendue. En fait, les deux fonctions array_find_max et multiply_array_by accède au même tableau, donc les valeurs accédées par array_find_max peuvent avoir été modifiées par multiply_array_by et donc être plus grandes ou plus petites que les valeurs initialement présentes dans le tableau. On ne doit pas autoriser un accès en lecture et en écriture au tableau en même temps.

Question n°4

Il faut utiliser un verrou qui permet à une méthode de se garantir l’exclusivité de l’usage du tableau. Pour ce faire, nous pouvons utiliser un objet std::mutex qui encapsule un mécanisme d’exclusion mutuelle. L’objet std::unique_lock permet d’obtenir un accès exclusif sur un object std::mutex. Quand nous écrivons le code suivant : 

#include <iostream>       // std::cout
#include <thread>         // std::thread
#include <mutex>          // std::mutex, std::unique_lock
 
std::mutex mtx;           // mutex fournissant le mécanisme d’exclusion mutuelle.
 
void my_function (int n, char c) {
	// section critique, tant que l'objet lck existe, personne ne pourra
	// accéder à mtx.
	std::unique_lock<std::mutex> lck(mtx);
	// Code s'exécutant.
}

Question n°3.1

Modifier les fonctions 

int array_find_max(std::vector<int>& theArray, int* theMaxValue)

et 

void array_multiply_by(std::vector<int>& theArray, int theValue)

pour implanter le mécanisme d’exclusion mutuelle propose.

Correction

Correction

Nous insérons simplement un objet vector_mutex et nous ajoutons avant toute exécution dans les deux fonctions la demande d'un verrour sur la mutex protégeant le tableau. 

#include<vector>
#include<random>
#include<algorithm>
#include<thread>
#include<iostream>
#include <mutex>          
 
std::mutex vector_mutex;
 
void array_find_max(
	std::vector<int>::const_iterator begin, 
	std::vector<int>::const_iterator end, int* theMaxValue)
{
	std::unique_lock<std::mutex> lock(vector_mutex);
	if (begin != end)
	{
		int result = *begin;
		begin++;
		for (; begin != end; begin++)
			if (*begin > result)
				result = *begin;
		*theMaxValue = result;
	}
}
 
void array_multiply_by(
	std::vector<int>::iterator begin,
	std::vector<int>::iterator end, 
	int theValue)
{
	std::unique_lock<std::mutex> lock(vector_mutex);
	for (; begin != end; begin++)
		*begin *= theValue;
}
 
void initialize_array(std::vector<int>& theArray, int theSize,
	int theMaxValue)
{
	theArray.clear();
	theArray.resize(theSize);
	int step = theMaxValue / 3;
	theArray[0] = 0;
	for (int i = 1; i < theSize; i++)
		theArray[i] = (theArray[i - 1] + step) % (theMaxValue + 1);
}
 
void initialize_random_array(std::vector<int>& theArray, int theSize,
	int theMaxValue)
{
	static std::mt19937 gen(1729);
	std::uniform_int_distribution<> distrib(0, theMaxValue);
	theArray.clear();
	for (int i = 0; i < theSize; i++)
		theArray[i] = distrib(gen);
}
 
void test_valid_execution(std::vector<int>& theArray)
{
	std::mutex mutex;
	 // Get the max value of the array
	int referenceMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
 
	// Execute both threads in parallel
	int maxValue;
	std::thread max_proc(&array_find_max, theArray.begin(), theArray.end(), &maxValue);
	array_multiply_by(theArray.begin(), theArray.end(), 2);
	max_proc.join();
 
	int modifiedMaxValue = *(std::max_element(theArray.begin(), theArray.end()));
	if (referenceMaxValue != maxValue)
		std::cout << "Error when computing the max value: " << maxValue << " found, " << referenceMaxValue << " expected";
}
 
int main()
{
	std::vector<int> array;
	initialize_array(array, 10000, 100);
	test_valid_execution(array);
}

Question n°3.2

Exécuter le code et vérifier que les résultats sont dorénavant cohérents.

Correction

Correction

Nous garantissons que la fonction termine avant qu'une autre fonction puisse modifiée le tableau. Le résultat retourné est toujours correct par rapport à l'instant où la première fonction a obtenu l'accès, il y a bien une “race condition”, mais le résultat de l'exécution est toujours correct, c'est soit la valeur maximale avant la modification, soit après la modification par la fonction multiply_array_by mais jamais une valeur qui correspond à un état du tableau dont partie était avant la modification et partie après la modification.