3

我正在尝试开发一个由线程池组成的应用程序，使用工作窃取算法同时执行任务。

这些任务

  • 访问一组预定义的对象；
  • 必须在实际运行之前“原子地”获取它访问的所有对象的读/写权限；
  • 完成后（并保证最终完成）释放他们获得的对象。

解决此问题的一种可能方法是让每个线程一次执行一项任务，然后尝试使用预定义的顺序锁定每个对象。如果至少有一个失败，则释放所有锁，然后继续执行另一项任务。

然而，这种方法增加了具有大对象依赖性的任务饥饿的可能性，甚至可能导致活锁。

是否有另一种方法可以在最大化并发的同时获取一组锁？（没有全局锁）或者可能以不再需要的方式更改系统？如果是这样，有什么好的论文吗？

ps：正如 thiton 回答的那样，这是“哲学家就餐”问题的广义版本。我正在寻找非集中式解决方案，特别是在高负载（添加和删除任务）中表现良好的算法。

4

3 回答 3

1

订购资源是一种有效的方法。想到的另一个直接方法是引入一个共享仲裁器，该仲裁器持有有关资源可用性的信息。任务将通过仲裁器在单个原子步骤“acquire(r1, r2, ..., rn)”中锁定它们需要的所有资源，并使用“release(r1, r2, ..., rn)”类似地释放它们。

如果“获取”请求 A 可以得到满足，仲裁器将确保没有其他任务可以获取 A 持有的任何资源，直到 A 释放它们。

仲裁者可以使用几种策略来满足传入的请求：

  1. 拒绝无法立即满足的请求 - 任务将不得不重试。这为活锁和饥饿打开了大门。
  2. 将所有传入请求保留在队列中，并在头部请求所需的资源可用时以 FIFO 方式为它们提供服务。
  3. 将所有未满足的请求保存在一个列表中（不阻塞它们所需的资源），并在每次释放某些资源时遍历它们（可能对较旧的请求具有优先级），以找到可以满足的请求。
于 2011-08-02T13:23:00.377 回答
0

如果一个任务试图锁定对象只是在某个时候失败，那么另一个任务可能无法锁定一个对象，因为第一个任务当时拥有它。

我想我会在最初尝试获取锁时使用全局锁，也可能在最终释放它们时使用全局锁。

当一个简单的解决方案在实践中证明是不够的时，我会担心最大并发性。

于 2011-08-01T22:38:53.603 回答
0

你的问题被称为餐饮哲学家。您应该在此关键字下找到所需的任何数量的文献 :-)。

于 2011-08-02T06:46:43.483 回答