1.1 xv6 scheduler - KeonYeong/LKY GitHub Wiki

Default :

Default scheduling method will be MLFQ scheduling. However if SYS_CALL (CPU_Share) occurs, the method will automatically switched to stride scheduling method.

Basic Queue Rule (in MLFQ):

  1. If a new process starts, it is located on Q0 (the highest level queue) and allotted t time of CPU occupation.
  2. Regardless of which queue, if any process still has task to keep on even after it used entire given time, it is demoted to the lower level queue.
  3. Regardless of which queue, if any process gives up allotted time due to any event wait or I/O wait, it promotes to higher level queue so that make sure it remains on high level queue.
  • If process is already on the highest level queue, it’s just put behind the queue.
  1. Q0, Q1, Q2 queues afford its belonging processes t, 2t, 4t time of CPU occupation each.

+ The initial t value will be 10 ms(=1 tick).

Execution Rule (in MLFQ):

  1. Processes are executed in the order of assigned queue’s level which means processes in the highest level queue (Q0) will be held to CPU.
  • If there are two or more processes in the same level of queue, processes will be executed following the method of Round Robin.
  1. If all of processes in the higher level queue are blocked because of task complete or occurrence of event / I/O wait, the processes in the lower (next) level queue will be executed next.
  2. If the process in the higher level queue, which had been blocked due to I/O etc., became ‘ready’ state, ongoing process (if it’s lower) will be halted and CPU will be occupied by process coming.
  3. If the process completes its task, it leaves the MLFQ system.

Exception (in MLFQ):

Starvation: There will be certain time period set so that after certain time scheduler will boost all processes’ level to the highest level in order to prevent starvation. At first, It will be designed it as 100t.

SYS_CALL Event:

If SYS_CALL (CPU_Share) occurs, scheduler will be run in stride scheduling method:

  1. There will be Pass Value Table, Strides of each process, a large number (constant) contained. (Large number will be initially 1000)
  2. Portion of CPU will be passed by arguments or in process itself (proc.c).
  • Stride will be calculated by: 1000 / portion
  1. The smallest pass value process will have priority to run.
  2. After process runs requiring time, its pass value will be increased by its stride.

+ MLFQ also has the share of CPU, it will contain rest of the CPU share after all processes are allocated in certain amount of shares. At this point, sum of share amounts (except MLFQ) will not exceed 80%. This will ensure that at least 20% of CPU time will follow MLFQ method. Moreover, if no processes are to run in stride scheduling, the scheduling method will also be switched into MLFQ method.

Return