Hi,
jerryleecooper wrote:I hope that's not hijacking the thread, but, is 2500hz too fast a timer for a scheduler? Because my scheduler is running at that speed, and the strategy employed for now is to give equal time to each processes. The problem would be, approaching 2500 processes, each process would be given one instruction and after that there would be one interrupt, and another interrupt after another instruction for the other process. The equality of time for each processes is good when theres' not alot of process, but whjen a lot of the,m, it is not.
Do your maths again. Here's some interesting formulas...
First, for all schedulers:
Code: Select all
Overhead = TaskSwitchesPerSecond * CyclesPerTaskSwitch / CyclesPerSecond * 100
Where:
Overhead is the percentage of CPU time you spend doing task switches alone
TaskSwitchesPerSecond is the number of task switches that occur each second
CyclesPerTaskSwitch is the total cost of a task switch
CyclesPerSecond is how many cycles the CPU is capable of in one second
Also (for most "simple" schedulers):
Code: Select all
CyclesPerTaskSwitch = IRQcycles + SchedulerCycles + TaskSwitchCycles
Where:
CyclesPerTaskSwitch is the total cost of a task switch
IRQcycles is the number of CPU cycles your timer IRQ costs
SchedulerCycles is the number of CPU cycles it takes to decide which task to switch to
TaskSwitchCycles is the number of CPU cycles it takes to save/load task states
Note: "TaskSwitchCycles" includes direct costs (saving and loading task state, etc) and indirect costs (blowing away TLB entries, screwing up data and instruction caches, etc).
From this, you can calculate that (for e.g.) for a 25 MHz 80486 and a round robin scheduler doing 2500 task switches per second, if it takes 50 cycles for IRQ overhead, 50 cycles for scheduler overhead and 900 cycles for task switch overhead, then:
Code: Select all
CyclesPerTaskSwitch = IRQcycles + SchedulerCycles + TaskSwitchCycles
= 50 + 50 + 900
= 1000 cycles
Overhead = TaskSwitchesPerSecond * CyclesPerTaskSwitch / CyclesPerSecond * 100
= 2500 * 1000 / 25000000 * 100
= 10% of CPU time spent on task switches alone!
Note: The number of tasks running makes no difference (unless only one task is running and the task switch can be skipped entirely).
Also (for round robin only):
Code: Select all
TaskCPUusage = 100 / RunningTasks
Where:
TaskCPUusage is the percentage of CPU time each task gets
RunningTasks is the number of tasks that are running
In this case, for round robin scheduler running 2500 tasks each task gets 0.04 % of CPU time, and for round robin scheduler running 2 tasks each task gets 50 % of CPU time.
And (for round robin only):
Code: Select all
TaskCycles = CyclesPerSecond / TimerFrequency - CyclesPerTaskSwitch
Where:
TaskCycles is the number of cycles a task can actually use before it's preempted
CyclesPerSecond is how many cycles the CPU is capable of in one second
TimerFrequency is the frequency of the timer IRQ in Hz
CyclesPerTaskSwitch is the total cost of a task switch
In this case (using our 25 MHz 80486 with "CyclesPerTaskSwitch" from the example above):
Code: Select all
TaskCycles = CyclesPerSecond / TimerFrequency - CyclesPerTaskSwitch
= 25000000 / 2500 - 1000
= 9000 cycles
Of course formulas can be re-arranged. For example, I like this version of the first formula:
Code: Select all
TaskSwitchesPerSecond = Overhead / 100 * CyclesPerSecond / CyclesPerTaskSwitch
Where:
TaskSwitchesPerSecond is the number of task switches that occur each second
Overhead is the percentage of CPU time you spend doing task switches alone
CyclesPerTaskSwitch is the total cost of a task switch
CyclesPerSecond is how many cycles the CPU is capable of in one second
The other good thing about formulas is you can invent your own (e.g. play around with a spreadsheet) and then do the calculation during boot to (for e.g.) get a nice compromise between overhead and other scheduler characteristics (based on measured CPU speed)...
Cheers,
Brendan
