Java - Week 10

Creating Threads in Java

Concurrency allows a program to execute multiple tasks simultaneously. In Java, this is achieved using threads. A thread is an independent path of execution within a program. There are two primary ways to create threads in Java:

1. Extending the Thread class.
2. Implementing the Runnable interface.

1. Extending the Thread Class

To create a thread by extending the Thread class, you must:

• Create a class that extends java.lang.Thread.
• Override the run() method. This method contains the code that will execute in parallel.
• Create an instance of your class and call its start() method. Important: You call start(), not run(). Calling start() tells the JVM to create a new thread and execute the run() method within that new thread.

public class Parallel extends Thread {
    private int id;
    
    public Parallel(int i) { 
        id = i; 
    }
    
    // The run() method defines the task for the thread
    public void run() {
        for (int j = 0; j < 5; j++) {
            System.out.println("My id is " + id);
            try {
                // Sleep for 1000 milliseconds (1 second) to simulate work
                // and allow context switching
                sleep(1000); 
            } catch (InterruptedException e) {
                System.out.println("Thread interrupted.");
            }
        }
    }
}

public class TestParallel {
    public static void main(String[] args) {
        Parallel[] p = new Parallel[5];
        
        for (int i = 0; i < 5; i++) {
            p[i] = new Parallel(i);
            // Start p[i].run() in a concurrent thread
            p[i].start(); 
        }
        // This loop generates 5 concurrent computations.
    }
}

2. Implementing the Runnable Interface

Because Java only supports single inheritance (a class can only extend one superclass), extending Thread can be limiting if your class already needs to extend another class. The preferred and more flexible approach is implementing the Runnable interface.

• Create a class that implements java.lang.Runnable.
• Implement the required run() method.
• To execute it, you must explicitly create a Thread object, passing your Runnable instance to its constructor, and then call start() on the Thread object.

// Implementing Runnable instead of extending Thread
public class Parallel implements Runnable { 
    private int id;
    
    public Parallel(int i) {
        id = i;
    }
    
    public void run() {
       // Implementation of the parallel task...
    }
}

public class TestParallelRunnable {
    public static void main(String[] args) {
        Parallel[] p = new Parallel[5];
        Thread[] t = new Thread[5];
        
        for (int i = 0; i < 5; i++) {
            p[i] = new Parallel(i);
            // Explicitly create a Thread, passing the Runnable object
            t[i] = new Thread(p[i]); 
            // Start the thread, which calls p[i].run()
            t[i].start(); 
        }
    }
}

// Creating and starting a thread using a lambda expression
Thread t = new Thread(() -> {
    System.out.println("Running in a new thread!");
});
t.start();

Thread Execution Order and join()

When multiple threads are started, their execution order is determined by the thread scheduler and is generally unpredictable. They execute asynchronously and their outputs will often be interleaved.

If the main program (or another thread) needs to wait for a thread to finish its execution before proceeding, you use the join() method. When you call t.join(), the current thread pauses execution and waits until thread t has fully completed.

// Assume PriSequence is a Thread that prints 5 numbers
Thread th1 = new PriSequence(10); // Prints 10-15
Thread th2 = new PriSequence(20); // Prints 20-25
Thread th3 = new PriSequence(30); // Prints 30-35

th1.start(); 
th2.start(); 
// th1 and th2 are now running concurrently. Their output will likely be interleaved.

// The main thread will pause here until th1 and th2 finish
th1.join(); 
th2.join(); 

// th3 will ONLY start after both th1 and th2 have fully completed.
th3.start(); 

Maintaining Data Consistency: Race Conditions

When multiple threads operate concurrently and share data, data consistency becomes a critical issue. If threads access and modify shared data without proper synchronization, the final outcome depends on the unpredictable timing of their execution.

The Bank Account Problem

Consider a banking system with an array of accounts. Two common operations are transfer() (moving money between two accounts) and audit() (summing all balances to ensure the total money in the bank remains constant).

// Thread 1 executing transfer
boolean transfer(double amount, int source, int target) {
    if (accounts[source] < amount) {
        return false;
    }
    // Step 1: Debit source
    accounts[source] -= amount; 
    
    // --- Context switch could happen here! ---
    
    // Step 2: Credit target
    accounts[target] += amount; 
    return true;
}

// Thread 2 executing audit
double audit() {
    double balance = 0.00;
    for (int i = 0; i < 100; i++) {
        balance += accounts[i];
    }
    return balance;
}

What goes wrong?

A Race Condition occurs when the audit() thread reads the accounts exactly between Step 1 and Step 2 of the transfer() thread.

If audit() runs after the source account has been debited but before the target account has been credited, the total calculated balance will temporarily appear to be less than the actual assets (e.g., short by 500.00). The total money in the system appears incorrect because the update operation wasn't completed as a single, uninterrupted unit.

Atomicity of Updates

An operation is atomic if it appears to the rest of the system to occur instantaneously. Even simple statements like m++ or accounts[source] -= amount are not atomic at the machine level; they involve reading a value, modifying it, and writing it back.

Consider two threads incrementing a shared variable n:

If execution is interleaved as follows due to time-slicing:

