Semaphores made from mutexes?

SDL Development
1

Could people who know threads and semaphores take a look at this
implementation and let us know if it has flaws? It’s also in SDL CVS,
but not guaranteed to stay.

See ya!–
-Sam Lantinga, Lead Programmer, Loki Entertainment Software
-------------- next part --------------
/*
SDL - Simple DirectMedia Layer
Copyright © 1997, 1998, 1999, 2000 Sam Lantinga

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

Sam Lantinga
slouken at devolution.com

*/

#ifdef SAVE_RCSID
static char rcsid =
"@(#) $Id: SDL_mutex.c,v 1.2.2.5 2000/03/31 05:22:50 hercules Exp $";
#endif

/* An implementation of counting semaphores using mutexes */

#include “SDL_error.h”
#include “SDL_mutex.h”
#include “SDL_semaphore.h”

struct SDL_semaphore
{
int count;
SDL_mutex *count_lock;
SDL_mutex *wait_lock;
};

SDL_sem *SDL_CreateSemaphore(int initial_value)
{
SDL_sem *sem;

if ( initial_value < 0 ) {
	SDL_SetError("Cannot create semaphore with negative value");
	return(0);
}

sem = (SDL_sem *)malloc(sizeof(*sem));
if ( ! sem ) {
	SDL_OutOfMemory();
	return(0);
}
sem->count = initial_value;

sem->count_lock = SDL_CreateMutex();
sem->wait_lock = SDL_CreateMutex();
if ( ! sem->count_lock || ! sem->wait_lock ) {
	SDL_DestroySemaphore(sem);
	return(0);
}
SDL_LockMutex(sem->wait_lock);

return(sem);

}

void SDL_DestroySemaphore(SDL_sem sem)
{
if ( sem ) {
if ( sem->count_lock ) {
/ Small attempt at releasing threads */
SDL_LockMutex(sem->count_lock);
while ( sem->count < 0 ) {
SDL_UnlockMutex(sem->wait_lock);
++sem->count;
}
SDL_UnlockMutex(sem->count_lock);
SDL_DestroyMutex(sem->count_lock);
}
if ( sem->wait_lock ) {
SDL_DestroyMutex(sem->wait_lock);
}
free(sem);
}
}

void SDL_SemWait(SDL_sem *sem)
{
SDL_bool must_wait;

SDL_LockMutex(sem->count_lock);
if ( sem->count > 0 ) {
	must_wait = SDL_FALSE;
} else {
	must_wait = SDL_TRUE;
}
--sem->count;
SDL_UnlockMutex(sem->count_lock);

if ( must_wait ) {
	SDL_LockMutex(sem->wait_lock);
}

}

SDL_bool SDL_SemTryWait(SDL_sem *sem)
{
SDL_bool must_wait;

SDL_LockMutex(sem->count_lock);
if ( sem->count > 0 ) {
	must_wait = SDL_FALSE;
} else {
	must_wait = SDL_TRUE;
}
if ( ! must_wait ) {
	--sem->count;
}
SDL_UnlockMutex(sem->count_lock);

return !must_wait;

}

int SDL_SemValue(SDL_sem *sem)
{
int value;

if ( sem->count < 0 ) {
	value = 0;
} else {
	value = sem->count;
}
return value;

}

void SDL_SemPost(SDL_sem *sem)
{
SDL_LockMutex(sem->count_lock);
if ( sem->count < 0 ) {
SDL_UnlockMutex(sem->wait_lock);
}
++sem->count;
SDL_UnlockMutex(sem->count_lock);
}

2

Hi !

Could people who know threads and semaphores take a look at this
implementation and let us know if it has flaws? It’s also in SDL CVS,
but not guaranteed to stay.

As for as I know, the answer is “yes, it has a flaw”, sorry.

If initial_value > 1, SDL_SemPost() will (potentially) be called by a
thread that has not originally locked the mutex.
My pthreads book tells me that the behaviour is “undefined” by POSIX;
I haven’t read the standards and can confirm the book’s statement.
Our experience is that this works under Solaris 2.6 anyway, but that it
fails under Linux 2.2 (hang on unlock) or AIX 4.3 (doesn’t unlock).

Besides, I believe that SDL_CreateSemaphore() should leave the wait_lock
in the unlocked state, and that SDL_SemValue() should be protected by
locking count_lock.

If you want to use only the pthreads interface and not rely on realtime
POSIX, I have attached a bit of C++ code that uses pthread_mutex_t and
pthread_cond_t.
The MNOSem is untested (lack of time), just written to show what I
consider a safer approach for waiting. If you look at the code, don’t
be confused by the name MNSem, it’s actually a condition variable and
the name is a historical error on our part.

If I should implement this with mutexes only, I would be in trouble.
Maybe something with a thread, some Unix pipes and select?

Tschuess,
Carsten

-------------- next part --------------
A non-text attachment was scrubbed…
Name: osem.tgz
Type: application/gzip
Size: 1764 bytes
Desc: osem.tgz
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20000419/2b1f416a/attachment.bin

3

If initial_value > 1, SDL_SemPost() will (potentially) be called by a
thread that has not originally locked the mutex.

That’s okay. In fact that is the way it is supposed to work. The first
block on the mutex when count == 0 should block, and then any subsequent
post should unblock the waiting thread.

Am I misunderstanding you?

