DEV Community: Piyush

Deadlocking

Piyush — Fri, 07 Jan 2022 14:08:41 +0000

Understanding Locks

In Java, Lock is an interface available in the Java.util.concurrent.locks package. Java lock acts as thread synchronization mechanisms that are similar to the synchronized blocks.

When threads in a process share and update the same data, their activities must be synchronized to avoid errors. In Java, this is done with the "synchronized" keyword, or with wait and notify. Synchronization is achieved by the use of locks, each of which is associated with an object by the JVM (Java Virtual Machine). For a thread to work on an object, it must have control over the lock associated with it, it must "hold" the lock. Only one thread can hold a lock at a time. If a thread tries to take a lock that is already held by another thread, then it must wait until the lock is released. When this happens, there is so called "contention" for the lock.
There are four kinds of locks:

Fat Locks: A fat lock is a lock with a history of contention (several threads trying to take the lock simultaneously), or a lock that has been waited on.
Thin Locks: A thin lock is a lock that does not have any contention.
Recursive Locks: A recursive lock is a lock that has been taken by a thread several times without having been released.
Lazy Locks: A lazy lock is a lock that is not released when a 'critical section' is excited. Once a lazy lock is acquired by a thread, other threads that try to acquire the lock have to ensure that the lock is, or can be, released.

Spinning and Sleeping

Spinning occurs when a thread that wants a specific lock continuously checks that lock to see if it is still taken, instead of yielding CPU-time to another thread.
Alternatively, a thread that tries to take a lock that is already held waits for notification from the lock and goes into a sleeping state. The thread will then wait passively for the lock to be released.

Lock Chains

Several threads can be tied up in what is called lock chains. Although they appear somewhat complex, lock chains are fairly. They can be defined as follows:

Threads A and B form a lock chain if thread A holds a lock that thread B is trying to take. If A is not trying to take a lock, then the lock chain is 'open'.
If A->B is a lock chain, and B->C is a lock chain, then A->B->C is a more complete lock chain.
If there is no additional thread waiting for a lock held by C, then A->B->C is a complete and open lock chain.

Lock Chain Types

There are three possible kinds of lock chains: open, Deadlock and Blocked lock chains.

Open Chains

Open lock chains represent a straight dependency, thread A is waiting for B which is waiting for C, and so on. If we have long open lock chains, the application might be wasting time waiting for locks. We then want to consider how locks are used for synchronization in the application.

Deadlock Chains

A deadlocked, or circular, lock chain consists of a chain of threads, in which the first thread in the chain is waiting for the last thread in the chain. In the simplest case, thread A is waiting for thread B, while thread B is waiting for thread A.
"A deadlocked chain has no head."

Blocked Chains

A blocked lock chain is made up of a lock chain whose head thread is also part of another lock chain, which can be either open or deadlocked.

Thread Congestion In Java

Piyush — Sun, 02 Jan 2022 14:19:24 +0000

Thread Congestion can occur when two or more threads are trying to access the same, guarded data structure at the same time. "Guarded" mean that the data structure is guarded using synchronized blocks or a concurrent data structure so that the data structure is thread safe. The resulting thread congestion means that the threads trying to access the shared data structure are spending a high amount of time waiting in line to access the data structure - wasting valuable execution time on waiting.

Thread Blocking Data Structure May Cause Thread Congestion

A data structure which blocks threads from accessing it - depending on what other threads are currently accessing it, may cause thread congestion. If more than one thread accesses such a data structure at the same time, one or more of the threads may be queued up waiting to access the data structure. The queueing of threads is not visible in code. This queueing happens inside the JVM. Therefore thread congestion is not easy to spot simply by looking at the code. We need profiling tools to detect thread congestion.

A Blocked Thread Loses Execution Time

While a thread is blocked trying to execute a blocking data structure, it cannot do anything. While being blocked the thread loses possible execution time. The longer the thread is blocked, the more potential execution time it loses.

More Threads - Higher Congestion

The more the number of threads that attempts to access a shared data structure, the higher the risk of thread congestion.

Alleviating Thread Congestion

To lessen thread congestion we must reduce the number of threads trying to access the blocking data structure at the same time. There are several ways to reduce thread congestion namely:

Multiple Data Structures
Non-blocking Concurrency Algorithms

Multiple Data Structures
One way to alleviate thread congestion is to give each consuming thread its own queue, and have the producing thread distribute the objects among those data structures.
Non-blocking Concurrency Algorithms
Another way is to use "non-blocking concurrency algorithms" where the threads accessing the data structure are never blocked.

