[cpp-threads] Spurious failures of try_lock{_for}({rel_time}) vs. strong try_lock{_for}({rel_time})
Alexander Terekhov
alexander.terekhov at gmail.com
Tue Dec 23 15:16:08 GMT 2008
On Tue, Dec 23, 2008 at 7:44 AM, Hans Boehm <Hans.Boehm at hp.com> wrote:
>
> On Mon, 22 Dec 2008, Alexander Terekhov wrote:
>
>> N2800's try_lock():
>>
>> "Effects: Attempts to obtain ownership of the mutex for the calling
>> thread without blocking. If ownership is not obtained, there is no
>> effect and try_lock() immediately returns. An implementation may fail
>> to obtain the lock even if it is not held by any other thread."
>>
>> N2800's try_lock_for(rel_time):
>>
>> "Effects: The function attempts to obtain ownership of the mutex
>> within the time specified by rel_time. If the time specified by
>> rel_time is less than or equal to 0, the function attempts to obtain
>> ownership without blocking (as if by calling try_lock())."
>>
>> seem to contradict POSIX:
>>
>> http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_trylock.html
>>
>> "The pthread_mutex_trylock() function shall be equivalent to
>> pthread_mutex_lock(), except that if the mutex object referenced by
>> mutex is currently locked (by any thread, including the current
>> thread), the call shall return immediately."
>>
>> http://www.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_timedlock.html
>>
>> "Under no circumstance shall the function fail with a timeout if the
>> mutex can be locked immediately."
>
> I would argue that this is a mistake in the Posix standard. Current
I disagree. Current POSIX XBD 4.10 Memory Synchronization states that
http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap04.html#tag_04_10
"Unless explicitly stated otherwise, if one of the above functions
returns an error, it is unspecified whether the invocation causes
memory to be synchronized."
So there isn't any release-acquire pairing involving failed
try{timed}lock() in POSIX. See my interpretation of XBD 4.10 in terms
of release-acquire pairings:
http://www.decadentplace.org.uk/pipermail/cpp-threads/2005-April/000222.html
I agree with N2800's note stating
"[ Note: Since lock() does not synchronize with a failed subsequent
try_lock(), the visibility rules are weak enough that little would be
known about the state after a failure, even in the absence of spurious
failures. —end note ]"
The situation is the same in POSIX.
> implementations on weakly ordered architectures are arguably often
> incorrect with respect to this specification. If you want to promise
> sequential consistency for data-race-free programs in the presence of
> pthread_mutex_timedlock(), you would need lock() to have release semantics
> as well.
I disagree, see below.
>
> The details are in my PPoPP 07 paper. But the basic example is:
>
> Thread1: x = 42; pthread_mutex_lock(&l);
>
> Thread2:
>
> while (pthread_mutex_timed_lock(&l, small) == 0) pthread_mutex_unlock(&l);
> pthread_mutex_lock(&dummy); pthread_mutex_unlock(&dummy);
> assert(x == 42);
This example is not data-race-free. Consider that it doesn't prevent
reordering of x's load above dummy's unlock() and completion of failed
timedlock() after x's load resulting in a race on x.
>
> (The initial loop waits for thread 1 to acquire the lock. Yes, this
> is evil code.)
>
> This can result in non-sequentially-consistent behavior, and the
> assertion may fail, if the assignment and lock acquisition in thread1
> are not ordered. I believe they often are not. Fixing this can result
> in appreciable, and completely useless, overhead for most lock
> acquisitions.
Well, consider lock operations on semaphores
http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap04.html#tag_04_15_00_01
sem_wait() (and XSI IPC sema's locking as well).
The example would be
(Initially: semaphore value == 1)
Thread1:
x = 42;
sem_wait(&l); // decrement semaphore value
Thread2:
int v;
sem_getvalue(&l, &v);
if (l == 0) assert(x == 42);
I think that this shall be data-race-free due to release-acquire
pairing between sem_wait(&l) and sem_getvalue(&l, &v).
> (The dummy lock acquisition isn't necessary to see that this is non-SC
> behavior. It does help to argue that the current behavior is actually
> officially inconsistent with the current spec, which is unclear
> about when SC behavior is intended.)
I agree that POSIX XBD 4.10 needs some fixing to provide clear listing
of all release-acquire pairings involving XBD.4.10 calls.
http://www.decadentplace.org.uk/pipermail/cpp-threads/2005-April/000222.html
regards,
alexander.
More information about the cpp-threads
mailing list