avoid calling serialization methods while holding lock #java

In java, serialization operations usually involve I/O — file I/O or network I/O. Do we ever serialize an object without I/O? I don’t think so.

Because I/O could block, we should not serialize while holding a lock.

readObject(), writeObject() …

Advertisements

3rd effect@volatile ] java5

A Wells Fargo java interviewer said there are 3 effects. I named

  1. load/store to main memory on the target variable
  2. disable statement reordering

I think interviewer mentioned a 3rd effect about memory barrier.

This quote from Java Concurrency in Practice, chap. 3.1.4 may be relevant:

The visibility effects of volatile variables extend beyond the value of the volatile variable itself. When thread A writes to a volatile variable and subsequently thread B reads that same variable, the values of all variables that were visible to A prior to writing to the volatile variable become visible to B after reading the volatile variable. So from a memory visibility perspective, writing a volatile variable is like exiting a synchronized block and reading a volatile variable is like entering a synchronized block.

https://stackoverflow.com/questions/9169232/java-volatile-and-side-effects address my doubt about “other writes“. Nialscorva’s answer echoes the interviewer:

Before java 1.5, the compiler can reorder the two steps

  1. construction of the new object
  2. assigning the new address to the variable

In such a scenario, other threads (unsynchronized) can see the address in the variable and use the incomplete object, while the construction thread is preempted indefinitely like for 3 hours!

So in java 1.5, the construction is among the “other writes” by the volatile-writing thread! Therefore, the construction is flushed to memory before the address assignment. Below is my own solution, using a non-static volatile field:

public class DoubleCheckSingleton {
	private static DoubleCheckSingleton inst = null;
	private volatile boolean isConstructed = false;
	private DoubleCheckSingleton() {
		/* other construction steps */
		this.isConstructed = true; //last step
	}
	DoubleCheckSingleton getInstance() {
		if (inst != null && inst.isConstructed) return inst;
		synchronized(DoubleCheckSingleton.class) {
			if (inst != null && inst.isConstructed) return inst;
			
/**This design makes uses of volatile feature that's reputed to be java5
*
* Without the isConstructed volatile field, an incomplete object's 
* address can be assigned to inst, so another thread entering getInstance()
* will see a non-null inst and use the half-cooked object 😦
* 
* The isConstructed check ensures the construction has completed
*/
			return inst = new DoubleCheckSingleton();
		}
	}
}

Wells IV #socket/c++/threading

This is one of the longest tech interviews and one of the most enriching 🙂 even though I don’t “like” all their questions — very academic/theoretical, text-book driven, too low-level to be practical, not testing practical zbs.

Q: Any consistently reliable technique to detect stale order in your book?

Q: what’s your frame size if your tcp/ucp buffers sizes are so large?

Q: experience storing ticks?

—— C++ questions:
Q1: how can you avoid the cost of virtual function?
%%A: enum/switch or CRTP

Q1b: what’s CRTP

Q: what if your copy ctor signature is missing the “const”?
%%A: you can’t pass in temporaries or literal values. Such arguments must pass into “const &” parameter or “const” parameter. Correct.

Q: double delete?

Q: policy class? traits class?

Q: STL binders.. use case?

Q: how many types of smart pointers do you use?

Q: difference between java generics vs c++ templates?
%%A: type erasure. Java Compiler enforces many rules, but bytecode saves no info about the type argument, so we can get strange runtime errors.
%%A: template specialization. Template meta-programming
%%A (accepted): code bloat since each template instantiation is a separate chunk of code in the object file and in memory.
A: I have a dedicated blog post on this.

Q: what’s returned by a std::queue’s dequeue operation when it’s empty?
AA: undefined behavior, so we must check empty() before attempting dequeue. I believe ditto for a std::stack

Q: why template specialization?
%%A: customize behavior for this particular vector since the standard implementation is not suitable.

Q: how do you implement a thread-safe c++singleton
A: not obvious. See concurrent lazy singleton using static-local var

Q12: in a simple function I have
vector v1 = {“a”, “b”}; vector v2 = v1; cout<<….
What happens to the ctor, dtor etc?
A: 2 std::strings constructed on heap, vector constructed on stack; 2nd vector copy-constructed on stack; 2 new strings constructed on heap; vector destructors deletes all four strings
A: the actual char array is allocated only once for each actual value, due to reference counting in the current std::string implementation.

Q12b: you mean it’s interned?

Coding question: implement void remove_spaces(char * s) //modify the s char array in place. See %%efficient removeSpaces(char*) #Wells

—— threading, mostly in java
Q: What are the problems of CAS solutions?
A: too many retries. CAS is optimistic, but if there are too many concurrent writes, then the assumption is invalid.
%%A: missed update? Not a common issue so far.

%%Q: Synchronized keyword usage inside a static method?
AA: you need be explicit about the target object, like synchronized(MyClass.class)

Q21: Name 3 effects of java volatile keyword — Advanced. See 3effects@volatile ] java5.

Q21b: analyze the double-checking singleton implementation.
staticInst = new Student(); // inside synchronized block, this can assign an incomplete object’s address to staticInst variable, which will be visible to an unsynchronized reader. Solution – declare staticInst as volatile static field

—— System programming (ANSI-C) questions
Q: have you used kernel bypass?

Q5: how do you construct a Student object in a memory-mapped-file?
%%A: placement new

Q5b: what if we close the file and map it again in the same process?
%%A: the ptr I got from malloc is now a dangling ptr. Content will be intact, as in Quest

Q5c: what if Student has virtual functions and has a vptr.
%%A: I see no problem.

Q: you mentioned non-blocking TCP send(), so when your send fails, what can you do?
%%A: retry after completing some other tasks.

Q4: why is UDP faster than TCP
%%A: no buffering; smaller envelopes; no initial handshake; no ack;
%%A: perhaps most important for market data — multiple recipient with TCP is very heavy on sender and on network

Q4b: why buffering in tcp?
%%A: resend

Q: can tcp client use bind()?
%%A: bind to a specific client port, rather than a random port

Q6: is there socket buffer overflow in TCP?
A: probably not

Q6b: what if I try to send a big file by TCP, and the receiver’s buffer is full? Will sender care about it? Is that reliable transmission?
A: Aquis sends 100MB file. See no overflow]TCP slow receiver #non-blocking sender

Q: in your ticking risk system, how does the system get notified with new market data?
%%A: we use polling instead of notification. The use case doesn’t require notification.

Q: any network engineering techniques?

Q: what kernel parameters did you tune?

 

—— Stupid best-practice questions:
Q: what’s the benefit of IOC?

Q: Fitnesse, mock objects

Question on j4 factory. See separate blog post.

 

java lock: atomic^visibility

You need to use “synchronized” on a simple getter, for the #2 effect.!

 

A typical lock() operation in a java method has two effects:

  1. serialized access — unless I release the lock, all other threads will be blocked grabbing this lock
  2. memory barrier — after I acquire the lock, all the changes (on shared variables) by other threads are now visible. The exact details are .. to be detailed.

I now feel the 2nd effect is often more important (and more tricky) than the 1st effect. See P94 [[Doug Lea]] . I like this simple summary, even if not 100% complete —

“In essence, releasing a lock forces a flush of all writes from working memory….and acquiring a lock forces reload of accessible fields.”

Q: what are the subset of “accessible fields” in a class with 9 fields?
A: I believe the compiler knows “in advance” what subset of fields will be accessed after lock acquisition.

Q: what if I acquire a lock, do nothing and release the lock? Is there the #2 effect?
A: I doubt it. You need to enclose all the “tricky” operations between a lock grab/release. If you leave some update (to a shared mutable) outside in the “cold”, then #1 will fail and #2 may also fail.

 

y concurrentHM.size() must lock entire map#my take

Why not lock one segment, get the subcount, unlock, then move to next segment?

Here’s my take. Suppose 2 threads concurrently inserts an item in each of two segments. Before that, there are 33 items. Afterwards, there are 35 items. So 33 and 35 are both "correct" answers. 34 is incorrect.

If you lock one segment at a time, you could count an old value in one segment then a new value in another segment.

java ReentrantLock^synchronized keyword

I told Morgan Stanley interviewers that reentrantLock is basically same thing as Synchronized keyword. Basically same thing but with additional features:

  • Feature: lockInterruptibly() is very useful if you need to cancel a “grabbing” thread.
  • Feature: tryLock() is very useful. It can an optional timeout argument.

Above features all help us deal with deadlock:)

  • Feature: Multiple condition variables on the same lock.
  • Feature: lock fairness is configurable. A fair lock favors longest-waiting thread. Synchronized keyword is always unfair.
  • — query operations —
  • Feature: bool hasQueuedThread(targetThread) gives a best-effort answer whether targetThread is waiting for this lock
  • Feature: Collection getQueuedThreads() gives a best-effort list of “grabbing” threads on this lock
  • Feature: Collection getWaitingThreads (aConditionVar) gives a best-effort view of the given “waiting room”.
  • Feature: int getHoldCount() basically gives the “net” re-entrancy count
  • Feature: bool isHeldByCurrentThread()

[17]java MS java threading IV#phone

See also https://bintanvictor.wordpress.com/2009/03/21/realtime-inter-vm-communication-in-front-desk-trading-sys/

These are in the QQ category i.e. skills required for QnA IV only.

Q1: 3 threads to print the numbers 1,2,3,4,5… in deterministic, serial order. Just like single-threaded.

Q1b: what if JVM A has T1, T2, and JVM B has T3? How do they coordinate?
%%A: in C++ shared memory is the fastest IPC solution for large data volume. For signaling, perhaps a semaphore or named pipe
%%A: I feel the mutex is probably an kernel object, accessible by multiple processes.

On Windows, mutex, wait handle, … are all accessible cross-process, but java (on Windows or unix) is designed differently and doen’t have these cross-process synchronization devices.

%%A: use a database table with one row one column. Database can notify a JVM.
AA: The java.nio.file package provides a file change notification API, called the Watch Service API. The registered JVM has a thread dedicated to watching.AA: in java, the JDK semaphore is NOT a wrapper of the operation system semaphore so not usable for IPC
A: java Semaphore? Probably not an IPC construct in java.

Q2: have you used any optimized Map implementations outside the JDK?

Q3: to benchmark your various threading solutions how do you remove the random effects of GC and JIT compilation?
%%A: allocate enough memory to avoid GC. Turn off JIT to compile every code path. Perhaps give the JVM some warm-up period to complete the JIT compilation before we start the benchmark.

java exception passing between threads

Many people ask how to make a child thread’s exception “bubble up” to the parent thread.

Background — A Runnable task is unsure how to handle its own exception. It wants to escalate to parent thread. Note parent has to block for the entire duration of the child thread (right after child’s start()), blocked either in wait() or some derivative of wait().

This question is not that trivial. Here are my solutions:

1) Callable task and Futures results — but is the original exception escalated? Yes. P197 [[java threads]]

2) Runnable’s run() method can temporarily catch the exception, save the object in a global variable such as a blocking queue, and notifyAll(). Parent thread could check the global variable after getting notified. Any thread can monitor the gloabal.

If you don’t have to escalate to parent thread, then

3) setUncaughtExceptionHandler() – I think the handler method is called in the same exception thread — single-threaded. In the handler, you can give the task to a thread pool, so the exception thread can exit, but I don’t know how useful.

4) adopt invokeAndWait() design — invokeAndWait() javadoc says “Note that if the Runnable.run() method throws an uncaught exception (on EDT) it’s caught and rethrown, as an InvocationTargetException, on the callers thread”

In c#, there are various constructs similar to Futures.get() — seems to be the standard solutions for capturing child thread exception.
* Task.Wait()
* Task.Result property
* EndInvoke()

##thread cancellation techniques: java #pthread, c#

Cancellation is required when you decide a target thread should be told to give up halfway. Cancellation is a practical technique, too advanced for most IV.

