OSDev.org

Recently I was thinking about updating my scheduler to include priorities. I wanted to look at some example code so I consulted the Linux scheduler(the original one and not the new one from version 2.6.) After reading over it several times I am finally starting to understand it, here is what I understand it as doing so far(correct me if I am wrong):

1. It looks through all of the tasks in the runqueue to find the one with the highest counter value
2. If all of the task's counters are equal to 0, the scheduler recomputes the counter value for each of the tasks( counter = (counter >> 1) + priority ).

Now the thing about the scheduler is this, since it doesn't recompute the counter value until all of the counters are 0 doesn't that mean that all of the low priority tasks will get a chance to run before any high priority tasks run(if they have used up their time slice)? If that is true then all it would take is 3 or 4 low priority tasks to completely block any high priority tasks for almost half a second or more.

Can someone help me to understand this a little better or recommend a better scheduler to look at?

Also I have looked and looked on Google for a place where I can view the 2.6 kernel source online and I have yet to find anything. Can anyone give me a link? I am asking because the source is 42mb and I have slow speed internet.

Thanks,
Frank

Hi,

Online Linux source code:
http://lxr.linux.no/source/
http://users.sosdg.org/~qiyong/lxr/source/

About Linux-2.6 scheduler it had been developed by Ingo Molnár and its an O(1) scheduler which means that scheduling is constant regarding the runqueue length (number of process in runqueue).
The O(1) manages another queue called expired runqueue, when a task in the runqueue uses all of its time slice, it's moved to the expired runqueue and its time slice is re-calculated.

http://en.wikipedia.org/wiki/Ingo_Moln%C3%A1r
http://josh.trancesoftware.com/linux/
http://www.samspublishing.com/articles/ ... 01760&rl=1
http://www.hpl.hp.com/research/linux/kernel/o1.php
http://www.ibm.com/developerworks/linux ... scheduler/

Thank you for all of that nice information about the 2.6 scheduler. The only problem is that my question was about the earlier O(n) scheduler. I'll just rephrase it here for everyone:

Does the O(n) scheduler (the original one) allow all of the low priority tasks to their completion(or until they sleep) before allowing any high priority tasks the ability to run?

I have a rather thorough description for the Linux's Scheduler and I just uploaded it into my web-site.

You can download the file here:

Linux's CPU Scheduler at AsmTrauma

Hope that helps.

From http://www.samspublishing.com/articles/ ... 01760&rl=1

As mentioned, the Linux operating system is preemptive. When a process enters the TASK_RUNNING state, the kernel checks whether its priority is higher than the priority of the currently executing process. If it is, the scheduler is invoked to pick a new process to run (presumably the process that just became runnable). Additionally, when a process's timeslice reaches zero, it is preempted, and the scheduler is invoked to select a new process.

I hope that clarifies it

Hi,

frank wrote:Recently I was thinking about updating my scheduler to include priorities. I wanted to look at some example code so I consulted the Linux scheduler(the original one and not the new one from version 2.6.) After reading over it several times I am finally starting to understand it, here is what I understand it as doing so far(correct me if I am wrong):

1. It looks through all of the tasks in the runqueue to find the one with the highest counter value
2. If all of the task's counters are equal to 0, the scheduler recomputes the counter value for each of the tasks( counter = (counter >> 1) + priority ).

Now the thing about the scheduler is this, since it doesn't recompute the counter value until all of the counters are 0 doesn't that mean that all of the low priority tasks will get a chance to run before any high priority tasks run(if they have used up their time slice)? If that is true then all it would take is 3 or 4 low priority tasks to completely block any high priority tasks for almost half a second or more.

I don't know much about the scheduler Linux used - my comments are based on what you wrote...

Imagine you've got 3 tasks that look like this just after a reschedule:

TaskA, count = 90/90
TaskB, count = 50/50
TaskC, count = 10/10

Assuming time slices are 1 ms, for the first 40 ms TaskA will have the highest count and will get all time slices. After 40 ms it'll look like this:

TaskA, count = 50/90
TaskB, count = 50/50
TaskC, count = 10/10

Now the count for TaskA and TaskB is equal. When the scheduler selects one of them it'd decrease it's count and there'd be a new "task with highest count". Because of this there's a task switch every 1 ms and TaskA and TaskB take turns. After doing this for 80 ms it'd look like this:

TaskA, count = 10/90
TaskB, count = 10/50
TaskC, count = 10/10

Now all the tasks have the same count. TaskA, TaskB and TaskC would take turns being the "task with highest count", while getting 1 ms each. After 30 ms it'd look like this:

TaskA, count = 0/90
TaskB, count = 0/50
TaskC, count = 0/10

Now they're all zero, so it reschedules it, and now we're back where we started.

If this is right, then:
- it takes 150 ms between reschedules
- TaskA gets 90 ms per 150 ms
- TaskB gets 50 ms per 150 ms
- TaskC gets 10 ms per 150 ms
- TaskA waits for a maximum of 2 ms between time slices
- TaskB waits for a maximum of 41 ms between time slices
- TaskC waits for a maximum of 120 ms between time slices


Cheers,

Brendan

I guess I am right about the part about once a high priority task runs out of time it will not get rescheduled until after all of the low priority tasks.

@Brendan
Well it would be a nice explanation but not knowing the linux scheduler as you say, you made one fundamental flaw. The scheduler is not called on every tick, it is only called when one task depletes its time slice or calls sleep.

@everyone

Well thanks for the help.