I am trying to understand the Round Robin preemptive scheduling example given in link

https://en.m.wikipedia.org/wiki/Round-robin_scheduling

I don't understand what is shown in this picture. I don't understand which task or process is executing when its executing and for how long its executing



Does anyone understand what is happening in this diagram and what is the purpose of this

 

The black is where a process is executing and the gray is where it is waiting white is before it is started or after it has finished.

Looking across:

time 0 is p1
time 1 and 2 is p2
time 2 3 an 4 is p3

etc.

Bob

 

The black is where a process is executing and the gray is where it is waiting white is before it is started or after it has finished.

Looking across:

time 0 is p0
time 1 and 2 is p1
time 2 3 an 4 is p2

etc.

Bob

I still don't get how all 10 tasks/process execute on single-processor. I don't see P0 anywhere process is starting from P1 and ending on P10

 

There is no P0 process.
The processes are numbered P1 to P10.

 

Sorry, my numbers should be p1, p2 and p3. Edited post to correct it.

Note that the (x,y) after each process is start time, run time.

Bob

 

I still don't get how all 10 tasks/process execute on single-processor. I don't see P0 anywhere process is starting from P1 and ending on P10

They execute at different times! That is the whole point of multi-tasking.

Bob

 

They execute at different times! That is the whole point of multi-tasking.

That's what I want to understand which process is executed when and for how long.

Note that the (x,y) after each process is start time, run time.

I think I'm going in the same direction as you mentioned but I don't understand what will happen after Time 23?

Please check my sequence

Time 0  P1 executing

Time 1  P2 executing

Time 2  P2 executing

Time 3  P3 executing

Time 4  P3 executing

Time 5  P3 executing

Time 6  P4 executing

Time 7  P4 executing

Time 8  P4 executing

Time 9  P5 executing

Time 10  P5 executing

Time 11  P5 executing

Time 12  P6 executing

Time 13  P6 executing

Time 14  P6 executing

Time 15  P7 executing

Time 16  P7 executing

Time 17  P7 executing

Time 18  P8 executing

Time 19  P8 executing

Time 20  P8 executing

Time 21  P9 executing

Time 22  P9 executing

Time 23  P10 executing

 

The other thing to note is the quantum 3. No process gets more than 3 quanta of time in one go. Once a task is scheduled it gets its fair share 'round robin', but no task has priority... so task P1-P5 get scheduled at time 0. P1 completes in 1 quanta so P2 gets to start and completes in 2 quanta. P3 then gets 3 of its 4 and gives way to P4 which gets 3 of its 6 and similarly P5 gets 3 of its 8. While P5 was running P6 - P10 appeared on the schedule and so each get 3 quanta in sequence though P9 and P10 don't need or use all 3 and release early. NOW we see the full meaning of round robin... the scheduler looks back at the top of the the list to see the next runnable task, which is P3, which completes its final quanta and releases, and similarly P4. P5 gets another 3 quanta but not having finished goes back into the schedule. P6 gets another go and goes back on the list giving way to P7 and P8 which both complete dropping off the schedule leaving P5 and then P6 to complete.

Round robin is works best where there are a lot of similarly sized tasks and none are particularly time critical. Its a fairly lightweight and easily implemented scheduling mechanism. A task arriving on the list will get to run in exact sequence. No task has priority and each gets the same amount of time in one go. Tasks do not automatically re-run, they must put themselves back on the list or some other mechanism does - they go back on the list AFTER any task already on the list - so if at time 37 P1 wanted to run again it wouldn't until P5 and P6 completed.

 

The other thing to note is the quantum 3. No process gets more than 3 quanta of time in one go. Once a task is scheduled it gets its fair share 'round robin', but no task has priority... so task P1-P5 get scheduled at time 0. P1 completes in 1 quanta so P2 gets to start and completes in 2 quanta. P3 then gets 3 of its 4 and gives way to P4 which gets 3 of its 6 and similarly P5 gets 3 of its 8. While P5 was running P6 - P10 appeared on the schedule and so each get 3 quanta in sequence though P9 and P10 don't need or use all 3 and release early. NOW we see the full meaning of round robin... the scheduler looks back at the top of the the list to see the next runnable task, which is P3, which completes its final quanta and releases, and similarly P4. P5 gets another 3 quanta but not having finished goes back into the schedule. P6 gets another go and goes back on the list giving way to P7 and P8 which both complete dropping off the schedule leaving P5 and then P6 to complete.

