c++ - 在能够从另一个线程添加元素的同时迭代列表时如何最小化互斥锁？

Question

在工作线程中，我遍历需要更新的项目列表。在主线程中，用户经常调用一个函数来将元素添加到该列表中。我正在使用互斥锁来防止列表在迭代时被修改。通常，伪代码如下所示:

// called by the client to add an element.
void AddElementToList(element)
{
    // lock mutex
    // add element to the list
    // unlock mutex
}

// this function is run by the worker thread
void WorkerThreadUpdate()
{
    // lock mutex
    // for each element in the list
    //     update the element
    //     mark the element for deletion if finished
    // for every finished element
    //     remove element from list
    // unlock mutex
}

更新元素时​​出现问题。元素的更新功能可能需要很长时间，在某些情况下最多大约一秒钟。发生这种情况时，用户对 AddElementToList 的下一次调用会阻塞，导致他们的应用程序卡住，直到所有元素都已更新。 AddElementToList 函数被调用的次数足够频繁，因此这是一个非常明显的问题。

所以我正在寻找更好的方法。我想在保护列表的同时更新元素，但保持用户的主线程响应。我确定这几乎是多线程 101，但我想不出正确的术语来查找我正在寻找的示例。

我在考虑一个使用两个列表的解决方案，一个“请求”列表和一个“工作”列表。

用户调用 AddElementToList 将元素添加到请求列表。在工作线程中，在迭代工作列表后，它遍历请求列表并将其元素添加到下一帧的工作列表中。它仅在实际修改列表时锁定。

// called by the client to add an element.
void AddElementToList(element)
{
    // lock mutex
    // add element to the request list
    // unlock mutex
}

// this function is run by the worker thread
void WorkerThreadUpdate()
{
    // for each element in the work list
    //     update the element
    //     mark the element for deletion if finished

    // for every finished element
    //     lock mutex
    //     remove element from work list
    //     unlock mutex

    // lock mutex
    // for every element in the request list
    //     add element to the work list
    // clear the request list
    // unlock mutex
}

我认为这应该可行，但我不完全确定。这是一种可以接受的方式吗？有没有更好的方法来处理这个问题？

Answer 1

您对添加进行排队的计划应该可行。它是否可以接受取决于等待队列添加直到线程进行下一次“更新”传递是否可以接受。

更新时甚至需要锁定列表吗？还有什么正在访问此列表，何时访问？您可以锁定列表，制作引用的复制 vector/列表，解锁列表，然后对每个复制引用逐一运行更新吗？