Go Back

A Quick Abstract:

1. Introduction to Round Robin Scheduling:

Definition:

 Round Robin is a preemptive CPU scheduling algorithm that assigns a fixed time quantum to each process. Processes are executed in a circular order, with each process receiving CPU time for a specified quantum before moving to the next.

2. Time Quantum:

Time Quantum:

Each process is allocated a fixed time quantum for execution on the CPU.

3. Execution and Process Rotation:

Execution:

A process runs for its allocated time quantum or until it voluntarily releases the CPU.

Process Rotation:

If a process completes before its time quantum expires, the next process in the queue is selected.

If a process's time quantum elapses, it is moved to the back of the ready queue, and the next process is chosen.

4. Waiting Time and Turnaround Time:

Waiting Time:

Waiting time is the cumulative time a process spends waiting in the ready queue.

Turnaround Time:

Turnaround time is the overall time taken by a process from submission to completion.

5. Pros and Cons:

Pros:

Fair distribution of CPU time among processes.

Suitable for time-sharing systems and environments with varying process burst times.

Cons:

Overheads associated with context switching.

May not be optimal for processes with consistent, long burst times.

6. Starvation:

Round Robin is designed to prevent starvation, as each process is guaranteed a time quantum on the CPU.

7. Example Scenario:

Consider processes A, B, and C with time quantum 4.

A → B → C → A → B → C → ... (and so on)

Processes rotate in a cyclic manner, each receiving CPU time for the specified time quantum before moving to the next.

8. Conclusion:

Round Robin scheduling provides a balanced approach to CPU allocation, ensuring fairness among processes. While it may incur context-switching overhead, Round Robin is well-suited for environments with diverse process burst times.

Notes From The Slides:

Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds.  After this time has elapsed, the process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once.  No process waits more than (n-1)q time units.
• Timer interrupts every quantum to schedule next process
• Performance

• q large  FIFO
• q small  q must be large with respect to context switch, otherwise overhead is too high

Example of RR with Time Quantum = 4

Process	Burst Time
P1	24
P2	3
P3	3

• The Gantt chart is:

• Typically, higher average turnaround than SJF, but better response
• q should be large compared to context switch time

• q usually 10 milliseconds  to 100 milliseconds,
• Context switch < 10 microseconds

Time Quantum and Context Switch Time

Turnaround Time Varies With The Time Quantum

80% of CPU bursts should be shorter than q