Midterm 2 Cheatsheet: Concurrency

Content locked

The catalog is public. Reading this content requires approved access.

Sign in to read

Midterm 2 Cheatsheet: Concurrency

Why Concurrency? (Lecture 11)

Threads (Ch. 26)

Shared vs Per-Thread

Thread Context Switch

APIs

User-Level vs Kernel-Level Threads

Key Gotchas

Locks (Ch. 28)

Goals

Lock Types

Hardware Primitives — Detailed Breakdown

TestAndSet (XCHG / xchg)

CompareAndSwap (CMPXCHG / cmpxchg)

Lock-Free Add with CAS

FetchAndAdd (XADD / xadd)

LoadLinked / StoreConditional (LL/SC — RISC)

Comparison Table

Queue-Based Lock (park/unpark)

Key Gotchas

Load+Store Lock (BROKEN — from lecture)

Ticket Lock (from lecture)

Inverted Flag Values Trick (from exam)

Condition Variables (Ch. 30)

API

Four Rules (from Lecture 13)

The cond_wait Contract

signal vs broadcast

Common CV Mistakes

Key Properties

thread_join / thread_exit — Building Up (Lecture 13)

Producer-Consumer with CVs (Lecture 13)

Key Gotchas

Locked Data Structures (Ch. 29)

Concurrent Counter (Approximate/Sloppy)

Concurrent Queue (Two-Lock)

Hash Table

Key Gotchas

Concurrency Bugs (Ch. 32)

Deadlock: 4 Coffman Conditions (ALL must hold)

Deadlock vs Starvation vs Livelock (Lecture 14)

Prevention Strategies (Lecture 14)

Practice: Which Can Deadlock? (Lecture 14)

Key Gotchas

Reader-Writer Locks

Data Races & Race Detection (Lecture 15)

Data Race Definition

ThreadSanitizer

Happens-Before Relation

False Positives / False Negatives

Linearizability

Real-World Bug Examples (Lecture 13)

Atomicity Bug (MySQL)

Ordering Bug (Mozilla)

Assembly Race Condition Tracing (Lecture 11)

Thread Join/Exit Schedule Tracing

Producer-Consumer Schedule Tracing

Easily Confused Concepts

volatile vs Locks vs Atomic Instructions

yield() vs park() vs Blocking Lock

Locks Do NOT Prevent Context Switches

fork() vs pthread_create()

Process State (PCB) vs Thread State (TCB)

Coarse-Grained vs Fine-Grained Locking

Data Race vs Race Condition

Quick Reference: Exam Traps