memory synchronization

Question

I have the function display.c :

/* DO NOT EDIT THIS FILE!!!  */

#include <stdio.h>
#include <unistd.h>
#include "display.h"

void display(char *str)
{
    char *p;

    for (p=str; *p; p++)
    {
        write(1, p, 1);
        usleep(100);
    }
}

and display.h is:

/* DO NOT EDIT THIS FILE!!!  */

#ifndef __CEID_OS_DISPLAY_H__
#define __CEID_OS_DISPLAY_H__
void display(char *);
#endif

My task is to use pthreads in order to have the following output:

abcd
abcd
abcd
..
..

Note that I must not edit the file display.c or the file display.c. I have to use mutexes in order to succeed the output that is shown above.

The following block of code is my closest attempt to finally reach the result I want:

#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#include <pthread.h>
#include "display.h"

pthread_t mythread1;
pthread_t mythread2;
pthread_mutex_t m1, m2;

void *ab(void *arg)
{
    pthread_mutex_lock(&m1);            
    display("ab");      
    pthread_mutex_unlock(&m1);
}    

void *cd(void *arg)
{    
    pthread_mutex_lock(&m1);       
    display("cd\n");            
    pthread_mutex_unlock(&m1);      
}

int main(int argc, char *argv[])
{
    pthread_mutex_init(&m1, NULL);
    pthread_mutex_init(&m2, NULL);  

    int i;

    for(i=0;i<10;i++)
    {     
        pthread_create(&mythread1, NULL, ab, NULL);         
        pthread_create(&mythread2, NULL, cd, NULL);    
    }

    pthread_join(mythread1, NULL);
    pthread_join(mythread2, NULL);   
    pthread_mutex_destroy(&m1);
    pthread_mutex_destroy(&m2);
    return EXIT_SUCCESS;    
}

The output of the code above is something like this:

abcd
abcd
abcd
abcd
ababcd
cd
abcd
abcd
abcd
abcd

As you can see "ab" and "cd\n" are never mixed but every time I run the code the output differs. I want to make sure that every time I run this code the output will be:

abcd
abcd 
abcd

for ten times.

I am really stuck with this since I can't find any solution from the things I already know.

Answer 1

A mutex cannot (by itself) solve your problem. It can prevent your two threads from running concurrently, but it cannot force them to take turns.

You can do this with a condition variable in addition to the mutex, or with a pair of semaphores. Either way, the key is to maintain at all times a sense of which thread's turn it is.

Myself, I think the semaphore approach is easier to understand and code. Each semaphore is primarily associated with a different thread. That thread must lock the semaphore to proceed. When it finishes one iteration it unlocks the other semaphore to allow the other thread to proceed, and loops back to try to lock its own semaphore again (which it cannot yet do). The other thread works the same way, but with the semaphore roles reversed. Roughly, that would be:

sem_t sem1;
sem_t sem2;

// ...

void *thread1_do(void *arg) {
    int result;

    do {
        result = sem_wait(&sem1);
        // do something
        result = sem_post(&sem2);
    } while (!done);
}

void *thread2_do(void *arg) {
    int result;

    do {
        result = sem_wait(&sem2);
        // do something else
        result = sem_post(&sem1);
    } while (!done);
}

Semaphore initialization, error checking, etc. omitted for brevity.

Updated to add:

Since you now add that you must use mutexes (presumably in a non-trivial way) the next best way to go is to introduce a condition variable (to be used together with the mutex) and an ordinary shared variable to track which thread's turn it is. Each thread then waits on the condition variable to obtain the mutex, under protection of the mutex checks the shared variable to see whether it is its turn, and if so, proceeds. Roughly, that would be:

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int whose_turn = 1;

// ...

void *thread1_do(void *arg) {
    int result;

    result = pthread_mutex_lock(&mutex);
    while (1) {
        if (whose_turn == 1) {
            // do something
            whose_turn = 2;  // it is thread 2's turn next
        }
        // break from the loop if finished
        result = pthread_cond_broadcast(&cond);
        result = pthread_cond_wait(&cond, &mutex); 
    }
    result = pthread_mutex_unlock(&mutex);
}

void *thread1_do(void *arg) {
    int result;

    result = pthread_mutex_lock(&mutex);
    while (1) {
        if (whose_turn == 2) {
            // do something else
            whose_turn = 1;  // it is thread 1's turn next
        }
        // break from the loop if finished
        result = pthread_cond_broadcast(&cond);
        result = pthread_cond_wait(&cond, &mutex); 
    }
    result = pthread_mutex_unlock(&mutex);
}

Error checking is again omitted for brevity.

Note in particular that when a thread waits on a condition variable, it releases the associated mutex. It reaquires the mutex before returning from the wait. Note also that each checks at each iteration whether it is its turn to proceed. This is necessary because spurious wakeups from waiting on a condition variable are possible.

Answer 2

You can use a conditional variable to take turns between threads:

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int turn = 0;

void *ab(void *arg)
{
    pthread_mutex_lock(&m1);
    while (turn != 0)
       pthread_cond_wait(&cond, &m1);

    display("ab");
    turn = 1;
    pthread_mutex_unlock(&m1);
    pthread_cond_signal(&cond);
}

void *cd(void *arg)
{
    pthread_mutex_lock(&m1);
    while (turn != 1)
       pthread_cond_wait(&cond, &m1);

    display("cd\n");
    turn = 0;
    pthread_mutex_unlock(&m1);
    pthread_cond_signal(&cond);
}

Another problem is, you are joining with the last two pair of threads created in main() thread, which are not necessarily the ones get executed as last. If threads created early are not completed, then you are destroying the mutex m1 while it might be in use and exiting whole process.

Answer 3

Consider this approach to the issue:

for(i=0;i<10;i++)
{     
    ab();
    cd();
}

This achieves your goals completely, given the shown code. The problem with your example is that you effectively prevent any synchronization and that seems to be your goal even!

Assuming that before the output, you actually want to do something useful which takes CPU time, the answer is that you will have to change the code of display(), which is simply not suitable for parallelization. Proper concurrent code is designed to work independent of other code, in particular it shouldn't compete for resources (locks) with other calls and it shouldn't rely on the order it finishes.

In summary, you can't learn much from this, it's a bad example. In order to improve the code (the one you don't want to change, but that's your problem), consider that the resource the different threads compete for is stdout. If they each wrote to their own buffer, you could create the threads, wait for them to finish and only then reorder their results for output.