A process $P_i$ is scheduled to a processor $M_k$, if the processor is free and no other process $P_j$ is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?
Scheduling Processes with Non-Preemptive Priority Scheduling
This problem involves calculating the average waiting time for four processes ($P_1, P_2, P_3, P_4$) scheduled on two processors ($M_1, M_2$) using a non-preemptive priority scheduling algorithm. All processes arrive at the same time (time 0).
Understanding the Setup
- Processors: $M_1$, $M_2$
- Processes & CPU Bursts:
- $P_1$: 20 ms
- $P_2$: 16 ms
- $P_3$: 25 ms
- $P_4$: 10 ms
- Arrival Time: All processes arrive at time 0.
- Scheduling Algorithm: Non-preemptive Priority Scheduling.
- Processor $M_1$ Priority: $P_1 > P_3 > P_2 > P_4$ (Higher number means higher priority).
- Processor $M_2$ Priority: $P_2 > P_3 > P_4 > P_1$ (Higher number means higher priority).
- Scheduling Rule: A process runs if the processor is free and no higher priority process is waiting for that specific processor.
- Goal: Calculate the average waiting time.
Scheduling Simulation
We simulate the process execution step-by-step:
Initial Scheduling (Time = 0)
- Both processors $M_1$ and $M_2$ are free. All processes ($P_1, P_2, P_3, P_4$) are waiting.
- Processor $M_1$: Follows priority $P_1 > P_3 > P_2 > P_4$. The highest priority process available is $P_1$. Processor $M_1$ starts executing $P_1$.
- $P_1$ runs from time 0 ms to 20 ms (Burst time = 20 ms).
- Processor $M_2$: Follows priority $P_2 > P_3 > P_4 > P_1$. The highest priority process available is $P_2$. Processor $M_2$ starts executing $P_2$.
- $P_2$ runs from time 0 ms to 16 ms (Burst time = 16 ms).
Scheduling After $P_2$ Completes (Time = 16 ms)
- Processor $M_2$ becomes free at 16 ms.
- Processes remaining: $P_3$ (Burst=25), $P_4$ (Burst=10).
- Processor $M_1$ is still busy running $P_1$.
- Processor $M_2$: Priority is $P_2 > P_3 > P_4 > P_1$. Among the waiting processes ($P_3, P_4$), $P_3$ has the higher priority ($P_3 > P_4$). Processor $M_2$ starts executing $P_3$.
- $P_3$ runs from time 16 ms to $16 + 25 = 41$ ms.
Scheduling After $P_1$ Completes (Time = 20 ms)
- Processor $M_1$ becomes free at 20 ms.
- Process remaining: $P_4$ (Burst=10).
- Processor $M_2$ is busy running $P_3$.
- Processor $M_1$: Priority is $P_1 > P_3 > P_2 > P_4$. The only waiting process is $P_4$. Processor $M_1$ starts executing $P_4$.
- $P_4$ runs from time 20 ms to $20 + 10 = 30$ ms.
Process Completion Summary
- $P_1$ completed at 20 ms.
- $P_2$ completed at 16 ms.
- $P_4$ completed at 30 ms.
- $P_3$ completed at 41 ms.
Calculating Waiting Times
The waiting time for a process is the time elapsed from its arrival until it starts execution.
Waiting Time = Start Execution Time - Arrival Time
Since all processes arrive at time 0, the waiting time is simply the start time of execution.
- Waiting Time for $P_1$ ($W_{P1}$): Started at 0 ms. $W_{P1} = 0$ ms.
- Waiting Time for $P_2$ ($W_{P2}$): Started at 0 ms. $W_{P2} = 0$ ms.
- Waiting Time for $P_3$ ($W_{P3}$): Started at 16 ms. $W_{P3} = 16$ ms.
- Waiting Time for $P_4$ ($W_{P4}$): Started at 20 ms. $W_{P4} = 20$ ms.
Average Waiting Time Calculation
The average waiting time is the sum of all waiting times divided by the number of processes.
Average Waiting Time = $\frac{W_{P1} + W_{P2} + W_{P3} + W_{P4}}{4}$
Average Waiting Time = $\frac{0 \text{ ms} + 0 \text{ ms} + 16 \text{ ms} + 20 \text{ ms}}{4}$
Average Waiting Time = $\frac{36 \text{ ms}}{4}$
Average Waiting Time = $9$ ms
Therefore, the average waiting time of the processes is 9 milliseconds.
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.- 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)
