java - 不使用 Synchronized 的安全线程队列

Question

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

• 如果只有一个线程尝试插入或删除元素，它将能够；
• 如果两个或多个线程同时尝试，其中一个可以尝试，下一个线程将在第一个线程完成后执行其操作。

我使用同步块(synchronized block)来实现它，就像这样:

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 block)如何保证互斥？

编辑:我不能使用类似于synchronized的东西(就像锁一样)

Answer 1

不，是的。

从根本上来说，您需要使用某种形式的同步来执行此操作。没有办法自己做。

但是，java.util.concurrent 包中的一些类可以准确提供您所需的行为，并在尽可能减少锁定和同步成本的同时实现这一点。

例如LinkedBlockingQueue。 https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingQueue.html

如果您真的想了解这些东西是如何工作的，那么您还应该阅读非阻塞算法。维基页面是一个好的开始。一般来说，很多非常聪明的人都知道自己在做什么，但他们都在并发包上工作过。线程很难正确执行。

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