Assume that the following tasks are to be executed on a single processor system. All tasks have arrived at 0 msec. How long does it take for task "a" to complete if the scheduling time slice is a round-robin with 1 ms?Job ID CPU a 4 b 1 c 7 d 2
10
Understanding the Round Robin Scheduling Problem
This problem asks us to determine the completion time of a specific task, task "a", when multiple tasks are scheduled on a single processor using the Round Robin scheduling algorithm. All tasks arrive at the same time (0 msec), and the scheduling uses a fixed time slice (quantum) of 1 ms.
What is Round Robin Scheduling?
Round Robin (RR) is a CPU scheduling algorithm where each process is assigned a fixed time slice (quantum) in a cyclic way. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval up to one time slice. If a process finishes its burst time within the time slice, it is terminated. If not, the process is preempted and added to the end of the ready queue.
Analyzing the Given Tasks and Time Slice
We have the following tasks with their CPU burst times:
- Task "a": 4 ms
- Task "b": 1 ms
- Task "c": 7 ms
- Task "d": 2 ms
All tasks arrive at time 0 msec. The time slice for Round Robin is 1 ms.
Step-by-Step Round Robin Execution Simulation
Let's simulate the execution of these tasks using the 1 ms time slice. We will assume the initial ready queue order is [a, b, c, d].
| Time Interval (ms) | Task Executing | Remaining CPU Burst | Ready Queue (after execution/preemption) | Notes |
|---|---|---|---|---|
| 0 - 1 | a | a=3, b=1, c=7, d=2 | [b, c, d, a] | 'a' runs for 1ms. Preempted, added to end. |
| 1 - 2 | b | a=3, b=0, c=7, d=2 | [c, d, a] | 'b' runs for 1ms. Finishes. |
| 2 - 3 | c | a=3, c=6, d=2 | [d, a, c] | 'c' runs for 1ms. Preempted, added to end. |
| 3 - 4 | d | a=3, c=6, d=1 | [a, c, d] | 'd' runs for 1ms. Preempted, added to end. |
| 4 - 5 | a | a=2, c=6, d=1 | [c, d, a] | 'a' runs for 1ms. Preempted, added to end. |
| 5 - 6 | c | a=2, c=5, d=1 | [d, a, c] | 'c' runs for 1ms. Preempted, added to end. |
| 6 - 7 | d | a=2, c=5, d=0 | [a, c] | 'd' runs for 1ms. Finishes. |
| 7 - 8 | a | a=1, c=5 | [c, a] | 'a' runs for 1ms. Preempted, added to end. |
| 8 - 9 | c | a=1, c=4 | [a, c] | 'c' runs for 1ms. Preempted, added to end. |
| 9 - 10 | a | a=0, c=4 | [c] | 'a' runs for 1ms. Finishes. |
From the simulation table, we can see the timeline of execution. Task 'a' runs during the intervals 0-1, 4-5, 7-8, and 9-10.
Task 'a' completes its required 4 ms of CPU burst at the end of the time interval 9-10 msec. Therefore, the completion time for task "a" is 10 msec.
Determining Task "a" Completion Time
Task "a" requires a total CPU burst of 4 ms.
- It runs from 0 to 1 ms (1 ms completed). Remaining burst: 3 ms.
- It runs from 4 to 5 ms (1 ms completed). Remaining burst: 2 ms.
- It runs from 7 to 8 ms (1 ms completed). Remaining burst: 1 ms.
- It runs from 9 to 10 ms (1 ms completed). Remaining burst: 0 ms.
Task 'a' finishes exactly at the 10 msec mark.
Thus, the time it takes for task "a" to complete is 10 msec.
Revision Table: Key Round Robin Concepts
| Concept | Description |
|---|---|
| Round Robin (RR) Scheduling | A preemptive scheduling algorithm where each process gets a fixed time slice (quantum) of CPU time in a cyclic order. |
| Time Slice (Quantum) | A small unit of time assigned to each process in RR scheduling. After this time, the process is preempted. |
| CPU Burst | The amount of time a process needs the CPU to complete its execution. |
| Completion Time | The time at which a process finishes its execution. |
Additional Information: Related CPU Scheduling Algorithms
While Round Robin is used here, other common CPU scheduling algorithms include:
- First-Come, First-Served (FCFS): Processes are executed in the order they arrive. Non-preemptive.
- Shortest Job Next (SJN)/Shortest Job First (SJF): The process with the smallest CPU burst time is executed next. Can be preemptive (SRTF) or non-preemptive.
- Priority Scheduling: Processes are executed based on their priority. Can be preemptive or non-preemptive.
Each algorithm has different characteristics regarding throughput, turnaround time, waiting time, and response time.
Important Questions from CPU Scheduling
- Consider the following processes with CPU Burst time P1, P2, P3 arrived at time 0.
Process CPU Burst Time (MS) P1 24 P2 3 P3 3
What is the average waiting time of these processes executed using FCFS algorithm. Consider the following table about processes, their burst time and arrival time
Process Burst Time Arrival Time P1 09 0 P2 30 0 P3 04 0 P4 08 2 P5 11 6
Now which of the process shall finish second last as per the respective GANTT charts for the non- preemptive SJF and Round Robin (time quantum = 10) scheduling methods.- A computer has two processors, $M_1$ and $M_2$. Four processes $P_1, P_2, P_3, P_4$ with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
- $M_1$ uses priority of execution for the processes as, $P_1 > P_3 > P_2 > P_4$, i.e., $P_1$ and $P_4$ have highest and lowest priorities, respectively.
- $M_2$ uses priority of execution for the processes as, $P_2 > P_3 > P_4 > P_1$, i.e., $P_2$ and $P_1$ have highest and lowest priorities, respectively.
- Processes $P_1, P_2, P_3, P_4$ arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively.
Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.
Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds? - Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time $t = 10$, 20, 30, 40, and 50 (in seconds). Similarly, a new process of type C arrives at time $t = 11$, 22, 33, 44, and 55 (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at $t = 10$ seconds. The average waiting time (in seconds) for the 10 processes is ___________. (rounded off to one decimal place)
