[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Semaphore

Posted on 2006-05-26
7
Medium Priority
?
869 Views
Last Modified: 2008-02-01
Hi all,
 I have 2 threads : thread1 and thread2. How can I use semaphore to make sure thread1 will always run before thread2? Thanks a lot for details and explainations.
0
Comment
Question by:valleytech
5 Comments
 
LVL 45

Accepted Solution

by:
sunnycoder earned 1000 total points
ID: 16772215
Assuming
P(Semaphore s)
{
  await s > 0, then s := s-1; /* must be atomic once s > 0 is detected */
}

V(Semaphore s)
{
  s := s+1;   /* must be atomic */
}

sem1 = -1

Thread 1
         V(sem1)   sem1=0
             operations
         V(sem1)  sem1=1

Thread 2
        P(sem1) sem1>0 only if thread 1 has finished
             operations
        V(sem1)
0
 
LVL 2

Assisted Solution

by:Razor2k5
Razor2k5 earned 1000 total points
ID: 16772431
Here is an example:

The code implements the problem of N Missionaries and N Cannibals that whants to cross the river with a boat. The problem is about synchronize the threads which are the Missionaries and Cannibals. Here we will have 2 condition variables which will represent the missionaries and cannibals that could be loaded on the boat based on the condition: the number of cannibals in a boat cannot be greater than the number of missionaries.

The condition variables work just like semaphores, but the concept of having semaphores is old. If I remember correct, Dijkstra introduced the concept in the '60s and semaphores are a bit rudimentary regarding mutual exclussion of the "paralel" threads. I quoted the paralel word because we all know that if you have a single core CPU then at a certain time only one process is running. The "paralel" view is a virtual mechanism provided by Operating System.

How does condition variable works?

The mechanism is very simple: Lock and Unlock

When you whant to block threads use a condition variable that will solve also the race condition for that shared resource. So, if you whant to block all threads that have to modify a variable then all you have to do is to call:

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

These functions atomically release mutex and cause the calling thread to block on the condition variable cond; atomically here means "atomically with respect to access by another thread to the mutex and then the condition variable". That is, if another thread is able to acquire the mutex after the about-to-block thread has released it, then a subsequent call to pthread_cond_signal() or pthread_cond_broadcast() in that thread behaves as if it were issued after the about-to-block thread has blocked.Upon successful return, the mutex has been locked and is owned by the calling thread.

The code:

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

int numM = 0, numC = 0;
pthread_mutex_t mutex;
pthread_cond_t missWait, canWait;

void RowBoat(const int m, const int c){
      printf("Boat with: %d missionaries and %d cannibals\n",m,c);
}

void *MissionaryArrives(void *arg){
      pthread_mutex_lock(&mutex);
      
LABEL0:      printf("M %d - %d\n",numM,numC);
      
      if(numC<=1){
            printf("M\n");
            numM++;
            pthread_cond_broadcast(&missWait);
      }
      else{
            printf("M - sleep\n");
            pthread_cond_wait(&missWait, &mutex);
            printf("M - woke up!\n");
            goto LABEL0;
      }
      if((numM==3 && numC==0)||(numM==2 && numC==1)||(numM==0 && numC==3)){
            RowBoat(numM,numC);
            numM=0;
            numC=0;
            pthread_cond_broadcast(&missWait);
            pthread_cond_broadcast(&canWait);
      }

      
      pthread_mutex_unlock(&mutex);
}

void *CannibalArrives(void *arg){
      pthread_mutex_lock(&mutex);
      
LABEL1:      printf("C %d - %d\n",numM,numC);
      if((numM<=2 && numC==0) || (numM==0)){
            printf("C\n");
            numC++;
            pthread_cond_broadcast(&canWait);
      }
      else{
            printf("C - sleep\n");
            pthread_cond_wait(&canWait, &mutex);
            printf("C - woke up!\n");
            goto LABEL1;
      }
      if((numM==3 && numC==0)||(numM==2 && numC==1)||(numM==0 && numC==3)){
            RowBoat(numM,numC);
            numM=0;
            numC=0;
            pthread_cond_broadcast(&missWait);
            pthread_cond_broadcast(&canWait);
      }

      
      pthread_mutex_unlock(&mutex);
}

int main(int argc, char **argv){
      if(argc==2){
            int n,i;
            pthread_t th_m[100], th_c[100];
            n=atoi(argv[1]);
            if(n>100){
                  printf("Number of missionaries/cannibals cannot exceed 100.\n");
                  exit(1);
            }
            for(i=0;i<n;i++){
                  pthread_create(&th_c[i], NULL, CannibalArrives, NULL);
                  pthread_create(&th_m[i], NULL, MissionaryArrives, NULL);
                  
            }
            /*for(i=0;i<cannibals;i++){
                  pthread_create(&th_c[i], NULL, CannibalArrives, NULL);
            }*/
            for(i=0;i<n;i++){
                  pthread_join(th_m[i],NULL);
                  pthread_join(th_c[i],NULL);
            }
            /*for(i=0;i<cannibals;i++){
                  pthread_join(th_c[i],NULL);
            }*/
      }
      else{
            printf("usage: %s <number of missionaries>/<number of cannibals>\n",argv[0]);
      }
      printf("%d - %d\n",numM,numC);
      return 0;
}
0
 

Author Comment

by:valleytech
ID: 16772713
I need to read carefully. SO i give each 250 hihi. Thanks a lot.
0
 

Author Comment

by:valleytech
ID: 16820508
Hi sunnycoder,
 I read your psedocode but i do'nt get it. I am reading the dinasour OS book about semaphore , but i don't get it too.
 Could you please explain me how thread1 always run before thread2 in that case? thanks
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 16851066
In sunnycoder's pseudo code, try to visualize what happens.

thread1 and thread2 are started. thread2 blocks untill sem1 > 0 ... and this only happens when thread1 has finished. So, thread2 starts when thread1 is finished.
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question