Secure Queue for Threads without using Synchronized

Question

I gotta create a program that, given a number N of threads, these threads can Insert or Remove an element from a queue, but there are conditions for the threads to access the queue:

• if only one thread try to insert or remove an element, it will be able to;
• if two or more threads are trying at the same time, one will be able to, and the next one will execute its operations when the first one finishes.

I made it using synchronized blocks, just like that:

import java.util.ArrayList;
import java.util.Random;

public class EditorThread extends Thread {

    static int N = 10; // number of threads
    static queue Q = new queue(); // shared queue
    private int number; //number of the thread

    public EditorThread(int n) {
        number = n;
    }

    @Override
    public void run() {
        Random r = new Random();

        while (true) {
            int t = r.nextInt(2);
            if (t == 1) {
                int value = Q.get();
                if (value == -1) {
                    System.out.println("The Thread " + number + " couldnt get any element (empty queue)");
                }

                else {
                    System.out.println("The Thread " + number + " got the element " + value );
                }
            }

            else {
                int n = r.nextInt(100);
                Q.put(n);
                System.out.println("The Thread " + number + " inserted the element " + n);
            }

        }

    }

    public static void main(String[] args) {

        for (int i = 0; i < N; i++) {
            Thread t = new EditorThread(i);
            t.start();
        }

    }

}

class queue {
    node head;
    node tail;

    queue() {
        head = tail = null;
    }

    public synchronized int get() {
        if (head == null)
            return -1;
        int r = head.value;
        if (head != tail)
            head = head.next;
        else
            head = tail = null;
        return r;
    }

    public synchronized void put(int i) {
        node n = new node(i);
        if (head == null)
            head = tail = n;
        else {
            tail.next = n;
            tail = n;
        }
    }

}

class node {

    int value;
    node next;

    public node(int value) {
        this.value = value;
    }

}

the run void is simple, it just loops forever while inserts or removes elements.

My question is, how can I follow that conditions without using synchronized?

How is it possible to guarantee mutual exclusion without the synchronized blocks?

EDIT: I cannot use things similar to synchronized (just like locks)

Answer 1

No, and yes.

Fundamentally you need to use some form of synchronization to do this. There is no way to do it yourself without.

However there are classes in the java.util.concurrent package that provide exactly the sort of behaviour you need and do it while minimizing locking and the cost of synchronization as much as possible.

For example LinkedBlockingQueue. https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingQueue.html

If you really want to understand how this stuff works though you should also read up on Non Blocking Algorithms. The wiki page is a good start. In general a lot of very smart people who know exactly what they are doing have worked on the concurrent package though. Threading is hard to get right.

https://en.wikipedia.org/wiki/Non-blocking_algorithm