web analytics

Explain and Solve : Round Robin (RR) CPU Scheduling Algorithm in C++ with Explanation

If you haven’t read/tried the earlier/other problems then click the links follow:

Round Robin CPU Scheduling Algorithm in C++ with Explanation: 

This method is quite same as the FCFS but the difference is the in this case the processor will not process the whole job (process) at a time. Instead, it will complete an amount of job (quantum) at a turn and then will go to the next process and so on. When all job has got a turn, it will again start from the first job and work for a quantum of time/cycle on each job and proceed. Now consider a CPU and also consider a list in which the processes are listed as follows,

Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1
Quantum = 2 Second
Here, Arrival is the time when the process has arrived the list, Process Number is used instead of the process name, and Burst Time is the amount of time required by the process from CPU. Well, as the unit of time you can take anything like nano-second, second, minute etc whatever. We consider it as second.
Now for an instance, consider the above list as the ready queue for the CPU, that is the CPU will take processes from this list and will process it.
Here in Round Robin, what will happen is as follows,
AT 0s:
            There is only 1 job, that is Process-1 with burst time 3. So CPU will do 1 quantum amount (that is 2 second of job) job of Process-1. Thus Process-1 has 1s more job to be done. And now the time is 2s as CPU worked on process-1 at 0s and 1s (for 2 second, right?)
AT 2s:
            Now there are 3 jobs,
                        Process-1 that arrived at 0s and has 1s job to be done.
                        Process-2 that arrived at 1s and has 2s job to be done.
                        Process-3 that arrived at 2s and has 1s job to be done.
            At the previous turn, CPU worked on process-1, so this time it will work on process-2. It will for a quantum time (that is, 2 second). Thus process-2 has 0s more job to be done and now time is 4s as CPU worked on process-2 at 2s and 3s.
AT 4s:
            Now there are 2 jobs,
                        Process-1 that arrived at 0s and has 1s job to be done.
                        Process-3 that arrived at 2s and has 1s job to be done.
Now it is the turn of process-3. Process-3 has less job than a quantum. So CPU will work for the amount of job that process-3 has (CPU can work for less or equal amount of time than quantum). So process-3 has 0s job more to be done and now the time is 5s as CPU worked on process-3 only at 4s.
AT 5s:
            There are no more jobs after process-3. So now the process will start from the beginning. So this is the turn of process-1. Process-1 has 1s job to be done. CPU will complete it as it is less than the quantum.
All Job Done.
We can show the above thing as the following time-line
Process-1
Process-1
Process-2
Process-2
Process-3
Process-1
0s
1s
2s
3s
4s
5s
A shortened view of the above time-line is as follows,
| Process-1
| Process-2
| Process-3
| Process-1
|
0                
2
4
5
6
So now came the main thing, Waiting Time. Okay, Look carefully,

See the following time-line for Process-1. Here, RED marked seconds symbolizes the seconds while Process-1 was waiting and GREEN marked second symbolizes the seconds while Process-1 was working.
Process-1
Process-1
Process-2
Process-2
Process-3
Process-1
0s
1s
2s
3s
4s
5s
Thus Process-1 waited for 3 seconds.
See the following time-line for Process-2. Here, RED marked seconds symbolizes the seconds while Process-2 was waiting and GREEN marked second symbolizes the seconds while Process-2 was working.
Process-1
Process-1
Process-2
Process-2
Process-3
Process-1
0s
1s
2s
3s
4s
5s
Thus Process-2 waited for 1 seconds.
See the following time-line for Process-3. Here, RED marked seconds symbolizes the seconds while Process-3 was waiting and GREEN marked second symbolizes the seconds while Process-3 was working.
Process-1
Process-1
Process-2
Process-2
Process-3
Process-1
0s
1s
2s
3s
4s
5s
Thus Process-3 waited for 2 seconds.
So total waiting time = (Waiting Time of Process-1)+ (Waiting Time of Process-2)
                                      + (Waiting Time of Process-3)
                                   = (3+1+2)s
                                   = 6s
So the average waiting time is = (Total waiting time / Number of Processes)s
                                                 = (6/3)s
                                                 = 2s
