线程安全的排序集合

Question

在Python中，是否有线程安全的排序集合实现？
Python文档中提到了SortedCollection，但我不确定它是否是线程安全的（它是吗？）
如果没有这样的实现，你会如何实现它？

- Jonathan Livni

---

其实我不明白为什么 Python 没有内置这样一个类... - Jonathan Livni

Answer 1

浏览代码后，似乎它不是线程安全的。如果要从多个线程中使用它，则访问它的应用程序代码应该受到信号量锁的保护。

如果您想使SortedCollection类线程安全，可以编写一个装饰器函数。

它可能看起来像这样：

SortedCollection：

def __init__(self):
    self.mysemaphore = threading.Semaphore()

def guard(func):
    def guarded(*args, **kwds):
        self.mysemaphore.acquire()
        try:
            return func(*args, **kwds)
        finally:
            self.mysemaphore.release()

return guarded

# edit the class, applying the decorator to its methods.
@guard
def unsafeFunc(self, a, b, c):
    ''' do work here'''

编辑

不要错误地认为线程安全的数据结构会使您的应用程序代码线程安全。如果您在SortedCollection上执行多个操作，则所有这些操作都需要由锁保护。

即使SortedCollection是线程安全的，以下代码也不会是线程安全的：

slist.insert(1)
slist.insert(2)

另一个线程可能会在这两个语句之间插入一个条目，因此您需要在应用程序代码中进行保护。 如果您将此添加到应用程序代码中，则无需修改 SortedCollection 以使其线程安全。

semaphore2.acquire()

try:
    slist.insert(1)
    slist.insert(2)
finally:
    semaphore2.release()

- mikerobi

---

函数返回会阻止信号量的释放吗？ - Eduardo

从文档中得知：当try语句的任何其他子句通过break、continue或return语句离开时，“finally”子句也会在“退出时”执行。@eduardocereto - rplnt

再次说明，“线程安全”只是指来自多个线程的调用不能破坏数据结构的内部，不同线程的调用仍可能以任意顺序执行。另外，在现代Python中，您可以像这样使用锁定：with mylock: dostuff()。 - Jochen Ritzel

使用全局的mysemaphore，你会不会错误地在不同的SortedCollection实例之间进行锁定？你如何才能针对每个实例执行此操作？ - Jonathan Livni

@Jonathan，你说得对。我表达不够清晰。我试图让答案更简洁。我已经编辑过了，避免任何混淆。 - mikerobi

Answer 2

collections.OrderedDict类在更新时不是线程安全的。可以进行并发读取，但写入需要使用锁。有关如何在OrderedDict中使用锁的示例，请参见functools.lru_cache()源代码。

- Raymond Hettinger

Answer 3

您可以使用heapq模块来维护一个排序列表。由于GIL的作用，所有对C扩展的调用都是原子性的（在CPython中，除非扩展显式释放锁），因此heappush和相关函数是线程安全的。

from heapq import heappush, heappop

class Heap:

    def __init__(self):
        self._heap = []

    def push(self, x):
        heappush(self._heap, x)

    def pop(self):
        return heappop(self.heap)

- Jochen Ritzel

---

除了 heapq 不是 C 扩展之外！！ heapq 是纯 Python 实现的。请查看代码。从快速查看中，heapq 明显不是线程安全的！ - Russ

我需要补充一点，虽然 heapq 函数本身并不是线程安全的，但是你可以使用 Queue 模块的 PriorityQueue。该模块是线程安全的，并且在内部使用了 heapq。 - Russ

Answer 4

Python与Java不同：如果一个类在文档中没有指定其线程行为，那么可以安全地假设它不是线程安全的。

Python并非为多线程编写而设计。即使在今天，多线程也只是一个二等公民，因为一次只有一个线程处于活动状态（这并不能防止大多数数据竞争问题）。这被称为全局解释器锁（GIL）。

如果一个类或数据结构没有为并发构建，则必须通过外部锁来保护对它的访问。

- dmeister

---

这实际上与Java没有什么不同。在Java中，如果没有提及线程，可以安全地假设它不是线程安全的。然而，与Python相反，你可以获得线程安全的集合 - 不幸的是，Python在这方面有所欠缺 :/ - Voo

Answer 5

在Python中，原子操作始终是线程安全的。只有当操作不是原子操作时才需要同步。无论线程数量如何，GIL始终只允许一个原子操作。但在Python中进行多进程操作则另当别论。

- Wyrmwood