[coyotos-dev] Continued (corrected)

[Haplo]

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  
calculated thusly:
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  
tasks.
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.

http://en.wikipedia.org/wiki/Non-blocking_synchronization
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...
URL: http://www.coyotos.org/pipermail/coyotos-dev/attachments/20061202/bd8ed18a/attachment.html