Introduction to Concurrency

In the early days of computing, CPUs executed instructions one after the other in a strict linear sequence. However, as hardware limits halted raw clock speed increases, chip makers pivoted to multi-core architectures. Today, writing high-performance software requires Concurrency—the art of structuring programs to handle multiple tasks overlapping in time.

1. Learning Objectives

• Differentiate between synchronous (blocking) and asynchronous (non-blocking) execution structures.
• Explain how operating system schedulers use time-slicing and context switching to simulate concurrency on single CPU cores.
• Analyze the difference between CPU-bound and I/O-bound workloads and identify when concurrency adds value.
• Map high-level application threads down to native operating system kernel threads.
• Explain the memory layout of multi-threaded programs (shared heap vs. private thread stacks).

2. Problem & Naive Solution

Imagine you are building a custom Log Processing Engine. The engine needs to fetch logs from three remote HTTP endpoints, parse their JSON entries, and write the consolidated output to a local disk database.

The Naive Solution (Sequential Execution)

A beginner developer would write a sequential program that processes each server's logs step-by-step:

3. Issues with the Naive Approach

• Wasted Hardware Resources: Network calls are I/O-bound. While the application is waiting for a response from server1.com, the CPU sits completely idle, doing no work for 2 seconds.
• Synchronous Blocking Bottlenecks: The total execution time is cumulative ($2 + 2 + 2 = 6$ seconds). If you scale this to 100 servers, the process will block for over 3 minutes, which is unacceptable for real-time systems.
• Frozen User Interfaces: In desktop or mobile systems, running I/O operations sequentially on the main thread locks the event loop, rendering the UI completely unresponsive to user inputs.

4. Real-world Analogy

5. Theory: Core Concurrency Concepts

To understand how concurrency functions, we must explore how the operating system interacts with execution threads:

A. Concurrency vs. Parallelism

• Concurrency is about structure. It is the composition of independently executing processes or threads. A program is concurrent if it is designed to manage multiple tasks overlapping in time.
• Parallelism is about execution. It is the simultaneous execution of multiple tasks at the exact same physical instant on multi-core hardware.

B. Time-Slicing and Context Switching

On a single CPU core, physical parallelism is impossible. The operating system kernel achieves the illusion of multitasking using time-slicing. The OS scheduler allocates a tiny slice of CPU execution time (typically 10-100 milliseconds) to a thread. When the time slice expires, the OS performs a context switch:

1. It pauses the active thread and saves its current CPU state (registers, program counter) to its Thread Control Block (TCB).
2. It selects another thread from the ready queue.
3. It loads the saved register values of the new thread into the physical CPU cores.
4. Execution resumes from the new thread's last recorded program counter position.

C. Workload Types

• I/O-Bound Workloads: Spend most of their time waiting for external systems (network downloads, database query results, disk reads). Concurrency is highly beneficial here because the CPU can perform context switches to other threads while waiting.
• CPU-Bound Workloads: Spend all their time performing heavy math or logical operations (video encoding, cryptography, machine learning). Concurrency on a single core actually *slows down* CPU-bound tasks due to context switching overhead. They only benefit from true physical parallelism on multi-core CPUs.

6. Thread Timeline

Below is a timeline diagram illustrating how a single CPU core interleaves execution between two concurrent threads, simulating simultaneous progress.

7. Synchronization, Race Conditions & Deadlocks

Spawning threads introduces coordination complexity:

• Race Conditions: Occur when multiple threads attempt to read and write to the same shared memory location concurrently without synchronization. The final value depends on the exact, unpredictable interleaving of execution steps.
• Synchronization: The mechanism of using locks, mutexes, or semaphores to coordinate access to shared state, ensuring only one thread can modify critical data sections at any time.
• Deadlocks: Happen when Thread A holds Lock 1 and waits for Lock 2, while Thread B holds Lock 2 and waits for Lock 1. Both threads stall permanently, freezing the application.

8. Syntax Explanation

To run a task concurrently, we instruct the language runtimes to allocate a new thread execution path:

• Java: Uses Thread classes or Runnable interfaces. You instantiate a thread with a task and call .start() (not .run()) to register the thread with the OS scheduler.
• Python: Uses the threading library. Tasks are passed as targets to the threading.Thread constructor. Note: Python's Global Interpreter Lock (GIL) limits pure Python threads to single-core execution, making them ideal for I/O-bound tasks but ineffective for parallel CPU tasks.
• C++: Uses standard library templates. Instantiating a std::thread immediately launches the thread, requiring you to call .join() before the main execution context exits to prevent runtime aborts.

9. Step-by-Step Implementation

1. Define the Worker Task: Create the logic that needs to run concurrently (e.g., download a file, parse log chunks). This task should contain isolated, non-shared state variables to avoid race conditions.
2. Instantiate Execution Threads: Wrap the task in the language's thread container.
3. Trigger Execution: Call the start command to fork the parent thread and create a child thread.
4. Synchronize Lifecycle (Join): Instruct the main thread to wait for worker thread completion, ensuring all concurrent operations finish before printing results.

10. Complete Code (Concurrent Downloader Simulator)

This project simulates downloading files from multiple servers concurrently. Observe how the print statements interleave at runtime, indicating asynchronous execution.

11. Code Walkthrough

Let's trace how the program executes:

