En el capítulo anterior, explicamos la cola de bloqueo implementada en ArrayBlockingqueue, utilizando el formulario de matriz.
La longitud de la matriz debe determinarse al crear. Si la longitud de la matriz es pequeña, la cola de arraybockingqueue se bloqueará fácilmente. Si la longitud de la matriz es grande, desperdiciará fácilmente la memoria.
La estructura de datos de la cola es naturalmente adecuada para la forma de listas vinculadas, y Linked Blokingqueue es una cola de bloqueo implementada utilizando listas vinculadas.
1. Implementación de la lista vinculada
1.1 Clase interna del nodo
/ *** El nodo de la lista vinculada también se usa para implementar una lista vinculada unidireccional*/ nodo de clase estática <E> {e item; // señala el siguiente nodo del nodo de lista vinculado <E> SIGUIENTE; Nodo (e x) {item = x; }}Hay una variable E que almacena datos, y hay una siguiente referencia variable que apunta al siguiente nodo. Puede implementar la lista unidireccional más simple.
1.2 Cómo implementar la lista de enlaces
/ *** Su siguiente punto al cabezal de cola, y este nodo no almacena datos*/ nodo transitorio <E> CABEZA; / *** nodo de cola de cola*/ nodo transitorio privado <E> last;
Para implementar una lista vinculada, debe haber dos variables, una representa el jefe de la lista vinculada y la otra representa la última de la lista vinculada. Tanto la cabeza como el último se inicializan cuando se crea el objeto LinkedBlockingqueue.
último = head = nuevo nodo <E> (nulo);
Tenga en cuenta que se usa un pequeño truco aquí. El nodo principal de la lista vinculada no almacena datos. El siguiente nodo apunta realmente para almacenar los primeros datos en la lista vinculada. El último al final de la lista vinculada de hecho almacena los últimos datos en la lista vinculada.
1.3 Insertar y eliminar nodos
/ *** Inserte el nodo a la cola de la cola*/ private void enqueue (nodo <e> nodo) {// afirmar putlock.isheldbycurrentThread (); // El hilo actual debe haber obtenido el bloqueo de Putlock // punto la siguiente referencia del nodo de cola de cola original al nuevo nodo del nodo, y luego establecer el nodo del nodo en el nodo de cola de la cola Última // Esto realiza el nodo insertado en la cola de la cola last = last.next = node; }Es muy simple insertar un nodo al final de la lista vinculada. Apunte el siguiente nodo de la cola original al final del nodo del nuevo nodo, y luego asigne el nodo del nuevo nodo al último nodo al final de la cola. Esto permite insertar un nuevo nodo.
// elimina el nodo del cabezal de la cola y devuelve los datos del nodo eliminados privados e dequeue () {// afirmar takelock.isheldbycurrentThread (); // El hilo actual debe haber obtenido el bloqueo de Takelock // afirmar head.item == null; Nodo <E> h = cabeza; // Los datos del primer elemento en la cola se almacenan en el primer nodo del nodo <E> primero = H.Next; H.Next = H; // Ayuda GC // Configurar el nuevo valor de la cabeza es equivalente a eliminar el primer nodo. Porque el nodo principal en sí no almacena datos de datos = primero; // Los datos del encabezado de cola e x = first.item; // elimina los datos originales primero.item = null; regresar x; }Tenga en cuenta que la cabeza no es el encabezado, su siguiente punto al encabezado, por lo que es muy simple eliminar el encabezado, que es asignar cabezal.
Al eliminar, preste atención a la situación en la que la lista vinculada está vacía. El valor de Head.Next se agrega utilizando el método Enqueue. Cuando head.next == Dast, significa que el último elemento ha sido eliminado. Cuando head.next == NULL, no se puede eliminar porque la lista vinculada ya está vacía. No hay juicio aquí porque el juicio se ha hecho en el lugar donde se llama el método de dequista.
2. Reentrantlock y condición de reentrante de bloqueo sincrónico
Debido a que la cola de bloqueo debe bloquearse y esperar cuando la cola está vacía y la cola está llena, entonces se requieren dos condiciones naturalmente. Para garantizar la seguridad de la concurrencia múltiple, se necesita un bloqueo de sincronización. Esto se ha dicho en ArrayBlockingqueue.
Aquí hablaremos sobre las diferentes cosas sobre Linked Bloquingqueue.
/ ** Bloqueo exclusivo, utilizado para manejar problemas de concurrencia de insertar operaciones de cola, es decir, poner y ofrecer operaciones*/ REENTRANTLOCT FINAL PRIVADO PUTLOCK = new ReentrantLock (); / ** Condición Condición de que la cola no esté satisfecha, se genera por el bloqueo de Putlock*/ condición final privada notfull = putlock.newcondition (); / ** Bloqueo exclusivo, utilizado para manejar problemas de concurrencia de eliminar las operaciones de la cabeza de la cola, es decir, operaciones de toma y encuesta*/ REENTRANTLOCK final privado Takelock = new ReentrantLock (); / ** Condición Condición de que la cola no esté vacía, usa la condición final privada generada por el bloqueo de Takelock*/ Condición final privada Notempty = Takelock.newCondition ();
2.1 Putlock y Takelock
Encontramos dos cerraduras utilizadas:
Según la declaración anterior, puede haber operaciones de insertar y eliminar elementos al mismo tiempo, ¿no habrá ningún problema?
Analicémoslo en detalle. Para las colas, las operaciones se dividen en tres tipos:
Por lo tanto, use el bloqueo de Putlock para mantener la última variable segura y use el bloqueo de Takelock para mantener la variable de cabeza segura.
Para todas las variables de recuento involucradas en el número de elementos en la cola, AtomicInteger se utiliza para garantizar problemas de seguridad de concurrencia.
/ ** El número de elementos en la cola, use la variable AtomiCInTeger aquí para garantizar problemas de seguridad de concurrencia*/ private final AtomicInteger Count = new AtomItInseger ();
2.2 Noto y notable
2.3 Proceso de control
Al insertar un elemento:
Al eliminar elementos:
También tenga en cuenta que la señal y la espera de métodos de condición deben llamarse cuando se adquiere un bloqueo. Por lo tanto, hay métodos SignalTempty y SignalNotFull:
/*** Despierta el hilo esperando bajo la condición notable, es decir, al quitar el encabezado de la cola, el hilo que se encuentra vacío y obligado a esperar. * Tenga en cuenta que para llamar al método de condición de señal, se debe obtener el bloqueo correspondiente, el método Takelock.lock () se llama aquí. * Cuando se inserta un elemento en la cola (es decir, la operación de poner u ofrecer), la cola definitivamente no está vacía, y se llamará a este método. */ private void SignalNotEmpty () {final reentrantlock takelock = this.takelock; takelock.lock (); intente {noTempty.signal (); } finalmente {takelock.unlock (); }} /*** Despierta el hilo esperando debajo de la condición notable, es decir, cuando el elemento se agrega al final de la cola, el hilo que está lleno y obligado a esperar. * Tenga en cuenta que para llamar al método de condición de señal, se debe obtener el bloqueo correspondiente, por lo que el método PutLock.Lock () se llama aquí* Cuando el elemento (es decir, la operación de la encuesta) se elimine en la cola, la cola definitivamente no estará satisfecho y llamará a este método. */ private void SignalNotFull () {final ReentrantLock Putlock = this.putlock; putlock.lock (); intente {notfull.signal (); } finalmente {putlock.unlock (); }}3. Insertar método de elemento
public void put (e e) lanza interruptedException {if (e == null) tirar nueva nullpointerException (); // registrar el número de elementos antes de la operación de inserción int c = -1; // crear un nuevo nodo de nodo <E> nodo = nuevo nodo <E> (e); final reentrantlock putlock = this.putlock; Conteo final AtomicInteger = this.count; putlock.lockInterruptable (); Pruebe {// indique que la cola está llena, luego debe llamar al método de Await noble para hacer que el hilo actual espere mientras (count.get () == Capacidad) {notfull.await (); } // insertar un nuevo elemento enqueue (nodo); // Agregue 1 al número de elementos en la cola actual y devuelva el número de elementos antes de agregar 1. C = count.getAndIrcrement (); // C + 1 <Capacidad significa que la cola no está llena, y el hilo que puede estar esperando la operación de inserción se despierta si (c + 1 <capacidad) nofly.signal (); } finalmente {putlock.unlock (); } // c == 0 significa que la cola está vacía antes de la inserción. Cuando la cola está vacía a un elemento que se coloca, // despierta el hilo esperando la eliminación // evita la adquisición frecuente de los bloqueos de takelock, consuma el rendimiento si (c == 0) SignalNotEmpty (); }Tomando el método Put como ejemplo, el proceso general es el mismo que presentamos anteriormente. Aquí hay un código muy extraño. Cuando se inserta el elemento, si encuentra que la cola no está llena, llame a Notfull.signal () para despertar el hilo esperando la inserción.
Todos están muy confundidos. En términos generales, este método debe colocarse en el elemento Delete (Tome el método de la serie), porque cuando eliminamos un elemento, la cola debe estar infalible, luego llame al método Notfull.signal () para despertar el hilo esperando la inserción.
Esto se hace principalmente aquí porque al llamar al método de señal, el bloqueo correspondiente debe obtenerse primero. El bloqueo utilizado en el método Take Series es Takelock. Si desea llamar al método Notfull.signal (), primero debe obtener el bloqueo de Putlock. Esto hará que el rendimiento disminuya, por lo que se utiliza otro método.
4. Elimine el elemento de encabezado de la cola
public e take () lanza interruptedException {e x; int c = -1; Conteo final AtomicInteger = this.count; Reentrantlock final Takelock = this.takelock; Takelock.lockInterruptable (); Pruebe {// significa que la cola está vacía, entonces debe llamar al método Notempty.Await para hacer que el hilo actual espere mientras (count.get () == 0) {noTempty.aWait (); } // Eliminar el elemento de encabezado de cola y devuélvalo x = dequeue (); // devuelve el número de las colas actuales y luego reste el número de las colas por un c = count.getAndDeCrement (); // c> 1 significa que la cola no está vacía, por lo que despierta el hilo que puede estar esperando la operación de eliminación si (c> 1) notempy.signal (); } finalmente {takelock.unlock (); } /*** C == Capacidad significa que la cola está llena antes de la operación de eliminación. * Despertar el hilo esperando la inserción solo cuando un elemento se elimina de la cola completa* evita la adquisición frecuente de los bloqueos de putlock, consume el rendimiento*/ if (c == capacidad) SignalNotFull (); regresar x; }¿Por qué se llama el método Notempty.signal (), compare nuestra explicación en el método del elemento inserto?
5. Ver elementos de encabezado de cola
// Ver el elemento de encabezado de cola public e peek () {// La cola está vacía, return null if (count.get () == 0) return null; Reentrantlock final Takelock = this.takelock; takelock.lock (); Pruebe {// Obtenga el nodo del nodo de encabezado de cola Primer Nodo <E> First = head.next; // primero == NULL significa que la cola está vacía, devuelve nulo if (primero == null) return null; else // Devuelve el elemento del encabezado de cola return First.Item; } finalmente {takelock.unlock (); }}Vea el elemento de encabezado de cola, que involucra el nodo de cabeza, por lo que se debe usar el bloqueo de Takelock.
VI. Otros métodos importantes
6.1 Eliminar el método (objeto o)
// Eliminar el elemento especificado de la cola o Public Boolean Remete (Object o) {if (o == null) return false; // Debido a que no es para eliminar el elemento de encabezado de la lista, las dos variables cabezales y el último están involucrados, // putlock y takelock deben bloquearse completamente (); Pruebe {// Traver la cola completa, P representa el nodo actual, y el sendero representa el nodo anterior del nodo actual // porque es una lista vinculada de ida, dos nodos deben registrarse para (nodo <e> sendel = head, p = sendel.next; p! = null; sendy = p, p = P.Next) {// Si el elemento especificado se encuentra, luego se encuentra el deje el nodo el nulo de los nulos; sendero = p, p, p = P.Next) {// si el elemento especificado se encuentra, luego se encuentra eleTete el nodo el n conteequeo de los nóloos; (O.Equals (p.item)) {Unlink (p, rastro); devolver verdadero; }} return false; } finalmente {plottyUnlock (); }}Eliminar el elemento especificado de la lista. Debido a que el elemento eliminado no está necesariamente en la cabeza de la lista, puede haber dos variables cabeza y última vez, por lo que debe usar los bloqueos de Putlock y Takelock al mismo tiempo. Debido a que es una lista vinculada unidireccional, se necesita una ruta de variable auxiliar para registrar el nodo anterior para que el nodo actual P se pueda eliminar.
6.2 Método UNLINK (NODO <E> P, NODO <E> TRAIL)
// Eliminar el nodo actual P, y el rastro representa el nodo anterior de P void UNLAINK (nodo <E> P, nodo <E> sendero) {// Establezca los datos del nodo actual en null p.item = null; // Esto elimina el nodo P Trail.next = P.Next; // Si el nodo P es el último último de la cola y se elimina, luego configure el sendero para que dure si (last == p) Last = Trail; // Resta el número de elementos por uno, si la cola original está llena, llame al método notofly.signal () // de hecho, esto se llama directamente sin juicio, porque el bloqueo de putlock debe obtenerse aquí si (count.getAndDeCrement () == Capacidad) notfull.signal (); }Para eliminar un nodo P en la lista vinculada, solo necesita señalar la siguiente ruta de nodo anterior de P al siguiente nodo NEGNO NEGONO P.
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.