[xv6-kernel] Lab 2 ; Scheduling implementation

Lab2

• Add a priority value to each process
  • proc.h의 struct proc에 priority 추가
  • proc.h의 HIGHPRIO, LOWPRIO 변수를 통해 priority arrange 지정
• Add a system call to change the priority of a process
  • syscall.c, syscall.h : syscall 함수 추가
  • usys.S : SYSCALL(getpriority), SYSCALL(setpriority)
  • defs.h, user.h : syscall 함수 추가
  • syscall 함수 : int getpriority(int pid); , int setpriority(int pid, int priority);
• Goal
  • Understand how the scheduler works
  • Understand how to implement a scheduling policy and characterize its impact on performance
  • Understand priority inversion and a possible solution for it

How the scheduler works

• Introduction
  • sched and scheduler are co-routines of each other
  • Find a process to run
  • Run the found process until it stops
• Scheduler holds ptable.lock for most of its actions
  • Scheduler realeases the lock once in each eateration of its outer loop (explicitly enables interrupts)
    • When CPU is idle (can find no RUNNABLE process)
      • If an idle scheduler looped with the lock continuously held no other CPU that was running a process
        1) could never perform a context switch or any process-related system call
        2) could never mark a process as RUNNABLE process
        (so as to break the idling CPU out of its scheduling loop)
  • The reason to enable interrupts periodically on an idling CPU
    • There migit me no RUNNABLE process
    • Because processes are waiting for I/O
    • If the scheduler left interrupts disabled all the time, the I/O would never arrive
• The flow in infinite loop
  • The scheduler loops over the process table looking for a runnable process, one that has p->state == RUNNABLE
  • Once it finds a process
    • It sets the per-CPU current process variable proc
    • It switches to the process's page table with switchuvm
    • It marks the process as RUNNING
    • It calls swtch to start running it

How to implement scheduling policy

• Scheduling policy

  • Round Robin
    1) It runs a job for a time slice (scheduling quantum)
    2) Switches to the next job in the run queue
    3) It repeatedly does so until the jobs are finished
    4) Time slice

    • Note that the length of a time slice must be a multiple of the timer-interrupt period
    • The shorter it is, the better performance of RR under the response-time metric
    • The Round Robin policy is excellent under only the response-time metric
    • But under a turn-around time metric, it is one of the worst policies

  • Multi-level Feedback Queue
    1) It tries to address

    • a problem for optimizing turnaround time
    • a problem for minimizing response time

    2) Basic Rule

    • 1: If priority(A) > priority(B), A runs (B doesn't)
    • 2: If priority(A) = priority(B), A&B run in RR
    • 3: When a job enters the system, it is placed at the highest priority (the topmost queue)
    • 4a: If a job uses up an entire time slice while running, its priority is reduced
    • 4b: If a job gives up the CPU before time slice is up, it stays at the same priority level

  Diary

  For an implementation of scheduler considering each process's priority, it is not easy to edit scheduler function. Before editing scheduler, I added system call for getpriority and setpriority. After fully testing execution of two system calls, I started to check flow of scheduler and discussed about what scheduling policy is applied, When Round Robin is applied, what is the additional variable for RR.

  I had a difficulty to devise a scheduling policy and update newly scheduler. Thus, in evening, I reviewed the flow of scheduler and existing scheduling policy. When I think Round Robin, it is very difficult that how the concept of time slice is applied in scheduling. Through evening study, I figured out the meaning of time slice and exactly and how time slice works in multi-level feedback queue and Round Robin. Based on this, tomorrow I would discuss how a concept of time slice can be applied in our scheduler of xv6.