Jos*_*vin 5 algorithm debugging multithreading reference-counting shared-memory
假设您在共享内存中有一个引用计数对象.引用计数表示使用该对象的进程数,进程负责通过原子指令递增和递减计数,因此引用计数本身也在共享内存中(它可以是对象的字段,也可以是对象可以包含指向计数的指针,如果他们协助解决这个问题,我愿意接受建议.有时,进程会有一个错误,阻止它减少计数.如何让它尽可能简单地确定哪个过程不会减少计数？
我想到的一个解决方案是给每个进程一个UID(可能是他们的PID).然后当进程递减时,他们将UID推送到与引用计数一起存储的链表上(我选择了一个链表,因为你可以原子地附加到CAS的头部).当您想要调试时,您有一个特殊的进程,它查看共享内存中仍然存在的对象的链接列表,并且列表中没有的任何应用程序的UID是尚未减少计数的那些.
该解决方案的缺点在于它具有O(N)存储器使用,其中N是进程的数量.如果使用共享内存区域的进程数很大,并且您有大量对象,则这很快就会变得非常昂贵.我怀疑有可能是一个中间解决方案,其中有部分固定大小的信息,您可以通过某种方式能够缩小可能的进程列表,即使你不能找出一个一协助调试.或者,如果你能发现它的过程还没有递减当只有一个单一的过程还没有(即无法处理2个或多个进程未能递减计数的检测),这将可能仍然是一个很大的帮助.
(这个问题有更多'人类'解决方案,比如确保所有应用程序使用相同的库来访问共享内存区域,但是如果共享区域被视为二进制接口,并且并非所有进程都是由你不能控制自己.而且,即使所有的应用程序使用相同的库,一个应用程序可能会在库外部出现一个破坏内存的错误,这样就不会减少计数.是的我正在使用不安全的语言C/C++;)
编辑:在单进程情况下,您将拥有控制权,因此您可以使用RAII(在C++中).
您可以使用每个对象仅使用一个额外的整数来完成此操作.
将整数初始化为零.当进程递增对象的引用计数时,它将其PID转换为整数:
object.tracker ^= self.pid;
当进程递减引用计数时,它也会这样做.
如果引用计数始终保持为1,则跟踪器整数将等于增加它但不减少它的进程的PID.
这是因为XOR是可交换的((A ^ B) ^ C== A ^ (B ^ C)),所以如果一个进程使用自己的PID对跟踪器进行偶数次XOR,则与对其进行异或运算相同PID ^ PID- 即零,这使得跟踪器值不受影响.
您也可以使用无符号值(定义为包裹而不是溢出) - 在递增使用计数时添加PID,在递减使用时减去它.