Metrics

• performance metric: turnaround time = completion time - arrival time
  • completion time: when the job finishes
  • arrival time: when the job arrives at the system
  • calculate the avg for all jobs
• fairness metric: Jain’s index
• interactivity: response time = first run time - arrival time
  • first run time: when the job is first scheduled to run
  • due to time sharing kernel, this metric avoids that users enter a command and wait for the process for eternity

Policies

Optimized for performance

• First come first serve
  • convoy effect: heavy jobs get queued before light jobs ⇒ increase completion time!
• Shortest job first
  • this is optimal scheduling algorithm if we know all jobs beforehand
    • modified version if need online scheduling: shortest time-to-complete first
      • whenever a new job arrives, interrupt the current running job and replace with one that is estimated to complete first

Optimized for interactivity

• Round robin: run a job for a time slice and moves to the next one
  • time slice should not be too long to ensure interactivity and not too short to amortize the context switching cost!
  • quite fair: dividing CPU time among active jobs with a period…
  • RR is one of the worst algorithms if measured by turnaround time
    • in general, there is a trade-off for fairness vs performance

Balance between the 2

• Multi-level Feedback Queue
  • MLFQ contains multiple distinct queues, each with different priority level

    • 2 scheduling rules:

      1. if priority(A) > priority(B) then A runs
      2. if priority(A) = priority(B) then A and B runs in RR

    • how to set priority?

      • intuition: If a job yields and waits for user input a lot → interactive process, needs to prioritize. If a job just wants CPU time, then it might be a long running process and has lower priority
      1. when a job arrives, put it in the highest priority
      2. if a job uses up its allotment while running, its priority is reduced
         • allotment = the amount of time a job can spend at a priority level before being demoted
         • this rule helps guard against several adverse cases:
           • …
         • we can let each priority level has a different allotment…
      3. after certain time period S, move all existing jobs in the system to the highest priority

    • this avoids long-running jobs (therefore have lowest priority) being starved by bursts of short jobs

    • tuning MLFQ:

      • how many queues? what value of S should be? time slices for each queue?
        • open-ended questions…

    • In today practice:

      • modern OS kernels are not using MLFQ much anymore because:
        • failed (or perhaps unable?) to incorporate other attributes of a job, for example:
          • caching behavior

      Real systems these days don't use MLFQ because:

      1. Cache is everything. Moving between queues trashes locality
      2. Modern CPUs have 128+ cores. Your "queue" becomes a lock bottleneck
      3. NUMA exists. Running on the wrong socket costs more than unfairness
      4. Power management matters. Sometimes NOT scheduling is correct

      The scheduler's real job isn't "fairness"; it's keeping caches warm and cores fed. CFS does this by being simple enough to run fast and getting out of the way.

Proportional scheduling

ticket = proportion of a resource that a process should receive

Approaches

• lottery scheduling (random appraoch)
  • example: imagine the CPU time is comprised of 100 tickets, process A holds 75 tickets from 1 to 75, and process B holds the remaining 25. For each time slice, get a random number. Whichever process holds the lucky number is scheduled to run.
  • Why randomness? 3 pros:
    1. avoid strange corner cases easily
    2. lightweight, avoid complicated process accounting…
    3. fast: generating random number is quite fast compared to doing stuffs
• Stride scheduling
  • each job has a stride = (total #tickets / #tickets the job has) and a counter initially set to 0
    • every time the job runs, counter += stride
    • the counter is called the pass value of the job
  • at each time slice, pick the job with lowest pass value (pick any process if they are equal)
  • this is a deterministic approach that is guarantees the CPU time proportion each job gets!
  • what if there is a new job coming in?
    • set its pass value to 0 → CPU will be monopolized by the new job!
      • lottery scheduling doesn’t have global state, no need for accounting.. (point 2!)
• Linux CFS:
  • extends stride scheduling in several ways…
    • involved physical time in scheduling…
  • keeps track of each process vruntime, at each scheduling step, pick the process with lowest vruntime to run
  • sched_latency = target period during which all runnable jobs are run at least once
    • If there are multiple CPUs in the system, the latency target becomes kernel.sched_latency_ns * (1+log2(the number of CPUs))
  • min granularity = minimum time slice
  • weight controlled by setting niceness of a process (less nice = higher priority)
    • there is a const array mapping between niceness (-20 to +19) to weight value
    • default niceness is 0
  • time slice for process k = max((weight of k) / (total weight) * sched_latency, min_granularity)
  • vruntime of k += weight k / (weight of niceness 0) * (actual elapsed time)
  • when a new process is created or after a process is woke up from waiting for IO, set its vruntime = min vruntime of all jobs ⇒ avoid monopolizing CPU time
    • however if a process sleeps (for short periods) frequently don’t get (really) fair share

multi-cpu scheduling