0

好的，最近我一直在考虑线程安全，我想知道为什么链表或双端队列不是线程安全的。

假设我们有一个像这样的简单链表类：

class myLinkedList {
private:
    myLinkedList* next;
    int m_value;

public:
    myLinkedList() { next = NULL; m_value = 0; }
    void setValue(int value) { m_value = value; }
    int getValue() { return m_value; }
    void addNext(int value) { next = new myLinkedList; next->setValue(value); }
    myLinkedList* getNext() { return next; }
};

现在我只想在末尾添加新元素并在开头删除元素（先读取它们然后删除它们）。我基本上只是得到第一个的地址next，删除第一个元素并记住next作为我的新第一个元素。对于添加新元素，我只记得最后一个元素，当我添加一个新元素时，我只设置一个新元素并将我的新元素next记住next为最后一个元素。

在这种情况下，线程的问题在哪里？作家和读者不应该对此有任何问题，因为他们从不相互交流。这不像使用数组或向量（我很清楚它为什么会导致问题）。

4

4 回答 4

5

对您问题的评论是正确的，您的实施将不起作用。但是，要回答实际问题，您的代码中有一个竞争条件：

void addNext(int value) { next = new myLinkedList; next->setValue(value) }

假设线程 A 执行：

next = new myLinkedList;

现在线程 A 被抢占，线程 B 也执行相同的指令。这意味着nextnow 并不指向线程 A 希望它指向的任何位置，而是指向线程 B 设置它的任何位置。线程 B 继续执行：

next->setValue(value)

此后不久（甚至同时），线程 A 也执行上述操作。

你能看出问题吗？线程 A 调用next->setValue()Bnext并且 Anext丢失。

于 2012-10-20T17:52:28.743 回答
1

当您使用std::list在多个线程中共享的容器（或其他任何东西）的类实例时，您需要使用互斥锁或类似机制来保护并发访问，以获取线程保存行为。

更新

如您所见的构造

 void setValue(int value) { m_value = value; }
 int getValue() { return m_value; }
 void addNext(int value) { next = new myLinkedList; next->setValue(value); }

不是原子操作。因此，只要它们不在受保护的上下文中使用，它们就不是线程安全的。对于像std::list.

于 2012-10-20T17:46:44.457 回答
1

以下是将问题中给出的代码转换为最基本的锻炼程序：

class myLinkedList {
private:
    myLinkedList* next;
    int m_value;

public:
    myLinkedList() : next(0), m_value(0) { }
    int  getValue() const { return m_value; }
    void setValue(int value) { m_value = value; }
    void addNext(int value) { next = new myLinkedList; next->setValue(value); }
    const myLinkedList *getNext() const { return next; }
};

#include <iostream>

static void print_list(const myLinkedList *rover)
{
    std::cout << "List:";
    while (rover != 0)
    {
        std::cout << " " << rover->getValue();
        rover = rover->getNext();
    }
    std::cout << std::endl;
}

int main()
{
    myLinkedList mine;
    print_list(&mine);
    mine.addNext(13);
    print_list(&mine);
    mine.addNext(14);
    print_list(&mine);
    mine.setValue(3);
    print_list(&mine);
    mine.addNext(15);
    print_list(&mine);
}

该程序的输出是：

List: 0
List: 0 13
List: 0 14
List: 3 14
List: 3 15

如您所见，它不是普通的链表；它是最多两个项目的列表。在 下运行程序（称为ll链表）valgrind，我得到：

==31288== Memcheck, a memory error detector
==31288== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==31288== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==31288== Command: ll
==31288== 
List: 0
List: 0 13
List: 0 14
List: 3 14
List: 3 15
==31288== 
==31288== HEAP SUMMARY:
==31288==     in use at exit: 6,239 bytes in 36 blocks
==31288==   total heap usage: 36 allocs, 0 frees, 6,239 bytes allocated
==31288== 
==31288== LEAK SUMMARY:
==31288==    definitely lost: 48 bytes in 3 blocks
==31288==    indirectly lost: 0 bytes in 0 blocks
==31288==      possibly lost: 0 bytes in 0 blocks
==31288==    still reachable: 6,191 bytes in 33 blocks
==31288==         suppressed: 0 bytes in 0 blocks
==31288== Rerun with --leak-check=full to see details of leaked memory
==31288== 
==31288== For counts of detected and suppressed errors, rerun with: -v
==31288== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1)

如果代码是一个有效的链表实现，那么在addNext().

基本上，您创建一个节点，new然后需要将其挂接到列表中。如果另一个线程同时尝试执行此操作，则您有一个可能导致结构不一致的时间窗口。为了线程安全，您需要在修改列表时确保互斥。

于 2012-10-20T17:58:02.943 回答
0

看似简单的事情有几个线程安全问题

next = new myLinkedList;

根据硬件，next可以通过线程切换来破坏分配；也就是说，可能会写入部分值，然后处理器在写入其余值之前更改为不同的线程。然后另一个线程会看到一个垃圾值。

对于多个处理器，还有一个额外的问题是分配给的值next被写入执行存储的处理器的本地缓存。其他处理器有自己的缓存，因此它们可能看不到新值。或者他们可能会看到它，但看不到调用写入的new myLinkedList值，或者可能写入的值next->setValue(value);。

或者其他事情可能会出错。

当另一个线程正在读取或写入相同的数据位置时，从一个线程写入数据位置是数据竞争，并且具有数据竞争的程序的行为是未定义的。在实践中，这意味着它可以正常工作，直到您为最重要的客户演示该程序，那时它会严重崩溃。

于 2012-10-20T18:12:44.067 回答