Process Burst Time Priority $P_1$ 10 3 $P_2$ 1 1 $P_3$ 2 4 $P_4$ 1 5 $P_5$ 5 2
Priority Scheduling Average Waiting Time Calculation
This solution calculates the average waiting time for processes using non-preemptive priority scheduling. It assumes a lower numerical value indicates a higher priority.
Process Details
| Process | CPU Burst Time (ms) | Priority | Arrival Time (ms) |
|---|---|---|---|
| P1 | 10 | 3 | 0 |
| P2 | 1 | 1 | 0 |
| P3 | 2 | 4 | 0 |
| P4 | 1 | 5 | 0 |
| P5 | 5 | 2 | 0 |
Execution Order Determination
Processes are scheduled based on priority. Lower numbers mean higher priority. All arrive at time 0, so the execution order is determined solely by priority.
- Priority 1: P2
- Priority 2: P5
- Priority 3: P1
- Priority 4: P3
- Priority 5: P4
The non-preemptive execution sequence is: P2 → P5 → P1 → P3 → P4.
Calculating Individual Waiting Times
Waiting Time = Start Time - Arrival Time. Since all processes arrive at time 0, Waiting Time = Start Time.
| Process | Burst Time (ms) | Priority | Start Time (ms) | Waiting Time (ms) | Completion Time (ms) |
|---|---|---|---|---|---|
| P2 | 1 | 1 | 0 | 0 | 1 |
| P5 | 5 | 2 | 1 | 1 | 6 |
| P1 | 10 | 3 | 6 | 6 | 16 |
| P3 | 2 | 4 | 16 | 16 | 18 |
| P4 | 1 | 5 | 18 | 18 | 19 |
Average Waiting Time Computation
Sum the waiting times of all processes and divide by the total number of processes.
- Total Waiting Time = 0 + 1 + 6 + 16 + 18 = 41 ms
- Average Waiting Time = $ \frac{\text{Total Waiting Time}}{\text{Number of Processes}} $
- Average Waiting Time = $ \frac{41}{5} $ ms
- Average Waiting Time = 8.2 ms
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)
