4
\$\begingroup\$

I'm a Pthreads newbie and I've been giving myself a challenge: I want to have a resource that multiple threads can access at the same time as read. However, if a thread wants to write, then this need to be exclusive.

Now, I know that there are read/write locks designed specifically for this purpose. I would not do this in production code; this is just to learn. For simplicity, I assume there is only one thread that can write (but of course, multiple that read).

I have come up with two version. The first one does not use signals, the second one does. I tested it a little bit and both seem to work. However, multi-thread programming is tricky.

Could someone review the two versions and let me know whether there might be a bug that my tests missed?

Version 1

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string>

class limited_resource
{
public:
             limited_resource()
                {
                pthread_mutex_init(&d_mutext, NULL);
                d_write_request = false;
                d_nreading = 0;
                }

    virtual ~limited_resource()
                {
                pthread_mutex_destroy(&d_mutext);
                }

    void read(int thread_id)
        {
        // Do a stupid waiting
        while(true)
            {
            pthread_mutex_lock(&d_mutext);
            if(!d_write_request)
                {
                d_nreading++;
                break;
                }
            pthread_mutex_unlock(&d_mutext);

            sleep(1);
            }
        pthread_mutex_unlock(&d_mutext);

        // Do the actual reading
        char data[4];

        for(int ii = 0; ii < 4; ++ii)
            {
            data[ii] = d_data[ii];
            sleep(1); // Super slow reading to create bugs on purpose
            }

        printf("Thread %d read \"%c%c%c%c\"\n", thread_id, data[0], data[1], data[2], data[3]);

        // Decrement the number of readers
        pthread_mutex_lock(&d_mutext);
        d_nreading--;
        pthread_mutex_unlock(&d_mutext);
        }

    void write(const char *str)
        {
        pthread_mutex_lock(&d_mutext);
        d_write_request = true;
        pthread_mutex_unlock(&d_mutext);

        // Do a stupid waiting
        while(true)
            {
            pthread_mutex_lock(&d_mutext);
            if(d_nreading == 0)
                break;
            pthread_mutex_unlock(&d_mutext);

            sleep(1);
            }
        pthread_mutex_unlock(&d_mutext);

        // Do the work
        printf("Writing\n");
        for(int ii = 0; ii < 4; ++ii)
            {
            d_data[ii] = str[ii];
            sleep(1); // Super slow writing to create bugs on purpose
            }

        // Release the writing
        pthread_mutex_lock(&d_mutext);
        d_write_request = false;
        pthread_mutex_unlock(&d_mutext);
        }

protected:
    pthread_mutex_t d_mutext;

    int d_nreading;
    bool d_write_request;

    char d_data[4];
};


limited_resource lr;


void* thread_function(void* input)
{
    int thread_id = *((int*)input);

    while(true)
        {
        sleep(thread_id + 1);
        lr.read(thread_id);
        }

    return NULL;
}

int main(int argc, char **argv)
{
    int N = 10;

    pthread_t tIDs[N];
    int vals[N];

    for(int ii = 0; ii < N; ++ii)
        {
        vals[ii] = ii;
        pthread_create(tIDs + ii, NULL, thread_function, vals + ii);
        }

    char str[80];
    while(true)
        {
        scanf("%s", str);
        lr.write(str);
        }

    return 0;
}

Version 2

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string>

class limited_resource
{
public:
             limited_resource()
                {
                pthread_mutex_init(&d_mutext, NULL);

                d_write_request = false;
                pthread_cond_init(&d_write_request_false, NULL);

                d_nreading = 0;
                pthread_cond_init(&d_nreading_zero, NULL);
                }

    virtual ~limited_resource()
                {
                pthread_mutex_destroy(&d_mutext);
                pthread_cond_destroy(&d_write_request_false);
                pthread_cond_destroy(&d_nreading_zero);
                }

    void read(int thread_id)
        {
        // Wait
        pthread_mutex_lock(&d_mutext);
        while(d_write_request)
            pthread_cond_wait(&d_write_request_false, &d_mutext);
        d_nreading++;
        pthread_mutex_unlock(&d_mutext);

        // Do the actual reading
        char data[4];

        for(int ii = 0; ii < 4; ++ii)
            {
            data[ii] = d_data[ii];
            sleep(1); // Super slow reading to create bugs on purpose
            }

        printf("Thread %d read \"%c%c%c%c\"\n", thread_id, data[0], data[1], data[2], data[3]);

        // Decrement the number of readers
        pthread_mutex_lock(&d_mutext);
        d_nreading--;
        if(d_nreading == 0)
            pthread_cond_signal(&d_nreading_zero);
        pthread_mutex_unlock(&d_mutext);
        }

    void write(const char *str)
        {
        pthread_mutex_lock(&d_mutext);
        d_write_request = true;
        while(d_nreading != 0)
            pthread_cond_wait(&d_nreading_zero, &d_mutext);
        pthread_mutex_unlock(&d_mutext);

        // Do a stupid waiting
        while(true)
            {
            pthread_mutex_lock(&d_mutext);
            if(d_nreading == 0)
                break;
            pthread_mutex_unlock(&d_mutext);

            sleep(1);
            }
        pthread_mutex_unlock(&d_mutext);

        // Do the work
        printf("Writing\n");
        for(int ii = 0; ii < 4; ++ii)
            {
            d_data[ii] = str[ii];
            sleep(1); // Super slow writing to create bugs on purpose
            }

        // Release the writing
        pthread_mutex_lock(&d_mutext);
        d_write_request = false;
        pthread_cond_broadcast(&d_write_request_false);
        pthread_mutex_unlock(&d_mutext);
        }

protected:
    pthread_mutex_t d_mutext;

