Recap

CS3211 Parallel and Concurrent Programming

Concurrency – a definition
• Two or more separate activities happening at the same time
• Everywhere around us
• Eating and watching the lecture
• Listening and watching
• For computers, concurrency refers to a a single system performing
multiple independent activities in parallel, rather than sequentially
• Multitasking in OS

CS3211 Recap 2
Concurrency vs. Parallelism
Concurrency Parallelism
• Two or more tasks can start, run, • Two or more tasks can run
and complete in overlapping (execute) simultaneously, at the
time periods exact same time
• They might not be running • Tasks do not only make progress,
(executing on CPU) at the same but they also actually execute
instant simultaneously
• Two or more execution flows
make progress at the same time
by interleaving their executions
or by executing instructions (on
CPU) at exactly the same time
CS3211 Recap 3
Concurrency
vs. Parallelism

CS3211 Recap 4
Hardware enables parallelism
• Computers are genuinely able to run more than one task in parallel
• Multicore processors are used everywhere
• Multiple processors used everywhere
• High performance computing
• Hardware threads dictate the amount of TRUE concurrency
(parallelism)
• Processors have multiple cores
• A core can support multiple hardware threads (SMT)

CS3211 Recap 5
Benefits of concurrency
• Separation of concerns
• Performance
• Take advantage of the hardware
• Optimization strategy

CS3211 Recap 6
Disadvantages of concurrency
• Concurrency problems
• Data race, other race conditions, deadlock, livelock, starvation
• Maintenance difficulties
• Complicated code
• Debugging is challenging
• Threading overhead
• Stack
• Context switching
• Memory contention

CS3211 Recap 7
Concurrency paradigms
• Thread programming using shared memory – C++
• Threads
• Atomic (weapons)
• Message passing programming – Go
• Goroutines and channels
• Patterns
• Asynchronous programming – Rust
• Ownership and borrowing
• Futures and non-blocking I/O

CS3211 Recap 8
Why C++?
• Many existing codebases are written in C++
• Fine control at the lowest levels, while supporting high-level patterns
• A "classic" language everyone should learn!

CS3211 Recap 9
C++11 multithreading
• Write portable multithreaded code with guaranteed behavior
• Multithreading without relying on platform-specific extensions
• Thread-aware memory model
• Includes classes for managing threads, protecting shared data,
synchronization between threads, low-level atomic operations
• Use of concurrency to improve application performance
• Take advantage of the increased computing power
• Low abstraction penalty - C++ classes wrap low-level facilities
• Low-level facilities: atomic operations library

CS3211 Recap 10
Testing and debugging concurrent code is hard
• Any type of bug is possible in concurrent code
• Synchronization issues: deadlocks, livelocks, starvation
• Memory-related issues: undefined behavior, UAF
• Focus on concurrency-related bugs
• Unwanted blocking – easier to discover
• Use formal specification and model checking
• Data races – sometimes difficult to discover
• Use sanitizers
• Model checking
• Write a model and (automatically) prove that the model is correct

CS3211 Recap 11
Concurrency paradigms
• Thread programming using shared memory – C++
• Threads
• Atomic (weapons)
• Message passing programming – Go
• Goroutines and channels
• Patterns
• Asynchronous programming – Rust
• Ownership and borrowing
• Futures and non-blocking I/O

CS3211 Recap 12
Why Go?
• Programming language announced at Google in 2009

• (Partially) syntactically similar to C, but with

• Memory safety
• Garbage collection
• CSP-style concurrency

CS3211 Recap 13
Concurrency + Communication
• Go model – based on Communicating Sequential Processes (CSP)*
• Concurrency: structure a program by breaking it into pieces that can be
executed independently
• Communication: coordinate the independent executions
*C. A. R. Hoare: Communicating Sequential Processes (CACM 1978)
• Ideas of CSP
• Refined to process calculus
• Can be used to reason about program correctness

CS3211 Recap 14
Abstractions in Go
Concurrency Communication

• Goroutines • Channels
• A function running independently • Goroutines can write to and read
• Spin up (start) a goroutine using from a channel
go function_name channel<-
• Run on OS threads <-channel
• select statements

• Tasks • Dependencies

CS3211 Recap 15
Patterns in Go
• Separation of concerns
• Data chunks (confinement)
• for-select loop
• Error handling
• Data processing (pipeline)

