My Experiences Interviewing for a New Job

I recently interviewed for a new software engineering role.  It is a terrific time to be a software engineer in the Bay Area.  Lots of companies, big and tiny, are hiring.

Last time I searched for a job, I didn't really look around much.  This time, I went the other extreme and interviewed at 10 companies, mostly startups.  In retrospect, 10 was too many.  I should have spent more effort filtering out startups after the initial conversations with the founders/engineering leads, and should have avoided the first round of technical interviews if I wasn't entirely enthusiastic and convinced about the company or the role.  In multiple cases, I cancelled the second round of interviews after it became clear to me that a company would not be among my final top choices.  That way, I avoided further wasting everyone's time.

I applied to a couple of startups and big companies through friends who already worked there.  For most startups, I applied via a recruiter who contacted me over LinkedIn multiple times over the last one year.  He, and his colleagues at his firm, turned out to be excellent and presented many exciting startup opportunities to me, which I otherwise would not have known about.  I was initially concerned about recruiters being pushy, but these guys were super nice and professional.  I also participated in developerauction.com.

Last time I applied for jobs, I used my pdf resume.  This time, all I needed was my LinkedIn profile.  Only one company even asked for my pdf resume.  I spent a good deal of time (grudgingly) searching for my resume's latex source files, which I finally found on an external backup drive.  Now, it is checked in at bitbucket; but hopefully, I will never need it again.  An up-to-date LinkedIn profile is all you need these days when applying for a job.

Since I applied to too many companies this time, I did a LOT of interviews.  Most of my interviews were the standard "write code for simple algorithmic problem on the whiteboard". I really don't enjoy writing code on the whiteboard - it is so unnatural - but I did it without complaining and was successful.  At a couple of startups, I was asked only about my current projects and some high-level design problems - didn't write a single line of  code.  The best interview process was at a mid-sized mobile payment startup - 4 pair-programming interviews where we produced real working code and unit tests, 2 design interviews and one interview just to talk about my work experience.

Successfully tackling algorithmic questions on the whiteboard requires practice, especially if you, like most software engineers, don't deal with linked lists, dynamic programming, graphs, etc on a daily basis.  The last time I dealt with such problems on a daily basis was during my undergrad Algorithms class.   To refresh my memory, I went back to my old favorite algorithms text book - Introduction to Algorithms by Cormen, Leiserson and Rivest.  It was a great $8 investment made 10 years ago (a lot of money for a textbook in India in those days).  Here is a photo of the first page that is marked with my initials (DAnJo) and roll number.    The http://www.careercup.com website and associated book Cracking the Coding Interview: 150 Programming Questions and Solutions were also very useful in preparing for the interviews.

Interviewing took a lot of time.  However, it was a very enjoyable experience for me.  I was able to meet many amazing engineers across multiple super-cool companies (If you are looking for interesting startups, shoot me an email and I can send you some pointers).  I probably never exercised my brain so much in such a short span of time since undergrad exam crunch time.

Lastly, in case you are wondering, I am joining Facebook on Monday.

My Talk on Spark at AMPCamp 2012

I recently gave a talk about how Conviva uses Spark at AMPCamp 2012.  Spark has helped Conviva speed up online video data analysis by 30x.  My talk video is embedded below.

Java Concurrency in Practice - Summary

I recently read Java Concurrency in Practice by Brian Goetz.  It is a fantastic book.  Every Java programmer must read it.  In order to firmly internalize the concepts described in the book, I read it a second time and took down notes summarizing each chapter.  My notes were very popular when I was in school and college.  Hopefully, these notes will be useful to others as well.  

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it.

1. Part 1 - Introduction, Thread Safety
2. Part 2 - Sharing Objects
3. Part 3 - Composing Objects, Building Blocks
4. Part 4 - Task Execution
5. Part 5 - Cancellation & Shutdown
6. Part 6 - Applying Thread Pools
7. Part 7 - GUI Applications, Avoiding Liveness Hazards
8. Part 8 - Performance & Scalability, Testing Concurrent Programs
9. Part 9 - Explicit Locks, Building Custom Synchronizers
10. Part 10 - Atomic Variables & Non-blocking Synchronization,  Java Memory Model

Java Concurrency in Practice - Summary - Part 10

This is part 10 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 15 - Atomic Variables and non-blocking synchronization

1. Non-blocking algorithms use low-level atomic machine instructions like compare and swap (CAS) instead of locks to ensure data integrity under concurrent access.  An algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread.  An algorithm is called lock-free if some thread can make progress at each step.
2. Locking has many disadvantages.  For small operations like incrementing a counter, the overhead imposed by locking is just too much.
3. Almost every modern processor supports atomic Compare and Swap (CAS) instructions.  CAS atomically updates a memory location to a new value if the old value matches what we expect.  Otherwise it does nothing.  In either case, it returns the original value of the memory location.
1. CAS: "I think V should have the value A.  If it does put B there, otherwise don't change it but tell me I was wrong."
2. CAS is an optimistic technique - proceeds with update and detects collisions.
3. A thread that loses in CAS is not suspended.  It can choose to retry,  do some other recovery action or do nothing.
4. Primary disadvantage of CAS is that the caller must deal with contention.  Locking automatically deals with contention by blocking.
5. Rule of thumb : cost of uncontended lock acquisition and release is twice the cost of a CAS on a multi-processor system.
4. Atomic Variables
1. AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference
2. Elements in the atomic array classes (available in Integer, Long and Reference versions) can be updated atomically.  
3. Not good candidates for keys in hash based collections since they are mutable.
4. At low to moderate contention, Atomic variables provide better scalability.  At high contention, locks are better.
5. Refer the book for non-blocking stack and linked list code listing.
6. Atomic field updaters can be used to update existing volatile variables atomically.  Only to be used when there is a performance problem associated with creating multiple new Atomic* variables (like for each node of a linked list).
7. ABA problem - During an update, the value of a reference field can change from A to B and back to A.  In this case, we do not want the update to proceed.  But in regular CAS, it will.  This problem usually happens when we manage our own object pools.  One option to avoid this problem is to use versioned references with AtomicMarkedReference and AtomicStampedReference.

Chapter 16 - The Java Memory Model

1. A memory model is required because compilers can reorder instructions, store variables in caches instead of memory, etc.  Hence the result of assigning a value to a variable may not be immediately visible to another thread.  The Java Memory Model (JMM) specifies the minimal guarantees the JVM must make about when writes to variables become visible to other threads.
2. The JMM shields application developers from differences in memory models across different processor architectures.
3. Within a single thread, the JVM must maintain serial semantics.
4. Actions - reads/writes to variables, locks/unlocks, starting/joining threads.
5. The JMM defines a partial ordering called happens-before between actions:
1. Program rule order - Each action in a thread happens-before every subsequent action in that thread.
2. Monitor lock rule - An unlock on a monitor happens-before every subsequent lock on the same monitor lock.
3. Volatile variable rule - A write to a volatile variable happens-before every subsequent read of that same variable.
4. Thread start rule - A call to Thread.start happens-before every action in the started thread.
5. Thread termination rule - Any action in a thread happens-before any other thread detects that it has terminated (either by successfully returning from Thread.join or by Thread.isAlive() returning false).
6. Interruption rule - A thread calling interrupt() on another thread happens-before the interrupted thread detecting the interrupt.
7. Finalizer rule - The end of an object's constructor happens-before the start of its finalizer.
8. Transitivity - A happens-before B and B happens-before C implies A happens-before C.
9. Placing an item in a thread-safe collection happens-before another thread retrieves that item.*
10. Counting down on a CountdDownLatch happens-before a thread returns from await().
11. Releasing a permit to a Semaphore happens-before acquiring a permit from the same Semaphore.
12. A FutureTasks computation happens-before another thread successfully returns from Future.get().
13. Submitting a Runnable/Callable to an Executor happens-before the task begins execution.
14. A thread arriving at a CycleBarrier or Exchanger happens-before the barrier action, which happens-before threads are released from the barrier.
6. Piggybacking - advanced technique that uses an existing happens-before ordering to ensure visibility of an object X, rather than creating an happens-before relationship for publishing X.  Do not use unless absolutely necessary for performance.
7. Static initialization provides safe publication as static initializers are run by the JVM at class initialization time.  You can use static initialization lazily by using a private static holder class.
8. Double-checked locking - incorrect technique to avoid synchronization during lazy initialization.  First check if resource is non null without holding lock.  If non-null, just use it. If null, synchronize and initialize it.  The problem is that using the resource without any happens-before relationship can expose it in a partially constructed state.

