Brief

  • CPU Virtualization
    • Mechanism => Limited Direct Execution
    • Policy => Scheduling
    • Q) How to build a scheduling policy?
  • Memory Virtualization

Scheduling

Metric #1: Turnaround Time (Tcompletes−Tarrives)

  • “Run to completion”
    • FIFO (FCFS)
      • Bad (Short jobs stuck behind long jobs)
    • SJF
  • Process does not all arrive at T0
    • STCF (Shortest Time to Completion First)
      • “Generalized” SJF

Metric #2: Response Time: (Tfirstruns−Tarrives)

  • Round Robin
    • ABCABC….ABC (Switch frequently)
    • Time Slice (Quantum):
      • Multiple of how often Timer goes off

“Real” Scheduler

  • Don’t know job length (How to learn?)
  • Do well on different Workload:
    • interactive
    • long-running (Batch/backgroud)
  • Jobs do I/O (don’t just use CPU)
  • Key: use history to predict future

Policy: Multi-Level Feedback Queue (MLFQ)

  • A process can be on only 1 queue
  • PriorityQueueProcessesTime slice
    HighQ2A10ms
    MediumQ1C20ms
    LowQ0E,L40ms
  • Priority: process at highest queue runs
  • When to change queues?
    • Each queue has time slice (how long job will run at that priority)
    • When time slice is used move down one level
    • Initially, jobs go to highest priority queue
    • If >1 job at some priority, use round robin
  • Working Example
    • 1 long running job; Occasionally, an “interactive” job comes
    • Long job drops to bottom queue, interactive job goes to top queue => Works
  • Problem: Starvation
    • “Too many” short jobs arrive + run, long-running jobs may never get service
    • Solution: Periodically reset jobs to top
  • What about I/O?
    • Approach #1
      • If do I/O, stay at same queue and reset time counter
      • Problem: “gaming” the scheduler (retaining high priority artificially)
    • Approach #2
      • Do not reset time counter

Memory Virtualization

  • Shared by all running programs
    • Want: Efficiently, Protection
  • Virtual address -> Physical Address “Address Translation”
    • This happens on every memory access
    • e.g. load addr(virtual), R1
      • 2 translations
      • Program Counter: virtual address then load another virtual address
    • MMU: hardware on CPU (per CPU) (Memory Management Unit)

Simplest Form of MMU

  • Base & Bounds
  • 2 Registers in MMU (base & bounds)
    • Base for translation
      • Where is first byte of addr in the physical memory
    • Bounds for protection
  • On every memory access:
    • Virt addr -> MMU base + virt addr => phys.addr