Synchronization Supplement 1: Organizing time

Overview

In this supplemental lecture, we discuss how synchronization relates to organizing time.

Full notes on synchronization

Programming organizes state

• A function’s local variables are isolated from the rest of the program
• Process memory is isolated from the rest of the system
• Isolation helps organize state (values, memory)
  • Prevents interference and bugs
• Imagine programming only in assembly!

Complete isolation is useless, overisolation is inefficient

• Software’s purpose is to interact with the world through input and output
• Input and output can be slow
• What should a computer do while one process is waiting for input and output?
  • “Nothing” is the safest response
  • But that wastes computing resources (and power, money)
• Answer: Run other software
  • OS runs other processes
  • Within a process, run other threads

Multithreaded programming must organize time

• Multiprocessing lets two or more processes access the same environment
• Multithreading lets two or more logical threads of control access the same memory state
• Simultaneous accesses to the same state can conflict
• Bad schedules (access orders) can block threads forever
• Synchronization is the art of organizing time to prevent conflicts and comatose threads

Thanksgiving example

• I made a Brussels sprout dish in my brother’s kitchen

• Usually one roasts Brussels sprouts
• In this dish, you separate all the leaves first
• That takes an hour

• Meanwhile, my mother is trying to help by cleaning up garbage

Our procedures

Me	Marilyn
Cut bottom from sprout Separate sprout into leaves Put leaves in bowl If bowl is full, put it somewhere and get clean bowl Goto 1	Find unattended container Check if it contains garbage If so, throw out garbage, clean container Goto 1

Conflict 1: Data race

• Two threads access normal memory simultaneously, and at least one access is a write
• Result: Undefined behavior
• Example: incr-basic
• Solution: Atomic access with std::atomic or mutual exclusion (below)
• Detect issue with thread sanitizer

Conflict 2: Invariant-violating conflicts

• A thread assumes a value does not change, but it does change because of concurrent access
• Result: Incorrect computation
• Example: incr-atomicbad
• Solution: Mutual exclusion

Horrifying real-world example of invariant-violating conflict

Mutual exclusion and locks

• Mutual exclusion holds when only one thread can access a certain part of memory at a time
• Mutual exclusion can avoid data races and invariant-violating conflicts
• How to enforce it?

Mutual exclusion synchronization objects

• Atomic effect can be modeled as exclusion
• One thread of control (CPU or process thread) gains temporary exclusive access to some data
• Atomic instructions and atomic data types provide inexpensive exclusion, but to tiny data chunks (e.g., single integers)
• Synchronization objects are higher-level concepts that help implement exclusion on larger or more complex data types

Lock interface

• A (mutual exclusion) lock is a synchronization object with two methods, lock (also known as acquire) and unlock (also known as release)
• C++ datatype: std::mutex
• Underlying state: the lock owner (which is a thread ID)
• Operation of m.lock()
  • Block until no lock owner, then atomically assign owner to self
• Operation of m.unlock()
  • Assert that lock owner is self, then clear owner

incr-mutex.cc

std::scoped_lock

• Acquire a mutex (or several mutexes) for a block of code
• Automatically releases the mutex when the block exits
• incr-scopedlock.cc

Question

• How can we implement a mutex?

Compare-exchange (compare-and-swap)

• bool atomic<T>::compare_exchange_weak(T& expected, T desired)

incr-spinlock.cc

• The spinlock version polls
• The mutex version blocks

process4/timedwait-threads.cc