Threads and Locks, Critical Sections and Isolation

Threads and Locks
Critical Sections and Isolation

Coursera Concurrent Programming in Java - Week 1,2

Threads and Locks

Threads

Thread t1 = new Thread(new HelloRunnable); // can put a class that implements Runnable
Thread t2 = new HelloThread(); // HelloThread extends Thread
// Which of these idioms should you use? The first idiom, which employs a Runnable object, is more general, because the Runnable object can subclass a class other than Thread. The second idiom is easier to use in simple applications, but is limited by the fact that your task class must be a descendant of Thread.

// in main()
t1.start();
t1.join(); // main thread t0 will wait for t1 to finish

Reading : (The SimpleThreads Example)[https://docs.oracle.com/javase/tutorial/essential/concurrency/simple.html]

Structured Locks

Structured locks can be used to enforce mutual exclusion and avoid data races

Guarded blocks : 𝚜𝚢𝚗𝚌𝚑𝚛𝚘𝚗𝚒𝚣𝚎𝚍 keywords
Intrinsic lock or monitor lock : synchronized statement
bounded buffer implementation
wait()
notify()

https://docs.oracle.com/javase/tutorial/essential/concurrency/guardmeth.html

https://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html

Unstructured Locks

𝚁𝚎𝚎𝚗𝚝𝚛𝚊𝚗𝚝𝙻𝚘𝚌𝚔()

The first example showed how explicit 𝚕𝚘𝚌𝚔() and 𝚞𝚗𝚕𝚘𝚌𝚔() operations on unstructured locks can be used to support a hand-over-hand locking pattern that implements a non-nested pairing of lock/unlock operations which cannot be achieved with synchronized statements/methods.
The second example showed how the 𝚝𝚛𝚢𝙻𝚘𝚌𝚔() operations in unstructured locks can enable a thread to check the availability of a lock, and thereby acquire it if it is available or do something else if it is not.
The third example illustrated the value of read-write locks (which can be obtained in Java by creating instances of 𝚁𝚎𝚎𝚗𝚝𝚛𝚊𝚗𝚝𝚁𝚎𝚊𝚍𝚆𝚛𝚒𝚝𝚎𝙻𝚘𝚌𝚔()), whereby multiple threads are permitted to acquire a lock 𝙻 in “read mode”, 𝙻.𝚛𝚎𝚊𝚍𝙻𝚘𝚌𝚔().𝚕𝚘𝚌𝚔(), but only one thread is permitted to acquire the lock in “write mode”, 𝙻.𝚠𝚛𝚒𝚝𝚎𝙻𝚘𝚌𝚔().𝚕𝚘𝚌𝚔().

Liveness

Deadlock

The first is deadlock, in which all threads are blocked indefinitely, thereby preventing any forward progress.

Livelock

The second is livelock, in which all threads repeatedly perform an interaction that prevents forward progress, e.g., an infinite “loop” of repeating lock acquire/release patterns.

Starvation

The third is starvation, in which at least one thread is prevented from making any forward progress.

Dining Philosophers

The following simple algorithm can deadlock with all philosophers holding their left chopsticks.

// All philosophers:
while (True) {
    acquire philosopher's left chopstick
    acquire philosopher's right chopstick
    eat
    release right chopstick
    release left chopstick
}￼

If we use unstructured locks with 𝚝𝚛𝚢𝙻𝚘𝚌𝚔() and 𝚞𝚗𝚕𝚘𝚌𝚔() operations that never block, but this solution could lead to a livelock scenario (but not deadlock)

Finally, we observed how a simple modification to the first solution with structured locks, in which one philosopher picks up their right chopstick and their left, while the others pick up their left chopstick first and then their right, can guarantee an absence of deadlock. (But may cause starvation)

Further reading : (Dining philosophers problem)[https://en.wikipedia.org/wiki/Dining_philosophers_problem]

Critical Sections and Isolation

Critical Section

Concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed are protected. This protected section is the critical section.

With critical sections, two blocks of code that are marked as isolated, say 𝙰 and 𝙱, are guaranteed to be executed in mutual exclusion with 𝙰 executing before 𝙱 or vice versa.

https://en.wikipedia.org/wiki/Critical_section

Object Based Isolation (Monitors)

The fundamental idea behind object-based isolation is that an isolated construct can be extended with a set of objects that indicate the scope of isolation, by using the following rules: if two isolated constructs have an empty intersection in their object sets they can execute in parallel, otherwise they must execute in mutual exclusion.

Linked list delete() example
The Java code sketch to achieve this object-based isolation using the PCDP library is as follows:

isolated(cur, cur.prev, cur.next, () -> {
    . . . // Body of object-based isolated construct
});

Concurrent Spanning Tree Algorithm

Spanning Tree Algorithm : recursive DFS, multiple thread may try to call makeParent(v, c) to same vertex c, which may cause data race. Solution : we can use object isolation to isolate vertex c to avoid data race, now we can allow multiple threads to explore different branches concurrently.

compute(v) {
  for each neighbor n of v {
    if makeParent(v, n) {
      async compute(n)
    }
  }
}

boolean makeParent(v, c) {
  isolated(c) {
    if c.parent == null {
      doWork(1)
      c.parent = v
      return true
    } else {
      return false
    }
  }
}

finish {
  root.parent = root;
  root.compute();
}

Atomic Variables

j=cur.getAndAdd(1)

has same semantics as

isolated(cur) { j=cur; cur=cur+1}

(compare-and-swap (CAS))[https://en.wikipedia.org/wiki/Compare-and-swap]
If we have an atomic reference ref, then the call to ref.compareAndSet(expected, new) will compare the value of ref to expected, and if they are the same, set the value of ref to new and return true. This all occurs in one atomic operation that cannot be interrupted by any other methods invoked on the ref object. If ref and expected have different values, compareAndSet() will not modify anything and will simply return false.

https://en.wikipedia.org/wiki/Primitive_wrapper_class#Atomic_wrapper_classes
https://docs.oracle.com/javase/tutorial/essential/concurrency/atomicvars.html

Read-Write Isolation

The main idea behind read-write isolation is to separate read accesses to shared objects from write accesses. This approach enables two threads that only read shared objects to freely execute in parallel since they are not modifying any shared objects. The need for mutual exclusion only arises when one or more threads attempt to enter an isolated section with write access to a shared object.