Overview

reference counting

对于一般的 reference counting， 比如在 reference 创建或复制是对 count 进行加一，在 reference 销毁时，发送信息给 owner ，让 owner 对 count 进行减一。

这种简单的 reference counting 会出现 race conditions between increment and decrement message 的问题。即 可能出现 A 刚复制一个 reference 给 B， 然后立刻就要销毁这个 reference， 所以就可能出现 A 的 -1 信号先发送给了 owner ， 然后 owner 的 count 为 0 就被销毁，而后才收到 B 的 +1 信号。一种解决以上 race 问题的方法是在 A 复制reference 之前首先发送 +1 信号给 owner，接收到 owner 的 ack 信号之后，再进行后面的操作。对于这种简单的改进方法，还存在问题是加减信号没有幂等性（idempotent），即可能出现 ack 信号丢失，加减信号重复发送给了 owner。

以下介绍两种解决 race 和    message fail 问题的该进方法：Weighted Reference Counting 和

Weighted Reference Counting

每个 owner 存在两个 weight， 分别为 partial weight 和 total weight。每个 reference 包含一个 partial weight， 当新建或者复制 reference 时，会将 partial 减半，然后将另一半赋给新的 reference。 当 reference 销毁时，向 owner 发送销毁信息附带该 reference 的 partial weight 的值。当 owner 收到该信息后，将 total weight 减去收到的 partial weight 的值，当 owner 上的 partial weight 和 total weight 相等时则说明该 object 为 garbage。

$$

total_weight = \sum partial_weight $$

该方法的主要缺点在于初始化的 total weight 为 $2^k$ 只能复制创建 k 次 reference，partial weight 即为 1，不可再分。

为了解决该问题，一种改进的方法时允许 client 发送一个数给 owner， owner 将 total weight 加上该数值，client 也将其 partial weight 加上该数值，如此则可继续再分。另一种解决方法是采用 indirect 的方法，即当在一个 client 中 partial weight 为 1，需要继续再分，则创建一个 indirect entry 包含 partial weight 和 total weight ，且指向原 owner，而新分的 reference 则指向该 client。所以之后产生的 reference 获取数据需要两步。

weighted reference counting 优于 naive reference counting 在于它在复制 reference 是不需要向 owner 发送信息，同时也解决了 race condtions 的问题。但是依旧没有解决message loss 和 message duplication 的问题。

Optimised weighted reference counting

基于 weighted reference counting 有人进行了改进使得支持 message loss。

$$ total_weight \geq \sum partial_weight $$

本方法在 partial weights 不能再分的的时候引入了 null weight value. 这样的话，total weight 总是大于 partial weights 的和，所以 object 并不会被释放。

Reference listing

通过在 owner 处维护一个 reference table ， 用于表明有哪些 client 指向了该 object。这样便可以解决 message duplication 的问题。但是消耗了更多的 memory。

Stub-Scion Pair Chains