I currently have a real-time scheduler (with compile-time adjustable number of priorities) in my kernel, but I'm going to replace it in the near future. My basic idea is to have 4 types of scheduling: real-time, interactive, service and batch.
The basic idea is that the classes are ordered by priority: real-time is the most important group, interactive next, then service, and finally batch. Then there's drivers which don't belong to any of those. The complications are that I want some kind of fairness scheduling in there, so what I'm thinking about is handling each class separately, but then move some jobs between some of the classes. So far I've got the following scheme in mind:
- Real-time class can be explicitly set, in which case I call it "hard" and these have the highest priority. I'm probably going to need several real-time priorities for the "hard" class to order them in regards to each other. This is probably the easiest class to schedule.. just pick the highest priority thread.
- The next thing to schedule, would be "soft" real-time threads: interactive threads which the system thinks (by using feedback from rest of the system) are doing stuff like audio/video/animation/whatever. Idea is that multi-media be kept running smoothly as long as doing so won't use too much CPU (more below). Feedback would be used to not only promote interactive threads, but also to demote them back to normal interactive class.
- Interactive scheduling would be the default for any normal threads for which there's no explicitly scheduling set. These would basicly get equal CPU each, with two minor exceptions by feedback from GUI: give the owner of the focused window slightly more priority than the rest, and give a small boost to the timeshare length to the thread that owns a window that just got a message initiated by user interaction. Threads with even soft-real-time scheduling class, will still get priority over all normal interactive threads.
- Service class would be like interactive class, but without focus boosts, and with longer timeshares. Something similar to focus boosts could be done by preferring unblocked threads over threads that are waiting because they run out of their timeshare, but that's normal thing to do, I guess. I don't want this class to be totally ignored if interactives run at 100% though, so I probably want to reserve some amount of CPU for these.
- Batch would run at idle priority, without any explicit timeshares (or very long ones). Start new batch jobs if we're running idle too much, and only provide order by letting the starting-order to be selected. Ultimately one would probably want shortest jobs done first, but I can't think of a good way to do this automatically. Probably this class could be best handled by some user-space batch-manager, so I think all that's needed in kernel is an "idle" priority class..
That's my basic idea. Now in order to avoid starving other processes, I'd probably want to limit real-time threads (both soft and hard) to something like 70% of CPU usage (last second is probably good period). With hard-real-time threads I'm not sure what to do. One thing would be to require each such thread to actually state it's time requirements before accepting the priority (and deny if it can't be guaranteed). For soft-real-time, the best thing would be to demote the thread using most CPU back to interactive?
Interactives would be preferred to services as a next thread at all times, services shouldn't be starved completely, so I guess I'd like to reserve some amount (20%?) for services at all times. So after the real-time threads have run, schedule the next interactive, unless it's necessary to schedule services in order to give them the 20% reserved time, unless all services are blocking, in which case schedule interactives. If all interactives are blocking, schedule services. Finally, if everything else has been run, schedule some idles.
Pseudocode would look something like this:
Code: Select all
if(hard-realtime-threads-available):
schedule-highest-realtime()
else if(soft-realtime-threads-available):
schedule-soft-real-time() # no idea yet how to give these priorities
else if(time-left + services-used < 20% and services-available):
schedule-services()
else if(interactives-available):
schedule-interactive()
else if(services-available):
schedule-services()
else if(batch-available):
schedule-batch()
else if(batch-queued-for-starting):
start-next-batch()
else:
do-kernel-idle-loop()
