[Nickle]Mutex replacements in nickle

[Keith Packard]

Nickle currently has two built-in synchronization types 'mutex' and 
'semaphore'.  Of course, 'semaphore' is more powerful, but the current 
'mutex' type has the nice property that only the thread which acquired the 
mutex may release it (else an exception is raised). The code also checks 
to see if the current thread holds the mutex and raises the 'deadlock' 
exception.

The obvious question is then can mutexes be implemented in terms of 
semaphores, and naturally the answer is 'yes'.  However, when I sent this 
code to Bart, he was confused by the locking order within the objects.

Here's the datatype:

	typedef union { 
	    thread; 
	    integer; 
	} nmt;
	
	public typedef struct { 
	    semaphore sem; 
	    semaphore crit; 
	    nmt t; 
	} nmutex_struct;

	public typedef *nmutex_struct nmutex;

A mutex is a reference to a data structure containing two semaphores and 
an object which refers either to the thread owning the mutex or '0' which 
indicates that no thread holds the mutex.

The 'crit' semaphore protects access to the 't' variable, the 'sem' 
variable is used to block waiting for the mutex to become available.

I wrote the acquire/release functions as:

    public integer function acquire (nmutex m)
    {
        twixt (Semaphore::wait (m->crit); Semaphore::signal (m->crit))
        {
            if (m->t == Thread::current())
                raise deadlock (m);
            twixt (Semaphore::signal (m->crit); Semaphore::wait (m->crit))
                Semaphore::wait (m->sem);
            m->t = Thread::current();
        }
        return 1;
    }

    public integer function release (nmutex m)
    {
        twixt (Semaphore::wait (m->crit); Semaphore::signal (m->crit))
        {
            if (m->t != Thread::current())
                raise notowned (m);
            m->t = 0;
            Semaphore::signal (m->sem);
        }
        return 1;
    }

The funny part is inside 'acquire' where it waits for the 'crit' 
semaphore, checks for deadlock then releases the 'crit' semaphore to wait 
for the 'sem' semaphore.  The problem is that if the code blocks on the
'sem' semaphore with the 'crit' semaphore locked, there's no way a thread 
can ever signal the 'sem' semaphore -- it must wait for the 'crit' 
semaphore first.  Classic deadlock.  So, I signal the 'crit' semaphore
before attempting to wait for the 'sem' semaphore.

I think this could be better written as:

    public function acquire (nmutex m)
    {
        twixt (Semaphore::wait (m->crit); Semaphore::signal (m->crit))
            if (m->t == Thread::current())
                raise deadlock (m);
        Semaphore::wait(m->sem);
        twixt (Semaphore::wait (m->crit); Semaphore::signal (m->crit))
            m->t = Thread::current ();
    }

    public integer function release (nmutex m)
    {
        twixt (Semaphore::wait (m->crit); Semaphore::signal (m->crit))
        {
            if (m->t != Thread::current())
                raise notowned (m);
            m->t = 0;
        }
        Semaphore::signal (m->sem);
        return 1;
    }

Now the semaphore usage is much clearer -- the 'sem' semaphore is always used 
with the 'crit' semaphore unlocked.

-keith