Study Notes on Concurrency

Chapter: Concurrency

Introduction

  • Instructor: Adil Ibrahim
  • Content Source: "Operating Systems: Three Easy Pieces"
  • Characteristics of the Chapter:
      - Programming-heavy chapter
      - No homework assigned
      - Three labs planned
      - Challenge: Writing a correct concurrent program is complex

Importance of Concurrent Programming

  • Moore’s Law:
      - States that the number of transistors in a dense integrated circuit doubles approximately every two years.
        - Historically, prior to 2005, more transistors resulted in faster CPUs.
        - Nowadays, more transistors are used to create more CPUs rather than increase speed.
      - Implication: To utilize multiple CPUs effectively, programs need to be parallelized rather than relying solely on faster individual CPUs.

Limitations of Parallelism

Amdahl’s Law
  • Amdahl’s Law: Speedup from adding more CPUs is constrained by the sequential part of the program.
  • Example of bottleneck:
      - If 90% of a program is parallelized, the remaining 10% acts as a bottleneck, limiting speedup.
      - E.g., if file reading is sequential, using 100 CPUs does not aid performance on that part.
I/O and Memory Bottlenecks
  • Adding more CPUs does not enhance the speed of hard drives or RAM.
  • When a program relies on disk access or memory bandwidth, CPUs may remain idle waiting for data.
  • Example: Loading large files into memory is bottlenecked by disk read speeds, regardless of CPU speed.
Insufficient Work to Distribute
  • Some tasks are too trivial for multiple CPUs to manage efficiently.
  • Example: Simple operations (e.g., x=a+bx = a + b) do not necessitate parallel execution.

Threads: A New Abstraction

  • Traditional assumption: Sequential execution in a process.
      - Programs begin at main, execute function calls, and end at main again.
  • Introduction of Multi-threaded programming:
      - Programs can execute multiple code segments (threads) concurrently.
      - Threads share the same address space, differing from multi-processing where processes have separate memories.

OS Support for Multi-threading

  • Similar to multi-processing support:
      - Each thread has its own program counter (PC).
      - Context switching occurs between threads.
      - Thread Control Blocks (TCBs) manage thread information.
  • Key distinction:
      - Threads utilize a shared address space, avoiding the need for page table switching during context changes.

Understanding Shared Address Space

  • Programmers’ Perspective on Shared Memory:
      - Global variables exist in the static data section.
      - Local variables are stored in threads' stacks.
      - malloc-allocated objects reside in the heap.
      - Each process has shared global variables and heap objects, allowing thread visibility of any modifications.
      - A unique local stack per thread prevents data interference during function calls.

Advantages of Multi-threading/Multi-processing

  • Reason 1: Parallelism
      - Today's machines often possess multiple processors/cores.
      - To optimize resource use, tasks should be executed in parallel.
  • Reason 2: Balancing I/O and CPU Operations
      - Programs that engage in I/O should switch tasks while waiting to avoid CPU idle time.
      - This method is effective even on single-core machines.

Comparing Multi-threading to Multi-processing

  • Multi-threading has no functionality that multi-processing cannot achieve.
  • Fundamental Difference:
      - Threads can share memory address space; processes cannot.
  • Trade-offs:
      - Inter-process communication is more complex and less efficient (e.g., sockets, pipes).
      - Processes enhance protection: a faulty process doesn’t affect others, while a thread fault can compromise the whole process.
      - Multi-processing is preferable for distributing programs across multiple machines (distributed systems).

Creating Threads in Programming

Header File Inclusion
  • When compiling code, include the necessary threading libraries and use the -lpthread flag for gcc/Makefile.
