Comment puis-je atomiquement "mettre en file d'attente si l'espace libre OU dequeue puis mettre en file d'attente" pour une file/liste Java?

Question

J'ai besoin d'une liste en Java avec une capacité fixe mais qui permette toujours aux threads d'ajouter des éléments au début. S'il est plein, il faut retirer un objet de la fin pour faire de la place. Aucun autre processus ne supprimera les éléments, mais d'autres processus souhaiteront itérer sur les éléments.

Y a-t-il quelque chose dans le JDK qui me permettrait de le faire de manière atomique? Mon plan actuel consiste simplement à utiliser une collection threadsafe existante (par exemple LinkedBlockingQueue) et à la synchroniser davantage lorsque je vérifie la capacité/ajouter/supprimer. Cela fonctionnerait-il aussi?

Merci.

Answer 1

Je travaille dans une ancienne version de Java (oui 1.3, je n'ai pas le choix), donc même si elle est là plus tard dans Javas je ne peux pas l'utiliser. Donc, je codé dans ce sens:

public class Fifo { 
private LinkedList fifoContents = new LinkedList(); 
public synchronized void put(Object element) { 
    if (fifoContents.size() > 100){    
      fifoContents.removeFirst();     
      logger.logWarning("*** Backlog, discarding messaage "); 
    } 
    fifoContents.add (element); 
    return; 
} 

public synchronized Object get() throws NoSuchElementException { 
    return fifoContents.removeFirst(); 
} 
} 

Answer 2

Votre idée fonctionnerait, mais impliquerait de prendre des serrures multiples (voir exemple ci-dessous). Étant donné que vous avez besoin de synchroniser plusieurs opérations lors de l'ajout de données, vous pouvez également envelopper une implémentation LinkedList d'un Queue à pour éviter la surcharge des verrous supplémentaires.

// Create queue with fixed capacity. 
Queue<Item> queue = new LinkedBlockingQueue<Item>(1000); 

... 

// Attempt to add item to queue, removing items if required. 
synchronized(queue) { // First lock 
    while (!queue.offer(item)) { // Second lock 
    queue.take(); // Third lock 
    } 
} 

Answer 3

Vous pourriez être en mesure de sortir avec juste le test/suppression/insertion sans serrures supplémentaires:

class DroppingQueue<E> 
extends ArrayBlockingQueue<E> { 
    public boolean add(E item) { 
     while (! offer(item)) { 
      take(); 
     } 
     return true; 
    } 
} 

Bien que cette méthode ne soit pas synchronisé, add et offer sont encore, de sorte que le pire qui puisse arrive que le thread n ° 1 appelle offer, trouve la file d'attente pleine, le thread n ° 2 fera de même, et les deux supprimeront les éléments, réduisant temporairement le nombre d'éléments à moins que le maximum, avant que les deux threads ajoutent leurs éléments . Cela ne causera probablement pas de problèmes sérieux.

Answer 4

Il n'existe aucune classe de ce type dans JDK. Si vous souhaitez implémenter une telle collection, vous pouvez utiliser array avec des pointeurs tête/queue flottants - puisque vous avez une taille fixe, vous n'avez pas du tout besoin de liste chaînée.