Multilevel feedback queue scheduling

2018-06-04 13:52:01

Can somebody please explain how to draw the gantt chart for the following using multilevel feedback queue scheduling

Consider a multilevel feedback queue scheduling with three queues, numbered as Q1,Q2,Q3. The scheduler first executes processes in Q1, which is given a time quantum of 10 milli-seconds. If a process does not finish within this time, it is moved to the tail of the Q2.The scheduler executes processes in Q2 only when Q1 is empty. The process at the head of the Q2 is given a quantum of 16 milli-seconds.If it does not complete, it is preempted and is put into Q3. Processes in Q3 are run on an FCFS basis, only when Q1 and Q2 are empty.

Processes Arrival time     Burst time
 

P1           0              17

P2          12              25

P3          28              8 

P4          36              32 

P5          46              18

First of all, let's fix a quantum time = 10 ms as we need to implement Multilevel Feedback Queue Scheduling algorithm.

Processes will be kept in the ready queue! So, queue will contain P1,P2,P3,P4,P5 in queue as per time,but,feedback will be keep on sending to a lower queue if a process crosses the quantum time and hence, will be placed in the lower queue,if left with incomplete execution!

As given below, last times are inclusive to the interval and starting times are exclusive,but the time-interval in between has to be considered :-

   1--->10 ms-------P1
   10-->17 ms-------P1     // P1 finished execution..........
   17-->20 ms-------P2   
   20-->30 ms-------P2     // P2 sent to 1st lower queue as it's still incomplete
   30-->38 ms-------P3     // P3 finished execution..........
   38-->40 ms-------P4
   40-->50 ms-------P4     // pushed next to P2 in 1st lower queue
   50-->60 ms-------P5     // pushed next to P4 in 1st lower queue

Now,1st lower queue comes in action with time-quantum of 16 ms.

   60-->82 ms-------P2     // P2 finished execution.........
   82-->98 ms-------P4     // P4 sent in 2nd lower queue as it's still incomplete
   99->107 ms-------P5     // P5 finished execution..........

Now,2nd lower queue comes in action with FCFS algorithm implementation.

 107-->111 ms-------P4     // Finally, P4 finished execution..........

Hence, this would be the Gantt chart diagram for time-quantum = 10 ms.

If you're left over with any doubt,please leave a comment below!

A process that arrives for queue 1 preempts a process in queue 2.(Operating System Concepts Book, International Student Version, 9th Edition, page 216)

So, I think P2 preempts P1 at 12th second and the suggestion above is not correct.

链接地址: http://www.djcxy.com/p/14856.html

上一篇: 防止任务被安排

下一篇: 多级反馈队列调度