|
|
Threads-Devel : |
From: Allen Pulsifer (pulsifer3_at_[hidden])
Date: 2007-08-04 10:25:32
Hello Anthony,
In thinking about it a little more over my morning coffee, I have another
thought that may help.
In general, we have some # of readers and some # of writers. The readers
can go together (shared), while a writer must be exclusive.
It might be possible to make some arbitrary scheme that takes into account
application behavior to optimize when one or more readers get to access the
resource vs. one of the writers. Its my understanding that we want to keep
it simple though, which basically means no priority queues and no per-thread
data such as wait times.
In our simplified scheme, we could have the following states:
State 0. The resource is idle. If either a reader or writer requests
access, it is immediately granted the lock.
State R0. One or more readers hold the lock, and no writers are waiting. If
another reader comes along, it is also immediately granted access.
State R1. One or more readers hold the lock, and one or more writers are
waiting. If another reader comes along, it is also granted immediate
access. In most implementations, this state is not used.
State R2. One or more readers hold the lock, and one or more writers are
waiting. If a new reader comes along, it is forced to wait.
State RF0. All running readers have just finished, and there is no one
waiting. We go back to State 0.
State RF1. All running readers have just finished, and there are only
readers waiting. This state should never occur, but if it did, we would go
to State R0.
State RF2. All running readers have just finished, and there are only
writers waiting. We choose one of the writers to run, and go to State W.
State RF3. All running readers have just finished, and there are both
readers and writers waiting. We either (a) choose one or more of the
readers to run and go to either State R1 or R2; or (b) chose one of the
writers to run, and go to State W.
State W. One writer holds the lock. Any number of readers and/or writers
may be waiting. If another reader or writer comes along, it must wait.
State WF0. A writer has just finished, and there is no one waiting for the
lock. We go to State 0.
State WF1. A writer has just finished, and there are only readers waiting.
We go directly to State R0, with all readers given access to the lock.
State WF2. A writer has just finished, and there are only writers waiting.
We choose one of the writers to run, and go to State W.
State WF3. A writer has just finished, and there both readers and writers
waiting. We either (a) choose one or more of the readers to run and go to
either State R1 or R2; or (b) chose one of the writers to run, and go to
State W.
In summary, the decisions that have to be made are:
- at RF2 and WF2: which writer runs?
- at RF3 and WF3: do one or more readers run, or does one of the writers
run? If one or more readers, how many readers and which readers? If a
writer, which writer?
[Note if we were being thorough, we would also have to decide when to enter
State R1 as opposed to R2, and once in R1, when to enter R2. For the moment
however, we've decided to not use State R1.]
The solution that apparently has been proposed and implemented for all of
the decisions above is that we simple wake all threads and allow the OS to
make these decisions as a side-effect of its scheduling algorithms and
whoever gets back to the mutex in whatever order.
For State RF3, I think that is the wrong approach, for the reasons I
mentioned in my last email--as long as you are using State R2, where new
readers are forced to wait in an effort to clear the resource for exclusive
access, then you should follow this by going to exclusive access. In State
RF3, the library should only wake the writer threads and allow one of them
to run.
For State WF3, I think it would also be a mistake to simply wake all threads
and make it a free-for-all. The reason again is that you might end up with
only one of the readers having access while 20 other readers wait, when it
would be better to have two or more readers running with shared access.
Therefore, in State WF3, I think the library should do one of the following:
Either:
(A) Wake only the writers.
(B) Wake only the readers, and allow N readers to get shared access to the
lock, where N is from 1 to the # of readers then waiting. Note that this
could be implemented by temporarily going into State R1. Also note N could
be dynamically set by the application at any time, to allow the behavior to
be adapted to the workload.
(C) Wake all of the threads. If a writer gets the lock first, go to State
W. If a reader gets the lock first, then allow N readers to get shared
access to the lock before going to State R2.
(D) Invoke an application callback that gets to set the value of N and
dynamically chose A, B or C.
This I think would give the application a fair bit of flexibility without
making it too complicated or relying on unpredictable OS behavior. If no
other behavior has been selected by the application, I think C with N set to
the pseudo-value "ALL" would be a good default behavior--in fact, C with N
set to "ALL" could be implemented as the only behavior, until the class is
expanded to allow other choices.
What do you think of this suggestion?
Allen