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