Concurrent Programming

• has its own heap and stack (address space)
• IPC: requires sys call, hence slow
• created in UNIX using fork – everything same except return code

• share address space; shared heap
• pthreads: POSIX threads
• IPC don't require sys call

everything which is created is deleted/cleared after return Thread safe

• Gives methods such as increment
• C++ added atomic DS in C++ 11.
• utilizes hardware to provide atomicity

• Package java.util.lock - Interface
• ReenterantLock
• Exceptions in critical section

  • use unlock in finally

    l.lock()
    try
      //critical section
    finally
      l.unlock()
    

• Note, we need to lock lastNumber return lastFactor, we return what we checked [slide 25]

• pthread_mutex_[lock,trylock,unlock]
• tryLock returns true/false
• reenterantLock or pthread_mutex_recursive same thread can lock the same lock
  • Java - reenterantLock is default; C,C++ says otherwise
• No garbage collector: pthread_mutex_destroy

• used with synchronized keyword
• compiler gives support for proper use
• this is default object for locking
• synchronized keyword is not inherited in sub classes
• Java: intrinsic lock can also be on class object, refer SO (slide 47)

• ++ is overloaded
• implemented by runtime
  • often utilized using hw instruction
  • if not available, it uses lock
  • in c++, is_lock_free indicates if lock is used

• sides of the FENCE are not mixed
  • eg: ARM calls fence as sync
• compiler takes care of it
• add FENCE only when required

• eg: dead code elimination -> spin locks

• some mean race, as un wanted behavior due to schduler

• ensure happens before relation between construction and use of object
• wrapper for implementing multithreading
• do not trush the function
• block pointers

• final is special in Java wrt to concurrency
• call_once is corresponding stuff in C++

• one single lock
• no public fields
• finite
• consistent
• publish object without data race

• maybe too small granularity
• identify stateless
  • does not rely on mutable object
  • slide 56, why make a copy of b
    • maybe read > 1 in compute

• lock only one element of the data structure
  • in example in slides: lock means, to delete predecessor we need lock
    • what about inserting new node (my question)

• let things happen, then check if something went wrong
• better if low contention
• Atomic commit
  • check if anything changed
  • if no, then edit/commit
• dont use optimistic sync if irreversible side effects

• relevant when we need to update multiple field in the same object

• main thread
• event queue for GUI

• create button
• create listener
• install listener

• event dispatch thread cannot do long computation - GUI freeze
• listenerList is copy-on-write
• what happens if event is removed from listenerList
  • handle events even after removing listener

• C++, template - any class can be put in
• use exception - inherit from standard exception
• default compiler will generate the function
• delete cannot be called
  • copy constructor
  • = operator
• lock_guard auto release when goes out of scope
  • even if exception happens
• shared_pointer auto deleted after all reference are exhausted

• cannot be solved just by making all methods synchronized
  • empty is shared, two threads in different synchronized methods can access the same variable.

• how to test data races?
• create threads, add to queue
• make threads to add certain intervals
• time to make thread v/s work done in thread

• when thread hold multiple locks - think about deadlocks

• hard to detect deadlock accurately in distributed concurrent programs
• if there suspicion that there is deadlock, consider as there is deadlock
• synchronized keyword doesn't allow to try_lock
• try_lock returns false if could not acquire lock else lock.
• try to get lock, if not acquired then release own lock
  • 0, try again immediately
  • constant delay
  • random delay
  • exponential back off

• 10 priority levels in Java, maybe mapped to lesser number of OS thread priority
  • thread priority may not be very useful
• give daemon thread low priority

• obj reacquires the lock after coming from wait state.
• check and wait must be in a while loop

• safety is correctness
• doing nothing can also be correct
  • ensure Liveness
• notify v/s notifyAll
  • notify may be efficient
  • notifyAll may be easier to prove correct

• condition_variable

• concurrent read allowed

  nr > 0 || nw == 1
  

• invariant

  0 <= i ^ 0 <= j ^ 0 < i - j <= N
  

