[cpp-threads] pthreads (was: RE: C++ Connections proposal)

[Alexander Terekhov]

On 4/26/05, Peter Dimov <pdimov at mmltd.net> wrote:
[...]
> lock-free code doesn't use non-competing accesses.

It can (in addition to competing accesses).

http://www.decadentplace.org.uk/pipermail/cpp-threads_decadentplace.org.uk/2005-April/000229.html

----
  void producer(const T & value) {
    ELEM * tail = m_tail.load(msync::naked_noncompeting);
    ELEM * next = advance(tail);
    while (next == m_head.load(msync::cchsb)) usleep(1000);
    new(tail) T(value);
    m_tail.store(next, msync::ssb);
  }

  T consumer() {
    ELEM * head = m_head.load(msync::naked_noncompeting);
    while (head == m_tail.load(type_list< msync::cchlb_t, msync::ccacq_t >::
      element<copy_ctor_or_dtor_can_mutate_object>::type())) usleep(1000);
    T value(*head);
    head->~T();
    m_head.store(advance(head), type_list< msync::slb_t, msync::rel_t >::
      element<copy_ctor_or_dtor_can_mutate_object>::type());
    return value;
  }
----

The idea is to make it easier for compiler to reuse cached value
and omit load instruction (in the example above) for
msync::naked_noncompeting accesses if implementation does caching
(more precise annotations helping to understand the stuff aside
for a moment).

Another example std::string COWs with zero (in refcount) used as 
"unshareable" indicator. Setting "unshareable" state is a 
noncompeting "exclusive" access.

http://www.google.de/groups?selm=425BFD41.952231D8%40web.de

----
> > First off, an access can be either atomic or not atomic. Non-competing
> > load accesses need not be atomic. Non-competing store accesses must be
> > atomic (because it is non-competing with respect to stores, but it is
> > "competing" with respect to loads), exclusive store or load accesses
> > need not be atomic.
> 
> Hmm, I must be missing something. When I say "non-competing" I mean
> "exclusive" in your terminology. The PLn models use the same definition for

PLn models say that "two operations conflict if they are to the same 
location and at least one of them is a write" and that "given a pair 
of conflicting operations u and v in an execution, operation u 
competes with operation v if and only if there is no ordering chain 
(as defined above) between u and v (either from u to v or vice versa). 
An operation u is a competing operation if and only if there exists 
at least one conflicting operation v in this execution that competes 
with u. Otherwise, the operation is a non-competing operation."

> "competing" - if there is a race.

And what I meant was that for loads, "competing" means that it can 
collide with other store. For stores, "competing" means that it can 
collide with other store, "non-competing" means that it can collide 
(and survive ;-) ) with other load (but not store), and "exclusive" 
means no collision at all. 
----

regards,
alexander.