You will take this exam on BrightSpace. There will be multiple choice, multi-select, matching, free response, and programming problems with a 120 minute time limit. You MAY use books, notes, and web searches to look things up. You will not be spied on: there is no browser lock down and hence no need to hide a mobile device in a bag of potato chips. However, you MAY NOT solicit answers in any way. There is to be no asking for help, no posting on forums, no communication with other humans or intelligent bots in any way; you can only “look things up.” No chatbots are permitted! You also MAY NOT post answers or help any other test taker either. You are bound by an honor code to follow these rules.
The exam will be online but must be taken in any two hour period on June 26–30, 2025, America/Los Angeles time.
You should:
Review the course notes if you can, but to help you a little, here’s an outline of the topics we covered:
PRELIMINARIES
Programming Languages
Values
Numbers
Symbols
Characters
Tuples
Sequences
Strings
Records
Sets
Dictionaries
References
Statics
Literals
Variables
Declarations
Expressions
Statements
Functions
Generators
Classes
Modules
Dynamics
Control Flow
Concurrency
Control Flow
Sequential
Conditional
Iterative
Loops
Each-Functions
Iterator Objects
Recursion
Nondeterministic
Disruptive
Goto
Exceptions
Panics
Loop Disruption: break, continue, redo, retry
return and yield
INTRODUCTION AND OVERVIEW OF CONCURRENCY
Real-world examples
Why Study
Challenges
Safety
Race Conditions
Critical Regions
Deadlock
Livelock
Starvation
Reliability
Liveness
Weak Fairness
Strong Fairness
Linear Waiting
FIFO
Important Definitions
Program, Process, Thread
Multiprocessing, Multithreading
Concurrency, Distribution, Parallelism
Shared Resources vs Message Passing
Synchronization
Barrier
Resource (Mutual Exclusion)
Condition
Architecture
Distributed (message passing, share nothing)
Shared Memory (locks required)
Event Queue (probably single-threaded)
Models
1. Shared Memory
2. Message Passing
3. Coroutines
4. Asynchronous Programming
5. Parallelism
Topics
Granularity: at least four grains
Scheduling: thread states
Communication: shared memory vs. message passing
Synchronization
Barriers
Latches
Condition Variables
Exchangers
Mutual Exclusion
Locks
Semaphores
Monitors
Rendezvous
Atomics
Software Transactional Memory
Nonblocking
Real-Time
Language intrinsic vs. Library concurrency support
INITIAL PROGRAMMING EXAMPLES IN 8 LANGUAGES
Ada, Java, Perl, Rust, C++ C (with pthreads), Go, Erlang
Thread declarations
Thread creation
Thread startup and shutdown
Joining, which languages need it and which don't
Very basic locking
The three examples
(Example 1) 0, 1, 2
(Example 2) Parallel Array Sum
(Example 3) Dining Philosophers
Why we care about this classic (see course notes for big list!)
Variations on the implementation
The Enhanced Dining Philosophers Problem
LANGUAGE-SPECIFIC DEEP DIVES
Java
The thread class (what it gives you and what it doesn't)
Runnables and Callables
Thread objects
Thread states
Creating threads (don't use the constructors)
Starting threads
Stopping (remember the thread itself should permit this)
Uncaught exceptions
Synchronization (at least seven approaches)
Atomic Objects
Volatile Fields
Synchronized Statement
Explicit Locks (reentrant simple locks, read/write locks)
Explicit vs. Implicit Locking
Condition Synchronization
Wait/notify vs. Condition interface
Sync objects
countdowns - to wait for n things to happen
barriers - to wait for n threads to arrive at some point
semaphores - to allow n threads to use a resource at a time
exchangers - to allow two threads to exchange data
phasers - to allow multiple threads to synchronize at a point
Interrupts
Suspension (should be on the suspendee's terms only)
The massive collection API
Which collections are threadsafe and which aren't
Copy on write stuff
Iterators and concurrent modification exceptions
Thread Pools
The Executor interface and friends
The Executors utility class
How the bouncing balls example works
Scheduling tasks with the ScheduledExecutorService and Timers
Ada
Tasks vs. Protected objects
Tasks are not top-level entities
Lifecycle
Activation
Termination
Communication
Rendezvous
Conditional Entry Call
Timed Entry Call
Selective Wait
Requeue
Abort
ATC
Synchronized queues
Task States
Task Attributes
Go
Goroutines
Creation
Shared memory and channels
Buffered vs. Unbuffered channels
Synchronization
Communication
Channels
Select statement
Wait groups
Mutexes (sync.Mutex)
Atomics (sync.atomic)
SHARED MEMORY AND MUTUAL EXCLUSION
Why? To avoid races on shared resources
Requirements
Two main approaches
Bare machine approaches
Why non-atomic test and set fails
Why atomic test and set works
Peterson's algorithm
(Bakery algorithm would go here, but we didn't cover it)
Scheduler-Assisted Approaches
Barriers
Semaphores
Smart data objects that protect themselves
Notification Mechanisms
Ada protected objects
Explicit Locking
Avoiding the need for mutual exclusion
Serialize all access on a single thread (events or coroutines)
Protect it with a critical region
COROUTINE CONCURRENCY
Explicit vs Implicit yield and resume
Cooperative vs. Preemptive
Lua
Kotlin
ASYNCHRONOUS AND EVENT-DRIVEN PROGRAMMING
Asynchronous vs. Synchronous
Paradigms
Fire and forget
Callbacks
Promises and Futures
Async/Await
Event-driven programming
Event emitters
Event listeners
DISTRIBUTED PROGRAMMING
Terms, definitions, areas of study
List of paradigms
Enterprise vs. Grid computing
Message Passing
Naming
Symmetric vs. Asymmetric
Name the other party vs. Name the channel
Communication: synchronous vs. asynchronous
Kinds of calls
Asynchronous calls
Blocking calls (wait forever)
Timeout calls (back off after a time)
Conditional calls (don't jump in if not ready)
Client-Server communication styles
Rendezvous
Callbacks
Receipt
Mailbox
Relay
Buffer
Networks and Internets
The basics
Protocols and layers
Internet (TCP/IP) applications
Socket-based programming
Python sockets
Python multithreaded servers
Other languages
WWW
URI
HTTP
REST
Interchange Formats (not covered)
JSON
Protocol Buffers
Thrift
Remoting (not covered)
Classics
RPC
RMI
.NET Remoting
Hessian/Burlap
DWR
Modern
gRPC
Distributed Algorithms (not covered)
Distributed Transactions (not covered)
Languages for Distributed Programming
The big paper you read from 1989
Modern Languages
PARALLELISM
SIMD vs MIMD
Memory Models
Shared Memory
PRAMs
EREW
ERCW
CREW
CRCW
Distributed Memory
Topologies
Mesh
Hypercube
Tree
Ring
Star
Communication
Broadcast
Reduction
Parallel algorithm design
Performance measures
Speedup
Efficiency
Cost efficiency
THEORY
Process algebras
CCS
Pi-Calculus
CSP
ACP
Temporal Logic
Operators
Linear Temporal Logic (LTL) (not covered)
Computation Tree Logic (CTL) (not covered)
Relationship to other modal logics
Notations
Petri Nets (not covered)
Harel Statecharts (not covered)
UML
Activity Diagrams
Sequence Diagrams
State Diagrams
Communication Diagrams
Make sure to do the recall questions at the bottom of each of the labs.
Keep in mind that our (world’s) knowledge culture is far more literary than oral, so read, skim, or watch outside resources linked from the course notes.
You have to put in the time for effortful self-study. Although the exam is open resources, you will not have time to look everything up. Those who come in with a strong comfort level with the material will finish on time. I am assessing your fluency and your proficiency with the material, not your Google-Fu.
Here’s a breakdown of the focus for each problem (not in order):