OSDev.org

Brendan had his thread about batch scheduling, and I kinda wrote about my scheduling thoughts there. I then realized I better start a new thread for general scheduling discussion..

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:
Does this scheme seem like sane? Comments please? Drivers I guess can be handled by giving them hard-real-time priorities, or something...

That does seem like a sane scheme. What I am doing for my scheduler is that I am allowing 16 different priorities (0 to 15 - 0x00 to 0x0F). Each process has its own priority. The formula that I am using is that I divide the current PIT's frequency by 16 and then multiply that by N+1 where N is the priority of the process. So for example, lets say I have one IDLE process with the priority of (0x00) and one REALTIME priority process with the priority of 0x03. The PIT's frequency is 18 for example. Divide the 18 by 16 and the integral quotient will be 1. Now multiply it by IDLE+1 = 1*(0+1) = 1. Therefore, the IDLE process should only be given 1 time slice per second or scheduler's time period. The REALTIME will have 18/16 * (3+1) = 1*4 = 4 time slices per second.

Also in my scheduler, I give each process the above calculated value and set its current time slice to zero. So the REALTIME process will be given the time slice of 4 and the current time slice of 0 because it has not yet been given a time slice by the scheduler. In the scheduler, i calculate ORIGINAL TIME SLICE - CURRENT TIME SLICE to calculate the actual priority and then select the highest priority process. For example, the REALTIME process (time slice = 4) is given 2 time slices already. This makes it 4:2. Now the IDLE process (time slice = 1) has not yet been given a time slices which makes it 1:0. Now I calculate 4-2 = 2 and also 1-0 = 1. I then pick the biggest value as the process that should be executed. So if the IDLE process is executed 3 times 4:3, its delta will be 4-3 = 1 which will be equal to IDLE process's priority 1-0 =1. Then there might be a chance for the scheduler to pick the IDLE process over the REALTIME process.

In this scheme, the process with the priority of 0x0F can get the scheduler's processing power to the maximum. Because for example, if you set the PIT's frequency to 1193181 KHZ, you divide 1193181 by 16 you will get 74573. Now if you multiply it by 15+1 you will get (almost) the original frequency. Also if you noticed, using this scheme, no process will starve to death.