Note in both java and c#, cancellation is cooperative. The requester (on it’s own thread) can’t force the target thread to stop.

C# has comprehensive support for thread cancellation (CancellationToken etc). Pthreads also offer cancellation feature. Java uses a numbers of simpler constructs, described concisely in [[thinking in java]]. Doug Lea discussed cancellation in his book.

* interrupt
* loop polling – the preferred method if your design permits.
* thread pool shutdown, which calls thread1.interrupt(), thread2.interrupt() …
* Future — myFuture.cancel(true) can call underlyingThread.interrupt()

Some blocking conditions are clearly interruptible — indicated by the compulsory try block surrounding the wait() and sleep(). Other blocking conditions are immune to interrupt.

NIO is interruptible but the traditional I/O isn’t.

The new Lock objects supports lockInterruptibly(), but the traditional synchronized() lock grab is immune to interrupt.

CompletionService.java – initial phrasebook

producer/consumer – upgraded.

buffer – as explained elsewhere in my blog, there’s buffer in any async design. In the ExecutorCompletionService scenario, the buffer is the “completion queue”. In the classic producer/consumer scenario, buffer is the item queue.

items = “tasks” – In P/C setup, Thread 1 could be producing “items” and Thread 2 could be taking up the items off the buffer and using them. In the important special case of task items, the consumer thread
(possibly worker thread) would pick up the task from queue and execute them. CompletionService is all about task items.

tasks executed by..? – in P/C with task queue, tasks are executed by consumer. In CompletionService, tasks are executed by the mysterious “Service”, not consumer. See CompletionService javadoc.

3-party – 1 more than P/C. Beside the P and C threads, the task executor could run on another thread.

send slow task to worker thr then back to EDT, briefly

How do you thread a long-running operation (a “tortoise”) that needs to update the GUI? Putting it on the EDT will block all screen

updates and user interactions until the tortoise finishes.

P930 [[Pro WPF in c#]] confirmed my belief that in wpf (as in swing),

1) the task should first be dispatched (from EDT or another thread) to a worker thread, which is designed for tortoises, and

2) any resulting update to GUI is then sent back, from the worker thread, to the EDT, which is the only thread permitted to update

the screen.

##java inter-thread communication – practical designs

— Practical solutions–
– producer/consumer — best eg is invokeLater()
– wait/notify with the lock holding the “message” data
– a callable thread returning result or exception to the submitter thread via future task.
– global variables
– gemfire
– database, file — much slower
– (actually fairly practical in MOM designs) one thread sending a tibrv/jms message out of the host process to the MOM, another thread in the host process receiving it

— other designs —
join()
env var
parent passing data when creating a child thread

replacement for stop/suspend/resume in java threads – intrusive?

c# Thread.Abort() is slightly better than java’s stop()…

—-
For suspend/resume, [[java thread programming]] P91 has a BestReplacement.java. However, I feel most designs don’t need suspend and resume. wait/notify is the standard replacement technique.

Nowadays, even wait/notify is seldom used by app developers. Nevertheless, BestReplacement.java presents some FUNDAMENTAL techniques or idioms. Do you ever need to go beyond the java5
concurrent utilities?

Some veterans point out that suspend/resume/stop are intrusive operations on a vm-thread via the thread handle. The non-intrusive alternatives are locks, conditions, interrupts and flow-control flags monitored by the “driver” methods (the method seeded in the thread). Most good designs use a combination of the above constructs to let the thread decide when to suspend/resume/stop itself. In contrast, the intrusive operations are unconditional, abrupt, unilateral actions on the thread by another thread.

never edit table model on non-EDT?

A Swing interviewer asked me

Q: Can a non-EDT thread ever writes to the underlying data-structure of a (table/tree/list) model? 
A: If it does, we are at risk. EDT could be reading it — uncoordinated and unexpected. EDT might see corrupted data. Classic reader/writer race scenario. Murphy’s Law — if it could happen it will.

(In theory, EDT can also update the data due to a message listener or a DB operation –writer/writer race, but) This one scenario alone is reason enough. All underlying data queried by EDT should Never be modified outside EDT.

In one real world live trading app though, some MOM listener threads do indeed update underlying data structure. When that happens, users are not allowed to trigger a refresh — we can disable some buttons. After the update, we send invokeLater(fireXXX()) to refresh the view.

You may want to lock-protect the underlying data, but then EDT might be blocked. Yet, this is widespread. Look at DefaultTableModel in which EDT does access the underlying Vector, which is lock-protected. If the Vector is large, growing it (perhaps 2 folds) can take log(N) time, and EDT would be blocked for that duration. However, in practice this latency is probably below 50ms and unnoticeable.

As a minimum requirement, ALL models need to be thread-safe. That often entails locking or CAS or copy-on-write.

Swing models normally do not use large data structures (since a screen can’t realistically show even 1000 rows). If it does, update should ideally be designed with a worker thread, to populate a replacement data structure, and then ask EDT to swap it in. Many non-ideal situations exist in practice, which calls for specific techniques and tactical solutions.

size of Object.java, and how does it add up?

(Hypotheses and Personal opinion only. I’m no authority.)

Minimum info to be stored in an Object.java instance —

– (4-byte) wait-set as a hidden field — to hold the waiting threads. Expandable set, so perhaps a WS_pointer to a linked list
** It’s probably inefficient to try to “save” memory by building a static VM-wide lookup table of {instance-address, wait-set}. As this table grows, such hashtable lookup is going to impact the most time-critical operations in JVM. Not having this lookup means minimum overhead locating the wait-set.
** this particular WS_pointer starts out as null pointer
** Note c# value types don’t have wait-set. c# Reference types do. The sync-block takes 4-bytes
** why linked list? Well, Arrays can’t grow. Vector involves re-allocation.

– How about the data structure holding the set of threads blocked in lock() or synchronized keyword? A mutex “contender set” associated with each Object.java instance? Apparently there’s no such thing mentioned in popular literature. Is it possible to put these contenders in the wait-set but use a flag to distinguish?

– (4-byte) vptr as a hidden field — If you try to be clever and put this ptr as the first element of the wait-set, then every Object instance still must occupy 64bits == WS_pointer + 1st element in the wait set. Therefore it’s faster to store the vptr directly in the Object instance

– ? pointer to the class object as a hidden (static) field — representing the Runtime type of the object.
** This can be stored in the per-class vtbl, as C++ does. This hidden field occupies 32 bits per Class, not per instance.
** I believe myObject.getClass() would use this pointer.
** See my blog post on type info stored inside instances (http://bigblog.tanbin.com/2012/02/type-info-stored-inside-instances-c-c.html).

– hashcode — Once generated, hashcode must not mutate (due to garbage collection relocation), until object state changes.
** I feel this can live on the wait-set, since most Object instances don’t get a hashcode generated.
** Why not use another hidden field? Well, that would require 32 bits dedicated real estate per object, even if an object needs no hashcode in its lifetime.
** Note python hashcode never mutates. See separate blog post.

?? this-pointer as a hidden field — to hold “my” own address. Remember this.m(…) is compiled to m(this, …) to let m() access fields of the host object.
** However, I believe this-pointer is possibly added (as a hidden field) only when you subclass Object.java and introduce a field, and then a method referencing that field. There’s no need to add this-pointer to classes whose instance methods never access instance fields. Such an object doesn’t (need to) know it’s own address — like a lost child.
** even in those “other” cases, I feel it’s possible for the compiler to remove this-pointer as a field (reducing memory footprint) because compilers implicitly translate myInstance.m1() to m1(&myIntance)

In conclusion, I’d guess minimum size = 8 bytes but will grow when hashcode generated.

Q1a: min size of a c# struct or any value type instance?
%%A: C# structs need zero overhead, so an Int32 instance needs just 32 bits.
%%A: 
When we call myStruct.m2(), there’s no vptr involved — just a compile-time resolved function call as in C and non-OO languages. Compiler translates it to some_Free_Function(ptr_to_myStruct). Note even for this value-type there’s no pass-by-value — no passing at all. Just translation by compiler.

Q1b: min size of c# System.Object instance.
A: Supposed to be 8 bytes minimum (A value type instance has no such overhead)
* 4-byte vptr
* 4-byte sync block
A real instance seem to be 12-bytes long.

Q2: why is the minimum size of an empty c++ object no more than 1 byte?
%%A: obvious from the analysis above.

Q2b: why not 0 byte?
A: an object is defined as a storage location. Even if there’s no field in it, a=new MyObject() and b=new MyObject() (twice in a row, single-threaded program) must produce 2 objects at 2 locations.

Note the size of an empty c++ string class instance is 12 bytes, according to [[c++ primer]]

According to P89 [[C# in depth]] a C# byte takes 1 byte, but 8+1 bytes of heap usage when “boxed”. These 9 bytes are rounded up to 12 bytes (memory alignment). Since heap objects are nameless and accessed only via a pointer, the pointer becomes a field (of the boxed object) and takes 4 bytes (assuming a 32-bit machine)

starting thread in a ctor – my take on a common pattern

It’s common to start a thread within a ctor, as seen in many articles and projects.

Danger – the half-cooked object under-construction should not be exposed and accessible in the child thread. Often in practice it’s not disastrous but accessing a half-cooked object is a code smell.

I’d say it’s fine if the code is simple and you know for sure the thread.start() is at end of ctor and the child thread doesn’t do anything fancy. Make sure other developers don’t mess things up.

http://docs.oracle.com/javase/tutorial/essential/concurrency/syncmeth.html explains that constructor is single-threaded by default and is designed to run in a single-threaded “context”. Don’t break that assumption.

send event from EDT to EDT – user update jtable

I feel it’s a very common pattern to (Let’s not worry about how frequently) send event from EDT to EDT.

+ Most (if not all) user edits on jtable are processed on EDT. What if you want to update something else on screen, or translate the raw user input to a different value? Your event listener need to fire events. This action happens on EDT, and generates a new event to be placed at the tail  of the EDT queue.

+ invokeLater() is often included in a method that may run on EDT or non-EDT

+ invokeLater() often calls another invokeLater()

Don’t invokeAndWait() from EDT. Runtime exception. Reason? a fine technical point — Caller of invokeAndWait() must remain on top of its call stack (CS1) throughout, when the runnable’s run() is “Pushed” on EDT call stack, executes and popped off EDT stack. If CS1 is EDT, then the caller can’t remain on top.

y a nested java class can only access final local variables

The explanation is tedious because it has to cover primitive/reference type local variables.

1) Primitive is easier. Say there’s local_boolean isGood variable. If it’s final, then the nested class can simply get an implicit isGood final_private_boolean_field when the nested instance (I’m not saying “class”) is allocated. Probably 1 byte added. All final primitive variables are immutable, which makes things simple.

2) Suppose this local variable is not final, and it’s accessed by a static or non-static NestedClass.m1(). At run time, when m1() runs, isGood is quite possibly out of scope if the stack frame is wiped out. The “last” value of isGood is lost.

3) Contrast 2) with a final_local_reference variable acct, with a mutable Boolean field acct.isGood. Final, so NestedClass instantiation can allocate a 32-bit immutable pointer to the object behind acct. This will put off the garbage collector. When NestedClass.m1() runs, the real time value of acct.isGood will be used, even though it’s mutable.

4) Now consider non-final_local_reference variable acct. acct can point at one object then another object. These objects are on heap, but the 32-bit local pointer is on stack. Stack frame could be gone when m1() runs. The address of the “last” object referenced by acct would be gone.

a java thread doesn’t map to an object

Some java developers intuitively think a thread maps to an object in JVM (or kernel), and we can control it by calling methods on it (similar to how we control a JDBC connection or JMS session). For both novice and experienced java developers, it can be hard to unlearn that idea.

