MULTITHREADING Flashcards
What’s the difference between a thread and a process?
Processes and threads are related to each other but are fundamentally different.
A process can be thought of as an instance of a program in execution. A process is an independent entity to
which system resources (e.g., CPU time and memory) are allocated. Each process is executed in a separate
address space, and one process cannot access the variables and data structures of another process. If a
process wishes to access another process’ resources, inter-process communications have to be used. These
include pipes, files, sockets, and other forms.
A thread exists within a process and shares the process’ resources (including its heap space). Multiple
threads within the same process will share the same heap space. This is very different from processes, which
cannot directly access the memory of another process. Each thread still has its own registers and its own
stack, but other threads can read and write the heap memory.
A thread is a particular execution path of a proces
Implement Dining Philosophers problems:
In the famous dining philosophers problem, a bunch of philosophers are sitting around a circular table with one chopstick between each of them. A philosopher needs both
chopsticks to eat, and always picks up the left chopstick before the right one. A deadlock could
potentially occur if all the philosophers reached for the left chopstick atthe same time. Using threads
and locks, implement a simulation of the dining philosophers problem that prevents deadlocks
https://app.gitbook.com/s/LtOCx4PXhezd4jPeeJTa/
What is Concurrency model?
The concurrency model in java is defined as the model which is responsible for carrying out the communication between the threads in the system which is responsible for carrying out the large or executing the large process running in the system along with proper synchronization to prevent partial reading or writing of the final value in the program which is running in the system.
List concurrency models that you know?
jenkov.com/tutorials/java-concurrency/concurrency-models.html
stackoverflow.com/questions/31627441/java-support-for-three-different-concurrency-models
1) Parallel workers
The first concurrency model is what I call the parallel worker model. Incoming jobs are assigned to different workers.
2) Assembly line
The workers are organized like workers at an assembly line in a factory. Each worker only performs a part of the full job. When that part is finished the worker forwards the job to the next worker.
Each worker is running in its own thread, and shares no state with other workers. This is also sometimes referred to as a shared nothing concurrency model.
3) Functional Parallelism
The basic idea of functional parallelism is that you implement your program using function calls. Functions can be seen as “agents” or “actors” that send messages to each other, just like in the assembly line concurrency model (AKA reactive or event driven systems). When one function calls another, that is similar to sending a message.
Describe Parallel Workers concurrency model
https://jenkov.com/tutorials/java-concurrency/concurrency-models.html
Incoming jobs are assigned to different workers.
In the parallel workers concurrency model a delegator distributes the incoming jobs to different workers. Each worker completes the full job. The workers work in parallel, running in different threads, and possibly on different CPUs.
If the parallel workers model was implemented in a car factory, each car would be produced by one worker. The worker would get the specification of the car to build, and would build everything from start to end.
The parallel workers concurrency model is the most commonly used concurrency model in Java applications (although that is changing). Many of the concurrency utilities in the java.util.concurrent Java package are designed for use with this model. You can also see traces of this model in the design of the Java Enterprise Edition application servers.
The parallel workers concurrency model can be designed to use both shared state or separate state, meaning the workers either has access to some shared state (shared objects or data), or they have no shared state.
List adventages and disadventages of parallel workers
The advantage of the parallel workers concurrency model is that it is easy to understand and implement. To increase the parallelization level of the application you just add more workers.
For instance, if you were implementing a web crawler, you could crawl a certain amount of pages with different numbers of workers and see which number gives the shortest total crawl time (meaning the highest performance). Since web crawling is an IO intensive job you will probably end up with a few threads per CPU / core in your computer. One thread per CPU would be too little, since it would be idle a lot of the time while waiting for data to download.
Whar are the disadventages of Parallel Workers?
[1] Share state can get complex
In case the shared workers need access to some kind of shared data, either in memory or in a shared database, managing correct concurrent access can get complex.
E.g. access to shared data in memory or database
Some of this shared state is in communication mechanisms like job queues. But some of this shared state is business data, data caches, connection pools to the database etc.
As soon as shared state sneaks into the parallel workers concurrency model it starts getting complicated. The threads need to access the shared data in a way that makes sure that changes by one thread are visible to the others (pushed to main memory and not just stuck in the CPU cache of the CPU executing the thread). Threads need to avoid race conditions, deadlock and many other shared state concurrency problems.
Additionally, part of the parallelization is lost when threads are waiting for each other when accessing the shared data structures. Many concurrent data structures are blocking, meaning one or a limited set of threads can access them at any given time. This may lead to contention on these shared data structures. High contention will essentially lead to a degree of serialization of execution (eliminating parallelization) of the part of the code that access the shared data structures.
Modern non-blocking concurrency algorithms may decrease contention and increase performance, but non-blocking algorithms are hard to implement.
[2] Stateless workers
Shared state can be modified by other threads in the system. Therefore workers must re-read the state every time they need it, to make sure they are working on the latest copy. This is true no matter whether the shared state is kept in memory or in an external database. A worker that does not keep state internally (but re-reads it every time it is needed) is called stateless .
Re-reading data every time you need it can get slow. Especially if the state is stored in an external database.
[3]Job Ordering is Nondeterministic
Another disadvantage of the parallel worker model is that the job execution order is nondeterministic. There is no way to guarantee which jobs are executed first or last. Job A may be given to a worker before job B, yet job B may be executed before job A.
The nondeterministic nature of the parallel worker model makes it hard to reason about the state of the system at any given point in time. It also makes it harder (if not impossible) to guarantee that one task finishes before another. This does not always cause problems, however. It depends on the needs of the system.
Describe “Assembly Line” (Reactive ,event driven) concurrency model
jenkov.com/tutorials/java-concurrency/concurrency-models.html
The second concurrency model is what I call the assembly line concurrency model. I chose that name just to fit with the “parallel worker” metaphor from earlier. Other developers use other names (e.g. reactive systems, or event driven systems) depending on the platform / community.
The workers are organized like workers at an assembly line in a factory. Each worker only performs a part of the full job. When that part is finished the worker forwards the job to the next worker.
Systems using the assembly line concurrency model are usually designed to use non-blocking IO. Non-blocking IO means that when a worker starts an IO operation (e.g. reading a file or data from a network connection) the worker does not wait for the IO call to finish. IO operations are slow, so waiting for IO operations to complete is a waste of CPU time. The CPU could be doing something else in the meanwhile. When the IO operation finishes, the result of the IO operation ( e.g. data read or status of data written) is passed on to another worker.
With non-blocking IO, the IO operations determine the boundary between workers. A worker does as much as it can until it has to start an IO operation. Then it gives up control over the job. When the IO operation finishes, the next worker in the assembly line continues working on the job, until that too has to start an IO operation etc.
In reality, the jobs may not flow along a single assembly line. Since most systems can perform more than one job, jobs flows from worker to worker depending on what part of the job that needs to be executed next. In reality there could be multiple different virtual assembly lines running on at the same time.
Jobs may even be forwarded to more than one worker for concurrent processing. For instance, a job may be forwarded to both a job executor and a job logger.
Systems using an assembly line concurrency model are also sometimes called reactive systems, or event driven systems. The system’s workers react to events occurring in the system, either received from the outside world or emitted by other workers. Examples of events could be an incoming HTTP request, or that a certain file finished loading into memory etc.
At the time of writing, there are a number of interesting reactive / event driven platforms available, and more will come in the future. Some of the more popular ones seems to be:
Vert.x
Akka
Node.JS (JavaScript)
ACTORS vs CHANNELS
Actors and channels are two similar examples of assembly line (or reactive / event driven) models.
In the actor model each worker is called an actor. Actors can send messages directly to each other. Messages are sent and processed asynchronously. Actors can be used to implement one or more job processing assembly lines, as described earlier. Here is a diagram illustrating the actor model:
In the channel model, workers do not communicate directly with each other. Instead they publish their messages (events) on different channels. Other workers can then listen for messages on these channels without the sender knowing who is listening.
What are the adventages of “Assembly line (reactive, / event driven) “ concurrency model?
The assembly line concurrency model has several advantages compared to the parallel worker model:
[1] No Shared State
The fact that workers share no state with other workers means that they can be implemented without having to think about all the concurrency problems that may arise from concurrent access to shared state. This makes it much easier to implement workers. You implement a worker as if it was the only thread performing that work - essentially a singlethreaded implementation.
[2] Stateful workers
Since workers know that no other threads modify their data, the workers can be stateful. By stateful I mean that they can keep the data they need to operate in memory, only writing changes back the eventual external storage systems. A stateful worker can therefore often be faster than a stateless worker.
[3] Better Hardware Conformity
Singlethreaded code has the advantage that it often conforms better with how the underlying hardware works. First of all, you can usually create more optimized data structures and algorithms when you can assume the code is executed in single threaded mode.
Second, singlethreaded stateful workers can cache data in memory as mentioned above. When data is cached in memory there is also a higher probability that this data is also cached in the CPU cache of the CPU executing the thread. This makes accessing cached data even faster.
I refer to it as hardware conformity when code is written in a way that naturally benefits from how the underlying hardware works. Some developers call this mechanical sympathy. I prefer the term hardware conformity because computers have very few mechanical parts, and the word “sympathy” in this context is used as a metaphor for “matching better” which I believe the word “conform” conveys reasonably well. Anyways, this is nitpicking. Use whatever term you prefer.
[4] Job Ordering is possible
It is possible to implement a concurrent system according to the assembly line concurrency model in a way that guarantees job ordering. Job ordering makes it much easier to reason about the state of a system at any given point in time. Furthermore, you could write all incoming jobs to a log. This log could then be used to rebuild the state of the system from scratch in case any part of the system fails. The jobs are written to the log in a certain order, and this order becomes the guaranteed job order.
Implementing a guaranteed job order is not necessarily easy, but it is often possible. If you can, it greatly simplifies tasks like backup, restoring data, replicating data etc. as this can all be done via the log file(s).
How Do Concurrent Modules Execute?
https://www.baeldung.com/concurrency-principles-patterns
It’s been a while since Moore’s Law hit a wall with respect to the clock speed of the processor. Instead, since we must grow, we’ve started to pack multiple processors onto the same chip, often called multicore processors. But still, it’s not common to hear about processors that have more than 32 cores.
Now, we know that a single core can execute only one thread, or set of instructions, at a time. However, the number of processes and threads can be in hundreds and thousands, respectively. So, how does it really work? This is where the operating system simulates concurrency for us. The operating system achieves this by time-slicing — which effectively means that the processor switches between threads frequently, unpredictably, and non-deterministically.
What are the problems in Concurrent Programming?
For a very large part, our experience with concurrent programming involves using native threads with shared memory.
Common problems:
[1] Mutual Exclusion (Synchronization Primitives): Interleaving threads need to have exclusive access to shared state or memory to ensure the correctness of programs. The synchronization of shared resources is a popular method to achieve mutual exclusion. There are several synchronization primitives available to use — for example, a lock, monitor, semaphore, or mutex. However, programming for mutual exclusion is error-prone and can often lead to performance bottlenecks. There are several well-discussed issues related to this like deadlock and livelock.
[2] Context Switching (Heavyweight Threads): Every operating system has native, albeit varied, support for concurrent modules like process and thread. As discussed, one of the fundamental services that an operating system provides is scheduling threads to execute on a limited number of processors through time-slicing. Now, this effectively means that threads are frequently switched between different states. In the process, their current state needs to be saved and resumed. This is a time-consuming activity directly impacting the overall throughput.
List design patterns used to achieve high concurrency
[1] Actor based concurrency
[2] Event based concurrency
[3] Non-blocking algoithms
What is a “concurrency model”?
Concurrent systems can be implemented using different concurrency models. A concurrency model specifies how threads in the the system collaborate to complete the tasks they are are given. Different concurrency models split the tasks in different ways, and the threads may communicate and collaborate in different ways.
What is the Java native concurrency model?
It is based on:
Threads
Semaphores
Locks
Synchronization (monitors)
How you can create and start Thread in java?
[1] Thread subclass
create a subclass of Thread and override the run() method. The run() method is what is executed by the thread after you call start().
public class MyThread extends Thread {
public void run(){
System.out.println("MyThread running");
} }
MyThread myThread = new MyThread();
myTread.start();
[2] Runnable Interface Implementation
The second way to specify what code a thread should run is by creating a class that implements the java.lang.Runnable interface. A Java object that implements the Runnable interface can be executed by a Java Thread.
What is a race condition?
A race condition is a concurrency problem that may occur inside a critical section. A critical section is a section of code that is executed by multiple threads and where the sequence of execution for the threads makes a difference in the result of the concurrent execution of the critical section.
When the result of multiple threads executing a critical section may differ depending on the sequence in which the threads execute, the critical section is said to contain a race condition. The term race condition stems from the metaphor that the threads are racing through the critical section, and that the result of that race impacts the result of executing the critical section.
There are 2 types of Race conditions:
1) Read-modify-write
2) check-then-act
Describe two types of race condition
Race conditions can occur when two or more threads read and write the same variable according to one of these two patterns:
- Read-modify-write
- Check-then-act
[1] Read-modify-write
The read-modify-write pattern means, that two or more threads first read a given variable, then modify its value and write it back to the variable. For this to cause a problem, the new value must depend one way or another on the previous value. The problem that can occur is, if two threads read the value (into CPU registers) then modify the value (in the CPU registers) and then write the values back.
[2] Check-then-act
The check-then-act pattern means, that two or more threads check a given condition, for instance if a Map contains a given value, and then go on to act based on that information, e.g. taking the value from the Map. The problem may occur if two threads check the Map for a given value at the same time - see that the value is present - and then both threads try to take (remove) that value. However, only one of the threads can actually take the value. The other thread will get a null value back. This could also happen if a Queue was used instead of a Map.
Give an example of “Read-modify-Write” critical section and explain when race condition can occur
As mentioned above, a read-modify-write critical section can lead to race condition
public class Counter {
protected long count = 0;
public void add(long value){
this.count = this.count + value;
} }
Imagine if two threads, A and B, are executing the add method on the same instance of the Counter class. There is no way to know when the operating system switches between the two threads. The code in the add() method is not executed as a single atomic instruction by the Java virtual machine. Rather it is executed as a set of smaller instructions, similar to this:
1) Read this.count from memory into register.
2) Add value to register.
3) Write register to memory.
The code in the add() method in the example earlier contains a critical section. When multiple threads execute this critical section, race conditions occur.
More formally, the situation where two threads compete for the same resource, where the sequence in which the resource is accessed is significant, is called race conditions. A code section that leads to race conditions is called a critical section.
Give an example of “Check-Then-Act” critical section
As also mentioned above, a check-then-act critical section can also lead to race conditions. If two threads check the same condition, then act upon that condition in a way that changes the condition it can lead to race conditions. If two threads both check the condition at the same time, and then one thread goes ahead and changes the condition, this can lead to the other thread acting incorrectly on that condition.
public class CheckThenActExample {
public void checkThenAct(Map sharedMap) {
if(sharedMap.containsKey("key")){
String val = sharedMap.remove("key");
if(val == null) {
System.out.println("Value for 'key' was null");
}
} else {
sharedMap.put("key", "value");
}
} }
If two or more threads call the checkThenAct() method on the same CheckThenActExample object, then two or more threads may execute the if-statement at the same time, evaluate sharedMap.containsKey(“key”) to true, and thus move into the body code block of the if-statement. In there, multiple threads may then try to remove the key,value pair stored for the key “key”, but only one of them will actually be able to do it. The rest will get a null value back, since another thread already removed the key,value pair.
How can we prevent race conditions?
To prevent race conditions from occurring you must make sure that the critical section is executed as an atomic instruction. That means that once a single thread is executing it, no other threads can execute it until the first thread has left the critical section.
Race conditions can be avoided by proper thread synchronization in critical sections. Thread synchronization can be achieved using a synchronized block of Java code. Thread synchronization can also be achieved using other synchronization constructs like locks or atomic variables like java.util.concurrent.atomic.AtomicInteger.
How can we increase Critical Section Throughput?
For smaller critical sections making the whole critical section a synchronized block may work. But, for larger critical sections it may be beneficial to break the critical section into smaller critical sections, to allow multiple threads to execute each a smaller critical section. This may decrease contention on the shared resource, and thus increase throughput of the total critical section.
Here is a very simplified Java code example to show what I mean:
public class TwoSums {
private int sum1 = 0;
private int sum2 = 0;
public void add(int val1, int val2){
synchronized(this){
this.sum1 += val1;
this.sum2 += val2;
}
} }
Notice how the add() method adds values to two different sum member variables. To prevent race conditions the summing is executed inside a Java synchronized block. With this implementation only a single thread can ever execute the summing at the same time.
However, since the two sum variables are independent of each other, you could split their summing up into two separate synchronized blocks, like this:
public class TwoSums {
private int sum1 = 0;
private int sum2 = 0;
private Integer sum1Lock = new Integer(1);
private Integer sum2Lock = new Integer(2);
public void add(int val1, int val2){
synchronized(this.sum1Lock){
this.sum1 += val1;
}
synchronized(this.sum2Lock){
this.sum2 += val2;
}
} }
Now two threads can execute the add() method at the same time. One thread inside the first synchronized block, and another thread inside the second synchronized block. The two synchronized blocks are synchronized on different objects, so two different threads can execute the two blocks independently. This way threads will have to wait less for each other to execute the add() method.
What is a critical section?
A critical section is a section of code that is executed by multiple threads and where the sequence of execution for the threads makes a difference in the result of the concurrent execution of the critical section
What does it mean ‘Thread safe’?
Code that is safe to call by multiple threads simultaneously is called thread safe. If a piece of code is thread safe, then it contains no race conditions. Race condition only occur when multiple threads update shared resources. Therefore it is important to know what resources Java threads share when executing:
a) local variables
Local variables are stored in each thread’s own stack. That means that local variables are never shared between threads. That also means that all local primitive variables are thread safe.
b) local object refrences
Local references to objects are a bit different. The reference itself is not shared. The object referenced however, is not stored in each threads’s local stack. All objects are stored in the shared heap.
If an object created locally never escapes the method it was created in, it is thread safe. In fact you can also pass it on to other methods and objects as long as none of these methods or objects make the passed object available to other threads.
c) object member variables
Object member variables (fields) are stored on the heap along with the object. Therefore, if two threads call a method on the same object instance and this method updates object member variables, the method is not thread safe
What is immutability and how it prevents race conditions?
Race conditions occur only if multiple threads are accessing the same resource, and one or more of the threads write to the resource. If multiple threads read the same resource race conditions do not occur.
We can make sure that objects shared between threads are never updated by any of the threads by making the shared objects immutable, and thereby thread safe
Describe ‘The Java Memory Model’
The Java memory model used internally in the JVM divides memory between thread stacks and the heap.
Each thread running in the Java virtual machine has its own thread stack. The thread stack contains information about what methods the thread has called to reach the current point of execution. I will refer to this as the “call stack”. As the thread executes its code, the call stack changes.
The thread stack also contains all local variables for each method being executed (all methods on the call stack). A thread can only access it’s own thread stack. Local variables created by a thread are invisible to all other threads than the thread who created it. Even if two threads are executing the exact same code, the two threads will still create the local variables of that code in each their own thread stack. Thus, each thread has its own version of each local variable.
All local variables of primitive types ( boolean, byte, short, char, int, long, float, double) are fully stored on the thread stack and are thus not visible to other threads. One thread may pass a copy of a pritimive variable to another thread, but it cannot share the primitive local variable itself.
The heap contains all objects created in your Java application, regardless of what thread created the object. This includes the object versions of the primitive types (e.g. Byte, Integer, Long etc.). It does not matter if an object was created and assigned to a local variable, or created as a member variable of another object, the object is still stored on the heap.
A local variable may be of a primitive type, in which case it is totally kept on the thread stack.
A local variable may also be a reference to an object. In that case the reference (the local variable) is stored on the thread stack, but the object itself if stored on the heap.
An object may contain methods and these methods may contain local variables. These local variables are also stored on the thread stack, even if the object the method belongs to is stored on the heap.
An object’s member variables are stored on the heap along with the object itself. That is true both when the member variable is of a primitive type, and if it is a reference to an object.
Objects on the heap can be accessed by all threads that have a reference to the object. When a thread has access to an object, it can also get access to that object’s member variables. If two threads call a method on the same object at the same time, they will both have access to the object’s member variables, but each thread will have its own copy of the local variables.
Describe Hardware Memory Architecture
https://jenkov.com/tutorials/java-concurrency/java-memory-model.html
Modern hardware memory architecture is somewhat different from the internal Java memory model. It is important to understand the hardware memory architecture too, to understand how the Java memory model works with it.
A modern computer often has 2 or more CPUs in it. Some of these CPUs may have multiple cores too. The point is, that on a modern computer with 2 or more CPUs it is possible to have more than one thread running simultaneously. Each CPU is capable of running one thread at any given time. That means that if your Java application is multithreaded, one thread per CPU may be running simultaneously (concurrently) inside your Java application.
Each CPU contains a set of registers which are essentially in-CPU memory. The CPU can perform operations much faster on these registers than it can perform on variables in main memory. That is because the CPU can access these registers much faster than it can access main memory.
Each CPU may also have a CPU cache memory layer. In fact, most modern CPUs have a cache memory layer of some size. The CPU can access its cache memory much faster than main memory, but typically not as fast as it can access its internal registers. So, the CPU cache memory is somewhere in between the speed of the internal registers and main memory. Some CPUs may have multiple cache layers (Level 1 and Level 2), but this is not so important to know to understand how the Java memory model interacts with memory. What matters is to know that CPUs can have a cache memory layer of some sort.
A computer also contains a main memory area (RAM). All CPUs can access the main memory. The main memory area is typically much bigger than the cache memories of the CPUs.
Typically, when a CPU needs to access main memory it will read part of main memory into its CPU cache. It may even read part of the cache into its internal registers and then perform operations on it. When the CPU needs to write the result back to main memory it will flush the value from its internal register to the cache memory, and at some point flush the value back to main memory.
The values stored in the cache memory is typically flushed back to main memory when the CPU needs to store something else in the cache memory. The CPU cache can have data written to part of its memory at a time, and flush part of its memory at a time. It does not have to read / write the full cache each time it is updated. Typically the cache is updated in smaller memory blocks called “cache lines”. One or more cache lines may be read into the cache memory, and one or mor cache lines may be flushed back to main memory again.
What is Java synchronized block?
A Java synchronized block marks a method or a block of code as synchronized. A synchronized block in Java can only be executed a single thread at a time (depending on how you use it). Java synchronized blocks can thus be used to avoid race conditions.
Synchronized blocks in Java are marked with the synchronized keyword. A synchronized block in Java is synchronized on some object. All synchronized blocks synchronized on the same object can only have one thread executing inside them at the same time. All other threads attempting to enter the synchronized block are blocked until the thread inside the synchronized block exits the block.
The synchronized keyword can be used to mark four different types of blocks:
- Instance methods
- Static methods
- Code blocks inside instance methods
- Code blocks inside static methods
What is Semaphore? What is it used for?
A Semaphore is a thread synchronization construct that can be used either to send signals between threads to avoid missed signals, or to guard a critical section like you would with a lock. Java 5 comes with semaphore implementations in the java.util.concurrent package so you don’t have to implement your own semaphores.
A Semaphore is used to limit the number of threads that want to access a shared resource. In other words, it is a non-negative variable that is shared among the threads known as a counter. It sets the limit of the threads. A mechanism in which a thread is waiting on a semaphore can be signaled by other threads.
If counter > 0, access to shared resources is provided.
If counter = 0, access to shared resources is denied.
In short, the counter keeps tracking the number of permissions it has given to a shared resource. Therefore, semaphore grants permission to threads to share a resource.
Semaphore controls over the shared resource through a counter variable. The counter is a non-negative value. It contains a value either greater than 0 or equal to 0.
If counter > 0, the thread gets permission to access the shared resource and the counter value is decremented by 1.
Else, the thread will be blocked until a permit can be acquired.
When the execution of the thread is completed then there is no need for the resource and the thread releases it. After releasing the resource, the counter value incremented by 1.
If another thread is waiting for acquiring a resource, the thread will acquire a permit at that time.
If counter = 0, the thread does not get permission to access the shared resource.
Compare Thread Synchronization Mechanisms in Java
Monitor, Lock and Semaphore
https://medium.com/swlh/comparing-thread-synchronization-mechanisms-in-java-53e66ea059be
What is multithreading?
Multithreading is the ability to have multiple threads executing concurrently. While each thread shares the same process resources, they operate independently of each other.
