Unit 5: Scheduling and Synchronization
High-level Performance Concepts/Lessons
Context Switch: The operating
system switches execution to a different thread.
Responsiveness/Throughput:
Both
motivations for multiple threads, even on a uniprocessor.
Threadpools: A set pool of threads executes
tasks.
Work-Stealing:
When
threadpool threads finish work on their local task
queue, they can “steal” tasks from the queues of other threads.
High-level Correctness Concepts/Lessons
Interleaving execution model
·
Operations
in each thread happen in program order
·
Operations
in different threads are interleaved arbitrarily
·
Data-Race
Freedom allows programmers to use this model on a multiprocessor system
State machines
·
States
encapsulate the values of program variables
·
Transitions
occur on each program instruction
Temporal Safety
·
Program does
not end up in “bad” states
·
Violation
is exhibited by a finite execution
Liveness
·
Program transitions
maintain “good” pattern
·
Violation
can only be exhibited by an infinite execution
Deadlocks
·
Program
does not make progress because threads are blocked waiting for resources held
by other blocked threads.
Livelocks
·
Program does not make progress, even
though threads keep executing.
Code-level Concepts/Lessons
·
Thread.Start: Starts a new thread executing.
·
Thread.Join: Blocks until the
specified thread finishes executing.
·
Interlocked operations: Atomically
increment, decrement, or compare-and-swap values.
·
Thread.Yield: Try and switch execution to another thread.
·
Volatile: Tells
compiler multiple threads may access a variable; prevents optimizations that
could lead to funny behaviour.
·
Synchronization primitives: These allow threads to coordinate with each other.
·
.NET 4.0 Schedulers: Uses
a work-stealing queue implementation with provably good locality and work
distribution properties.
Sample Learning Outcomes
·
Use
synchronization primitives to implement a task scheduling system.
·
Explain
tradeoffs between using threads and tasks.
Assignment Ideas
·
Rewrite some examples from the ParallelExtensions
samples (such as ParallelGrep) using only threads.
·
Code up full implementations for high level
synchronization primitives (e.g. ReaderWriterLock)
using lower level primitives (such as pulses, Interlocked
operations, etc.)
·
Write a simple implementation of a work-stealing
queue.
Resources
Parallel Extensions Samples & Extras (http://code.msdn.microsoft.com/ParExtSamples):
·
ParallelGrep
·
DiningPhilosophers
·
ParallelExtensionsExtras.TaskSchedulers
·
ParallelExtensionsExtras .Extensions.
·
TaskFactoryExtensions
·
TaskSchedulerExtensions
Parallel Programming with Microsoft .NET
book (http://parallelpatterns.codeplex.com):
·
Chapter 3 (Parallel Tasks)
·
Especially Task Scheduling subsection