Reader Preferred and Writer Preferred in Read-Write Multithreading

Question

I was given the assignment to write a Read-Write implementation using POSIX threads. I would like to know if my implementation is correct for both cases:

Horrible Attempt Erased

Attempt Number 2

Reader Preferred:

Variables:

int readersActive_;

sem_t lock_;
sem_t writeLock_;

Implementation:

void PalindromeDatabase::lockReaders()
{
    sem_wait(&lock_);
    {
        ++readersActive_;

        if (readersActive_ == 1)
            sem_wait(&writeLock_);
    }
    sem_post(&lock_);
}

void PalindromeDatabase::unlockReaders()
{
    sem_wait(&lock_);
    {
        --readersActive_;

        if (readersActive_ == 0)
            sem_post(&writeLock_);
    }
    sem_post(&lock_);
}

void PalindromeDatabase::lockWriters()
{
    sem_wait(&writeLock_);
}

void PalindromeDatabase::unlockWriters()
{
    sem_post(&writeLock_);
}

Writer Preferred:

Variables:

int readersActive_;
int readersWaiting_;

int writersActive_;
int writersWaiting_;

pthread_mutex_t lock_;
pthread_cond_t read_;
pthread_cond_t write_;

Implementation:

void PalindromeDatabase::lockReaders()
{
    pthread_mutex_lock(&lock_);
    {
        if (writersActive_ || writersWaiting_)
        {
            ++readersWaiting_;

            do
            {
                pthread_cond_wait(&read_, &lock_);
            } while(writersActive_ || writersWaiting_);

            --readersWaiting_;
        }

        ++readersActive_;
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::unlockReaders()
{
    pthread_mutex_lock(&lock_);
    {
        --readersActive_;

        if (writersWaiting_)
            pthread_cond_signal(&write_);
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::lockWriters()
{
    pthread_mutex_lock(&lock_);
    {
        if (readersActive_ || writersActive_)
        {
            ++writersWaiting_;

            do
            {
                pthread_cond_wait(&write_, &lock_);
            } while(readersActive_ || writersActive_);

            --writersWaiting_;
        }

        writersActive_ = 1;
    }
    pthread_mutex_unlock(&lock_);
}

void PalindromeDatabase::unlockWriters()
{
    pthread_mutex_lock(&lock_);
    {
        writersActive_ = 0;

        if (writersWaiting_)
            pthread_cond_signal(&write_);
        else if (readersWaiting_)
            pthread_cond_broadcast(&read_);
    }
    pthread_mutex_unlock(&lock_);
}

Threads are fun- they also make my brain hurt. If I'm wrong, please refrain from giving a direct answer, but guide me in the right direction as this is a homework assignment and I, and other people like me, would surely benefit from getting the solution on our own.

score 2 · Answer 1 · answered Dec 20 '11 at 23:57

2

None of your code is right. You have to release the mutex as soon as you've acquired a read lock. While holding the mutex, you need to arrange to block a writer. While releasing a read lock, you need to arrange to unblock a writer if the last read lock is being released.

In pseudo-code:

read_lock:
1) Acquire mutex.
2) Increment read lock count.
3) Block on condition variable until there are no writers.
4) Release mutex.

read_unlock:
1) Acquire mutex.
2) Decrement read lock count.
3) If read lock count is zero, wake writers.
4) Release mutex.

write_lock:
1) Acquire mutex.
2) If using writer priority, arrange there to be no new readers.
3) Block on condition variable until there are no active readers. (You need to block releasing the mutex otherwise no readers can complete their unlock operations!)

write_unlock:
1) Wake waiting readers/writer (which depends on priority you are implementing)
2) Release mutex.

answered Dec 20 '11 at 23:57

David Schwartz

179,497
17
214
278

@Schwartz: None of it? D: Well, that sucks. Ah well, best get it right now so I learn from my mistakes. Thanks for the pseudocode, it should help me get a correct implementation. – IAE Dec 21 '11 at 00:06
@Schwarz: On a side note, could you tell me what's wrong with the Writer Preferred implementation? What I gathered from this pdf tutorial (*) is that all of what you described in your pseudocode is what the rwlock does internally. (*) www.multicoreinfo.com/research/misc/Pthread-Tutorial-Peter.pdf – IAE Dec 21 '11 at 00:09
You don't allow two readers at the same time, defeating the entire point of a read/write lock. – David Schwartz Dec 21 '11 at 00:14

score 2 · Answer 2 · answered Dec 21 '11 at 00:02

2

By way of hint, I don't think

    // If I'm the last reader, we can let the writers work.
if (--numberOfReadersActive_)
    pthread_cond_signal(&readersActive_);

is doing what it says in the comment. This might also be why you are getting a deadlock.

answered Dec 21 '11 at 00:02

antlersoft

14,636
4
35
55

Reader Preferred and Writer Preferred in Read-Write Multithreading

2 Answers2

Linked