I am trying to understand how preemptive multitasking works. I don't understand how all tasks will be executed. once I understand the basics I will try to write plain c code, not for specific MCU but It should show some basic ideas for preemptive multitasking design

I am taking the following example after searching on the google

• I assume that we have three tasks.
• Each task has its own execution time.
• Each task needs to be completed within the time limit.
• Each task has a priority that should be followed.
• system time tick 1ms

LCM of the time period of all tasks is 40ms

40ms/8ms = 5
40ms/5ms = 8
40ms/10ms = 4

I don't understand how tasks will be executed between 15ms and 40ms?

Table for task execution on priority

1--------> T2 running
2--------> T2 running
3--------> T2 running
4--------> T2 running
5--------> T2 running
6--------> T1 running
7--------> T1 running
8--------> T1 running
9--------> T1 running
10-------> T1 running
11-------> T1 running
12-------> T1 running
13-------> T1 running
14------->
15------->
16------->
17------->
18------->
19------->
20------->
21------->
22------->
23------->
24------->
25------->
26------->
27------->
28------->
29------->
30------->
31------->
32------->
33------->
34------->
35------->
36------->
37------->
38------->
39------->
40------->
continue

can you @djsfantasi @click_here help in this matter

 

Will all tasks execute for preemptive multitasking in following order ?

How long T3 will run on microcontroller?

Will it be run for 10ms time?

Will it only run for 5ms because T2 will again ready to run?

1--------> T2 running
2--------> T2 running
3--------> T2 running
4--------> T2 running
5--------> T2 running
6--------> T1 running
7--------> T1 running
8--------> T1 running
9--------> T1 running
10-------> T1 running
11-------> T2 running
12-------> T2 running
13-------> T2 running
14-------> T2 running
15-------> T2 running
16-------> T1 running
17-------> T1 running
18-------> T1 running
19-------> T3 running
20-------> T3 running
21-------> T3 running
22-------> T3 running
23-------> T3 running
24-------> T3 running
25-------> T3 running
26-------> T3 running
27-------> T3 running
28-------> T3 running
29-------> T3 running
30-------> T3 running
31-------> T3 running
32-------> T3 running
33-------> T3 running
34-------> T3 running
35-------> T3 running
36-------> T3 running
37-------> T3 running
38-------> T3 running
39------->
40------->

My understanding

T2 is the highest priority task that runs on the microcontroller for the first 5 ms.

T1 is the next high priority task that should be runs 8ms but it only run for 5ms only because T2 run again its high priority than T1.

 

It will depend on the details of the scheduling algorithm.

Bob

 

It will depend on the details of the scheduling algorithm.

Bob

https://www.sciencedirect.com/topics/engineering/preemptive-scheduling

Preemptive scheduling is normally implemented in two different ways: using Round Robin (RR) scheduling, or using interrupt-based (IB) scheduling.

 

That statement is wrong in multiple ways. All preventive multitasking must be interrupt based, how else could it be preemptive?

And “round robin” and “interrupt based” are not the same category of things. The prior is a scheduling policy, and the latter is an implementation choice.

Bob

 

An example of flashing LEDs is not a good demonstration of multitasking. This can be accomplished with straight sequential processing.

It is not easy to come up with a simple example of preemptive multitasking. It should come as no surprise that multitasking is desirable only for complex systems. The one example that comes to mind is a frequency spectrum analyzer.

An ADC is sampled at a fixed sampling rate using a timer interrupt. This does not consume much CPU time but it occurs repeatedly at very high rates. An array of data is acquired and processed using FFT function. The resulting frequency spectrum must be displayed in real-time.

The problem here is that the FFT computation is time consuming and uses most of the CPU resources, almost 100% if allowed to do so. In the meantime, timer interrupts and ADC data samples must be handled in a timely manner. This is the #1 priority.
Updating the screen also takes time. A compromise must be reached between the FFT computation and the screen update. The goal would be to avoid any flicker on the screen. The screen buffer can only be updated during the blanking period of the display. For example, you might only have a processing window of 1ms every 17ms to update the screen.

How do we apply preemptive multitasking in this example?

1) The FFT function is running in full demand of the CPU.
2) Timer interrupts occur frequently, e.g. every 10μs. However, it only requires a few cycles of CPU time to execute.
3) A screen update interrupt occurs every 17ms. If the update is not completed withing 1ms the process is suspended until the next 17ms.

 

