sys/sched_rr: Add a simple round robin scheduler module by kfessel · Pull Request #14810 · RIOT-OS/RIOT

kfessel · 2020-08-20T16:01:08Z

I would like to use RIOT with multiple threads at the same priority,
that might not cooperate but should share CPU time.

Contribution description

This contains a simple round robin scheduler module using xtimer to rearrange the current run queue

Testing procedure

create multiple threads of same priority that should work in parallel
without this module only one of them will run.

with this module and calling start_schedule_rr() form #include "sched_rr.h"
they run parallel , sharing cpu time.

see https://github.com/kfessel/riot-thread-duel for a demonstration.

Issues/PRs references

non yet

benpicco · 2020-08-20T16:13:24Z

Would probably be a good idea to include the test application with this PR.

benpicco · 2020-08-20T16:41:39Z

sys/sched_rr/sched_rr.c

+    //this will try to reorder the current priority
+    //(put the current thread at the end of the list)
+    thread_t * active_thread = thread_get_active();
+    if(active_thread != NULL){


Makes me wonder: Can't we simply turn off the sched tick when we enter the idle state?
And turn it back on when we leave idle?

it would be possible to do that (turn off on idle) or to check when switching priority if there is more than one thread in that priority run queue. That would need a little more integration with the existing scheduler.
active_thread == NULL is not a case for idle but for a thread ended and no new one is scheduled yet

kfessel · 2020-08-21T07:20:03Z

@maribu may also like to look at this

kfessel · 2020-08-21T07:59:54Z

I will add a small example of the thread_duel to the PR

maribu

Some inline comments mostly regarding coding style.

In addition, I think that this should be in core, as it needs to access scheduler internal data structures. IMO there should be no accesses to internals of core outside of core, only APIs should be used from outside. (An alternative to moving this to core would be to provide APIs as needed. But new core APIs need extra care for maintaining, so IMO it is better to move this to core.)

sys/include/sched_rr.h

maribu · 2020-08-21T09:09:13Z

sys/include/sched_rr.h

+
+/**
+ * @defgroup    Sched_RR
+ * @ingroup     sys


IMO scheduler and everything strongly coupled to it should be in core.

maribu · 2020-08-21T09:10:41Z

sys/include/sched_rr.h

+/**
+ * time between rond robin calls default 1ms
+ */
+#ifndef SCHED_RR_TIMER
+    #define SCHED_RR_TIMER 1000
+#endif


Suggested change

/**

* time between rond robin calls default 1ms

*/

#ifndef SCHED_RR_TIMER

#define SCHED_RR_TIMER 1000

#endif

#if !defined(SCHED_RR_TIMER) || defined(DOXYGEN)

/**

* @brief Time between round robin calls in µs

*

* @details Defaults to 1ms

*/

#define SCHED_RR_TIMER 1000

#endif

You should always use the @brief command.

The doxygen comment should be right before the macro it applies to

In order to appear in the Doxygen documentation regardless of whether SCHED_RR_TIMER is previously defined, it is best to add an || defined(DOXYGEN).

Also: Please align the text that comes after @brief, @details etc.

maribu · 2020-08-21T09:11:53Z

sys/include/sched_rr.h

+/**
+ * masks off priorities that should not be scheduled default 0
+ */
+#ifndef SCHED_RR_MASK
+    #define SCHED_RR_MASK 1<<0
+#endif


Suggested change

/**

* masks off priorities that should not be scheduled default 0

*/

#ifndef SCHED_RR_MASK

#define SCHED_RR_MASK 1<<0

#endif

#if !defined(SCHED_RR_MASK) || defined(DOXYGEN)

/**

* @brief masks off priorities that should not be scheduled default 0

*/

#define SCHED_RR_MASK BIT0

#endif

The macro BIT0 is provided in bitarithm.h

i do no bitarithmetics so i rather not like to include bitarithm.h in the header (especially since its prone to conflict with other similar definitions)
i would go for #define SCHED_RR_MASK 1<<PRIO_HIGHEST if there is such a thing

sys/sched_rr/sched_rr.c

maribu · 2020-08-21T09:14:11Z

sys/sched_rr/sched_rr.c

+    thread_t * active_thread = thread_get_active();
+    if(active_thread != NULL){
+        if(! (SCHED_RR_MASK & 1 << active_thread->priority)){
+            clist_lpoprpush(&sched_runqueues[active_thread->priority]);


As this is accesses scheduler internal data structures, this should be IMO

a) Either moved to core
b) core_sched should be extended to provide a public API that this could use

I'm personally for a)

I am not sure: wouldn't moving this to core make this not a module?
This uses xtimer which is not part of core maybe this would be a blocker for it being in core.
Aside from that i am all for it:
If we move this to core we could also go for a little bit more integration
(e.g.: switching RR on and off depending on if the current queue needs it or at least stop it on idle as @benpicco said)

core is indeed a single module, which contains submodules. E.g. core_thread_flags enables an optional feature, which is part of core. If this would be part of core, it could be named e.g. core_sched_round_robin. (I think the extra verbosity in the module name doesn't hurt.)

This using a high level timer is to my understanding not a blocker for this being part of core. E.g. stdio is used in core for debugging and for panic(), but is not part of core.

sys/sched_rr/sched_rr.c

maribu · 2020-08-21T09:24:07Z

sys/sched_rr/sched_rr.c

+    // this lets the current thread give way
+    // simple RoundRobin


Please use C style comments (e.g. /* ... */), instead of C++ style. (I'm aware that recent versions of C also support C++ style comments, but the coding conventions wants C style comments.)

The comment seems content-wise a bit confusing to me. Maybe you could rephrase it.

kfessel · 2020-08-21T11:15:51Z

Fixed comments and coding style

benpicco · 2020-08-21T12:12:20Z

Probably worth adding a note that this scheduler does not attempt to be fair.

e.g. you could have

A |........Y |........Y.|
B |         .|         .|

Here A would yield before it's time slice expires, B gets scheduled only to be scheduled away by the next timer tick.

kfessel · 2020-08-21T13:04:29Z

you are right i went for a as simple as possible approach to get this started

kfessel · 2020-08-21T13:24:05Z

what does linux do:
preempt_rt adds 4 RT classes which are in order of priority SCHED_DEADLINE, SCHED_FIFO, SCHED_RR, SCHED_OTHER (contains everything else (fair scheduled))

kfessel · 2020-08-21T13:30:26Z

I did some more fair RR attempt which can be seen in https://github.com/kfessel/riot-thread-duel, it uses the shed_cb to monitor the used cpu time and prefers to run the thread with the least used time.

maribu

Some inline comments. You might want to consider giving uncrustify a try ;-) There is a configuration for uncrustify in the root of the RIOT repo that automatically formats your code as required by the coding convention (with some minor issues).

examples/thread-duell/README.md

examples/thread-duell/Makefile

examples/thread-duell/main.c

maribu · 2020-08-21T18:48:34Z

examples/thread-duell/main.c

+    {
+        int size = THREAD_STACKSIZE_DEFAULT ;
+        char * wech = malloc(size + 4);
+        * (uint32_t *) wech = 3; /* 0-10 workness*/


Suggested change

* (uint32_t *) wech = 3; /* 0-10 workness*/

*(uint32_t *)wech = 3; /* 0-10 workness*/

Also: It would improve readability if you don't abuse the stack for this, but just use distinct variables for this.

examples/thread-duell/main.c

maribu · 2020-08-21T18:58:33Z

sys/sched_rr/sched_rr.c

+    thread_t * active_thread = thread_get_active();
+    if(active_thread != NULL){
+        if(! (SCHED_RR_MASK & 1 << active_thread->priority)){
+            clist_lpoprpush(&sched_runqueues[active_thread->priority]);


core is indeed a single module, which contains submodules. E.g. core_thread_flags enables an optional feature, which is part of core. If this would be part of core, it could be named e.g. core_sched_round_robin. (I think the extra verbosity in the module name doesn't hurt.)

This using a high level timer is to my understanding not a blocker for this being part of core. E.g. stdio is used in core for debugging and for panic(), but is not part of core.

maribu · 2020-08-21T18:59:26Z

examples/thread-duell/README.md

+Thread_Duel
+============
+
+this is a thread duell application to test RIOTS mutithreading abblities


Test applications should be placed in tests/

its not a test in a unit-test sense but i replaced the word

kfessel · 2020-08-24T10:37:24Z

should

+ifneq (,$(filter sched_rr, $(USEMODULE)))
+    USEMODULE += xtimer
+endif

got to /Makefile.dep
or to /sys//Makefile.dep << i think this but i see much of the other

maribu · 2020-08-24T18:20:17Z

should
+ifneq (,$(filter sched_rr, $(USEMODULE)))
+    USEMODULE += xtimer
+endif
got to /Makefile.dep
or to /sys//Makefile.dep << i think this but i see much of the other

It should be in sys/Makefile.dep. For historic reasons the root-level Makefile.dep was previously used a lot.

kfessel · 2020-08-26T11:32:14Z

moved the the dependancy
btw. working on core/sched_rr for deeper integration (atm that is a little delayed)

kfessel · 2021-03-17T09:27:16Z

Closing this in favor of #16126 please continue the review there

sys/sched_rr: Add a simple round robin scheduler module

5070699

benpicco requested a review from kaspar030 August 20, 2020 16:14

benpicco added Area: core Area: RIOT kernel. Handle PRs marked with this with care! Type: new feature The issue requests / The PR implemements a new feature for RIOT labels Aug 20, 2020

benpicco reviewed Aug 20, 2020

View reviewed changes

maribu reviewed Aug 21, 2020

View reviewed changes

fixes for conding style and comments

9df38f8

kfessel force-pushed the sched_rr branch from 5ffe73f to 9df38f8 Compare August 21, 2020 11:15

add a thread-duel example

764a1bd

comment on fairness

80f22f2

kfessel requested a review from jia200x as a code owner August 21, 2020 13:07

maribu reviewed Aug 21, 2020

View reviewed changes

stripped the README

902f40a

kfessel added 4 commits August 24, 2020 12:39

Makefile pruning

aeef78a

softening the crust

f265ddf

removed the malloc, use thread-name if availible

a3a416a

add sched_rr dependencies

0d34e46

move dependency

2d4f87d

kfessel mentioned this pull request Sep 23, 2020

core/sched_round_robin: Add a simple round robin scheduler to core #15069

Closed

kfessel mentioned this pull request Feb 12, 2021

RIOT-core is missing timer and time functionality #15080

Closed

kfessel mentioned this pull request Mar 2, 2021

sys/sched_rr: Add a round robin scheduler module #16126

Merged

kfessel closed this Mar 17, 2021

kfessel mentioned this pull request Apr 11, 2021

core/sched: keep scheduler clist internal to sched #16311

Merged

		// this lets the current thread give way
		// simple RoundRobin

	* (uint32_t ) wech = 3; / 0-10 workness*/
	(uint32_t )wech = 3; /* 0-10 workness*/

Conversation

kfessel commented Aug 20, 2020

Contribution description

Testing procedure

Issues/PRs references

Uh oh!

benpicco commented Aug 20, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel Aug 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel commented Aug 21, 2020

Uh oh!

kfessel commented Aug 21, 2020

Uh oh!

maribu left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maribu Aug 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel Aug 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel Aug 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel commented Aug 21, 2020

Uh oh!

benpicco commented Aug 21, 2020

Uh oh!

kfessel commented Aug 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kfessel commented Aug 21, 2020

Uh oh!

kfessel commented Aug 21, 2020

Uh oh!

maribu left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel Aug 24, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kfessel commented Aug 24, 2020

kfessel Aug 21, 2020 •

edited

Loading

maribu Aug 21, 2020 •

edited

Loading

kfessel Aug 21, 2020 •

edited

Loading

kfessel Aug 21, 2020 •

edited

Loading

kfessel commented Aug 21, 2020 •

edited

Loading

kfessel Aug 24, 2020 •

edited

Loading

kfessel commented Aug 26, 2020 •

edited

Loading