Dans le chapitre précédent, nous avons introduit la file d'attente de blocage BlockingQueue. Ci-dessous, nous introduisons sa classe d'implémentation couramment utilisée ArrayBlockingQueue.
1. Utilisez des tableaux pour implémenter des files d'attente
En raison des exigences particulières de la structure de données de la file d'attente, il est naturellement adapté à être mis en œuvre sous la forme d'une liste liée. Deux variables sont utilisées pour enregistrer respectivement l'en-tête et la fin de la liste liée. Lors de la suppression ou de l'insertion de la file d'attente, modifiez simplement l'en-tête ou la fin de la liste liée. De plus, la liste liée est liée de manière référence, donc sa capacité est presque illimitée.
Alors, comment utiliser les tableaux pour implémenter des files d'attente, nous avons besoin de quatre variables: objet [] tableau pour stocker des éléments dans la file d'attente, HeadIndex et TailIndex enregistrent la tête et la queue de file d'attente, et comptez enregistrer le nombre de files d'attente.
Un moyen très intelligent est utilisé ici. Nous savons que lorsqu'un élément est inséré dans la file d'attente, il prend une position dans le tableau. Lorsqu'un élément est supprimé, la position du tableau est réellement gratuite, indiquant qu'un nouvel élément peut être inséré dans cette position.
Donc, avant d'insérer un nouvel élément, nous devons vérifier si la file d'attente est pleine, et avant de supprimer l'élément, nous devons vérifier si la file d'attente est vide.
2. Variables des membres importants dans ArrayBlockingQueue
/ ** stocker les éléments dans la file d'attente * / objet final [] éléments; / ** la position de la tête de file d'attente * / int prenantIndex; / ** la position de la queue de file d'attente * / int putIndex; / ** le nombre d'éléments dans la file d'attente actuelle * / int count; / ** Utilisé pour garantir la sécurité des variables partagées multi-thread * / verrouillage final reentrantlock; / ** Lorsque la file d'attente est vide, la méthode d'attente de Notempty sera appelée pour faire en sorte que le thread actuel attende * / condition finale privée Notempty; / ** Lorsque la file d'attente est pleine, la méthode d'attente de Notfull sera appelée, faisant attendre le fil actuel * / condition finale privée notable;
Il y a plus de variables de verrouillage, de note et de notable pour implémenter des conditions de sécurité et d'attente de threads multiples. Comment fonctionnent-ils?
2.1 Le rôle du verrouillage
Étant donné que ArrayBlockingQueue fonctionne sous plusieurs threads, lors de la modification des variables des membres telles que des éléments, TakeIndex, Putindex et Count, les problèmes de sécurité multi-thread doivent être pris en compte. Par conséquent, le verrouillage exclusif de verrouillage est utilisé ici pour assurer la sécurité des opérations simultanées.
2.2 Le rôle de Notors et Notfull
Étant donné que les files d'attente de blocage doivent être implémentées, lorsque la file d'attente est vide ou que la file d'attente est pleine, l'opération de lecture ou d'insertion de file d'attente doit attendre. Nous avons donc pensé à l'objet de condition sous le cadre de concurrence et l'utiliser pour le contrôler.
Dans AQS, nous présentons le rôle de cette classe:
3. Ajouter une méthode d'élément
3.1 Ajouter (e e) et offrir (e e) Méthodes:
// Appelez la méthode dans la classe Parent AbstractQueue. public boolean add (e e) {// implémenter si (offrir (e)) renvoie true; Sinon jetez un nouveau IllégalStateException ("Full Full"); } // Ajouter un nouvel élément à la fin de la file d'attente. Retour vrai signifie que l'addition est réussi, faux signifie que l'addition a échoué, et aucune exception n'est lancée par l'offre booléenne publique (e e) {checknotnull (e); Ventrantlock final Lock = this.lock; // Utilisez le verrouillage pour garantir que la modification multi-threadded des attributs de membre Lock.LOCK (); Essayez {// La file d'attente est pleine et l'ajout d'éléments échoue, renvoie false. if (count == items.length) return false; else {// Appelez la méthode d'EnQueue pour insérer l'élément dans la file d'attente Enqueue (E); Retour Vrai; }} enfin {lock.unlock (); }}La méthode ADD est implémentée en appelant la méthode de l'offre. Dans la méthode de l'offre, il est nécessaire de déterminer d'abord si la file d'attente est pleine. S'il est plein, il renverra directement False sans bloquer le thread actuel. Si vous n'êtes pas satisfait, appelez la méthode d'Enqueue pour insérer l'élément dans la file d'attente.
Remarque: Utilisation de Lock.Lock () VICIAGE ALIME qu'un seul thread modifie les variables membre en même temps pour éviter des problèmes de fonctionnement simultanés. Bien qu'il bloque également le thread actuel, ce n'est pas une attente conditionnelle, c'est simplement parce que le verrou est maintenu par d'autres threads, et le temps de fonctionnement de la méthode dans ArrayBlockingQueue n'est pas long, ce qui équivaut à ne pas bloquer le fil.
3.2 Méthode de put
// Ajoutez un nouvel élément à la fin de la file d'attente. Si la file d'attente est pleine, le fil actuel attendra. Réponse à l'interruption Exception publique void put (e e) lève InterruptedException {checknotnull (e); Ventrantlock final Lock = this.lock; // Utilisez le verrouillage pour vous assurer que les multi-threads modifient la sécurité des attributs de membre LOCK.LOCKinterruptily (); essayez {// si la file d'attente est pleine, appelez la méthode notull.await () pour permettre au thread actuel d'attendre que la file d'attente ne soit pas pleine pendant (count == items.length) notull.await (); // Appelez la méthode d'Enqueue pour insérer l'élément dans la file d'attente en file d'attente (E); } enfin {lock.unlock (); }}Le processus général de la méthode de l'offre est le même que la méthode de l'offre. Cependant, lorsque la file d'attente est pleine, la méthode notull.await () sera appelée pour faire le bloc de thread actuel et attendre que la file d'attente soit supprimée par d'autres threads. Lorsque la file d'attente n'est pas satisfaite, le fil d'attente sera éveillé.
3.3 Offre (e e, temps de temps de longue date, unité de timeUnit)
/ ** * Ajoutez un nouvel élément à la fin de la file d'attente. S'il n'y a pas d'espace disponible dans la file d'attente, le fil actuel attendra. * Si le temps d'attente dépasse le délai d'expiration, alors False est renvoyé, indiquant que l'ajout a échoué * / Public Boolean Offre (E E, Long Timeout, TimeUnit Unit) lève InterruptedException {CheckNotNull (e); // Calculez la valeur temporelle des nanos de nanos totaux maximaux en attente = Unit.Tonanos (délai d'expiration); Ventrantlock final Lock = this.lock; // Utilisez le verrouillage pour vous assurer que la modification multi-thread des attributs de membre LOCK.lockinterruptily (); Essayez {// La file d'attente est complète while (count == items.length) {// nanos <= 0 signifie que le temps d'attente maximal est arrivé, il n'est donc plus nécessaire d'attendre. Retour False, indiquant que l'addition a échoué. if (nanos <= 0) renvoie false; // Appelez la méthode notfull.awaitnanos (nanos), le temps de délai d'expiration des nanos sera automatiquement éveillé. // s'il est réveillé à l'avance, le temps restant est renvoyé nanos = notull.awaitnanos (nanos); } // Appelez la méthode d'EnQueue pour insérer l'élément dans la file d'attente (E); Retour Vrai; } enfin {lock.unlock (); }}Le flux général de la méthode de put est le même que la méthode de put, il s'agit simplement d'appeler la méthode notfull.awaitnanos (nanos) pour faire attendre le fil actuel et définir le temps d'attente.
4. Méthode de suppression de l'élément
4.1 Retirez () et Poll () Méthodes:
// Appelez la méthode dans la classe Parent AbstractQueue. public e dis do dans () {// implémentation en appelant le scrutin e x = poll (); if (x! = null) return x; Sinon, jetez un nouveau NosucheMelementExement (); } // Supprimez le premier élément de la file d'attente (c'est-à-dire l'en-tête de file d'attente) et renvoyez-le. Si la file d'attente est vide, elle ne lance pas d'exception, mais renvoie NULL. public e poll () {final reentrantlock Lock = this.lock; // Utilisez le verrouillage pour garantir que la modification multi-threadded des attributs de membre Lock.LOCK (); Essayez {// Si Count == 0 et la liste sont vides, renvoyez NULL. Sinon, appelez la méthode Dequeue pour renvoyer l'élément d'en-tête de liste (count == 0)? NULL: DEQUEUE (); } enfin {lock.unlock (); }}La méthode de suppression est implémentée en appelant la méthode Poll (). Dans la méthode Poll (), si la liste est vide, elle renvoie NULL, sinon la méthode de désagréation est appelée pour retourner l'élément d'en-tête de liste.
4.2 Méthode Take ()
/ ** * Retournez et supprimez le premier élément de la file d'attente. Si la file d'attente est vide, le fil avant attendra. Exception d'interruption de réponse * / public e prise () lance InterruptedException {final reentrantLock Lock = this.lock; // Utilisez le verrouillage pour vous assurer que les multi-threads modifient la sécurité des attributs de membre LOCK.LOCKinterruptily (); Essayez {// Si la file d'attente est vide, appelez la méthode NotEmpty.Await () pour laisser le thread actuel attendre. // jusqu'à ce qu'un autre thread insère des éléments dans la file d'attente, le fil sera éveillé. while (count == 0) notEmpty.Await (); // Appelez la méthode DeQueue pour retourner l'élément d'en-tête de liste retourne dequeue (); } enfin {lock.unlock (); }}Lorsque la méthode Take () est vide, le thread actuel doit attendre qu'un autre thread insère un nouvel élément dans la file d'attente et le thread sera éveillé.
4.3 Sondage (temps d'attente longue, unité TimeUnit)
/ ** * Retournez et supprimez le premier élément de la file d'attente. Si la file d'attente est vide, le fil avant attendra. * Si le temps d'attente dépasse le délai d'expiration, alors FAUX est renvoyé pour indiquer que l'élément est échoué * / public e Poll (temps d'attente longue, unité de tempsunit) lance InterruptedException {// Calculer la valeur maximale du temps d'attente dans les nanos totaux Long Nanos = Unit.Tonanos (délai d'attente); Ventrantlock final Lock = this.lock; // Utilisez le verrouillage pour garantir que la modification multi-threadded des attributs de membre LOCK.lockinterruptily (); Essayez {// La file d'attente est vide while (count == 0) {// nanos <= 0 signifie que le temps d'attente maximum est arrivé, donc il n'est plus nécessaire d'attendre, retourne null. if (nanos <= 0) renvoie null; // Appelez la méthode NotEmpty.Awaitnanos (Nanos) pour faire attendre le fil du fil du programme et définir l'heure du délai d'expiration. nanos = nompy.awaitnanos (nanos); } // Appelez la méthode DeQueue pour retourner l'élément d'en-tête de liste return dequeue (); } enfin {lock.unlock (); }}Tout comme le processus de méthode Take (), il est simplement appelé la méthode Awaitnanos (nanos) pour faire attendre le fil actuel et définir le temps d'attente.
5. Méthodes pour voir les éléments
Méthodes 5.1 élément () et peek ()
// Appelez la méthode dans la classe Parent AbstractQueue. public e element () {e x = peek (); if (x! = null) return x; Sinon, jetez un nouveau NosucheMelementExement (); } // Voir les éléments d'en-tête de file d'attente public e peek () {final reentrantlock lock = this.lock; // Utilisez le verrouillage pour garantir que la modification multi-threadded des attributs de membre Lock.LOCK (); essayez {// renvoie l'élément de l'en-tête de file d'attente actuel return itemAt (takeIndex); // null lorsque la file d'attente est vide} enfin {lock.unlock (); }}Vi. Autres méthodes importantes
6.1 Méthodes d'observation et de déshabitation
// Insérez l'élément x dans la queue de la file d'attente privée void enque (e x) {// Assert Lock.GetholdCount () == 1; // affirme les éléments [putIndEx] == null; // L'élément de position actuel PutIndEx doit être un objet final nul [] items = this.items; éléments [puttindex] = x; // Si putIndEx est égal à items.length, puis réinitialisez putIndEx à 0 if (++ putIndex == items.length) putIndEx = 0; // Ajouter un compte ++ au nombre de files d'attente; // Parce qu'un élément est inséré, la file d'attente actuelle n'est certainement pas vide. Réveillez ensuite un fil en attente sous la condition de notempty NotEmpty.Signal (); } // Supprimer l'élément de l'en-tête de file d'attente et le renvoyer privé e deQueue () {// Assert Lock.GetholdCount () == 1; // affirme les éléments [TakeIndex]! = null; objet final [] items = this.items; // Obtenez l'élément de l'en-tête de file d'attente actuel @SuppressWarnings ("Unchecked") e x = (e) items [TakeIndex]; // Définissez la position de l'en-tête de file d'attente actuelle sur les éléments nuls [TakeIndex] = null; if (++ TakeIndex == items.length) TakeIndex = 0; // moins le nombre de files d'attente par un compte -; if (itrs! = null) iTrs.ElementDequeUeEd (); // Parce qu'un élément est supprimé, la file d'attente n'est certainement pas satisfaite, alors réveillez-vous un fil en attente sous la condition notable notfull.signal (); retour x; }Ces deux méthodes représentent, l'insertion des éléments dans et la suppression des éléments de la file d'attente, respectivement. Et ils veulent réveiller le fil d'attente. Après avoir inséré un élément, la file d'attente ne doit pas être vide, de sorte que le fil qui attend sous la condition de note doit être éveillé. Après avoir supprimé l'élément, la file d'attente doit être insatisfaite, de sorte que le fil qui attend dans la condition notable doit être éveillé.
6.2 Supprimer (objet O) Méthode
// Supprimer l'élément objet O dans la file d'attente, et supprimer au plus un booléen public retire (objet o) {if (o == null) return false; objet final [] items = this.items; // Utilisez le verrouillage pour garantir la sécurité de la modification multi-thread des attributs de membres Lock RentrantLock final = this.lock; lock.lock (); Essayez {// Supprimer uniquement lorsqu'il y a une valeur dans la file d'attente. if (count> 0) {// la position suivante à la fin de la file d'attente final int putIndEx = this.putindex; // la position de l'en-tête de file d'attente int i = TakeIndex; faire {// L'élément de position actuel est le même que l'élément supprimé if (o.equals (items [i])) {// supprimer l'élément de position I Removeat (i); // RETOUR Vrai Return True; } if (++ i == items.length) i = 0; // lorsque i == putIndEx signifie que tous les éléments ont été traversés} while (i! = PutIndEx); } return false; } enfin {lock.unlock (); }} Supprimez l'objet spécifié O de la file d'attente, vous devez ensuite traverser la file d'attente et supprimer le premier élément qui est le même que l'objet o. S'il n'y a pas d'élément d'objet O dans la file d'attente, retourne false pour supprimer l'échec.
Voici deux points à noter:
Comment traverser une file d'attente consiste à traverser la tête de la file d'attente à la fin de la file d'attente. Cela dépend des deux variables qui prennent en index et puttindex.
Pourquoi objet [] items = this.items; Ce code n'est pas placé dans le bloc de code de verrouillage de verrouillage synchrone. Les éléments sont des variables membres. Lorsqu'il y a tant de fils, il n'y aura pas de problèmes de concurrence?
En effet, les éléments sont des variables de référence, pas les types de données de base, et nos opérations d'insertion et de suppression sur les files d'attente sont toutes pour ce tableau d'élément, et la référence au tableau n'est pas modifiée. Par conséquent, dans le code de verrouillage, les éléments apporteront les dernières modifications par d'autres threads. Mais si le int putIndex = this.putindex; La méthode verrouille le bloc de code à l'extérieur, un problème se produira.
Méthode de suppression (Final int removeIndex)
// Supprime l'élément dans la file d'attente de la position de la position de survalide // Affirmer les éléments [devoieIndex]! = null; // Affirmez à removeIndex> = 0 && devoieIndex <items.length; objet final [] items = this.items; // Cela signifie qu'il est beaucoup plus facile de supprimer l'élément en tant qu'en-tête de liste, ce qui est similaire au processus de méthode de Dequeue if (retireIndex == TakeIndex) {// Supprimez l'élément dans les éléments de position de SupporIndex [TakeIndex] = NULL; // Lorsque la fin du tableau, vous devez accéder à la position de l'en-tête du tableau si (++ TakeIndex == items.length) TakeIndex = 0; // moins le nombre de files d'attente par un compte -; if (itrs! = null) iTrs.ElementDequeUeEd (); } else {// Un "intérieur" supprime final int putIndEx = this.pudIndex; for (int i =vovIndex ;;) {int next = i + 1; if (next == items.length) next = 0; // La fin de la file d'attente n'a pas encore atteint la fin de la file d'attente, alors l'élément de la position suivante est écrasé par l'élément dans la position précédente si (suivant! = PutIndex) {items [i] = items [Suivant]; i = suivant; } else {// Définissez l'élément de queue des éléments null de file d'attente [i] = null; // Réinitialise la valeur de putIndex this.putindex = i; casser; }} // diminuer le nombre de files d'attente par le comte--; if (itrs! = null) itrs.reMovedAt (retireIndex); } // Parce qu'un élément est supprimé, la file d'attente n'est certainement pas satisfaite, alors réveillez-vous un fil en attente sous la condition notable notfull.signal (); }Supprimer les éléments à l'emplacement spécifié dans la file d'attente. Il convient de noter que le tableau après la suppression peut toujours maintenir la forme de file d'attente, qui est divisée en deux situations:
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.