On Mon, 2014-05-05 at 20:27 +0200, Ingo Molnar wrote:
> > Ingo,
> >
> > The delta patch is included below. Thinking a bit more,
> > the state diagram approach is not necessarily less verbose
> > because the state is a tuple (count, wait queue state).
> > After enumerating the states, we may wind up with very similar
> > to what I have.
>
> Could we at least try with one diagram and see how it goes?
>
I've tried (see below). But I don't like how it came out :(
Tim
---
Events:
(1) Attempt read lock (+ACTIVE_BIAS)
(2) Attempt write lock (+ACTIVE_WRITE_BIAS)
(3) Abort read lock or read unlock (-ACTIVE_BIAS)
(4) Abort write lock or write unlock (-ACTIVE_WRITE_BIAS)
(5) Put reader/writer on queue after read/write lock attempt has been
aborted
(+WAITING_BIAS if queue empty)
(6) Pull reader/writer from head of queue
(-WAITING_BIAS if queue becomes empty)
State Event Next-State
----- ----- ----------
(A) count > 0 (0x0000000X), queue empty
1 => (A)
2 => (C.0)
3 => (A if count > 1, B if count =1)
4 not applicable
5 => (C.0)
6 not applicable
(B) count = 0 (0x00000000), queue empty
1 => (A)
2 => (C.0)
3, 4 not applicable
5 => (E.0)
6 not applicable
(C.0) 0 > count > WAITING_BIAS (0xffff000X), queue empty
1 => (C.0)
2 => (E.0)
3 => (count=0xffff0001 implies 1 writer, no readers to abort, C.0 if
count > 0xffff0001)
4 => (B if count=0xffff0001, A if count > 0xffff0001)
5 => (E.1)
6 not applicable
(C.1) 0 > count > WAITING_BIAS (0xffff000X), queue non-empty
1 => (C.1)
2 => (E.1)
3 => (D if count=0xffff0001, C.1 if count > 0xffff0001)
4 => (B if count=0xffff0001, A if count > 0xffff0001)
5 => (E.1)
6 => (A or B if queue becomes empty, C.1 if queue remains non-empty)
(D) count = WAITING_BIAS (0xffff0000), queue non-empty
1 => (C.0)
2 => (E.0)
3,4 not applicable
5 => (D)
6 => (A if queue becomes empty, D otherwise)
(E.0) count < WAITING_BIAS, queue empty
1 => (E.0)
2 => (E.0)
3 => (E.0)
4 => (C.0 if count > 2*WAITING_BIAS E.0 otherwise)
5 => (E.1)
6 not applicable
(E.1) count < WAITING_BIAS, queue non-empty
1 => (E.1)
2 => (E.1)
3 => (E.1)
4 => (C.1 if count < 2*WAITING_BIAS, E.1 otherwise)
5 => (E.1)
6 => (D if count = 2*WAITING_BIAS, E.1 otherwise, queue remains
non-empty) or
E.0 otherwise
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
