Read the following and answer the questions that follow. Consider the following set of processes with the arrival time and length of CPU Burst time given in milli-seconds (ms):Process Arrival Time Burst Time P1 0 5 P2 2 3 P3 2 2 P4 5 3 P5 6 1
Find the average weighted turnaround time for these process using Highest Response Ratio Next (HRN) Algorithm?
2.834 ms
Highest Response Ratio Next is non-preemptive; when the CPU becomes free it picks the ready process with the largest \(RR = \dfrac{W + S}{S}\), where W is the time waited so far and S the burst time. Weighted (normalised) turnaround time = turnaround time / burst time.
Step 1 — t = 0: only P1 is ready, it runs 0–5.
Step 2 — t = 5: P2 \(\tfrac{3+3}{3}=2\), P3 \(\tfrac{3+2}{2}=2.5\), P4 \(\tfrac{0+3}{3}=1\); P3 runs 5–7.
Step 3 — t = 7: P2 \(\tfrac{5+3}{3}\approx 2.67\), P4 \(\tfrac{2+3}{3}\approx 1.67\), P5 \(\tfrac{1+1}{1}=2\); P2 runs 7–10.
Step 4 — t = 10: P4 \(\tfrac{5+3}{3}\approx 2.67\), P5 \(\tfrac{4+1}{1}=5\); P5 runs 10–11, then P4 runs 11–14.
| Process | Arrival | Burst | Finish | Turnaround | Turnaround / Burst |
|---|---|---|---|---|---|
| P1 | 0 | 5 | 5 | 5 | 1.000 |
| P2 | 2 | 3 | 10 | 8 | 2.667 |
| P3 | 2 | 2 | 7 | 5 | 2.500 |
| P4 | 5 | 3 | 14 | 9 | 3.000 |
| P5 | 6 | 1 | 11 | 5 | 5.000 |
Step 5 — \(\text{Average weighted turnaround} = \dfrac{1 + 2.667 + 2.5 + 3 + 5}{5} = \dfrac{14.167}{5} \approx 2.83\), which is the 2.834 value given. The plain average turnaround is 32/5 = 6.4 ms, so 6.721 ms is not it either, and 3.2 ms and 1.632 ms do not match the normalised values.
2.834 ms option is correct.
Similar Questions
Which of the following statements is not true for Multi Level Feedback Queue processor scheduling algorithm ?
Consider a uniprocessor system where new processes arrive at an average of five processes per minute and each process needs an average of 6 seconds of service time. What will be the CPU utilization ?
Match the following :
List - I List - II a. Multilevel feedback queue i. Time-slicing b. FCFS ii. Criteria to move processes between queues c. Shortest process next iii. Batch processing d. Round robin scheduling iv. Exponential smoothening Codes :
Match List - I with List - II.
List - I (Algorithms) List - II (Characteristics) (A) First Come First Served (FCFS) (I) Each process is assigned a priority. (B) Shortest Job First (SJF) (II) Ensures fair allocation of CPU time by assigning time slice. (C) Round Robin (RR) (III) Processes are executed in the order they arrive. (D) Priority Scheduling (IV) Select the process for execution with smallest next Burst time. Choose the correct answer from the options given below :
What is the average turnaround time for these Processes with First Come First Serve (FCFS) scheduling Algorithm?
When we apply Shortest Job First (SJF) scheduling Policy/algorithm, Process (P2) faces partial starvation and waits for the longer time to execute. Which one of the following non-preemptive algorithms addresses this problem?
Calculate the average response time for these processes with nonpreemptive priority Scheduling algorithm? Priority of the process are as follows and consider that all the processes came at zero (0) time. (Note low numbers represent high priority).
Process Burst Time Priority P1 5 3 P2 3 1 P3 2 5 P4 3 4 P5 1 2 What is the average waiting time for these processes with non-preemptive Shortest Job First (SJF) scheduling Algorithm?
Given the following processes with their times and priority (lower number indicates higher priority)
Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Which of the following is a value of average waiting time using priority scheduling algorithm?
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.
Process Name Arrival Time Execution Time A 0 6 B 3 2 C 5 4 D 7 6 E 10 3 Using the shortest remaining time first scheduling algorithm, the average process turnaround (in milliseconds) is ________.
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 - A scheduling Algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (lowest priority). The scheduler reevaluates the process priority for every ‘T’ time units and decides next process to be scheduled. If the process have no I/O operations and all arrive at time zero, then the scheduler implements _________ criteria.
