====== Section critique ======

[[in204:tds:sujets:td9|TD9]]

===== Références=====

[[http://en.cppreference.com/w/cpp/thread/unique_lock|std::unique_lock]]
[[http://en.cppreference.com/w/cpp/thread/mutex|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 :

<code cpp>
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;
	}
}
</code>

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

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

Implanter chacune des fonctions.

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


===== 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. 

<code cpp>
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);
}
</code>
Ou 

<code cpp>
#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);
}
</code>


<hidden Correction>

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

<code cpp>

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);
}

</code>

</hidden>


===== 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.

<hidden Correction>

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

<code cpp>
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);
}
</code>

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.

</hidden>
===== 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 [[http://en.cppreference.com/w/cpp/thread/unique_lock|std::unique_lock]] permet d’obtenir un accès exclusif sur un object [[http://en.cppreference.com/w/cpp/thread/mutex|std::mutex]]. Quand nous écrivons le code suivant :

<code cpp>
#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.
}
</code>

==== Question n°3.1 ==== 
Modifier les fonctions 
<code cpp>
int array_find_max(std::vector<int>& theArray, int* theMaxValue)
</code>

et 

<code cpp>
void array_multiply_by(std::vector<int>& theArray, int theValue)
</code>
pour implanter le mécanisme d’exclusion mutuelle propose.

<hidden 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.
<code cpp>

#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);
}

</code>
</hidden>

==== Question n°3.2 ====

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


<hidden 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.

</hidden>