Concurrency Flashcards
What is a race condition?
Race condition is the only concurrent problem that can happen when two threads manipulate the same state (value) in the same time-lapse, the last thread to write the state will overwrite the state modification of the first thread.
What is mutual exclusion?
Mutual Exclusion also known as Mutex was first identified by Dijkstra. When a process is accessing shared variable is known as in critical section. When no two processes can be in Critical Section at the same time , this state is known as Mutual Exclusion.
It is property of concurrency control which is used to prevent race conditions.
Mutual Exclusion Devices: Locks, Reader’s Writer’s Problem,recursive locks,semaphores,monitor, message passing etc.
Requirements:
- No more than one thread can be in its critical section at any one time.
- A thread which dies in its critical non-critical section will not affect the others’ ability to continue.
- No deadlock: if a thread wants to enter its critical section then it will eventually be allowed to do so.
- No starvation.
- Threads are not forced into lock-step execution of their critical sections.
What is starvation and when does it occur?
Starvation occurs if two threads are running and one thread creates a lock which prevents a second thread from using a method. Normally the first thread should remove the lock quickly and the second thread can use the resource. If the first thread does not remove the lock, the second thread cannot continue.
What is a deadlock?
Deadlocks are the worst kind of starvation. They occur when two threads are both holding locks which the other needs to complete their task. Neither will give up its lock, which prevents the other from finishing, therefore neither can finish! There is no simple way to prevent deadlocks. They can be detected at runtime, but you need to think carefully about how threads will interact with locked objects.
Deadlock describes a situation where two or more threads are blocked forever, waiting for each other. Here’s an example.
Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time.
What is a synchronised method?
The Java programming language provides two basic synchronization idioms: synchronized methods and synchronized statements.
To make a method synchronized, simply add the synchronized keyword to its declaration:
public class SynchronizedCounter { private int c = 0;
public synchronized void increment() { c++; } public synchronized void decrement() { c--; } public synchronized int value() { return c; } }
If count is an instance of SynchronizedCounter, then making these methods synchronized has two effects:
- First, it is not possible for two invocations of synchronized methods on the same object to interleave. When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block (suspend execution) until the first thread is done with the object.
- Second, when a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of the object are visible to all threads.
Synchronized methods enable a simple strategy for preventing thread interference and memory consistency errors: if an object is visible to more than one thread, all reads or writes to that object’s variables are done through synchronized methods. (An important exception: final fields, which cannot be modified after the object is constructed, can be safely read through non-synchronized methods, once the object is constructed) This strategy is effective, but can present problems with liveness.
When does a memory consistency error occur?
Memory consistency errors occur when different threads have inconsistent views of what should be the same data.
How do you avoid a memory consistency error?
The key to avoiding memory consistency errors is understanding the happens-before relationship. This relationship is simply a guarantee that memory writes by one specific statement are visible to another specific statement.
What actions create a happens-before relationship?
There are several actions that create happens-before relationships. One of them is synchronization.
Two actions that create happens-before relationships:
- When a statement invokes Thread.start, every statement that has a happens-before relationship with that statement also has a happens-before relationship with every statement executed by the new thread. The effects of the code that led up to the creation of the new thread are visible to the new thread.
- When a thread terminates and causes a Thread.join in another thread to return, then all the statements executed by the terminated thread have a happens-before relationship with all the statements following the successful join. The effects of the code in the thread are now visible to the thread that performed the join.
What is thread interference and when does it happen?
Interference happens when two operations, running in different threads, but acting on the same data, interleave. This means that the two operations consist of multiple steps, and the sequences of steps overlap.
What are examples 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.
- 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, so…
What problems do thread present?
Threads communicate primarily by sharing access to fields and the objects reference fields refer to. This form of communication is extremely efficient, but makes two kinds of errors possible:
- thread interference
- memory consistency errors.
The tool needed to prevent these errors is synchronization.
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.
What is concurrency?
Concurrency means that an application is making progress on more than one task at the same time (concurrently). Well, if the computer only has one CPU the application may not make progress on more than one task at exactly the same time, but more than one task is being processed at a time inside the application. It does not completely finish one task before it begins the next. Instead, the CPU switches between the different tasks until the tasks are complete.
It is possible to have a concurrent application even though it only has a single thread running inside it.
What is parallelism?
Parallelism means that an application splits its tasks up into smaller subtasks which can be processed in parallel, for instance on multiple CPUs at the exact same time.
To achieve true parallelism your application must have more than one thread running, or at least be able to schedule tasks for execution in other threads, processes, CPUs, graphics cards etc.
As you can see, concurrency is related to how an application handles multiple tasks it works on. An application may process one task at at time (sequentially) or work on multiple tasks at the same time (concurrently).
Parallelism on the other hand, is related to how an application handles each individual task. An application may process the task serially from start to end, or split the task up into subtasks which can be completed in parallel.
As you can see, an application can be concurrent, but not parallel. This means that it processes more than one task at the same time, but the thread is only executing on one task at a time. There is no parallel execution of tasks going in parallel threads / CPUs.
An application can also be parallel but not concurrent. This means that the application only works on one task at a time, and this task is broken down into subtasks which can be processed in parallel. However, each task (+ subtask) is completed before the next task is split up and executed in parallel.
Additionally, an application can be neither concurrent nor parallel. This means that it works on only one task at a time, and the task is never broken down into subtasks for parallel execution.
Finally, an application can also be both concurrent and parallel, in that it both works on multiple tasks at the same time, and also breaks each task down into subtasks for parallel execution. However, some of the benefits of concurrency and parallelism may be lost in this scenario, as the CPUs in the computer are already kept reasonably busy with either concurrency or parallelism alone. Combining it may lead to only a small performance gain or even performance loss. Make sure you analyze and measure before you adopt a concurrent parallel model blindly.
How do you create and start a new thread?
Creating a thread in Java is done like this: Thread thread = new Thread();
To start the Java thread you will call its start() method, like this:
thread.start();
This example doesn’t specify any code for the thread to execute. Therfore the thread will stop again right away after it is started.
There are two ways to specify what code the thread should execute. The first is to create a subclass of Thread and override the run() method. The second method is to pass an object that implements Runnable (java.lang.Runnable) to the Thread constructor.
The first way to specify what code a thread is to run, is to create a subclass of Thread and override the run() method. The run() method is what is executed by the thread after you call start(). Here is an example of creating a Java Thread subclass:
public class MyThread extends Thread {
public void run(){ System.out.println("MyThread running"); } }
To create and start the above thread you can do like this:
MyThread myThread = new MyThread(); myTread.start();
You can also create an anonymous subclass of Thread like this:
Thread thread = new Thread(){ public void run(){ System.out.println("Thread Running"); } }
thread.start();
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.
The Runnable interface is a standard Java Interface that comes with the Java platform. The Runnable interface only has a single method run().
There are three ways to implement the Runnable interface:
- Create a Java class that implements the Runnable interface.
- Create an anonymous class that implements the Runnable interface.
- Create a Java Lambda that implements the Runnable interface.
Java Class Implements Runnable: public class MyRunnable implements Runnable {
public void run(){ System.out.println("MyRunnable running"); } }
All this Runnable implementation does is to print out the text MyRunnable running. After printing that text, the run() method exits, and the thread running the run() method will stop.
Anonymous Implementation of Runnable: Runnable myRunnable = new Runnable(){ public void run(){ System.out.println("Runnable running"); } }
Apart from being an anononymous class, this example is quite similar to the example that used a custom class to implement the Runnable interface.
What is a thread in java?
A Java Thread is like a virtual CPU that can execute your Java code - inside your Java application. when a Java application is started its main() method is executed by the main thread - a special thread that is created by the Java VM to run your application. From inside your application you can create and start more threads which can execute parts of your application code in parallel with the main thread.
Java threads are objects like any other Java objects. Threads are instances of class java.lang.Thread, or instances of subclasses of this class. In addition to being objects, java threads can also execute code.