有向图上的无死锁互斥体
Deadlock free mutexes on directed graph
假设我正在编写一个多线程服务器。服务器维护一个节点的有向图，其中每个节点都可以指向许多其他节点并被许多其他节点指向。客户端可以添加新节点，在节点之间添加新指针，也可以删除其中任何一个。引用计数用于垃圾收集。如果两个客户端尝试执行可能导致竞争条件的操作，则应阻止其中一个。客户端和节点之间阻塞的频率应该保持一致。
我如何使用互斥原语来完成此操作并避免争用和死锁？我似乎无法创建一个简单的全球通行权排名，因为这会对某些客户端或节点有利。
如果它改变了答案，它是使用 POSIX 线程接口在 C 中实现的。这是定义节点的一种方式：
struct node {
pthread_mutex_t mut;
int refs; /* reference counting */
void *content; /* immutable */
struct node *links[];
}
我试过只使用递归互斥锁来锁定每个需要操作的节点（假设例如客户端将节点链接到自身）但我不确定这是正确的。
回答：很仔细
引用计数将需要一个来自链接列表的单独互斥体。 （或者只是在引用计数上使用原子操作。）否则你最终会同时持有两个可能死锁的互斥锁。引用计数的互斥量不会 "count" 作为潜在的死锁，因为如果它只修改引用计数，那么它就是一个终点 - 你永远不会在持有它的同时抓住另一个锁，因此它不能造成僵局。锁定、增加、解锁。 （或更好 - 原子增量）持有引用计数锁时没有别的。
在 "using" 节点之前，您需要增加其引用计数。但在执行此操作之前，您需要知道该节点不会被删除 - 否则 refs 变量可能会消失。因此，您需要锁定指向该节点的列表之一 - 通过持有该锁定，您知道无法完全删除该节点 - 有人正在引用它。
但是如果不增加引用计数就无法获取节点列表。鸡和蛋。
即你不知何故 "on" 节点 C，并想使用节点 D。首先将列表锁定在节点 C，然后遍历 D 并增加 D 的引用计数是安全的。但是你是怎么把 "on" 转到 C 的呢？
好吧，显然你是从 A 开始的。或指向 A 的 "head"。即您需要从某个地方开始，从某个地方指向 "stand"。也许是一个永远不会消失的默认节点。
无论如何，假设你可以到达节点N，并且N指向M，你可以到达M
- 锁定N.links
- incr M.refs（锁定引用；增加引用；解锁引用）
- 解锁N.links
- （即使现在取消了 N-to-M 链接，您已经增加了 M，所以它不会消失）
- 移动到 M
其他操作同理
当然，这假设单个线程可以在 "same time" 的其他地方实际断开连接的一块图上。即，一旦您到达 M 并使用其数据或其他任何内容，它现在可能会与图表断开连接（但不会因为您增加了引用计数而被删除）。这应该没问题，因为"same time"在线程中意义不大。
假设我正在编写一个多线程服务器。服务器维护一个节点的有向图，其中每个节点都可以指向许多其他节点并被许多其他节点指向。客户端可以添加新节点，在节点之间添加新指针，也可以删除其中任何一个。引用计数用于垃圾收集。如果两个客户端尝试执行可能导致竞争条件的操作，则应阻止其中一个。客户端和节点之间阻塞的频率应该保持一致。
我如何使用互斥原语来完成此操作并避免争用和死锁？我似乎无法创建一个简单的全球通行权排名，因为这会对某些客户端或节点有利。
如果它改变了答案，它是使用 POSIX 线程接口在 C 中实现的。这是定义节点的一种方式：
struct node {
pthread_mutex_t mut;
int refs; /* reference counting */
void *content; /* immutable */
struct node *links[];
}
我试过只使用递归互斥锁来锁定每个需要操作的节点（假设例如客户端将节点链接到自身）但我不确定这是正确的。
回答：很仔细
引用计数将需要一个来自链接列表的单独互斥体。 （或者只是在引用计数上使用原子操作。）否则你最终会同时持有两个可能死锁的互斥锁。引用计数的互斥量不会 "count" 作为潜在的死锁，因为如果它只修改引用计数，那么它就是一个终点 - 你永远不会在持有它的同时抓住另一个锁，因此它不能造成僵局。锁定、增加、解锁。 （或更好 - 原子增量）持有引用计数锁时没有别的。
在 "using" 节点之前，您需要增加其引用计数。但在执行此操作之前，您需要知道该节点不会被删除 - 否则 refs 变量可能会消失。因此，您需要锁定指向该节点的列表之一 - 通过持有该锁定，您知道无法完全删除该节点 - 有人正在引用它。
但是如果不增加引用计数就无法获取节点列表。鸡和蛋。 即你不知何故 "on" 节点 C，并想使用节点 D。首先将列表锁定在节点 C，然后遍历 D 并增加 D 的引用计数是安全的。但是你是怎么把 "on" 转到 C 的呢？
好吧，显然你是从 A 开始的。或指向 A 的 "head"。即您需要从某个地方开始，从某个地方指向 "stand"。也许是一个永远不会消失的默认节点。
无论如何，假设你可以到达节点N，并且N指向M，你可以到达M
- 锁定N.links
- incr M.refs（锁定引用；增加引用；解锁引用）
- 解锁N.links
- （即使现在取消了 N-to-M 链接，您已经增加了 M，所以它不会消失）
- 移动到 M
其他操作同理
当然，这假设单个线程可以在 "same time" 的其他地方实际断开连接的一块图上。即，一旦您到达 M 并使用其数据或其他任何内容，它现在可能会与图表断开连接（但不会因为您增加了引用计数而被删除）。这应该没问题，因为"same time"在线程中意义不大。