That statement is wrong in multiple ways. All preventive multitasking must be interrupt based, how else could it be preemptive?
Bob

This information is given in the website page 15.2.2 Preemptive Scheduling

 

It is not easy to come up with a simple example of preemptive multitasking. It should come as no surprise that multitasking is desirable only for complex systems. The one example that comes to mind is a frequency spectrum analyzer.

@MrChips Is the Zero Crossing Detector of 5V AC Signal an example of preemptive Multitasking ? Each zero-crossing has to be counted and stored in a variable. It's important to count every zero-crossing and we can't miss a single count. Saving record of even number of crossings and odd number of crossings as well as.

 

No.
All computer systems take advantage of interrupt processing to service hardware modules. This does not make it multitasking.
Interrupt handling is an important tool of multitasking. Multitasking uses interrupts.
Use of interrupts does not make it multitasking.

 

This information is given in the website page 15.2.2 Preemptive Scheduling

They both are very likely implemented using hardware interrupts. The scheduling of which next task is the point.
https://www.sciencedirect.com/topics/computer-science/round-robin-scheduling

18.4.2 Round-robin scheduling and context switching
In round-robin scheduling the operating system is driven by a regular interrupt (the ‘clock tick’). Tasks are selected in a fixed sequence for execution. On each clock tick, the current task is discontinued and the next is allowed to start execution. All tasks are treated as being of equal importance and wait in turn for their slot of CPU time.

 

How do we apply preemptive multitasking in this example?

1) The FFT function is running in full demand of the CPU.
2) Timer interrupts occur frequently, e.g. every 10μs. However, it only requires a few cycles of CPU time to execute.
3) A screen update interrupt occurs every 17ms. If the update is not completed withing 1ms the process is suspended until the next 17ms.

I do not have much idea about your example, I will do research on it by taking time to understand it.

I don't know about FFT function and I need to read about it.

I understand that a timer interrupt occur every 10μs

I don't understand what it means "A screen update interrupt occurs every 17ms". Is it a timer interrupt and LCD will the update every 17ms"?

 

I only present this as an example of multitasking. You can ignore this example.

What we are looking for are:

1) Two or more processes that are CPU intensive. Each process can be suspended and processing is allowed to continue when CPU time is available.
2) High priority processes that must be handled and completed without failure. These in general do not require a lot of CPU cycles in order to be completed.

 

In my categorization, there are two general classes of multitasking: cooperative and preemptive.

For either of those forms there are multiple scheduling policies. Here are a few:

Round robin: the next task ready is scheduled.

Strict priority: the highest priority task that is ready is scheduled.

Time slicing: the task that has used the least time up to now is scheduled.

In real systems, a combination of these (and other) policies is likely used.

Bob

 

I only present this as an example of multitasking. You can ignore this example.

What we are looking for are:

1) Two or more processes that are CPU intensive. Each process can be suspended and processing is allowed to continue when CPU time is available.
2) High priority processes that must be handled and completed without failure. These in general do not require a lot of CPU cycles in order to be completed.

Please correct me if there is a mistake in my understanding.

We have two tasks one FFT computation task and the other screen updating task

FFT computation task is highest priority task. it should be complete every 10us without failure .

The screen display task takes 1 ms to update screen and should be updated once every 17ms

 

No.
Often, you have to examine the consequences of an incomplete task and seek compromises.

There are three tasks in my example.

1) Collect data
2) Compute result
3) Display result

The top priority task is #1, collect data. No data point can be missed.

#2 and #3 tasks together can take up 100% of the CPU time. Results of each process may be delayed. What are the consequences of a delay? How much screen flicker is acceptable? How much of delayed update is acceptable.

Task #2 could be running in the background. If the results of the computation is delayed, what are the consequences?

Task #3 takes priority over task #2. At every 17ms, the screen update function is given priority over task #3. It is given a fixed window to process otherwise flicker on the screen becomes noticeable.

 

I am trying to understand how preemptive multitasking works. I don't understand how all tasks will be executed. once I understand the basics I will try to write plain c code, not for specific MCU but It should show some basic ideas for preemptive multitasking design

I am taking the following example after searching on the google

