0
$\begingroup$

The object can be locked two different ways, where if the lock is entered the same way a second time, the lock is recursive, but if it's entered the other way, it blocks. Like a reader-writer lock, but symmetric.

In case the text isn't clear, this code should be clear. Beware of bugs. I've only proved it correct, I haven't actually used it yet.

struct mylock {
    pthread_mutex_t entry;
    pthread_mutex_t manager;
    pthread_mutex_t core;
    int counter;
    int state;
}

void mylock_acquire(struct mylock *lock, int state)
{
    assert(state != 0);
    pthread_mutex_lock(&lock->entry);
    if (lock->state != state) {
        pthread_mutex_lock(&lock->core);
        lock->state = state;
    }
    pthread_mutex_lock(&lock->manager);
    ++lock->counter;
    pthread_mutex_unlock(&lock->manager);
    pthread_mutex_unlock(&lock->entry);
}

void mylock_release(struct mylock *lock)
{
    pthread_mutex_lock(&lock->manager);
    if (--lock->counter == 0) {
        lock->state = 0;
        pthread_mutex_unlock(&lock->core);
    }
    pthread_mutex_unlock(&lock->manager);
}

This is exactly the same as reader-writer, right down to there being exactly two classes of lock holder, except that the "writer" side is also multi-entry. So I took the core reader-writer code I learned two decades ago and converted it from P-V notation to mutexes and made both sides use the reader-type logic. ratchet freak did catch that it's no longer allowed to unlock a mutex from another thread anymore.

The actual code is different due to using atomic operations, but that complicates the question too much. The sample code is designed to illustrate the lock structure as simply as possible.

If I call up the Debian man page for pthread_mutex_unlock it actually says you can unlock from another thread ("If the mutex is of the "fast" kind, pthread_mutex_unlock always returns it to the unlocked state."), but ratchet freak has pointed out this isn't portable.

What is the name of this kind of lock? If it has a name, it would be helpful for documenting the thing.

$\endgroup$
  • $\begingroup$ If you've actually proven this code correct, then you should have a formal specification... $\endgroup$ – Derek Elkins May 29 at 19:50
  • $\begingroup$ @DerekElkins: Formal specification: Do not call fork() while close() is being called. Do not call close() while fork() is being called. Do not deadlock. Do not livelock. Do not starve. $\endgroup$ – Joshua May 29 at 20:17
  • $\begingroup$ That's not a formal specification. This or this are examples of formal specifications. $\endgroup$ – Derek Elkins May 29 at 20:36
1
$\begingroup$

The code is far from optimal, if you instead use a condition variable it is much clearer:

struct mylock {
    pthread_cond_t entry;
    pthread_mutex_t manager;
    int counter;
    int state;
}

void mylock_acquire(struct mylock *lock, int state)
{
    assert(state != 0);
    pthread_mutex_lock(&lock->manager);
    while (lock->state != 0 && lock->state != state) {
        pthread_cond_wait(&lock->entry, &lock->manager);
    }
    lock->state = state;
    ++lock->counter;
    pthread_mutex_unlock(&lock->manager);
}

void mylock_release(struct mylock *lock)
{
    pthread_mutex_lock(&lock->manager);
    if (--lock->counter == 0) {
        lock->state = 0;
        pthread_cond_broadcast(&lock->entry);//may have multiple waiters on same state
    }
    pthread_mutex_unlock(&lock->manager);
}

It is also fairly useless, I cannot think of any scenario where such a pattern of exclusion would be useful. Which would be the reason why it doesn't have a name.

$\endgroup$
  • $\begingroup$ It's not useless. I derived the lock from actual requirements. Your code doesn't match well with stackoverflow.com/a/20772586/14768. $\endgroup$ – Joshua May 29 at 14:02
  • $\begingroup$ @Joshua how doesn't it match? cond_wait only exits when lock->state is either 0 or equal to the given state. I admit I should have used broadcast but the rest is fine. $\endgroup$ – ratchet freak May 29 at 14:07
  • $\begingroup$ Apologies. I'm trying to add condition variables to my knowledge. I've previously only used semaphores for this purpose. $\endgroup$ – Joshua May 29 at 14:12
  • $\begingroup$ @Joshua you say you derived this lock style from actual requirements, I smell an XY problem with that. Especially if you are not knowledgeable with synchronization primitives. $\endgroup$ – ratchet freak May 29 at 14:18
  • $\begingroup$ This code is not equivalent. pthread_cond_wait temporary releases lock->manager which is not desired. Once trying to switch state, other requests for the same state should block. While this does work, the characteristics under load are different. $\endgroup$ – Joshua May 29 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.