Describe in details how to implement the new scheduling policy (MLFQ) in the xv6.

"The existing scheduler in xv6 is a Round-Robin (RR) scheduler. Upon each timer interrupt (every 10 ms), the interrupt handler switches to the kernel scheduler, which then selects the next runnable process to run. This scheduler, while simple, is too primitive to do anything interesting. In this project, you will be putting a new scheduler – the revised Multi-Level Feedback Queue (rMLFQ) – into xv6. It has three queues: Qi, i = 1, 2, 3, 4 with time quantum size 10 ms for Q1, 20 ms for Q2, 40 ms for Q3, and 80ms for Q4. The detailed policy is described as follows:

ˆ- Any new process will be inserted to the end of Queue Q1

ˆ- The scheduler will always choose the front process in the highest-priority non-empty queue in the order of Q1, Q2, Q3, and Q4

ˆ- Any chosen process will be scheduled for the queue-corresponding quantum size or the remaining burst size if its remaining burst size is large enough

ˆ- If the process has nothing remaining, the process will be removed from the queue after its execution

ˆ- If the process is not done within this round, it shall be moved to the next lower-priority queue except for any process in Q4

ˆ- Q4 runs a Round-Robin with a time quantum size of 80 ms. If a process is not done within the assigned quantum size, it remains in Q4 competing for more rounds. The scheduler adopts a revised priority boosting in Q4. After three rounds, any unfinished job will be pushed to Q1."