CPU Virtualization

CS 537
CS 537: Operating Systems — CPU Virtualization

Process

What is a process

  • A running program is a process
  • Stream of executing instructions and their “context”

Thread

  • Can have multiple threads within a single process
  • Lightweight process
  • Share an address space

Why do we need processes?

  • Share CPU: Time sharing

OS Scheduler

  • Scheduler save context when process is pause
  • Restore context on resumption

Goals for CPU Virtualization

  • Policy goals
    • Virtualize CPU resource using processes
    • Reschedule process for fairness? efficiency?
  • Mechanism goals
    • Efficiency: Time sharing should not add overhead
    • Control: OS should be able to intervene when required

Mechanism

System call

  • User mode and kernel mode
    • User processes run in user mode (restricted mode)
    • OS runs in kernel mode (not restricted)
  • System call
    • Separate user mode from kernel mode for security
    • Use system call to invoke kernel mode functions
  • Procedure for calling read()
    1. Set system call table index to 6 movl $6, %eax
    2. Call trap with id 64 int $64

Dispatch mechanism

  • Dispatch loop while (1) { run process A for some time-slice stop process A and save its context load context of another process B }

  • Cooperative Multi-tasking

    • Trust process to relinquish CPU through traps
    • Provide special yield() system call
    • Processes can misbehave

  • Timer-based Multi-tasking

    • Hardware generates timer interrupt (CPU or separate chip)
    • User must not be able to mask timer interrupt

Policy

Vocabulary

  • Workload: set of jobs (arrival time, run_time)
  • Job ~ Current execution of a process
  • Scheduler: Decides which ready job to run
  • Metric: measurement of scheduling quality
  • Turnaround time = completion time - arrival time
  • Response time = first run time - arrival time

FIFO (First In, First Out)

  • Disadvantage: Turnaround time suffers when short jobs must wait for long jobs (Convoy Effect)

SJF (Shortest job first)

  • Disadvantage: Only schedule new job when previous job voluntarily relinquishes CPU

STCF (Shortest Time-to-Completion First)

  • Preemptive: Schedule different job by taking CPU away from running job
  • Always run job that will complete the quickest

Round Robin

  • Goal: reduce response time
  • Trade-off: increase turnaround time

I/O Aware Scheduling

  • Goal: process won’t hold CPU when doing IO

Multilevel Feedback Queue

  • Motivation: Run-time of each job is not known

  • Approach

    • Multiple levels of round-robin
    • Each level has higher priority than lower level
    • Can preempt them

  • Rules

    1. If priority(A) > Priority(B), A runs
    2. If priority(A) == Priority(B), A & B run in RR
    3. Processes start at top priority
    4. If job uses whole slice, demote process (longer time slices at lower priorities)

  • Avoid starvation

    • Problem: Low priority job may never get scheduled
    • Solution: Periodically boost priority of all jobs (or all jobs thathaven’t been scheduled)