Question

Consider a multilevel feedback queue shown below. Assuming that the following processes are the only ones that exist, determine the finish time for each of the processes. Assume that each queue is following FCFS scheduling policy. CPU first schedules all processes in the top queue (Quantum-8) before scheduling processes in queue 2 (Quantum 16), and only then it will schedule processes in queue 3 (FCFS). CPU Burst time Arrival time Priority Process P1 8 15 1 P2 10 15 2 P3 25 5 P4 32 20 5 P5 15 25 4 quantum 8 16 quantum FCFS

Answer 1

In FCFS (First come, First Serve), a process is run till completion in order which they arrive and only then the next process is undertaken.

In Multilevel Feedback Queue, if a process exceeds the quantum limit, it gets demoted to the lower queue. All processes in a higher priority queue are executed before any of the lower priority queues are touched. The last queue has no quantum limit, it processes each process till completion (FCFS).

This is the sequence flow: (For simplicity, whenever I mention a number, assume it's time)

P3 arrives at 5, and runs for 8. Demotes to queue2 P3: 5 - 13 (remaining 17)

P2 was already in the queue at 10, it starts at 13 and runs for 8. Demotes to queue2 P2: 13 - 21 (remaining 7)

P1 was already in the queue at 15, it starts at 21 and runs for 8. As it only required 8, it exits P1: 21 - 29 (exits)

P4 was already in the queue at 20, it starts at 29 and runs for 8. Demotes to queue2 P4: 29 - 37 (remaining 24)

P5 was already in the queue at 25, it starts at 37 and runs for 8. Demotes to queue2 P5: 37 - 45 (remaining 7)

.................................................................................................................................................................................

Now the first queue is empty, the second queue looks like this: P3 -> P2 -> P4 -> P5

.................................................................................................................................................................................

P3 continues execution at 45, runs for 16 (quantum=16). Demotes to queue3 P3: 45 - 61 (remaining 1)

P2 continues at 61, runs for 7 (as only 7 remaining). Exits P2: 61 - 68 (exits)

P4 continues at 68, runs for 16. Demotes to queue3 P4: 68 - 84 (remaining 8)

P5 continues at 84, runs for 7 (as only 7 remaining). Exits P5: 84 - 91 (exits)

.................................................................................................................................................................................

Now the first and the second queues are empty, the third queue looks like this: P3 -> P4

.................................................................................................................................................................................

P3 continues at 91, runs for 1. Exits P3: 91 - 92 (exits)

P4 continues at 92, runs for 8. Exits P4: 92 - 100 (exits)

.................................................................................................................................................................................

Now to determine the finish times, see where each process exited.

P1: 29

P2: 68

P3: 92

P4: 100

P5: 91

.................................................................................................................................................................................

If you have any doubts, feel free to comment and I'll be happy to respond!