Dans le chapitre précédent, nous avons expliqué la file d'attente de blocage implémentée dans ArrayBlockingQueue, en utilisant le formulaire Array.
La longueur du tableau doit être déterminée lors de la création. Si la longueur du tableau est petite, la file d'attente ArrayBlockingQueue sera facilement bloquée. Si la longueur du tableau est grande, elle gaspillera facilement la mémoire.
La structure de données de file d'attente convient naturellement à la forme de listes liées, et LinkedBlockingQueue est une file d'attente de blocage implémentée à l'aide de listes liées.
1. Implémentation de la liste liée
1.1 Classe interne de nœud
/ ** * Le nœud de la liste liée est également utilisé pour implémenter une liste liée unidirectionnelle * / nœud de classe statique <E> {e item; // pointer vers le nœud suivant du nœud de liste lié <e> Suivant; Nœud (e x) {item = x; }}Il existe une variable E qui stocke les données, et il existe une variable de référence suivante pointant vers le nœud suivant. Il peut implémenter la liste à sens unique la plus simple.
1.2 Comment implémenter la liste des liens
/ ** * son prochain point vers la tête de file d'attente, et ce nœud ne stockait pas les données * / nœud transitoire <e> tête; / ** * Node de queue de file d'attente * / nœud transitoire privé <E> Last;
Pour implémenter une liste liée, il doit y avoir deux variables, l'une représente la tête de la liste liée et l'autre représente le dernier de la liste liée. La tête et la dernière sont initialisées lorsque l'objet LinkedBlockingQueue est créé.
dernier = head = new nœud <e> (null);
Notez qu'une petite astuce est utilisée ici. Le nœud de tête de la liste liée ne stockait pas les données. Le nœud suivant indique vraiment stocker les premières données de la liste liée. Le dernier à la fin de la liste liée stockage en effet les dernières données de la liste liée.
1.3 Insérer et supprimer les nœuds
/ ** * Insérez le nœud à la queue de la file d'attente * / private void ENQUEUe (nœud <e> nœud) {// Assert putlock.isheldbyCurrentThread (); // Le thread actuel doit avoir obtenu le verrouillage putlock // pointer la référence suivante du nœud de queue de file d'ouverture d'origine au nouveau nœud de nœud, puis définir le nœud de nœud sur le nœud de queue de la file d'attente Last // Cela réalise le nœud d'insertion sur la queue de la file d'attente = Last.Next = Node; }Il est très simple d'insérer un nœud à la fin de la liste liée. Pointez le nœud suivant de la file d'attente d'origine en dernier vers le nouveau nœud de nœud, puis affectez le nouveau nœud de nœud au dernier nœud à la fin de la file d'attente. Cela permet d'insérer un nouveau nœud.
// Supprimez le nœud de tête de file d'attente et renvoyez les données de nœud supprimées privées e dequeue () {// Assert Takelock.isheldByCurrentThread (); // Le thread actuel doit avoir obtenu le verrouillage Takelock // Assert Head.item == null; Node <e> h = tête; // Les données du premier élément de la file d'attente sont stockées dans le premier nœud nœud <e> first = h.next; H.Next = H; // Aide GC // La définition de la nouvelle valeur de tête équivaut à supprimer le premier nœud. Parce que le nœud de tête lui-même ne stocke pas la tête de données = d'abord; // les données de l'en-tête de file d'attente e x = first.item; // supprime les données d'origine First.item = null; retour x; }Notez que la tête n'est pas l'en-tête, son prochain point vers l'en-tête, il est donc très simple de supprimer l'en-tête, qui est d'attribuer Head.Next à la tête, puis de retourner les données du nœud Head.Next original.
Lors de la suppression, faites attention à la situation où la liste liée est vide. La valeur de Head.Next est ajoutée à l'aide de la méthode ENQUEUe. Lorsque head.next == dernier, cela signifie que le dernier élément a été supprimé. Lorsque head.next == null, il ne peut pas être supprimé car la liste liée est déjà vide. Il n'y a pas de jugement ici parce que le jugement a été porté à l'endroit où la méthode de déshabille est appelée.
2. Verrouillage synchrone reentrantlock and condition
Étant donné que la file d'attente de blocage doit être bloquée et attendue lorsque la file d'attente est vide et que la file d'attente est pleine, alors deux conditions sont naturellement requises. Afin d'assurer la sécurité de la concurrence multithread, un verrou de synchronisation est nécessaire. Cela a été dit dans ArrayBlockingQueue.
Ici, nous parlerons des différentes choses sur LinkedBlockingQueue.
/ ** verrouillage exclusif, utilisé pour gérer les problèmes de concurrence de l'insertion des opérations de file d'attente, c'est-à-dire des opérations de put et d'offre * / private final rentrantlock putlock = new ReentrantLock (); / ** Condition de condition dont la file d'attente n'est pas satisfaite, elle est générée par Putlock Lock * / Condition finale privée Notfull = putlock.newCondition (); / ** verrouillage exclusif, utilisé pour gérer les problèmes de concurrence de supprimer les opérations de tête de file d'attente, c'est-à-dire les opérations de prise et de sondage * / private final reentrantlock takelock = new rentrantlock (); / ** Condition condition conditionnelle que la file d'attente n'est pas vide, il utilise la condition finale privée générée par Takelock Lock * / Condition finale privée NotEmpty = Takelock.NewCondition ();
2.1 Putlock et Takelock
Nous avons trouvé deux serrures utilisées:
Selon la déclaration ci-dessus, il peut y avoir des opérations d'insertion et de suppression d'éléments en même temps, donc il n'y aura donc pas de problème?
Analyons-le en détail. Pour les files d'attente, les opérations sont divisées en trois types:
Par conséquent, utilisez le verrouillage de putlock pour garder la dernière variable en sécurité et utilisez Takelock Lock pour garder la variable de tête en sécurité.
Pour toutes les variables de comptage impliquées dans le nombre d'éléments dans la file d'attente, AtomicInteger est utilisé pour garantir des problèmes de sécurité de la concurrence.
/ ** Le nombre d'éléments dans la file d'attente, utilisez la variable ATOMICInteger ici pour assurer des problèmes de sécurité de concurrence * / Private Final AtomicInteger Count = new ATOMICInteger ();
2.2 Notfull et Notorse
2.3 Processus de contrôle
Lors de l'insertion d'un élément:
Lors de la suppression des éléments:
Notez également que le signal et l'attente des méthodes de condition doivent être appelés lorsqu'un verrou est acquis. Par conséquent, il existe des méthodes de signal et de signal Notfull:
/ ** * Réveillez le fil en attente sous la condition novice, c'est-à-dire lors du retrait de l'en-tête de file d'attente, le fil qui se trouve vide et forcé d'attendre. * Notez que pour appeler la méthode de condition du signal, le verrouillage correspondant doit être obtenu, la méthode TakeLock.Lock () est appelée ici. * Lorsqu'un élément est inséré dans la file d'attente (c'est-à-dire en fonctionnement ou offrant une opération), la file d'attente n'est certainement pas vide et cette méthode sera appelée. * / private void SignalNotempty () {final reentrantlock takelock = this.Takelock; Takelock.lock (); essayez {notEmpty.signal (); } enfin {takelock.unlock (); }} / ** * Réveillez le fil en attente dans la condition notable, c'est-à-dire lorsque l'élément est ajouté à la fin de la file d'attente, le fil qui est plein et forcé d'attendre. * Notez que pour appeler la méthode de condition du signal, le verrouillage correspondant doit être obtenu, de sorte que la méthode putlock.lock () est appelée ici * lorsque l'élément (c'est-à-dire l'opération de prise ou de sondage) est supprimé dans la file d'attente, la file d'attente sera certainement insatisfaite et appellera cette méthode. * / private void signalNotfull () {final reentrantlock putlock = this.putlock; putlock.lock (); essayez {notfull.signal (); } enfin {putlock.unlock (); }}3. Méthode d'insertion de l'élément
public void put (e e) lance InterruptedException {if (e == null) lance un nouveau nullpointerException (); // Enregistrez le nombre d'éléments avant l'opération d'insertion int C = -1; // Créer un nouveau nœud nœud <e> node = new nœud <e> (e); reentrantlock final putlock = this.putlock; Count d'atomicinteger final = this.Count; putlock.lockInterruply (); essayez {// indique que la file d'attente est pleine, alors vous devez appeler la méthode notull.await pour faire attendre le thread actuel while (count.get () == capacité) {notull.await (); } // insérer un nouvel élément enqueue (nœud); // Ajouter 1 au nombre d'éléments dans la file d'attente actuelle et renvoyez le nombre d'éléments avant d'ajouter 1. C = count.getAndIncrement (); // C + 1 <La capacité signifie que la file d'attente n'est pas pleine, et le thread qui peut attendre l'opération d'insertion est éveillé si (C + 1 <Capacité) Notfull.Signal (); } enfin {putlock.unlock (); } // c == 0 signifie que la file d'attente est vide avant l'insertion. Lorsque la file d'attente est vide à un élément en cours de place, // réveillez le fil en attendant la suppression // Empêcher une acquisition fréquente des verrous Takelock, consommer des performances si (c == 0) signalNotempty (); }Prenant l'exemple de la méthode de vente, le processus général est le même que nous avons introduit plus tôt. Voici un code très bizarre. Lorsque l'élément est inséré, si la file d'attente n'est pas pleine, appelez Notull.Signal () pour réveiller le fil en attendant l'insertion.
Tout le monde est très confus. De manière générale, cette méthode doit être placée dans l'élément de suppression (méthode de la série), car lorsque nous supprimons un élément, la file d'attente doit être sous-pleine, puis appelez la méthode notfull.signal () pour réveiller le fil en attendant l'insertion.
Cela est principalement fait ici car lors de l'appel de la méthode du signal, le verrouillage correspondant doit être obtenu en premier. La serrure utilisée dans les méthodes Take Series est Takelock. Si vous souhaitez appeler la méthode notfull.signal (), vous devez d'abord obtenir le verrou de putlock. Cela entraînera une diminution des performances, donc une autre méthode est utilisée.
4. Supprimer l'élément d'en-tête de file d'attente
public e prise () lance InterruptedException {e x; int c = -1; Count d'atomicinteger final = this.Count; rentrantlock final takelock = this.Takelock; takelock.lockinterruptiblement (); Essayez {// signifie que la file d'attente est vide, alors vous devez appeler la méthode notEmpty.Await pour faire attendre le thread actuel while (count.get () == 0) {notEmpty.Await (); } // Supprimer l'élément d'en-tête de file d'attente et le renvoyer x = dequeue (); // Renvoie le numéro des files d'attente en cours, puis soustrayez le nombre des files d'attente par un c = count.getAndDecment (); // c> 1 signifie que la file d'attente n'est pas vide, donc elle réveille le fil qui peut attendre l'opération de suppression si (c> 1) NOTHEMPTY.SIGNAL (); } enfin {takelock.unlock (); } / ** * C == La capacité signifie que la file d'attente est pleine avant l'opération de suppression. * Réveillez le thread en attendant l'insertion uniquement lorsqu'un élément est supprimé de la file d'attente complète * Empêche l'acquisition fréquente de verrous putlock, consommant des performances * / if (c == capacile) signalNotfull (); retour x; }Pourquoi la méthode NotEmpty.signal () est-elle appelée, comparez notre explication dans la méthode de l'élément d'insert.
5. Afficher les éléments d'en-tête de file d'attente
// Affichez l'élément d'en-tête de file d'attente public e peek () {// La file d'attente est vide, renvoie null if (count.get () == 0) renvoyer null; rentrantlock final takelock = this.Takelock; Takelock.lock (); essayez {// obtenez le nœud d'en-tête de file d'attente premier nœud <e> first = head.next; // d'abord == null signifie que la file d'attente est vide, renvoie null if (premier == null) retourner null; else // retourne l'élément d'en-tête de file d'attente return First.item; } enfin {takelock.unlock (); }}Affichez l'élément d'en-tête de file d'attente, qui implique le nœud de tête, donc le verrouillage de Takelock doit être utilisé.
Vi. Autres méthodes importantes
6.1 Supprimer (objet O) Méthode
// Supprimez l'élément spécifié de la file d'attente o publique booléen supprime (objet o) {if (o == null) return false; // Parce qu'il ne s'agit pas de supprimer l'élément d'en-tête de liste, la tête des deux variables et la dernière sont impliquées, // putlock et takelock doivent être entièrement verrouillées (); essayez {// traverse toute la file d'attente, P représente le nœud actuel, et Trail représente le nœud précédent du nœud actuel // Parce qu'il s'agit d'une liste liée à sens unique, deux nœuds doivent être enregistrés pour (nœud <e> trail = tête, p = trail.next; p! = null; trail = p, p = p. {Unlink (p, trail); Retour Vrai; }} return false; } enfin {entièrementUnlock (); }}Supprimez l'élément spécifié de la liste. Étant donné que l'élément supprimé n'est pas nécessairement dans la tête de la liste, il peut y avoir deux variables la tête et la dernière fois, vous devez donc utiliser les serrures Putlock et Takelock en même temps. Parce qu'il s'agit d'une liste liée à sens unique, une piste variable auxiliaire est nécessaire pour enregistrer le nœud précédent afin que le nœud actuel P puisse être supprimé.
6.2 Méthode de link (nœud <e> p, nœud <e> trail)
// Supprimer le nœud actuel P, et le sentier représente le nœud précédent de p void unlink (nœud <e> p, nœud <e> trail) {// Définissez les données du nœud actuel sur null p.item = null; // Cela supprime le nœud p trail.next = p.Next; // Si le nœud P est le dernier dernier de la file d'attente et qu'il est supprimé, définissez le sentier pour Last If (Last == P) Last = Trail; // soustrayez le nombre d'éléments par un, et si la file d'attente d'origine est complète, appelez la méthode notull.signal () // En fait, ceci est appelé directement sans jugement, car la serrure de putlock doit être obtenue ici si (count.getandDecment () == Capacité) Notfull.Signal (); }Pour supprimer un nœud P dans la liste liée, il vous suffit de pointer le prochain nœud précédent de P de P vers le nœud suivant prochain nœud p.
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.