Liam's UF Notes

Search

SearchSearch

The Scheduler

  • The part of the OS that schedules when to run Processes
  • Decides which project gets to run (and when)
    • Not necessarily FIFO
  • Is ready to respond after interrupts
    • It has to know where to stop, where to restart

Implementation

  • Quanta
    • The unit of time that a process is allowed to run before moving onto the next process (typically fractions of a second)
    • Can still be interrupted by a Hardware Interrupts
  • Cycle
    1. Scheduler triggered → OS enters kernel mode
    2. Suspends the execution of the current process and saves its state into memory
    3. Loads the CPU registers with the states of the next process to execute and runs the new process
    4. The OS switches back to user mode
    5. The scheduler sets an alarm (with the length of a quanta) for the next switch
  • When does the context switch
    • Blocking Operations (Voluntary)
      • I/O
    • CPU Yielding Operations (Voluntary)
      • Gives up the rest of the time
    • CPU Sharing (Involuntary)
      • Quanta time expired
    • Asynchronous Events (Involuntary)

Algorithms

Non-Preemptive

  • First-Come First-Serve
    • Jobs run in order of arrival
    • Simple but does not give the best results
  • Shortest Job First
    • Job that will finish first will run first
  • Priority
    • Job with highest priority is executed first
    • Can use information about the tasks to set the priority and optimize over time
  • Optimal (Crystal Ball)
    • Uses future knowledge of arrivals for optimization
    • Theoretical (base for comparison)

Preemptive

  • Shortest Remaining Time First
    • Ready job that will finish first runs first
    • Would be optimal if there is no context switch cost
  • Round Robin
    • Has processes in a circular queue
      • finishing running (and wanting to still run) or creation adds to the back of the queue
    • Each process runs for some quanta of time
    • Notated RR(quanta)
    • It’s performance is connected to the process size and the size of the quanta
    • Size of quanta is a balance
      • Too short: Spends more time context switching (copying memory and stuff) than actually running the processes
      • Too long: OS feels less interactive
  • Preemptive Priority
    • Ready job with highest priority is run first
    • Uses multiple queues
    • Exists in combinations with other strategies (such as round robin)
    • Run all tasks in the queue with highest priority until they are done, and then move to the lower priority
    • Problem: really low priority tasks never get to run (starve)
      • Sometimes it’s okay if they just eventually run (fasting)
      • Or some systems increase the priority of tasks that waited for a while
  • Compatible Time-Sharing System
    • Attempts to approximate SRTF
    • Uses growing allocations and multiple priority queues
    • Each time a process quanta ends, it adds two of itself to a lower priority queue

Proportionate

  • Guaranteed
    • If we have processes, then we shouldn’t ever allow any process to exceed of the total runtime
  • Lottery
    • Each process gets “tickets” (can get multiple tickets for higher priority)
    • Pick a ticket at random
    • More tickets = higher probability of being selected
    • Priority without starvation issues (because the ticket would eventually get chosen)
  • Fair-Share Scheduling
    • CPU time allocated per user, not process
    • Can use lottery approach (and prioritize users by number of tickets)

Real-Time

  • Static Schedule Priorities
    • Priority of tasks don’t change
    • Runs higher priority task first
    • Is preemptive
  • Dynamic Schedule Priorities
    • Prioritizes scheduling according to the system’s deadlines
    • Hard real time: missed deadline = disaster
    • Soft real time: missed deadline = annoying

Modeling

  • Coarse Approach
    • We can do a very coarse measure of probability
    • = probability that one process is idle
    • = degree of multiprogramming (# of processes)
    • = idle probability
    • = utilization
  • Models don’t work that well because there is a big difference between theoretical and actual efficiency

Components

Long-Term: Admission Scheduler

  • Goal is to maximize throughput
  • Important for batch systems when there are jobs waiting
  • Much longer quanta
  • Question: Is there room in the system for another job? (good mix of jobs in RAM, CPU, esc.)
  • Generally, not used in interactive systems because high latency
    • Might be in interactive OS for low-load, background tasks
    • ex: running a virus scan or backup overnight

Medium-Term: Memory Scheduler

  • Checks memory load, decides what remains in memory and what goes back to storage
  • Adds processes to memory or send them back to disk
  • Question: Is memory taxed?
  • Needs to work with the CPU scheduler to prevent processes from being moved back and forth too much (called thrashing)

Short-Term: CPU Scheduler

  • Decides which process gets to be executed next in the CPU
  • Runs super frequently → must execute fast
  • Depends on priority and process history

Relationship to OS Types

  • All
    • Fairness: giving each process a fair share of the CPU
    • Policy enforcement: seeing that stated policy is carried out
    • Balance: Keeping all parts of the system busy
  • Batch
    • Throughput: Maximize jobs per hour
    • Turnaround time: Minimize time between submission and termination
    • CPU utilization: Keep the CPU busy at all times
    • Can be preemptive or not
    • Relies more on the admission scheduler
  • Interactive
    • Response time: Respond to request quickly
    • Proportionality: Meets users expectations
    • Almost always preemptive
  • Real-Time
    • Meeting deadlines: Avoid losing data
    • Predictability: Avoid quality degradation

Graph View

Backlinks