java.lang.Thread static methods obviously don’t affect any particular “object” [1], since they are static method. java.lang.Thread instance methods do affect the target thread, in limited ways. The stop/suspend/resume methods are direct actions on an an “instance” but are deprecated. The most fundamential programmatic controls on a thread involve locks and wait/notify, which paradoxically never name the threads they affect. Using these constructs demands that we visualize the affected threads as unassociated with any jvm object including the java.lang.Thread instances.

All experienced multi-threading developers eventually get the idea that a thread is not really associated with any object we create in our source code.

Java confuses us by giving us object-oriented thread creation constructs + thread pool. These make us feel threads are just objects. Well, are ebooks real books?

As explained in my blog on [[programmatic control on threads]], a VM thread has its memory structure residing in the stack space, including program counters and per-thread registers. The Thread.java object we create is a JVM heap object having a pointer to the VM thread. This Thread object is unrelated [2] to those objects accessible on the VM thread.

VM thread is basically a stack of open method CALLS. Each non-static method call like m1() has a host object (myAccount for eg) but that host object is UNRELATED[2] to the vm thread. However, myAccount can become problematic to our vm thread due to data corruption if
* m1() read/write myAccount fields
* and other vm threads also have method CALLs that read/write fields of this same myAccount instance.
* In addition, m1() often read/write other shared objects like herAccount, while other threads may also read/write herAccount

It’s exactly due to this kind of concurrent access to shared objects (like myAccount) that we end up with locks, wait/notify and all the consistency/liveness issues.

Among vm thread t1, corresponding Thread instance T1, and a regular object U1 on t1, we can say
+ T1 has a pointer to t1, but never to U1
+ t1 has no pointer to T1 or U1. This t1 is not a java object with fields and methods.
+ U1 has no pointer to t1, but the can get a pointer to T1 using Thread.currentThread(). But can it access fields of T1 if you put custom fields into T1? YES. Thread.currentThread() returns the same Thread instance every time.

In conclusion, the Thread.java object is a poor handle on the vm thread. The vm thread is not an object but a call stack. You don’t have a good java object (with fields and methods) manipulating the vm thread. Crucially, the method calls on a vm thread often access shared objects, but these objects are unrelated[2] to the vm thread

[1] Actually Thread.sleep does affect the current thread but that’s a minor point.
[2] there’s no pointer between the vm thread and myAccount. If you know myAccount.m1() is running on a vm thread, myAccount.m1() might simultaneously be running on antoher vm thread too.

java concurrent hash map iterator consistency

As mentioned repeatedly in other blog posts, thread safety primarily means liveness + consistency. Consistency with reality.

For any collection, counting the size of the collection should reflect a _snapshot_. On a multiprocessor machine, if Thread A adds 3, while Thread B removes 100 items all within the same time window, over a 1000-element collection, all after I start counting, then I should eventually return a count of 1000 or 903. If I were to return 1003, then that’s inconsistent with reality, since at no time is the collection 1003-long??

Now let’s turn to iterators. If one thread is iterating while another thread write a structural change, one valid result (consistent) is the create-time snapshot of the underlier. Another valid result would be that snapshot + changes in the unseen items, assuming all the changes are in the unseen items. Personally, I see this as a consistent snapshot — the snapshot taken after the changes.

What if the change happens ON a segment already visited? Iterator already “shipped” them to client, so I feel we had better ignore those changes and all future changes. Use the create-time snapshot instead??

Brian Goetz said — Iterators returned by ConcurrentHashMap.iterator() will return each element once at most and will not ever throw ConcurrentModificationException, but may or may not reflect insertions or removals that occurred after creation. No table-wide locking is needed (or even possible) to provide thread-safety when iterating the collection. Note size() does need table-wide locking.

http://tech.puredanger.com/2009/02/02/java-concurrency-bugs-concurrentmodificationexception/ points that CHM iterator is _NOT_ a snapshot iterator.

when a heap variable gets updated behind your back

Beginning developers aren’t really familiar with how a normal-looking variable can suddenly change value between Line 1 and Line 2 where we read it twice without writing. We are slightly more familiar with a shared hash table being updated concurrently. Well, an int variable can be equally “volatile”.

Most commonly, it’s another thread. If a variable is placed in shared memory, then another process can modify it.

In C, it can even be hardware driven — the so-called volatile object.

Heap? not necessarily. In C, if you declare an auto variable (on stack) in main(), and pass its address around, then many threads can update it.

How about JNI? What if a purely native thread and a jvm-only thread both write to a variable? Possible? (Note a JVM thread extending into native method is fine and won’t cause unexpected outcome.)

programmatic control on a java thread

Update: The Process object in dotnet is another “handle” on a OS construct…

Suppose a virtual machine thread FastRunner is linked to a Thread Object TO2.
A) As a java object, a Thread.java object TO2 is a chunk of HEAP mem, and can have fields.
B) As a real thread ie “vm thread”, FastRunner occupies memory for its call stack and can receive cpu cycles.

In general, a call stack can have “access” to any heap object if you pass in a (indirect) reference. TO2 is a heap object and can be accessed on the call stack of FastRunner. In fact it’s dead easy. Thread.currentThread() will return a TO2 reference. This is a embrace.
1) TO2 has a pointer to the call stack of FastRunner and can affect FastRunner in a few limited ways.
2) among the local variables of the call stack, there’s now a pointer to TO2.

A field f1 in TO2 is not related to anything in the vm thread FastRunner. You might potentially want to use TO2 fields to control FastRunner, but TO2.f1 is just like a field in any heap object.

Fundamentally, TO2 has a pointer to the FastRunner vm thread. JVM provides no reference to FastRunner as it’s not on the heap and not a java Object.

Suppose you have a (usually stateless) Runnable object R2. It is basically a function pointer. R2 has nothing but 4 bytes holding the address of run() method which lives in Code Section, not stack not heap. You can pass R2 to Thread() ctor to create TO2 object. TO2 has a different address than R2 though.

If TO2 is a television remote control, then it offers a small number of “buttons” to control FastRunner, like

  • * interrupt()
  • * join() – will block the current thread
  • * stop() – deprecated but still useful as in SureStop.java
  • * start(). – could be useful to control timing
    • Note run() should never be called except by start()

– if you have a java reference to the TO2 object, you can’t use it to make FastRunner sleep
– if you have a java reference to the TO2 object, you can’t use it to make FastRunner grab a lock
– if you have a java reference to the TO2 object, you can’t use it to make FastRunner wait in a monitor
– if you have a java reference to the TO2 object, you can’t use it to notify FastRunner

I’d say the remote control is so limited that most of the important “buttons” are missing. As explained below, TO2 is a “poor” handle on the vm thread (FastRunner) known as a “thread” with its call stack, thread registers, cpu cycles etc. Better to avoid confusion — distinguish “Thread” and “thread”. P27 [[java threads]] explains
* when a vm thread in VM is running its run() method, both the VM thread and the Thread object are connected. TO2 is a relatively good handle on the vm thread in VM.
* after run() returns, vm thread no longer gets cpu cycles, but the Thread object is still useful until it’s garbage collected.
* after you instantiate a Thread, but before you call its start(), the call stack doesn’t exist.
* bottom line — Thread object lives a bit longer than a vm thread.

If you naively think that an instance method in TO2 is related to the corresponding call stack of FastRunner, then you are wrong on multiple accounts.
* if FastRunner run() method calls such a method m1(), then the method runs on FastRunner, but m1() body may have nothing to do with the VM thread FastRunner.
* As explained earlier, Thread has longer lifespan than thread, so any method call made outside FastRunner’s lifespan is unrelated to FastRunner the vm thread.
* the main thread can call any of those methods. Such method calls may have nothing to do with the VM thread’s call stack.

In terms of programmatic control on the vm thread, D) is most useful, followed by B and C —
C) thread instance methods — least used. Quiz — can you name 2?
TO2.interrupt() is one of the few important instance methodS. Others include run(), join() and the associted isAlive(). These operations can be invoked on main thread or another thread. They mostly affect the current thread not the target thread.
B) Thread.java static methods let you probe/modify the thread to some extent, such AS Thread.sleep(). These Thread methods are static methods, without a specific Thread instance as the target. They usually affect the current thread. The static and non-static mix in Thread.java is confusing. I feel these should be put into a ThreadControl.java class and converted to instance methods, and instantiated as a static member of System, just like System.out.
D) Many of the modifications, controls && operations on the thread are effected through constructs outside the Thread instance, such as wait(), the all-important keyword synchronized, which is similar to the Lock.lock() …
There’s something like TO2.isInterrupted() instance(!) method which is often called — Thread.currentThread().isInterrupted().

no blocking feature in ThreadPoolExecutor

A known issue — The Sun bugs database http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6648211 describes the unexpected immediate-failure behavior of blocking-thread-pool, and mentions a Spring forum discussion —

“You have to modify the java.util.concurrent.ThreadPoolExecutor by overriding the execute method and place a task with a put instead of an offer with a zero timeout on the workqueue. Or you could use the BlockingExecutor (and the ThreadPoolBlockingExecutor) from Prometheus. The primary reason of existence of these classes was to create an Executor that is able to block.”

JDK ThreadPoolExector javadoc made it clear — “New tasks submitted in method ThreadPoolExecutor.execute will be rejected when the Executor … uses finite bounds for work queue capacity, and is saturated.” Root cause beneath the non-blocking behavior of blocking-queue is the use of queue.offer(). “Offer” sounds like “try inserting” and therefore non-blocking. It returns false if queue full. In contrast, the put() method is blocking.

   public void execute(Runnable command) {
       if (poolSize >= corePoolSize || !addIfUnderCorePoolSize(command)) {
           if (runState == RUNNING && workQueue.offer(command)) {

Personal experience #1 — we created a simple blocking thread pool. Avoid ThreadPoolExecutor.execute(). Manually create an array blocking queue of fixed capacity, and add tasks using put().

Personal experienc #2 — An even simpler solution is a “shared unbounded queue” (see javadoc) free of blocking altogether —

     virtThrPool = (ThreadPoolExecutor) Executors.newFixedThreadPool(howManyThreads);

(You don’t have to cast, but casting gives many convenient methods of ThreadPoolExecutor.java)

You can easily submit() tasks and never get blocking or rejection.

demo from XR, showing non-blocking behavior of blocking queue

You can get blocking behavior if you avoid ThreadPoolExecutor.execute(). You can create an Array blocking queue (myABQ) and submit tasks using myABQ.put().

I learnt this from my Taiwan colleague.

On Fri, Apr 8, 2011 at 11:56 PM, Bin TAN (Victor)  wrote:

ThreadPoolExector api made it clear — New tasks submitted in method ThreadPoolExecutor.execute will be rejected when the Executor has been shut down, and also when the Executor uses finite bounds for both maximum threads and work queue capacity, and is saturated.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6648211 describes the non-blocking behavior of blocking thread pool, and mentions a Spring forum discussion —

You have to modify the java.util.concurrent.ThreadPoolExecutor by overriding the execute method and place a task with a put instead of an offer with a zero timeout on the workqueue.

Or you could use the BlockingExecutor (and the ThreadPoolBlockingExecutor as standard implementation) from Prometheus. The primary reason of existence of these classes was to create an Executor that is able to block.

Milestone events in a growing thread pool

M22a) core threads all busy
M22) start queuing

M33a) queue full
M33) create first thread beyond core threads

M44) 1st rejected task

As shown above, task queue has a max size; thread pool has a core size and max size.
P194 [[Java threads]] has a good illustration of these milestones in a “bounded pool” i.e. a pool with bounded queue. Here’s my modified version based on P194
* Pool starts with no thread no task
* First task -> create first thread
* tasks come in a flurry -> M22
* Queue full -> M33
* Pool capacity reached -> M44

How about an unbounded pool? M33 never happens.

Executor iwt ExecutorService

Executor.java javadoc ties together
– ExecutorService.java extended-interface
– Executor.java parent-interface
– Executors.java — all-static utility class, similar to Collections and Arrays.

This Javadoc hints that

