Instructor: Doug Lea
Class: T-Th 9:35
Office/Lab hours. Normally every day 11-12
Prereqs: CSC241 (365 strongly encouraged) and CSC322 (or 222)
The design, implementation, and analysis of concurrent algorithms,
protocols, data structures, software components, and systems, on
computer architectures supporting parallelism and synchronization.
- Architectural support: Processor-level, multicore, and
cluster parallelism, shared memory and message passing;
associated programming constructs.
- Atomicity: Synchronization, locks, atomic operations, transactions.
- Asynchrony: Threads, processes, tasks.
- Coordination: Monitors, barriers, futures, messaging, scheduling.
- Data structures: Shared data stores and queues.
- Algorithmic strategies: Actors, parallel divide and conquer,
completions and streams.
- Analysis: safety, liveness, invariants, graph-based performance
models, empirical evaluation.
Upon completion of this course, students will demonstrate ability to:
- [Design] Choose among relevant design strategies to approach
problems; construct and use components that apply atomicity,
asynchrony, and coordination techniques for correct and efficient
- [Analysis] Determine safety, liveness, and parallel speedup
properties; recognize sequential vs parallel constructions;
empirically evaluate multiple solutions to a given problem.
- [Development] Incorporate covered techniques in concurrent and
The course does not follow these books in sequence, but they provide
additional background and coverage that will be assigned as needed.
Other recommended online readings include:
- Herlihy, Maurice and Nir Shavit, The Art of Multiprocessor
Programming, Morgan Kaufmann 2008. ISBN-13: 978-0123705914.
book companion site.
- Goetz, Brian, et al. Java Concurrency in Practice.,
Addison-Wesley 2006. ISBN-13: 978-0321349606.
See also Book supplement site.
Subject to minor change:
- Two exams (one during final exam week) (35%)
- Exam questions cover the design and theory of operation of
concurrent components and algorithms, as well as analysis in
terms of safety, liveness, efficiency, and appropriateness for
a given problem.
- 3-4 programming assignments (if 3, the third has multiple parts) (65%)
- Projects entail specialized versions of covered techniques
and components in support of concurrent applications. At least
one project entails systematic performance evaluation, and at
least one requires modeling a concurrent system. Programs may
not be submitted unless they successfully run according to
specification. You must demo your program to me within 2 days
of submitting it. Five percent credit is taken off per day
- Assignment 1
- Assignment 2
- Assignment 3
CS and College course policies and resources.
If you have a disabling condition, which may interfere with your
ability to successfully complete this course, please contact the
Office of Disability Services.
SUNY Oswego is committed to Intellectual Integrity. Any form of
intellectual dishonesty is a serious concern and therefore prohibited.
The full policy can be found at http://www.oswego.edu/integrity
Here are the targeted topics for lectures, not including classes for
review, exams, or coverage of project-specific applications. Topics
don't always fit exactly into class times, so these don't always
exactly correspond to dates.
- Overview and terminology: safety, liveness, latency, throughput.
- Creating and running activities: Threads, Executors
- Shared Memory consistency: atomicity, happens-before
- Avoiding Data races: isolation, safe publication, ordered access modes
- Consensus: CompareAndSet, etc; ABA problems
- Locks: before/after idioms, deadlock; reentrance
- Count-based synchronization: semaphores, latches, barriers, phasers
- Condition Variables and their application
- Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
- Concurrent data stores and collections; scalable counters
- Optimistic locks and transactions
- Performance measurement; read-mostly designs