• Sockets have timeout
  • poll when timed out

• forcefully close resource

• no support
• use Boost
• can be implemented using Java.socket like timeout
  • Refer: C++ concurrency in action: Practical Multithreading

• only one thread does (slide 59)

//thread 0
int x = ...
Boolean done = true;

//thread 1
if (done) {
//do something with x
}

Here declare x as volatile This is also the reason for problem in double checking idiom. Due to assignment re-ordering, the constructed object can reflect as non NULL before construction is finished.

If a thread acquires >= 2 locks, think of deadlock. Two ways of dealing with deadlocks:

1. Avoidance: order them so that without first locking 'A', should not lock 'B'. In java, we can use System.identityHashCode to get unique value from totally ordered set.
2. Dealing with deadlock: use tryLock, which uses timeout to tell locking failed. Then re-try, with:
   1. certain timeout
   2. exponential back off
   3. random delay
   4. 0 delay

1. mark variable as static
2. mark as volatile
3. refer from concurrent data structure, such as ConcurrentQueue etc.
4. keep atomic reference.

• obj.wait() only releases one lock, if it is nested inside multiple locks, this will release only 1 (outer ones are still acquired).

• #guards = conditions to be satisfied
• guards are conditions, thus multiple invariant expression can form a single guard. Ex: in reader/writer, nr == 0 ^ nw == 0 denotes safe for writer.
• be careful of the initial state of semaphores

A Runnable, does not return a result and cannot throw a checked exception.

• ReentrantLock provides timed lock waits, interruptible lock waits, non-block-structured locks, multiple condition variables and lock polling
• ReentrantLock can give conditional locking.

• getAndSet() creates a lot more traffic on message bus than get(). Thus it is better to test by get() before spinning on getAndSet(). getAndSet() invalidates the cache, thus substantial performance penalty.

• lock_guard automatically releases lock on reaching closing brace. Takes care of exception.
• unique_guard: same as lock_guard, but can be unlocked and locked again.

• safety says nothing bad happens
• liveness something good will eventually happen

• 2 options:
  1. Thread Pool
  2. Futures

Java lambda automagically turns into runnable or callable depending on if value is returned

Lambda, runnable, callable are all closure.

• Lvalues are memory location

typical use case: divide and conquer

• LinkedBlockingQueue: blocks if queue empty
• Saves the thread somewhere so that it can interrupted if needed.
  • since executor class is used, we don't know which thread computes what
• efforts made to make thread cancel at safe point

• atomic reference to array of int
• array of atomic int
  • atomicInt are mutable
  • safe
• atomicIntArray
  • safe to add new integers: java docs

• uses virtual linked list

• check java.util.ConcurrentLinkedQueue source code

• use bits to denote lock
• rest of the bits to represent tail position index

missed inital part, was fixing fiber lamp! :D

• stored in hashtables

• fast path if no contention
• convert to fat lock if contention
• header contatains bits which indicate if there is a lock. If there is need for fat lock, the bits points to fat lock.

No!

resolve conflict by

• happens before
• mark as volatile

• what is it for a data structure to be correct to be serial
• when not locks

• Linearization order is order lock released

• not composible
  • re-ordering can cause cycles

wiki link

• Every contending thread is guaranteed to complete its method call within a bounded

number of its own time steps.

• have helper thread to substitute for the thread
  • so that even if the thread fails, it can take over

• Lock-freedom allows individual threads to starve but guarantees system-wide throughput
• Some contending threads are guaranteed to complete their method call within a bounded number of steps
• The difference between Wait free and lock free is, in wait free operations every process is guaranteed to succeed in finite amount of steps

In absence of contention, a thread is guaranteed to complete its method within a bounded number of steps

• if a read call that doesn't overlap a write call returns the value written by the most recent write call
• otherwise, if a read call overlaps with a write call then it can return any value within register's allowed range of values

• safe
• if read overlaps i^th write, then read value can be between i and (i - 1) write

• SRSW

