Semaphore algorithm

This is a discussion on Semaphore algorithm within the C Programming forums, part of the General Programming Boards category; I am trying to implement the following algorithm as a semaphore. The semaphore struct will be passed as a parameter ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    70

    Semaphore algorithm

    I am trying to implement the following algorithm as a semaphore. The semaphore struct will be passed as a parameter to semWait and semSigal.

    - Are the mutexes responsible for protecting the critical sections?
    - How could i test my semaphore implementation?

    I would like to know if i am on the right track before i go any further.

    Algorithm:

    Code:
    procure(Semaphore *semaphore)
    {
        begin_critical_section(semaphore);  // make the following concurrency-safe
        while (semaphore->value <= 0)
    	wait_for_vacate(semaphore);     // wait for signal from vacate()
        semaphore->value--;                 // claim the Semaphore
        end_critical_section(semaphore);
    }
    
    vacate(Semaphore *semaphore)
    {
        begin_critical_section(semaphore);  // make the following concurrency-safe
        semaphore->value++;                 // release the Semaphore
        signal_vacate(semaphore);           // signal anyone waiting on this
        end_critical_section(semaphore);
    }
    My code:

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <pthread.h>
    #include <unistd.h>
    
    typedef struct semaphore
    {
        int count;
        pthread_cond_t got_request;
        pthread_mutex_t request_mutex;
        pthread_mutex_t count_mutex;
    } semaphore;
    
    semaphore init_semaphore(semaphore *s)
    {
        s->count = 0;
    }
    
    semaphore destroy_semaphore(semaphore *s)
    {
      
    }
    
    void semWait(semaphore *s)
    {
        pthread_mutex_lock(&(s->request_mutex));
            
        if (s->count < 0)
        {                
       	pthread_cond_wait(&(s->got_request), &(s->request_mutex));
            s->count--;                
        }
    		
        pthread_mutex_unlock(&(s->request_mutex));
    	
    }
    
    void semSignal(semaphore *s)
    {
    
        pthread_mutex_lock(&(s->request_mutex));
    	
        if (s->count <= 0)
        {
    	pthread_cond_signal(&(s->got_request));
    	s->count++;
        }
    
        pthread_mutex_unlock(&(s->request_mutex));
    	
    }
    
    int main(void)
    {
    }
    Last edited by erasm; 09-20-2009 at 09:37 AM.

  2. #2
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Well, yes, mutexes will guarantee that the critical section will be "protected". If used correctly of course.

    You have implemented semWait. Lets see if it would work correctly:
    1) Two threads call the function the same time.
    2) The first reads the if statement. Then the second reads the if statement
    3) Both will pass the if statement, since s->count will be higher than 0
    So, you will have a bug here!
    You want:
    Code:
    void semWait(semaphore *s)
    {
            pthread_mutex_lock(&(s->request_mutex));
            if (s->count < 0)
            {                
                    pthread_cond_wait(&(s->got_request), &(s->request_mutex));
                    s->count--;
            }
            pthread_mutex_unlock(&(s->request_mutex));
    }

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    70
    And the semSignal function:

    Code:
    void semSignal(semaphore *s)
    {
    
        pthread_mutex_lock(&(s->request_mutex));
    	
        if (s->count <= 0)
        {
    		pthread_cond_signal(&(s->got_request));
    		s->count++;
        }
    
        pthread_mutex_unlock(&(s->request_mutex));
    	
    }
    Could someone provide a simple intuitive example implementation of my functions or pseudo code implementation?
    Last edited by erasm; 09-20-2009 at 09:49 AM.

  4. #4
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Also the count has to be outside the if statement.

    Look at this

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Semaphore Question
    By azamsharp1 in forum C Programming
    Replies: 4
    Last Post: 10-30-2005, 08:01 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21