OK, je sais que cela peut sembler assez stupide (et je crains que ce soit), mais je ne suis pas complètement satisfait de la réponse que je me suis donnée, je pensais que cela valait la peine de le demander ici. Je traite avec un exercice sur la concurrence (en Java) qui va comme ça
Étant donné un graphique Sudoku résolu, déterminez, à l'aide d'un nombre fixe de threads fonctionnant en même temps, que le graphique a été correctement résolu, c'est-à-dire aucune violation des règles canoniques ne surviennent (un nombre doit apparaître dans sa ligne, sa colonne. et son bloc qu'une seule fois).
Maintenant, ma question est la suivante: puisque les threads ne doivent-ils que jouer des "lectures", rassembler des infos de la carte et les élaborer ailleurs, n'ont-ils pas pu travailler sans se soucier de la concurrence? L'état du graphique est toujours cohérent car aucune "écrit" n'est effectuée, il n'est donc jamais changé.
ne sont pas des blocages / blocs synchronisés / méthodes synchronisées nécessaires si et uniquement s'il y a un risque de perte de ressources "des ressources" En d'autres termes, ai-je compris la concurrence de la bonne façon?
7 Réponses :
À mon avis, votre compréhension est correcte. La corruption des données ne peut se produire que si l'un des threads écrit sur les données.
Si vous êtes sûr à 100% qu'aucun thread ne écrit, il est prudent de sauter la synchronisation et le verrouillage ...
EDIT: Sauter le verrouillage dans les thèses des cas est la meilleure pratique! :)
En fait, c'est la meilleure pratique. Le partage des données immuables parmi les threades de lecture uniquement est la meilleure façon de ne pas gâcher les problèmes de synchronisation et fournit la meilleure performance :-)
@Jbnizet merci d'avoir souligné cela. Je monte cette dernière ligne.
Mais n'oubliez pas ce que Stuart Mark a dit dans la première réponse: les objets immuables doivent être «publiés en toute sécurité». Cela signifie, sans aucun autre thread ne peut voir l'objet de données immuable jusqu'à ce qu'il soit complètement construit. Il y a des moyens subtiles (décrit dans Java simultancy dans la pratique ) qu'un programme multi-threadé exécuté sur une machine multi-processeur peut laisser un thread de voir un objet tel qu'il était avant que d'autres discussions soient terminées. .
Aucun besoin de synchronisation du fichier s'il est en lecture seule.Basical verrouiller est appliqué à la section Section critique . Étant donné que la synchronisation rend le programme lent, car aucun accès à threads multiples, il est donc préférable de ne pas utiliser de verrouillage en cas de fichiers en lecture seule.
De mon point de vue, le verrouillage est nécessaire si vous écrivez et cette écrit prend beaucoup de temps à compléter en raison de la latence de réseau ou de la tenue de traitement massive. Sinon, il est assez sûr de laisser le verrouillage.
Même si l'opération d'écriture prend deux cycles d'horloge ou 1 nanoseconde, le verrouillage est nécessaire lors de l'écriture.
En théorie c'est correct. La chose est que de telles opérations d'écriture sont effectuées dans 99% de tous les cas pour un support de stockage en mémoire, tels que CHM et la synchronisation d'écriture est fourni hors de la boîte. Vous n'avez donc pas à vous soucier de lui par vous-même. Pour tous les autres cas, vous devez faire le verrouillage à la main et je pense que le démarreur de sujet signifiait exactement cela.
@Ijejeteer: C'est mauvais. Et votre règle est inapplicable de toute façon: "Une longue période" ne veut rien dire de manière concrète. Je vous suggère de lire la concurrence dans la pratique, de Brian Goetz.
Imaginez que vous ayez un tas de travail à compléter (vérifier 9 lignes, 9 colonnes, 9 blocs). Si vous souhaitez que les threads complètent ce groupe de 27 unités de travail et si vous souhaitez terminer le travail sans double travail, les threads devront être synchronisés. Si d'autre part, vous êtes heureux d'avoir des threads pouvant effectuer une unité de travail effectuée par un autre fil, puis vous n'avez pas besoin de synchroniser les threads.
En fait, cela n'a rien à faire si vous voulez éviter de faire dupliquer le travail, mais simplement avec la manière dont vous planifiez le travail. Il est trivial pour le travail de planification statique qu'aucun travail n'est répété sans verrouillage du tout.
En effet. Il pourrait y avoir un algorithme de Monte-Carlo avec une probabilité non nulle de travail Certains , mais qui complète en moyenne suffisamment de processeurs, en moins de temps qu'un autre algorithme qui garantit de ne jamais dupliquer le travail.
@VOO Dans cet exemple simple de vérification de la validité d'une carte Sudoku, oui on peut distribuer statiquement le travail entre différents threads et aucun verrouillage n'est requis. Mais en général, si chaque unité de travail prend différentes fois de temps à compléter, il n'est pas optimal de diviser le travail entre les threads statiquement. Certains threads seraient surchargés et certains threads n'auraient peut-être pas assez de travail. JamesLarge, comment déduisez-vous que la duplication du travail se termine en moyenne en moins de temps qu'un algorithme qui ne duplique jamais de travail? En général, je dirais que la duplication du travail est un grand non.
@Anonymous Il y a beaucoup de problèmes lorsque les frais de communication et de synchronisation supplémentaires sont de beaucoup moins que certains threads dupliquant accidentellement des travaux. Les simulations de Monte Carlo à mesure que James mentionne l'être un bon exemple de celui-ci. Tout simplement une question de savoir combien vous dupliquez et à quelle hauteur le coût de la communication serait de l'éviter. Pas de règle difficile et rapide là-bas.
C'est une question assez subtile, pas stupide du tout.
Les threads multiples qui lisent une structure de données simultanément peut le faire sans synchronisation, uniquement si la structure de données a été publiée en toute sécurité . C'est une question de visibilité de la mémoire, pas un problème de synchronisation ou une condition de course.
Voir la section 3.5 de Goetz, et. Al., Java Concurrence dans la pratique , pour une discussion ultérieure du concept de publication sûre. Section 3.5.4 sur "Objets efficaces immuables" semble applicable ici, car la Commission devient effectivement immuable à un moment donné, car elle n'est jamais écrite après avoir atteint l'état résolu.
brièvement, les threads de l'écrivain et les threads du lecteur doivent effectuer une activité de coordination de la mémoire pour vous assurer que les threads de lecteur ont une vue cohérente de ce qui a été écrit. Par exemple, le fil de l'écrivain pourrait écrire la carte Sudoku puis, tout en maintenant une serrure, stockez une référence au tableau dans un domaine statique. Les filets de lecture pourraient alors charger cette référence, tout en maintenant la serrure. Une fois qu'ils ont fait cela, ils sont assurés que toutes les écrivies précédentes à la Commission sont visibles et cohérentes. Après cela, les threads de lecteur peuvent accéder à la structure de la carte librement, sans autre synchronisation.
Il existe d'autres moyens de coordonner la visibilité de la mémoire, telle que écrit / lit à une variable volatile ou à un Basé sur un échange dans les commentaires avec Donal Fellows , je devrais aussi souligner que les La publication sécurisée l'exigence s'applique également lors de l'obtention des résultats des threads de lecteur. C'est-à-dire qu'une fois que l'un des threads de lecteur résultait de sa partie du calcul, il doit publier ce résultat quelque part afin de pouvoir être combinés avec les résultats des autres fils de lecteur. Les mêmes techniques peuvent être utilisées comme avant, telles que le verrouillage / la synchronisation sur une structure de données partagée, des volatiles, etc. Toutefois, cela n'est généralement pas nécessaire, car les résultats peuvent être obtenus à partir d'un futur renvoyé par atomicreference . Utilisation de constructions de simultanées de niveau supérieur, telles que des verrous ou des barrières, ou la soumission de tâches à un exécuteur fournira également des garanties de visibilité de mémoire.
ExecuTeurservice.Submit ou invoke . Ces constructions gèrent automatiquement les exigences de publication sans danger, la demande n'a donc pas à traiter de la synchronisation.
Cependant, les différents threads de lecteur doivent également voter quelque part sur la question de savoir si leur fragment de tâche contribue au succès global ou à l'échec du chèque Sudoku. Qui est une écriture ...
Les rapports et la fusion des résultats partiels ne doivent pas nécessairement nécessairement impliquer l'écriture à l'état mutable partagé. Une alternative, souvent préférable, consiste à renvoyer un résultat en tant que valeur de fonction, telle que d'un appelable . Ceci est disponible pour les tâches de coordination du fil via un futur . Voir exécutorservice.invokeall . Cela implique de remettre les valeurs entre les threads, mais aucun verrouillage supplémentaire n'est nécessaire.
Cela dépend vraiment de la mise en œuvre de la messagerie interentrée, n'est-ce pas? Si vous allez appeler une barrière de mémoire aller simple, vous aurez besoin de quelque chose d'équivalent de retour. (Mind You, car c'est vraiment un seul bit - ou plus de manière réaliste un octet unique ou un mot en fonction de la méthode utilisée - il y a un certain nombre de moyens assez efficaces de le faire.)
Droite, il doit y avoir une barrière de mémoire pour les valeurs de retour. Dans mon commentaire ci-dessus, cela est encapsulé dans appelable et futur (implémenté par futueTask ). Si l'application utilise ces constructions, elle n'a pas besoin de faire sa propre synchronisation.
Fwiw, j'irais avec un exécuttorservice aussi, mais c'est parce que les tâches d'tangage à une piscine de thread (avec une implémentation standard) sont easy à coder correctement et facile à calibrer à le matériel disponible.
Ouais! Non seulement les bibliothèques J.U.C traitent automatiquement la filetage, elles traitent également des exigences de publication sans danger. J'ai mis à jour la réponse avec ces informations. Merci d'avoir élevé ce point.
Scénario où Si vous passez cet objet aux threads de travailleur, vous êtes prêt à partir. Si vos objets ne répondent pas à toutes ces conditions, vous pouvez toujours rencontrer des problèmes de concurrence, dans la plupart des cas, il est dû au fait que JVM peut réorganiser les déclarations de la volonté (pour des raisons de performance), et elle pourrait réorganiser ces déclarations de telle manière. Ce threads de travailleur sont lancés avant la construction de la carte Sudoku.
Voici un très bel article sur Objets immuables . thread1 écrit certaines données, puis une bande de fils doit lire ces données ne nécessite pas de verrouillage si elle est faite correctement. En correctement, je veux dire que votre carte Sudoku est un objet immuable et, par objet immuable, je veux dire:
myClass.instnce = ceci ).
Pour qu'un fil soit garanti pour observer les effets d'une mémoire d'écriture à la mémoire principale, l'écriture doit arriver-avant la lecture. Si écriture et de lecture se produire dans différents threads, qui nécessite une action de synchronisation. La spécification définit de nombreux types d'actions de synchronisation différents. Une telle action exécute une déclaration synchronisée , mais des alternatives existent.
Détails
La spécification de langue Java écrit:
Deux actions peuvent être commandées par un arrive-avant relation. Si une action arrive - avant une autre, la première est visible et commandée avant la seconde.
et
Plus précisément, si deux actions partagent une relation avant la relation, elles ne doivent pas nécessairement sembler avoir eu lieu dans cet ordre à tout code avec lequel ils ne partagent pas une relation. Écrit dans un fil dans une course de données avec des lectures dans un autre thread peut, par exemple, semble se produire à l'écart de ces lectures.
Dans votre cas, vous voulez que les fils de lecture pour résoudre le droit sudoku. C'est-à-dire que l'initialisation de l'objet Sudoku doit être visible aux filets de lecture et l'initialisation doit donc se produire - avant les fils de lecture lus du Sudoku.
La spécification définit arrive-avant comme suit:
Si nous avons deux actions x et y, nous écrivons Si Il existe un avantage avant la fin d'un constructeur d'un objet au début d'un finaliseur (§12.6) pour cet objet.
Si une action x synchronise - avec une action suivante Y, nous avons également HB (x, y).
si hb (x, y) et hb (y, z), puis hb (x, z).
Depuis la lecture se produit dans un autre thread que l'écriture (et non dans un finaliseur), nous avons donc besoin d'une action de synchronisation pour établir que l'écriture arrive-avant la lecture. La spécification donne la liste exhaustive suivante des actions de synchronisation:
Une action de déverrouillage sur le moniteur M Synchronise - avec toutes les actions de verrouillage ultérieures sur m (où "suivant" est définie en fonction de l'ordre de synchronisation).
une écriture à une variable volatile V (§8.3.1.4) Synchronise - avec toutes les lectures ultérieures de V par n'importe quel thread (où "suivant" est défini en fonction de l'ordre de synchronisation).
Une action qui commence un thread synchronise - avec la première action dans le fil qu'il commence.
L'écriture de la valeur par défaut (zéro, false ou null) à chaque variable se synchronise - avec la première action dans chaque thread. (Bien que cela puisse paraître un peu étrange d'écrire une valeur par défaut à une variable avant que l'objet contenant la variable est allouée, conceptuellement chaque objet est créé au début du programme avec ses valeurs initialisées par défaut.)
L'action finale dans un thread T1 se synchronise - avec toute action dans un autre thread T2 qui détecte que T1 a terminé (T2 peut l'accomplir en appelant Si le thread T1 interrompt le thread T2, l'interruption par T1 se synchronise - avec n'importe quel point où tout autre thread (y compris T2) détermine que T2 a été interrompu (en ayant une exception interrompue ou en invoquant une interruption .Interrupted ou un fil .isInterrupted).
Vous pouvez choisir l'une de ces méthodes pour établir se-avant. En pratique, le démarrage des fils de lecture après que le Sudoku ait été entièrement construit est probablement le moyen le plus simple.
hb (x, y) pour indiquer que x arrive-avant y .
x et y sont des actions du même fil et x est avant y Commande de programme, puis hb (x, y) .
t1.isalive () ou ou T1.Join () )
"Un nombre fixe de threads" règne-t-il à l'aide d'un seul thread?
L'état partagé et mutable doit être protégé.