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)

Is there a good reason not to use a [`BlockingQueue`](https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html) implementation like `LinkedBlockingQueue`? These are, by contract, thread safe. — Andy Turner, Dec 07 '15 at 16:08
whateever you implement is going to be a recreation of synchronized method mate(to some extent), you may want to read this nice question: http://stackoverflow.com/questions/9749746/what-is-the-difference-of-atomic-volatile-synchronize — nafas, Dec 07 '15 at 16:16
I cannot use atomic, but its possible to do some tricks, like making the threads static, so one thread can stop another ( but I couldn't use this safely ) — Daniel, Dec 07 '15 at 16:19
@nafas, Not if he implements a non-blocking queue. A thread-safe, non-blocking queue can be implemented without locks. https://en.wikipedia.org/wiki/Non-blocking_algorithm — Solomon Slow, Dec 07 '15 at 16:47
You can't guarantee mutual exclusion without locks. "locking" and "mutual exclusion" both mean the same thing. You _can_ create a thread-safe queue without mutual exclusion/locking, but it will not be a _blocking_ queue. Google for "wait free algorithm" and "lock free algorithm." — Solomon Slow, Dec 07 '15 at 16:49

score 0 · Answer 1 · answered Dec 07 '15 at 17:05

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

Secure Queue for Threads without using Synchronized

1 Answers1