CODEWITHSUNDEEP
cpthreadsmutex
Dima00782
Dima00782

Reputation: 171

Producer consumer only mutexes

I can not think of a logical solution to the problem. There are two streams - the main and child. They must in turn display a message like this:

Parent

Child

Parent

... and so forth 10 times each.

You can only use pthread mutexes and do not use idle cycle. Idle cycle is allowed only during the initialization phase. Who - anyone know of a nice solution?

Upvotes: 1

Views: 853

Answers (3)

Deepthought
Deepthought

Reputation: 2931

What you need is 2 threads (parent and child) allowing each other to execute.

This is the pseudo-code, you are free to use any locking primitives you want.

//global variables and initializations
parent_lock = UNLOCKED; //This allows your first print to be from parent
child_lock = LOCKED;

parent_counter = 0; //to count the number of prints 
child_counter = 0;

//Parent should do this                  |        //Child should do this
while(1)                                 |while(1)
{                                        |
spin: if(parent_lock == LOCKED)          |spin: if(child_lock == LOCKED)
      {                                  |      {
         //spin till child unlocks you   |      //spin till parent unlocks you
          goto spin;                     |          goto spin;
      }                                  |      }
      else                               |      else
      {                                  |      {
          print("PARENT");               |          print("CHILD");
          parent_counter++;              |          child_counter++;
          //lock yourself allow the other|          //lock yourself allow the other
          parent_lock = LOCKED;          |          child_lock = LOCKED;
          child_lock = UNLOCKED;         |          parent_lock = UNLOCKED;
          if (parent_counter == 10)      |          if (child_counter == 10)
          {                              |          {
              break;//printed 10 times   |              break;     
          }                              |          }
       }                                 |       }
}                                        |}

//PARENT has printed 10times wait for    |//CHILD has printed 10times wait for 
//child                                  |// parent

PS: *I assume you are free to spin on a lock which is what I have done, if that's not the case you need to modify the above algorithm to do sleep and wake up instead of spin.
*You can choose pthread lock primitives to initialize the parent_lock and child_lock.
*For the program to be correct we need to assume that assignment statements are atomic Ex: child_lock = LOCKED statement is atomic.

Extremely Important: See the order in parent:

parent_lock = LOCKED;
child_lock = UNLOCKED;

and its counter part in the child thread. If you interchange this two lines then you may DEADLOCK!!!!, because of a sequence of mixed execution by parent and child(due to OS scheduler).

Upvotes: 0

Taylor Brandstetter
Taylor Brandstetter

Reputation: 3623

I think I got it... the big hint is "only idle can be done during the initialization phase."

First of all, a restriction on mutexes is that you must unlock in the same thread that you locked in. So each unlock() in a thread must be paired with a lock(), and we must have an equal number of them (or else we would get a deadlock).

This means that the only way we can prevent a thread from printing multiple times is to ensure that each thread ALWAYS OWNS AT LEAST ONE MUTEX. If thread B at any time released all its mutexes, and then the CPU switched to thread A, it could just run indefinitely.

We can't do this with 2 mutexes without deadlock, but we CAN do it with 3.

Parent thread:

    bool initDone = false;
    lock(m1);
    lock(m2);
    spawnChild();
    while (!initDone)
        sleep();
    while (true) {
        print("Parent");
        unlock(m1);
        lock(m3);
        unlock(m2);
        lock(m1);
        unlock(m3);
        lock(m2);
    }

Child thread:

    lock(m3);
    initDone = true;
    while (true) {
        lock(m1);
        unlock(m3);
        lock(m2);
        print("Child");
        unlock(m1);
        lock(m3);
        unlock(m2);
    }

We start with parent owning locks 1 and 2, and child owning 3. Then they take turns releasing and acquiring locks: parent gives lock 1 to child, child gives lock 3 to parent, parent gives lock 2 to child, child gives lock 1 to parent, parent gives lock 3 to child, child gives lock 2 to parent, repeat.

An interesting problem; I bet you see the appeal of conditional variables now, as they trivialize this.

Upvotes: 3

twalberg
twalberg

Reputation: 62369

You might need to be more specific regarding the requirements. If the toggling output is the only actual requirement, then something like this ought to work (somewhat pseudo-codey):

const char *strings[2] = { "Parent", "Child" };
pthread_mutex_t m; // needs to be properly initialized, of course
int which = 0;

thread_func()
{ while (1)
  { lock(&m);
    printf("%s\n", strings[which])
    which = !which;
    unlock(&m);
  }
}

You can spawn as many threads as you want, and the output will continue to alternate. However, the threads won't necessarily interleave one iteration at a time. Trying to get proper single-iteration interleaving with only a mutex and without a yield function (which pthreads doesn't specify) is a bit more difficult...

Upvotes: 0

Related Questions