Remplissage d'un tableau, plusieurs threads

Bonjour,

J'ai 3 threads qui s'occupent de remplir un tableau.
Soit la variable "i" représentant l'index dans le tableau... i part de 0 jusqu'à "max".

Le programme fonctionn un px comme suit:
thread 1 met un int dans le tableau puis incrémente i
thread 2 fait de même
thread 3 aussi

l'ordre d'apparition m'importe peux dans le tableau, c'est d'ailleurs pourquoi je veux utiliser plusieurs threads.
Mais un problème potentiel que je vois venir me chicote et je voudrais en être sûr.

Chaque thread fait comme suit:

Code:

---

1 2 3

int j = ++i; array[j] = value

---

Voilà, avant de modifier le tableau, j'incrémente d'abord i afin que deux threads ou plus n'utilisent pas simultanément la même valeur de i (ce qui serait bien embêtant).
Le problème est... est-il encore possible que cela arrive? En effet disons dans un cas assez idéal où deux threads sont parfaitement synchronisés, parfaitement, aucun n'a de retard sur l'autre, alors ils auront donc la même valeur de 'j' au même moment et il pourrait y avoir conflit non?

Suis-je mieux d'intégrer des mutex?

Merci bcp

Array

Il y a un truc qui m'échappe... je n'ai pas compris ce que tu veux faire (ce que tu veux comme résultat final).

Chaque thread va de 0 à max ?
Si oui, vu le bout de code, le tableau contiendra (logiquement) la valeur du dernier qui a écrit.

Veux-tu obtenir le même résultat qu'en séquentiel ?
-> Il suffit de définir un i par thread avec le bon indice de début et le bon indice de fin (ou la taille).

---

Selon tes besoins tu peux peut être utiliser OpenMP pour exprimer le parallélisme, c'est plus simple et la plupart du temps ça ne modifie que peu ton programme séquentiel.

Clairement tu t'y prends mal, synchroniser des threads signifie les ordonnancer successivement pour éviter des accès concurrents à une ressource. Tu dois ainsi utiliser des mutexes pour ce que tu veux faire.

@Ehonn : le tableau "array", la variable "i" ayant de 0 à max... toutes ces variables sont communes aux 3 threads.

Oui, mais je n'ai pas compris ce que tu veux faire.

Par exemple,
avec array[9]
et value = 0 pour le thread 0
et value = 1 pour le thread 1
et value = 2 pour le thread 2
Veux tu ça (résultat aléatoire (le dernier qui écrit)) :

Code:

---

{1, 2, 0, 1, 2, 0, 2, 2, 1}

---

Ou ça (partage des itérations) :

Code:

---

{0, 0, 0, 1, 1, 1, 2, 2, 2}

---

---

Si tu veux écrire / mettre à jour une valeur dans un tableau partagé avec aucun partage des itérations, alors oui, il faut mettre un mutex lors des accès au tableau.

(Mais cela dégradera les performances.
En général, on utilise le parallélisme pour deux raisons:
- faire plusieurs choses simultanément (ex: une petite animation durant un temps de chargement)
- améliorer les performances (ex: faire plusieurs calculs (plus ou moins) indépendants sur plusieurs cœurs ou/et processeurs))

---

Dans le bout de code qui tu as donné, si i est partagé, et que chaque thread va de 0 à max (et qu'ils font chacun ++i) et si la taille de array est max, alors la lecture de array est comprise entre 0 et 3 * max (!)

En tout cas, le programme proposé ne va pas faire ce que tu veux, quoi que tu veuilles.
Parce que ce qu'il fera sera quasiment aléatoire ; et qu'il y a de bonnes chances qu'il finisse en segfault ou autre erreur encore plus tordue après avoir écrit en dehors des limites.

En cause : le test. Je suppose que ton code ressemble à :

Code:

---

1 2 3 4

while (i < N) { int j = ++i; tab[j] = V; }

---

Si ce thread est interrompu entre les lignes 1 et 2, et que i valait N-2, alors un autre thread le fera monter à N-1 (autorisé) ; puis le contrôle reviendra à ce thread qui incrémentera i pour obtenir N et dépasser la limite du tableau.

Ceci n'est qu'un des nombreux scénarios d'échec possibles.

Il faut donc au strict minimum employer des mutexes (entre le test et l'incrémentation il ne doit pas y avoir de modification).

Mais, étant donné le peu de code à exécuter, il y a de très fortes chances pour que le gain temporel apporté par la parallélisation soit totalement diminué par le coût des mutexes ; et donc pour que le programme soit bien plus lent.
Personnellement, je ramènerais donc l'exécution à un contexte séquentiel pour cette partie du code.

Après, si V est une fonction longue à calculer (ie. plus de quelques microsecondes ; valeur inventée à l'instant), alors la parallélisation et le coût des mutexes pourrait être intéressant. Mais pourrait être évité en coupant le tableau en portions à assigner par chaque fonction ; et en incrémentant directement, n'accédant donc jamais au même emplacement mémoire en parallèle, et en évitant donc tout besoin de mutex.

Voilà, bon courage !