JDK *implementations* i.e. concrete classes provided in this package implement ExecutorService, which is a more extensive interface than Executor. The Executors class provides convenient factory methods for these Executors.

Remember the Lab49 IV question? There are just 2 executor services (bundled in JDK), so better know them
* ThreadPoolExecutor
* ScheduledThreadPoolExecutor

avoid calling wait() while holding multiple locks

Avoid calling wait() while holding 2 locks. I always try very hard to call lock1.wait() while holding nothing but lock1. Any lock2 held would NOT be released by lock1.wait().

Similarly, avoid grabbing a lock while holding other locks.

Beware of all blocking operations like lock-grabbing, wait(), while loop, join() and sleep(longPeriod). If the blocked thread is the only thread capable of “releasing” some shared resource, then that resource gets locked up along with the thread, starving other threads who needs it.

In contrast, tryLock(), wait(shortPerod), join(shortPeriod) are safer.

call thisThread.run() +! calling thisThread.start() first

2. What will happen when you call thisThread.run() without calling thisThread.start() first?
answer: doesn’t create a thread
i agree. start() is a hook into the JVM.

It sets up the call stack in the JVM stack segment and those internal memory structures (like instruction pointers) needed by a real thread. Then it points the instruction pointer to the run() method’s address. Then it joins the other Eligible threads to be scheduled by the jvm scheduler. I believe this start() runs on the thread-creator thread, but run() would execute on the new thread. If I’m right, then it’s misleading to say start() calls run(). start() returns after setting up the jvm thread. When the new thread is scheduled to execute, first method executed is run().

This jvm thread exists independent of the thisThread object. Jvm thread can run (till shutdown) even after thisThread object is garbage collected. Conversely, thisThread object can live in the heap without the call stack — this is the situation before we call start(), or after the jvm thread exits.

Physically, the jvm thread occupies a bunch of memory cells (its home, in the stack) in order to do its job. Our thisThread object also occupies a bunch of memory cells (in the heap) to hold indirect pointers to the jvm thread’s home.

countDownLatch in server shutdown – real example

In Neo, we use a count down latch to block System.exit() until a number of clean-up tasks are completed on several event-handlers. Event handler could run on any thread, but not the shutdown thread. Each clean-up would trigger upon an event, do the clean-up then call countDown() exactly once.

If a clean-up should run twice, then it should call countDown() exactly twice.

benign race condition (homegrown ConcurrentMutableInteger

Does the getInt() below need “synchronized”? I am not expert but I would go out on a limb and say no. It either gets the value before or the value after the increment, never a value inconsistent with reality. As Bill Lewis said in his pthread book about semaphore getCount(), whenever some thread wants to /use/ the getInt() return value, it should bear in mind the value could be stale, since other threads could change it any time.

The race between increment() and getInt() is probably benign. However, if increment() isn’t synchronized, then you could get lost-updates — inconsistent with reality. Note volatile field won’t help.

// simpler than AtomicInteger, but not lockfree.
class ConcurrentMutableInteger implements Serializable{
 private int i = 0;
 public synchronized void increment() {this.i++;}
 public int getInt() {return this.i; }
}

split 30 threads into 3 JVM processes?

Q: if I want to support up to 30 concurrent tasks, which is better

X: 3 processes, 10 threads each
Y: 1 process holding 30 threads

It depends primarily on data-sharing. If there's a pattern of clustering among the threads, where most traffic is within 10 threads, then it's possible to run those 10 in one JVM.

If threads share data randomly and heavily, then X may require IPC overhead. You can minimize it with a database or file-based task allocation. IPC adds dev effort, maintenance effort, complexity.

In practice, X is more fault-tolerant. You can configure the processes differently.

Thread.java methods – 2+1+1 types

For a novice, It's instructive to classify Thread.java methods —

1) Methods affecting the executing jvm thread, always static methods – sleep, yield
2) Methods affecting “this” which is a Thread object linked to a jvm thread. Always non-static methods – targetThread.set/getUncaughtExceptionHandler(), targetThread.isDaemon()

Those are the 2 most common types of Thread.java methods, but there are also —

3) Methods (very special) affecting b_o_t_h — targetThread.join(), targetThread.interrupt()

4) Methods affecting no particular thread, but entire JVM — getAllStackTraces(), set/getDefaultUncaughtExceptionHandler()

threadA triggering immediate reaction on blocked threadB

Note this write-up is about _immediate_ reaction in a _blocking_ thread B.

If B is not blocking, then reaction can’t be immediate.

1) If executing thread A calls “threadB.interrupt()”, B sometimes gets an immediate exception. This is the original “simple thread communication”, before JDK 5 added …

1b) throwing an exception in a Callable task (on Thread A) will cause the blocking thread B to throw exception while blocking on futureA.get()

2) threadA.join() will cause the host thread B to block until A exits. When the operation in A exits, the exit will release ThreadB immediately.

I believe all of them rely on
3) wait/notify

AtomicReference = a global lookup table

As briefly mentioned in another post, an AtomicReference object is (serious!) a global [1] lookup table.

Example 1: Imagine a lookup service to return the last trade on NYSE. If 2 trades execute in the same clock cycle (rare in a GHz server), then return a Collection.

This is a lookup table with just one default key and a value which is an object’s address. A simple example, but we may not need CAS or AtomicReference here — each thread just overwrite each other.

Example 2: say a high frequency trading account must maintain accurate cash balance and can’t afford to lose an update, because each cash balance change is large. CashBalance isn’t a float (there’s no AtomicFloat anyway) but an object.

This is also a single-entry lookup table. Now how do you update it lock-free? CAS and AtomicReference.

[1] In reality, the AtomicReference is not globally accessible. You need to get a reference to it, but it’s better to ignore this minor point and focus on the key concept.

Usage of ScheduledFuture and Callable in our pricing engine

The dependency manager may have submitted 1000 requests for repricing and the engine has gotten through 300 of them. If the dependency manager knows that for example position 106 no longer needs a revaluation, it can use the future object to cancel it.

Future also gives us access to the result of the task, but we mostly use Future to cancel tasks for multithreading efficiency

FIFO read/write lock – another home-made design

1) A writer-friendly rwlock says each writer is assigned an auto-increment queue-num (qnum), and all readers — early-birds or late-comers — all get qnum = -1, which is behind all writers. [[pthreads]] covers this kind of rwlock.

2) A strict FIFO rwlock says each writer is assigned a queue-number (qnum), and between 2 writers, any readers all get the same qnum.

Note all rwlock implementations are based entirely on mutex and condition objects. Nothing else needed.

Naive design 1: everyone waits on the same condition. Last release will notifyAll. The head the queue is self-aware [1] and proceeds. Everyone else goes back to wait. This is inefficient IF too many waiters.
[1] How? The rwlock knows (via a private field) the qnum of the head node. Alternatively, we can use a linked list.

Design 2 (notify only the head node): have the head thread(s) wait on a head-condition; everyone else in the everyone-condition. Whoever sends notify would notifyALL on the head condition, yield, and notifyAll on the everyone-condition. Everyone wakes up but only the next thread(s) in the linked list proceeds to wait in the head condition. However, before they enter, better check if the rwlock is free — it’s possible by the time they  wake up the lock is free.

FIFO read/write lock #my take

A simple counting-semaphore-based reader/writer lock is unfair.

I proposed long ago that we initialize a large number (2000+, up to max long integer) of permits for each lock instance, and require the writer to block to acquire all the permits in one go. As stated on P89 [[Pthreads programming]], such a design is unfair to writer, as a troop of readers can circulate a token among themselves, A passing to B, passing to C, passing to D … and the writer will wait forever even if it arrives on the scene just after A, and before B, C, D… Note the token is not a permit or a lock, just some object represent a “turn”. When Reader Thread A leaves the scene, A releases the Permit, but only After B takes up another Permit. At any moment in time, there’s some permit owned by the readers. The writer is starved unfairly.

One idea is incremental acquisition by writer, who acquires all the free permits ASAP, and waits to grab A’s permit. I feel this is susceptible to deadlock. It also (fairly or unfairly) disables the “shared read” functionality.

A more fair design puts the candidates into some kind of FIFO queue, perhaps a simple linked list. This tentative design uses 2 condition variables (and 2 associated locks). Whenever the RW lock becomes completely free (all permits freed), a signal is sent by the last returning thread, on the rw_free condition. In contrast to the simple design, there’s only one (special) waiting thread on that condition — a messenger thread, who wakes up and then notifies the first thread in the queue, before going back to wait(). In fact, all the queue threads (to be capped at 200) are waiting on the same queue condition, but only the FIFO queue-head thread is allowed to proceed, while others re-enter wait().

A new reader candidate joins the queue if any, otherwise grabs a permit and proceeds.

A new writer candidate joins the queue if any, otherwise determines if lock is completely free. If not free, then it starts the queue. Queue can be started by writer only.

Once a writer leaves the queue, does its job and frees all permits, all the readers before the next writer proceeds to leave the queue.

The queue holds Nodes, each having a pointer to a thread handle — a java Thread instance or a thread id in C. Any thread returning from wait() would check the queue to see if its own thread handle equals the queue-head’s thread handle.

(A tentative design.)

FIFO read/write lock from a java book (multiprocessor)

I feel this is similar to the simple algorithm in wikipedia.

A design adapted from P186 [[art of multiprocessor programming]]. I found a few bugs in the original. The http://www.elsevierdirect.com/companions/9780123705914/exercises/05~Chapter_08.zip site actually confirmed my suspicions.

However, I don’t know how to test it.

My Adaptations
– await() before readAcquires++.
– perhaps multiple condition objects for different conditions.

Basic ideas —
* Use a private lock (plock) to guard the counters this.readAcquires and this.readReleases, which are updated by readers.
* (first) writer thread if unsuccessful would set flag this.writerIsPending
** subsequent readers block in while(writerIsPending){cond.await(); }before readAcquires++.
** subsequent writers block in while(wlockAcquired){cond.await(); }
** both block in await() rather than busy waiting
* invariant : readReleases <= readAcquires
* how many conditions? 1

/* Created on January 9, 2006, 7:39 PM
*
* From "Multiprocessor Synchronization and Concurrent Data Structures",
* by Maurice Herlihy and Nir Shavit.
*
* Modified ...
*/
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;
public class FifoReadWriteLock implements ReadWriteLock {
    private int readAcquires = 0; // read acquires since start
    private int readReleases = 0; // read releses since start
    private boolean writerPendingOrRunning = false; // writer present?
    private final Lock lock = new ReentrantLock(); // short-term synchronization
                                                   // one condition for multiple purposes?
    private final Condition cond = lock.newCondition();
    private final Lock rLock = new ReadLock(); // readers apply here
    private final Lock wLock = new WriteLock(); // writers apply here
    @Override
    public Lock readLock() {
        return rLock;
    }
    @Override
    public Lock writeLock() {
        return wLock;
    }
    private class ReadLock extends AbstractLock {
        public void lock() {
            lock.lock();
            try {
                while (writerPendingOrRunning) {
                    try {
                        cond.await();
                    }catch (InterruptedException ex) {}
                    readAcquires++;
                }
            }
            finally {
                lock.unlock();
            }
        }
        
        public void unlock() {
            lock.lock();
            try {
                readReleases++;
                if (readAcquires == readReleases)
                    cond.signalAll();
            }
            finally {
                lock.unlock();
            }
        }
    }
    private class WriteLock extends AbstractLock {
        public void lock() {
            lock.lock();
            try {
                while (writerPendingOrRunning) {
                    try {
                        cond.await();
                    }catch (InterruptedException ex) {}
                }
                writerPendingOrRunning = true;

                while (readAcquires != readReleases) {
                    try {
                        cond.await();
                    }catch (InterruptedException ex) {}
                }
            }
            finally {
                lock.unlock();
            }
        }
        public void unlock() {
            writerPendingOrRunning = false;
            cond.signalAll();
        }
    }
}
abstract class AbstractLock implements Lock {
    public void lockInterruptibly() throws InterruptedException {
        throw new UnsupportedOperationException();
    }
    public boolean tryLock() {
        throw new UnsupportedOperationException();
    }
    public boolean tryLock(long time, TimeUnit unit)
        throws InterruptedException {
        throw new UnsupportedOperationException();
    }
    public Condition newCondition() {
        throw new UnsupportedOperationException();
    }
}