-Sam Lantinga, Lead Programmer, Loki Entertainment Software
4

If initial_value > 1, SDL_SemPost() will (potentially) be called by a
thread that has not originally locked the mutex.

That’s okay. In fact that is the way it is supposed to work. The first
block on the mutex when count == 0 should block, and then any subsequent
post should unblock the waiting thread.

Am I misunderstanding you?

I assumed that this was intentional.

The problem is that this is not supported by POSIX and that it does not work
with pthreads on Linux. Only the locking thread is allowed to unlock the
mutex.

Tschuess,
Carsten>

-Sam Lantinga, Lead Programmer, Loki Entertainment Software

5

If initial_value > 1, SDL_SemPost() will (potentially) be called by a
thread that has not originally locked the mutex.

That’s okay. In fact that is the way it is supposed to work. The first
block on the mutex when count == 0 should block, and then any subsequent
post should unblock the waiting thread.

Am I misunderstanding you?

I assumed that this was intentional.

The problem is that this is not supported by POSIX and that it does not work
with pthreads on Linux. Only the locking thread is allowed to unlock the
mutex.

Ahh, yes, this is a serious flaw.

From looking at the source to linuxthreads, it appears that fast mutexes
do not check ownership of the lock, but a comment elsewhere in the code
gives me pause:

This is safe because there are no concurrent __pthread_unlock
operations – only the thread that locked the mutex can unlock it.

sigh

Okay, so we need a condition variable implementation
… which is often implemented by semaphores …

Hmm.
A good discussion of condition variables and implementation is available
at: http://www-classic.be.com/aboutbe/benewsletter/volume_III/Issue40.html

Stephane, I don’t have a good solution for you right now.

See ya,
-Sam Lantinga, Lead Programmer, Loki Entertainment Software

6

Hi,

I can only provide a version for the pthread interface (attached). I have
never used the semctl interface.

Wouldn’t it be appropriate to provide system-specific semaphores? Win32
has a native(?) implementation anyway.

Tschuess,
Carsten

-------------- next part --------------

/*

  • glibc-check copied from SDL_mutex.c - cg
    /
    #ifdef linux
    /     Look to see if glibc is available, and if so, what version */
    #include <features.h>

#if (GLIBC == 2) && (GLIBC_MINOR == 0)
#warning Working around a bug in glibc 2.0 pthreads
#undef SDL_USE_PTHREADS
/* The bug is actually a problem where threads are suspended, but don’t
wake up when the thread manager sends them a signal. This is a problem
with thread creation too, but it happens less often. :-/
We avoid this by using System V IPC for mutexes.
/
#endif / glibc 2.0 /
#endif / linux */

#ifdef SDL_USE_PTHREADS

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

#include “SDL_semaphore.h”
#include “SDL_error.h”
#include “SDL_mutex.h”

struct SDL_semaphore
{
pthread_mutex_t count_lock;
pthread_cond_t wait_cond;
Uint32 count;
Uint32 max;
};

SDL_sem SDL_CreateSemaphore(Uint32 initial_value)
{
SDL_sem sem;

if ( initial_value < 0 ) {
    SDL_SetError("Cannot create semaphore with negative value");
    return(0);
}

sem = (SDL_sem *)malloc(sizeof(*sem));
if ( ! sem ) {
    SDL_OutOfMemory();
    return(0);
}
sem->count = initial_value;
sem->max   = initial_value;
pthread_mutex_init( &sem->count_lock, NULL );
pthread_cond_init( &sem->wait_cond, NULL );

return sem;

}

void SDL_DestroySemaphore(SDL_sem *sem)
{
Uint32 holding;
if ( sem )
{
holding = 0;
pthread_mutex_lock( &sem->count_lock );
while ( holding < sem->max )
{
pthread_cond_wait( &sem->wait_cond, &sem->count_lock );
sem->count–;
holding++;
}
pthread_cond_destroy ( &sem->wait_cond );
pthread_mutex_unlock( &sem->count_lock );
pthread_mutex_destroy( &sem->count_lock );
}
}

void SDL_SemWait(SDL_sem *sem)
{
SDL_bool must_wait;

pthread_mutex_lock( &sem->count_lock );
while ( sem->count <= 0 ) {
    pthread_cond_wait( &sem->wait_cond, &sem->count_lock );
}
--sem->count;
pthread_mutex_unlock( &sem->count_lock );

}

SDL_bool SDL_SemTryWait(SDL_sem *sem)
{
SDL_bool must_wait;

pthread_mutex_lock( &sem->count_lock );
if ( sem->count > 0 ) {
    must_wait = SDL_FALSE;
    --sem->count;
} else {
    must_wait = SDL_TRUE;
}
pthread_mutex_unlock( &sem->count_lock );

return !must_wait;

}

Uint32 SDL_SemValue(SDL_sem *sem)
{
Uint32 value;

pthread_mutex_lock( &sem->count_lock );
if ( sem->count < 0 ) {
    value = 0;
} else {
    value = sem->count;
}
pthread_mutex_unlock( &sem->count_lock );
return value;

}

void SDL_SemPost(SDL_sem *sem)
{
pthread_mutex_lock( &sem->count_lock );
++sem->count;
pthread_cond_signal ( &sem->wait_cond );
pthread_mutex_unlock( &sem->count_lock );
}

#else

#error sorry I dont know the semctl interface

#endif