Lecture 9 Synchronization 1 Java Synchronization - concurrent objects safety

The problem: Threads may access the same object concurrently. @invariant/correctness is not guaranteed. Solutions (achieve safety) Design concurrent execution using copies of (immutable) objects. Synchronize access to internal state of the object.

2 class Even 3 Visibility and Reordering unsafe constructs in concurrent execution

Visibility - when threads see values written to memory by other threads. Reordering - compiler / RTE change code to optimize it. 4 Visability example 5

thread t may not "see" the changes to the state of d performed in main thread main calls d.set(10): 10 is written to i_ member of VisibilityDemo object t reads from i_: (d.get() ) At the same time d.set(20) is performed (race condition). Java does not guarantee t sees any recent

value written to this memory location. 6 Re-ordering compiler must be able to re-order simple instructions to optimize our code compiler guarantees safe reordering in non-concurrent execution environments.

7 must-happen-before compiler would not reorder if "must-happenbefore" constraint 8 Monitors:

synchronized construct in Java Any object has a monitor, used as a lock. Allows only one thread at a time to enter the object. synchronized keyword on a non-null object: 9 The house analogy

Object = house. Objects Monitor = key. People = threads. Only one thread can have the key and enter the house.

10 synchronized construct in Java Similarly to the previous case, we may write: This is just syntactic sugar. 11 synchronized

Java ensures that only one thread access this Object. public synchronized int add() - only one thread is allowed to enter all the Objects methods. solves visibility and reordering problems; "write" to memory during synchronized code section is guaranteed to be returned to all "read" operations following it.

12 How "synchronized" is implemented? Each object inside JVM (at runtime) has a lock ("monitor") JVM maintain/initialize locks. We cannot access locks explicitly We can access implicitly using synchronized

13 Monitors (locks) locks are in one of two states; 1. in possession of thread 2. available thread T tries to acquire the lock of any object. if available lock transferred to Ts possession

otherwise, T sleeps (in a queue) until lock available T wakes up and tries to acquire lock 14 synchronized each thread, calling the method, must first acquire lock.

when thread exits thread releases lock 15 The cost of locks time, concurrency Memory sync.: after thread exits, it synchronizes with the main memory thread may cache copies of memory in its

own memory (e.g., CPU registers / CPU cache). Blocking: threads must wait for each other 16 When to Use Synchronization When we want atomic (all-at-once) actions. When we want to solve the re-ordering and

visibility problems. monitor - internal state of object is encapsulated. objects are responsible to synchronize access to state: synchronized get()/set(). Try to avoid and reduce Synchronization!!! Our threads are waiting for synchronization. 17

Synchronized Properties synchronized keyword is not part of the method signature. synchronized keyword cannot be specified in an interface. constructors cannot be synchronized (syntax error) no point - as long as constructor is not complete, object instance is not accessible to other threads, unless static method as synchronized - lock associated with the class to be used

(each class in Java is also an object on its own) Java locks are Reentrant: same thread holding the lock can get it again and again. 18 Partially synchronized Objects (example)

19 Design patterns 20 Is the doSomething function "thread safe"? 21

Is the doSomething function "thread safe"? No. After calling the l.contains other thread may add 42 to our list, and then doSomething will add another one.. 22

Is this solution correct? 23 No. The lock protecting doSomething() is different from the lock protecting the add(). 24

Option: add a addIfAbsent()method. Extending LinkedList class and add the function we want? do not know how the class LinkedList protects itself from concurrent access. 25

Composition / Containment wrapper around LinkedList class: Enforces right synchronization policy Delegates all calls (after synchronization is verified) to underlying implementation class. 26 Composition / Containment

We know exactly which lock is used to synchronize access to our list. best applied in situations where: We are not sure/ do not know the internal implementation of an object. Implementation of object may change without our knowledge. 27

Client Side Locking If we know the identity of the object which is used for synchronization If LinkedList class uses its own monitor (lock) to achieve synchronization, then: 28

Client side locking not so good approach only when we know internal implementation not when implementation may change not Object Oriented: responsibility of synchronization to clients instead of object cannot ensure consistency among ALL clients : If client does not synchronize correctly, then

ALL the code will behave incorrectly. better to enforce safety on provider side 29 Version Iterators 30

