multithreading寻路引擎中的共享数据

想象一下,在一个大世界里有很多代理的情况下,他们经常需要计算从A到B的最短/最好的path。在这种情况下,创建一个寻路引擎是很自然的,每个path请求都在一个单独的线。 类似于这个例子。 请求存储在一个队列中,当有可用的线程执行计算时,请求将从队列中取出,最后移动到一组计算path。

我的问题是: 如何存储和更新将在所有线程之间共享的数据? 线程需要访问某种地图结构(可能是二维数组),他的数据需要经常更新。 使用某种同步机制会太昂贵,因为我们有多个线程频繁地从数据中读取数据。

我有两个建议:

  1. 将地图结构存储为一个primefacesarrays。 这似乎是一个简单有效的解决scheme,但是我们会给自己一个限制:我们只能使用可以作为primefacestypes存储的数据 – 在大多数情况下应该是可以的。
  2. 创建两个包含数据副本的缓冲区,并为当前正在使用缓冲区的线程数保持一个引用计数。 首先更新缓冲区A,然后为每个新的path请求让我们从缓冲区A读取线程。当没有更多的线程访问缓冲区B(RefCount == 0)更新缓冲区B并将其设置为新的活动缓冲区。 有了这个解决scheme,我们可以使用任何types的数据结构,但它将(取决于计算时间)稍微不同步 – 我相信这不应该是寻路的一个大问题。 如果计算时间很长,无论如何也不会同步。

你怎么看? 我在这个领域没有太多的经验,所以我不确定这个问题是否有“stream行”的解决scheme。

编辑

这是我结束了(在阅读克罗姆斯特的答案后):

  1. 更新数据
  2. 从队列中取出请求并为每个请求启动一个线程。
  3. 对于每一帧:检查所有线程是否完成。
  4. 所有线程完成后,请返回到步骤1。

在第1步,所有工作线程都空闲。

当代理需要从A到B的path时,它将调用requestPath(from,to) ,这将返回唯一的票据。 票据有一个primefaces(由探路者线程修改,由代理访问),指出它是否有效。 当path已经被计算出来时,票证变成有效的并且代理可以调用getPath(票)来获得path。

我期望所有的探路者在线程中工作,而其余的游戏忙于与地图更改无关的其他事情。 所以地图结构可以被更新locking,并在探测器工作时处于只读模式。

当然,这样的系统是很方便的,当你有几条冗长的path来构建每个tick或其他可以并行化的任务时(至less考虑成千上万的非caching友好的代理)。