CS3211 Recap 16
Concurrency paradigms
• Thread programming using shared memory – C++
• Threads
• Atomic (weapons)
• Message passing programming – Go
• Goroutines and channels
• Patterns
• Asynchronous programming – Rust
• Ownership and borrowing
• Futures and non-blocking I/O

CS3211 Recap 17
Why Rust?
• Performance
• No runtime, no GC
• Same (or better!) performance compared to C/C++
• Reliability
• Strong and expressive type system
• Guaranteed memory safety and data-race-freedom in safe Rust
• Productivity
• Compiler has very friendly error messages (compared to C++…)
• Integrated official package manager and build tool

CS3211 Recap 18
Memory safety in Rust
• Statically prevents aliasing + mutation
• Ownership prevents double-free
• The owner frees
• Borrowing (lifetime checking) prevents use-after-free

• No segfaults!

Type Ownership Alias? Mutate?

T Owned Yes
&T Shared reference Yes
&mut T Mutable reference Yes
CS3211 Recap 19
Async/await: zero-cost abstraction for futures
• Async/await in Rust compiles down to an optimised state machine
• The compiled code has no additional allocations or overhead in
comparison to writing it by hand (non-assembly code )

CS3211 Recap 20
Concurrency paradigms
• Thread programming using shared memory – C++
• Threads
• Atomic (weapons)
• Message passing programming – Go
• Goroutines and channels
• Patterns
• Asynchronous programming – Rust
• Ownership and borrowing
• Futures and non-blocking I/O

CS3211 Recap 21
Concurrency is everywhere
• All the systems that we use (and program) nowadays deal with some
type of concurrency and parallel execution
• Systems around us are distributed systems
• Events happen at different times
• Different interleaving of events are possible
• The participants see the events interleaving in different ways
• Concurrent algorithms are needed to ensure consistency in replicated
information

CS3211 Recap 22
Trade-offs of concurrency
• Locks force trade-off between
• Degree of concurrency ⇒ performance
• Chance of races, deadlock ⇒ correctness
• Coarse grain locking
• low concurrency, higher chance of correctness
• E.g. single lock for the whole data structure or all shared memory
• Fine grain locking
• high concurrency, lower chance of correctness
• E.g. hand-over-hand locking
• Are there a better synchronization abstractions?

CS3211 Recap 23
From CS3211 onwards
• Our topics: from machine-level atomic operations to synchronization
primitives
• Atomic operations are used to construct higher-level synchronization
primitives in software:
• Locks, barriers
• It can be challenging to produce correct programs using these primitives
• Let’s raise the level of abstraction for synchronization even further
• Transactional memory (… or how CS3211 can help you understand and
implement higher-level synchronization constructs)

CS3211 Recap 24
Transactional memory
• Is it possible to get correct concurrent programs that are easy to write and write
efficiently?

• Declarative: programmer defines what should be done

• Execute all these independent 1000 tasks
• Imperative: programmer states how it should be done
• Spawn N worker threads. Assign work to threads by removing work from a shared task queue
• Acquire a lock, perform operations, release the lock
Reference: Stanford CS149 I Parallel Computing
CS3211 Recap 25
Transactional memory
• Transactional memory relies on memory transactions
• Inspired by database transactions
• A memory transaction is an atomic and isolated sequence of memory
accesses
• Nowadays, transactional memory is often supported at the hardware
level

CS3211 Recap 26
TM example

CS3211 Recap 27
Performance: lock vs transactional memory (HW)

CS3211 Recap 28
Properties of STM
• Thread-safe: Free of data races (only for variables in the atomic block)
• Atomicity: When the transaction succeeds (commits), all memory
writes in the transaction take effect at once.
• Isolation: No other thread/process can observe writes before a
transaction commits.
• Serializability: Transactions appear to commit in a single serial order,
and all threads observe the same order
• The semantics of transaction does not guarantee exact order
• Progress: Ensure that transactions continue to make forward
progress, either completing their work or making measurable steps
towards completion.
• No deadlock or livelock

CS3211 Recap 29
STM
• Two key implementation questions
• Conflict detection policy: how/when does the system determine that two
concurrent transactions conflict?
• Data versioning policy: How does the system manage uncommitted (new) and
previously committed (old) versions of data for concurrent transactions?

CS3211 Recap 30
Conflict detection
• Detect and handle conflicts between transactions
• Read-write conflict: transaction A reads address X, which was written to by
pending (but not yet committed) transaction B
• Write-write conflict: transactions A and B are both pending, and both write to
address X
• Track transaction’s read set and write set
• Read-set: addresses read during the transaction
• Write-set: addresses written during the transaction

