Session 2.4: Concurrency and Threading
Understanding concurrency concepts, interacting processes, and multithreading models
Learning Objectives
By the end of this session, you will be able to:
- Understand concurrency concepts and terminology
- Explain interacting processes and their challenges
- Describe multithreading and its advantages
- Compare different multithreading models
- Analyze benefits of multithreading
- Distinguish between processes and threads
- Understand synchronization primitives and their applications
Key Concept
Concurrency and multithreading enable multiple tasks to execute simultaneously or appear to execute simultaneously, improving system performance and responsiveness.
Historical Context
The concept of concurrency dates back to the 1960s with the development of time-sharing systems. Threading became prominent in the 1980s with the advent of graphical user interfaces that needed to remain responsive while performing background tasks.
Concurrency Concepts
Definition
Concurrency is the ability to execute multiple tasks or processes simultaneously, or at least appear to execute simultaneously through rapid context switching.
Theoretical Foundation
Concurrency is rooted in the concept of non-determinism in computer science, where the order of execution isn't predetermined. This was formally studied through models like Petri nets (1962) and process calculi (1980s) which provided mathematical frameworks for reasoning about concurrent systems.
The actor model (1973) proposed by Carl Hewitt introduced another approach where concurrent entities ("actors") communicate through message passing rather than shared memory.
Types of Concurrency:
- True Parallelism: Multiple CPUs/cores executing simultaneously
- Pseudo-parallelism: Single CPU rapidly switching between tasks
- Distributed Concurrency: Tasks running on different machines
Concurrency Challenges:
- Race Conditions: Outcome depends on timing
- Deadlocks: Processes waiting for each other
- Starvation: Process never gets resources
- Synchronization: Coordinating access to shared resources
Why Concurrency?
- Performance: Better CPU utilization
- Responsiveness: User interface remains active
- Resource Sharing: Multiple users access same data
- Modularity: Separate concerns into different processes
- Scalability: Take advantage of multiple processors
Sequential vs Concurrent Execution:
Sequential: Task A: |████████████| Task B: |████████████| Task C: |████████████| Time: 0 4 8 12 Concurrent: Task A: |████| |████| |████| Task B: |████| |████| |████| Task C: |████| |████| |████| Time: 0 1 2 3 4 5 6 7 8
Concurrency vs Parallelism
While often used interchangeably, these terms have distinct meanings:
- Concurrency is about dealing with multiple tasks at once, regardless of whether they're executing simultaneously.
- Parallelism is about executing multiple tasks simultaneously, typically on multiple processors/cores.
All parallel systems are concurrent, but not all concurrent systems are parallel. Concurrency is a programming model, while parallelism is a runtime execution concept.
Interacting Processes
Process Communication Mechanisms
Cooperating processes require mechanisms to communicate and synchronize their actions. The two primary approaches are:
- Shared Memory: Processes read and write to a shared memory region. Faster but requires synchronization.
- Message Passing: Processes exchange messages through communication channels. Slower but provides better isolation.
These mechanisms form the basis of Inter-Process Communication (IPC) which is fundamental to modern operating systems.
Independent Processes:
- Cannot affect or be affected by other processes
- Do not share data with other processes
- Deterministic execution
- Easier to debug and test
Advantages
- No synchronization needed
- Predictable behavior
- Fault isolation
- Simple debugging
Cooperating Processes:
- Can affect or be affected by other processes
- Share data or resources
- Non-deterministic execution
- Require synchronization mechanisms
Challenges
- Race conditions
- Synchronization overhead
- Complex debugging
- Potential deadlocks
Reasons for Process Cooperation
- Information Sharing: Multiple processes need access to same data
- Computation Speedup: Break task into parallel subtasks
- Modularity: Divide system functionality into separate processes
- Convenience: User can perform multiple tasks simultaneously
Producer-Consumer Problem
Classic example of cooperating processes:
- Producer: Generates data and puts it in a buffer
- Consumer: Removes data from the buffer
- Challenge: Synchronize access to shared buffer
- Solutions: Semaphores, monitors, message passing
Historical Perspective: Dijkstra's Contributions
Edsger W. Dijkstra made fundamental contributions to concurrent programming in the 1960s:
- Introduced the concept of semaphores (1965) as a synchronization primitive
- Formalized the dining philosophers problem (1965) to illustrate synchronization issues
- Coined the term "structured programming" which influenced concurrent programming methodologies
These contributions laid the groundwork for modern approaches to process synchronization.
Multithreading
What is a Thread?
A thread is a lightweight process - the smallest unit of processing that can be scheduled by an operating system. Multiple threads can exist within a single process and share the process's resources.
Theoretical Background
The concept of threading evolved from the need for more efficient concurrency within a single process. Threads are sometimes called "lightweight processes" because they:
- Share the same address space
- Have lower creation and context-switching overhead
- Allow more efficient communication through shared memory
Threads implement what is known as intra-process concurrency, allowing parallel execution paths within the same program.
Traditional Process
- Single thread of execution
- One program counter
- Sequential execution
- Heavy context switching
- Separate memory space
Multithreaded Process
- Multiple threads of execution
- Multiple program counters
- Concurrent/parallel execution
- Lightweight context switching
- Shared memory space
Single-threaded vs Multithreaded Process:
Single-threaded Process: ┌─────────────────────────┐ │ Process │ │ ┌─────────────────┐ │ │ │ Thread │ │ │ │ - Program Counter │ │ │ │ - Registers │ │ │ │ - Stack │ │ │ └─────────────────┘ │ │ Code | Data | Files │ └─────────────────────────┘ Multithreaded Process: ┌─────────────────────────┐ │ Process │ │ ┌─────┐ ┌─────┐ ┌─────┐│ │ │Thread│ │Thread│ │Thread││ │ │ 1 │ │ 2 │ │ 3 ││ │ └─────┘ └─────┘ └─────┘│ │ Code | Data | Files │ │ (Shared by all threads)│ └─────────────────────────┘
Thread Components:
- Thread ID: Unique identifier
- Program Counter: Current instruction
- Register Set: CPU register values
- Stack: Local variables and function calls
Shared Resources:
- Code Section: Program instructions
- Data Section: Global variables
- Heap: Dynamic memory
- OS Resources: Open files, signals
Thread Control Block (TCB)
Each thread is represented in the OS by a Thread Control Block, which contains:
- Thread state (running, ready, blocked)
- Thread ID
- Program counter value
- CPU register values
- Pointer to the Process Control Block
- Stack pointer
- Scheduling information
The TCB is much smaller than a Process Control Block (PCB), making thread management more efficient.
Multithreading Models
Thread Types
User Threads: Managed by user-level thread library
Kernel Threads: Managed by operating system kernel
Relationship between user and kernel threads determines the multithreading model
Evolution of Threading Models
Threading models have evolved alongside operating system design:
- Early systems (1980s) typically used many-to-one model due to kernel limitations
- Unix systems initially didn't support threads, leading to the development of user-level threading libraries
- Modern operating systems (Windows NT, Linux, macOS) typically use one-to-one or many-to-many models
The choice of threading model significantly impacts application performance, scalability, and programming complexity.
Three Main Multithreading Models:
Many-to-One Model
User Threads Kernel Thread
T1 ────┐
T2 ────┤──── KT1
T3 ────┘
T4 ────┘
Advantages:
- Fast thread switching
- No kernel involvement
- Portable
Disadvantages:
- No true parallelism
- Blocking system call blocks all
- No multicore utilization
One-to-One Model
User Threads Kernel Threads
T1 ──────── KT1
T2 ──────── KT2
T3 ──────── KT3
T4 ──────── KT4
Advantages:
- True parallelism
- Multicore utilization
- Non-blocking system calls
Disadvantages:
- Overhead of kernel threads
- Limited number of threads
- Slower thread creation
Many-to-Many Model
User Threads Kernel Threads
T1 ────┐ ┌── KT1
T2 ────┤────┤
T3 ────┤ └── KT2
T4 ────┘ ┌── KT3
T5 ─────────┘
Advantages:
- Best of both models
- True parallelism
- Efficient resource usage
Disadvantages:
- Complex implementation
- Difficult to debug
- Scheduling complexity
Two-Level Model
Variation of Many-to-Many that allows some user threads to be bound to kernel threads. Provides flexibility for applications that need guaranteed kernel thread access.
Benefits of Multithreading
1. Responsiveness
Allows program to continue running even if part of it is blocked. User interface remains responsive while background tasks execute.
2. Resource Sharing
Threads share memory and resources of the process, making communication easier and more efficient than IPC.
3. Economy
Creating and context-switching threads is much cheaper than processes. Less memory and CPU overhead.
4. Scalability
Can take advantage of multiprocessor architectures. Threads can run in parallel on different processors.
Performance Comparison:
| Operation | Process | Thread | Improvement |
|---|---|---|---|
| Creation Time | High | Low | 10-100x faster |
| Context Switch | Expensive | Cheap | 5-10x faster |
| Memory Usage | High | Low | Shared memory space |
| Communication | IPC required | Direct sharing | Much faster |
Real-World Examples
- Web Browser: One thread for UI, others for downloading, rendering
- Word Processor: Separate threads for typing, spell-check, auto-save
- Web Server: Thread per client request for concurrent handling
- Database: Multiple threads for query processing and I/O operations
Process vs Thread Comparison
| Aspect | Process | Thread |
|---|---|---|
| Definition | Independent execution unit with own memory space | Lightweight execution unit within a process |
| Memory | Separate address space | Shared address space |
| Communication | IPC (pipes, sockets, shared memory) | Direct memory sharing |
| Creation Overhead | High (memory allocation, PCB setup) | Low (minimal setup required) |
| Context Switch | Expensive (save/restore full context) | Cheap (minimal context) |
| Fault Tolerance | High (isolated from other processes) | Low (crash affects entire process) |
| Scalability | Limited by system resources | Better scalability |
| Synchronization | Not required (independent) | Required (shared resources) |
When to Use Processes
- Need strong isolation between tasks
- Fault tolerance is critical
- Tasks are largely independent
- Security requirements are high
- Running on distributed systems
When to Use Threads
- Need frequent communication between tasks
- Performance is critical
- Tasks share common data
- Want to utilize multiple CPU cores
- Building responsive user interfaces
Advanced Theory
Synchronization Primitives
To manage concurrent access to shared resources, operating systems provide several synchronization mechanisms:
- Mutex (Mutual Exclusion): A locking mechanism that ensures only one thread can access a resource at a time.
- Semaphore: A signaling mechanism that maintains a counter to control access to a pool of resources.
- Monitor: A high-level synchronization construct that encapsulates shared data and procedures.
- Condition Variables: Allow threads to wait for certain conditions to become true.
- Barriers: Synchronization points where threads must wait until all participating threads reach the barrier.
Thread Safety and Reentrancy
Thread-safe code functions correctly during simultaneous execution by multiple threads. Key approaches to achieve thread safety include:
- Reentrancy: Code that can be interrupted and safely called again ("re-entered") before previous executions complete.
- Immutable objects: Objects whose state cannot be modified after creation.
- Thread-local storage: Data that is unique to each thread.
- Atomic operations: Operations that complete in a single step relative to other threads.
Concurrency Problems
- Race Conditions: When the system's behavior depends on the sequence or timing of uncontrollable events.
- Deadlocks: When two or more operations are waiting for each other to complete.
- Livelocks: Similar to deadlocks but where processes constantly change state without making progress.
- Priority Inversion: When a low-priority task holds a resource needed by a high-priority task.
Solutions to Concurrency Problems
- Locking protocols: To prevent race conditions
- Deadlock prevention: Ensuring at least one necessary condition for deadlock doesn't hold
- Deadlock avoidance: Using algorithms like Banker's algorithm
- Deadlock detection and recovery: Identifying and breaking deadlocks
- Wait-free algorithms: Ensuring progress regardless of other threads' behavior
Memory Models and Consistency
Multithreaded programs must consider memory consistency models that define how memory operations become visible to threads:
- Sequential Consistency: The simplest model where all operations appear to execute in program order.
- Relaxed Consistency: Allows certain reorderings of memory operations for performance.
- Release Consistency: A specific relaxed model that distinguishes between acquire and release operations.
Understanding memory models is crucial for writing correct multithreaded code, especially on architectures with weak memory ordering.
Session Summary
Key Takeaways:
- Concurrency enables multiple tasks to execute simultaneously or appear to do so
- Processes can be independent or cooperating, with cooperating processes requiring synchronization
- Multithreading allows multiple threads of execution within a single process
- Three main threading models: Many-to-One, One-to-One, Many-to-Many
- Multithreading provides benefits in responsiveness, resource sharing, economy, and scalability
- Threads are lighter weight than processes but require careful synchronization
- Concurrency control mechanisms like mutexes and semaphores are essential for thread safety
Important Concepts:
- Concurrency vs Parallelism: Appearing simultaneous vs actually simultaneous
- User vs Kernel Threads: Different levels of thread management
- Thread Components: ID, program counter, registers, stack
- Shared Resources: Code, data, heap, OS resources
- Threading Models: Different mappings between user and kernel threads
- Synchronization Primitives: Mutex, semaphore, monitor, condition variables
Next Module
Module 3: Process Coordination and Deadlock
Process synchronization fundamentals, synchronization solutions, high-level tools, and deadlock concepts
Further Reading
- Dijkstra, E. W. (1965). "Cooperating sequential processes"
- Hoare, C. A. R. (1974). "Monitors: An operating system structuring concept"
- Lamport, L. (1978). "Time, clocks, and the ordering of events in a distributed system"
Study Tips:
- Understand the difference between concurrency and parallelism
- Practice identifying scenarios where multithreading is beneficial
- Compare the three threading models and their trade-offs
- Understand when to use processes vs threads
- Review the benefits of multithreading with real-world examples
- Experiment with synchronization primitives in code examples