CSC375

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)

Overview

The design, implementation, and analysis of concurrent algorithms, protocols, data structures, software components, and systems, on computer architectures supporting parallelism and synchronization.

Topics

Outcomes

Upon completion of this course, students will demonstrate ability to:

Readings

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:

Requirements

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 late.
  1. Assignment 1
  2. Assignment 2
  3. Assignment 3

Campus references

See the 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

Lectures

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.
  1. Overview and terminology: safety, liveness, latency, throughput.
  2. Creating and running activities: Threads, Executors
  3. Shared Memory consistency: atomicity, happens-before
  4. Avoiding Data races: isolation, safe publication, ordered access modes
  5. Consensus: CompareAndSet, etc; ABA problems
  6. Locks: before/after idioms, deadlock; reentrance
  7. Count-based synchronization: semaphores, latches, barriers, phasers
  8. Condition Variables and their application
  9. Non-blocking stacks and queues; wait/lock/obstruction freedom; linearizability
  10. Concurrent data stores and collections; scalable counters
  11. Optimistic locks and transactions
  12. Performance measurement; read-mostly designs
  13. [mid-term]
Doug Lea