Go Down

Topic: Concurrent Arduino - Intelligent Scheduling for Arduino (New Library) (Read 1 time) previous topic - next topic

bloc97

I've made a full-fledged CEDF scheduler for Arduino based systems. It has features that current multitasking libraries do not have.

Criticism, suggestions and contributions are welcome.

The features are listed in the Readme.

https://github.com/bloc97/ConcurrentArduino

Thank you for your time,
Bloc97

pert

The most simple methods of installing an Arduino library are via Library Manager or Sketch > Include Library > Add .ZIP Library, both of which require the library to be in the root of the repository. So you might consider changing the folder structure of your library to make installation easier.

I would also recommend adding an example sketch, just a simple Blink sort of thing is all that's needed.

bloc97

Thanks for the suggestions, I've added a Zip in the releases section and a blink example.

Coding Badly

Quote
To change this license header, choose License Headers in Project Properties.
Updating the source files to include the license or a reference to the license would be a welcome change.

Quote
Copyright (c) 2017 bloc97
I believe a copyright has to be assigned to a legal entity (you, company, school, etcetera).  It would be interesting to see how the courts rule when a copyright is assigned to a Github moniker.


pert

I've wondered about the user name copyright issue myself. I do the same thing because I don't want to put my full name on there. Not that I'm trying to hide my identity. It's just that I have a completely unrelated online business and I'd rather people find my products if they do a search for my name rather than some programming projects I did as a hobby.

Robin2

I suspect the legal position would be clear if the proper legal name of the copyright holder is included in the source-code files.

I have not looked at this library but if it uses more MCU cycles than doing the same thing using millis() as in Blink Without Delay I would find it hard to see any value.

...R
Two or three hours spent thinking and reading documentation solves most programming problems.

bloc97

[...]

I have not looked at this library but if it uses more MCU cycles than doing the same thing using millis() as in Blink Without Delay I would find it hard to see any value.

This library is much heavier compared to the other simpler alternatives, but implementing an EDF (Earliest Deadline First) scheduler is much more complex compared to a FIFO (First-In-First-Out) scheduler, since you have take in account and track each task's deadline.

However, EDF schedulers handle resource starvation much better compared to FIFO, where some high priority tasks will be starved. However, in EDF, those tasks will be dropped in favour of those who fit within available cpu cycles.

Robin2

I would be interested to hear a description of the sort of tasks that would work better with your EDF scheduler compared to the system using millis() in Several Things at a Time. IMHO the code in that demo deals with the earliest deadline first. But maybe I misunderstand what you mean by EDF.

...R
Two or three hours spent thinking and reading documentation solves most programming problems.

bloc97

But maybe I misunderstand what you mean by EDF.

...R
In true EDF, a lower priority task that will certainly make a higher priority task late will be dropped. Each task within a priority gets run one after the other, like in round robin scheduling.

In FIFO, the scheduler checks for the first task that is run, only if it is not yet time for the first task does the second task get run. You can either implement a version where recurring tasks are dequeued and enqueued each time they are run (Which makes FIFO similar to round robin for recurring tasks) or you can make the queue into a priority list (Where the first added task always gets checked and run first, and is similar to Fixed priority pre-emptive scheduling)

In RR (Round Robin), the scheduler just checks (and runs if necessary) each task at equal intervals, which is equivalent to a FIFO scheduler that dequeues and enqueues a recurring task.

I can give you an example where the EDF will be better than using simple milis(), which is just FIFO. If there is a low priority task and a time-critical (Real Time) task that needs to be run at 40ms intervals, and the low priority task's execution time fluctuates predictably, say between 20ms and 70ms. In FIFO, even if the low priority task's execution time goes above 40ms (lets say it is 70ms), it will be run (since the CPU was idle at that time) and will cause the high priority task to be late (by 30ms in our case).
In EDF, the scheduler should predict that the next run of the low priority task will cause the high priority task to be late, so it will not run the task, causing that task to starve. (Which is not ideal in all cases, but if the programmer defined a task to be time critical the scheduler only does what the programmer said)

I will benchmark the scheduler soon and let you know.

Robin2

In EDF, the scheduler should predict that the next run of the low priority task will cause the high priority task to be late, so it will not run the task, causing that task to starve. (Which is not ideal in all cases, but if the programmer defined a task to be time critical the scheduler only does what the programmer said)
I can understand that. Don't go to the shop for milk if the postman will arrive in the next 5 minutes with a package that you have to sign for.

I guess I just can't think of a situation where I would need that sort of thing on an Arduino.

...R
Two or three hours spent thinking and reading documentation solves most programming problems.

bloc97

Sure, even I don't have that many uses for it right now, and it is somewhat buggy, but I would like one day the scheduler to be very robust and allow many concurrent tasks to be squeezed into limited cpu resources.

Preliminary benchmarks reveal about 70ns overhead on average and 98ns in the worst case. I might release a limited feature set version. That should cut down the overhead to 40ns to use with high performance applications.

Robin2

40ns seems unlikely - that is only 2.46 Atmega 328 clock cycles. Even 98ns is only 6 clock cycles.

Wrong. See next Reply.

...R
Two or three hours spent thinking and reading documentation solves most programming problems.

AWOL

40ns seems unlikely - that is only 2.46 Atmega 328 clock cycles. Even 98ns is only 6 clock cycles.

...R
40ns is 0.46 cycles.
98ns is 1.57 cycles.
"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.
I speak for myself, not Arduino.

Robin2

40ns is 0.46 cycles.
98ns is 1.57 cycles.
OOPs. You are quite correct. I got my decimal point in the wrong place.

Thanks

...R
Two or three hours spent thinking and reading documentation solves most programming problems.

Go Up