threads: introduce new state

[IldarValiev]

I suggest to introduce new state for threads STATUS_WAITING. This status will be considered in the "runqueue" group and will be used in cases when a thread have to wait a flag to be set.

Currently, in such cases threads are polling this flag without yielding control to another threads. My suggestion is to save the flag pointer, the mask and the result which are expected to be achieved after masking of the flag. Than thread will yield control to another thread. When his turn comes again, scheduler will check if the condition is fulfilled (flag & mask == result) and then enter this thread or skip it in other case.

Pros:

• While a thread is waiting his flag to be set, it can yield control to other threads;
• Thread supervisor can be implemented to monitor other threads and restart them if they are hung (some kind of a soft watchdog);
• ... ?

Cons:

• Little bit more complicated scheduler;
• Performance penalty in case of short delays (especially for transceivers);
• ... ?

[kaspar030]

@IldarValiev I implemented something like that a while ago: #4103

Would that fit your needs?

[IldarValiev]

@kaspar030, no, I am talking about other thing. It is quite similar to your PR, but I suggest to add thread_flag_t flags as pointer to a variable or (more usable) the register we are waiting to be changed.

[IldarValiev]

Actually I wanted to know if this community is interested in such feature. If yes, I want to implement it. But looks like you have finished a major part of this work already.

[kaspar030]

This "thread flag" stuff is part of a new event subsystem I've been experimenting with.

With that, "event notifiers" can be registered to "event sources", which can be "triggered" (with an optional argument). Together with thread_flags, that allows very complex yet elegant combinations of "events".

Your use-case (if I get it right) can easily be implemented like this:

1. the register/variable of your example becomes an event source (which is "pointer to list of event notifiers")
2. interested users register an "event notifier", that when executed, checks if the variable fits the mask, and then either sets a thread_flag or releases a mutex or ...
3. any code changing the variable in (1) calls event_broadcast(source), triggering the notifiers from 2).

Check out my (totally WIP) "add_generic_events" branch...

[IldarValiev]

@kaspar030, what if the register was changed by the hardware? Who will call event_broadcast(source)?

[kaspar030]

Ah, so you propose checking the register at every context switch?

That would probably not work as expected. Imagine thread B waits for register, thread A is active, goes to sleep, scheduler checks register, it doesn't match, scheduler switches to idle thread, register changes & matches. Now, until any other thread or interrupt causes the scheduler to run, thread B waits even if the register would match.

Your proposal would work with time-sliced scheduling.

[IldarValiev]

In my proposal, this thread is considered to be in running state, so idle thread won't be called. If there are no other active threads, the scheduler will continuously check the register until it match.

[kaspar030]

@IldarValiev I'm sorry, but I don't like that approach.

It would completely mess up the scheduler concept. E.g., the thread waiting for a register change would need to have a high priority, otherwise it can't be scheduled. But any lower priority thread could block it from scheduling. Also the frequency of actually checking the register would probably be indeterministic, as it is scheduled by context switches.

Do you have an actual use-case in mind?

[IldarValiev]

@kaspar030, I think you don't understand fully what I suggest.

If some thread needs to wait for some flag to be set, currently it polls this flag without yielding control to other threads, so we have here useless consumption of power and time. In my suggestion instead of while ((flag & MASK) != RESULT) { } ; this task can call wait_until_flag_is_set(flag, MASK, RESULT);. After this, the control is given to next thread with the same priority. Next time the scheduler will try to give control to this thread again it will check if the condition is met - if no then the scheduler will skip this thread.

So here two cases:

• Only one thread with this priority. Behavior of the system will be the same as it is now, the only difference is that the condition will be checked by the scheduler but not by the thread itself.
• Several threads with the same high priority. Our thread will be skipped until the condition is met. No useless polling, other threads with the same priority don't wait until our thread check his flag several thousand time.

the thread waiting for a register change would need to have a high priority, otherwise it can't be scheduled. But any lower priority thread could block it from scheduling.

No, it doesn't need to have any specific priority. This thread will be considered in "running" state, so lower priority tasks won't be called until our task is suspended. If you have higher priority tasks, in current system our thread will be suspended anyway too.

Also the frequency of actually checking the register would probably be indeterministic, as it is scheduled by context switches.

You are completely right here. That's why I suggest to use this function only for not urgent cases. Usage for transceivers is not recommended.

Do you have an actual use-case in mind?

Only abstract for now. One example is waiting for ADC to reach or exceed some value on its input. Another example is monitoring of the errors count and making some actions after reaching a critical count (restarting a thread, rebooting the device). But most useful here is a possibility to implement some kind of watchdog in the scheduler. If a thread is waiting for his flag too long, may be something is wrong here and this thread (or even whole system) should be restarted? I told it before to several contributors and I still think that this OS urgently needs an extended control over it's threads in form of watchdog. But hardware WDT may inappropriate for such situations.

[kaspar030]

What happens if the thread gets checked once, condition isn't met, and the only other thread waiting to be run is the idle-thread? The condition would be checked once, and then idle would send the device to sleep.

Are you aware that RIOT's scheduler doesn't use time-slices?

