From mboxrd@z Thu Jan  1 00:00:00 1970
From: miller@hamnavoe.demon.co.uk
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Kernel question: i386 test-and-set problem
Date: Sun, 23 Jul 2000 15:41:47 +0100
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Message-Id: <E13GMvE-0009IY-0K@tele-post-20.mail.demon.net>
Topicbox-Message-UUID: e967b8b6-eac8-11e9-9e20-41e7f4b1d025

presotto@plan9.bell-labs.com writes:
> If I have two locks,
> one in r and one in p, I can't figure out how to get them both to lock
> in the same order.

My suggestion is below.  The interaction between sleep() and wakeup() is
exactly as in the beautiful and succinct algorithm in your paper, using
the lock on r.  Adding postnote() introduces the pointer p->r to enable
postnote() to find r, so the lock p->rlock is introduced to protect it
in the interaction between sleep() and postnote().  The interaction
between wakeup() and postnote() is protected by the lock on r.

Eliminating interrupt dis/en-abling for simplicity:

sleep(r):    {'up' is the current Proc}
	lock(up->rlock)
	lock(r)
	if wakeup condition is satisfied or up->notepending != 0
		unlock(r)
		unlock(up->rlock)
	else
		r->p = up
		up->r = r
		up->state = Wakeme
		unlock(r)
		unlock(up->rlock)
		-- reschedule --
	if up->notepending
		up->notepending = 0
		error(Eintr)

wakeup(r):    {wakeup condition is satisfied}
	lock(r)
	p = r->p
	if p != 0
		r->p = 0
		p->r = 0	
		ready(p)
	unlock(r)

postnote(p):
	p->notepending = 1
	lock(p->rlock)
	r = p->r
	if r != 0
		lock(r)
		if(r->p == p)
			r->p = 0
			p->r = 0
			ready(p)
		unlock(r)
	unlock(p->rlock)

Explanation: we can think of locks in terms of the invariants they
protect.  Define S(p,r) = "Proc p is sleeping or committed to
sleeping on Rendez r", where committed means that p will sleep on r
without first testing the wakeup condition or testing for pending
notes.  Define T(p,r) =  "Proc p is not sleeping on r, and will not
sleep on r without first testing both the wakeup condition and
notepending".  The significance of these predicates is that
if S(p,r) holds, then wakeup(r) or postnote(p) must take steps
to awaken p from r; whereas if T(p,r) holds, then wakeup(r) or
postnote(p) need not -- must not -- do so.

The invariant we want to maintain on each Rendez r is:

IR(r): { for all p: (p = r->p) <=> S(p,r) }

or informally, r->p points to a Proc if and only if that Proc is
sleeping or committed to sleeping on r.  Any critical section of
code where IR(r) is temporarily untrue (e.g. while testing conditions
or manipulating r->p) must be protected by locking r.  Because the
inverse of S(p,r) is not quite the same as T(p,r) -- p may have
tested only one of the two conditions -- we also impose a global
invariant:

IPR: { for all p,r: !S(p,r) => T(p,r) }

To protect this invariant, testing of the wakeup condition and
notepending before sleeping on r must be within a lock on r.
The invariant for Proc p, protected by p->rlock, is weaker than IR:

IP(p): { for all r: S(p,r) => (r = p->r) }

or informally, if p is sleeping or committed to sleeping on a Rendez,
then p->r points to that Rendez.  Note that the reverse implication
is not stipulated: if p->r points to a Rendez, we can't necessarily
conclude that S(p,p->r) holds; only that !S(p,r) -- and therefore
T(p,r), by IPR -- holds for all other r.  But the uncertainty over
S(p,p->r) can be resolved using IR(p->r).

Key point: wakeup() can safely set p->r = 0 without locking p->rlock,
because this assignment does not affect the invariant IP(p).  In fact
the assignment could be deleted and the algorithm would still work;
it is only an optimisation to avoid postnote() looking at a Rendez
unnecessarily.  This observation is what saves us from the dilemma
of locking order.

-- Richard Miller