kill a stuck thread using SureStop – practically

Suppose you suspect your thread is stuck in a nonresponsive I/O call, or a super slow and unnecessary compute job, or more importantly a *deadlock*, you need to restart JVM. However, in some contexts you have a lot of other healthy threads doing useful work halfway, so you don’t want to lose those. You want to terminate that thread.

First get a thread dump and try to detect the deadlock cycle by inspection. In “some” cases you can see signs of deadlock, so how do you kill a thread that’s holding a lock?

Well, usually the lock is held for a reason, often to prevent access to a guarded object in an inconsistent state. In that case you don’t want to risk your system *integrity* by killing the thread and exposing the inconsistent object.

Suppose you know it’s ok and want to kill the thread, here’s one proposal.

A server often has a GUI admin console showing the live threads. Thread objects register in a static lookup table, so the GUI can monitor and show their status, perhaps by JMX. On GUI, hit “kill” on the target thread. Now the admin thread will get the Thread object from the lookup table and use the SureStop utility to kill it.

Another solution — remote debugging with authentication. This gives you direct access to suspend any thread or terminate it.

Doug Lea’s 3 chapters

Doug Lea’s book consists of 1 overview chapter and 3 specific chapters, organized around 3 challenges and 3 java language features

· Exclusion and locking
· State dependency and wait/notify
· Thread creation

In financial apps, locking seems to be much more relevant and visible than wait/notify. It’s possible that wait/notify plays absolutely critical roles in critical financial apps, but I don’t know any.

By remote debugging, I see wait/notify exists behind the scene in low-level concurrency routines, but finance developers seldom need such knowledge.

Thread-safety, consistency, races and exclusion is primarily achieved by locking. Other exclusion techniques are much less used, and includes
* thread-safe collections
* threadlocals
* immutables

According to the Stanford lecture, it’s absolutely clear that semaphores are low-level constructs and can implement “synchronized” keyword. It uses notification to implement lock release. Simplest railway semaphore is a (binary) light that turns *on* to inform multiple waiting trains. Terminology warning — in this case,
* signal or notify means release lock and inform all blocking threads. Object.notify() means (after getting the lock) inform all threads in the waiting room, without releasing lock
* “wait” means attempt to grab the lock. Object.wait() means (after getting the lock) enter waiting room and release the lock, and upon wake-up, grab lock again and return from wait().

2 threads using a singleton servlet

Get this into your blood — 2 threads can simultaneously run the same instance method (un-synchronized) of a singleton, on separate processors.

* Only 1 copy of the method throughout entire memory — Say method1() is at memory 0x289c2. No difference between static or instance methods
* each thread knows 0x289c2 and keeps a private instruction counter.
* Only 1 object in memory
* for a non-static method, threads access 0x289c2 only via the object. A thread can't invoke method1 without a pointer to the object.

A thread is… (loosely) a call stack. Each method call can access various objects in memory. Objects live on HEAP not STACK.

Very loosely, you can think of each servlet as a singleton. Hundreds of concurrent call stacks (on separate processors) have access to this object. Object should avoid mutable fields.

Future.java designed for …

IMO, Future is designed for

* cancel, if pending i.e. not completed
* retrieve return value of a callable task, if completed
* detect exception thrown on the worker/executor thread.

3 tricky requirements! For any one of them, Future.java is the standard solution.

The CompletionService javadoc shows that a Future can represent either a 1) pending or 2) completed task.

wait/notify, yield and green thread

(taken from some website)

Scheduling is more of a worry for programs with green (simulated) threads that run in tight loops or that spend significant amounts of time running mathematical computations with no I/O. In those cases, a simple call to Thread.yield() is enough to give other threads of the same priority a chance to run.

To share the CPU with a lower-priority thread, a thread can call Thread.sleep() or, more precisely, call wait() on an object until the low-priority thread signals the end of its run by calling notify() on that object.

consistency vs liveness — 2 concurrency issues

2 main risks of concurrency: consistency ^ liveness

([[concur programming on windows]] also singles out these 2 “hazards”)

Concurrency risk with collections? Race condition (inconsistency problem) is the main risk.

While Consistency is explained in other posts, Liveness is still vague at this stage of my understanding. One way to define it is “every thread should make progress”. No waiting forever, no permanent blocking. No deadlock.

Now the upshot. To prevent inconsistency, use locks everywhere, but locks affect liveness.

Atomic variables and thread-safe collections [NO NO NO] seem to be an alternative.

Now I think thread-safe collections are a liveness hazard and can increase chance of deadlocks, because they use locks. Locks are by nature
* exclusive
* u must wait for them, potentially forever.

Single-threaded execution is free from consistency/liveness issues. If you synchronize and serialize too much, you might achieve (but hard to guarantee) consistency but your liveness may be worse than single-threaded due to blocking.

single-thread thread-pool

newSingleThreadExecutor()

Creates an Executor that uses a single worker thread operating off an unbounded queue. (Note however that if this single thread terminates due to a failure during execution prior to shutdown, a new one will take its place if needed to execute subsequent tasks.) Tasks are guaranteed to execute sequentially, and no more than one task will be active at any given time. Unlike the otherwise equivalent newFixedThreadPool(1) the returned executor is guaranteed not to be reconfigurable to use additional threads.

objects (in addition to methods) on a call stack

In my previous java debugging experience, the call stack is often perceived as a stack of method calls. Since most of the methods are non-static, why don’t we care about the receiver (and caller) objects of these calls? I think it’s because we don’t need to.

Now, in multi-threaded, the objects making/receiving the calls are relevant.
* Frequently threads lock on those objects.
* Also the object states could get corrupt.
* wait/notify can use these objects as waiting rooms

See P287 of Doug Lea’s book.

practical use cases of wait/notify@@

* most efficient blocking consumer/reader. See post on simplest wait/notify app.
* After finishing tasks, idle threads in thread pools wait in awaitNanos(), the new version of wait()
* callback, listeners
** callback — from server thread to client thread. Async. Client thread can wait()
** GUI event handler?
** listener. See the post on callback. Swing event queue thread waits in wait().
** event dispatcher thread — RV and swing use such a thread. I think this thread blocks in wait() when it has no event to process.

* producer/consumer — consumer can wait() when the queue is empty. producer can wait() when the queue is full. If you use BlockingQueues then u probably don’t need to call wait() yourself, and you don’t need to hold any lock. This (ie wait/notify) is especially appropriate in situations where threads have a producer-consumer relationship (actively cooperating on a common goal) rather than a mutual exclusion relationship (trying to avoid conflicts while sharing a common resource).

* Any time you want one thread to initiate and another thread to react (thread communication), the reacting thread will need to block when there’s nothing to do. Sleep-poll loop is inefficient. wait/notify is the standard solution

simplest wait-notify app


String consume() {
synchronized (queue) {
while (queue.size() == 0) {
queue.wait(5000);
}
return queue.remove(0);
}
}
void produce(String s) {
synchronized(queue) {
queue.add(s);
queue.notify();
}
}
// entire test program is
public class WaitNotifyDemo{
final private List queue = new ArrayList();
final private Random rand=new Random();
public static void main(String[] args) {
final WaitNotifyDemo instance=new WaitNotifyDemo();
//an anon class implementing Runnable, passed into new Thread() as constructor arg
Thread t = new Thread(new Runnable(){
public void run() {
for(Integer i=0;i<100;i++) {
instance.produce(i.toString());
try {
int sleep = Math.abs(instance.rand.nextInt()%5000);
Thread.sleep(sleep);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
});
t.setName("producer");
t.start();
new Thread("consumer"){
public void run() {
for(;;) {
String item = instance.consume();
}
}
}.start();
}

String consume() {
synchronized (queue) {
while (queue.size() == 0) {
try {
queue.wait(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(Thread.currentThread().getName() + "] either timeout or notification happened");
}
String a= queue.remove(0);
System.out.println(Thread.currentThread().getName() + "] notification received. removing " + a);
return a;
}
}
void produce(String s) {
synchronized(queue) {
System.out.println(Thread.currentThread().getName() + "] notifying after producing " + s);
queue.add(s);
queue.notify();
}
}
}

synchronized static init block@@

I vaguely remember a static init block can have “synchronized”. I guess 2 threads might (in theory) run the block concurrently.

But each classloader (and all its ancestors) can only load a class once, so i guess the 2 threads will load the same class into separate class loaders that aren’t in parent-child@@

reference type volatile fields in java

Most volatile fields I know are primitive. What’s the usage of reference type volatiles? http://www.ibm.com/developerworks/java/library/j-jtp06197.html has several examples. One is on partial object.

I think JVM guarantees to finish object instantiation and save the pointer in the volatile field in one atomic step, so another thread reading (dereferencing) this volatile reference will never see a partial object? Now I feel without volatile, reader can *see* stale image of an “under-construction” state of the object like a half-built mosque, even though by now the writer has finished construction on the heap.

Partial-object breaks double-check locking. See P 86 [[java threads]]. 2nd thread may see foo != null when the foo object is partially constructed.

poll^interrupt: 2ways to cancel threads]any lang

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Thread.html#stop() officially recommends these 2 ways, echoed by [[java threads]]

“Many uses of stop should be replaced by code that simply modifies some variable to indicate that the target thread should stop running. The target thread should check this variable regularly, and return from its run method in an orderly fashion if the variable indicates that it is to stop running. If the target thread waits for long periods (on a condition variable, for example), the interrupt method should be used to interrupt the wait.”

Unix signal is conceptually similar to interrupt.

 

sleep() ^ yield() ^ wait()

Feature 1: does the thread let go of CPU@@
Feature 2: does the thread release lock@@
Feature 3: which real-world thread is affected? current call stack or another thread in an argument?
Feature 3a: is any Thread object explicitly mentioned? as arg or host object?
Feature 4: What objects are involved?

myObj.wait() is most complex:
1) yes
2) exactly 1 and only 1 lock (myObj), even if the thread holds multiple locks
3) current thread only
3a) none.
4) an object to serve as the waiting room

sleep() is simple:
1) yes
2) no, even if holding n locks
3) current thread only
3a) none. this is a static method.
4) No object involved. Thread.sleep() is a static method

yield() is similar to sleep()
4) No object involved. Thread.yield() is a static method
3) current thread only
2) no, even if holding n locks
1) yes

simple race condition illustration

Simplest eg: consider 2 threads both running counter++ on a shared variable.You expect counter to increment twice but it may increment once.

Key factor: the operation is not an (so-called atomic) one-stepper. counter++ is a “load-and-store”. It’s not *atomic*. Between the steps, another thread can change the shared variable.

For a bigger example, consider a web page hit counter.