1. Thread 1: m = n; (Assume n starts at 5, so m = 5)
2. Thread 1: m++; (m becomes 6)
3. Thread 2: k = n; (Thread 2 reads the original n, so k = 5)
4. Thread 2: k++; (k becomes 6)
5. Thread 1: n = m; (n is set to 6)
6. Thread 2: n = k; (n is set to 6 again)

We expected n to increase by 2 (becoming 7), but it only increased by 1 because Thread 2 overwrote Thread 1's work.

Solving Race Conditions: Mutual Exclusion

To prevent race conditions, sections of code that access shared, modifiable data must be protected. These areas are called Critical Sections.

We need a mechanism to ensure that if one thread is executing inside a critical section, no other thread can enter that same critical section. This concept is known as Mutual Exclusion.

Early Attempts at Software Locks

Programmers tried building locks using shared variables, but these attempts often had flaws.

Attempt 1: Strict Alternation (One Shared Variable)

Using a single turn variable to dictate which thread can run.

// Thread 1
while (turn != 1) { /* Busy wait */ }
// Enter critical section
turn = 2; // Pass turn to Thread 2

Problem: Starvation. If Thread 1 finishes its turn, it cannot re-enter the critical section until Thread 2 takes a turn, even if Thread 2 doesn't need to enter the section. Thread 1 is starved.

Attempt 2: Checking Intent (Two Shared Variables)

Using flags to indicate a thread wants to enter.

// Thread 1
request_1 = true;
while (request_2) { /* Busy wait */ }
// Enter critical section
request_1 = false;

Problem: Deadlock. If both threads set their request flags to true simultaneously, they will both get stuck in their while loops waiting for the other to finish. Neither can proceed.

Peterson's Algorithm

Peterson's algorithm is a classic software solution that successfully combines the ideas of intent and turns to guarantee mutual exclusion for two threads without starvation or deadlock.

// Thread 1
request_1 = true; // Indicate intent
turn = 2;         // Be polite, offer turn to the other thread

// Wait only if the other thread wants in AND it's their turn
while (request_2 && turn == 2) {
    // "Busy" wait
}

// --- Enter critical section ---

// --- Leave critical section ---
request_1 = false; // I'm done

While Peterson's algorithm works, generalizing it for more than two processes is complex (e.g., Lamport's Bakery Algorithm). Furthermore, software solutions rely on "busy waiting" (spinning in a loop), which wastes CPU cycles.

Dijkstra's Semaphores

To provide a robust, low-level mechanism for synchronization, Edsger W. Dijkstra introduced Semaphores. A semaphore is an integer variable accessed only through two special, guaranteed atomic operations. These operations are often implemented with hardware support (like a "test-and-set" instruction).

The Two Atomic Operations

A semaphore S supports:

1. P(S) (Wait/Acquire): From Dutch passeren (to pass). Used to request access.
   if (S > 0) { decrement S; } else { block thread and wait for S to become positive; }
2. V(S) (Signal/Release): From Dutch vrygeven (to release). Used to release access.
   if (threads are waiting) { wake one of them up; } else { increment S; }

Mutual Exclusion using Semaphores

To protect a critical section, you initialize a semaphore to 1 (often called a Mutex - Mutual Exclusion object).

Semaphores are powerful because they guarantee mutual exclusion, freedom from starvation, and freedom from deadlock when used correctly.

Problems with Semaphores

While effective, semaphores are considered low-level and prone to programming errors:

• There is no explicit connection in the code between the semaphore variable and the specific data or critical section it protects.
• It relies entirely on developer discipline. A developer might write a P(S) but forget the matching V(S), causing the system to halt permanently.
• A developer might accidentally execute V(S) without having done P(S), corrupting the synchronization state.

Monitors: High-Level Synchronization

Because semaphores are error-prone, higher-level abstractions were developed. A Monitor (introduced by Per Brinch Hansen and C.A.R. Hoare) is a language-level construct that attaches synchronization control directly to the data being protected.

The Concept of a Monitor

You can think of a monitor as an object-oriented class that enforces mutual exclusion implicitly.

• It contains private data definition (the shared resources).
• It contains a collection of functions operating on that data.
• The Guarantee: Only one thread can be active inside any of the monitor's functions at a time. The mutual exclusion is handled automatically by the programming language runtime, not by manual lock management.

Pseudocode Example of a Monitor

If we applied the monitor concept to our banking problem, we wouldn't need to write P() and V() operations around the transfer code. By simply declaring it inside a monitor, the environment ensures thread safety.

monitor bank_account {
    double accounts[100]; // Protected data

    // These methods are implicitly mutually exclusive.
    // If Thread A is in transfer(), Thread B must wait to enter transfer() or audit().
    
    boolean transfer(double amount, int source, int target) {
        if (accounts[source] < amount) { return false; }
        accounts[source] -= amount;
        accounts[target] += amount;
        return true;
    }

    double audit() {
        double balance = 0.00;
        for (int i = 0; i < 100; i++) {
            balance += accounts[i];
        }
        return balance;
    }
}

Note: The monitor keyword shown above is pseudocode to illustrate the concept. In actual Java, this high-level synchronization is implemented using the synchronized keyword applied to methods or code blocks within a class.