En el capítulo anterior, presentamos el bloqueo de la cola de bloqueo. A continuación presentamos su clase de implementación de matriz de implementación comúnmente utilizada.
1. Use matrices para implementar colas
Debido a los requisitos especiales de la estructura de datos de la cola, es naturalmente adecuado para implementarse en forma de una lista vinculada. Se utilizan dos variables para registrar el encabezado y el final de la lista vinculada respectivamente. Al eliminar o insertar la cola, simplemente cambie el encabezado o el final de la lista vinculada. Además, la lista vinculada está vinculada de manera de referencia, por lo que su capacidad es casi ilimitada.
Entonces, cómo usar matrices para implementar colas, necesitamos cuatro variables: matriz de objeto [] para almacenar elementos en la cola, la cola y el tailIndex registran la cabeza y la cola de la cola, y cuente registrar el número de colas.
Una manera muy inteligente se usa aquí. Sabemos que cuando se inserta un elemento en la cola, ocupa una posición en la matriz. Cuando se elimina un elemento, la posición de la matriz es realmente gratuita, lo que indica que se puede insertar un nuevo elemento en esta posición.
Entonces, antes de insertar un nuevo elemento, debemos verificar si la cola está llena y antes de eliminar el elemento, debemos verificar si la cola está vacía.
2. Variables de miembro importantes en ArrayBlokingqueue
/ ** Almacene los elementos en la cola*/ objeto final [] elementos; / ** La posición de la cabeza de cola*/ int TakeIndex; / ** La posición de la cola de cola*/ int putIndex; / ** El número de elementos en la cola actual*/ int count; / ** Se utiliza para garantizar la seguridad de las variables compartidas de múltiples subprocesos*/ Bloqueo de reentrantlock final; / ** Cuando la cola está vacía, se llamará al método de espera de notempty para que el hilo actual espera*/ condición final privada notaficada; / ** Cuando la cola está llena, se llamará al método de espera de Notfull, lo que hace que el hilo actual espere*/ Condición final privada notfull;
Hay más variables de bloqueo, notable y notable para implementar condiciones de seguridad de múltiples subprocesos y esperanza de hilos. ¿Cómo operan?
2.1 El papel del bloqueo
Debido a que ArrayBlockingqueue funciona en múltiples hilos, al modificar las variables de los miembros como elementos, TakeIndex, PutIndex y Count, se deben considerar problemas de seguridad de múltiples subprocesos. Por lo tanto, el bloqueo exclusivo de bloqueo se usa aquí para garantizar la seguridad de las operaciones concurrentes.
2.2 El papel de Notempty and Notfull
Debido a que se deben implementar las colas de bloqueo, cuando la cola está vacía o la cola está llena, la operación de lectura o inserción de la cola debe esperar. Así que pensamos en el objeto de condición bajo el marco de concurrencia y lo usamos para controlarlo.
En AQS, presentamos el papel de esta clase:
3. Agregar método de elemento
3.1 Agregar (e e) y ofrecer (e e) métodos:
// Llame al método en la clase principal de Abstractqueue. public boolean add (e e) {// implement if (oferta (e)) return true; de lo contrario, arroje nuevo IlegalStateException ("cola llena"); } // Agregar nuevo elemento al final de la cola. Return true significa que la adición es exitosa, falso significa que la adición falló y no se presenta una excepción de la oferta pública booleana (e e) {checkNotNull (e); LOQUERA DE REENTRANTLOCHLACT FINAL = this.lock; // Use el bloqueo para garantizar que la modificación multiproceso de los atributos del miembro Lock.lock (); Pruebe {// La cola está completa y la adición de elementos falla, devuelve falso. if (count == items.length) return false; else {// llame al método Enqueue para insertar el elemento en la cola enqueue (e); devolver verdadero; }} finalmente {Lock.unlock (); }}El método Agregar se implementa llamando al método de oferta. En el método de oferta, es necesario determinar primero si la cola está llena. Si está lleno, devolverá directamente falso sin bloquear el hilo actual. Si no está satisfecho, llame al método Enqueue para insertar el elemento en la cola.
Nota: Uso de Lock.Lock () aquí asegura que solo un subproceso modifique las variables de los miembros al mismo tiempo para evitar problemas de operación concurrentes. Aunque también bloqueará el hilo actual, no es una espera condicional, es solo porque el bloqueo está sostenido por otros hilos y el tiempo de operación del método en ArrayBlockingqueue no es largo, lo que es equivalente a no bloquear el hilo.
3.2 Método Put
// Agregue un nuevo elemento al final de la cola. Si la cola está llena, el hilo actual esperará. Respuesta a la excepción de interrupción El anuncio public Put (E E) lanza interruptedException {checkNotNull (e); LOQUERA DE REENTRANTLOCHLACT FINAL = this.lock; // Use el bloqueo para garantizar que los múltiples subconjuntos modifiquen la seguridad de los atributos del miembro bloque.lockInterruptable (); Pruebe {// si la cola está llena, llame al método notoful.await () para dejar que el hilo actual espere hasta que la cola no esté llena mientras (count == items.length) notaqu.await (); // llame al método Enqueue para insertar el elemento en la cola Enqueue (e); } Finalmente {Lock.unlock (); }}El proceso general del método de oferta es el mismo que el método de oferta. Sin embargo, cuando la cola está llena, se llamará al método NotfulL.Await () para hacer el bloque de subprocesos actual y esperar hasta que la cola sea eliminada por otros hilos. Cuando la cola no está satisfecha, el hilo de espera se despertará.
3.3 OFERTA (E E, LARGO TIEOUT, TIMEUNIT UNIT) Método
/*** Agregue un nuevo elemento al final de la cola. Si no hay espacio disponible en la cola, el hilo actual esperará. * Si el tiempo de espera excede el tiempo de espera, entonces se devuelve el falso, lo que indica que la adición falló*/ oferta pública booleana (e e, tiempo de espera largo, unidad de tiempo de tiempo) arroja interruptedException {checkNotNull (e); // Calcule el valor de tiempo del total de Nanos Long Nanos largos de nanos largos = unit.tonanos (tiempo de espera); LOQUERA DE REENTRANTLOCHLACT FINAL = this.lock; // Use el bloqueo para garantizar que la modificación múltiple de los atributos del miembro Lock.LockInterruptable (); Pruebe {// La cola está llena mientras (count == items.length) {// nanos <= 0 significa que ha llegado el tiempo de espera máximo, por lo que no hay necesidad de esperar más. Devolver falso, lo que indica que la adición falló. if (nanos <= 0) return false; // Llamar al método Notfull.Awaitnanos (Nanos), el tiempo de tiempo de espera de Nanos se despertará automáticamente. // Si se despierta de antemano, entonces el tiempo restante se devuelve nanos = notfull.awaitnanos (nanos); } // llame al método Enqueue para insertar el elemento en la cola Enqueue (e); devolver verdadero; } Finalmente {Lock.unlock (); }}El método de flujo general de PUT es el mismo que el método PUT, solo está llamando al método Notfull.Awaitnanos (NANOS) para que el hilo actual espere y establezca el tiempo de espera.
4. Método del elemento eliminar
4.1 Métodos eliminar () y encuestar ():
// Llame al método en la clase principal de Abstractqueue. public e remove () {// Implementación llamando a la encuesta e x = encuesta (); if (x! = null) return x; else Thing New NosuchelementException (); } // Elimine el primer elemento de la cola (es decir, el encabezado de la cola) y devuélvalo. Si la cola está vacía, no lanza una excepción, pero devuelve nulo. public e enchufe () {fin final reentrantlock bloqueo = this.lock; // Use el bloqueo para garantizar que la modificación multiproceso de los atributos del miembro Lock.lock (); Pruebe {// if count == 0 y la lista está vacía, return null. De lo contrario, llame al método Dequeue para devolver el elemento de encabezado de la lista (Count == 0)? nulo: dequeue (); } Finalmente {Lock.unlock (); }}El método de eliminación se implementa llamando al método Poll (). En el método Poll (), si la lista está vacía, devuelve NULL, de lo contrario, se llama al método Dequeue para devolver el elemento de encabezado de la lista.
4.2 Take () Método
/*** Regrese y elimine el primer elemento de la cola. Si la cola está vacía, el hilo delantero esperará. Respuesta Excepción de interrupción*/ public e Take () lanza interruptedException {final de reentrantLock Lock = this.lock; // Use el bloqueo para garantizar que los múltiples subconjuntos modifiquen la seguridad de los atributos del miembro bloque.lockInterruptable (); Pruebe {// Si la cola está vacía, llame al método Notempty.AWait () para dejar que el hilo actual espere. // Hasta que otro hilo inserta elementos en la cola, el hilo se despertará. while (Count == 0) Notempty.Await (); // llame al método dequeue para devolver el elemento del encabezado de lista return dequeue (); } Finalmente {Lock.unlock (); }}Cuando el método Take () está vacío, el hilo actual debe esperar hasta que otro hilo inserta un nuevo elemento en la cola, y el hilo se despertará.
4.3 Método de encuesta (tiempo de espera, unidad de tiempo de tiempo de tiempo de tiempo
/*** Regrese y elimine el primer elemento de la cola. Si la cola está vacía, el hilo delantero esperará. * Si el tiempo de espera excede el tiempo de espera, entonces se devuelve el falso para indicar que el elemento está fallido*/ Public E Poll (Tiempo de tiempo largo, unidad de tiempo de tiempo) arroja interruptedException {// Calcule el valor máximo de tiempo de espera en Nanos Long Nanos = unit.tonanos (tiempo de espera); LOQUERA DE REENTRANTLOCHLACT FINAL = this.lock; // Use el bloqueo para garantizar que la modificación multiproceso de los atributos del miembro Lock.LockInterruption (); Pruebe {// La cola está vacía mientras (count == 0) {// nanos <= 0 significa que ha llegado el tiempo de espera máximo, por lo que no hay necesidad de esperar más, devolver nulo. if (nanos <= 0) return null; // Llame al método Notempty.Awaitnanos (Nanos) para que el hilo de horario espere y establezca el tiempo de tiempo de espera. nanos = notempty.awaitnanos (nanos); } // llame al método dequeue para devolver el elemento del encabezado de lista return dequeue (); } Finalmente {Lock.unlock (); }}Al igual que el proceso del método Take (), se solo llama el método Awaitnanos (NANOS) para que el hilo actual espere y establezca el tiempo de espera.
5. Métodos para ver elementos
5.1 Métodos de elemento () y peek ()
// Llame al método en la clase principal de Abstractqueue. public e element () {e x = peek (); if (x! = null) return x; else Thing New NosuchelementException (); } // Ver elementos de encabezado de cola public e peek () {final de reentrantlock bloqueo = this.lock; // Use el bloqueo para garantizar que la modificación multiproceso de los atributos del miembro Lock.lock (); Pruebe {// devuelve el elemento del encabezado actual de retorno del encabezado de la cola itemat (TakeIndex); // NULL cuando la cola está vacía} finalmente {Lock.unlock (); }}VI. Otros métodos importantes
6.1 Métodos de enqueue y dequeue
// Inserte el elemento x en la cola de la cola privada vacía enqueue (e x) {// afirmar lock.getholdCount () == 1; // Afirmar elementos [putIndex] == null; // El elemento de posición PutIndex actual debe ser objeto final nulo [] elementos = this.items; elementos [putIndex] = x; // Si PutIndex es igual a elementos.length, luego restablezca putIndex a 0 if (++ putIndex == items.length) putIndex = 0; // Agregar un recuento ++ al número de colas; // Debido a que se inserta un elemento, la cola actual definitivamente no está vacía. Luego despierta un hilo esperando bajo una condición notable no notable.signal (); } // Eliminar el elemento del encabezado de cola y devolverlo privado e dequeue () {// afirmar lock.getholdCount () == 1; // Afirmar los elementos [TakeIndex]! = NULL; objeto final [] elementos = this.items; // Obtenga el elemento del encabezado de cola actual @suppleswarnings ("sin control") e x = (e) elementos [takeIndex]; // Establezca la posición del encabezado de cola actual en elementos nulos [TakeIndex] = null; if (++ takeIndex == items.length) takeIndex = 0; // menos el número de colas por un recuento; if (itrs! = null) ITrs.ElementDequeueD (); // Debido a que se elimina un elemento, la cola definitivamente no está satisfecha, así que despierta un hilo que espera bajo la condición notable notfull.signal (); regresar x; }Estos dos métodos representan, insertando elementos y eliminando elementos de la cola, respectivamente. Y quieren despertar el hilo de espera. Después de insertar un elemento, la cola no debe estar vacía, por lo que el hilo que espera debajo de la condición notable debe despertarse. Después de eliminar el elemento, la cola debe estar insatisfecha, por lo que el hilo que espera bajo la condición notable debe despertarse.
6.2 Eliminar (Objeto O) Método
// Eliminar el elemento objeto o en la cola, y eliminar como máximo una eliminación pública booleana (objeto o) {if (o == null) return false; objeto final [] elementos = this.items; // Use el bloqueo para garantizar la seguridad de la modificación múltiple de los atributos del miembro de los atributos finales de reentrantlock bloqueo = this.lock; Lock.lock (); Pruebe {// Eliminar solo cuando haya un valor en la cola. if (count> 0) {// La siguiente posición al final de la cola final int putIndex = this.putindex; // La posición del encabezado de cola int i = TakeIndex; do {// El elemento de posición actual es el mismo que el elemento eliminado if (O.Equals (elementos [i])) {// Eliminar el elemento de posición I Eliminar (i); // return verdadero return verdadero; } if (++ i == items.length) i = 0; // Cuando i == putIndex significa que todos los elementos han sido atravesados} mientras (i! = PutIndex); } return false; } Finalmente {Lock.unlock (); }} Elimine el objeto especificado O de la cola, luego debe atravesar la cola y eliminar el primer elemento que es el mismo que el objeto o. Si no hay objeto o elemento en la cola, entonces devuelve falso a eliminar fallado.
Aquí hay dos puntos a tener en cuenta:
Cómo atravesar una cola es atravesar la cabeza de la cola hasta el final de la cola. Depende de las dos variables que TakeIndex y PutIndex.
¿Por qué es objeto [] items = this.Items; Este código no se coloca en el bloque de código de bloqueo de bloqueo sincrónico. Los elementos son variables miembros. Cuando hay tantos hilos, ¿no habrá problemas de concurrencia?
Esto se debe a que los elementos son variables de referencia, no tipos de datos básicos, y nuestras operaciones de inserción y eliminación en colas son todas para esta matriz de elementos, y la referencia a la matriz no se cambia. Por lo tanto, en el código de bloqueo, los elementos obtendrán las últimas modificaciones por otros hilos. Pero si int putindex = this.putindex; El método bloquea el bloque de código afuera, se producirá un problema.
Método de eliminación (final int removeDindex)
// Eliminar el elemento en la cola RemoutIndex Position Void Removeat (final int removeDex) {// afirmar Lock.getholdCount () == 1; // Afirmar los elementos [RemoveDindex]! = NULL; // afirmar removeDindex> = 0 && removeDindex <items.length; objeto final [] elementos = this.items; // Significa que es mucho más fácil eliminar el elemento como el encabezado de la lista, que es similar al proceso del método Dequeue si (removeindex == takeIndex) {// Eliminar el elemento en los elementos de posición de removeindex [takeIndex] = null; // Cuando el final de la matriz, debe ir a la posición del encabezado de la matriz si (++ TakeIndex == items.length) TakeIndex = 0; // menos el número de colas por un recuento; if (itrs! = null) ITrs.ElementDequeueD (); } else {// un "Interior" eliminar final int putIndex = this.putindex; for (int i = removeDindex ;;) {int next = i + 1; if (next == items.length) Next = 0; // El final de la cola aún no ha alcanzado el final de la cola, entonces el elemento en la siguiente posición está sobrescribido por el elemento en la posición anterior if (siguiente! = PutIndex) {elementos [i] = elementos [next]; i = Siguiente; } else {// Establezca el elemento de cola de los elementos nulos de cola [i] = null; // restablecer el valor de putIndex this.putindex = i; romper; }} // Disminución del número de colas por recuento--; if (itrs! = null) ITRS.REMOVEDAT (eliminarindex); } // Debido a que se elimina un elemento, la cola definitivamente no está satisfecha, así que despierta un hilo que espera bajo la condición notable notfull.signal (); }Eliminar elementos en la ubicación especificada en la cola. Cabe señalar que la matriz después de la eliminación aún puede mantener la forma de cola, que se divide en dos situaciones:
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.