what will happen if while executing printList() another thread will change l? Optional solution: create a temporary copy of the LinkedList, and then iterate over this copy. It may be too expensive. We still need to iterate the LinkedList in order to copy it.

synchronize the loop on LinkedList? body of loop may be arbitrarily long - locking the entire list for the entire loop. 32 Solution - fail-fast iterators

A better solution is a fail-fast iterators - which are iterators that: Detect that a change to the data structure happened while they are in use. Throw an exception in order to indicate that they are inappropriate for usage any more. useful for many readers few writers model. Version iterators implementation of fail fast

iterators. 33 34 Balking Popular in serial codes. Methods fail if precondition does not hold.

35 Guarded suspension precondition may hold in the future (other threads may change it) wait until precondition holds. guard asserts that another thread will make required state changes

36 Guarded Suspension (wait) constructs: wait() and notify(), notifyAll() 37 Policies for failed preconditions/invariants Balking. throw exception if precondition fails.

Guarded suspension. suspend method invocation (and thread) until precondition becomes true. Time-outs. Something in between balking and suspension. bounded wait for precondition to become true. Implemented using Objects wait(long timeout) 38

wait() Threads wait() until some other thread wakes them up each object has a wait set - similar to locks maintained internally by the JVM set holds threads blocked by wait() on object until notifications are invoked or waits released 39

notify() threads enter wait queue of object o by invoking the wait() of o. thread wakeups threads from queue of o by: o.notify()/o.notifyAll()

40 41 wait/notify cycle o.wait() - wait invocation current thread calling wait() is blocked. JVM places thread in wait set(queue) of o.

o.notify() - notify invocation arbitrary thread T is removed from os wait set T is resumed from the point of wait(). o.notifyAll() like notify except for all threads in os wait set 42

Common pitfalls - guard atomically Can we put if instead of while? 43 Common pitfalls - guard atomically 44

Common pitfalls - guard atomically Can we put if instead of while? No! If two threads are waiting, and only one add() is invoked: Two threads are notified. Only one of the notified threads can remove item. The other one needs to keep waiting. 45

Common pitfalls - wait atomically 46 Common pitfalls - wait atomically Scenario: exactly one producer and one consumer. Consumer calls removeFirst() but stopped after

the condition by the scheduler. Producer calls add() successfully. Producer: NotifyAll() but no one in queue! Consumer: checks the condition and wait() forever. Sometimes threads are woken up without notify(). 47 Rules of Thumb for Wait and Notify

Guarded wait - Blocking a thread to wait() for a condition. Guard atomicity - Condition checks must always be placed in while loops. Multiple guard atomicity If there are several conditions which need to be waited for, place them all in the same loop. Don't forget to wake up - To ensure liveness, classes must wake up waiting threads. notify() Vs. notifyAll():

when multiple threads wait for a multiple conditions on the same object, we must use notifyAll() to ensure that no thread misses an event. 48 Semaphores Object controls bounded number of permits (permit = train ticket):

Threads ask semaphore for permit (a ticket). If semaphore has permits available, one permit is assigned to requesting thread. If no permit available, requesting thread is blocked until permit is available (when a thread returns back a permit). 49

implementation 50 implementation 51 Java Semaphore properties

not re-entrant thread calls acquire() twice, must release() twice! semaphore can be released by a thread other than owner (unlike lock) no ownership. services as tryAcquire() and managing permits. 52 Readers/Writers Example

We wish to allow readers and writers to access a shared resource under different policies. Common policy: several readers can access resource together. only one writer can access resource at given time. Example: Readers wait if writer is pending. One writer at a time can access the shared

resource, if no readers are reading from it. 53 java.util.concurrent.locks.ReadWriteLock interface ReentrantReadWriteLock implementation. 54

55 RW implementation Several readers can access the resource together. Only one writer can access it at any given time. Only if no readers are Readers will wait if any writer is pending. Prevents starvation of writers.

Reads in principle can be starved. 56 Atomic Instructions Atomic: happens all-at-once. Most CPU operations (like add, mov etc.) are atomic. CPUs today offer a set of atomic instructions for multithreading. The CompareAndSet (cas) example:

57 Atomic Instructions Atomic: the scheduler cannot stop a thread in the middle of this operation - only before or after it. The compareAndSet instruction is extremely useful and powerful. Java has several classes (all beginning with

Atomic* that allow us to use compareAndSet). 58 Even using synchronized 59 Even counter class using

