Mutex entirely in ANSI-C possible, without I/O routines?

[TGOS]

I was thinking about it for a while, a mutex written in C and without
disabling any interrupts. Is it possible?

typdef struct mutex {
unsigned int owner1;
unsigend int owner2;
} *mutex;


void mutex_init(mutex *m) {
m->owner1 = 0;
m->owner2 = 0;
}

void mutex_lock(mutex *m) {
int *owner1;
int *owner2;
int currentThread;

currentThread = getThreadIdOfCurrentThread();
owner1 = &(m->owner1);
owner2 = &(m->owner2);
while ( (*owner1 += currentThread) != currentThread &
/* Note the &, not &&, that is important */
(*owner2 ^= currentThread) != currentThread) ) {
*owner1 -= currentThread;
*owner2 ^= currentThread;
mutex_sleep(m);
}
}

I believe that no matter where a context-switch takes place, the code
should be safe, with one exception: It may happen that two threads, trying
to lock the mutex are both sent to sleep, although nobody has the mutex
locked. So mutex_sleep() may not be an enternal sleep, that is only
interrupted by a wake up. Instead it should be a sleep that wakes up on
it's own after some ms.

ADD and XOR are atomic operations. Either they succeed or they don't. If
both owers are 0, both will have the ID of the running thread. Otherwise
they will have some other, arbitrary value, with the current thread
falling into the while loop and restoring the old values again. This is
possible because ADD and XOR are both reversible operations, so you can
easily undo them without backing up the original value. The ADD may cause
a register overflow, but the SUB will then cause an underflow and the
result is correct again.

Why are there two operations? Why not just XOR or just ADD? Well, with ADD
I can think of a scenario with 4 threads, where one is locking the mutex
and then the 3 other try to lock it. Depending on ID, order of tries and
twice a very evil context switch in the middle of the while condition, a
situation may occur where 2 threads fail to lock it, but the third one
believes it has locked the mutex, athough another thread still holds the
lock. A similar situation can occur with XOR. But that both fail is very
unlikely, if not impossible (I'm not good engouh at math to proof or
disproof that it is or isn't possible; it's just an assumption). So it may
not be a *perfect* mutex, but we are also not using perfect OSes. Every OS
has one or more possible dead lock situations and they have no dead lock
detection either (if such a situation occurs, only resetting the system
will resolve it), still we live with it.

Unlock is very easy:

unlock(mutex *m) {
int currentThread;

currentThread = getThreadIdOfCurrentThread();
m->owner1 -= currentThread;
m->owner2 ^= currentThread;
mutex_wakeUp(m);
}


Using 64 bit for the add would make it even more stable, but 64 bit add is
not atomic on 32 bit systems, is it?

 

[Flash Gordon]

I was thinking about it for a while, a mutex written in C and without
disabling any interrupts. Is it possible?

No, since the C language does not define anything about having multiple
processes/threads/fibres.

To be more precise, it might be possible to write something in ISO
standard C that will do the job on your implementation, but it might not
on others.

typdef struct mutex {
unsigned int owner1;
unsigend int owner2;

Operations on unsigned ints are not guaranteed to be atomic.
Unfortunately for you sig_atomic_t might not be large enough for you to
store the process ID, but it is your best chance in C of getting atomic
access. However, as C does not know about multiplt threads it might only
be atomic in terms of signal handlers within the thread.

} *mutex;


void mutex_init(mutex *m) {
m->owner1 = 0;
m->owner2 = 0;
}

void mutex_lock(mutex *m) {
int *owner1;
int *owner2;
int currentThread;

currentThread = getThreadIdOfCurrentThread();

Not a standard C function, so we have no knowledge about this here.

owner1 = &(m->owner1);
owner2 = &(m->owner2);
while ( (*owner1 += currentThread) != currentThread &
/* Note the &, not &&, that is important */
(*owner2 ^= currentThread) != currentThread) ) {
*owner1 -= currentThread;
*owner2 ^= currentThread;
mutex_sleep(m);
}
}

I believe that no matter where a context-switch takes place, the code
should be safe, with one exception: It may happen that two threads,
trying to lock the mutex are both sent to sleep, although nobody has
the mutex locked. So mutex_sleep() may not be an enternal sleep, that
is only interrupted by a wake up. Instead it should be a sleep that
wakes up on it's own after some ms.

ADD and XOR are atomic operations. Either they succeed or they don't.

