multi-threading

1. concurrent vs parallel
concurrent is to have multiple tasks running concurrently
parallel is one way to achieve concurrency by task switching/CPU time-slicing/quantum
another way to have concurrency is running different tasks across different CPU/Core at the same time

from Joe Armstrong (Erlang)
v2-674f0d37fca4fac1bd2df28a2b78e633_hd

2. process vs threads

process is directly managed by OS, have dedicated memory blocks
Thread exist within a process, among threads they co-share existing memory blocks and could share variables/attributes between each other

3. daemon thread

in java, GC thread is daemon thread. at the same time, any thread can be change the priority, and set as daemon.
at any time, if there is no non-daemon thread live, JVM would exit.

4. ways to create thread

Extends Thread class, and implements Runnable
while java doesn’t allow multi-class inheritance (diamond problem), implementing interface(Runnable/Callable) is preferred

5. Runnable vs Callable
Runnable would run without returning the response
Callable would give a handle(future), to check and get the response if any

6. Thread sleep vs wait

Sleep will still holds the object lock
while wait would release the lock, and put this thread on the blocking “queue” waiting for the mark word in the object header

7. threadpool
as creating the thread is a relative expensive operation, a reusable threadpool become helpful to save the effort of continuously creating and killing threads.

at the same time, for the operation, it could be executed once submitted to the pool, save the time waiting for thread to be created.

Threadpool can be created using the Executors (the -s utility classes), methods like newFixedThreadPool, newSingleThreadExecutor, newCachedThreadPool

8. exec vs submit on threadPool
exec would run the task
submit would run the task, at the time return the handle (Future) to check possible reponse

9. run vs start on thread
run is a direct method call on the thread, running in same current executing thread
start would have the thread to invoke the run method in a different thred

10. thread safety

mainly two ways, one is locking, which basically blocks threads touching the shared variable/memory at the same time; this basically convert parallelism to serial operation, which slows the performance

another way is to exchange space with time, to use more memory space, however enabling time efficiency. ThreadLock is one such implementation

11. locks
there are different locks:
synchronized keyword in java is a Pessimistic locking, (this is used when there are more updates than reading)
synchronized can lock on static methods/blocks, then the lock acquired on the class object
synchronized on the method is acquiring the lock on the instance object
synchronized on block, can specify what’s the object to get the lock from. in javap to check the compiled class, synchronized on block, would have a monitorenter and monirtoexit on beginning and exiting the block

reentrant lock is a explicit lock, also pessimistic, which give developers more control to explicitly control when/where to lock and unlock. (worth taking note, the unlock should be put into the finally block, so in case of exceptions, the lock can also be released, otherwise it creates deadlocks)
another point to use reentrant lock is to use fairness, which on releasing the lock, can prioritize to give the lock to threads waiting longest

When the thread first enters into lock, a hold count is set to one. Before unlocking the thread can re-enter into lock again and every time hold count is incremented by one. For every unlock request, hold count is decremented by one and when hold count is 0, the resource is unlocked.

The unlock statement is always called in the finally block to ensure that the lock is released even if an exception is thrown in the method body(try block).

ReentractLock.lock():
Acquires the lock.
Acquires the lock if it is not held by another thread and returns immediately, setting the lock hold count to one.
If the current thread already holds the lock then the hold count is incremented by one and the method returns immediately.
If the lock is held by another thread then the current thread becomes disabled for thread scheduling purposes and lies dormant until the lock has been acquired, at which time the lock hold count is set to one.

ReentrantLock.tryLock():
Acquires the lock only if it is not held by another thread at the time of invocation.
Acquires the lock if it is not held by another thread and returns immediately with the value true, setting the lock hold count to one. Even when this lock has been set to use a fair ordering policy, a call to tryLock() will immediately acquire the lock if it is available, whether or not other threads are currently waiting for the lock. This “barging” behavior can be useful in certain circumstances, even though it breaks fairness. If you want to honor the fairness setting for this lock, then use tryLock(0, TimeUnit.SECONDS) which is almost equivalent (it also detects interruption).
If the current thread already holds this lock then the hold count is incremented by one and the method returns true.
If the lock is held by another thread then this method will return immediately with the value false.

ReentrantLock.tryLock(timeout, TimeUnit):
Acquires the lock if it is not held by another thread within the given waiting time and the current thread has not been interrupted.
Acquires the lock if it is not held by another thread and returns immediately with the value true, setting the lock hold count to one. If this lock has been set to use a fair ordering policy then an available lock will not be acquired if any other threads are waiting for the lock. This is in contrast to the tryLock() method. If you want a timed tryLock that does permit barging on a fair lock then combine the timed and un-timed forms together:

if (lock.tryLock() ||
lock.tryLock(timeout, unit)) {

}

12. Lock vs CAS

Lock is pessimistic, which is for situations where there are more writes/updates than reads
CAS is optimistic, for cases where there are more reads than writes, hence no need to blocking most of the time

CAS basically checking target value if same as expected, then update; otherwise repeat reading and CAS again until abort the tasks; however, downside is for ABA problem.
to tackle ABA, timestamp could be taken into account

in atomicInteger class, it’s using CAS.

    public final int getAndAdd(int delta) {
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }
    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