Okay. I think you have understood the thing. Now lets talk about the program. Move on to the next part.
Input: You will ask the user for the number of processes. Then for each process you will take its Process Number, Arrival Time and its Burst time. You don’t have to worry, the number of processes wont be more than 5 or 6, Arrival time of a process can only be equal or greater than the arrival time of its previous process and Process will be entered as a serial number, so no problem.
Output: In the output you will have to print out the shortened time-line we showed you above. For example, if the input is as follows,
Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1
Quantum = 2s
Then the shortened time-line will be,
| Process-1
| Process-2
| Process-3
| Process-1
|
0                
2
4
5
6
You can also print out the time-line vertically if you want (thats what I have done, see the output of my program)
Ok beneath this shortened time-line you will have to print a table as follows,
Process
Arrival
Finish
Total
Wait
2
1
3
2
1
3
2
4
1
2
1
0
5
3
3
                                             
Beneath this, you will have to show the Average Waiting Time.

I know you have understood, now see a screen-shot of exactly what I was talking about,



Exception: One exception is that, I said “Arrival time of a process can only be equal or greater than the arrival time of its previous process”. So take a look at the following list of process,
Arrival
Process
Burst Time
0
1
6
55
2
2
60
3
1
Quantum = 2s
You see, CPU will on process-1 for 1 quantum at 0s and 1s. After that, at 2s it has no job to do, so it will return and will another quantum of job of process-1 at 2s and 3s. After that, at 4s it still has nothing to do so it will return and will do another quantum of job of process-1 at 4s and 5s. At 6s, it still has nothing to do so it will return and find that process-1 is also complete. So the processor will start remaining IDLE from here to the next process on the list.
The job Process-2 arrived at 55s, so the CPU will work for 1 quantum on process-2 at 55s and 56s and from 57s it will again remain IDLE until the next job arrives.

The next job process-3 arrived at 60s with burst time 1s. Thus CPU will do 1s job of process-3 at 60s and as all the job are done, your program now can take a break… See the following screenshot,



You can download my program on this (.exe) from this link, click here.


This was the last problem or you can say algorithm on this series. I don’t think people have enjoyed these posts, however these are what I do…Thanks for being here.

Please follow and like us:
Pin Share

26 thoughts on “Explain and Solve : Round Robin (RR) CPU Scheduling Algorithm in C++ with Explanation”

  1. yes, but facing problem with displaying output. displaying formatted output is the most annoying thing

  2. You are the first one among all readers of these 4 related posts who Tried and Replied.

    I am sure, if can solve the problem, you will make the output too.

    However, have you done it the same way I explained here, I mean is your program outputting the same as my program?

    Even if it is or not, don't forget to post the program.

    Good Luck.

  3. Is round robin a simple application of queue or is it much more 'cause i cannot understand many of the terms in your explanation

  4. FCFS is something related to Queue, but not Round Robin directly. Here the first process that will arrive will get processed first, thats ok, but may not get completely processed. For example, consider there are 3 processes,

    1st process with burst time 8sec
    2nd process with burst time 6sec
    3st process with burst time 3sec

    Also consider that our processor only process 4sec of job of a single process at a time. thus it will

    In 1 to 4 sec, will process 4sec of job of process 1
    In 5 to 8 sec, will process 4sec of job of process 2
    In 9 to 11 sec, will process 3sec of job of process 3 [cause, process 3 has only 3 sec of burst time], process 3 is done; process 1 and 2 are having jobs remaining.

    Then, it will return to process 1 as again and work as follows,

    In 12 to 15 sec, will process 4sec of job of process 1 [Thus process 1 is done]
    In 16 to 17 sec, will process 2sec of job of process 2 [Thus process 2 is done]

    This is what is RR, work for a limited time for all the processes, then again start working from the beginning and continue finishing jobs.

    This 4sec working limit of our processor is the quantum time in this case, which means, it can only work for less than or equal to 4 sec of a process at a turn.

  5. You can not use floating values in my program, because to bring the simulation first, everything is in seconds, no floating. Secondly, to test your program in my program, use Integer values as process number.

    And last thing is, I haven't wrote or post this to get inputs from readers, I did post it here to inspire others to write a program that will do the work.

  6. Arrival times will never be same, they just can be so SO so close, but not the same. Even if the processor is having multiple cores, each core will receive processes 1 by 1, none will receive 2 at the same time. Things happen way too fast (faster than nanoseconds may be). And more than that, even in parallel computing, each process hits different processor, that can be at the same time, but at different processors, so still not the same.

  7. It is very good to learn from this, but I would tell you about a big mistake in Round Robin. "At the previous turn, CPU worked on process-*2, so this time it will work on process-2."
    *Instead of process-2, process-1 would come, That so I believe..
    Thank you..
    If I am wrong then please tell me why…

  8. Thanks for sharing! Can you show us the source code of the program too, on how this scheduling possible on c++ or java.

Comments are closed.

RSS
Follow by Email
Scroll to Top