Re: Global lock contention problem

Joe Seigh wrote:
Dervish wrote:

Global lock is a most general solution to protect global data. However
for special cases sometimes it is possible to create lock-free
solution.
E.g. if:
1. Global data is changed by only by one writer thread with moderate
speed (e.g. once per second).
2. There are 0 or more readers.
3. It takes no more than limited time (e.g. 0.1 sec) for reader to get
data.

Than:
0. Access to global data is performed through global pointer.

Writer:
1. Copy data to new place.
2. Modify data.
3. Swap pointers. Store old one.
4. Delete data pointed by old pointer after 0.5 sec (or let garabage
collector clean up).

Reader:
5. Just read by pointer, but don't spent more than 0.1 sec in reading
(or let garbage collector work).

There are two problems with this solution:
1. Possible huge memory consumption (write speed is too big).
2. Access to deallocated memory (if reader failed to get access in
timely fashion, or cached some pointer).

Making timing assumptions is known not to work reliably. For GC, it
has to be atomically thread-safe and you have "stop the world" GC problems.

Indeed.




There
are forms of GC that will work, e.g. RCU, hazard pointers, atomic reference
counting which have been discussed before but that's all lock-free. I'm
looking for solutions using Posix synchronization only.

I have a solution for this that uses %99.99 POSIX mutexs; only relies on dependent load ordering. I will now briefly describe how the garbage collection part of my solution works:


- Each thread has two mutexs ( owner_lock, memory_lock ) an array of persistent reference counters ( prefs[] ), a synchronization state variable ( sync_state ), and a list of deferred objects ( my_defer ).

- A polling thread has a condition variable ( poll_cond ), a mutex ( poll_lock ), a list of registered threads ( treg ) and three lists of deferred objects ( new_defer, old_defer, final_defer )

- Each thread that registers with the polling thread shall lock the poll_lock; "lock memory_lock"; push itself onto treg; unlock poll_lock and signal poll_cond.

- Each thread that unregisters with the polling thread shall lock the poll_lock; "unlock memory_lock"; pop itself from treg; move my_defer to the polling threads new_defer; unlock poll_lock and signal poll_cond.

- A registered thread is supposed to periodically or episodically execute a synchronization operation. This can be achieved by locking the owner_lock; unlocking the memory_lock; set a flag in sync_state; lock the memory_lock and finally unlock the owner_lock. When the thread "unlocks and subsequently locks" the memory_mutex "inside of the owner_locks critical region" it has the effect of making the critical section that was protected by memory_mutex "visible to the polling thread". All of the modifications to the prefs[] array are carried out under the critical section of the memory_mutex because it is "always locked", except for "explicit synchronization".

- A registered thread acquires persistent references to an object by loading a pointer to object; dependent load barrier; hash pointer to object into index; the indexed counter in prefs[] is incremented.

- A registered thread releases persistent references to an object by hashing a previously acquired object into an index; the indexed counter in prefs[] is decremented.

- A registered thread defers an object by making it unreachable and queuing it into my_defer.

- The polling thread periodically or episodically checks to see if each registered thread has executed a synchronization operation. This is achieved by waiting on poll_cond for the desired polling interval. When its time to poll it iterates through treg and for each thread: lock owner_lock; examining the sync_state variable for a flag; if the flag is set continue, if not unlock previously acquired owner_locks and wait for another polling interval.

- After the polling thread has determined that all of the threads have executed a synchronization then it resets the sync_state flag of each thread and unlocks all previously acquired owner_locks; It is now guaranteed that all "previous effects" on the prefs[] arrays "since the last synchronization" are "fully visible". It then calls the deferred requests that exist in final_defer and empties it; swaps new_defer with old_defer; collects a new generation of deferred requests from my_defer in all registered threads into new_defer; checks the old_defer list against each threads prefs[] array. If a old deferred request is not found to have any persistent references, it is then moved into a the final_defer list. Then another polling interval is waited for.




That briefly describes a certain portable embodiment of my vzoom patent. As you can see, the only place that dependent load ordering is required is when a thread loads a pointer to a shared object. That has to be about as portable as you can get and still allow for virtually zero-overhead access. If you have any questions please feel free to fire away...


:)




Now to address the global locking issue... I have posted a solution that I call multi_mutex here:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/e0c011baf08844c4/3ca11e0c3dcf762c?q=multi+mutex&rnum=1#3ca11e0c3dcf762c

This can be augmented with a simple "back-off-retry" algorithm to allow for true two-phase locking. I bet this can be used for lock-based STM which should address per-node locking. What do you think of this one Joe?




P.S.

I found some more time to hang out here on c.p.t. so I will be around for a while. I know I promised demo applications of vzoom. The truth is that I am still tinkering around with them, and I was advised not to give away any actual source code but only brief descriptions and perhaps some of the drawings. Plus, I received a couple of licensing offers as well. So I need to address these issues before I can provide source code.

For now, I can only give brief descriptions, like the one above. If you want to see some of the drawings I can post some of them as well. Any thoughts on this?
.

Relevant Pages

  • Question about vZOOM reference handling
    ... persistent reference counters, a synchronization state ... Each thread that unregisters with the polling thread shall lock the ... A registered thread acquires persistent references to an object by ... As I understand particular cell in prefs[] contain sum of references ...
    (comp.programming.threads)
  • Re: Independent thread fireing events in ATL Service synchronization requirements?
    ... and made my client list a class with synchronization inside ... my guess is that the lock for the COM object ... pointer is not enough and that I would also need to lock ... > the entire loop notifying your objects. ...
    (microsoft.public.vc.atl)
  • Re: Independent thread fireing events in ATL Service synchronization requirements?
    ... You'll need synchronization for your list all right. ... "Phil Ten" wrote in message ... > I remove the pointer from my list in the destructor of the ... >>>>> features to fire events only when possible. ...
    (microsoft.public.vc.atl)
  • Re: An atomic lock-free refcounting patent application
    ... The similarities in our algorithms seem to have nothing to do with single-target synchronization. ... It only has to do with the way are are managing the nodes lifetimes. ... They make a clear separation in the paper between the single-target stuff and the method used for node lifetime tracking. ... They read the pointer along with the version count then double-check with CAS to make sure the pointer read is synchronized with the version read. ...
    (comp.programming.threads)