并发计算的示例问题

Question

今天使用的并发编程有很多范例和方法.软件事务内存,参与者,共享状态并发,元组空间等等.

然而,我发现缺少的是一个有趣的并发测试问题库.一个众所周知的例子是"餐饮哲学家问题",它既不复杂也不激励,也不现实.然后有许多并行算法(矩阵乘法,渲染,通用嵌套数据并行)只需要分配工作,但没有真正的并发与执行线程之间的通信.

那么,任何人都能指出一些有趣的问题需要在交互式,甚至是分布式环境中实现并发,这些问题很简单,可以用作并发范例的例子吗？理想情况下,我想找到一系列问题,作为并发范式的"缺乏测试"(或突出它们的差异,因为每个范例都有其优点和缺点).

任何帮助深表感谢 :)

Answer 1

我之前已经考虑过这个确切的问题，之前我自己提出了一些并发编程范例：p

我当时得出的结论是，这样的测试集似乎并不真正以独立于语言的方式存在。虽然它的存在可能会有帮助，但似乎有一些相当充分的理由它不存在（据我所知）。

并发编程的大部分焦点往往集中在数据并行性上，以便将相同的操作并行应用于同一数据集的不同部分。我认为您所谈论的任务级并行性（即并行执行不同的任务，可能共享数据）实际上并没有做太多。我想这是因为它有点难。但我认为这也有点困难，因为大多数问题并不特别适合这种并发性。用并发原语描述分布式系统可能会有所帮助，但这些系统往往是解耦的，因此有一个协议（书面的或隐含的）来调节它们的通信。人们往往不会将这些类型的系统视为明显的“并发”编程情况，即使它们是在正确的框架内查看的（即，将“客户端”和“服务器”视为在某些点上并行操作并同步的代理） 。

我认为您唯一能找到灵感来源的地方是在个人实现中。Erlang、Occam（和 Occam-pi）、Alice、CML、Concurrent Haskell 等都可能有小型测试语料库，但问题及其实现都将偏向于在特定语言中实现（因为它们显然是可以用该语言实现！）。也许您还可以查看致力于多方会话类型和各种流程演算（例如 pi 演算、CCS 和 CSP）的社区，看看他们使用什么类型的系统作为示例模型。我认为，用一组与语言无关的标准问题来描述并发通信系统的想法很有吸引力，但目前有些难以捉摸。