Thread Safe LIFO Data Structure Implementations – 线程安全的LIFO数据结构实现

最后修改: 2018年 8月 7日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

In this tutorial, we’ll discuss various options for Thread-safe LIFO Data structure implementations.

在本教程中，我们将讨论线程安全的LIFO数据结构实现的各种选项。

In the LIFO data structure, elements are inserted and retrieved according to the Last-In-First-Out principle. This means the last inserted element is retrieved first.

在LIFO数据结构中，元素的插入和检索是按照后进先出的原则。这意味着最后插入的元素会先被检索到。

In computer science, stack is the term used to refer to such data structure. 

在计算机科学中，stack是指这种数据结构的术语。

A stack is handy to deal with some interesting problems like expression evaluation, implementing undo operations, etc. Since it can be used in concurrent execution environments, we might need to make it thread-safe. 

一个栈可以方便地处理一些有趣的问题，如表达式评估、实现撤销操作等。由于它可以在并发执行环境中使用，我们可能需要让它成为线程安全的。

2. Understanding Stacks

2.了解堆栈

Basically, a Stack must implement the following methods:

基本上，一个Stack必须实现下列方法：

  1. push() – add an element at the top
  2. pop() – fetch and remove the top element
  3. peek() – fetch the element without removing from the underlying container

As discussed before, let’s assume we want a command processing engine.

正如之前所讨论的，我们假设我们想要一个命令处理引擎。

In this system, undoing executed commands is an important feature.

在这个系统中，撤销已执行的命令是一个重要的功能。

In general, all the commands are pushed onto the stack and then undo operation can simply be implemented:

一般来说，所有的命令都被推入堆栈，然后可以简单地实现撤销操作：

  • pop() method to get the last executed command
  • call the undo() method on the popped command object

3. Understanding Thread Safety in Stacks

3.了解堆栈中的线程安全

If a data structure is not thread-safe, when accessed concurrently, it might end up having race conditions.

如果一个数据结构不是线程安全的，在并发访问时，它可能最终会出现竞赛条件。

Race conditions, in a nutshell, occur when the correct execution of code depends on the timing and sequence of threads. This happens mainly if more than one thread shares the data structure and this structure is not designed for this purpose.

简而言之，当代码的正确执行取决于线程的时间和顺序时，就会出现竞赛条件。这主要发生在一个以上的线程共享数据结构，而这个结构不是为此目的而设计的。

Let’s examine a method below from a Java Collection class, ArrayDeque:

让我们看看下面来自Java集合类的一个方法，ArrayDeque。

public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // ... other book-keeping operations removed, for simplicity
    head = (h + 1) & (elements.length - 1);
    return result;
}

To explain the potential race condition in the above code, let us assume two threads executing this code as given in the below sequence:

为了解释上述代码中潜在的竞赛条件，让我们假设有两个线程在执行这段代码，如下面的序列所示。

  • First thread executes the third line: sets the result object with the element at the index ‘head’
  • The second thread executes the third line: sets the result object with the element at the index ‘head’
  • First thread executes the fifth line: resets the index ‘head’ to the next element in the backing array
  • The second thread executes the fifth line: resets the index ‘head’ to the next element in the backing array

Oops! Now, both the executions would return the same result object. 

糟糕!现在，两个执行都会返回同一个结果对象。

To avoid such race conditions, in this case, a thread shouldn’t execute the first line till the other thread finishes resetting the ‘head’ index at the fifth line. In other words, accessing the element at the index ‘head’ and resetting the index ‘head’ should happen atomically for a thread.

为了避免这种竞赛条件，在这种情况下，一个线程不应该执行第一行，直到另一个线程在第五行完成了对 “头 “索引的重设。换句话说，对于一个线程来说，访问索引为 “头 “的元素和重置索引 “头 “应该是原子发生的。

Clearly, in this case, correct execution of code depends on the timing of threads and hence it’s not thread-safe.

显然，在这种情况下，代码的正确执行取决于线程的时间，因此它不是线程安全的。

4. Thread-safe Stacks Using Locks

4.使用锁的线程安全堆栈

In this section, we’ll discuss two possible options for concrete implementations of a thread-safe stack. 

在本节中，我们将讨论线程安全栈的具体实现的两种可能选择。

In particular, we’ll cover the Java Stack and a thread-safe decorated ArrayDeque. 

特别是，我们将介绍Java的Stack和一个线程安全的装饰ArrayDeque。

Both use Locks for mutually exclusive access.

两者都使用Locks进行互斥访问.。

4.1. Using the Java Stack

4.1.使用Java的Stack

Java Collections has a legacy implementation for thread-safe Stack, based on Vector which is basically a synchronized variant of ArrayList.

