multithreading - 如何/何时以免等待算法释放内存

Question

我在找出免等待算法设计的关键点时遇到了麻烦。假设一个数据结构有一个指向另一个数据结构的指针(例如链表，树等)，那么如何在合适的时间发布一个数据结构呢？

问题是，有一些单独的操作，如果没有锁，就无法自动执行。例如，一个线程读取指向某个内存的指针，并增加该内存的使用计数，以防止该线程正在使用数据时释放内存，这可能需要很长时间，即使没有使用，这也是竞争条件。是什么阻止另一个线程读取指针，减少使用计数并确定不再使用该指针并在第一个线程增加使用计数之前释放该指针？

主要问题是当前的CPU只有一个字CAS(比较和交换)。另外一个问题是，我对免等待算法和数据结构一无所知，在阅读了一些论文之后，我仍然看不到光明。

恕我直言，垃圾回收不能解决问题，因为如果在原子块内有任何单个线程，则必须阻止GC运行(这意味着不能保证GC会再次运行)，或者只是将问题推送给了GC，在这种情况下，请解释一下GC如何判断数据是否处于傻状态(读取了指针(例如，存储在局部变量中)，但是使用计数没有增加)。

PS，欢迎引用有关傻瓜的免等待算法的高级教程。

编辑:您应该假定已使用非托管语言(例如C或C++)解决了问题。毕竟，如果它是Java，则无需担心释放内存。进一步假设编译器可以在使用计数器递增之前生成将对对象的临时引用存储在寄存器中(对其他线程不可见)的代码，并且可以在加载对象地址和递增计数器之间中断线程。当然，这并不意味着该解决方案必须限于C或C++，而是该解决方案应提供一组原语，以允许在链接的数据结构上实现免等待算法。我对原语以及它们如何解决设计免等待算法的问题感兴趣。有了这样的原语，可以在C++和Java中同样良好地实现免等待算法。

Answer 1

经过一番研究，我学到了这一点。

这个问题并非微不足道，有几种解决方案各有优缺点。复杂性的原因来自CPU间同步问题。如果操作不正确，它可能会在99.9％的时间内正常工作，这还不够，否则可能会在负载下失败。

我发现了三个解决方案:1)危险指针，2)基于静止期的回收(由RCU实现中的Linux内核使用)3)引用计数技术。 4)其他5)组合

危险指针的工作方式是将当前 Activity 的引用保存在每个线程已知的位置，因此，任何决定释放内存的线程(当计数器为零时)都可以检查该内存是否仍在被任何人使用。一个有趣的改进是在一个较小的数组中缓冲释放内存的请求，并在数组已满时批量释放它们。使用危险指针的优势在于，它实际上可以保证未回收内存的上限。缺点是给读者增加了负担。

基于静止期的回收通过延迟实际的内存释放来进行，直到知道每个线程都有机会完成可能需要释放的任何数据的工作为止。知道是否满足此条件的方法是检查每个线程在删除对象后是否经过了静止期(不在关键部分)。在Linux内核中，这意味着像每个任务一样进行自愿任务切换。在用户空间应用程序中，这将是关键部分的结尾。这可以通过一个简单的计数器来实现，每次计数器连线程都不在关键部分时(读取共享数据)，每次计数器奇数时，线程都在关键部分内，从关键部分移动或返回的所有线程需要做的就是原子地增加数字。基于此，“垃圾收集器”可以确定每个线程是否有机会完成。有几种方法，一种简单的方法是将释放内存的请求排队(例如，在链表或数组中)，每种请求都使用最新的一代(由GC管理)，当GC运行时，它会检查状态。线程(它们的状态计数器)查看每个线程是否传递给下一代(它们的计数器高于上次或等于或什至相同)，在释放任何内存后，都可以对其进行回收。这种方法的优点是使读取线程的负担最小。缺点是它不能保证等待释放的内存上限(例如，一个线程在关键部分花费5分钟，而数据不断变化且内存没有释放)，但实际上它可以解决好的。

有许多引用计数解决方案，其中许多需要双重比较和交换，有些CPU不支持，因此无法依赖。但是，关键问题仍然存在，在更新计数器之前先进行引用。我没有找到足够的信息来解释如何简单而可靠地完成此操作。所以 .....

当然，有许多“其他”解决方案，这是一个非常重要的研究主题，那里有大量论文。我没有检查所有的人。我只需要一个。

当然，可以将各种方法结合起来，例如，危害指标可以解决引用计数的问题。但是组合的数量几乎是无限的，在某些情况下，自旋锁理论上可能会破坏等待的自由度，但实际上并不会损害性能。就像我在研究中发现的另一个花絮一样，从理论上讲，不可能使用比较和交换来实现免等待算法，这是因为从理论上(纯理论上)，基于CAS的更新可能会因不确定性过多而失败(想象一百万个内核上的一百万个线程，每个线程都尝试使用CAS递增和递减同一计数器)。但是实际上，它很少会失败几次(我怀疑这是因为CPU花费在CAS上的时钟要比CPU花费的时钟多，但是我认为如果算法每隔50个时钟返回到同一位置的相同CAS，并且有64核可能会出现重大问题，然后再说一次，谁知道，我没有100核的机器来尝试这个问题。我的研究的另一个结果是，设计和实现免等待算法和数据结构非常具有挑战性(即使有些繁重的工作外包给了垃圾收集器(例如Java))，也可能不如小心放置锁的类似算法。

因此，是的，即使没有延迟，也可以释放内存。这很棘手。而且，如果您忘记使正确的操作原子化或放置正确的内存屏障，那么，您就敬酒了。 :-)谢谢大家的参与。