    int d_nreading;
    pthread_cond_t d_nreading_zero;

    bool d_write_request;
    pthread_cond_t d_write_request_false;

    char d_data[4];
};


limited_resource lr;


void* thread_function(void* input)
{
    int thread_id = *((int*)input);

    while(true)
        {
        sleep(thread_id + 1);
        lr.read(thread_id);
        }

    return NULL;
}

int main(int argc, char **argv)
{
    int N = 10;

    pthread_t tIDs[N];
    int vals[N];

    for(int ii = 0; ii < N; ++ii)
        {
        vals[ii] = ii;
        pthread_create(tIDs + ii, NULL, thread_function, vals + ii);
        }

    char str[80];
    while(true)
        {
        scanf("%s", str);
        lr.write(str);
        }

    return 0;
}
\$\endgroup\$

migrated from stackoverflow.com Aug 28 '12 at 12:59

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ This is a huge code dump. You're right for asking, because testing almost by definition won't find bugs in concurrency. But the answer to this is probably "take an OS class". As a quick and dirty answer, as long as you have one mutex per resource that you must obtain before writing, you won't have race conditions. But you could easily have problems with "starvation"; a thread that doesn't get to write ever, or "deadlocks"; where each is waiting for the other to give up a resource. People still don't know how to solve these generally, so you'd really need to study it properly to do it right. \$\endgroup\$ – Robert Nov 13 '11 at 1:13
3
\$\begingroup\$

You forgot to remove the "stupid waiting" from version 2. Otherwise, it looks good. Not particularly efficient, but correct.

You can and should remove this chunk of code from version 2. The code before it already does this:

    // Do a stupid waiting
    while(true)
        {
        pthread_mutex_lock(&d_mutext);
        if(d_nreading == 0)
            break;
        pthread_mutex_unlock(&d_mutext);

        sleep(1);
        }
    pthread_mutex_unlock(&d_mutext);

Here's an optimization for you. Change:

    if(d_nreading == 0)
        pthread_cond_signal(&d_nreading_zero);

to

    if( (d_nreading == 0) && d_write_request)
        pthread_cond_signal(&d_nreading_zero);

Reader/writer locks are based on the assumption that reading is frequent and writing is rare. So the common case would be that there's no writing. Your code makes an extra call into the pthread library for each read unlock, even that call is not needed.

\$\endgroup\$
  • \$\begingroup\$ Both versions are definitely not correct. \$\endgroup\$ – Employed Russian Nov 13 '11 at 1:36
  • \$\begingroup\$ @EmployedRussian Can you be just a bit more specific? (Perhaps you missed the problem statement that said it was okay to assume only one writing thread?) \$\endgroup\$ – David Schwartz Nov 13 '11 at 1:38
  • \$\begingroup\$ On the contrary: the problem statement says "However, if a thread wants to write, then this need to be exclusive." Just like for reader/writer locks, this means multiple writers are not allowed simultaneous access, not that there could only exist a single writer. \$\endgroup\$ – Employed Russian Nov 13 '11 at 1:47
  • \$\begingroup\$ @EmployedRussian I understood that to mean that a write lock means there are no outstanding (or new) read locks. "For simplicity, I assume there is only one thread that can write (but of course, multiple ones that read)." \$\endgroup\$ – David Schwartz Nov 13 '11 at 2:10
  • \$\begingroup\$ Thanks everyone. I've written the version 3, which should support multiple writers. It seems OK so far. I've also added David's optimization; I tried to add it to write routine but it is not correct (it results in the program freezing up); search for "cannot be". Thanks again -- Tony \$\endgroup\$ – Antoine Bruguier Nov 14 '11 at 0:47
2
\$\begingroup\$

Both versions are buggy: they allow multiple writers in at once!

Consider what happens if there are no readers, and two writers call "write" at the same time. They will both set d_write_request to true, wait for readers to finish (there are none) and start writing at the same time.

Your testing conveniently neglects to test for multiple writers.

Also please don't call mutex a mutext. The mutex stands for "mutual exclusion", there is no T after E there.

\$\endgroup\$
  • \$\begingroup\$ Ah, I missed that. Still, it's trivial to write code that doesn't make such simplifying assumption. I am not sure what OP stands to learn from "here is my simplified, inefficient implementation" (actually two imeplmentations) "of reader/writer lock that only solves half of the problem". \$\endgroup\$ – Employed Russian Nov 13 '11 at 4:22
  • \$\begingroup\$ I agree. It's completely trivial to fix. It should at least, if nothing else, have code to assert in that case. \$\endgroup\$ – David Schwartz Nov 13 '11 at 4:33
  • \$\begingroup\$ Thanks for your reply. It is not trivial to fix for me. I will give it a try. \$\endgroup\$ – Antoine Bruguier Nov 14 '11 at 0:46
  • \$\begingroup\$ You could trivially fix it by just having the writer hold the mutex while it writes. \$\endgroup\$ – David Schwartz Aug 28 '12 at 13:47

Your Answer

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