CODEWITHSUNDEEP
cmultithreadingsynchronizationsemaphorecondition-variable
Osama Ahmad
Osama Ahmad

Reputation: 2096

Why using semaphores instead of condition variables hang sometimes in this problem?

I'm writing a code for an assignment for an operating systems course.

This is the file I'm editing.

This is the test code for the solution.

Note: looking at these files isn't necessary to understand the code.

The assignment asks for a way to communicate between threads. There are 3 types of threads: male, female and matchmaker.

I have 3 functions: male(thread_id), female(thread_id) and matchmaker(thread_id).

A male, female or a matchmaker thread should sleep until two threads of the other two types are available. for example a male thread should sleep if there is no a single female thread running or if there is not a single matchmaker thread running. If the three types are present, the matchmaker will match the male and the female threads and then the 3 threads should exit.

The test code creates 10 male threads, 10 female threads and 10 matchmaker threads and expects one of each type to communicate together then exits.

Note: the function code that handles each type of thread is almost identical.

I solved the problem using condition variables and it's working fine. Here is the solution:

struct lock *lock = NULL;

struct cv *male_cv = NULL;
struct cv *female_cv = NULL;
struct cv *matchmaker_cv = NULL;

int male_count = 0;
int female_count = 0;
int matchmaker_count = 0;

void whalemating_init() {
    lock = lock_create("whalemating lock");

    male_cv = cv_create("male");
    female_cv = cv_create("female");
    matchmaker_cv = cv_create("matchmaker");

    male_count = 0;
    female_count = 0;
    matchmaker_count = 0;
}

/*
 * Called by the driver during teardown.
 */

void
whalemating_cleanup() {

    lock_destroy(lock);
    lock = NULL;

    cv_destroy(male_cv);
    cv_destroy(female_cv);
    cv_destroy(matchmaker_cv);

    male_cv = NULL;
    female_cv = NULL;
    matchmaker_cv = NULL;
}

void
male(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling male_start and male_end when
     * appropriate.
     */

    male_start(index);

    lock_acquire(lock);
    
    if (matchmaker_count > 0 && female_count > 0) {
        cv_signal(matchmaker_cv, lock);
        cv_signal(female_cv, lock);
    } else {
        male_count++;
        cv_wait(male_cv, lock);
        male_count--;
    }
        
    lock_release(lock);

    male_end(index);    

    return;
}

void
female(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling female_start and female_end when
     * appropriate.
     */

    female_start(index);

    lock_acquire(lock);
    
    if (matchmaker_count > 0 && male_count > 0) {
        cv_signal(matchmaker_cv, lock);
        cv_signal(male_cv, lock);
    } else {
        female_count++;
        cv_wait(female_cv, lock);
        female_count--;
    }
        
    lock_release(lock);

    female_end(index);  

    return;
}

void
matchmaker(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling matchmaker_start and matchmaker_end
     * when appropriate.
     */

    matchmaker_start(index);
    
    lock_acquire(lock);
    
    if (male_count > 0 && female_count > 0) {
        cv_signal(male_cv, lock);
        cv_signal(female_cv, lock);
    } else {
        matchmaker_count++;
        cv_wait(matchmaker_cv, lock);
        matchmaker_count--;
    }
        
    lock_release(lock);

    matchmaker_end(index);  

    return;
}

And here is the one using semaphores that doesn't always work (works fine on some runs and hangs on ther runs):

struct semaphore *male_sem = NULL;
struct semaphore *female_sem = NULL;
struct semaphore *matchmaker_sem = NULL;

/*
 * Called by the driver during initialization.
 */

void whalemating_init() {
    // sem_create(sem_name, sem_initial_value);
    male_sem = sem_create("male", 0);
    female_sem = sem_create("female", 0);
    matchmaker_sem = sem_create("matchmaker", 0);
}

/*
 * Called by the driver during teardown.
 */

void
whalemating_cleanup() {
    sem_destroy(male_sem);
    sem_destroy(female_sem);
    sem_destroy(matchmaker_sem);

    male_sem = NULL;
    female_sem = NULL;
    matchmaker_sem = NULL;
}

