Content
- Scheduling Overview
- Scheduling Policies
- Multiprocessor Scheduling
Scheduling Overview
- Prevent
thread starvation, BUT context switching is expensive
- Runs another program when I/O performed
- Goals
- Batch systems: Long running, no interactive users, no time constraints
CPU utilization
Throughput
- Number of programs complete per unit time
Turnaround time
- Total time to finish a program
turnaround = processing + waiting
- Interactive (general-purpose) systems: Short running, interactive suers, weak time constraints
Response time
- Time between receiving request & starting to produce output
Scheduling Policies
- Batch systems
- Policies
FIFO (non-preemptive)
- In order of arrival time
- Run thread until completion
Shortest job first (non-preemptive)
- In order of shortest running time
- Run thread until completion
- Starving long jobs
Shortest remaining time (preemptive)
- In order of shortest remaining time
- Run thread until completion OR another thread arrives
- Preemptive version of
shortest job first
- Starving long jobs
- Optimal w.r.t. avg waiting time
- Properties
- Some require estimate of processing time
- May starve long running threads
- Long response time
- Interactive systems
- Policies
Round-Robin
- Preemptive version of
FIFO
Time slice
- Upper time bound each process runs
time slice >> context switch timecs overhead = cs/(ts+cs)
- Run thread until
time slice interrupt OR thread blocks
- Effectiveness:
- Number of threads
- Size of
time slice
Long -> slow response
Short -> high overhead
- Does not require estimation of job processing time; no
starvation; enables interactivity by limiting the amount of time each thread can run
- Reduces
throughtput due to frequent context switching
Static priority
- In order of priority assigned
- Starving low prioriy threads
- Priority inversion: low priority threads holding locks that high priority threads want
Multi-level queue
- High, medium, & low PQs
- Choose from high-priority PQ first (e.g. I/O threads)
- For each queue,
round-robin scheduling
Dynamic priority (feedback)
- Priority changed based on thread behavior; CPU-bound threads have priority reduced
Feedback scheduling
- Goals
- Allocate CPU fairly
- I/O-bound threads receive higher priority
- Each thread:
- CPU usage (C)
- Current priority (Pi)
- Initial priority (P0)
- Nice value (N)
- Steps
- Scheduler chooses thread with the smallest Pi
- On timer interrupt, update CPU C of running thread
C = C + 1
- Every time slice, update Pi
Pi = Pi-1/2 + C + N
- Reset C for all threads
Time slice
- Many interrupts in between
time slice to avoid excessive context switches
- A
thread runs for a full time slice unless:
- The
thread blocks
- Some blocked
thread wakesup
- Longer
time slice improves throughput
Multiprocessor Scheduling
- Asymetric multiprocessing
- 1 processor runs all OS code, I/O processing code, etc.
- Others run user code
- Simple implementation
- Symmetric multiprocessing (SMP)
- All processors run OS & user code
- Efficient
- Difficult implementation
- Scheduling issues
- Processor affinity
- Cache issue, want to ensure
threads run on the same thread before
Hard affinity: a thread specifies which processor it wants to use
- Load balancing
- Single ready queue: easy BUT tends to bottleneck because each processor needs a spinlock for ready queue
- 1 ready queue per processor: scalable BUT task migration & load balancing tricky
- task migration -
Deadlock?
- load balancing -
Push migration: thread find less-busy processors
Pull migration: idle processor find thread on busy processors