[coyotos-dev] Continued (corrected)
starfirex at comcast.net
Sat Dec 2 15:32:03 CST 2006
Ok, so I did some more in depth research on scheduling and came up
with a more definitive solution. The strategy I've settled upon is
not strictly preemptive, however guarantees no-starvation and for the
majority of situations should schedule in a way that's proportional
to the immediate need and handles real-time applications preferentially.
The basic idea is a modified Highest Response Ratio Next strategy.
That is, highest priority on the queue goes next, with priority
Priority = (time spent waiting + estimated time to complete task)/
estimated time to complete task.
This preferentially schedules short tasks first, with tasks gaining
priority incrementally the longer they wait. However, this would put
user-activated larger tasks in a long wait, so there needs to be a
way to prioritize real-time and user specified tasks to run first
(and allow those processes to pass their scheduling privileges to
processes they call capabilities on). In order for this to work, you
need a way to mark 'critical tasks'. Processes in the user's focus
should receive this flag automatically, but for other processes you
need to stochastically or deterministically (which with this method
could be done on compile rather than on install) determine a
process's dependencies. A process calling a dependency is flagged
critical. This might simply be done automatically during an active
period for a process by flagging it critical should it make any
external capability calls.
Scheduling for 'critical' processes is simpler than for non-critical
Critical Priority = time spent waiting + estimated time to complete.
If a critical task calls a capability on another process, the called
process automatically inherits the caller's priority. A process in
the active state will remain there until either it completes or
another queued process exceeds its priority. Priorities, by 'time
spent waiting', are incremented by 1 every scheduling time slice. If
a process is preempted, it retains its priority and is re-queued
(continues to accrue priority). A process that completes within its
time slot loses its accrued priority and is reinserted into the queue
at 0 'time spent waiting' for the next slice.
I've also found two very good non-locking contention management
strategies. I don't think a locking strategy can really be used
within the constraints of coyotos anyway, as it's impossible to
completely prevent deadlock/livelock with a single locking strategy.
There is a 2 lock strategy which can avoid it, but the performance of
all known locking strategies degrades almost exponentially with every
added processor and also with each contending thread per processor.
The particular strategy I found outperforms locking strategies on a
single processor slightly, is slightly worse on 2 processors, and
performs exponentially better than any locking strategy when the
number of processors increases beyond 2. Furthermore, in addition to
being immune to deadlock/livelock (not sure about the ABA bug), this
strategy, as far as I can tell, could have the throughput-enhancing
strategies of Polka applied to it to further increase the
performance. Information on this strategy (including pseudocode and
performance results) are attached (pdf). I'll post more specifics on
Polka whenever I can find more information on it.
It has come to my attention that the documents I was to attach are
copyrighted. In light of this, I'm including a link to the wikipedia
article which uses these documents either with permission or under
fair use policy.
External Links: #1 (simple lock-free strategy and a two-lock
strategy, explained and compared in detail)
Resources: #3 (compares various lock-free, non-blocking, and wait-
free algorithms, while presenting new high-performance algorithms
such as Polka(POlite-KArma hybrid), written in 2005)
The wikipedia article also compares some modern strategies and is a
good read by itself.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the coyotos-dev