trjhtr

Just wrote an Evicting Queue implementation, as an ordinary Linked List working under the hood, in Java; which, I hope, I've made thread safe, could you review?

Code:

package com.threadsafedatastructs.EvictingQueue;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

public class EvictingQueue<T> 
private final int MAX_SIZE;
private List<T> data = new LinkedList<>();
private volatile T o;
private volatile ArrayDeque<T> dequeO;

public EvictingQueue(int _maxSize) 
 this.MAX_SIZE = _maxSize;


public synchronized boolean isEmpty() 
 return data.isEmpty();


public synchronized int size() 
 return data.size();


public T head() /* Peek the first element */
 return this.data.get(0);


public T tail() /* Peek the last element */
 return this.data.get(this.data.size() - 1);


public synchronized T popFirst() 
 if (!this.data.isEmpty()) 
 o = data.remove(0);
 notifyAll();
 return o;
 
 throw new NoSuchElementException();


public synchronized T popLast() 
 if (!this.data.isEmpty()) 
 o = data.remove(data.size() - 1);
 notifyAll();
 return o;
 
 throw new NoSuchElementException();


public synchronized boolean push(T item) 
 if (this.data.size() <= MAX_SIZE) 
 if (this.data.size() == MAX_SIZE) 
 this.popFirst();
 this.data.add(0, item);
 notifyAll();
 return true;
 
 this.data.add(0, item);
 notifyAll();
 return true;
 
 throw new IndexOutOfBoundsException();


public synchronized boolean append(T item) 
 if (this.data.size() <= MAX_SIZE) 
 if (this.data.size() == MAX_SIZE) 
 this.popFirst();
 boolean obj = this.data.add(item);
 notifyAll();
 return obj;
 
 boolean obj = this.data.add(item);
 notifyAll();
 return obj;
 
 throw new IndexOutOfBoundsException();


public synchronized ArrayDeque<T> pollAll() 
 dequeO = new ArrayDeque<>(this.data);
 this.data.clear();
 notifyAll();
 return dequeO;


@Override
public String toString() 
 return data.toString();


public int getMAX_SIZE() 
 return MAX_SIZE;

I'm interested in that volatile variables, are they necessary? Or maybe I should add more? notifyAll() do those synchronized methods need this call?

Also, this: if (this.data.size() <= MAX_SIZE) condition seems redundant, because list data shouldn't be longer than 100 anyway; but this is the simplest way for me to limit Linked List length in Java (also, may help with tests).

1. those volatile variables: not only do they seem redundant, they actually breach thread safety. volatile variables are used when you actually want the variable to be accessed by multiple threads (for example, when you want one thread to set a boolean and then have another read that variable). as far as I could detect, the two variables can be replaced by local ones.




2. those notifyAll() calls: they are mostly redundant. the method is only useful if a client thread has called wait(). that is usually the case if the queue is empty and a client wants to block until a new item has ben added. if the list is not empty, the client usually pops an item and goes about processing it. so you need to understand when clients will want to wait for an event to happen and get notified about it. Secondly, calling notifyAll() only makes sense if you release the lock immediately after the notification. calling notifyAll() in a loop without releasing the lock will not do anything.




3. as an exercise, this solution will work. However, it is not efficient. synchronizing all the methods mean that any access to the queue will prevent all other access. for example, if one thread calls isEmpty() it has locked the entire queue. you may think that isEmpty() is such a small method, but what if the thread just entered the wethod and got a context switch from the OS. it can wait for 2-3 milliseconds before releasing the lock (and that is a long time in the computation universe). so in order to be more efficient, you need better granularity on the scope of the locking. For example, set a boolean if the queue is in the process of being modified and only at these times lock the reading methods. and you can get more efficient with more sophisticated (and complex) mechanisms (like locking only part of the queue this is being modified etc)




4. ALL_CAPITAL names in Java (and other languages), are used for constant variables, not for those that hold state. (i.e. recevied from arguments). even if they are immutable.

EDIT

Regarding the question in the comment:

What happen when isEmpty and size don't be synchronized? Do we
care?

well, it can be that one thread will ask isEmpty at the same time that another is pushing an item into the queue. that is why I believe that in the body of the reading methods you need to create a synchronized block that is dependant on a boolean that is set when a writing method is called.

Another advice I can give you is to have a look at java.util.concurrent package. it contains several lock mechanisms that are more powerful and flexible than synchronized blocks. For example, ReentrantLock has the following text in its documentation:

A reentrant mutual exclusion Lock with the same basic behavior and
semantics as the implicit monitor lock accessed using synchronized
methods and statements, but with extended capabilities.

there is a useful example in this topic it shows how you can use a ReentrantLock instance across methods, something that may be useful in your case.

lastly, have a look at java.util.concurrent.ConcurrentLinkedQueue which seems to fit at least some of your requirements. if you are doind this asan exercise, then take a look at the class' source code and see hoe they dealt with thread safety issues.