Walter is right about transitive readonly - here's the alternative

[Janice Caron]

On 9/13/07, Regan Heath <regan at netmail.co.nz> wrote:
> > same time, but what it /won't/ do is prevent deadlocks.
> What sort of deadlocks

I only meant, it's not possible to eliminate all possible source of
deadlocks. (Whereas, it /is/ possible to eliminate all unauthorised
read/write access).

> [thread1]
> scope a = readable(x);
> --context switch here--
> scope b = readable(y);
>
> [thread2]
> scope b = readable(y);
> --or context switch here--
> scope a = readable(x);

Yep, that looks like a deadlock to me. It is possible to eliminate
this by writing your code differently, but let's not get too
complicated just yet.


> or, this sort:
>
> [thread1]
> scope a = readable(x);
> scope b = readable(x);  //deadlocks unless locks are re-entrant

Readables would definitely be re-entrant, since multiple read locks
are allowed anyway.


> >  scope a = readable(x);
> >  scope b = writable(x); /* Error - b is already locked by this thread */
>
> You mean "x is already locked.." :)

I guess I did, yes. A pending write lock causes all future lock
requests to wait, until the mutex becomes unlocked. In the above
example, the read lock a will never be released because the scope
rules, so it's a deadlock.


> Does it 'break' the system to allow a thread with a read lock to aquire
> a write lock (assuming we block until no other thread has a read lock)?

Yes. See my Lookup example for how to do it properly. In general, the
way you turn a read lock into a write lock is, you don't. You do this
instead:

(1) Get the read lock; do your test; release the read lock. If you
need to write then
(2) Get the write lock; REPEAT THE TEST; don't write if another thread
got there first.



> If one of the goals of this system is to prevent aliasing style
> problems, eg.
>
> int a;
> foo(&a,&a);

I see what you mean, but no, it won't fix that. If you try to get two
independent write locks, then you'll deadlock. If you use one write
lock for both parameters, then the aliasing problem is back. No,
that's a problem for "restrict".



> One observation;  as these variables are scoped you know that if you
> already have a read lock then the write lock lifetime is equal to or
> less than the read lock lifetime.
>
> And vice-versa.  So, how about the opposite case:
>
> scope b = writable(x);
> scope a = readable(x);
>
> Allowed?  Error?  Can we also handle this case?

Not allowed. You can't get a read lock until the write lock is
released. But in this case, you don't need to, since writeble implies
readable. Just read x through b.


> So, just to clarify under your system the only time a shared object may
> change is when it's locked by the thread making the change, correct?

Yes.

> It would therefore be quite beneficial to allow overlapping/simultaneous
> read/write locks (in a single thread), if at all possible.

It isn't possible. It just isn't. There are all sorts of weird and
whacky things that can happen if you try. It has to be forbidden.

(Although it /would/ be possible to make write locks reentrant. It
would mean more overhead though).


> It seems like it may be possible to code this idea up as a library
> solution, hmmm...

In C++ it absolutely is, and I have done it. You can code up
Shared<T>, Readable<T> and Writable<T>. It's not too hard either. But
it would be harder in D because you don't have operator arrow, and you
can't overload dot. So, whereas in C++ you can say p->member, a
library solution in D would have to have something like
p.dereference.member, which is not as nice.

But if you get to write the compiler, you can overcome that deficiency
easily! ;-)