多线程访问数据结构

我正在使用C，pthreads和套接字在Linux中编写应用程序。多线程访问数据结构

这将是客户端 - 服务器应用程序，服务器将具有N + 2个线程，其中N - 活动客户端的数目，一个线程用于接受新连接并为客户创造和最后一个线程将被接受用户输入。

我将使用链表来保存一些数据，这将是有关我的应用程序，与每一位客户都会有我的列表中相关联的一个节点。那些客户端线程会以一定的时间间隔更新存储在其节点中的信息，可能是一秒钟，可能是两分钟，它会动态更改。

现在问题在于，如果用户请求它，存储在链接列表中的信息需要写入标准输出。当然，在写作时我应该获得互斥体。我担心整个列表中的一个互斥量会妨碍性能。

我在考虑将互斥锁与每个节点关联起来，但它会使一些指定节点的移除复杂化（首先，我需要确保'stdout writer'线程不会遍历列表，我也会需要获取我的节点的互斥体和前一个节点来改变指向下一个节点的指针，依此类推 - 或者我需要遍历所有前一个节点，或者我需要创建双链表）。

所以我想知道如果涉及多个互斥体的解决方案，甚至更好用更复杂的代码，条件和这一切的锁定，等待和解锁。

来源

2012-06-08 Andna

你说得对，每个节点互斥会使代码更复杂。这是一个折衷，你将不得不决定价值。您可以对整个列表使用一个锁，这可能会导致锁争用，但代码很大程度上不受锁的存在的影响，因此更容易编写，或者您可以拥有更多的锁，争夺的机会更少，导致更好的性能，但代码很难写入并得到正确。您甚至可以通过为每组节点锁定一些东西 - 将一些节点分配在一起并为该组锁定一个锁定 - 但是，在跟踪空闲列表和碎片的可能性时会遇到问题。

你需要考虑添加操作的相对频率，删除等操作，以及全名单迭代，以及其他（重组，搜索，其他任何应用程序都需要）。如果添加/删除非常频繁，但是每隔三个蓝色月亮行走一次，单一锁定可能很容易。但是，如果列表（无论是完整的数据转储，还是搜索或其他内容）非常普遍，更细化的方法会变得更具吸引力。你甚至可能需要考虑读写器锁而不是互斥锁。

来源

2012-06-08 18:29:12 twalberg

那么这又怎么样呢，而不是物理地去除节点，我将它们标记为“未使用”，这样在写入数据和删除期间就不会有任何问题，因为我不需要访问任何其他节点，如果读者想要遍历他将锁定它的列表，并且只有当列表没有被读者遍历时才会发生列表添加。 – Andna

你可以做到这一点 - 但考虑是否值得。添加新节点将搜索未使用节点，然后分配一个，如果没有未使用的节点。遍历列表必须足够聪明以跳过未使用的列表。删除会更容易一些，因为您不必调整链接，但仍然需要使用锁来标记未使用的节点，所以不妨将其从列表中拉出。到处都是，我认为将节点标记为未使用会使代码变得更加复杂，而没有太多收获。 – twalberg

好吧，我想我会使用读写锁，据我所知，我可以保证作者将有权限读者访问列表。 – Andna

如果你将有N个线程N个活动的客户端，然后考虑使用pthread_setspecific和pthread_getspecific的选项。

来源

2012-06-08 18:04:32 Viswesn

它会工作，但有这个问题，我会neet在其他线程中检索数据，用户输入线程将打印数据到标准输出，如果这将是线程特定的，我不认为我可以从每个线程在一个线程中。 – Andna

在这种情况下，pthread_setspecific将不起作用。在打算在列表节点中写入内容之前，您需要锁定和解锁列表的头部;我宁愿建议你有树实现而不是列表实现;因为树实现遍历将提高系统的性能。 – Viswesn

你并不需要遍历列表中的所有回来的路上：当你穿越它，你测试，如果下一个元素是，你要删除的一个，然后你可以锁定两个节点 - 在同一直整个代码的顺序，所以你避免死锁。此外，您可以使用双重检查成语，并在需要确定它具有的功能时锁定互斥节点。

remove 
    for node in list 
     if node->next is the desired node 
      lock(node) 
      lock(node->next) 
       if node->next is the desired node 
        do removing stuff 
       else 
        treat concurrent modification - retry, maybe? 
      release(node->next) 
      release(node)

有了这个成语在阅读它，你也并不需要锁定整个列表检查第一个测试和锁定之间进行修改。我不相信代码会因为一组互斥体而变得复杂得多，并且锁定开销与您可能执行的操作（IO）相比毫无用处。

来源

2012-06-08 18:35:40

除非您有几十个甚至几十万个用户，否则读取该列表不会花费太长的时间。您可能想创建一个本地中间列表，以便在写入时原件不会被锁定，其中可能需要一些时间。这也意味着您可以在某个时间点获得列表的快照。如果您锁定了各个节点，则可以删除A，然后然后移除元素B，但是当B不存在时，A会出现在显示的列表中。

据我所知，如果你做想要锁定个别节点，你的列表必须单独链接。添加和删除变得相当棘手。在Java中，有几个使用快速比较和交换技术的系统类。 C中必须有类似的代码，但我不知道在哪里寻找它。你会得到那些按时间顺序挑战的结果。

来源

2012-06-08 18:51:40 RalphChapin

多线程访问数据结构

回答

相关问题