• get idea, skipped slides

• once in critical section, it can go away
• not all wait free are practical

• we get value of variable
• then check if value is still olf, if yes change to
• what if someone changes to old value

• cannot have lock free

• add to program, compiler takes care of it. If compiler doesn't understand it then it ignores
• Fork-join Parallelism
  • need not create actual thread, might be thread pool

• example:

  #include "omp.h"
  ...
  #pragma omp parallel for
  for (i = 0; i < 1000; i++) {
    //some big computation
  }
  

• works only (better?) on structured/blocked code
  • because there is implicit barrier at end of block

• most variables are shared
• local variables are not shared

• don't accumulate!
• operator
  • associative
  • commutative
• form: reduction(op : list)
• based on operator the var are initialized
  • + 0
  • * 1
• slide 60: by applying reduction clause, we get final result in res
  • each thread is doing some accumulation
  • without the reduction clause. res is shared, so accessing it needs to be synchronized

• incorrect update of cache.
• array: values next to each other, updating one, updates the whole cache line which contains other elements

• special case of critical section

• #pragma omp barrier: explicit
• wait until all threads arrive
• implicit barrier at end of block
• lot of barriers by default
  • nowait()

sequencial ordering

• if operation is not associative/commutative

• memory synchronization
• creates consistent view of memory
• write everything to memory before flush, read everything after flush from memory

• setting options at runtime (after compiling, during execution)

• when to flush
• memory not symmetric, some memory close to some processor

• divide and conquer
• serial to parallel

• programmer needs to take care of it

• Elapsed time
  • TODO: how good is this, multi processors real time
  • Java: System.nanoTime
  • C++: chrono package
• Price/Performance
• Speedup
• Efficiency
• Energy Efficiency

• Effect of serial part to overall performance.
  • or serial part limits the overall performance

• UE: unit of execution
• Memory Sharing needs locks
• You cannot receive a message before it is sent

• type inference

• share memory by communicating
• goroutine:
  • lightweight
• channels:
  • first class, can be passed around

• local data
• mailbox (message queueu)
• Loop - handle messages

• actors do not share memory
  • can't send references
  • send deep copy
    • many frameworks try to optimize this
      • send ref if safe
      • immutable messages are safe
      • enforcing encapsulation may not be guaranteed
• sending message is synchronous in OOP

• portable message passing format

• constant

• similar to MPI_recv

same code, based on id decide who process what part

• send and recv return immediately, we'll need to handle using MPI_Wait

• instead of having array of structs, have stucts of array
  • better performance due to locality

• Cuda and OpenCl

• portable way to use all CPUs, GPUs etc

• 6 pages notes
• 10am to 12, 14th December

• Homework
• Definitions
• Previous Exams

1. Resource ordering
   • can use System.identityHashCode
2. Deadlock suspicion
   • lock with timeout
     • not available with monitor -> use reentrant

ways to check

• Optimistic: do everything then check
• Balking
  • Guarded Suspension: suspend until preconditions not true
  • Timed Waiting: wait for certain time then balk
• atomic await <await B {S}> wait till B becomes true then atomically execute S
  • Implement
    • Test a condition and suspend thread if not true
    • release lock before suspending
    • awaken, re acquire lock before proceeding

  • Every Object in Java has 2 Queues: wait set and lock set

    <await B {S}> => synchronized (obj) {
                         while (!B) { obj.wait(); }
                         S;
                     }
    

    • wait gives safety
    • notify gives liveness
  • Condition Variables
    • Java: cv = ReentrantLock.newCondition()
      • each condition variable has it's own wait set.

      • Comparison with monitor

        cv	await	signal	signalAll	for specific condition
        monitor	wait	notify	notifyAll	for specific monitor lock

    • C++: std::condition_variable c;
      • c: takes in mutex (needed for release and reacquire mechanism)
      • optionally takes in condition (guard) else we need to manually loop on !B (condition)
  • Reader Writer lock: more expensive than mutex
    • only situation when write less and lock for small time