Scheduling Algorithm!!

[Vivek S]

Hi all...I am developing a micro kernal and have decided to implement priority based round robin scheduling as the scheduling policy..!..I have a doubt here....

when there is only one task which is of the highest priority and is currently running...does the scheduler context switch this task when the timer interrupt comes even though all other tasks are of lower priority than this task?

If the highest priority task is an infinite while loop then the lower priority tasks are starved of cpu time..!!

what should i do to give all taks a chance to run...pls explain me the algorithm!!

[codemastersnake]

If the highest priority task is an infinite while loop then the lower priority tasks are starved of cpu time..!!

Don't you think wherther the task running is using an infinite loop or not a timer interrupt is always going to be issued and the next qued task is going to be switched?

More over if you want to know about algos you can read Galvin or Tenenbum

[os.hacker64]

You could do something like Unix or Linux does, though I'm not sure which. I think this is how it goes, when ever it is time to schedule, three fields are added together, I believe it is cputime+nice+somethingelse, anyway, cpu time is how long the CPU has been running that process, nice is just a number that the lower it is the higher priority it has. As you can see, the higher the number the lower the priority. To keep the scale even cputime is decremented every schedule, and the processes' priority get higher as long as it is not running.

EDIT: I didn't see your thing about the infinite loop, yes there will always be a timer interrupt.

This is not exact, but I hope you get the idea.

[Vivek S]

the thing i wanted to say was that the priority of the task is highest and it gets scheduled at every alternate timer interrupt....and the tasks at lower priority will probably never get scheduled if the higher priority tasks ar einfinite loops..these high priority tasks keep getting scheduled!!!....

I want a way by which all processes get some amount of cpu time...!!

[Vivek S]

and can some one pls explain me the concept of aging!! which is used to assign dynamic priorities!!

[Brynet-Inc]

and can some one pls explain me the concept of aging!! which is used to assign dynamic priorities!!

I can only assume you meant ageing....

When someone grows older.. cells in their body begin to decay and even mutate.. free radicals account for most of the visual degradations, as does sun damage and other environmental causes..

...If you were talking about paging, see the Wiki.

http://en.wikipedia.org/wiki/Ageing
http://www.osdev.org/wiki/Paging

[Vivek S]

sorry..it was about ageing!!

[codemastersnake]

Check out following likes:

http://en.wikipedia.org/wiki/Round-robin_scheduling

http://www.osdcom.info/content/view/29/39/

[iammisc]

I'm not too sure why anyone would make a while loop a high-priority task. I think the way linux does it is that it has two queues, a running queue and a finished queue. Each process gets a certain timeslice and is put on the runqueue. The highest-priority task on the running queue that is not sleeping is run first. Once its timeslice is over, it is removed from the running queue and put on the finished queue with a newly assigned timeslice. The process continues. Once the running queue is empty, the running queue and finished queues are swapped and the process begins again.

[jerryleecooper]

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.

[Brendan]

Hi,

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