Data Structures & Concurrency

• A data structure has multiple elements
  • Multiple threads may access these elements
  • These accesses can conflict
  • Locks or atomic operations may be needed

Modifying Operations

• May affect other parts of the object

• Linked list

  • Data stored in a chain of nodes
  • Adding or removing an element modifies the surrounding nodes

• Vector / String / Dynamic Array

  • Data stored in memory block
  • Adding or removing elements moves the following elements in memory
  • Adding elements may cause the block to be reallocated

• If other threads are accessing those elements

  • Pointers and references may "dangle"
  • Iterators may become invalidated

Basic Thread Safety Guarantee

• STL containers are "memory objects"

• Concurrent reds of the same object are safe

  • Many threads can read from object X

• A single write of an object is safe

  • One thread can write to object X
  • Provided no other threads access X concurrently

• Concurrent reads and writes of the same object are not safe

  • One thread writes to object X
  • Other threads must not access X during this operation

Coarse grained locking

• Locks the entire object

  • Easy to do
  • Requires no change to the data structure

• Sometimes the only option

  • A variable of built-in type
  • Types in the C++ Standard Library
  • Types provided by other programmers, if we cannot modify them

• In effect, all code that accesses the object will be single threaded

  • Serial code

Fine grained locking

• We can choose which parts of the object to lock

  • We only lock some of the elements

• This is known as "fine-grained locking"

  • Allows concurrent access
  • Requires writing extra code
  • Requires careful design
  • Increases cost of created object (mutex initialization)