Multithreading: Threads, Synchronization, Deadlocks & Concurrency

TAKEAWAYS:

• Understand the thread lifecycle (New, Runnable, Blocked, Waiting, Terminated) and how threads transition between states.
• Learn synchronization using synchronized blocks/methods and wait(), notify(), and notifyAll() for thread coordination.
• Identify deadlocks and race conditions, and apply strategies to prevent them (e.g., lock ordering, timeouts).
• Compare thread creation methods (Runnable vs. Thread class) and thread pools (ExecutorService).
• Apply concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList) for thread-safe operations.
• Recognize real-world uses of multithreading in banks (transaction processing), e-commerce (order handling), and messaging apps (chat servers).

What is Multithreading?

Multithreading allows a program to execute multiple threads concurrently, sharing the same memory space. A thread is the smallest unit of execution within a process. Unlike single-threaded programs, multithreaded programs can perform multiple tasks simultaneously, improving efficiency.

Key Concepts:

1. Process vs. Thread:

   • A process is an independent program with its own memory space.
   • A thread is a lightweight subprocess within a process, sharing memory with other threads in the same process.
   • Advantages of threads:
     • Faster creation and destruction than processes.
     • Lower memory overhead (share heap memory).
     • Easier communication (shared memory).

2. Thread Lifecycle:

   flowchart TD
     A["New"] -->|"start()"| B["Runnable"]
     B --> C["Running"]
     C -->|"blocked"| D["Blocked"]
     C -->|"wait()"| E["Waiting"]
     E -->|"notify()"| B
     C --> F["Terminated"]

   • New: Thread is created but not yet started.
   • Runnable: Thread is ready to run (may or may not be executing).
   • Running: Thread is executing.
   • Blocked/Waiting: Thread is paused (e.g., waiting for I/O or monitor lock).
   • Terminated: Thread has completed execution.

Creating Threads in Java

Java provides two ways to create threads:

1. Extending Thread class:

   class MyThread extends Thread {
       public void run() {
           System.out.println("Thread running");
       }
   }
   

   MyThread t1 = new MyThread();
   t1.start(); // Starts the thread
   

2. Implementing Runnable interface (preferred):

   class MyRunnable implements Runnable {
       public void run() {
           System.out.println("Runnable thread running");
       }
   }
   

   Thread t2 = new Thread(new MyRunnable());
   t2.start();
   

Trace Example: Thread Execution

Note: Output order is non-deterministic due to thread scheduling by the JVM.

In the Real World

1. eSewa (Nepal):

   • Uses multithreading to handle simultaneous payment requests from users. Each payment transaction runs in a separate thread to ensure quick processing and avoid delays during peak hours (e.g., festival seasons).
   • Key Idea: Thread pools manage concurrent transactions without overloading the server.

2. Khalti (Nepal):

   • Employs multithreading for real-time fraud detection. While one thread processes payments, another monitors transactions for suspicious activity (e.g., duplicate payments or unusual patterns).
   • Key Idea: Separation of concerns via threads improves security and responsiveness.

3. Pathao (Nepal/Global):

   • Uses multithreading to match drivers and riders dynamically. Threads handle:
     • Rider location updates (GPS data).
     • Driver availability checks.
     • Order dispatching to the nearest driver.
   • Key Idea: Concurrent processing reduces wait times for riders.

4. Bank Loan Processing (Nepalese Banks):

   • Imagine a bank processing loan applications. A single-threaded system would handle one application at a time, causing delays. Instead, banks use multithreading:
     • Thread 1: Validates customer documents.
     • Thread 2: Checks credit history.
     • Thread 3: Calculates interest and repayment schedule.
   • Worked Example: A loan of ₹5,00,000 at 8% annual interest for 5 years is processed concurrently:
     • Thread 1: Fetches customer data (e.g., salary proof).
     • Thread 2: Queries credit bureau for score (e.g., 720).
     • Thread 3: Computes EMI using the formula: $$EMI=\frac{P\times r\times (1+r{)}^n}{(1+r{)}^n-1}$$ Where:
       • $P=5,00,000$, $r=0.08/12$, $n=60$ (months).
       • Result: EMI ≈ ₹10,801/month.
     • Output: Loan approved with EMI details sent to the customer’s email (handled by Thread 4).

Synchronization and Thread Safety

Problem: Without synchronization, threads can interfere with shared data, leading to race conditions (inconsistent results due to unsynchronized access).

Solutions:

1. synchronized Keyword:

   • Ensures only one thread can access a block/method at a time.
   • Example: Thread-safe counter.

     class Counter {
         private int count = 0;
         public synchronized void increment() {
             count++; // Atomic operation
         }
         public int getCount() {
             return count;
         }
     }
     

   • Visualization: Synchronized block as a locked door (only one thread enters at a time).

