How does the scheduler work?

Somaraju_Abhinav · 11 July 2014 07:26

Hello all,

I have recently started using Riot and it would be extremely helpful if there was a brief tutorial explaining how the scheduler is working. I have read the documentation on the website and also some papers published on this topic. However, the only information I have managed to get is that the scheduler is a tickles scheduler and that the threads can be assigned priorities. What I would like to know is

How and when the scheduler runs a thread with higher priority if a thread with lower priority is currently running.
If no threads are running then how does the scheduler check if new threads need to start.

Thanks,

Abhinav

Ludwig_Knupfer1 · 11 July 2014 07:41

Hi Abhinav,

I have recently started using Riot and it would be extremely helpful if there was a brief tutorial explaining how the scheduler is working. I have read the documentation on the website and also some papers published on this topic. However, the only information I have managed to get is that the scheduler is a tickles scheduler and that the threads can be assigned priorities.

Thanks for the input, I guess we really need proper documentation there. I'm volunteering to write it.

What I would like to know is

1) How and when the scheduler runs a thread with higher priority if a thread with lower priority is currently running.

Whenever an interrupt or blocking operation occurs AND the thread with the higher priority is runnable. I.e. the high priority thread becomes unblocked.

2) If no threads are running then how does the scheduler check if new threads need to start.

Not sure if I get your question, but: - New threads are only created by explicit calls to thread_create - Whether a thread is runnable depends on its blocking calls - At least the idle thread will always be runnable - Interrupts trigger scheduler runs

Cheers, Ludwig

Oleg_Hahm · 11 July 2014 08:36

Hi Ludwig, hi Abhinav!

Thanks for the input, I guess we really need proper documentation there. I'm volunteering to write it.

Indeed a good idea, thanks for the suggestion. And thanks for volunteering, Ludwig. It's appreciated!

> 2) If no threads are running then how does the scheduler check if > new threads need to start.

As Ludwig wrote, if nothing else has to be done, the IDLE thread will run (putting the µc into deep sleep mode). It won't be interrupt until an hardware IRQ (radio packet received, timer fired, user input over USART, sensor device triggers...) occurs.

Cheers, Oleg

Somaraju_Abhinav · 14 July 2014 07:29

Hello Ludwig, Thank you for volunteering to write the tutorial - I think it would be very helpful because it is very difficult to debug programs unless I understand what the scheduler is doing.

I think I partially understand your answers. Am I right in assuming that

1) The scheduler runs only if an interrupt occurs and/or the currently running thread enters a blocking operation and 2) When the scheduler runs it then picks a runnable thread with the highest priority.

Does the scheduler get triggered on every interrupt? Thanks, Abhinav

Kaspar · 15 July 2014 04:45

Hi,

1) The scheduler runs only if an interrupt occurs and/or the currently running thread enters a blocking operation and

... or any function that might make another thread runnable, e.g., sending a message or releasing a mutex.

2) When the scheduler runs it then picks a runnable thread with the highest priority.

Correct.

Does the scheduler get triggered on every interrupt?

Nope. The ISR has to set a flag (sched_context_switch_request) which will happen automatically on kernel functions that might trigger a context switch.

Kaspar

Somaraju_Abhinav · 15 July 2014 07:23

Thanks Kasper.

... or any function that might make another thread runnable, e.g.,

sending a message or releasing a mutex.

Suppose there are three threads A, B and C with priorities A > B > C. Also suppose all three threads are currently runnable and the therefore the scheduler is currently running thread A. If thread A sends a message to thread C then immediately after calling the message passing function, which thread does the scheduler execute? Will it continue to execute thread A till it gets blocked and then run thread B till it gets blocked and then finally run thread C?

Regards, Abhinav

Kaspar · 15 July 2014 09:53

Hi,

Somaraju_Abhinav · 15 July 2014 09:54

Hi, Is the same also true if creating a new thread? i.e.

Suppose there are two threads A and B with priorities A > B. Also suppose all both threads are currently runnable and therefore the scheduler is currently running thread A. If thread A creates a new thread C with priority A>B>C, which thread does the scheduler execute? Will it continue to execute thread A till it gets blocked and then run thread B till it gets blocked and then finally run thread C?

Thanks, Abhinav

Kaspar · 15 July 2014 11:13

Hi,

Somaraju_Abhinav · 15 July 2014 11:10

Okay! Thanks a lot Kasper. Regards, Abhinav

Ludwig_Knupfer1 · 15 July 2014 11:16

Hi Abhinav,

Yes.

You could also experiment by modifying and running (e.g. with native): https://gist.github.com/LudwigOrtmann/7fd2dab7aa91e801b05e

Interesting operations for you: - `thread_yield`: Do a voluntary context switch. The thread remains runnable and will be immediately scheduled again if there is no other runnable thread with a priority at least equal to it. - `thread_sleep` Do a voluntary "blocking" operation. Thread needs to woken again using: - `thread_wakup` Wake and possibly run sleeping thread again. I.e. "unblock".

Cheers, Ludwig