CS3211 Recap 31
Pessimistic detection
• Check for conflicts (immediately) during loads or stores
• Philosophy: “I suspect conflicts might happen, so let’s always check to see if
one has occurred after each memory operation… if I’m going to have to roll
back, might as well do it now to avoid wasted work.”
• “Contention manager” decides to stall or abort transaction when a
conflict is detected
• Various policies to handle common case fast

CS3211 Recap 32
Pessimistic detection writes are given priority

+ Undo less work, turn some

aborts to stalls
- No forward progress
guarantees, more aborts in
some cases
- Fine-grained communication
(check on each load/store)
- Detection on critical path

CS3211 Recap 33
Optimistic detection
• Detect conflicts when a transaction attempts to commit
• Intuition: “Let’s hope for the best and sort out all the conflicts only when the
transaction tries to commit”
• On a conflict, give priority to committing transaction
• Other transactions may abort later on

CS3211 Recap 34
Optimistic detection
+ progress guarantees
+ bulk communication and
conflict detection
- detects conflicts late, can still
have fairness problems

CS3211 Recap 35
Data versioning
• Manage uncommitted (new) and previously committed (old) versions
of data for concurrent transactions
• Eager versioning (undo-log based)
• Lazy versioning (write-buffer based)

CS3211 Recap 36
Eager versioning

CS3211 Recap 37
Lazy versioning

CS3211 Recap 38
STM API
• Software barriers (STM API call) for TM bookkeeping
• Versioning, read/write-set tracking, commit, …
• Using locks, timestamps, data copying, …
• Requires function cloning or dynamic translation for function used
inside and outside of transaction

CS3211 Recap 39
STM Runtime Data Structures
• Transaction descriptor (per-thread)
• Used for conflict detection, commit, abort, …
• Includes the read set, write set, undo log or write buffer
• Transaction record (per data)
• Pointer-sized record guarding shared data
• Tracks transactional state of data
• Shared: accessed by multiple readers
• Using version number or shared reader lock
• Exclusive: access by one writer
• Using writer lock that points to owner
• (same way that hardware cache coherence works)

CS3211 Recap 40
Conflict detection granularity
• Object granularity
• Low overhead mapping operation
• Exposes optimization opportunities
• False conflicts (e.g. Txn 1 and Txn 2)
• Element/field granularity (word)
• Reduces false conflicts
• Improves concurrency (e.g. Txn 1 and Txn
2)
• Increased overhead (time/space)
• Cache line granularity (multiple words)
• Matches hardware TM
• Reduces storage overhead of transactional
records
• Hard for programmer & compiler to
analyze
• Mix & match per type basis
• E.g., element-level for arrays, object-level
for non-arrays

CS3211 Recap 41
How does CS3211 help?
• You have encountered and used all primitives needed to implement
STM!
• Locks, barriers
• Data management understanding
• Generation counters
• Timestamping

CS3211 Recap 42
Why study this course?
• We did a tour of different languages for concurrency
• Concurrent code should have better performance than sequential
code
• Choose the correct paradigm and language for a given situation
• Running in parallel … is a daunting task
• Industry writes concurrent code in many of the programming
languages that we covered
• Even when you do not work directly on the concurrent implementations, you
will have a better understanding of what are the challenges

CS3211 Recap 43
By the end of the module, the students should be able to*:
• explain the concurrent programming challenges.
• define and correctly use different synchronization mechanisms.
• apply concurrent programming principles in programs in different
programming languages.
• define and identify different issues in the concurrent programs.
• adapt the concurrent programming principles to new programming
languages or paradigms.

*aka learning outcomes

CS3211 Recap 44
Let’s get serious for a minute: Final exam
• Mon, 5 May, 1pm in MPSH1-B
• In-person
• Open book – hard-copy materials only
• Only the exam papers from 2022 onward are relevant
• Email me to book a consultation, as needed
• Give some available time slots
• Zoom/in-person meeting?

CS3211 Recap 45
You did well!
• We are proud of what you have learned
• Concurrency paradigms in 3 languages
• Languages change over time, principles and paradigms stay

• Almost done! You survived the fourth run of CS3211!

• Thank you for your patience and understanding

CS3211 Recap 46
Thank you!
Say Hi! If you see me…

CS3211 Recap 48