Lock-free Programming

• Threads execute critical sections concurrently

  • Without data races
  • But without using the operating system's locking facilities

• Avoids or reduces some of the drawbacks to using locks

  • Race conditions caused by forgetting to lock, or using the wrong mutex
  • Lack of composability
  • Risk of deadlock
  • High overhead
  • Lack of scalability caused by coarse-grained locking
  • Code complexity and increased overhead caused by fine-grained locking

Locking vs Lock-free

• Both Programming styles are used to manage shared state

  • Analogous to managing a traffic intersection

• Locks

  • Traffic lights control access
  • Stop and wait until able to proceed into critical section

• Lock-free

  • Motorway style intersection
  • Traffic from different levels can go over the same section at the same time
  • Traffic from one level can merge with traffic from a different level without stopping
  • If not done carefully, collisions can occur!

Advantages of Lock-free Programming

• If done correctly, threads can never block each other
  • No possibility of deadlock or livelock
  • If a thread is blocked, other threads can continue to execute
  • Useful if work must be completed within a time limit (e.g. real time systems)

Drawbacks of Lock-free Programming

• Very difficult to write code which is correct and efficient

• The extra complexity makes it unsuitable for many applications

  • e.g. user interface code with separation of concerns
  • May be useful in performance critical code, such as infrastructure

• Should be used only if

  • A data structure in the program is subject to high contention
  • Which causes unacceptable performance
  • And the lock free version brings performance up to acceptable levels

The Everyday World of Programming with Locks

• We can make some very useful assumptions

• Global state is consistent

  • Provided we only access shared data inside a locked region
  • No other threads will see our changes
  • Until the lock is released

• Logical consistency

  • When working inside a locked region, global state will not change
  • e.g. between evaluating an "if" statement and executing the body

• Code order

  • Statements will execute in the same order as in the source code
  • Or at least, they will appear to...

The Strange World of Lock-free Programming

• None of these assumptions apply to lock-free programs
  • Shared data may have different values in different threads
  • The value may change between an "if" statement and its body
  • Statements may execute in a different order from the source code

Transactions

• Transactional model of lock-free programming

  • "ACID"

• Atomic / All or Nothing

  • A transaction either completes successfully ("commit")
  • Or it fails and leaves everything as it was ("rollback")

• Consistent

  • The transaction takes the database from one consistent state to another
  • As seen by other users, the database is never in an inconsistent state

• Isolated

  • Two transactions can never work on the same data simultaneously

• Durable

  • Once a transaction is committed, it cannot be overwritten
  • ... Until the next transaction sees the result of the commit
  • There is no possibility of "losing" an update

Transactional Memory

• Put shared data in transactional memory

• All operations on shared data will be transactional

• However, there is no standard implementation in C++

• The only way to write a lock-free program is to use atomic instructions

• We need to think very carefully about thread interactions

  • Other threads can interleave between each statement
  • Or between expressions within statements
  • How do concurrent writers interact with each other?
  • How to concurrent writers interact with concurrent readers?