Java Concurrency in Practice - Summary - Part 9

This is part 9 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it.

Chapter 13 - Explicit Locks

1. Unlike intrinsic locking, the Lock interface offers unconditional, polled, timed, and interruptible lock acquisition.
2. Lock implementations provide the same memory visibility guarantees as intrinsic locking.  They can vary in locking semantics, scheduling algorithms, ordering guarantees and performance.
3. ReentrantLock has same semantics as a synchronized block.
4. Why use explicit locks over intrinsic locks?
1. Unlike intrinsic locking, a thread waiting to acquire a ReentrantLock can be interrupted. 
2. ReentrantLock also supports timed lock acquisition.  
3. WIth intrinsic locks, a deadlock is fatal.
4. Intrinsic locks must be released in the same code block they are acquired in.  This makes non-blocking designs impossible.
5. ReentrantLock is much faster than intrinsic locking in Java 5.0
5. Lock objects are usually released in a finally block, to make sure that it is released if an exception is thrown.
6. lockInterruptibly() helps us build cancelable tasks.
7. tryLock() returns false if the lock cannot be acquired.  Timed tryLock() is also responsive to interruption.
8. ReentrantLock offers two fairness options
1. Fair - threads acquire locks in order of requesting.
2. Non-fair (default) - thread can acquire lock if it is available at the time of the lock request, even if earlier threads are waiting.  Non-fair locking is useful because it avoids the overhead of suspending/resuming a thread if the lock is available at time of the lock request.  
3. Fairness is usually not needed, and has a very high performance penalty (multiple orders of magnitude).
4. Fair locks work best when they are held for a relatively long time or when the mean time between lock requests is large.
9. When to use intrinsic locks?
1. synchronized blocks have a more concise syntax.  You can never forget to unlock a synchronized block.
2. Use ReentrantLock only when advanced features like timed, polled, interruptible lock acquisition, fairness or non-block structured locking are needed.
3. Harder to debug deadlock problems when using ReentrantLock because lock acquisition is not tied to a particular stack frame, and thus the stack dump is not very helpful.
4. synchronized is likely to have more performance improvements in the future (eg: lock coarsening) as it is part of the Java language spec.
10. Read-Write Lock - protected resource can be accessed by multiple readers or one writer at the same time.
1. offers readLock() and writeLock() methods which return a Lock object that must be acquired before doing the respective operations.
2.  More complex implementation.  Hence has lower performance except in read-heavy workloads.
11. Lock can only be released by thread that acquired it.

Chapter 14 - Building Custom Synchronizers

