不使用同步的线程的安全队列

Question

我要创建一个程序，给定N个线程，这些线程可以在队列中插入或删除一个元素，但是线程访问队列是有条件的:

null

我用同步块做的，就像这样:

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

}

run void很简单，它只是在插入或删除元素时永远循环。

我的问题是，在不使用synchronized的情况下，我如何遵循那个条件？

没有同步块，怎么可能保证互斥呢？

编辑：我不能使用类似于同步的东西（就像锁一样）

Answer 1

不，是的。

基本上，你需要使用某种形式的同步来做到这一点。没有就没有办法自己做。

然而，在< code > Java . util . concurrent 包中有一些类提供了您所需要的行为，并且在尽可能减少锁定和同步开销的同时做到了这一点。

例如< code>LinkedBlockingQueue。https://docs . Oracle . com/html" target="_blank">javase/7/docs/API/Java/util/concurrent/linkedblockingqueue . html

如果你真的想理解这个东西是如何工作的，你也应该阅读非阻塞算法。维基页面是一个良好的开端。总的来说，很多非常聪明的人知道他们在做什么，但是他们已经在并发包上工作了。穿线很难做对。

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