• I assume that we have three tasks.
• Each task has its own execution time.
• Each task needs to be completed within the time limit.
• Each task has a priority that should be followed.
• system time tick 1ms

View attachment 256247

LCM of the time period of all tasks is 40ms

40ms/8ms = 5
40ms/5ms = 8
40ms/10ms = 4

I don't understand how tasks will be executed between 15ms and 40ms?

Table for task execution on priority

1--------> T2 running
2--------> T2 running
3--------> T2 running
4--------> T2 running
5--------> T2 running
6--------> T1 running
7--------> T1 running
8--------> T1 running
9--------> T1 running
10-------> T1 running
11-------> T1 running
12-------> T1 running
13-------> T1 running
14------->
15------->
16------->
17------->
18------->
19------->
20------->
21------->
22------->
23------->
24------->
25------->
26------->
27------->
28------->
29------->
30------->
31------->
32------->
33------->
34------->
35------->
36------->
37------->
38------->
39------->
40------->
continue

can you @djsfantasi @click_here help in this matter

Like so so many things in computing - and operating systems are no exception - these concepts can be easily modeled using simply people and day to day activities.

If a person represents a CPU and a set of activities needs to be done, then all preemptive is, is a way to have the person work on an activity for a time and them remember where they are in the activity and jump to working on another activity.

To do that we might have a simple kitchen timer set to go off every five minutes say.

I could be in my workshop painting a wall and then when the timer goes off I stop that and move to say installing cabling in another wall. Again the timer goes off again and I stop wiring and go back to painting.

Pretty much all of the important abstract principles you see in a OS can be represented physically in an analogy like this.

Solve it for the analogy and you've likely solved it for the OS case too. For example if you had three people then you'd have to have ways for them to jump from activity to activity yet never let more than one person do any activity and so on.

 

There are three tasks in my example.

1) Collect data
2) Compute result
3) Display result

I came up with some facts after doing a little research

The spectrum analyzer capture a buffer of data from analog-to-digital converter.

You haven't mentioned. sampling time period so I'll just assume that it's N ms. CPU collects a single sample and waits for N ms to the next sample arrival. CPU is free to do other tasks for N ms. But the CPU does not have to miss a single sample which is its priority. When the next sample arrive it collects the sample and is free to do other task again for N ms.

1) What is sampling time period ?

2) What is the execution time of FFT ?
FFT and display cannot run longer than N ms

3) display update time is 1ms and it needs to be updated every 17ms.

 

The spectrum analyzer capture a buffer of data from analog-to-digital converter.

You haven't mentioned. sampling time period so I'll just assume that it's N ms. CPU collects a single sample and waits for N ms to the next sample arrival. CPU is free to do other tasks for N ms. But the CPU does not have to miss a single sample which is its priority. When the next sample arrive it collects the sample and is free to do other task again for N ms.

1) What is sampling time period ?

I gave an example of 10μs, i.e. sampling rate is 100ksps.
Sampling period could be any value. I have a system sampling at 40Msps, i.e. every 25ns.

That leaves 25ns for the processor? Go figure.

 

Don't be oversold on things such as floating point arithmetic, C++ and OOP, RTOS and multitasking.
They may make your life easier but they all come with a cost.

If the application is simple enough, you don't need any of the above.
If the application is marginally more complex then adding any of the above comes with baggage and overhead. Your system might take a hit in performance and necessitate more resources.

Only when the system is so complex and there is no viable alternative should you resort to using these higher level solutions.

 

The top priority task is #1, collect data. No data point can be missed
#2 and #3 tasks together can take up 100% of the CPU time. Results of each process may be delayed. What are the consequences of a delay? How much screen flicker is acceptable? How much of delayed update is acceptable.

Task #2 could be running in the background. If the results of the computation is delayed, what are the consequences?

Task #3 takes priority over task #2. At every 17ms, the screen update function is given priority over task #3. It is given a fixed window to process otherwise flicker on the screen becomes noticeable.

CPU collects a sample and waits for 10us to the next sample arrival. We will lose the incoming data If FFT and screen update takes more than 10us of CPU time.

If LCD is not updated within 17ms it will not show real time data. Updating the LCD requires at least 1ms CPU time.

I don't understand how CPU is sharing time for FFT and screen update. It's difficult to give full 1ms time for screen update. I don't have any idea how much short time the FFT take to perform?