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

  • MINE SWEEPER - University of Florida

    MINE SWEEPER - University of Florida

    Project Abstract The main objectives of this project are To move to the center of the playing surface and starting to look for IR. To find and deactivate four IR emitters, while avoiding 4 fixed mines and a random mine....
  • MSA 685 - Central Michigan University

    MSA 685 - Central Michigan University

    MSA 698 The Papers must be between 8-10 pages Executive Summary Introduction Body Conclusion Recommendations and next steps References MSA 698 For the conversion of the proposal to the paper introduction, rewrite to past tense (not future tense) and the...
  • MUGSHOTS Recognize anyone??? Snooki Snooki (real name: Nicole

    MUGSHOTS Recognize anyone??? Snooki Snooki (real name: Nicole

    'Son of Sam' David Berkowitz posed for this New York State Department of Correctional Services mug shot in March 2003. The serial killer received six consecutive sentences of 25 years to life for a late-70s murder spree in New York...

    TO DOWNLOAD APPLICATION FORM: Download the free software before opening the form, if you do not have Adobe Reader (version 10 or later). Download Application and "Save as" a PDF to your Local Drive before opening. Open directly with Adobe...
  • Circles Purple template

    Circles Purple template

    Ar ôl hanner tymor byddwch yn gwerthuso eich gwaith gwirfoddol eich gwersi Bagloriaeth Cymru felly bydd rhaid i chi fod wedi gorffen pan ddewch yn ôl i'r ysgol. Siaradwch â Miss Feathers neu Mrs Hawke-Jones os ydych yn poeni na...
  • Active Audiences Round Table National Plan of R+D

    Active Audiences Round Table National Plan of R+D

    Active Audiences Round TableNational Plan of R+D. Welcome and IntroductionL. Codina (UPF) Information Web Pages. Active Audiences > general information 2014 > issue devoted to Active Audiencies.
  • "Brevity is the soul of wit."

    "Brevity is the soul of wit."

    After you've written your speech, it can be helpful to put it on 3-by-5 inch index cards. Just be sure to put huge numbers on the front of each card, in case they accidentally get shuffled around. But don't use...
  • Présentation PowerPoint - Traditional Music Library

    Présentation PowerPoint - Traditional Music Library

    Silent night! holy night! All is calm, all is bright Round yon virgin mother and Child, Holy Infant so tender and mild, Sleep in heavenly peace, sleep in heavenly peace. Silent Night, Holy Night N°143 Silent night! holy night! Shepherds...