CPU Virtualization

  1. Mechanisms: How
  2. Policies: Scheduling

How to “Time-Share”

  1. Problem: What if process $P$ wants to do something restricted?

    • See prev Note

  2. Problem: Process may run for a long time

    • Q: How does OS regain control of CPU?
    • A: timer interrupt
      • @Boot:
        • set this up
        • interrupt the CPU every X milliseconds
          • Why not shorter?
          • A: Context switch overhead, Cache miss
      • OS responsibility
        • for each process: track current state
          • Running
          • Ready (Not running, but could be)

  3. Problem: What if Process does something “Slow”?

    • Desire: switch to other process when IO
    • Mark $P_a$ as Blocked -> Switch to $P_b$ -> I/O completes -> Mark $P_a$ as Ready

Scheduler

Scheduler Policy: How?

  • Assumptions about “workload”
    1. start: all jobs arrive at once
    2. just use CPU (no I/O)
    3. fixed length (runs for time $T$)
    4. length is known ahead of time
    5. metric: turnaround time $T = T_{completes} - T_{arrives}$
  • Algorithm #1: Fist In First Out, First Come First Serve
    • $T_A = 10, T_B = 10, T_C = 10$
      • $T_{avg} = 20$
    • Relax Assumption #3 ($T_A = 10, T_B = 100, T_C = 10$)
      • $T_{avg} = 80$
  • Algorithm #2: SJF (shortest job first)
    • $T_A = 10, T_B = 100, C = T_10$
      • $T_{avg} = 50$
    • Relax Assumption #1 (All jobs don’t arrive at once)
  • Algorithm #3: STCF (Shortest time to completion first)