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?
- 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? - Which one of the following CPU scheduling algorithms cannot be preemptive?
- 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)