java thread pool(phrasebook

* Runnable.java — the tasks/jobs lined up are objects implementing Runnable.java. It’s counter intuitive to me that the threads in the pool by definition implement Runnable.java, and the jobs also implement Runnable.java — see blog post [[ wrapper object of “me” as a field in me ]]

* queues — i think thread pools need a FIFO queue to hold the jobs/tasks. Usually it’s a blocking queue.

SureStop and Thread.stop()

SureStop.java from Paul Hyde seems to be fairly professional[1] and robust. But I wonder how it avoids the deadly pitfalls of Thread.stop()? Answer is in the post on unlock@thread death

[1] Paul even included a test.

Sometimes we do want to forcibly kill a runaway thread. Look at Pushmail. Also,

* a thread stuck in an infinite loop
* a thread blocked in IO
* a thread trying to acquire a lock
* deadlock

Many useful implementation techniques
– SureStop.java is Based on the simple self-running object. In fact SureStop is an extremely simple implementation of a simple idea, given the power it has. Simplicity is power.
– uses highest thread priority to avoid starvation.
– daemon thread

##20 specific thread constructs developers need

Hey XR,

We both asked ourselves a few times the same question —
Q: why multi-threading java interview questions touch on almost nothing besides synchronized, wait/notify + some Thread creation.

Well these are about the only concurrency features at the language level[1]. For an analogy, look at integrated circuit designers — They have nothing but transistors, diodes and resistors to playwith, but they build the most complex microchips with nothing else.

I feel the 2nd level of *basic*, practical concurrency constructs would include

* basic techniques to stop a thread
* event-driven design patterns, listeners, callbacks, event queues
* nested class techniques — rather useful in concurrent systems
* join()
* deadlock prevention
* timers and scheduled thread pools
* thread pools and task queues
* concurrent collections
* consumer/producer task queues

More advanced but still comprehensible constructs
* interrupt handling
* reader writer lock
* exclusion techniques by using local objects
* exclusion techniques by MOM
* immutables
* additional features in Lock.java
* Condition.java
* futures and callable
* latch, exchanger, barrier etc* AtomicReference etc, volatile
* lock free
* counting semaphore

[1] 1.5 added some foundation classes such as Lock, Condition, atomic variable …

3 notifyAll limitations — solved with conditionVar??

Classic Object.notifyAll()
* can’t control which subset of waiting threads NOT to wake up.
* cause every thread to wake up and grab the lock, even if only some of them should.
* can’t select a single thread to wake up

Can we solve these problems by having each waiting thread use its own condition variable? Save these condition instances in a global array. Notifier can then choose one condition instance? Any scheme involving shared collection (like this global array) of condition instances requires care and feeding as access to the shared collection need synchronization.

I think condition variable is designed to be 1 : m : mm i.e.

   “1-lock/m-conditions and 1-condition/m-threads” — not 1-condition/1-thread

Condition.java API gives an example of 2 conditions on one lock. There’s another sample code P168 [[java 1.5 Tiger, A developer’s notebook]]

pattern – start thread in constructor#briefly

This is an important element of many concurrency designs.

Q: is it good to instantiate threads in a constructor?
%%A: better be careful. I try to shorten my constructor *call* including any method calls made from my constructor.

Q: is it good practice to start a thread in a constructor?
%%A: i avoid it. On a multi-core machine, the new thread could do any amount of work before the constructor returns. Until then, the half-constructed object is invalid, hazardous and should be untouchable.
%%A: I notice this is fairly common practice.
A: Actually, std::thread ctor “starts” the kernel thread i.e. makes it Eligible to receive time slices.

Q: best practices for writing constructors for a Runnable? should a thread object maintain state — must be initialized

Runnable vs subclass of Thread

Fairly trivial implementation question

Thread derivatives [1] permits instance field ie state. Semantics of these Thread fields are confusing and should be avoided. If you don’t want to permit thread instance fields, then use Runnable.

[1] including anon thread class

CyclicBarrier and multi-processor parallel decomposition

One of the simplest yet most useful ways to utilize multi-processor hardware for *iterative* jobs is the cyclic barrier.

* Not for recursive problems. If your requirement is recursive in nature, there are other techniques of parallel decomposition.

** Sometimes (as in low-latency systems), we convert recursion into iteration for memory efficiency, without losing parallelism, on a multi-processor hardware. Note memory is critical in low-latency, for a number of reasons.

* segmentation

Q: how is a barrier different from a count down latch?

stateful^stateless Thread objects

Q: Say you have a Thread (either from a Runnable or Thread subclass). Is it good practice to remove all fields and make it stateless?

Obviously thread scheduler keeps state of the jvm thread, but application need not know those, and such state info is not exposed to the Thread object. As highlighted in other post, a Thread object is a poor handle on a real jvm thread…

Volatile boolean fields are popular, but must they be a field in the Runnable or Thread subclass?

I think ThreadLocal is implemented as an instance field of a Thread object. See http://stackoverflow.com/questions/1202444/how-is-javas-threadlocal-implemented-under-the-hood. As such it’s a stateful object inside a Thread object.

Let’s bear in mind any non-final field [1] in a Thread or Runnable can be modified by any (jvm) thread — Complex semantics. To simplify modeling[2] and semantics and improve maintainability, I’d avoid custom stateful Thread objects.

[1] or final reference field except String
[2] state ie instance fields are fundamental to OO modeling

Locking is all about state consistency, ie state of domain objects . There’s already enough state to complicate concurrent systems, even if our Thread objects are stateless.

threads and inner classes

Many programmers aren’t comfortable with nested classes or threading. Good to familiarize with common and uncommon usages. I feel concurrent OO modeling is more complex. May call for unusual modeling constructs such as nested classes.

* Anon classes are extremely widespread in concurrent programs.

* [[java thread programming]] details an active class that hides run() method, which is always public, using inner class. However, state can become complicated. Is it better to make these nested class stateless? I think so.

init method vs constructors

I usually start with and stick to constructors, and avoid creating init() until i see justifications such as
* multiple constructors need to share some initialization code. You can have init1(…), init2(..) as lego’s to be used by these constructors.

* init(..) can have weird arguments, unsuitable for constructors.
* constructors constraints — must call super(…) as*first* statement
* Spring init-method won’t work with constructors??

* a special justification in a multi-threaded context
All my constructors try to quickly button up the object and return. Before a constructor returns, the object is invalid. If a constructor creates a thread that thread might access this invalid object. You can put crazy things (DB, network access…) into init(), and you can choose to call init() after (or before?) a constructor returns.

callable tasks, simple thread pool set-up, shutdown, awaitTermination

What you added to task queue should not be a simple POJO or java bean. It needs a run() or call() method.

public class DualThreadPool {
//* Construct a thread pool (size 2) with an internal unbounded queue
private final ExecutorService eService = Executors.newFixedThreadPool(2);
private void addTask(Callable task) {
assert task != null;
this.eService.submit(task);
}
public static void main(String adfs32[]) throws FileNotFoundException, InterruptedException {
DualThreadPool pool = new DualThreadPool();
pool.addTask(new FileParserTask(Downloader.download("<a href="http://www.google.com/" target="_blank">http://www.google.com/</a>", ""), true));
pool.addTask(new FileParserTask(new FileReader("c:/windows/ie7.log")));
pool.eService.shutdown();
pool.eService.awaitTermination(22, TimeUnit.SECONDS);
MultiCounter.instance.dumpCounts();
}
}

y we need threads, my take

1) GUI — need lots of threads
one thread to process user input. might block
one thread to return data to screen
one thread to send email
one thread to save data. might block
one thread to call a web service. might block
Paradoxically, all major GUI toolkits are single-threaded in terms of screen resources.

2a) network servers such as servlets, market data subscribers — multiple concurrent connections. A single thread can hardly handle them concurrently (even though NIO can help)
** nonblocking IO?

2b) database server — multiple concurrent users. but often multi-process is a viable alternative to multi-thread. What if one server machine needs to support 500 concurrent users?
) async. MOM is one example. onMessage() often runs on its own thread.
) alarms and timers?
) complete a long task faster, in parallel, like in number crunching or large database operations
) multi-processor machines -> higher throughput
** Suppose we take periodic snapshots of hardware threads and count how many are busy and how many are idle. Most of the time these threads aren’t simultaneously busy.

Note many of these needs can be satisfied with multiple processes. Therefore there’s a constant question to be addressed — “why choose threads”. Answer is obvious so I won’t elaborate — data sharing, light-weight…

digestible insights on servlet threading

Background: we learnt servlet threading many times but still didn’t internalize it. Let’s distill into single-word keywords.

* objects in application-context are obviously thread unsafe. Before you consider session scope or servlet instance vars, consider application-context
* session scope objects can be modified from 2 browsers. This is more digestible than servlet instance vars.

Now let’s distill the digestible insights on servlet instance var.

* one servlet instance 1:m multiple threads. This is the final knowledge pearl.
* this 1:m is the prevalent set-up. 1:1 is rare

private/public void run()

What if you want to wrap some existing logic in a public void run() method in your class so you can pass its instance to “new Thread(instance)”, but you don’t like the “public” access to that method? One solution is to wrap that logic in a privateRun() method. When you need to construct a new Thread(instance), you do a


new Thread(){
public void run(){
instance.privateRun(); // anon inner class calling enclosing class's private method
}
}

I think in threading, you end up with lots of nested classes

primitive thread communication in practice

Threads can share any data in may ways, but there are some standard patterns to send primitive signals to each other, without any content. These are simple techniques, widely used, battle tested.

* wait/notify [3] – general purpose
* interrupt [1] [3]
* boolean done flag [1]
* join [3]

How about swing?

java.util.concurrent offers a few communication devices. These are not primitive.

[1] these are the 2 standard ways to inform [2] a thread stop itself. See the Thread.stop() api http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Thread.html#stop()

[2] from outside the thread ie another thread.

[3] These techniques cause the receiving thread to act immediately. Shared-data techniques need the receiving thread to poll the shared data.

always surround wait() with a while() loop

Wait() is always awakened by a notification message sent to the monitor object.

Between the notification thread releasing the lock and the waking thread acquiring, a third thread can modify some shared data[1], and the condition you are waiting for disappears as a result.

Therefore the waking thread need to recheck the condition. if() won’t do[2]. while() is required.

If you know there is no 3rd thread messing with the condition, then the waking thread can assume the condition is still intact. However, this design unnecessarily weakens code extensibility and re-usability. It’s fairly easy to put a while() loop around a wait(). No good reason not to do it.

[2] This kind of bug is intermitten.
[1] in a database for example (a crude example)

notifyAll() sending event data to waiting threads

Q: notifyAll() wakes up all waiting threads. How nice would it be if you can send some message to them so they know whether to stop waiting?

A: since notifyAll and wait are called on the same object, that object is usually the best message carrier. If you want, you can put in a setNotificationMessage()/getNotificationMessage(). You can use HASA to link this object to any other data object.

another look at swing event handlers