General Workflow for Thread Creation
  1. Function Definition: Specify the function to be executed by the thread.
       - Prototype: void *fun_name(void *args)
       - args holds the required arguments for execution.
  2. Thread Creation:
       - Use int pthread_create(pthread_t *pid, const pthread_attr_t *attr, void *(*routine)(void *), void *args);
         - Return Value: indicates success or failure.
         - Parameters:
           - pid: thread identifier for control
           - attr: thread attributes (NULL is acceptable for basic usage)
           - routine: the function assigned to the thread
           - args: the arguments for routine
  3. Multiple Arguments:
       - If multiple arguments are needed, encapsulate them within a struct.
  4. Thread Management: Control threads through various mechanisms:
       - int pthread_join(pthread_t pid, void **value_ptr): Waits for a thread’s completion.
         - Return Value: success or failure
         - pid: from pthread_create
         - value_ptr: can usually assume NULL for simplicity.
Points of Consideration
  • pthread_create initiates a thread without guaranteeing immediate execution—returns quickly.
  • Threads execute in any order; earlier-created threads may delay in starting.
  • No clean termination function for threads—this differs from processes.
  • Design thread functions to handle specific signals for termination.

Practical Example: Creating Multiple Threads

  • Task: Create 10 threads that output unique IDs (0-9).
  • Sample Code:
    ```c

define THREAD_NO 10

void *mythread(void *arg) {
 int *id = (int *)arg;
 printf("my id is %d\n", *id);
}
int main() {
 pthread_t p[THREAD_NO];
 int i = 0;
 for(i = 0; i < THREAD_NO; i++) {
   pthread_create(&p[i], NULL, mythread, &i);
 }
 for(i = 0; i < THREAD_NO; i++) {
   pthread_join(p[i], NULL);
 }
 return 0;
}
```

  • Issue: The parameter passing results in incorrect thread ID output due to shared use of i. If threads run at different times, they may exhibit race conditions.

Resolving the ID Output Issue

  • Solution 1:
      - Allocate an array of 10 integers to pass to each thread.
      - Local arrays require careful management to avoid deallocation issues.
      - A global array avoids local deallocation but is generally poor practice.
  • Solution 2:
      - Each ID could be allocated dynamically using malloc, remembering to free memory after use.

Challenges of Multi-threaded Programming

Complexity in Reasoning
  • In single-threaded programming, function call returns guarantee next statement execution follows.
  • In multi-thread programs, threads may not execute immediately after being invoked, complicating flow tracking.
Testing Difficulties
  • Bugs are often non-deterministic, necessitating multiple executions for testing.
  • Further complexity arises when integrating memory allocation with threading.

Sharing Problems in Multi-threaded Contexts

Race Conditions Example
  • Global variable example:
      - Two threads incrementing a variable num could lead to unexpected results.
      - Expected outcome after two increments: 2. Actual outcome may differ due to race conditions.
Explanation of Race Conditions
  • The operation num = num + 1 is not atomic—comprised of several instructions.
  • In single-thread execution, no complications arise.
      - In multi-thread execution, context switching can lead to unexpected outcomes.
Illustration of Context Switching Issues
  • Normal Execution:
      - Thread 1 and Thread 2 increment without conflict.
  • Problematic Execution:
      - Thread 1 reads 0, increments to 1 while Thread 2 reads 0 simultaneously, leading both to result as 1.

Atomicity and Synchronization

  • Aim: Ensure sections of code execute as if they are atomic operations (uninterruptible).
  • Need for synchronization mechanisms to ensure atomicity.
  • Lack of synchronization in shared data access leads to data races, which should be avoided.

Synchronization Needs

  • Multi-threading inherently raises the question of synchronization necessity.
      - The answer is frequently YES.
      - Exceptions: Threads do not share data or when shared data is read-only.
  • Even simple operations (e.g., a=1) may not be atomic.
      - Avoid assumptions about atomicity; rely on proper synchronization techniques.

Additional Considerations

  • Situations where one thread must wait for another’s completion:
      - This situation ties to but is distinct from synchronization needs.
  • Tools: Semaphores and condition variables will be introduced to manage such inter-thread dependencies.