1. State-dependent classes - blocking operations can proceed only if state-precondition becomes true (for example, you cannot retrieve result of FutureTask if computation has not yet finished).
2. Try to use existing state-dependent classes whenever possible. 
3. Condition queue - allows a group of threads (called wait set) to wait for a specific condition to become true.
4. Intrinsic condition queues - Any java object can act as a condition queue via the Object.wait(), notify() and notifyAll() functions.
1. Must hold intrinsic lock on an object before you can call wait(), notify() or notifyAll().   
2. Calling Object.wait() atomically releases lock and suspends the current thread.  It reacquires the lock upon waking up, just before returning from the wait() function call.   wait() blocks till thread is awakened by a notification, a specified timeout expires or the thread is interrupted.
3. In order to use condition queues, we must first identify and document the pre-condition that makes an operation state-dependent.  The state variables involved in the condition must be protected by the same lock object as the one we wait() on.
4. A single intrinsic condition queue can be used with more than one condition predicate.  This means that when a thread is awakened by a notifyAll, the condition it was waiting on need not be true.  wait() can even return spuriously without any notify().  The condition can also become false by the time wait() reacquires the lock after waking up.  Hence when waking up from wait(), the condition predicate must be tested again and we must go back to waiting if it is false.  Hence, call wait() in a loop: synchronized(lockObj) { while(!conditionPredicate()) { lock.wait();} // object is in desired state now
5. Notifications are not sticky - i.e. a thread won't know about notifications that occurred before it called wait().
6. In order to call notify() or notifyAll() on an object, you must hold the intrinsic lock on that object.  Unlike wait(), the lock is not automatically released.  The lock must be manually released soon as none of the woken up threads can make progress without acquiring the lock.
7. Use notifyAll() instead of notify().  If multiple threads are waiting on the same condition  queue for different condition predicates, calling notify() instead of notifyAll() can lead to missed signals, as only the wrong thread may be woken up.
1. However using notifyAll() can be very inefficient, as multiple threads are woken up and contend for the lock where only one of them can usually make progress.
2. notify() can be used only if 
1. The same condition predicate is associated with the condition queue and each thread executes the same logic on returning from wait().
2. A notification on the condition queue enables at most one thread to proceed.
8. A bounded buffer implementation needs to call notify only when moving away from the empty state or full states.  Such conditional notifications are efficient, but makes the code hard to get right.  Hence, avoid unless necessary as an optimization.
9. A state dependent class should either fully document its waiting/notification protocols to sub-classes or prevent sub-classes from participating in them at all.
10. Encapsulate condition queue objects in order to avoid external code from incorrectly calling wait() or notify() on them.  This often implies the usage of a private lock object instead of using the main object itself.
11. Explicit Condition objects - Condition 
1. Each intrinsic lock can have only one associated condition queue.  Hence multiple threads may wait on same condition queue for different condition predicates.
2. A Condition is associated with a single Lock object.   A Condition is created by calling Lock.newCondition().  You can create multiple Condition objects per Lock.
3. Equivalents of wait(), notify() and notifyAll() for Condition are await(), signal() and signalAll().  Since Condition is an Object, wait() and notify() are also available. Do not confuse them.
4. Explicit Condition objects make it easier to use signal() instead of signalAll().
12. Synchronizers
1. Both Semaphore and ReentrantLock extend AbstractQueuedSynchronzer (AQS) class.
2. AQS is a framework for building locks and synchronizers.
3. When using AQS, there is only one point of contention.
4. Acquisition - state dependent operation that can block.
5. Release - allows some threads blocked in acquire to proceed.  Not-blocking
13. AQS manages a single integer of state for the synchronizer class. It can be accessed with getState(), setState() and compareAndSetState() methods.  The integer can represent arbitrary semantics.  For example, FutureTask uses it to represent the state (running, completed, canceled) of the task.  Semaphore uses it to track the number of permits remaining.
1. Synchronizers track additional state variables themselves.
2. Synchronizers override tryAcquire, tryRelease, isHeldExclusively, tryAcquireShared and tryReleaseShared.  The acquire, release, etc methods of AQS call the appropriate try methods,

Java Concurrency in Practice - Summary - Part 8

This is part 8 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 11 - Performance and Scalability

1. Avoid premature optimization - first make it right, then make it fast, if not fast enough already (as indicated by actual performance measurements)
2. Tuning for scalability is often different from tuning for performance, and are often contradictory.
3. Amdahl's Law : Speedup <= 1/( F + (1-F)/N) where F is the fraction of computation that must be executed serially, and N is the number of processors.
4. A shared work queue adds some (often overlooked) serial processing.  Result handling is another form of serialization hidden inside otherwise seemingly 100% concurrent programs.
5. Costs of using threads
1. context switches - managing shared data structures in OS and JVM take memory and CPU. Can also cause flurry of processor cache misses on a thread context switch.
2. When a thread blocks on a lock, it is switched out by JVM before reaching its full scheduled CPU quantum, leading to more overhead.
6. Context switching costs 5000-10000 clock cycles (few microseconds).  Use vmstat to find % of time program spent in the kernel. High % can indicate high context switching.
7. synchronized and volatile result in the use of special CPU instructions called memory barriers that involve flushing/invalidating CPU caches, stalling execution pipelines, flushing hardware write buffers, and inhibit compiler optimizations as operations cannot be reordered.
8. Performance of contended and uncontended synchronization are very different.  synchronized is optimized for the uncontended scenario (20 to 250 clock cycles).  volatile is always uncontended. 
9. Modern JVMs can optimize away locking code that can be proven to never contend.
10. Modern JVMs perform escape analysis to identify thread-confined objects and avoid locking them.
11. Modern JVMs can do lock coarsening to merge multiple adjacent locks into a larger lock to avoid multiple lock/unlocks.
12. Synchronization by one thread affects performance of other threads due to traffic on the shared memory bus.
13. Uncontended synchronization can be handled entirely in JVM.  Contended synchronization involves OS activity - OS needs to suspend the thread that loses the contention.  
14. Blocking can implemented by spin-waiting or by suspending the thread via the OS.  spin-waiting is preferred for short waits.  JVM decides what to use based on profiling past performance.
15. Reducing lock contention
1. reduce duration for which locks are held.
2. reduce frequency at which locks are requested. Coarsen lock granularity by lock splitting (for moderately contended locks) and lock striping (for heavily contended locks).
3. replace exclusive locks with coordination mechanisms that permit greater concurrency.
16. Lock striping - ConcurrentHashMap uses 16 locks - bucket N is guarded by lock N % 16.  Locking for exclusive access to entire collection is hard when lock striping is used.
17. Avoid hot fields like cached values - for eg: size is cached for a Map, in order to convert an O(n) operation to a O(1) operation.  Use striped counters or atomic variables.
18. Alternatives to exclusive locks - concurrent collections, read-write locks, immutable objects, atomic variables.
19. Do not use object pools.  Object allocation and GC were slow in earlier versions of Java.  Now object allocation is faster than a C malloc - only 10 machine instructions.  Object pools also introduce synchronization overheads

Chapter 12 - Testing Concurrent Programs

1. Every test must wait till all the threads created by it terminate.  It should then report any failures in tearDown().
2. Testing blocking operations need some way to unblock a thread that has blocked as expected.  This is usually done by doing the blocking operation in a new thread and interrupting it after waiting for some time.  An InterruptedException is thrown if the operation blocked as expected.
3. Thread.getState() should not be used for concurrency control or testing.  Useful only for debugging.
4. One approach to test producer-consumer programs is to check that everything that is put into a queue or buffer eventually comes out of it, and nothing else does.  
1. For single producer-single consumer designs, use order sensitive checksum of elements that are added, and verify them when the element is removed.  Do not use a synchronized shadow list to track the elements as that will introduce artificial serialization.
2. For multiple producer-consumer designs, use an order insensitive checksum that can be combined at the end of the test to verify that all enqueued elements have been dequeued.
1. Make sure that the checksums are not guessable by the compiler (for eg: consecutive integers), so that they are not precomputed.  Use a simple random number generator like  xorShift(int y) { y ^= (y << 6); y ^= (y >>> 21); y ^= (y << 7); return y;}
5. Test on multi-processor machines with fewer processors than active threads.
6. Generate more thread interleaving by using Thread.yield() to encourage more context switches during operations that access shared state.  
7. Always include some basic functionality testing when doing performance testing to make sure that you are not measuring performance of broken code.
8. Non-fair semaphores provide better throughput, while fair semaphores provide lower variance in responsiveness.
9. Avoiding performance testing pitfalls
1. Ensure that garbage collection does not run at all during your test (check this using the -verbose:gc flag) OR ensure that garbage collection runs a number of times during the test (need to run test for a long time).
2. Your tests should run only after all code has been compiled; no point measuring performance of interpreted byte code.  Dynamic compilation takes CPU resources.  Compiled code executes much faster.
1. Code may be decompiled/recompiled multiple times during execution - for eg: if some previous assumption made by JVM is invalidated, or to compile with better optimization flags based on recently gathered performance statistics.
2. Run program long enough (several minutes) so that compilation and interpreted execution represent a small fraction of the results and do not bias it.
3. Or have an unmeasured warm-up run before starting to collect performance statistics.
4. Run JVM with -XX:+PrintCompilation so that we know when dynamic compilation happens.
3. When running multiple unrelated computationally intensive tests in a single JVM, place explicit pauses between tests in order to give the JVM a chance to catch up with its background tasks.  Don't do this when measuring multiple related activities, since omitting CPU required by background tasks gives unrealistic results.
4. In order to obtain realistic results, concurrent performance tests should approximate the thread-local computation done by a typical application.  Otherwise, there will be unrealistic contention.
5. Make sure that compilers do not optimize away benchmarking code.  
1. Trick to make sure that benchmarking calculation is not optimized away:  if (fox.hashCode() == System.nanoTime()) System.out.print(" ");
10. Complementary Testing Approaches
1. Code Review
2. Static analysis tools: FindBugs has detectors for:
1. Inconsistent synchronization.
2. Invoking Thread.run (Thread.start() is what is usually invoked, not Thread.run())
3. Unreleased lock
4. Empty synchronized block
5. Double-checked locking
6. Starting a thread from a constructor
7. Notification errors
8. Condition wait errors: Object.wait() or Condition.await() should be called in a loop with the appropriate lock held after testing some state predicate.
9. Misuse of Lock and Condition
10. Sleeping or waiting while holding a lock.
11. Spin loops

Java Concurrency in Practice - Summary - Part 7

This is part 7 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 9 - GUI Applications

1. Almost all GUI toolkits, including Swing, are implemented as a single-threaded subsystem.  All GUI activity is confined to a single dedicated event dispatch thread.  Attempts at multi-threaded GUIs suffered from deadlocks and race conditions.  User actions manifest as events that bubble up from the GUI component to the application.  Application initiated actions bubble down from the application code to the GUI components.  Hence, GUI components are often accessed in opposite order, creating ripe conditions for deadlocks.
2. Tasks that execute in the event thread must complete quickly.  Otherwise the UI will hang.
3. In Swing, GUI objects are kept consistent not by synchronization, but by thread confinement.  They must NOT be accessed from any other thread.
4. A few Swing methods are thread-safe:
1. SwingUtilities.isEventDispatchThread
2. SwingUtilities.invokeLater - schedules a Runnable to be executed on the event thread.
3. SwingUtilities.invokeAndWait - callable only from a non-GUI thread.  Schedules Runnable to be executed on GUI thread and waits for it complete
4. methods to enqueue a repaint or revalidate request on the event queue.
5. methods for adding/removing event listeners.
5. Short-running tasks can be run directly on the GUI thread.  For long running tasks, use Executors.newCachedThreadPool().
6. Use Future, so that tasks can be easily cancelled.  The task must be coded so that it is responsive to interruption.
7. SwingWorker class provides support for cancellation, progress indication, completion notification.  So, we don't have to implement our own using FutureTask and Executor.
8. Data models must be thread-safe if they are to be accessed from the GUI thread.
9. A program that has both a presentation-domain and an application domain data model is said to have a split-model design.
1. presentation data model is confined to event thread.  Application domain data model is thread-safe and is shared between the application and GUI threads.
2. presentation model registers listeners with the application model so that it can be notified of updates.  Presentation model can be updated from the application model by sending a snapshot of the current state or via incremental updates.

Chapter 10 - Avoiding Liveness Hazards

1. Unlike database systems, JVM does not do deadlock detection or recovery
2. A program will be free of lock-ordering deadlocks if all threads acquire the needed locks in a fixed global order.
1. The order of locks acquired by a thread may depend on external input. Hence static analysis alone is not sufficient to avoid lock-ordering deadlocks.
2. An alternative is to induce an ordering on locks by using System.identityHashCode.  Order lock acquisition by the hash code of the lock object.
1. In the extremely unlike scenario where the hash codes of two lock objects are equal, acquire a third "tie" lock before trying to acquire the original two locks.  The tie lock can be a global lock.  Since hash collisions are infrequent, the tie lock won't introduce a concurrency bottleneck.
3. If the lock objects (say bank Accounts) have a unique key, lock acquisition can be ordered by the key, and there is no need for the tie-lock.
4. Multiple locks may not always acquired in the same method.  Hence, it is not easy to detect lock-ordering deadlocks.  Watch out for invocation of alien methods while holding a lock.
3. Calling a method with no locks held is called an open call.  Liveness of a program can be more easily analyzed if all calls are open.
4. Use synchronized blocks within methods to guard shared state, instead of making the entire method synchronized.
1. In cases where loss of atomicity of the synchronized method is unacceptable, we need to construct application level protocols.  For example, when shutting down a service, lock for just long enough to mark the service as shutting down, and wait for existing tasks to complete without holding the lock. Since the service is marked as shutting down, no new tasks will start.
5. In addition to deadlocking waiting for locks, threads can also deadlock waiting for resources like database connections.
6. If you must acquire multiple locks, lock ordering must be part of your design. Minimize number of locks needed.  Document ordering policy.
7. Timed locks offered by the Lock class are another option for detecting and recovering from deadlocks.  The tryLock() method returns failure if timeout expires.  It can return failure even if no deadlock occurred, but the thread just took a long time due to some other reason.
8. JVM prints out deadlock information in thread dumps.  To trigger a thread dump, send SIGQUIT (kill -3) to the JVM.  Explicit Lock objects are not clearly shown in a thread dump.
9. Starvation - a thread is perpetually denied access to needed resources.
1. CPU cycle starvation can be caused by inappropriate use of thread priorities, or by executing infinite loops with locks held.
2. Avoid setting thread priorities as they are platform-dependent and can cause liveness issues.  Set lower priorities only for truly background tasks, that can improve the responsiveness of foreground tasks.
10. Livelock - thread is not blocked, but cannot make progress because it keeps retrying an operation that will always fail.  For example, when a code bug is triggered when processing a particular input, and that input is re-queued for processing by over-eager error handling code.  An unrecoverable error is being mistakenly being treated as a recoverable one.  Solution for some forms for livelocks is to introduce randomness into the retry.

Java Concurrency in Practice - Summary - Part 6

This is part 6 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 8 - Applying Thread Pools

1. In the Executor framework, there is an implicit coupling between tasks and execution policies.  Not all tasks are compatible with all execution policies.
2. If a task depends on the results of other tasks, then the execution policy must be carefully managed to avoid liveness problems.  Deadlocks can happen if the thread pool is bounded, i.e. thread starvation deadlock.
1. Will always deadlock if using Executors.newSingleThreadExecutor().
2. Other resources like JDBC connections may also be a bottleneck.
3. Document any pool sizing or configuration constraints.
3. Tasks that rely on thread confinement for thread-safety will not work well with thread pools.
4. Responsiveness of time-sensitive tasks may be bad if we use a single thread executor or if we submit several long running tasks to a small thread pool.  Use timed resource waits instead of unbounded waits.
5. Tasks that use ThreadLocal cannot be used with the standard Executor implementation as Executors may reuse or kill threads.  Do not use ThreadLocal to communicate value between tasks.
6. For compute-intensive tasks, an Ncpu-processor system achieves optimum utilization with a thread pool of Ncpu + 1 threads.  For tasks that include I/O or other blocking operations, use a larger thread pool since not all threads will be schedulable at all times.
7. ThreadPoolExecutor is the base class of executors returned by Executors.newCachedThreadPool, newFixedThreadPool and newScheduledThreadExecutor.  It is highly configurable.
8. We can specify the type of BlockingQueue that holds tasks awaiting execution.
1. unbounded LinkedBlockingQueue is the default for newFixedThreadPool and newSingleThreadExecutor.
2. Another option is to use a bounded LinkedBlockingQueue, ArrayBlockingQueue or PriorityBlockingQueue.
3. SynchronousQueue - not really a queue.  It is a mechanism for managing handoffs between threads.  Another thread must be waiting to accept handoff  - if pool maximum size has not been reached a new thread is created.  If no thread is available, the task is rejected.   Handoff is more efficient as we don't have to place the Runnable in an Queue. newCachedThreadPool uses a SynchronousQueue
9. newCachedThreadPool is a good default choice for an Executor.
10. Saturation Policy for a ThreadPoolExecutor can be modified by calling setRejectedExecutionHandler().
1. abort - causes execute() to throw the unchecked RejectedExecutionException.  Caller catches this exception and implements its own overflow handling.  This is the default.
2. discard - silently discard the newly submitted task.
3. discard-oldest - discard tasks that would be executed next and tries to resubmit the new task.
4. caller-runs - Tries to slow down the flow of new task submission by pushing some of the work to the caller.  It executes the newly submitted task not in a pool thread, but in the thread that calls execute().
5. There is no predefined saturation policy to make execute() block when the work queue is full.  However, this can be achieved using a Semaphore to bound the task injection rate. 
11. Thread Factories - whenever a thread pool needs to create a thread, it uses a thread factory.  ThreadFactory.newThread() is called whenever a thread pool needs to create a new thread.  Default thread factory creates a new non-daemon thread with no special configuration.  Use a custom thread factory to to specify an UncaughtExceptionHandler for pool threads, or instantiate an instance of a custom Thread class that does debug logging, or give pool threads more meaningful names.
12. Most ThreadPoolExecutor options can be changed after construction via setters.  Executors.unconfigurableExecutorService wraps an existing ExecutorService to ensure that its configuration cannot be changed further.  newSingleThreadExecutor() returns such a wrapped Executor rather than a raw ThreadPoolExecutor.  This is because newSingleThreadExecutor is implemented as a thread pool with one thread, and no one should be able to increase the pool size.
13. ThreadPoolExecutor was designed for extension.
1. beforeExecute and afterExecute hooks are called in the thread that executes the task.  Used for logging, timing, monitoring, statistics gathering.  Use ThreadLocal to share values between beforeExecute and afterExecute.
2. afterExecute is not called if task completes with an Error (regular exception is okay)
3. If beforeExcute throws a RuntimeException, the task is not executed and afterExecute() is not called.
4. terminated hook is called after the thread pool has shutdown - all tasks have finished and all worker threads have shut down.  Useful for releasing resources allocated by the Executor, notification, logging, finalize statistics gathering.
14. Parallelizing recursive algorithms
1. Sequential loops are suitable for parallelization when each iteration is independent of others, and the work done in each iteration is significant to offset cost of task creation.
2. Sequential loops within recursive algorithms can be parallelized.  Easier if iteration does not need value of recursive iterations it invokes.
3. In order to wait for all results, create a new Executor,  schedule the parallel tasks, call executor.shutdown() and then awaitTermination().

Java Concurrency in Practice - Summary - Part 5

This is part 5 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 7 - Cancellation & Shutdown

1. Java does not provide any mechanism for safely forcing a thread to stop what it is doing.  Instead, we need to rely on interruption where a thread can request another thread to stop.  The thread to be stopped may choose to ignore the request or can terminate after optionally performing cleanup operations.
2. Don't use the deprecated Thread.stop() and suspend() methods.
3. A task is cancelable if some external code can move it to a completed state before its normal completion. A task that supports cancellation must specify its cancellation policy:
1. how external code can request cancellation
2. responsiveness guarantees to cancellation requests
3. what happens on cancellation (such as cleanup operations)
4. One cooperative mechanism for terminating a task is to use a cancellation requested flag which the task periodically checks.  If the flag is set by some external code, then the task terminates early.  Remember to make the cancellation requested flag volatile.  Otherwise changes made by the external code may never become visible to the task.
1. The thread will exit only when it checks the cancellation flag.  Hence there is no guarantee on if and when the check will be made.
2. Can take a very long time to take effect (if at all) if the thread to be cancelled is stuck at a blocking operation.
5. Interruption Is usually the most sensible way to implement cancellation
6. Each thread has a boolean interrupted status, which is set to true when a thread is interrupted.
1. interrupt() interrupts the target thread
2. isInterrupted() returns the interrupted status of the target thread
3. interrupted() clears the interrupted status of the current thread and returns its previous value.  This is the only way to clear the interrupted status of a thread.  Poor choice of function name.
7. Blocking library calls try to detect when a thread has been interrupted and return early.  They clear the interrupted status and throw an InterruptedException.  There is no guarantee about how quickly a blocking method will detect interruption.  In practice, it happens fairly quickly.  When a thread that is not blocked is interrupted, its interrupted status is set.  It is upto the activity being cancelled to poll the interrupted status and respond appropriately. 
1.  A task does not need to immediately stop on detecting the interrupted status.  It can postpone acting on the interruption till a more opportune moment.  This can prevent internal data structures from being corrupted when interrupted in the middle of some critical operations.
8. There is a distinction between how tasks and threads react to interruption.  An interrupt on a worker thread in a thread pool can cancel the current task as well as shut down the worker thread. Hence, guesT code that doesn't own a thread must preserve the interrupted status of the thread after acting on the interrupt, so that the owner can appropriately deal with it later.
9. A thread should be interrupted only by its owner.  Because each thread has its own interruption policy, you should not interrupt a thread unless you know what interruption means to that thread.
10. Responding to interruption
1. Propagate the interruptedException, OR
2. Restore the interrupted status by calling Thread.currentThread.interrupt().  This is the only feasible solution in cases like Runnable.run() which does not allow exceptions to be thrown.
3. Only code that implements a thread's interruption policy may swallow an interruption request.  General purpose task and library code must never swallow interruption requests.
11. Activities that do not support cancellation but still call interruptible blocking methods must call them in a loop, retrying when interruption is detected.  The interruption status should be saved locally and restored before returning. Restoring the interrupted status immediately can result in an infinite loop.
12. Cancellation via Future
1. Future.cancel(boolean mayInterruptIfRunning)  - if mayInterruptIfRunning is true and the task is running in some thread, then that thread is interrupted.  If false, cancel() only means that don't run this task if it hasn't started yet.
2. Standard Executor implementation implement a thread interruption policy that allows tasks to be canceled through interruption.  Hence, it is ok to call Future.cancel(true) which interrupts the thread.
3. You should not interrupt a pool thread directly when attempting to cancel a task because you won't know what task is running at the time the interrupt is delivered. Cancel only through the task's Future.
4. When Future.get() throws an InterruptedException or TimeoutException and you know that the result is no longer required, cancel the task by calling Future.cancel().
13. Dealing with non-interruptile blocking
1. synchronous socket I/O in java.io - read/write in InputStream and OutputStream are not responsive to interruption, but closing the underlying socket makes any threads blocked in read/write to throw a SocketException.
2. Synchronous I/IO in java.nio - Interrupting a thread waiting on an InterruptibleChannel causes it to throw ClosedByInterruptionException and close the channel.  Closing an InterruptibleChannel cause threads blocked on channel operations to throw AsynchronousCloseException.
3. Asynchronous IO with Selector - A thread blocked in Selector.select() returns prematurely if close() or wakeup() is called.
4. Lock acquisition - A thread waiting for an intrinsic lock cannot be interrupted.  Explicit Lock class offers the lockInterruptibly method.
5. To perform non standard cancellation tasks (like closing a socket), override newTaskFor() in ThreadPoolExecutor to return a CancellableTask. CancellableTask extends Callable and overrides the FutureTask.cancel() method to close socket or perform any other nonstandard cancellation tasks.
14. Stopping a thread-based service
1. A thread pool owns the worker threads, and should be responsible for stopping them.  It should provide lifecycle methods that can be used by the application to shut down the pool, which in turn shuts down the worker threads.
15. ExecutorService provides shutdown() and shutdownNow(). shutdownNow() returns the list of tasks that had not started, so they can be logged or saved for future processing.  The returned Runnable objects may not be the same as what was submitted - they may be wrapped.
1. shutdownNow() provides no way of knowing the state of tasks in progress at shutdown time, unless the tasks themselves do checkpointing. Another option is to override execute() of AbstractExecutorService and pass in a wrapper Runnable that records tasks cancelled at shutdown.  There is a race condition that may cause a completed task to be marked as cancelled.  So tasks must be idempotent.
16. Poison Pill - a special object placed on the work queue is another way to convince a producer-consumer service to shut down.  Applicable only when the number of consumers and producers is known, and when the queue is unbounded.
17. Handling abnormal thread termination
1. Leading cause of premature thread death is RuntimeException.  If nothing special is done, the exception bubbles all the way up the stack and the thread is killed after printing a stacktrace to the console (which no one may be watching for)
2. If you are writing a worker thread class for a thread pool or executor service, be sure to catch Throwable and then notify the executor service of premature thread death.
3. Thread API provides an UncaughtExceptionHandler facility - when a thread exits due to an uncaught exception, the JVM reports this to an application provided UncaughtExceptionHandler.  Use Thread.setUncaughtExceptionHandler() to set the handler for the current thread or Thread.setDefaultUncaughtExceptionHandler to set it for all threads.
4. In long-running applications, always use uncaught exception handlers for all threads that at least log the exception.
5. To set an UncaughtExceptionHandler for pool threads, provide a ThreadFactory to the ThreadPoolExecutor.  Exceptions thrown from tasks make it to the UncaughtExceptionHandler only for tasks submitted with execute().  For those submitted with submit(), the exceptions are rethrown when calling Future.get()
18. JVM Shutdown
1. orderly shutdown - when the last nondaemon thread exits, System.exit(), Ctrl-C
2. abrupt shutdown - Runtime.halt(), SIGKILL the JVM
3. In orderly shutdown, JVM starts all shutdown hooks registered while Runtime.addShutdownHook(). Order of shutdown hook execution is not guaranteed.
4. After all shutdown hooks have completed, JVM may choose to run finalizers if runFinalizersOnExit is true,
5. JVM makes no attempt to stop or interrupt any application threads that are still running.
6. Shut-down hooks can run concurrently with other application threads.  So, they must be thread-safe.  Since JVM is shutting down, the application state may be messy. Hence the shut-down hooks must be coded extremely defensively.
7. Shut-down hooks should not use services that can be shutdown by the application or by other shutdown hooks.  One option is to use a single shutdown hook per application that executes various shutdown operations in sequence.
19. Daemon threads - existence of a Daemon thread does not prevent JVM from shutting down.  Internal JVM threads like GC thread are daemon threads.  When JVM exits, finally blocks of any existing daemon threads are not run.
1. Should be used sparingly, for activities that can be safely abandoned at any time without any cleanup.  
2. Do not use daemon threads for any tasks that perform I/O.
3. Generally used for housekeeping tasks like a background thread to remove expired cache entries.
20. Finalizers
1. GC treats objects that have a non-trivial finalize() method specially. finalize() is called after the memory is reclaimed.
2. Finalizers can run concurrently with application threads.  Hence, they must be thread-safe.
3. No guarantee about if or when they will run.
4. HIgh performance cost.
5. Usually, finally blocks and explicit close statements are sufficient to release resources, instead of using finalize().  
6. finalizers may be needed for objects that hold resources acquired by native methods.
7. Avoid finalizers

Java Concurrency in Practice - Summary - Part 4

This is part 4 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 6 - Task Execution

1. Individual client requests are a natural task boundary choice for server applications.
2. Creating a new thread per task is usually NOT a good idea.
1. Overheads of thread creation and teardown can add up to be quite significant.
2. Active threads consume system resources like memory even when they are idle, and also increase CPU contention.
3. Creating too many threads can result in an OutOfMemoryError.
3. Primary abstraction for task execution in Java is the Executor framework, not Threads.
1. Executor interface has a void execute(Runnable) methods.
4. Executors are the easiest way to implement a producer-consumer design.
5. Decouples task submission from execution.  Execution policy is separated from task submission.
6. Always use Executor instead of new Thread(runnable).start()
7. Different types of Thread Pools can be created using static factory methods of the Executors class:
1. newFixedThreadPool - creates new threads upto a maximum specified size.  Tries to keep pool size constant by adding new threads if some die due to  exceptions.
2. newCachedThreadPool - No bounds on number of threads.  Number of threads increase/decrease based on load.
3. newSingleThreadExecutor - Used to process tasks sequentially in order imposed by task queue (FIFO, LIFO, priority order).  Replaces thread if it dies unexpectedly.
4. newScheduledThreadPool - Fixed size thread pool that supports delayed and periodic task execution.
1. Use instead of Timer.
1. Timer creates only a single thread.  If one task takes too long, it affects the timing accuracy of subsequent TimerTasks.
2. An unchecked exception thrown by a TimerTask terminates the Timer thread.  The Timer thread is not resurrected, and the Timer is simply cancelled.
3.  Scheduled thread pools do not have the above two limitations  However,  Timers can schedule based on absolute time, while scheduled thread pools only support relative time.
8. Executor lifecycle has 3 states - running, shutting down, terminated.
9. ExecutorService interface (that extends Executor) offers methods like shutdown(), shutdownNow(), isShutdown(), isTerminated(), awaitTermination() to control Executor life cycle.
1. shutdown() - graceful shutdown.  Allow all running and previously submitted tasks to complete.  No new tasks are accepted.
2. shutdownNow() - cancel running tasks, and ignores any queued tasks.
3. Tasks submitted to executor after shutdown are passed to a rejection handler, which may silently drop the task or throw a RejectedExecutionException.
4. awaitTermination() is usually called immediately after calling shutdown().
10. ExecutorService.submit(Callable) returns a Future. A  Future represents the lifecycle of a task, and provides methods to monitor/control it.
11. CompletionService combines the functionality of an Executor and a BlockingQueue.  Submit a bunch of Callables to the Executor, and then wait for the results to be available using take() and poll().
1. An ExecutorCompletionService is a wrapper around an Executor - new ExecutorCompletionService(executor).
2. Tasks are submitted to the completion service, and not directly to the Executor.
3. Multiple completion services can share an Executor.
4. Keep track of the number of tasks submitted in order to determine the number of times to call take().
12. Future.get() supports a version that throws a TimeoutException if the result is not available within the specified time delay.
1. If a TimeoutException happens, then call cancel on the Future to cancel the task.  If the task is written to be cancelable, then it can be terminated to avoid consuming unnecessary resources.
13. ExecutorService.invokeAll - takes a collection of tasks and returns a collection of Futures.  Timed version of invokeAll returns when all tasks have completed, the calling thread is interrupted or if the timeout expires.  Use Future.isCancelled() to determine if a particular task completed or was interrupted/cancelled.

Java Concurrency in Practice - Summary - Part 3

This is part 3 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 4 - Composing objects

1. We often create thread-safe objects by composing together other thread-safe objects. In order to design a thread-safe class, we need to identify the object's state variables, establish invariants that constraint them and the post conditions associated with its method,  and then establish a policy for managing concurrent access to them.
1.  An object's state includes the state of other objects referenced from its state variables.  For eg: a LinkedList's state includes all the link node objects.
2. Synchronization policy - how an object uses immutability, thread-confinement, locking (how and which variables are guarded by which locks) to coordinate access to its state variable so that the invariants or post conditions are not violated.
3. Encapsulation enables us to determine that a class is thread-safe without having to examine the entire program, because all paths that use the data can be identified and made thread-safe.
1. Collection wrappers like synchronizedList make the underlying non-thread-safe ArrayList thread-safe by using encapsulation.
4. Java monitor pattern - object encapsulates all state and guards it with its own intrinsic lock.
1. Pro: Simplicity.
2. Con: External code can lock on the object's intrinsic lock and cause liveness problems that may require examining the whole program to debug.  This problem is avoided if a separate private object is used as the lock.
5. A composite object made of thread-safe components need not be thread-safe.  This is usually the case when there are constraints on the state of the components.
6. A state variable can be published if it is thread-safe, does not participate in any invariants that constrain its value and has no prohibited state transitions for any of its operations.
7. Re-use existing java thread-safe libraries whenever possible.  To add-functionality to an existing thread-safe class: 
1. The best option is to modify the source code of the class if available.  
1. Pro: details about synchronization policy are confined to one file, and is thus easier to maintain.
2. If modifying source code is not possible, the next best option is to extend the class, assuming it was designed for extension. 
1. Con: Fragile.  If base class changes synchronization policy (say which locks are used), then the extended class will silently fail.
3. Extension or source modification is not possible for collections wrapped in Collections.synchronized* wrappers, since the underlying wrapped class is unknown.  The solution is to use client-side locking - guard client code with the lock specified by the object's synchronization policy.  For Vector, the lock is the object itself.
4. Another option is Composition.  In a wrapper object, maintain a private internal copy of the object (say List) whose functionality we wish to extend.   Add the new functionality as a synchronized method of the wrapper.  Add synchronized methods for existing functionality of the wrapped object that simply delegate to the underlying object.
1. Pro: Less fragile
2. Con: Minor overhead due to double locking.
8. Document a class's thread-safety guarantees for users of the class; Document its synchronization policy for the class's maintainers.
1. Use @GuardedBy annotations to document the locks used to guard different state variables.
2. Since documentation for commonly used Java libraries is vague, we often have to guess whether a class is thread-safe or not.  For example, since a JDBC DataSource represents a pool of reusable database connections to be shared across multiple threads, we can assume that it is thread-safe.  However, individual JDBC Connection objects are intended to be used by a single thread, and are most likely not thread-safe.

Chapter 5: Building Blocks

1. Java offers a wide variety of thread-safe classes that can serve as building blocks for large concurrent programs.  
2. External locking is still required for thread-safe classes in order to provide a 'reasonable' behavior.  
3. Unreliable Iteration is one example where additional synchronization is required.  For example, using getLast() and deleteLast() on a thread-safe List requires additional synchronization.  If getLast() determines the index of the last element to be L and the element at L is deleted by deleteLast() before getLast() accesses it, an ArrayOutOfBoundsException will be thrown.   Otherwise, an ArrayOutOfBounds exception may be thrown if the last element of the list is deleted after getLast() determined the index of the last element to be returned.  Note that the data in the List is never corrupted, we just get unexpected behavior.
1. Java Iterators throw an unchecked ConcurrentModificationException if it detects that the underlying collection has changed during iteration. This is not reliable as the counters used to track whether the underlying collection has changed are not thread-safe.
2. Iterators can sometimes be hidden - For eg: an iterator is used if a collection object is passed to a log statement which tries to get its string representation.
3. Unreliable iteration can be solved by client-side locking.  When using the synchronized wrappers provided by Java, we can use the underlying collection as the lock for composite actions. Con: Decreases scalability.
4. Another option to avoid concurrent modification exception is to clone the collection as a local copy.  The lock on the collection must be held while cloning.  Con: Can be very expensive to clone large collections.
5. To avoid client-side locking during iteration, use the Concurrent collections offered by Java.  This improves scalability as multiple threads can now access the collections simultaneously without blocking
4. ConcurrentHashMap
1. HashMap uses a single lock to synchronize all its operations.
2. ConcurrentHashMap uses lock-striping.  Supports concurrent non-blocking access by infinite number of readers, and a limited number of writers.
3. Iterators do not throw ConcurrentModificationException.
4. size() and isEmpty() are approximate.  These methods are not useful in concurrent environments anyway.
5. Cannot lock the entire map for synchronized access, needed in rare cases where multiple map entries need to be added atomically.
6. Cannot use client-side mapping while adding new atomic operations.  If these are needed, you most likely need ConcurrentMap instead of ConcurrentHashMap.
5. CopyOnWriteArrayList 
1. Thread-safety derived from the immutability of underlying list.  Mutability is provided by creating and republishing a new copy of the list on every change.  Iterators point to the list at the time the iterator was created.
2. Copying large lists can be expensive.  Hence mainly useful when iteration is the more common operation rather than addition - for eg: when using a list of event listeners.
6. Some more concurrent collections - CopyOnWriteArraySet, ConcurrentLinkedQueue, ConcurrentSkipListMap - concurrent replacement for synchronized SortedMap, ConcurrentSkipListSet - concurrent replacement for synchronized SortedSets
7. Java offers multiple Queue implementations (esp. BlockingQueue) that can be very useful to implement producer-consumer designs.  Queues can be blocking or non-blocking.  For non-blocking queues, .retrieval operations return null if queue is empty.
8. BlockingQueue
1. blocking methods : take, put (blocking happens only if queue is bounded)
2. non-blocking methods: offer, poll
3. Use bounded blocking queues for reliable resource management.  Otherwise, if consumers are slow, producers can keeping adding to the queue till the JVM runs out of heap space.  Do this early in design; hard to retrofit later.
4. We can use offer() to check if the item will be accepted by the queue.  If the queue is full, the item can be discarded in application specific ways (for eg: simply drop it or save it to local disk for later usage)
5. BlockingQueue implementations - contain sufficient internal synchronization to safely publish objects from a producer thread to a consumer thread
1. LinkedBlockingQueue
2. ArrayBlockingQueue
3. PriorityBlockingQueue
4. SynchronousQueue - Not really a queue as it does not maintain storage space for elements.  Just maintains a list of queued threads waiting to enqueue or dequeue an element.  Directly transfers item from producer to consumer - more efficient.  Direct handoff also informs producer that consumer has taken responsibility for the item.  take() and put() will block if no thread is waiting to participate in the handoff.  Mainly used when there are always enough consumer threads.
9. Deque and BlockingDeque - allows efficient insertion and removal from head and tail.
1. Enables Work Stealing designs - In producer-consumer design, there is a single queue that is shared across all threads.  This causes lots of contention.  In work stealing,  each consumer has its own deque, from the head of which it consumes items. If its deque is empty, it can steal objects from the tail of some other consumer's deque. Most of the time, a consumer takes objects from the head of its own deque, thereby avoiding contention.  Even when it steals, there is little contention as it steals from the tail rather than the head.  Work stealing is well-suited for applications where producers are also consumers.
10. Interruption
1. Thread.interrupt() interrupts a thread.
2. Interruption is a cooperative mechanism, i.e.,  One thread cannot force another to stop what it is doing.  Thread.interrupt() merely requests a thread to stop at a convenient stopping point.
3. If a method is marked to throw an InterruptedException, it means that the method is blocking and that it will attempt to stop blocking early if interrupted.
4. No language specification about how to deal with interrupts.  Most natural option is to cancel whatever the thread is currently doing. Blocking methods that are interruptible make it easy to cancel long-running tasks when necessary.
5. One common option to handle the InterruptedException is to propagate it to your caller.  This can be done by not catching it at all, or by catching and rethrowing it after performing some local cleanup.
6. In cases where you cannot throw an InterruptedException (for eg: inside Runnabe.run()), you must catch the InterruptedException and restore the interrupted status by calling Thread.currentThread().interrupt() on the current thread.  This allows  code higher up in the call stack to see that the thread was interrupted.
7. Never catch an InterruptedException and ignore it - except when extending Thread (and therefore controlling all code higher up in the call stack).
11. Synchronizers - an object that coordinates the control flow of threads based on its state.  BlockingQueue is one example of a synchronizer.  Latch, FutureTask, Semaphores and Barriers are other examples of synchronizers.
1. Latch - a synchronizer that can block threads until it reaches its terminal state.  A latch acts as a gate.  Once open, it remains open forever.
1. Eg usage: Ensure that a computation cannot proceed until the resources needed by it have been initialized, Wait until all players in a multi-player game have finished their moves.
2. CountDownLatch - initialized with positive integer.Threads call await(), which blocks till counter becomes 0.  Other threads call countDown() which decreases the count.
2. FutureTask - mainly used to represent long running or async computation (for eg: by the Executor framework)
1. The computation is encapsulated in a Callable (result-bearing equivalent of Runnable).
2. FutureTask.get() returns result immediately if computation is done, or if exception is thrown or if cancelled; otherwise blocks till done.  Result obtained from get() is safely published.
3. Once complete, it stays in completed state forever.
4. Future.get() can throw an ExecutionException if the Callable.run() throws one. Check all known exceptions when calling get().  Other exceptions are generally rethrown.
3. Semaphores
1. Counting semaphores are used to control the number of threads that can simultaneously access a resource.  A thread wishing to use the resource must acquire() a virtual permit and release() it when done.  acquire() blocks if no permits are available.
2. A binary semaphore is a mutex with non-reentrant locking, unlike the intrinsic java object lock which is reentrant.
3. Can be used to turn any collection into a bounded blocking collection.
4. Barriers
1. Similar to latches, but all threads must come together at the barrier point at the same time in order to proceed.
2. CyclicBarrier allows a fixed number of threads to rendezvous repeatedly.  Useful in parallel iterative algorithms.
3. If a thread blocked on await() is interrupted or an await() times out, then BrokenBarrierException is thrown.
4. When barrier is successfully passed, await() returns with a  unique arrival index per thread, which can be used for leader election amongst the threads.
5. Also supports barrier action - a Runnable to be executed when barrier is successfully passed but before threads are released.
12. For building an efficient scalable result cache, use a ConcurrentHashMap> putIfAbsent()

Java Concurrency in Practice - Summary - Part 2

This is part 2 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 3 - Sharing Objects

1. Synchronization (for example, by using synchronized blocks) is not just about atomic execution of code blocks, it also influences memory visibility - i.e., ensures that a thread can see the changes made in another thread.  Without synchronization, the Java memory model does not guarantee that a value written by a thread will be seen by another thread on a timely basis or even at all.   For example,  if proper synchronization is not used, a thread X that relies on a control variable that is set in thread Y may NEVER see any updates to it that are written in thread Y.  In most cases, thread X will incorrectly loop for ever.
2. If synchronization is not used, reordering of operations done by multi-processor CPUs for improving performance, can cause a thread to see an incorrect or partial value written by another thread.  Without synchronization, the data can be stale.  If thread first sets variable x to 1 and then y to 2, another thread may see y set to 2 while x is still unset.  This can lead to bugs that are very hard to debug.
3. Always use synchronization whenever data is shared across threads.
4. Out-of-thin-air safety - A thread always sees the value of a variable that was written by some thread; not some random value pulled out of thin air.  Unless declared as volatile, 64-bit numeric variables (long and double) do not have out-of-thin-air safety, because the JVM treats 64-bit operations as two 32-bit operations.
5. Volatile variables provide a weaker form of synchronization.  
1. Volatile variables are specially treated by the compiler (for eg: not cached in registers). So a read of a volatile variable always returns the latest value written by some thread.
2. When thread A writes to a volatile variable and subsequently thread B reads that same variable, the values of all variables visible to A prior to writing the volatile variable become visible to B after reading the volatile variable.
3. Don't overuse volatile, and in tricky ways.  Synchronized blocks are still necessary for atomic operations.  
4. Volatile is commonly used for a control variable that determines when a thread should exit an infinite loop.
5. Locking guarantees visibility and atomicity; volatile variables guarantee only visibility.
6. Use volatile variables only when all the following conditions are satisfied:
1. Writes to the variable do not depend on its current value, or if it is guaranteed that only a single thread writes to the variable.
2. The variable does not participate in invariants with other state variables.
3. Locking is not required for any other reason while the variable is being accessed.
6. For server applications, always specify the -server JVM command line argument even while developing and testing, since the JVM does more drastic optimizations in server mode. Some concurrency bugs arise only under these optimizations.
7. Publishing an object means making it available to code outside of its current scope.
1. This can be done by:
1. storing a reference to it somewhere where other code can find it, say a public static field or in a publicly accessible HashMap.
2. returning it from a non-private method.
3. passing it to an alien method
1. a method in other classes
2. an overridable method in the same class
4. publishing an inner class instance (this automatically exposes the enclosing instance)
2. Sometimes we do not want to publish an object since that will break encapsulation.  An object that is published when it should not have been is said to have escaped.
3. Do not allow the this reference to escape during construction.  This commonly happens when the constructor registers some inner class with external event listeners or starts a thread.  Even if this is the last statement in the constructor, it is possible that a reference to the object may escape before it is fully constructed.  Other threads can see the partially constructed object and react incorrectly.  Use a separate start() method to start a thread created in the constructor, or to register event listeners created in the constructor.  Alternatively, to do it one step, use a newInstance() factory method that calls the constructor and then automatically calls start() before returning the newly created object.
4. Calling an overriden instance method from the constructor also allows this to escape before being fully constructed.
8. Thread confinement, i.e., make sure data is accessed only from one thread, is the easiest way to achieve thread safety.
1. Swing UI framework & JDBC connection objects use thread confinement extensively.
2. Thread confinement options:
1. Ad-hoc thread confinement - programmer entirely responsible to confine object to thread - no language features used. Not recommended due to fragility.
2. Stack confinement - Object can be reached only through local variables
1. Primitive types are always stack confined.
2. Care should be taken that object references do not escape.
3. ThreadLocal - provides get and set methods that maintain a separate copy of a value for each thread. Used as: new ThreadLocal() { public T initialValue() {...}}
9. Immutability - Immutable objects are always thread-safe.
1. Even if all fields of an object are final, it may still not be immutable as some of its final fields can refer to mutable objects.
2. Final fields provide initialization safety as they have special semantics under the Java Memory Model.  Make all fields of a class final unless they really need to be mutable 
3. When a group of related data items must be processed atomically, consider creating an immutable holder class.   When an immutable holder class, we may be able to avoid a synchronized block.
10. Safe publication
1. Simply storing a reference to an object into a public field is not safe, as it could lead to other threads seeing the object in a partially constructed state (due to reordering).
2. Immutable objects can be published through any mechanism; no synchronization necessary.
3. Others must be safely published, i.e., both the reference to the object and the object's state must be made visible to other threads at the same time.  A properly constructed object can be safely published by:
1. Initializing an object reference from a static initializer.  This is often the easiest way; static initializers are executed by the JVM at class initialization time which has JVM-internal synchronization.
2. Storing a reference to it in a volatile field or AtomicReference.
3. Storing a reference to it into a final field of a properly constructed object
4. Storing a reference to it into a field that is properly guarded by a lock, like thread-safe collections like Vector or synchronizedList.
4. Effectively immutable objects must be safely published.
1. Objects that are not technically immutable, but whose state will not be modified after publication are called effectively immutable.  Safely published effectively immutable objects can be safely used by any thread without additional synchronization.  For example, the Date object is often used as an effectively immutable object although it is technically mutable.
5. Mutable objects must be safely published, AND must be either thread-safe or guarded by a lock.