IMHO, if I understand your proposal correctly, you'd like to save the need to switch to a thread's context in order to check it's condition. I really think that the inpredictability of those checks make this useless for almost all applications. Also, it would need several changes to the scheduler. (Currently, if a thread is "on runqueue", it is being run unless another higher priority thread also is "on runqueue". Having a thread in running state, but not being run, would need special cases at many places.)

One thing that might make this possible would maybe be a scheduler hook, which could be a function that gets called at every task switch. That function could check the condition, and if it is met, awake a waiting thread. Do you think that would fit your needs?

waiting for ADC to reach or exceed some value on its input.

Isn't that covered by ADC interrupts?

If a thread is waiting for his flag too long, may be something is wrong here and this thread (or even whole system) should be restarted?

Usually any hardware registers that might trigger events have a way to notify the system through interrupts. If that is not the case, polling is the only option. Moving polling into RIOT's scheduler seems like "I don't care when to poll, just please poll sometime". That can easily be done using e.g., a recurring timer.

this OS urgently needs an extended control over it's threads in form of watchdog.

Again, what would be the use-case? If a thread is waiting for something to happen, but has some kind of timeout, timers are probably the way to check for that. Also, a higher-priority thread can do watchdog duties for lower-priority threads.

[OlegHahm]

If some thread needs to wait for some flag to be set, currently it polls this flag without yielding control to other threads, so we have here useless consumption of power and time.

I don't understand how letting the scheduler (or anything else) checking a flag would save power or time.

told it before to several contributors and I still think that this OS urgently needs an extended control over it's threads in form of watchdog.

I still wonder what make you believe that. Did you experience any problems?

[IldarValiev]

@kaspar030

What happens if the thread gets checked once, condition isn't met, and the only other thread waiting to be run is the idle-thread? The condition would be checked once, and then idle would send the device to sleep.

No, it won't call idle thread. Because our thread is still in running state and we have first case from my previous message.

I really think that the inpredictability of those checks make this useless for almost all applications.

Current checks are unpredictable too if you have higher priority threads active. :)

Are you aware that RIOT's scheduler doesn't use time-slices?

Yes, I am aware of it and I like this approach. But it adds constraints for threads such as manual control switching to next thread (and yes, I know that control can be yielded by ISRs, but it can be turned off).

Currently, if a thread is "on runqueue", it is being run unless another higher priority thread also is "on runqueue".

Nothing will be changed here.

One thing that might make this possible would maybe be a scheduler hook, which could be a function that gets called at every task switch. That function could check the condition, and if it is met, awake a waiting thread.

I am talking about almost the same thing! :) The only difference is that the threads are still in running state but skipped if the conditions are not met.

waiting for ADC to reach or exceed some value on its input.

Isn't that covered by ADC interrupts?

Not in every uC. Some of them don't have such feature at all, some of them allow to check only one voltage area for all channels. Anyway, it was the first thing that came to my mind. I am sure creative mind of developers can find more useful use-cases.

Moving polling into RIOT's scheduler seems like "I don't care when to poll, just please poll sometime". That can easily be done using e.g., a recurring timer.

You are right again. Exactly "I don't care when to poll, just please poll sometime". But instead of using of existing mechanism for checking potentially hung threads, you suggest to use additional module? Please notice that if you have two running threads with the same highest priority and both of them are polling their flags then currently inactive thread is in the same "I don't care when to poll, just please poll sometime" state, because control is held by second process for unspecified time.

Also, a higher-priority thread can do watchdog duties for lower-priority threads.

Yep, and the scheduler is the highest priority "thread" in the system. Why can't we use it for such duty?

@OlegHahm,

I don't understand how letting the scheduler (or anything else) checking a flag would save power or time.

No useless nano-second-frequency checking of the flag if you can yield control to other same-priority running threads.

I still wonder what make you believe that. Did you experience any problems?

I didn't, because I haven't use this OS in any projects yet. But can you or any other guarantee that your code is 100% right and it won't hung (because of your error, driver's error, uC error not described in erratas) when you flash it on several hundred uCs and leave them somewhere far away? What would you do then?

@kaspar030, @OlegHahm What so urgent do you usually poll in such cases? Any examples? Can't it wait several milliseconds (or how often do you plan to switch context)? The only thing that comes to my head and requires immediate attention is transceiver's activity, but it is handled by interrupts, as well as other high-priority cases.

Off topic: If you want, we can discuss necessity of including watchdogs and other stuff in RIOT, but let's do it in other place. Private messaging? Group chat? Feel free to contact me, I will be glad to share my thoughts why I think it is important for exactly this OS.

[miri64]

Any updates to this discussion or can it be closed?

[kaspar030]

@IldarValiev To sum up, you see a need for something I'll call "conditional scheduling", where an application can tell the scheduler "don't schedule me unless condition X is met", for conditions that cannot trigger an ISR or equivalent.

The usual way to do this is to have the thread run in a loop with sleeping/yielding in between. Moving this check into the scheduler might save some context switches. It would, though, lead to completely unpredictable behavior due to the tickless nature of the scheduler.

Thus I don't see it happening. :)

@IldarValiev If you still think this is important, let's continue on devel@.