What make you think that? It is not defined by the C standard and is
definitely not true on some processors. For example, on an 8 bit
processor it will take 2 operations and the processor can obviously be
implemented between the 2 operations. Also, on almost any processor, the
value could be read in to a register, then the processor could be
interrupted and switch to the another thread which accesses your mutex.

Using 64 bit for the add would make it even more stable, but 64 bit
add is not atomic on 32 bit systems, is it?

There is nothing to say that and add is atomic on any system. Especially
when you consider that it might me implemented using three operations
fetch value
add
store result

You need to discus this on a group dedicated to your platform of
interest. Only there will you get answers which might be useful. There
is definitely *no* answer which would be correct for all platforms.

 

[Chris Torek]

I was thinking about it for a while, a mutex written in C and without
disabling any interrupts. Is it possible?

Not portably. More important, the result is not nearly as useful
as the version you get if you throw portability to the wind and
just write one machine-specific implementation per machine:

#include "machine/mutex.h" /* get machine-dependent mutex impl. */

/*
* Now *use* the mutex "portably", where "porting" from Machine X to
* Machine Y requires writing a new Y/mutex.h.
*/

If you are willing to require some other standard than just an
ANSI or ISO C standard (such as POSIX), that standard may (or may
not) have its own mutex(es).

ADD and XOR are atomic operations.

Unless, of course, they are not.

(Neither operation is atomic on a load/store architecture like the
MIPS or PowerPC.)

You can use Dekker's algorithm (look it up ) to build mutexes
even for load/store architectures, provided *those* operations are
atomic. It has some drawbacks, though.

On modern microprocessors you will typically want to use one of
their special "multi-cpu" instructions: CAS, or LL/SC, or similar.
These may require that the mutex data structure live at a "special"
address (in lockable memory, or in a separate cache-line, or some
such). More exotic architectures may even put the atomicity
elsewhere, such as "incrementing memory".

 

[Xenos]

I was thinking about it for a while, a mutex written in C and without
disabling any interrupts. Is it possible?

What you are talking about is possible, but is not trivial and will consume
more cpu time, and thus is not advantageous to do over using OS specific
calls. See "Dekker's Algorithm."

DrX

 

[Old Wolf]

I was thinking about it for a while, a mutex written in C and without
disabling any interrupts. Is it possible?

typdef struct mutex {
unsigned int owner1;
unsigend int owner2;
} *mutex;

^^^
Did you intend that * to be there?

void mutex_init(mutex *m) {
m->owner1 = 0;
m->owner2 = 0;
}

I guess you are taking other measures to ensure that
only one thread calls this function.

void mutex_lock(mutex *m) {

This should be: mutex volatile *m
(otherwise the compiler could optimise this function, undoing
all your hard work).

int *owner1;
int *owner2;

int volatile *owner1; etc.
BTW these pointers are a waste of time, you only assign them once

int currentThread;

currentThread = getThreadIdOfCurrentThread();
owner1 = &(m->owner1);
owner2 = &(m->owner2);
while ( (*owner1 += currentThread) != currentThread &
/* Note the &, not &&, that is important */
(*owner2 ^= currentThread) != currentThread) ) {
*owner1 -= currentThread;
*owner2 ^= currentThread;
mutex_sleep(m);
}
}

You could have integer overflow when you add the thread IDs.
I don't think it works for 3 or more threads.
It doesn't work if a context switch occurs during the
assignments, eg. "owner1 += currentThread": it reads 'owner1'
and 'currentThread', then the other thread updates owner1,
then the first thread writes its calculated value.
+= ^= -= etc. are not atomic operations.

I believe that no matter where a context-switch takes place, the code
should be safe

Context-switch? Doesn't happen in a 2-processor system
(or 1-processor with Hyperthreading) where each processor has
1 thread running your code. They could both write some memory
at the same time, or a read after a write could get the
pre-write value due to hardware write cacheing.

Unlock is very easy:

unlock(mutex *m) {
int currentThread;

currentThread = getThreadIdOfCurrentThread();
m->owner1 -= currentThread;
m->owner2 ^= currentThread;
mutex_wakeUp(m);
}

What if wakeUp is called here, and then sleep is called straight
after, in the lock loop? It will stay asleep forever.

Using 64 bit for the add would make it even more stable, but 64 bit add is
not atomic on 32 bit systems, is it?

The only atomic operations are those on the type "sig_atomic_t".