• Asynchronous Forking: Calling .start() on the Thread objects instructs the operating system to spin up three independent threads. The execution flow forks—the main thread continues executing the next statements, while the child threads run their respective tasks in parallel or interleaved.
• Non-Deterministic Output: If you execute this program multiple times, the start order of download tasks can vary. This happens because the OS scheduler determines thread slice allocation dynamically based on system load, making execution non-deterministic.
• Join Operations: The .join() method is a block command. The calling thread (in this case, the main thread) halts its own execution until the target threads have completely finished running, ensuring consistent timing output.

12. Execution Flow

1. Main Execution Initiates: JVM main thread starts and allocates heap space for the thread metadata structures.
2. Thread Lifecycle Forking: Three threads transition from the NEW state to RUNNABLE when t1.start(), t2.start(), and t3.start() are called.
3. Interleaved Execution: * Downloader-1 runs, prints start statement, and calls Thread.sleep(). This changes its state to TIMED_WAITING, yielding the CPU. * Downloader-2 runs, prints start statement, and calls Thread.sleep(). * Downloader-3 runs, prints start statement, and calls Thread.sleep().
4. Main Thread Blocking: The main thread reaches t1.join(), transitioning to WAITING status.
5. Wake-up Triggers: * After 1.5 seconds, Downloader-2 wakes up, prints completion statement, and terminates. * After 2.0 seconds, Downloader-1 wakes up, prints completion, and terminates. * The main thread wakes up because t1 is complete, and moves to t2.join(). Since t2 is already done, it immediately checks t3.join(). * After 3.0 seconds, Downloader-3 terminates.
6. Termination: The main thread prints final time metrics and terminates.

13. Internal Working (JVM & OS Kernel Threads)

Let's explore the internal memory and thread architecture:

• 1:1 Thread Mapping: Modern JVM configurations utilize a 1:1 mapping model. Spawning a java.lang.Thread creates a native OS kernel thread (e.g., pthread on Linux/macOS). The OS scheduler is fully responsible for assigning these threads to CPU cores.
• Memory Division: * Shared Heap: All threads share access to the same heap storage. Objects instantiated in the main thread (like our log strings) can be read and modified by worker threads, requiring synchronization. * Thread Private Stack: Every thread receives its own call stack (typically 1MB of off-heap memory). The stack stores local primitive variables, method arguments, and reference addresses. It is completely isolated from other threads.
• CPU Register State Save: During context switches, the CPU stores the program counter (holding the address of the next instruction to execute) and register states in the Thread Control Block (TCB) in memory, ensuring exact state recovery when the thread is rescheduled.

14. Complexity Analysis

• Time Complexity: Running $N$ independent tasks concurrently with maximum delays of $T_{max}$ results in a runtime of $O(T_{max})$, down from $O(\sum_{i=1}^N T_i)$ in sequential execution.
• Memory Complexity: Spawning $N$ threads consumes $O(N \times 1\text{MB})$ of system RAM due to native stack allocation limits.
• Context Switching Overhead: A context switch takes 1-10 microseconds of CPU time. Spawning thousands of threads causes "thrashing"—where the CPU spends more time switching context than executing task instructions.

15. Best Practices & Production Considerations

• Always Use Thread Pools: Spawning raw threads manually in production is an anti-pattern. Use ExecutorService in Java to reuse a fixed number of threads, preventing resource exhaustion.
• Enforce Thread Naming: Always supply custom, descriptive names when creating threads (e.g., LogProcessor-Thread-1). This simplifies debugging stack traces during production outages.
• Graceful Thread Interruption: Always catch InterruptedException and restore the interrupt flag status using Thread.currentThread().interrupt() so calling scopes are aware of shutdown triggers.
• Design for Immutability: The easiest way to avoid multi-threaded race conditions is to make your data structures completely immutable. If threads cannot modify data, you do not need locks.

16. Common Mistakes

• Calling run() instead of start(): Calling run() executes the task synchronously on the caller's main thread instead of registering a new thread with the OS scheduler.
• Hardcoding Thread.sleep() for Coordination: Putting worker threads to sleep to wait for other tasks to complete. Use synchronization primitives (like CountDownLatch or CompletableFuture) instead.
• Ignoring Thread Exceptions: Unhandled exceptions inside background threads terminate the thread silently, leaving tasks unfinished without notifying the main application.

17. Interview Discussion

18. Practice Exercises

• Easy: Write a program that spawns 5 threads. Each thread prints numbers from 1 to 10 along with its thread name. Verify how the output numbers interleave.
• Medium: Create a multi-threaded web scraper simulator. It should take a list of 10 URLs, download pages concurrently (simulating delay), and return the total download size.
• Hard: Design an image thumbnail generator. The program takes a directory of image files, spawns worker threads, parses the image metadata in parallel, and saves thumbnails.

19. Challenge Problem

Design a custom Thread Throttle Manager. The manager receives a queue of 100 tasks (objects implementing Runnable or callbacks). It must execute these tasks concurrently, but ensure that no more than 4 tasks run at any given instant, without using built-in thread pool constructs (like ExecutorService). You can use raw threads, basic locks, or flags to implement this concurrency throttle.

20. Summary & Cheat Sheet

21. Quiz

22. Next Lesson Preview

In the next lesson, we will compare Concurrency vs. Parallelism in detail. We will explore how hardware design influences execution performance, study multi-core memory caches (like L1, L2, L3 caches), and learn how cache coherency protocols impact parallel software speedups!