Algorithm Scenario Analysis
The scheduling algorithm assigns priority based on waiting time, with processes starting at priority zero. Priorities are reassessed every T time units.
Key Conditions Analysis
- All processes arrive simultaneously at time 0.
- There are no Input/Output (I/O) operations.
- Priority increases proportionally with the time a process waits.
- Priority is re-evaluated at fixed intervals of T time units.
Reasoning for Round Robin Scheduling
Under these specific conditions, the algorithm effectively implements Round Robin scheduling:
- The fixed interval T acts as a time quantum, limiting the execution time for any process in one go.
- While a process executes, its waiting time does not increase.
- Processes that are ready but not currently running accumulate waiting time.
- Upon re-evaluation every T units, processes that have waited longer will naturally have accumulated more waiting time, thus gaining higher priority.
- This periodic reassessment and selection based on accumulated waiting time ensures a fair distribution of CPU time. Processes that wait longer get prioritized in subsequent scheduling turns.
- This cyclical process, constrained by the time quantum T, is the hallmark of Round Robin scheduling, ensuring that no single process monopolizes the CPU and all processes eventually get a chance to run.
Conclusion
The described scheduling mechanism, under the constraints of simultaneous arrival and no I/O, results in the implementation of Round Robin Scheduling criteria.
Important Questions from CPU Scheduling
Assume that the following tasks are to be executed on a single processor system. All tasks have arrived at 0 msec.
Job ID CPU a 4 b 1 c 7 d 2 How long does it take for task "a" to complete if the scheduling time slice is a round-robin with 1 ms?
- 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?