void
male(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling male_start and male_end when
     * appropriate.
     */

    male_start(index);

    V(male_sem);
    V(male_sem);
    P(female_sem);
    P(matchmaker_sem);

    male_end(index);    

    return;
}

void
female(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling female_start and female_end when
     * appropriate.
     */

    female_start(index);
    
    V(female_sem);
    V(female_sem);
    P(male_sem);
    P(matchmaker_sem);

    female_end(index);  

    return;
}

void
matchmaker(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling matchmaker_start and matchmaker_end
     * when appropriate.
     */

    matchmaker_start(index);

    V(matchmaker_sem);
    V(matchmaker_sem);
    P(male_sem);
    P(female_sem);

    matchmaker_end(index);  

    return;
}

The P function takes a semaphore, decrements its count if it's bigger than 0, or sleeps if the count is 0.

The V function increments the count, and wakes up a sleeping thread if there is any.

In the latter solution, each thread increments its semaphore twice because it's gonna be decremented once by each of the other two threads. Then calls P on each of the other two semaphores. If the count of both semaphores is greater than 0, the function continues till the end. If at least one of them has a count of 0, the thread sleeps until the count of that semaphore goes up.

What's wrong with the latter solution?

Edit

This code with semaphores works fine:

struct semaphore *male_sem = NULL;
struct semaphore *female_sem = NULL;
struct semaphore *matchmaker_sem = NULL;

/*
 * Called by the driver during initialization.
 */

void whalemating_init() {
    // sem_create(sem_name, sem_initial_value);
    male_sem = sem_create("male", 0);
    female_sem = sem_create("female", 0);
    matchmaker_sem = sem_create("matchmaker", 0);

}

/*
 * Called by the driver during teardown.
 */

void
whalemating_cleanup() {
    sem_destroy(male_sem);
    sem_destroy(female_sem);
    sem_destroy(matchmaker_sem);

    male_sem = NULL;
    female_sem = NULL;
    matchmaker_sem = NULL; 
}

void
male(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling male_start and male_end when
     * appropriate.
     */

    male_start(index);

    P(male_sem);
    V(matchmaker_sem);

    male_end(index);    

    return;
}

void
female(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling female_start and female_end when
     * appropriate.
     */

    female_start(index);
    
    P(female_sem);
    V(matchmaker_sem);

    female_end(index);  

    return;
}

void
matchmaker(uint32_t index)
{
    (void)index;
    /*
     * Implement this function by calling matchmaker_start and matchmaker_end
     * when appropriate.
     */

    matchmaker_start(index);

    V(male_sem);
    V(female_sem);
    P(matchmaker_sem);
    P(matchmaker_sem);

    matchmaker_end(index);  

    return;
}

Why does this one work and the other doesn't?

Upvotes: 1

Views: 131

Answers (1)

Vroomfondel
Vroomfondel

Reputation: 2898

In the working semaphore solution there never exists the situation where a matchmaker has left the semaphore access without at least one male and one female also having left behind the synchronisation code: when the matchmaker return from his second P(matchmaker_sem) there is guaranteed to be one male and one female past their final V(matchmaker_sem) so the matchmaker can do his magic.

The same can't be said of your solution: As soon as one male has signalled his very first V(male_sem) and one female her V(female_sem) the matchmaker can run through his two necessary P(male_sem) P(female_sem) and exit, while the male and the female still linger inside the synchronisation code. While the total count of semaphore accesses cancels out and all female, male and matchmakers will eventually terminate, they don't do so in any synchronized way, i.e. their states do not match any intended time sequence and the synchronisation code is just an arbitrary hold-up for some of the functions. I think that the code outside of these functions stops execution of the program, not the waiting on the semaphores.

PS: if the xy_end(index) functions should indicate the necessary state change in the three participants, then the second code is also broken and executes just because the scheduler has only a slim chance of hitting the time window between V(matchmaker_sem) and female/male_end(index).

PPS: maybe your misconception roots in V(semaphore). This instruction does not block!

Upvotes: 1

Related Questions