There are 2 distinct threads that interact in very restricted ways. Note the terminology
– METHOD is a compile-time, almostJ
– OBJECT is creation/event time
– CALL is always runtime
C) Thread C CCCreates the (event handler or) listener OBJECT. Often some reference objects (in the form of final arguments) are passed to the creator CALL (not  “method”) at Setup time. Creator passes them to the new event handler OBJECT (not “call”). At Setup time (not event time), event handler OBJECT (not “method” or “call”) has a copy or reference of those reference objects. This is all set up on Thread C. If the event never happen, then the event handler method never becomes a call.
E) Thread E dispatches the EEEvent to the handler OBJECT. In the handler CALL (not “method”), those reference objects are already there, not passed in at event time, and not passed on Thread E. A reference object is like a special device pre-installed in a James Bond car, available at event time.
Note the event handler OBJECT is really a wrapper-over—function-pointer with an invisible-field-for-each-reference-object. Each reference object passed to the creator CALL is stored in the handler OBJECT as an invisible instance field.
An event handler object is stateless and immutable since it can only have invisible fields.
The reference objects hold business data and are actively shared between Thread C and Thread E. Both threads can modify state of those reference objects.
      protected StructureEditAction createOfferingStructureEditAction (final Vector updaterList) {
            // this new() runs on Thread C
            return new StructureEditAction () {
                  // at creation-time, the implicit no-arg ctor saves updaterList as an invisible field. 
                 // This field is never needed until event-time
                  // this method runs on Thread E

                  public void startEdit (KeyEvent e) {

                        Iterator iter = updaterList.iterator ();
                        while (iter.hasNext ()) {
                              Object obj = iter.next ();
                              if (((OfferingUpdate) obj).isUpdatingColumn ((JTable) e.getSource ())) {
                                    ((OfferingUpdate) obj).startEdit (e);
                              }
                        }
                  }

threadpool && GUI examples, showcasing anon class

Get used to this kind of coding style. In this case I don’t see a good reason for the anon class. It’s more readable to pull it out into a named static nested (or top-level) class.

However, in real life the anon class’s methods often need the variables in the enclosing class. Anon is quick and dirty.


public static void main1(String args[]) {
new ScheduledThreadPoolExecutor(1).scheduleAtFixedRate(new Runnable() {
public void run() {
System.out.println(new Date());
}
}, 0, 1000, TimeUnit.MILLISECONDS);
}

// Now see the same pattern in this GUI code:

ActionListener taskPerformer = new ActionListener() {
public void actionPerformed(ActionEvent evt) {
//...Perform a task...
}
};
new Timer(delay, taskPerformer).start();

Callable tasks, Future results

A few learning notes based on P196 [[Java Threads]]. See also
http://bigblog.tanbin.com/2010/07/futurejava-designed-for.html
http://bigblog.tanbin.com/2009/05/callable-tasks-simple-thread-pool-set.html
http://bigblog.tanbin.com/2011/01/exception-passing-between-threads.html

Callable is an enhanced Runnable. Whenever possible, I’d design with Callable rather than Runnable. However, Callable doesn’t extend Runnable. For example, there’s no “new Thread(Callable)”.

Q: Does it make sense to implement both Runnable and Callable interfaces, so my class can be used in both contexts?
%%A: conceivable.

Q: Can this technique be used to convert existing Runnable designs to use Callable, assuming run() calls call()?
%%A: you might find it troublesome to get the task output (either result or exception) when you use the task object as a Runnable.

A Future object represents the result of a task. I feel it’s a window into that real world task in JVM. The (either real or symbolic) task is *stateful*.

I think of the “future” construct as a concept first. It represents a yet-to-complete async task. It could be ready when you read it. As such, I think it’s implemented using condVars.

FutureTask (like SwingWorker) is one of the implementations of Future interface.

Just as a Thread is a (rather imperfect) handle on a JVM thread, a Callable object with the corresponding FutureTask object are handles on the real world task.

y synchronized block !! method

Q: problems with synchronized methods? (It’s definitely easier than synchronized blocks, so most of us prefer it.)

A1: keep it simple.

As a rule, avoid holding more than 1 lock simultaneously. The longer you hold the lock, the tougher this rule becomes.

Somewhere in your method you might call an innocent-looking method and all hell breaks loose.

During the critical period your thread1 holds a lock (any lock), you want thread1 to avoid getting involved with any other lock. Analogy: when you are married, avoid getting involved with another person of the opposite sex.

A2: Deadllock is one of the risks and it’s extremely tough.

A3: performance. Over-serialization defeats concurrency.

A4: Suppose you use synchronized (lock1). The longer you hold the lock, the more likely you are to do stupid things like lock1=getAnotherObject(). See [[Practical Java]]

wrapper object of "me" as a field in me

Interesting thread pattern.

Usually the wrapper object is a different class containing a field holding the wrapped object, but In this example, …. see comment below. What’s the motivation? In a thread pool, I think this is how a task (implementing Runnable.java) from the queue is assigned a thread from the pool.

In memory, the thr object and THIS object hold pointers to each other. “wrapper” is misleading term. wrapper is a one-way HAS-A relationship.

In an object graph (at GC time), you often find 2 objects connected both ways, but in this case the 2-way linking is extremely barebones. Tight-coupling?

class MyThr implements Runnable{
Thread thr; // ----> a field but also a wrapper of this object
MyThr(){
this.thr = new Thread(this);
this.thr.start();
}
...
}

Thread object as a lock object: myThr.wait()sometimes useful

Someone (HSBC?) asked me what happens if I call myThread.wait().

MyThread thrd = new MyThread();
thrd.start();
synchronized(thrd){
 thrd.wait(); // similar to thrd.join()
}

Using a Thread.java object as a monitor object is legal, but not advisable. Unlike c++, java has no undefined behavior, so the behavior is probably “defined” in the java language spec. I guess the behavior is that main thread waits in the “waiting room” of the thrd object, but who will notify main thread?

My experiment shows that main thread actually gets notified when thrd ends. Before we uncover the mysterious notifier, let’s remember that it’s unusual, confusing and never necessary to use a Thread.java object as a lock. There’s always a simpler alternative.

If you really use a Thread.java object as a lock/conditionVar, there are hidden issues. Here’s one issue I know –

As a condition variable, a Thread.java object has the undocumented behavior of calling this.notifyAll() when it dies. Someone speculated — “In fact this is how the join() method is implemented, if I remember correctly: it waits on the thread object until it dies.” Note join() is an instance method of an Thread.java object. When main thread calls thrd2.join(), it treats thrd2 as a conditionVar and waits on it until another thread calls thrd2.notifyAll(). Notifying thread is actually the thrd2 itself.

java reentrant lock – key phrases

* seedless banana — all bananas are seedless. I believe most (All?) locks are reentrant. Lock interface has only 3 implementers.

* backward compatible — reentrant locks behave as [1] the synchronized keyword. So the reentrance feature is nothing new, just like “seedless” is nothing new for banana.

[1] Lock.java does offer a few more features such as unlock, lockInterruptibly and tryLock

* unacceptable design — i think many people talk about non-reentrant locks — if myThr already obtained lock1, and need to acquire it again, then the thread blocks!? but i think there’s no such non-reentrant lock in java. It’s an unacceptable design.

top 3 key nlg pearls on thread methods

A: wait(), lock()

#1. Each of the Thread object’s static/non-static methods must execute in a call stack — ie a real thread, and this real thread can be unrelated to the Thread. You should always ask “Is this Thread method affecting the call stack (ie the real thread) ?”

#2 Q: Many other methods (sometimes designed to) affect their call stack, but are not defined in Thread.java. Example?

thread quizzes+paradoxes

Q: class SimMessageConsumer extends Thread and overrides run(). In my main() method, i instantiate myThr1 = new SimMessageConsumer() and call myThr1.run(), on which thread does run() run?
A: on the main thread. The real world thread linked to myThr1 is not yet created by VM. That happens when you call myThr1.start().

As stated in another post, a Thread object is a poor handle on a real VM thread.

Q: if MyThread defines a (static or non-static) method m1(), and I call m1() from main(), on which thread does m1() run? Note this is not best practice. Avoid defining any other methods in a Thread derivative.
A: main thread.

anyObject.wait(maxDuration)^ static Thread.sleep(howLong)

It’s instructive to compare these 2. See P71 [[Java Threads]].

During sleep(), the sleeping thread doesn’t release lock. In fact, sleep() is a static method with no object mentioned.

I think *inside*[1] the myObj.wait() JVM takes the lock off the current thread. Immediately before/after wait(), current thread must possess the lock on myObj. thread blocks until this happens.

[1]right after we enter myObj.wait() and right before we exit myObj.wait().

interrupt() — 2 real threads, 1 Thread object

myThread.interrupt() methods involves 2 real threads. As another post mentions, each real thread has a rather poor handle on it in the form of a Thread object. In this case, one such object is involved — the target thread object. So the real and fake thread thingies involved are

A) the real sender thread (thread23) — the call stack containing the method (sendInterruptMsg()) that sends the interrupt() message
C) the target thread object — myThread object.
B) the real target thread — the thread accessible by myThread object, potentially executing some blocking method.

void sendInterruptMsg(){ // runs in thread23
myThread.interrupt()
}

Note, in this case, the thread object is not a poor handle on the real thread, but a solid handle on the real thread. There are very few such useful instance methods in a thread object though, that’s why i say thread objects are a poor handle on the real threads.

Next thing to learn is the exception thrown as a result of the interrupt.

Q: Which real thread (stack) will generate and receive the exception?
A: (B), not C, since the thread object is NOT a call stack and can’t deal with exceptions.

Q: which method will throw it?
A: the interrupted method. Note all other exceptions are triggered by actions by the call stack itself — synchronous. But InterruptedException is triggered by a lightning strike — asynchronous.

Q: what methods can be interrupted this way?
A: blocking methods. Any method that can be interrupted must declare “throws InterruptedException”. Actually there are very few such methods, so they are important — static Thread.sleep, myObject.wait()…

blocking methods susceptible to interrupt

interrupt() can be used to interrupt many blocking method. See P 29. Exactly what blocking methods? If you find a simple rule on this, probably it’s not completely trust-worthy. [[ java threads ]] isn’t clear. P 169 [[ concurrent programming in java ]] is better.

— blocking methods susceptible to interrupt(), based on my understanding
sleep()
wait() P29
a socket’s read() method
join() P27
Any method containing “synchronized”? NO. See Lock.lockInterruptibly()

pthreads also defines several “cancellation points”

multi-threaded java is everywhere

Q: In what areas must you deal with multi-threading? ranking in terms of importance
* swing is multi-threaded@@ I think so since GUI is inherently multi-threaded
* To exploit multi-processor. eg: Mansion’s T2 — 1 processor, 8 core, 32 native kernel threads
* Every java IO system

# eor
* applets are often multi-threaded@@
* Hibernate@@ I think so because each database transaction (a unit-of-work) maps to a session and a thread. See other posts
* XP: NextGen is multi-threaded
* Every servlet/JSP is by default multi-threaded
* Most database-backed java applications are multi-threaded. Every DB-connection is often used by a single thread. A db-transaction is associated with a connnection.
* I think most online transaction systems are multi-threaded, but how about before java?

Personal observations on the above scenarios:
#1 common characteristic: each thread is basically a call stack
But these threads don’t always share a lot of data
Not much deadlock worry

thread-safe JSP

Q: You know “session attributes” and “application attributes” aren’t thread-safe ie 2 threads can access the same data at the same [1] time. So what do you do?

%%A: synchronize each and every single method accessing them. Do that in every servlet. See P200, 197 [[ head first servlet ]]

%%A: Now i think it’s easier to use a database. Even a careless servlet becomes safe. Databases are concurrent, even before servlets were invented.

[1] in exactly the same clock cycle if using 2 of the 32 processor threads like in Mansion’s T2000 servers

In java, volatile means ..

In this post we avoid when-to-use-volatile. When we say “long” we mean “long, and double, the 64bit types”.

* volatile is a field modifier
* visibility — fields marked “volatile” are never cached in a thread’s register
* Local variables (ie stack variables local to a method) are different from fields. Local variables are never shared with other threads so never need volatile modifiers

**** volatile long/double:
– is permitted by compiler
– volatile has an important atomicity effect on long/double fields
–> According to 3rd edition of the Java Language specification, declaring a long field to be volatile ensures that reads or writes to it occur atomically.
–> “Unless they are declared volatile, implementations of Java are allowed to treat assignments to long and double variables as two assignments to two variables that hold 32 bits each rather than one assignment to single variable that holds 64 bits.” — http://www.mindspring.com/~mgrand/double-checked_locking_implementation.html

**** In a nutshell, volatile helps visibility and also helps (for 64bit load/store) atomicity.
1) volatile helps visibility for all primitive fields including long and double.
1.1) longer story for reference types. There’s another blog post on this.
2) volatile’s help on atomicity is limited to 64bit field’s load and store
2.1) load/store on smaller data types are always atomic whether volatile or not. Guaranteed by the Java Memory Model.
2.2) For ANY data type, Composite read/write operations (like *=, ++ ) on volatile fields can compile but are non-atomic. A float volatile field is similar to a field of type VFloat:

final class VFloat { //from http://g.oswego.edu/dl/cpj/jmm.html and P97 [[concurrent programming in java]]
private float value;
final synchronized void set(float f) { value = f; }
final synchronized float get() { return value; }
}

One of the most frequent/important consequences of 2.2 is

Q: how to avoid another thread modifying/reading such a float variable half way through my increment?” (or another composite operation)
A: volatile can’t help. Synchronize please.

consistent= consistent-with-reality