version checking on cache/database update is a CAS operation.

CAS

in AQS framework, it’s trying with cas optimistic lock to acquire the lock first. If it is not obtained, it will be converted into a pessimistic lock, such as RetreenLock.

CAS is a type of spin lock. basically swap the value if compare meet the expected value, others spin(spin lock) till success (or finished CPU time slice).

13. volatile

each thread has its own “cached” copy of the variables on main memory/heap, whether it’s being pc register or CPU L1/2/3 cache. Hence, there are cases, the variable on main memory has been updated, which thread’s local copy is not reflected.

to mark the variable as volatile, is tell JVM always read the variable from main memory. This will make sure the visibility. however, worth to note, this doesn’t gurantee thread safety, neither atomicity, as exclusive is not ensured.

for example volatile int a++; is actually 3 operation, 1) read a; 2) +1, 3) write back a
while first step is guranteed latest value on memory, however, step 2 and 3 is not exclusive(synchronized) hence not atomic

public class TestVolatile {
    public static void main(String... args) {

        OneThread t = new OneThread();
        t.start();
        try {
            Thread.sleep(1_000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        t.setRunning(false);

    }

    public static class OneThread extends Thread {
//        private volatile boolean running = true;//end of thread once set as false
        private boolean running = true;//forever running


        @Override
        public void run() {
            System.out.println("entering the thread run method");
            while(running) {
                try {
                    //Thread.sleep(1100);//if not commented, it try to update the local copy by reading from main memory
                    //System.out.println(running);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            System.out.println("end of thread");
        }

        public void setRunning(boolean running) {
            this.running = running;
        }

        public boolean isRunning() {
            return running;
        }
    }


}

14. dead lock vs live lock

dead lock is while thread waiting for lock to proceed, however not possible to get the lock. example as , thread 1 acquaired lock of object A, wait for object B lock; while thread 2 having acquaired lock of object B however waiting for object A lock; hence waiting for each other and no way to proceed

live lock is waiting for other operations to finish to release the lock.

15. spin lock
normmaly if threads cannot acquire a lock, it wlll move to blocked state to wait to be notified (notify/notifyall)
spin lock is keep trying to acquire the lock. so the thread is keep running, continuously checking if can acquire the lock until its time slice has finished

this is normmally used when cases the thread having already acquaired the lock is expected to be short lived/running

16. lock upgrading

according to HotSpot, there are cases, its actually only one thread trying to acquaire the lock, hence the lowest/fastest lock, biased lock towards that single thread.

“-XX:+UseBiasedLocking Enables a technique for improving the performance of uncontended synchronization. An object is “biased” toward the thread which first acquires its monitor via a monitorenter bytecode or synchronized method invocation; ”

Note HotSpot doesn’t use biased locking from VM start. There are some VM do that, like Azul.

if there is another thread trying to compete the lock, biased lock could be upgraded to lightweight lock.

Synchronization
https://wiki.openjdk.java.net/display/HotSpot/Synchronization

17. countdownlatch vs cyclicBarrier
both are mechanism/synchronization aid trying to control timing of parallelism. CountdownLatch is non re-usable. it’s create with a initial value bigger than 0, in each thread, it could count down (countdown()) the latch, then once the value become 0, it would lift up the latch (await()), and have all threads continued.
I have used this multiple times to simulate multi threading issue.

CyclicBarrier is reusable. another difference is, when constructing CyclicBarrier, a runnable can be passed in, which will be invoked when it’s tripped, (when given number of threads waiting upon it).

18. inter thread communication
wait method would cause the current thread to pause, and release the lock. so that other threads waiting for the lock could try to acquire the lock and get the time slice for operation.

note: thread sleep would pause the thread, (so that other threads can get the next cpu time slice), however wont the release the lock.

notify & notifyAll would wake up the paused/wait thread (randomly). this is only called by the thread which has the lock. the waken/notified thread would wake up, however, then need to wait/try to acquire with same priority as other threads, before it can operate.

19. object header
in object header, there is a marker word to tell what’s the current thread holding the object’s lock/monitor at the moment.
at the same time, in the object header, there are two pools, waiting queue which is the threads have acquired the lock before and hence has released and waiting for their turn (to be notified, and to fight for the lock) again.
another is the lock pool, which are the threads currently waiting to get the lock. Once object waken from waiting queue, should be then put into lock pool if trying to get the lock again.

20. how to implement a thread safe cache

    class Cache{

        Map container = new HashMap();
        Map lockOnKeyMap = new ConcurrentHashMap();
        Function retrieveFromDisk = new Function() {
            @Override
            public V apply(K k) {
                //IO to get the value
                return null;
            }
        };
        Cache(Function function){
            this.retrieveFromDisk = function;
        }

        V get(K k){
            V v = container.get(k);
            if(v ==null){
                K lockKey = lockOnKeyMap.putIfAbsent(k,k);
                synchronized (lockKey == null ? k: lockKey){//make sure, this locks on same Key
                    //so that IO is only done ONCE per cache miss
                    if(v==null){
                        v =retrieveFromDisk.apply(k);
                    }
                }


                container.put(k, v);
            }
            return v;
        }

    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s