AtomicInteger AtomicInteger: holds int so that we can call compareAndSet() on. There is no usage of synchronized anywhere in the class. 60 Even counter class using

AtomicInteger If there are n threads t_1,...,t_n that attempt to invoke add() one time all at once then, without the loss of generality: t_1 will enter the while loop once, t_2 at most twice, and t_n at most n times.

61 LinkedList using cas: 62 Atomic Instructions: Advantages Threads are given a choice When their requested action cannot be performed - they

are given a choice on what to do, code wise This is instead of just being blocked in blocking algorithms No thread suspension Code runs significantly faster than the synchronized counterpart Threads are never blocked thus no system calls used!

Called lock-free. Reduced Thread Latency Limitations: Sometimes we want to block a thread, but cannot. Lock-Free data structures much harder to write. Some complex data structures may need to copy large amounts of data for lock-free implementation.

64 Volatile variables 65 Output: With the volatile keyword the output is :

Incrementing MY_INT to 1 Got Change for MY_INT : 1 Incrementing MY_INT to 2 Got Change for MY_INT : 2 Incrementing MY_INT to 3 Got Change for MY_INT : 3 Incrementing MY_INT to 4 Got Change for MY_INT : 4 Incrementing MY_INT to 5

Got Change for MY_INT : 5 66 Output: Without the volatile keyword the output is (can be different): Incrementing MY_INT to 1 Incrementing MY_INT to 2 Incrementing MY_INT to 3

Incrementing MY_INT to 4 Incrementing MY_INT to 5 67

Recently Viewed Presentations

  • SDC 3: Probability of Protection by A/Brisbane/2007 (A/H3N2)

    SDC 3: Probability of Protection by A/Brisbane/2007 (A/H3N2)

    SDC 3: Probability of Protection by A/Brisbane/2007 (A/H3N2) Titers at Day 50 Following Two Doses of Vaccine in 6 to <72 Months Old Children derived from the Dunning model.
  • Case 4 Dr.Seethalekshmy N.V, Dr.Smitha N.V, Dr.Hiran K.R,

    Case 4 Dr.Seethalekshmy N.V, Dr.Smitha N.V, Dr.Hiran K.R,

    Studies on the antihyperlipidemic properties of Averrhoa bilimbi fruit in rats. Planta Med 2009;75:55-8. Neto MM, da Costa JA, Garcia-Cairasco N, Netto JC, Nakagawa B, Dantas M. Intoxication by star fruit (Averrhoa carambola) in 32 uraemic patients: Treatment and outcome....
  • Employee Safety and Health -

    Employee Safety and Health -

    Employee Safety and Health. Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall. Chapter 16-Safety, as are ethics and labor relations, is ...
  • Chapter 1 Introduction to Computer Repair

    Chapter 1 Introduction to Computer Repair

    • RAID 5 is disk striping with parity where parity data is kept on one of the three minimum drives. This parity data can be used to rebuild one drive if one of three or more drives fail. • File...
  • Introduction to Gender Studies -

    Introduction to Gender Studies -

    Alan Dundes: "a sacred narrative explaining how the world and man came to be in their present form" EleazarMeletynsky: "The basic purpose of mythology is the ordering of chaos into cosmos, and cosmos does, from the very beginning, contain aspects...
  • default BG with logo only - IECEx

    default BG with logo only - IECEx

    It supports the aims of applying the hierarchy of risk controls & hazard reduction precedence, that is, get it right at the design stage with a high degree of confidence. It also supports the application of the Nertney Wheel, that...
  • 2008-04-07 Sfsu

    2008-04-07 Sfsu

    Implementation Process & Issues Moving from "startup" to enterprise Organizational administration issues academic policies Implementation Process & Issues Culture changes Faculty (teaching methods, Scholarship of Teaching and Learning research) Sameer Verma (ISYS) & Joshua Mindel (ISYS) - article Brian Beatty...
  • Circulatory System

    Circulatory System

    Episodes of typical (though severe) angina are triggered when one of the major coronary arteries suddenly goes into spasm, temporarily shutting off blood flow. Hidden Biology in intellectual literature and movies Original Willy Wonka and the Chocolate factory completed with...