Exceptions "against" Errors

Piyush — Sun, 02 Jan 2022 08:26:59 +0000

Common misconception during programming

In java, both 'Exceptions' and 'Errors' are subclasses of "java.lang.throwable" class.
Error refers to an illegal operation performed by the user which results in abnormal behavior of the program. Programming errors many a time remain undetected until the program is executed or compiled. Some errors inhibit the program from getting executed. Thus making it necessary to remove errors before compiling or executing. Errors are of three types:

Compile-time errors
Run-time errors
Logical errors

Compile-time errors
Compile-time errors are those errors which prevent the code from running because of an incorrect syntax such as a missing semicolon at the end of a statement or a missing bracket, etc. These errors are detected by the java compiler and an error message is displayed onto the screen while compiling. Compile-time errors are also referred to as "Syntax errors".

Run-time errors
Run-time errors occur during the execution of the program. Sometimes these are discovered when the user enters an invalid data or data which is not relevant. Run-time errors occur when a program does not contain any syntax errors but asks the computer to do something that the computer is unable to reliably do. The compiler has no technique to detect these kind of errors. It is the JVM (Java Virtual Machine) which detects it while the program is running.

Logical errors
When the program compiles and executes, but does the wrong thing or returns an incorrect result or shows no output; it is a logical error. These errors are neither detected by compiler nor by JVM. The system has no idea what the program is supposed to do, so it provides an additional information to help find the error. Logical errors are also called Semantic errors.

Exceptions in java refer to an unwanted event, which occurs during the execution of a program, i.e. at run-time, that disrupts the normal flow of the program's instructions. Exceptions are the conditions that occur at runtime and may cause the termination of the program. But they are recoverable using try, catch and throw keywords. Exceptions are divided into two categories:

Checked exceptions
Un-checked exceptions

Checked exceptions are like IOException known to the compiler at compile time .
Un-checked exceptions are like ArrayIndexOutOfBoundException known to the compiler at runtime, mostly caused by the program written by programmer.

Kadane's Algorithm

Piyush — Sat, 01 Jan 2022 14:32:41 +0000

Maximum Subarray Sum: Kadane's Algorithm

If you are competitive programming or preparing for campus placements or technical interviews, you might have probably come across something like this:
*Given an array arr[] of N integers. Find the contiguous sub-array which has the maximum sum and return its sum. *
If not, so does the "Kadane's Algorithm" rings any bell?
Kadane's algorithm is an iterative dynamic programming approach in which we search for a maximum sum contiguous subarray within a one-dimensional numeric array.

Working of Kadane's Algorithm
Some may think okay it's just the sum of all elements in an array. But an array may have negative integer elements, which decreases the total array's sum.
Thus we can say that the sum of all array elements isn't always the case.
A simple idea of Kadane's algorithm is to look for all positive contiguous segments of array and keep track of the maximum sum contiguous subarray among all positive segments.
An array is a contiguous memory block. So, a subarray is a slice of contiguous array that maintains the order of the elements.
Let us consider an array:
arr={1,2,3,4}
For this array, the sub-arrays are:
For elements at 0th index {1},{1,2},{1,2,3},{1,2,3,4}
For elements at 1st index {2},{2,3},{2,3,4}
For elements at 2nd index {3},{3,4}
For elements at 3rd index {4}
Now we know sub-arrays for an array.
Brute Force Approach
The brute force solution calculates the sum of each sub-array and then compares the results to determine the maximum sum of all sub-arrays sums. This method is straight forward, but it is not used commonly.
This is because it has a time complexity of O(N^3) and O(N) space complexity.
As we know, while writing any program, Time and Space Complexity plays a vital role in choosing the algorithm. Therefore, Kadane's algorithm is used because of its advantage considering time and space complexity.
Kadane's Algorithm

First, we will consider two elements, one which stores the maximum end of the subarray and another which stores the maximum sum far.
Let the two elements be named variables as max_end and max_far, respectively.
We will initialise both as 0.
Each time we get a positive sum, we compare it with max_end and update max_far if it is greater than it. The Time and Space complexity are as: Time Complexity: O(N) Space Complexity: O(1) Comparing the "Time and Space Complexity" of 'Brute Force Approach' and of 'Kadan's Algorithm', the latter is better when it comes to solving the same problem. Hence, Kadane's algorithm is preferred method when it comes to finding the maximum contiguous sub-array sum.

Special Case
For all the negative numbers in an array, all the elements in array are less than 0. So, we compare the sum of the consecutive elements with the current element from the array.