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
- 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.
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.- 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 set of processes assumed to have arrived at time 0 in order $P_1, P_2, P_3, P_4$ and $P_5$ with the length of CPU burst given in Milliseconds.What is the average waiting time (in milliseconds) using priority scheduling.
Process Burst Time Priority $P_1$ 10 3 $P_2$ 1 1 $P_3$ 2 4 $P_4$ 1 5 $P_5$ 5 2 - 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)
