Synchronization 4: Synthesis

Overview

This is the last lecture.

Summary of last time

• weensydb-01 can handle only one connection at a time
  • Put each connection in its own thread
• weensydb-02 has data races
  • Add a coarse-grained mutex protecting the database
• weensydb-03 has coarse-grained locking and therefore little parallelism between connections
  • Implement fine-grained synchronization: one mutex per hash bucket
• weensydb-04 is vulnerable to a (perhaps unintentional) denial-of-service attack: if a connection doesn’t supply a value in set, then that thread will block forever with the corresponding mutex locked
  • Don’t block with a mutex acquired if possible
  • Read the value before acquiring the mutex
• weensydb-05 is vulnerable to a (perhaps unintentional) denial-of-service attack: if a connection doesn’t supply a value in set, then that thread will block forever with the corresponding mutex locked
  • Don’t block with a mutex acquired if possible
  • Read the value before acquiring the mutex
  • Also applies to writing data back to the user
• weensydb-06 introduces the exch command, which swaps two values: it’s vulnerable to deadlock!
  • Don’t acquire the same mutex twice
• weensydb-07 is perfect…?

Deadlock and lock ordering

Threads and memory

Principles of synchronization

• Atomic operations
  • Modern synchronization rests on atomic operations that read and write shared state in one atomic step
  • Example: Atomic increment, decrement
• Data races
  • Concurrent unsynchronized access to the same memory is undefined behavior unless all accesses are reads
• Mutual exclusion
  • Avoid data races with mutex synchronization objects
  • A mutex protects access to shared state
  • Guard synchronization objects ensure mutual exclusion throughout a scope
  • Relationship between mutex and state is implicit (marked by code)
• Condition variables
  • Threads may need to wait for a condition to become true
  • This can cause polling, which is expensive in CPU time
  • Condition variables allow safe blocking on a condition (no lost wakeups)
  • Code must notify cv when condition changes
• Granularity
  • Coarse-grained synchronization object covers large state/broad condition
  • Fine-grained synchronization object covers small state/narrow condition

Compare-exchange

• One atomic operation to rule them all

bool compare_exchange(std::atomic<T>* value, T* expected, T desired) {
    IN ONE ATOMIC STEP:
    if (*value == *expected) {
        *value = desired;
        return true;
    } else {
        *expected = *value;
        return false;
    }
}

• Other atomic operations: exchange, fetch_or, fetch_and…

Fairness

• Who wins the race to acquire a mutex? Is it fair? Can a thread starve?
• Ticket lock

Convenience

• std::recursive_mutex
• std::shared_mutex
  • Two lock modes: lock() and lock_shared()
  • lock() provides mutual exclusion: at most one thread in any mode
  • lock_shared() provides shared exclusion: one or more threads in shared mode

Implementation of mutexes and condition variables

Atomicity between processes

• Say you’re writing a grading server for a course like CS 61
• Want to check out student code into a new directory
• What if student has two browsers?
• open(FILE, O_WRONLY | O_CREAT | O_EXCL)
• rename(OLD, NEW)

Atomicity and security

• Time-of-check-to-time-of-use (TOCTTOU) vulnerabilities (link)

Research!

Next

• CS 161: Operating Systems

• CS 165: Data Systems (fall)

• CS 260r: Topics in Computer Systems (this year: parallel and distributed execution models)

• CS 263: Systems Security (fall 2023)

• CS 265: Big Data Systems (spring 2023)

• CS 153: Compilers (fall)

• CS 141: Computing Hardware

• CS 148/248: Design of VLSI Circuits and Systems

• CS 145/245: Cloud Networking and Computing (2022/2023)

• CS 96: System Design Projects: Machine Learning for Social Impact

• CS 124: Data Structures and Algorithms

• CS 143: Networks

• CS 175: Computer Graphics

• CS 181: Machine Learning

• CS 191: Classics of Computer Science

• CS 222: Algorithms at the Ends of the Wire (future)

• CS 286: Multi-Robot Systems: Control, Communication, and Security

THANK YOU!