From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,3ccb707f4c91a5f2
X-Google-Attributes: gid103376,public
From: Hannes Haug <haugha@informatik.uni-tuebingen.de>
Subject: Re: Fast locking (Was Re: Java vs Ada 95)
Date: 1996/11/06
Message-ID: <uvvk9rz9vte.fsf@chaq.informatik.uni-tuebingen.de>#1/1
X-Deja-AN: 194868250
sender: haugha@chaq.informatik.uni-tuebingen.de
references: <325BC3B3.41C6@hso.link.com>
organization: Uni Tuebingen
newsgroups: comp.lang.ada
Date: 1996-11-06T00:00:00+00:00
List-Id: <comp.lang.ada>


geert@fozzie.sun3.iaf.nl (Geert Bosch) writes:

> I meant a lock that uses some form of busy-waiting instead of
> blocking. Such a lock can be implemented using atomic test-and-set 
> or atomic swap. Although these locks are not efficient for long
> waits because of wasted CPU time and possible starving of other
> tasks, for resources that are only locked for a short time, like
> the ref-counted bounded string example, they are the best solution.

You can yield the task if the mutex is already locked.
Untested pseudo gnu c for sparc:

typedef struct mutex {
  volatile int lock;
} mutex_t;

static void
mutex_init (mutex_t *mp)
{
  mp->lock = 0;
}

static void
mutex_unlock (mutex_t *mp)
{
  mp->lock = 0;
}

static int
mutex_trylock (mutex_t *mp)
{
  int old_lock;
  asm volatile ("ldstub [%1],%0" : "=r" (old_lock) : "r" (&mp->lock));
  return old_lock;
}

static void
mutex_lock (mutex_t *mp)
{
  while (mutex_trylock (mp) != 0)
    thread_yield ();
}


typedef struct semaphore {
  mutex_t mutex;
  volatile int count;
} semaphore_t;

static void
semaphore_init (semaphore_t *sp, int count)
{
  mutex_init (&sp->mutex);
  sp->count = count;
}

static void
semaphore_post (semaphore_t *sp)
{
  mutex_lock (&sp->mutex);
  sp->count = sp->count + 1;
  mutex_unlock (&sp->mutex);
}

static int
semaphore_trywait (semaphore_t *sp) /* this is NOT the ordinary trywait */
{
  int old_count;
  mutex_lock (&sp->mutex);
  old_count = sp->count;
  if (old_count > 0)
    sp->count = old_count - 1;
  mutex_unlock (&sp->mutex);
  return old_count;
}

static void
semaphore_wait (semaphore_t *sp)
{
  while (semaphore_trywait (sp) == 0)
    thread_yield ();
}


This should be pretty fast. Even semaphore_wait
is small enough for automatic inlining.

 -hannes