Защищенная очередь для потоков без использования синхронных

Question

Я должен создать программу, которая, учитывая число N потоков, эти потоки могут вставлять или удалять элемент из очереди, но есть условия для доступа потоков к очереди:

• если только один поток попытается вставить или удалить элемент, он сможет;
• Если два или более потока пытаются одновременно, один сможет, а следующий выполнит свои операции, когда закончится первый.

Я сделал это с помощью синхронизированных блоков, так же, как что:

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; 
    } 

} 

вводной пустота проста, она просто зацикливается в то время как вставки или удаляют элементы.

Мой вопрос в том, как я могу следовать этим условиям без использования синхронизированного?

Как можно гарантировать взаимное исключение без синхронизированных блоков?

EDIT: Я не могу использовать вещи, подобные синхронизированные (так же, как замки)

Answer 1

Нет, и да.

Для этого вам необходимо использовать некоторую форму синхронизации. Нет никакого способа сделать это самостоятельно.

Однако в пакете java.util.concurrent есть классы, которые обеспечивают точно такое поведение, которое вам нужно, и выполняйте его, максимально минимизируя блокировку и стоимость синхронизации.

Например, LinkedBlockingQueue. https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingQueue.html

Если вы действительно хотите понять, как работает этот материал, вы также должны прочитать о неблокирующих алгоритмах. Страница wiki - хорошее начало. В общем, многие очень умные люди, которые точно знают, что они делают, работали над параллельным пакетом. Нить трудно понять.

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