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.

Answer 1

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.

Answer 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.