Consider the following task workload pattern:

P1 7 1 10 P2 2 3 2 P3 3 5 7 P4 8 11 9 P5 15 14 4 P6 2 14 1 P7 4 21 9 P8 8 25 3 P9 10 28 5 P10 8 32 2

Assuming the multi-level scheduling policy described below scheduling policy, compute the average waiting time. Use the following format to illustrate the details of your computation:

T0: P1(10,7) arrival CPU: P1(10,7) [waited 0] Q1: Q2: Q3: P1(10,7)

T3: P2(2,2) arrival CPU: P1(10,5) [no wait] Q1: P2(2,2) Q2: Q3: P1(10,5)

T5: P3(7,3) arrival CPU: P1(10,3) [no wait] Q1: P2(2,2) Q2: Q3: P1(10,3) P3(7,3)

T6: P1 used its quantum of 5, Q3 adjusted CPU: P2(2,2) [waited 3] Q1: P2(2,2) Q2: P3(6,3) Q3: P1(9,2) ...

SCHEDULING POLICY

There are three queues Q1, Q2, and Q3:

Q1 corresponds to tasks with the priority p < 4 (HIGH) Q2 - for tasks with priorities p > 3 and p < 7 (NORMAL), and Q3 - for tasks with priority p > 6 (LOW). Initially, a new task is added to a queue that corresponds toit's priority.

CPU scheduler uses a RR routine (Q1-Q2-Q3) with variable time quantum of across all queues. Processes coming from Q1 are allocated 20 time units, the ones from Q2 - 10, and the lowest priority processes are allowed to run only for 5 time units.

A process with the highest priority is selected from within each queue. If there are a number of processes with the same priority, then the FCFS policy is used.

If any queue is empty, then a task from the next queue is selected.

Decrease the priority of every process by 1 on the expiry of each time quantum (for that queue only). A process is moved to the higher-priority queue if its current priority justifies that. Priority never gets below zero. If a process arrives on time quantum expiry, it's priority is not changed; i.e., the adjustment of the priorities is done before inserting a new process in a queue.