Concurrency

Concurrency

1. Building Blocks

   • Spin Locks
     • i.e. keep testing whether the lock is free (busy wait), and grab it once it is
     • Atomic CAS
     • Atomic LL/SC
   • Semaphores
   • Conditional Critical Regions (CCRs)
     • shared int A, B, C; region A, B {     await( *some condition* );     // critical code using A and B }
   • Monitors
     • similar to CCRs but now - waiting is limited to EXPLICIT condition variables - all related routines are combined together into the monitor
     • Java's 'syncrhonized' primitive implements monitors
     • Condition Variables
       • basically a semaphore without the integer bit i.e. just a queue
     • Signal and Wait ("Hoare Monitor")
     • Signal and Continue

2. Concepts

   • Mutual Exclusion
   • Condition Synchronisation
     • Synchronizing on a condition. When you start working on a synchronization problem, first define the mutual exclusion constraints, then ask “when does a thread wait”, and create a separate synchronization variable representing each constraint. Bounded Buffer problem – producer puts things in a fixed sized buffer, consumer takes them out.  What are the constraints for bounded buffer?  1) only one thread can manipulate buffer queue at a time (mutual exclusion)  2) consumer must wait for producer to fill buffers if none full (scheduling constraint)  3) producer must wait for consumer to empty buffers if all full (scheduling constraint)
     • also tbh you can implement mutual exclusion with condition synchronisation the point is that you're waiting on a condition, not a lock

3. Problems

   • Critical Section
   • Producer Consumer
     • consumer condition: buffer can't be empty produce condition: buffer can't be full (have a semaphore Spaces and a semaphore Items) need mutual exclusion if we have multiple producers/multiple consumers
   • N-resource allocation
   • Multi-Reader Single-Writer (MRSW)
     • a shared resource accessed by a set of threads safe for many threads to read simultaneously, but a writer needs exclusive writer

4. Bad Things

   • Livelock
   • Deadlock
     • 4 conditions
       • Mutual exclusion
       • Hold-and-Wait
       • No preemption
       • Circular dependency
     • Dealing with it
       • Prevention
         • Impose partial order (dining philosophers)
       • Avoidance
       • Detection and Recovery
         • Resource Allocation Graphs
         • The matrix algorithm

5. Scheduling

   • Different policies
   • Priority inversion :(
     • priority inheritance

6. Concurrency Without Shared Data

   • Active Objects
   • Message Passing
   • Transactions
     • ACID properties
     • Serialisability