Lock-free reference counting



This is most probably not a novel idea, and I would be interested in
reading about this subject if there is some material out there about it.

One problem with reference counting smart pointers as a memory
management tool is that if an object is shared among different threads,
the reference counting becomes inefficient because each time the
reference count has to be changed, it needs locking. Two threads must
not change the reference count at the same time, or it will malfunction.

So I was thinking: Inside one single thread locking is not necessary
because one single thread never tries to access the reference count from
two places at the same time. Thus why not have separate reference
counters for each thread?

In other words, rather than having just one reference count for the
object, it could have n of them, where n is the number of threads which
share the object. The smart pointer would modify the reference count
corresponding to the thread it's running in. If it's running in thread
0, it modifies the first reference count, if it's running in thread 1 it
modifies the second, etc. How the smart pointer knows which thread it's
running in is an implementation detail, but the number could be, for
example, given to it when it's created (and it could keep it as a member
variable), or by other similar means.

The fact that once a reference count drops to 0 it will never be
changed again, can be used here. When a reference count drops to 0, the
smart pointer can simply check if *all* the reference counts are 0, and
if so, it can lock, delete the object, null the pointer, and unlock.
(The locking is necessary here to avoid double deletions, which could
happen if there was no locking.)

Thus the only place where locking is needed is in the deletion itself,
rather than each time the reference count is modified.

Can anyone see any flaw in this idea?
.



Relevant Pages

  • cvs-src summary for June 7-14
    ... Here's the summary - hope you like locking. ... You can get old summaries, and an HTML version of this one, at ... Poul-Henning Kamp committed reference counting for the tty code; ...
    (freebsd-current)
  • Re: Lock-free reference counting
    ... Thus why not have separate reference ... The smart pointer would modify the reference count ... modifies the second, etc. ... must decrease some other thread's counter; ...
    (comp.programming)
  • Re: Threads - why isnt a whole object locked when ...?
    ... All of your questions are answerable by pointing out that you have an incorrect mental model of what it means to "lock" something. ... That is, while it's entirely sensible to people who are familiar with standard thread synchronization techniques, in reality it's not actually locking anything. ... Instead, it's using the reference as a sort of traffic signal for other threads, which are cooperating, to respect. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: The future of "frozen" types as the number of CPU cores increases
    ... Frozen objects would live in a different memory space and be ... One way to implement locking is something like this: ... Mutable objects have a reference count field, a lock field, ... the owner of an object is its thread. ...
    (comp.lang.python)
  • Re: multi threading in C#
    ... guarantees that no-one else can screw things up by locking on it ... reference example, "listLock" is the reference only you have access to, and the implication is that "queue" is a reference that others have access to. ...
    (microsoft.public.dotnet.languages.csharp)