consistency means
* consistent with business reality
* P 39 [[ concurrent programming in java ]] object-consistency = “all fields and all fields of other objects on which they depend, possess legal, meaningful values”
* P 40: “An object is consistent if all fields obey their
invariants.”
* As in ACID, Consistent = consistent with reality . Inconcurrency can produce weird and unpredictable /state/
* our object should never “be seen in an embarrassing moment”. Our object is designed to expose its /state/ while interacting with clients

In multi-threading, Consistency covers race conditions, visibility, reorder, atomicity.

The essential protection against inconsistency is confinement including mutex. It’s like queuing up to enter a phone booth. Also known as mutex lock (including “synchronized”).

2 ways to create threads

(one of the most common interview questions)
 
1) … extends Thread or a subclass
override run(), to provide the job for your thread
no other compulsory methods to implement
 
 
2) myTask implements Runnable // and becomes a “task” object. Thread^task 2-object design is the idea behind Runnable.
implement run() — the only method in Runnable
but interrupt() is not inherited from Thread.java
 
    Thread thr = new Thread(new myTask()); // “insert” the task object
    thr.start();
 

open-call in FTTP loader singleton

To prevent deadlock, we took care to adopt open-call in our synchronized singleton constructor.

Basically, our long constructor (any long constructor) tend to make calls to other objects. Eventually, one of the calls that another programmer add may invoke a method that invoke a synchronized method. Now step back and count how many locks are involved.

Some may question this is over-cautious — the class doesn’t have any other static synchronized method. But Future?

Open-call is defensive design.

singleton race condition

http://www.javaworld.com/cgi-bin/mailto/x_java.cgi says

// Also an error, synchronization does not prevent
// two calls of constructor.
0) public static MySingleton getInstance() {
1) if (_instance==null) {
2) synchronized (MySingleton.class) {
3) _instance = new MySingleton();
4) }
5) }
6) return _instance;
7) }

Thread A passes Line 1
Thread B passes Line 1
Thread A gets the lock at Line 2 and releases it at Line 4
Thread A passes Line 7, sets _instance to point to a MySingleton object and returns it to caller who creates a reference to the object.
Thread B gets the lock at Line 2 and instantiates a second MySingleton.

Now both instances have reference count > 0

synchronized — main-effect^side-effect

Main effect? serialized (not concurrent) access of a block of code

Side effect? trigger a flush from register to main mem, achieving volatile's functionality. See

http://blog.tanbin.com/2007/06/volatile-briefly-visible-stale.html

Why the side effect? not important at this moment. Good to know.

There could be other side effects. No need to research.

java transaction — brief AR notes

a tx is often “managed” on the server. There’s one session per tx in server memory. But how is a XA tx managed??

a tx and a session always involve a private mem, often on server and client

a tx usually (always?) involves a SESSION. perhaps a session with the DB or MOM
a tx usually (always?) involves a java THREAD.
a tx always involves a private mem

“XA-enabled jdbc driver”?? I guess such a driver understands and responds to the commands of global tx mgr.

A Weblogic expert told me that the first phase can be lengthy as all parties fully prepare their commit and rollback infrastructure. It can fail. 2nd phase is extremely quick as the global tx mgr somehow triggers all parties (geographically distant) to perform the final step. Because this last step is extremely _simple_, it’s virtually impossible to fail.

Q: what if one of the parties fails during 2nd phase, while other parties commit.
A: looks like it is a technical possibility but known to be extremely unlikely.

volatile briefly: visible, stale

imprecise words? ok
problem ] 1 sentence: variable updates in one thread could be invisible in another.

volatile ^ synchronized? Yes synrhonized can replace volatile, but it’s nothing to do with atomicity. Synchonized getter/setters has a side-effect — trigger a flush from register to main mem, achieving volatile’s functionality

[[ java concurrency in practice ]] p34 has a simpler example than [[ java threads ]]

“update visibility”
“stale data”
read_uncommited

wait() means, to a beginner

To avoid overwhelming a beginner, the simpler meaning is “current thread please wait”.

* wait() means “current thread please wait at this statement, inside this waiting area”
* wait() means “Hey the thread executing this statement, please wait at this statement, in this object”

Note: Remember the method enclosing the wait() statement belongs to the “this” object? The “waiting area” is the “this” object.

Note: The “thread” is the real world thread, not to be confused with the Thread object returned by Thread.getCurrentTrhead()

statement re-order — within-thread^between-thread

— Based on http://g.oswego.edu/dl/cpj/jmm.html

JVM can re-order statements. “Ordering rules fall under two cases, within-thread and between-thread: “

)) “From the point of view of the thread performing the actions in a method, instructions proceed in the normal as-if-serial manner that applies in sequential programming languages. “

%% As an observer of this thread, you can ignore the re-ordering and assume that “statements appearing earlier never runs later”. Behind-the-scene shuffle will never break a single-thread spectator’s expectation.%%

)) “From the point of view of other threads that might be “spying” on this thread by concurrently running unsynchronized methods, almost anything can happen. The only useful constraint is that the relative orderings of synchronized code, as well as operations on volatile fields, are always preserved. “

synchronized protects against inconsistency?

Not always, unfortunately. After throwing exceptions, the synchronized method may leave the data in a /bizarre/, illogical, impossible state, but JVM always releases the lock automatically, and permits other threads to read/write this wierd data! For more on inconsistency, read other blog posts.

This exception issue is Arguably the Achilles’ heel of “synchronized” — perhaps the only weakness in its promised protection against inconsistency.

Luckily, Lock interface comes to the rescue. It doesn’t release the lock after an exception. However, this can create deadlocks, since the lock held is never automatically released. You need finally{}.

Conclusion: Lock interface with finally{} protects against the twin evils of inconsistency && deadlock, in the event of exceptions.

In fact, exceptions, consistency and deadlock are right at the heart of a major design challenge in JVM thread implementation. See P 123 [[ java threads ]].

thread ] NextGen

* Our system runs on SPARC and I know the new SPARC processors feature a large number of kernel threads — 32 kernel threads in T2000.
* NextGen is massively multi-threaded to deal with perhaps hundreds of concurrent sessions, each lasting 15 minutes to several hours.

* open call in constructor
* singleton in a multi-threaded environment
* promote local variables
* promote constants and immutables
* immutables as much as possible. Some things in a circuit model are updatable. Most are not, but if you don’t enforce immutability in your classes, then other objects could accidentally attempt to modify my objects’ states, posing a threading hazard.
* log4j logger ? It’s not just thread-safe, it uses synchronized methods everywhere. That means that for heavy logging log4j will induce performance bottleneck and possible deadlocks

— static fields
* EVERY static field is accessible by (true) concurrent threads.
* static fields are needed to model many characteristics of a given telecom equipment, such as …
* In my modules, static varables are mostly constants

— instance variables
* In terms of threading concerns in my modules, instance variables are trickier than static fields
* my classes use more instance variables than static fields, typically 10 – 50 in each object.
* EVERY instance var is, by default, open to hazardous concurrent access
* System was designed to assign 1 thread to each “trouble ticket”, thus minimizing concurrent access to instance variables of circuit elements. Similar to servlet.
* instance vars of parser object? Parser is supposed to be a singleton, so those instance fields are similar to static fields.

official^programmer-friendly thread states

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.html#getState() has the official thread states
[[ java precisely ]] and a few webpages each define a set of “thread states” but these authors don’t agree 100%.

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.State.html is the official 1.5 list. However, I think this list is perhaps too academic or too low-level. There must be a programmer-friendly version of “thread states”

If you decide to maintain your own list of easy-to-understand states, the state transition diagrams/tables supplied by those authors will need some adjustments. Below are a few ineligible states i.e. ineligible to receive CPU. See post on “Running” state.

* Blocked on I/O — A java thread may enter this state while waiting for data from the IO device. The thread will move to Ready-to-Run (ie eligible) after I/O condition changes (such as reading a byte of data).
* Blocked on Synchronization — A java thread may enter this state while waiting for object lock. The thread will move to Ready-to-Run when a lock is acquired.
* waiting in wait() without argument
* waiting in join() without argument — P 16 [[ concurrent programming in java ]] says “invoking t.join() for Thread t suspends the caller until t completes.”
* timed_waiting — when a thread is waiting in
sleep()
timed wait()
timed join()

a thread is a call stack?

“A thread is basically a call stack” is not a good description, no better than “a revolver is basically a handgun”.

Q: key phrases to describe the /salient/ features of the java thread model

A1: a call stack? Certainly the very first characteristic of a thread, but same for a light-weight process or a runing shell script. The key difference is a shared address space.

A2: a (A) call stack + (B) shared variables

If you find any system exhibiting A and B, I think it would resemble java threads.

I think many if not most of the powers and challenges of multi-threading are attributable to A or B.

– Consistency and safety hazards are due to B. Locks can help but lead to liveness hazards.

– To exploit kernel threads like the 8-core T1 processors, you need separate call stacks for each kernel thread. Similar for GUI

Eligible^Running — 2 thread (and process) states

Based on P66 [[ Java precisely ]]. To understand Thread.yield(), you need to recognize 2 of many states a real-world thread can be in.

“Eligible” = “Enabled” = eligible for CPU time-slice or “eligible for cpu assignment“. Not blocked or waiting for a lock or IO.
“Running” = “running on a cpu” or occupying the driver’s seat, and /driving/ the CPU to execute this thread’s instructions. I believe each native thread (T2000 has 32) can only have a single Running thread (driver) at any time. Running state is unrelated to Runnable.

Similarly, for a Process (rather than a thread), “Ready” means Eligible, i.e. not blocked. See P152 [[art of debugging]] http://web.cs.wpi.edu/~cs502/e07/LectureNotes/Week%202,%20Unix%20Processes.ppt shows that a process can be in Running state or in the Ready state. The Ready is very similar to the Eligible state of a thread – waiting to be assigned CPU

See http://www.javaworld.com/javaworld/jw-07-2002/jw-0703-java101.html

Now we are ready to explain Thread.yield() — it changes the current thread state from Running into Enabled. This thread now joins the “eligible bachelors” club. One of them will receive the CPU. If the club has nobody else, then this thread will.

State transition diagram on P 67 shows there exist only one route to Running — via Enabled. Implications:

1) At end of sleep(), the current thread doesn’t immediately start Running, but joins the Enabled club.
=> After sleeping, threads may not run.
2) A thread waking up from wait(), reacquiring lock, also joins the Enabled-club.
=> After notification, the awake thread can get delayed by lock-reacquisition or Enabled-club.

wait() means

this.wait() means

“current thread please release lock [1] on THIS and join the wait-set inside THIS waiting-area. When something happens in THIS waiting-area, u will reaquire the same lock and then wake up to join the Eligible-club[6].”

[1] if u call this.wait() without a lock on THIS, u get error.
[6] see blog post on Eligible^Running

Q: What happens when a thread returns from wait()?
A: the thread must be patient for a while to reaquire the lock (perhaps from the notifying thread), enter the Eligible-club, receive the CPU slot and run the next statement.

Current thread must clean up [2] the shared toilet before joining the wait-set, since current thread gives lock away to other threads to enter the “shared toilet”.

[2] “clean-up” = don’t leave any object in an inconsistent state. In imprecise terms, Rollback or commit.

timer && timerTask /duo/@@

Before looking at ch11-ex1 java source codes, PONDER these issues:

wait() is the key method beneath the Timer system. Understand wait()
and u understand much of Timer.

A: container of the schedule() method

A: the runnable container of the run() method

Q: which class maintains the schedule and the job @@ see Timer api

Q: which thread executes the jobs in queue@@ timerTask, being a
runnable thread@@. See Timer api

Q: how do u list the jobs in queue@@

Q: basic functionalities embodied by timerTask@@
run() containing the actions to take.
the schedule, perhaps a specification of the next kickoff time.

Q: which class is runnable@@ Which class has a run() method@@

Q: which class has methods to SET the number of seconds for delay@@