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-tip-commits" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
|