Round robin is works best where there are a lot of similarly sized tasks and none are particularly time critical. Its a fairly lightweight and easily implemented scheduling mechanism. A task arriving on the list will get to run in exact sequence. No task has priority and each gets the same amount of time in one go. Tasks do not automatically re-run, they must put themselves back on the list or some other mechanism does - they go back on the list AFTER any task already on the list - so if at time 37 P1 wanted to run again it wouldn't until P5 and P6 completed.

Irving Thanks understood what is happening in the picture.

After this there are two more pictures which I don't understand. I mainly do not understand the third diagram, what is happening in it?.

There are 5 tasks in total. CPU giving each task 100 ms of processing time before moving on to the next. The task may or may not be completed within 100 ms, and when their turn comes they will often pick up where they left off. CPU takes total 775 time to complete all 5 tasks.

 

Irving Thanks understood what is happening in the picture.

After this there are two more pictures which I don't understand. I mainly do not understand the third diagram, what is happening in it?.

There are 5 tasks in total. CPU giving each task 100 ms of processing time before moving on to the next. The task may or may not be completed within 100 ms, and when their turn comes they will often pick up where they left off. CPU takes total 775 time to complete all 5 tasks.

It works exactly the same way as the first example except that second diagram essentially shows the state of the scheduling queue at the relevant event times rather than showng the active/wait diagram for the individual tasks. Same info, different format.

 

It works exactly the same way as the first example except that second diagram essentially shows the state of the scheduling queue at the relevant event times rather than showng the active/wait diagram for the individual tasks. Same info, different format.

I think I got it. CPU gives each task 100 ms of processing time before moving on to the next. The task may or may not be completed within 100 ms, and when their turn comes they will often pick up where they left off. CPU takes a total of 775 ms times to complete all 5 tasks.

@DickCappels
You have mentioned in another thread https://forum.allaboutcircuits.com/threads/how-do-i-create-my-own-rtos.184129/ #22 that you have used round-robin scheduling. Can you tell How you have used it for a specific project?

@MrChips
Do you have any idea which project you think when you think of a round-robin scheduling algorithm?

 

This is what the hardware looks like:



Control Panel and LED Display Controller Firmware

This program is meant to simulate an ASCII serial terminal for the purpose of displaying control panel information from the Waveform Capture controller on a 4 digit LED clock display and accepting input from a set of push buttons on the control panel. There are five tasks called by the interrupt-driven round robin multitasked, which are:

1. Refresh LED display digit 1
2. Refresh LED display digit 2
3. Refresh LED display digit 3
4. Refresh LED display digit 4
5. Get the status of control panel buttons.

Communication with the waveform capture controller is via the on-chip hardware UART running at 9600 baud, 1 stop bit, no parity.

If, while loading the status of the control panel buttons, a button is found to be down, the controller will wait for the button to be released before sending the button's associated code and continuing program execution.

The details can be found at http://www.cappels.org/dproj/wfcp/wfcp.htm

 

@DickCappels Thank you

Your code is written in assembly language and I don't know assembly language. I tried to understand how all the five tasks are executed by reading the comments given in the code. But I could not figure out how and when you are scheduling the each task.

I'm trying to find out how long each task executes and how many times it executes. What is the maximum CPU time you are giving for each task? have you set timer interrupt what time it occur?

 

There is a loop and within it are sequential calls to each task. When the last task is completed the machine goes back to the start of the loop. Each task takes the amount of time it needs before returning to the loop.

It is not sophisticated but in this application it just needs to tie two other controllers together along with the interface to the user.

 

There is a loop and within it are sequential calls to each task. When the last task is completed the machine goes back to the start of the loop. Each task takes the amount of time it needs before returning to the loop.

It is not sophisticated but in this application it just needs to tie two other controllers together along with the interface to the user.

In a round robin scheduling algorithm it is necessary to know the time slice and how long each execute.

How much time slice you have set in your project?

How long each task executes?

 

If you look at the source code, you can see that I have listed the execution times as comments.

You can assign time to allow a task to run then execute a break, software interrupt or other interrupt (depending upon what your machine supports) and yank your machine out of tasks and that might be preferred at times. For what I do, which is embedded code that is frozen in place at the time it is burned into the controller memory, such flexibility is not needed, and besides it carrys the overhead of managing the return address so the task can resume execution when running the task again.

The execution times were important to assure that the refresh rate of the LED display was adequate to avoid appearing to flicker.

I am sorry if my examples are not suited to a RTOS like what you are considering. You can merely start with a simple round robin task manager and then modify it when you need to add flexibility, or maybe your style is similar to that which others encourage - sit down and draw up a comprehensive specification before writing any code. Both paths lead to the same place, only one starts showing results sooner.