Back to Notes

Concurrency

Process

  • Process registers
  • Program counters
  • Stack pointers
  • Memory pages

Each process has its own memory address space.

  1. Heap : It is dynamic allocated memory
  2. Stack:
  3. Registers:

Threads

  • Thread is a unit of execution in a process. A process has atleast one thread called as main thread.
  • Thread within a process share same memory address space.

Life cycle:

Blocked

New -> Running -> Terminated

Blocked vs Running

Blocked and Waiting

Blocked:

  • Waiting for the shared resources Waiting:
  • Waiting on another operation to be completed.

Concurrency vs Parallel

  • Concurrency: All tasks are look like running at once.
    • It is about managing multiple instruction sequences at the same time.
    • This is achievable on a single CPU with frequent switching between taks.

Race Condition

  • Two to more threads access a shared resource and at-least one of the thread modifies the shared resource.
  • It leads to indeterminism
  • Solution: Use concurrency and synchronization primitives to eliminate race conditions Critical sections - IMP Spinlocks - IMP Mutex Semaphore Condition variable Monitors Barriers

Critical Section

  • Single Processor systems
    • Begin critical section
    • Disable OS interrupts
    • avoid system calls to context switch
    • access the shared resource
    • Restore OS interrupts
    • End Critical section
  • This prevents any other thread from being scheduled on the CPU by the OS. Pros:
  • Simple and efficient Con:
  • Not portable to multiprocessor systems
  • Very low granularity
    • Single global lock for entire program
  • There are better alternatives

Mutex

  • When a thread tries to acquire a mutex that is already help by another thread, it is put to sleep until the mutex becomes available.

Spin Locks:

  • When a thread tries to acquire a spin lock that is already held, it enters a busy wait loop checking repeatedly if lock is available, instead of being put to sleep.

Deadlocks

  • Each thread waiting for the resource to get free
  • In a single thread also deadlock can happen if we try to acquire a locked instance without releasing previous lock it in the same thread

Reentrancy

  • A reentrant lock can be acquired again, even if it's already locked
  • Can only be acquired again by the thread that already holds the lock
  • Other threads that try to acquire it will block
  • Must be released the same number of times it was acquired

Producer Consumer Queue

Producer: Generates data and insert into shared data structure Consumers: Consumes data from the data structure Decouples production and consumption process

  • Separation of concerns
  • Producers and consumers can operate at different rate without affecting each other Example:

Problems:

  1. Shared Resource - Buffer
  2. Indefinite loop
  3. Inefficient instruction order in case of multiple threads of producer/consumer Solution:

Rate Limiter