2. volatile Keyword:

   • Ensures visibility of changes across threads (no caching).
   • Example: A flag to stop threads.

     volatile boolean flag = true;
     while (flag) {
         // Work
     }
     

3. wait(), notify(), notifyAll():

   • Used for inter-thread communication.
   • Example: Producer-Consumer problem.

     class SharedBuffer {
         private int item;
         private boolean empty = true;
         public synchronized void produce(int value) {
             while (!empty) wait(); // Wait if buffer is full
             item = value;
             empty = false;
             notify(); // Notify consumer
         }
         public synchronized int consume() {
             while (empty) wait(); // Wait if buffer is empty
             empty = true;
             notify(); // Notify producer
             return item;
         }
     }
     

   • State Diagram:

     flowchart TD
       A["Producer: produce(10)"] -->|"buffer empty"| B["Buffer: item=10, empty=false"]
       B -->|"notify()"| C["Consumer: consume()"]
       C -->|"buffer empty"| D["Buffer: item=?, empty=true"]
       D -->|"notify()"| A

Deadlocks and How to Avoid Them

A deadlock occurs when two or more threads are blocked forever, each waiting for the other to release a lock.

Conditions for Deadlock (The "Deadly Embrace"):

1. Mutual Exclusion: Threads claim exclusive locks.
2. Hold and Wait: Threads hold locks while waiting for others.
3. No Preemption: Locks cannot be forcibly released.
4. Circular Wait: Threads form a circular chain of dependencies.

Example Deadlock:

class DeadlockExample {
    private final Object lock1 = new Object();
    private final Object lock2 = new Object();
    public void thread1() {
        synchronized (lock1) {
            System.out.println("Thread 1: Lock 1 acquired");
            synchronized (lock2) {
                System.out.println("Thread 1: Lock 2 acquired");
            }
        }
    }
    public void thread2() {
        synchronized (lock2) {
            System.out.println("Thread 2: Lock 2 acquired");
            synchronized (lock1) {
                System.out.println("Thread 2: Lock 1 acquired");
            }
        }
    }
}

Result: Both threads acquire lock1 and lock2 in reverse order, causing a deadlock.

Prevention Strategies:

Thread Pools and Executor Framework

Creating threads manually is inefficient. Java’s ExecutorService manages a pool of threads.

Key Classes:

1. ThreadPoolExecutor:

   • Core pool size, maximum pool size, and queue capacity.
   • Example:

     ExecutorService executor = Executors.newFixedThreadPool(5);
     executor.submit(() -> System.out.println("Task running"));
     executor.shutdown();
     

2. Predefined Thread Pools:

   • newFixedThreadPool(n): Fixed number of threads.
   • newCachedThreadPool(): Scales dynamically.
   • newSingleThreadExecutor(): Single thread.

Visualization: Thread Pool Workflow

flowchart TD
  A["Task Submission"] --> B["Task Queue"]
  B --> C["Worker Thread 1"]
  B --> D["Worker Thread 2"]
  C -->|"Task Complete"| E["Return to Pool"]
  D -->|"Task Complete"| E
  E --> B

Trace Example: Task Execution

Concurrent Collections

Java provides thread-safe collections in the java.util.concurrent package:

• ConcurrentHashMap: Thread-safe HashMap.
• CopyOnWriteArrayList: Thread-safe ArrayList (snapshot on modification).
• BlockingQueue: Thread-safe queue for producer-consumer.

Example: ConcurrentHashMap

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("Nepal", 29); // Thread-safe put
int value = map.get("Nepal"); // Thread-safe get

Exam Tip

1. Thread Lifecycle: Be ready to draw the lifecycle diagram and explain state transitions (e.g., wait() moves a thread to Waiting state).
2. Synchronization: Know when to use synchronized, volatile, and wait()/notify(). Common exam questions ask about race conditions in shared variables.
3. Deadlocks: Memorize the 4 conditions and how to prevent them (e.g., lock ordering). A classic deadlock scenario (like the one above) is often tested.
4. Thread Pools: Understand the difference between newFixedThreadPool and newCachedThreadPool. Trace examples of task execution.
5. Real-World Scenarios: Relate multithreading to systems like eSewa (payment processing), Khalti (fraud detection), or Pathao (ride matching). Examiners may ask how threads improve performance in these cases.
6. Code Traces: Practice tracing code with multiple threads. Show the order of execution and shared variable states in tables (like the counter example above).
7. Short Answer: For 2-mark questions, define terms like:
   • Thread: "A lightweight subprocess within a process that shares memory."
   • Race Condition: "An inconsistency in shared data due to unsynchronized access by threads."
   • Deadlock: "A state where two or more threads are blocked forever, each waiting for a resource held by the other."

Pro Tip: For practical questions, always:

1. Draw the thread lifecycle or deadlock scenario.
2. Show a table of variable states for shared data.
3. Write a short code snippet to illustrate the concept.