En écrivant une implémentation multithread d'un BST en Java, j'arrive au problème suivant. Ce BST ne doit pas utiliser un verrou global, mais verrouiller le moins possible, en particulier uniquement les nœuds qui sont en cours de modification (commande d'ajout et de suppression). Ainsi, d'autres threads peuvent être actifs dans l'arborescence tant qu'ils n'essaient pas de changer les mêmes nœuds que vous.
Je ne trouve pas de moyen d'implémenter la suppression d'un nœud qui a 2 enfants. L'algorithme normal dit de trouver le successeur dans l'ordre du nœud à supprimer, de le mettre à la place du nœud supprimé, puis de supprimer le nœud copié. Mais cela peut créer un problème pour un thread qui se trouve entre ces deux nœuds et qui a besoin du nœud copié, après le transfert, le thread ne trouvera pas le nœud demandé, même s'il se trouve dans l'arborescence.
Regardez l'exemple suivant: Tread 1 exécute remove (5) . Il trouve et copie la clé suivante (6) sur le nœud, puis supprime le nœud de la copie. Mais en même temps, un autre thread exécutant une commande contains (6) et attend le nœud 8, après l'exécution du nœud numéro 6 ne sera plus dans son chemin et il renverrait un faux résultat même si le nœud 6 est toujours dans l'arbre.
Illustration de l'état avant la commande remove (la flèche bleue indique où se trouve le 2 nd thread.
Illustration de l'état après la commande remove (la flèche bleue indique où se trouve le 2 nd thread.
Comment puis-je surmonter ce problème sans verrouiller l'intégralité de l'arborescence?
3 Réponses :
Synchronisez les nœuds indépendamment du BST. Cela signifie que si vous supprimez un nœud, vous devrez verrouiller le nœud le plus en haut affecté et tous les nœuds en dessous pour empêcher d'autres threads de lire ou de modifier ces nœuds. Malheureusement, avec un BST, cela pourrait signifier le verrouillage du nœud racine en fonction de l'opération, ce qui empêcherait effectivement toute lecture de se produire.
Je pense que ce serait la mise en œuvre la plus rapide pour ce que vous essayez de faire.
Si le tri n'a pas d'importance, je vous recommande d'utiliser une implémentation HashMap à la place. Il vous suffirait de verrouiller les compartiments au lieu de potentiellement la carte entière.
Je pense que soutenir le BST avec un hashset pourrait être la voie à suivre ici. De cette façon, vos recherches seraient indépendantes du verrouillage BST et vous donneraient un O (1) sur contient.
La solution que j'ai utilisée était d'avoir un numéro de version pour le BST, et chaque fois qu'un remove est requis pour un nœud avec deux enfants, j'augmente le numéro de version avant de supprimer le nœud dupliqué.
/ p>
Ensuite, chaque opération vérifie le numéro de version avant de commencer et si j'obtiens un résultat qui indique qu'une clé n'a pas été trouvée, je vérifie si le numéro de version est toujours le même, si ce n'est pas le même je réessaye l'opération.
Cela signifie:
remove et contains - si l'action a échoué (ce qui signifie que la clé n'a pas été trouvée) et que la version a été modifiée, réessayez. insert - Je vérifie le numéro de version, pas à la fin de l'action, mais lorsque je suis à une feuille et avant de créer et d'ajouter un nouveau nœud. Si je suis sur le point d'ajouter un nouveau nœud, cela signifie que je n'ai pas trouvé de nœud avec cette clé, je veux m'assurer que la clé n'est vraiment pas dans l'arborescence avant de la changer et de créer une nouvelle feuille pour éviter une situation où une double clé sera ajoutée à l'arborescence, puis je devrai refaire cela en supprimant des nœuds. Mais cela ne vous obligerait-il pas à honorer le verrou sur un contient? Je vois comment cela fonctionnera, mais je ne sais pas s'il s'agit de la mise en œuvre optimale.
@RohitShetty, contient des exécutions sans engager aucun verrou car il n'écrit ni ne change rien dans l'arborescence. La seule chose qui doit être synchronisée est le compteur de version, mais là j'utilise des opérations atomiques ( AtomicInteger de Java).
Pourquoi utilisez-vous un BST pour cette exigence?
@RohitShetty, ceci est un exercice spécifiquement sur la création d'un BST sécurisé multithreading.
Je suppose que stackoverflow.com/a/54065194/4109972 est une option