Java Collections有一个用于线程安全的Stack的传统实现，基于Vector，基本上是ArrayList的同步变体。。

However, the official doc itself suggests considering using ArrayDeque. Hence we won’t get into too much detail.

然而，官方文档本身建议考虑使用ArrayDeque。因此，我们不会讨论太多细节。

Although the Java Stack is thread-safe and straight-forward to use, there are major disadvantages with this class:

尽管Java Stack是线程安全的，使用起来也很简单，但这个类有很大的缺点。

  • It doesn’t have support for setting the initial capacity
  • It uses locks for all the operations. This might hurt the performance for single threaded executions.

4.2. Using ArrayDeque

4.2.使用ArrayDeque

Using the Deque interface is the most convenient approach for LIFO data structures as it provides all the needed stack operations. ArrayDeque is one such concrete implementation.  

使用Deque接口是LIFO数据结构最方便的方法，因为它提供了所有需要的堆栈操作。ArrayDeque就是这样一个具体实现。

Since it’s not using locks for the operations, single-threaded executions would work just fine. But for multi-threaded executions, this is problematic.

因为它没有使用锁来进行操作，所以单线程的执行会很顺利。但是对于多线程的执行，这就有问题了。

However, we can implement a synchronization decorator for ArrayDeque. Though this performs similarly to Java Collection Framework’s Stack class, the important issue of Stack class, lack of initial capacity setting, is solved.

然而，我们可以为ArrayDeque实现一个同步装饰器。尽管这与Java Collection Framework的Stack类的性能相似，但Stack类的重要问题–缺乏初始容量设置–得到了解决。

Let’s have a look at this class:

让我们来看看这个班级。

public class DequeBasedSynchronizedStack<T> {

    // Internal Deque which gets decorated for synchronization.
    private ArrayDeque<T> dequeStore;

    public DequeBasedSynchronizedStack(int initialCapacity) {
        this.dequeStore = new ArrayDeque<>(initialCapacity);
    }

    public DequeBasedSynchronizedStack() {
        dequeStore = new ArrayDeque<>();
    }

    public synchronized T pop() {
        return this.dequeStore.pop();
    }

    public synchronized void push(T element) {
        this.dequeStore.push(element);
    }

    public synchronized T peek() {
        return this.dequeStore.peek();
    }

    public synchronized int size() {
        return this.dequeStore.size();
    }
}

Note that our solution does not implement Deque itself for simplicity, as it contains many more methods.

请注意，我们的解决方案为了简单起见没有实现Deque本身，因为它还包含了许多方法。

Also, Guava contains SynchronizedDeque which is a production-ready implementation of a decorated ArrayDequeue.

此外，Guava还包含SynchronizedDeque，它是一个可用于生产的装饰ArrayDequeue的实现。。

5. Lock-free Thread-safe Stacks

5.无锁线程安全堆栈

ConcurrentLinkedDeque is a lock-free implementation of Deque interface. This implementation is completely thread-safe as it uses an efficient lock-free algorithm.

ConcurrentLinkedDeque是Deque接口的一个无锁实现。这个实现是完全线程安全的，因为它使用了高效的无锁算法。

Lock-free implementations are immune to the following issues, unlike lock based ones.

与基于锁的实现不同，无锁的实现对以下问题具有免疫力。

  • Priority inversion – This occurs when the low-priority thread holds the lock needed by a high priority thread. This might cause the high-priority thread to block
  • Deadlocks – This occurs when different threads lock the same set of resources in a different order.

On top of that, Lock-free implementations have some features which make them perfect to use in both single and multi-threaded environments.

除此之外，无锁实现还有一些特点，使它们在单线程和多线程环境中都能完美使用。

  • For unshared data structures and for single-threaded access, performance would be at par with ArrayDeque
  • For shared data structures, performance varies according to the number of threads that access it simultaneously.

And in terms of usability, it is no different than ArrayDeque as both implement the Deque interface.

在可用性方面，它与ArrayDeque没有区别，因为两者都实现了Deque接口。

6. Conclusion

6.结语

In this article, we’ve discussed the stack data structure and its benefits in designing systems like Command processing engine and Expression evaluators.

在这篇文章中，我们已经讨论了stack 数据结构及其在设计命令处理引擎和表达式评估器等系统中的好处。

Also, we have analyzed various stack implementations in the Java collections framework and discussed their performance and thread-safety nuances.

此外，我们还分析了Java集合框架中的各种堆栈实现，并讨论了其性能和线程安全的细微差别。

As usual, code examples can be found over on GitHub.

像往常一样，可以在GitHub上找到代码示例。