Algorithms
Process, Threads and Synchronization
Given n, print numbers from zero to n sequentially using two threads such that one thread prints only odds and other prints only evens.
This is a simple classical thread synchronization problem. Before moving to the solution I would like revise basic process, thread, and synchronization/concurrency concepts. Some of the figures in this article are taken from this Silberschatz OS book.
Process
Process is an execution stream in the context of a particular process state. By Execution Stream we mean a sequence of instructions executed sequentially i.e. only one thing happens at a time. By Process State we mean everything that can affect, or be affected by, the process: code, data, call stack, open files, network connections, etc.
A process has a self-contained execution environment. A process generally has a complete, private set of basic run-time resources e.g. process has its own memory space. Process memory is divided into four sections as shown in Figure below:
- Text Section : contains compiled program code loaded when program is launched.
- Data Section : contains global and static variables, allocated and initialized prior to executing main
- Stack : contains local variables, function call frames. It starts from higher memory address and shrink down as elements are added.
- Heap : used for dynamic memory allocation using for example, new, delete, malloc, free, etc.
Note that the stack and the heap start at opposite ends of the process’s free space and grow towards each other. If they should ever meet, then either a stack overflow error will occur, or else a call to new or malloc will fail due to insufficient memory available.
Thread
Thread is unit of sequential execution. In other words, Threads are multiple execution streams within a single process. Threads share process state such as memory, open files, etc. Each thread has a separate stack for procedure calls (in shared memory).
Threads are sometimes called lightweight processes. Both processes and threads provide an execution environment, but creating a new thread requires fewer resources than creating a new process.
Threads exist within a process — every process has at least one. Threads share the process’s resources, including memory and open files. This makes for efficient, but potentially problematic, communication.
Process vs Threads
A process is an execution environment provided by the operating system that has its own set of private resources such as memory, open files, etc. On the other hand, Threads live within a process and share its resources : memory, open files, etc.
A process runs independently and isolated of other processes. It cannot directly access shared data in other processes. The resources of the process, e.g. memory and CPU time, are allocated to it via the operating system.
A thread is a so called lightweight process. It has its own call stack, but can access shared data of other threads in the same process. Every thread has its own memory cache. If a thread reads shared data it stores this data in its own memory cache. A thread can re-read the shared data.
For example, a Java application runs by default in one process. Within a Java application you work with several threads to achieve parallel processing or asynchronous behavior.
Process vs Program
A program by itself is not a process. It is a static entity made up of program statement while process is a dynamic entity. Program contains the instructions to be executed by processor.
A program takes a space at single place in main memory and continues to stay there. A program does not perform any action by itself.
How Process Works?
A process lifecycle goes through some states as described in the following figure –
When processes are swapped out of memory and later restored, additional information must also be stored and restored. Key among them are the program counter and the value of all program registers. kernel uses a Process Control Block (PCB) to keep track of processes as showed in following figure –
- Process State : Running, waiting, etc.
- PIDs : Process ID, and parent process ID.
- CPU registers and Program Counter : Information to restore swapped process out of memory.
- Memory-Management information : page tables or segment tables.
- I/O Status information : Devices allocated, open file tables, etc.
- Accounting information : user and kernel CPU time consumed, account numbers, limits, etc.
The dispatcher/scheduler is the one of the most important component (a kernel process itself) in OS that runs processes/threads. it does time slicing of the processor and assign one single thread to be in running state. Then it swaps this process by saving its state and load states of another process/thread from the scheduling queue based on a scheduling criteria or algorithm such as FIFO, Round Robin, or Priority based scheduling etc and run it. This incident is known as Context Switch i.e. changing the thread currently running on a CPU by first saving the state of the old process, then loading the state of the new process.
Note that, only one process can be running on a cpu at a particular time slice of the processor. So, if a thread is executing, scheduler isn’t running. So, question is how scheduler will run again to take control and schedule next process? Answer is Traps and Interrupts.
Traps are events occurring in current thread that cause a change of control into the operating system. There are 3 ways to trap OS –
- System call.
- Error (illegal instruction, addressing violation, etc.).
- Page fault.
Interrupts are events occurring outside the current thread that cause a state switch into the operating system, for example completion of am I/O, expiration of a timer, keyboard events etc. The context switch process can be described pictorially as follows –
Process Creation
- Load code and data into memory.
- Create and initialize process control block.
- Create first thread with call stack.
- Provide initial values for “saved state” for the thread
- Make process known to dispatcher; dispatcher “resumes” to beginning of process.
IPC : Inter Process Communication
Processes are often seen as synonymous with programs or applications. However, what the user sees as a single application may in fact be a set of cooperating processes. To facilitate communication between processes, most operating systems support Inter Process Communication (IPC) resources, such as message queues, pipes and sockets. IPC is used not just for communication between processes on the same system, but processes on different systems.
Read more in here.
Concurrency and Synchronization
When multiple threads access shared resources such that some of them modify a resource and others are reading that resource then we will face all sorts of data consistency problem due to synchronization issues among threads. For example, if thread A reads shared data which is later changed by thread B and thread A is unaware of this change. Let’s first define some terms before jumping into details –
- Synchronization : using atomic operations to ensure correct operation of cooperating threads.
- Critical section : a section of code, or collection of operations, in which only one thread may be executing at a given time. E.g. shopping.
- Mutual exclusion : mechanisms used to create critical sections (ensure that only one thread is doing certain things at a given time).
However, synchronization can introduce thread contention, which occurs when two or more threads try to access the same resource simultaneously and cause the Java runtime to execute one or more threads more slowly, or even suspend their execution. Starvation and livelock are forms of thread contention.
- Starvation : Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by “greedy” threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
- Livelock : A thread often acts in response to the action of another thread. If the other thread’s action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They’re still blocking each other.
Typically, mutual exclusion achieved with a locking mechanism: prevent others from doing something. For example, before shopping, leave a note on the refrigerator: don’t shop if there is a note. We can lock an object that can only be owned by a single thread at any given time. Basic operations on a lock:
- Acquire: mark the lock as owned by the current thread; if some other thread already owns the lock then first wait until the lock is free. Lock typically includes a queue to keep track of multiple waiting threads.
- Release: mark the lock as free (it must currently be owned by the calling thread).
Synchronization mechanisms need more than just mutual exclusion; also need a way to wait for another thread to do something (e.g., wait for a character to be added to the buffer). We can achieve this by using Condition variables.
Condition variables are used to wait for a particular condition to become true (e.g. characters in buffer).
- _wait(condition, lock): release lock, put thread to sleep until condition is signaled; when thread wakes up again, re-acquire lock before returning.
- signal(condition, lock): if any threads are waiting on condition, wake up one of them. Caller must hold lock, which must be the same as the lock used in the wait call.
- broadcast(condition, lock): same as signal, except wake up all waiting threads.
Note: after signal, signaling thread keeps lock, waking thread goes on the queue waiting for the lock.
Warning: when a thread wakes up after condition_wait there is no guarantee that the desired condition still exists: another thread might have snuck in.
When locks and condition variables are used together like this, the result is called a Monitor. Monitor is a collection of procedures manipulating a shared data structure.
- One lock that must be held whenever accessing the shared data (typically each procedure acquires the lock at the very beginning and releases the lock before returning).
- One or more condition variables used for waiting.
Semaphore vs Mutex
Mutex is a key to a toilet. One person can have the key – occupy the toilet – at the time. When finished, the person gives (frees) the key to the next person in the queue.
Formally, mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.
Semaphore is the number of free identical toilet keys. Example, say we have four toilets with identical locks and keys. The semaphore count – the count of keys – is set to 4 at beginning (all four toilets are free), then the count value is decremented as people are coming in. If all toilets are full, ie. there are no free keys left, the semaphore count is 0. Now, when eq. one person leaves the toilet, semaphore is increased to 1 (one free key), and given to the next person in the queue.
Formally, a semaphore restricts the number of simultaneous users of a shared resource up to a maximum number. Threads can request access to the resource (decrementing the semaphore), and can signal that they have finished using the resource (incrementing the semaphore).
Implement Locks
Uniprocessor solution –
- Acquire Lock : disable interrupts.
- put thread to sleep if lock not available:
- Hardware provides some sort of atomic read-modify-write instruction, which can be used to build higher-level synchronization operations such as locks. For example, aswap: atomically read memory value and replace it with a given value: returns old value.
struct lock {
int locked;
struct queue q;
int sync; /* Normally 0. */
};
void lock_acquire(struct lock *l) {
Disable interrupts;
while (aswap(&l-;>sync, 1) {
/* Do nothing */
}
if (!l->locked) {
l->locked = 1;
l->sync = 0;
} else {
queue_add(&l-;>q, thread_current());
l->sync = 0;
thread_block();
}
Enable interrupts;
}
void lock_release(struct lock *l) {
Disable interrupts;
while (aswap(&l-;>sync, 1) {
/* Do nothing */
}
if (queue_empty(&l-;>q) {
l->locked = 0;
} else {
thread_unblock(queue_remove(&l-;>q));
}
l->sync = 0;
Enable interrupts;
}
Threads and Concurrency in Java
In the Java virtual machine, every object and class is logically associated with a monitor. To implement the mutual exclusion capability of monitors, a lock (sometimes called a mutex) is associated with each object and class. This is called a semaphore.
If one thread owns a lock on some data, then no others can obtain that lock until the thread that owns the lock releases it. It would be not convenient if we need to write a semaphore all the time when we do multi-threading programming. Luckily, we don’t need to since JVM does that for us automatically.
To claim a monitor region which means data not accessible by more than one thread, Java provide synchronized statements and synchronized methods. Once the code is embedded with synchronized keyword, it is a monitor region. The locks are implemented in the background automatically by JVM.
Each object/class is associated with a Monitor. To enable collaboration of different threads, Java provide wait() and notify() to suspend a thread and to wake up another thread that are waiting on the object respectively. These methods can only be invoked within a synchronized statement or synchronized method. The reason is that if a method does not require mutual exclusion, there is no need to monitor or collaborate between threads, every thread can access that method freely.
The synchronized keyword in Java ensures:
- that only a single thread can execute a block of code at the same time
- that each thread entering a synchronized block of code sees the effects of all previous modifications that were guarded by the same lock
Synchronization is necessary for mutually exclusive access to blocks of and for reliable communication between threads.
We can use the synchronized keyword for the definition of a method. This would ensure that only one thread can enter this method at the same time. Another threads which is calling this method would wait until the first threads leaves this method.
public synchronized void method() {
//critical codes
}
We can also use the synchronized keyword to protect blocks of code within a method. This block is guarded by a key, which can be either a string or an object. This key is called the lock. All code which is protected by the same lock can only be executed by one thread at the same time
public void method() {
//un-critical codes
synchronized (this) {
//wait for resource
//critical codes
}
//notify all
//un-critical codes
}
notify() vs notifyAll()
- wait() tells the calling thread to give up the monitor and go to sleep until some other thread enters the same monitor and calls notify( ).
- notify() wakes up the first thread that called wait() on the same object.
In some cases, all waiting threads can take useful action once the wait finishes. An example would be a set of threads waiting for a certain task to finish; once the task has finished, all waiting threads can continue with their business. In such a case you would use notifyAll() to wake up all waiting threads at the same time.
Another case, for example mutually exclusive locking, only one of the waiting threads can do something useful after being notified (in this case acquire the lock). In such a case, you would rather use notify(). Properly implemented, you could use notifyAll() in this situation as well, but you would unnecessarily wake threads that can’t do anything anyway.
Thread vs Runnable
There are two way to create threads in Java – implementing a Runnable interface or by extending Thread class.
1. Provide a Runnable object. The Runnable interface defines a single method, run, meant to contain the code executed in the thread. The Runnable object is passed to the Thread constructor, as in the HelloRunnable example:
public class HelloRunnable implements Runnable {
public void run() {
System.out.println("Hello from a thread!");
}
public static void main(String args[]) {
(new Thread(new HelloRunnable())).start();
}
}
2. Subclass Thread. The Thread class itself implements Runnable, though its run method does nothing. An application can subclass Thread, providing its own implementation of run, as in the HelloThread example:
public class HelloThread extends Thread {
public void run() {
System.out.println("Hello from a thread!");
}
public static void main(String args[]) {
(new HelloThread()).start();
}
}
Which one to use when?
- Java doesn’t support multiple inheritance, which means we can only extend one class in Java. So if we extended Thread class then we can’t extend or inherit another class. So in situations where a child class in a hierarchy needs to be run as thread then we need to implement Runnable interface.
- If we are not making any modification on Thread than use Runnable interface instead.
- Runnable interface represent a Task which can be executed by either plain Thread or Executors or any other means. so logical separation of Task as Runnable than Thread is good design decision.
- Separating task as Runnable means we can reuse the task and also has liberty to execute it from different means. since you can not restart a Thread once it completes. again Runnable vs Thread for task, Runnable is winner.
- Java designer recognizes this and that’s why Executors accept Runnable as Task and they have worker thread which executes those task.
- Inheriting all Thread methods are additional overhead just for representing a Task which can can be done easily with Runnable.
Interrupts and Join
An interrupt is an indication to a thread that it should stop what it is doing and do something else. It’s up to the programmer to decide exactly how a thread responds to an interrupt, but it is very common for the thread to terminate. This is the usage emphasized in this lesson.
A thread sends an interrupt by invoking interrupt on the Thread object for the thread to be interrupted. For the interrupt mechanism to work correctly, the interrupted thread must support its own interruption. In java we can catch InterruptedException to catch the interrupt –
for (int i = 0; i < importantInfo.length; i++) {
// Pause for 4 seconds
try {
Thread.sleep(4000);
} catch (InterruptedException e) {
// We've been interrupted: no more messages.
return;
}
// Print a message
System.out.println(importantInfo[i]);
}
Many methods that throw InterruptedException, such as sleep, are designed to cancel their current operation and return immediately when an interrupt is received.
What if a thread goes a long time without invoking a method that throws InterruptedException? Then it must periodically invoke Thread.interrupted, which returns true if an interrupt has been received. For example:
for (int i = 0; i < inputs.length; i++) {
heavyCrunch(inputs[i]);
if (Thread.interrupted()) {
// We've been interrupted: no more crunching.
throw new InterruptedException();
}
}
The interrupt mechanism is implemented using an internal flag known as the interrupt status. Invoking Thread.interrupt sets this flag. When a thread checks for an interrupt by invoking the static method Thread.interrupted, interrupt status is cleared. The non-static isInterrupted method, which is used by one thread to query the interrupt status of another, does not change the interrupt status flag.
By convention, any method that exits by throwing an InterruptedException clears interrupt status when it does so. However, it’s always possible that interrupt status will immediately be set again, by another thread invoking interrupt.
The join method allows one thread to wait for the completion of another. If t is a Thread object whose thread is currently executing,
t.join();
causes the current thread to pause execution until t’s thread terminates. Overloads of join allow the programmer to specify a waiting period. However, as with sleep, join is dependent on the OS for timing, so you should not assume that join will wait exactly as long as you specify.
Like sleep, join responds to an interrupt by exiting with an InterruptedException.
Volatile and Immutable
If a variable is declared with the volatile keyword then it is guaranteed that any thread that reads the field will see the most recently written value. The volatile keyword will not perform any mutual exclusive lock on the variable.
Another simplest way to avoid problems with concurrency is to share only immutable data between threads. Immutable data is data which cannot changed. In order to make a class immutable we need to design the class such that –
- all its fields are final
- the class is declared as final
- this reference is not allowed to be used during construction
- any fields which refer to mutable data objects are private
- it doesn’t have no setter method
- they are never directly returned of otherwise exposed to a caller
- if they are changed internally in the class this change is not visible and has no effect outside of the class
An immutable class may have some mutable data which is uses to manages its state but from the outside this class nor any attribute of this class can get changed.
For all mutable fields, e.g. Arrays, that are passed from the outside to the class during the construction phase, the class needs to make a defensive-copy of the elements to make sure that no other object from the outside still can change the data.
Ok, that’s enough…….
If you have not been frustrated enough and still reading this hoping to see the solution to the original problem of this article, then let’s solve it –
Given n, print numbers from zero to n sequentially using two threads such that one thread prints only odds and other prints only evens.
In order to count numbers from 0 to n the two threads can access to a shared resource which will be initialized to 0 and each time a thread will increment it by one until it reaches n. Now, we need to make sure the coordination between two therads are synchronized such that odd numbers are printed by one thread and even by others. How to make this synchronized?
We can notice that odd thread should only access the shared counter if the counter value is odd and even thread if counter value is even. In order to identify whether a thread is a odd or even we can assign a turn value of 0 for even and 1 for odd. Each time a thread gets access to the shared counter it needs to check if it is a odd or even and if it matches with its turn then print it and increment it for the other thread.
In order to get access in synchronized manner we need to use a lock to make sure only one thread goes into the critical section where a thread accessed the shared counter to check and modify it. We can put all these critical codes inside a monitor using a synchronized block on a locking object. Below is an implementation of the above process using synchronized block on a locking object and using Java thread pool executor service for managing thread pools.
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
public class ThreadTest{
private final Object lock = new Object();
private int cur;
private final int max;
public ThreadTest(int n){
this.max = n;
}
protected class PrintThread implements Runnable {
private final int turn;
public PrintThread(int turn){
this.turn = turn;
}
@Override
public void run() {
while(true){
try {
Thread.sleep(10);
} catch (InterruptedException e1) {
e1.printStackTrace();
}
//get access to intrinsic lock of the ThreadTest class to access it's shared resources in synchronized manner
//synchronized (ThreadTest.class) {
//or get access to a explicit lock
synchronized (lock) {
if(cur > max){
return;
}
if(cur%2 == turn){
System.out.println("Thread "+this.turn+": "+cur++);
}
}
}
}
}
public void print() throws InterruptedException{
ExecutorService pool = Executors.newFixedThreadPool(2);
pool.execute(new PrintThread(0));
pool.execute(new PrintThread(1));
pool.shutdown();
}
public static void main(String args[]) throws InterruptedException{
ThreadTest tt = new ThreadTest(20);
tt.print();
}
}
Output
Thread 0: 0 Thread 1: 1 Thread 0: 2 Thread 1: 3 Thread 0: 4 Thread 1: 5 Thread 0: 6 Thread 1: 7 Thread 0: 8 Thread 1: 9 Thread 0: 10 Thread 1: 11 Thread 0: 12 Thread 1: 13 Thread 0: 14 Thread 1: 15 Thread 0: 16 Thread 1: 17 Thread 0: 18 Thread 1: 19 Thread 0: 20