Re: Read/Write locks that can be changed into each other?

H. Peter Anvin (hpa@transmeta.com)
24 Apr 2000 16:59:37 -0700

Followup to: <200004242013.WAA11676@smithers.cs.uni-sb.de>
By author: Henrik Theiling <theiling@absint.de>
In newsgroup: linux.dev.kernel
>
> Hi!
>
> Somewhere I read that it would be no problem to add read-locks that
> can be upgraded to write-locks. I'd like to have such locks. I'd
> also like to use the other direction.
>
> So the thing that would be nice is a read-lock that can be promoted to
> be a write-lock and then demoted again to be a read-lock before
> unlocking completely.
>

This is an invalid operation: you are bound to deadlock.

Proof:

Process 1 gets a READ lock
Process 2 gets a READ lock
Process 1 requests upgrade to WRITE; blocks because process 2
has a READ lock
Process 2 requests upgrade to WRITE -> DEADLOCK

You need a facility called a read-write-update lock. These have the
following properties:

Any number of READ locks can coexist.
Nothing can coexist with a WRITE lock.
An UPDATE lock can coexist with READ locks but not with other UPDATE
locks.
An UPDATE lock can be upgraded to WRITE or downgraded to READ.
A WRITE lock can be downgraded to UPDATE or READ.
A READ lock cannot be upgraded.

Now the situation above becomes:

Process 1 gets an UPDATE lock.
Process 2 gets an UPDATE lock; blocks because process 1 has an
UPDATE lock.
Process 1 requests upgrade to WRITE; this can be granted since
there are no other locks.
Process 1 finishes writing; requests downgrade to READ. Process 2
is unblocked (UPDATE can coexist with READ).
Process 2 requests upgrade to WRITE; blocks because process 1 has
a READ lock.
Process 1 releases the READ lock. Process 2 is unblocked.
... etc ...

There are no support for read-write-update locks in Linux, although
you can mimic them easily enough with one read-write lock and one
mutex. Note that the general rules are "you can only lock WRITE if you
hold MUTEX already, and you cannot acquire MUTEX while holding any
other lock."

/* Nothing -> READ */

lock READ;

/* Nothing -> UPDATE */

lock MUTEX;
lock READ;

/* Nothing -> WRITE */

lock MUTEX;
lock WRITE;

/* UPDATE -> WRITE */

drop READ;
lock WRITE;

/* WRITE -> UPDATE */

drop WRITE;
lock READ;

/* WRITE -> READ */

drop WRITE;
lock READ;
drop MUTEX;

/* UPDATE -> READ */

drop MUTEX;

/* WRITE -> nothing */

drop WRITE;
drop MUTEX;

/* UPDATE -> nothing */

drop READ;
drop MUTEX;

/* READ -> nothing */

drop READ;

-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/