Multithreading

Howto create a thread

Usage

The start method of a Thread object starts a new thread that executes the run method of its Runnable.
The sleep method puts the current Thread to sleep for a given number of milliseconds.
There are situations where a Thread is no longer valid, (after a long sleep), or not desired. The Thread can then be interrupted.
When a thread is interrupted, the most common response is to terminate the run method.
Thus, a thread terminates when the run method of its Runnable terminates or is terminated.
The construction of a Thread is a costly process. The solution to this, is a Thread Pool. Multiple threads waiting for a Runnable object to run.

Note: do not directly call run()! This will execute the code within run() in the current running thread, not a new thread.
Note: if you do not let a thread sleep after an execution, it will continue to run for it's maximum allotted time by the VM. The thread is then called selfish.
Threads are not executed and switched on a line by line basis, there is no garantuee for the order of thread execution!

Scheduling Threads

The thread scheduler allows each thread to execute for a short amount of time, called a time slice.
Each thread has a:

• Thread state
  • new (before start is called)
  • runnable
  • blocked
  • dead (after run exits)
• Priority

There is no state to indicate whether a runnable thread is actually running.
A thread can enter the blocked state for several reasons:

• Sleeping
• Waiting for input / output
• Waiting to acquire a lock
• Waiting for a condition

The thread scheduler selects among the runnable threads with the highest priority value.
The scheduler will switch to a different thread when one of three events occurs:

• A thread has completed its time slice
• A thread has blocked itself.
• A thread with a higher priority has become runnable.

Note: The scheduler behaves differently on different OSs. The behavior above is the Windows NT behavior. In Linux, a thread maintains control until a thread with higher priority becomes runnable.

Terminating Threads

To notify a thread that it should clean up, release resources and locks, and terminate; use the interrupt method.
The run method should constantly check if it has been interrupted, and if so, do any necessary cleanup and exit.
The most common way to solve this problem is this:

The Thread.sleep() method checks whether the thread is interrupted, and then exits the work loop, and resumes on the cleanup line.
The catching of InterruptedException, resets the thread to a uninterrupted state. Therefore, it is very bad coding style to "squelch" the InterruptedException.

But in some cases, it is impossible to encapsulate the entire code with the try{}catch().
The solution is to set the Thread back to the interrupted state within the catch, and check in the program code if the thread is interrupted.
And if so the thread is interrupted, then to exit the run method cleanly.

Corrupting a Shared Data Structure

When threads share acces to a common object, they can conflict with each other. An example would be if two threads are working on a queue.

Suppose both threads do the following: check if the queue is not empty, and if it is not, try to remove an object.
Remember: we are not allowed to remove objects from an empty queue.
Suppose the queue only has 1 object left, and both threads are at the queue.isEmpty() check line.
The first thread checks the queue, and passes the check, now suppose that the VM switches to the other thread.
This thread again, checks if the queue is empty, and passes the check. It then removes the last object from the queue.
The VM switches back to the first thread, which then tries to remove an object from an empty queue, crashing the program.

This behaviour only occurs under certain circumstances and not all the time. This is the very definition of a hard to catch multithreading bug!
This is just one example of how the program could crash. Another problem could be that the queue is removing an item, and before the thread can lower the indexcount, the other thread tries to remove an item, resulting in both threads removing the same item. This may seem harmless, but if we were adding objects to the queue, the item would be overwritten with the object from the other thread trying to add an item.

These situations are examples of race conditions. A race condition occurs if the effect of multiple threads on shared data depends on the order in which the threads are scheduled. In other words, the outcome of the operation changes if a different thread "wins".

Locks

A lock is an object to control and limit the amount of threads running a certain piece of code.
A thread can acquire a lock. When another thread tries to acquire the same lock, it is blocked.
When the first thread releases the lock, the other threads are unblocked, and the first thread to get execution time will get the lock.
A better metaphore would be: the protected code is "locked", and only 1 thread can get the "key".
There are multiple types of locks.

This first type of lock, locks the code within the try { } code. The finally {} statement is to ensure that the Lock will be released, even if an error or exception is thrown in the try {} code.
When a thread arrives at aLock.lock(), it checks if the lock is available, and if so, locks it, and continues. If it is locked, the thread will be blocked.

Avoiding Deadlocks

Now a new problem arrises, what if we have two pieces of code, protected by one lock. Let's say one code cannot finish if it doesn't have the results from the other piece of code.
What if the thread that is dependent on the result gets the lock first?
This problem is called a deadlock, a deadlock occurs if no thread can proceed because each thread is waiting for another to do some work first.

For this problem, the Condition interface was created. Each lock can have one or more associated Condition objects.
Calling await on a Condition object makes the current thread wait and allows another thread to acquire the lock.
The waiting thread is blocked until another thread calls signalAll or signal on the condition object for which the thread is waiting.

Java Example: 2 Methods: Add() & Remove(); Add() waits until there is space to add the object. Remove() waits until there is an element to remove.

Object Locks

Every Java Object has an associated object lock. To acces the lock, you just define a method as synchronized.
The object lock is shared between all methods with the synchronized tag of that instance object, so if one thread is working on a synchronized method, other synchronized methods of that same instance object are blocked.

Note: Methods of the object that do not have the synchronized tag are not locked!

The object lock also has one Condition associated with it. It's methods are wait(); to make a thread wait, and notify()& notifyAll(); to wake up one or all threads waiting for the condition respectively.
This implementation is much more simple than the code lock, but it is much more restrictive in it's options. It is a simple construct to ensure data structure integrity. Make all methods synchronized, and you will never have race conditions.

Special