More thoughts on tokens

[Matthew Dillon]

:Hi,
:
:At 19:49 23/2/04, Matthew Dillon wrote:
:>[...] Our tokens do not have any (theoretical)
:>     lock order reversal issues (theoretical because my initial
:>     implementation can't guarentee that a livelock won't happen) [etc]
:
:So how is this going to be generalised?
:
:--
:Bob Bishop		    +44 (0)118 977 4017
:rb at xxxxxxxxx		fax +44 (0)118 989 4254

    Not sure what you mean.  The abstraction doesn't care what order you
    get the tokens in because the tokens are only good while the thread
    is actually running.  The moment the thread blocks, other threads which
    need some of its tokens will be allowed to run.  When the thread gets
    cpu again, its held tokens are enforced again.

    This means that the scheduler can theoretically resolve all potential
    deadlocks.  A thread is either running and has all of its tokens, or
    it is not running and has none of its tokens.

    Now realistically speaking, making the scheduler actually *do* that
    properly will require more thought.  It could be as simple as having it
    detect a livelock (which would be done with a counter since they do not
    occur all that often) and then shifting to a timeslice scheme to resolve
    the livelock.  A timeslice scheme is where all the cpus in the system
    cooperate by divvying up their token requests based on 'ticks' or
    something similar.  e.g.

    if (maybe_in_livelock) {
	if ((ticks % ncpus) == mycpuid) {
	    ... send requests ...
	}
    } else {
	... send requests ...
    }

					-Matt
					Matthew Dillon 
					<dillon at xxxxxxxxxxxxx>