[Concurrency] Basic Concepts

Posted on | In , |

Video Introduction:

  1. https://www.youtube.com/watch?v=prFEyaUEAMM&t=1
  2. https://www.youtube.com/watch?v=x1xNUZ4OysA&t=4s
  3. https://www.youtube.com/watch?v=zvswM5pY-mk&list=PLzUGFf4GhXBLEQsoOfLzhH6JKybt8I5Ec

Concepts

Threads

  • Smallest sequence of programmed instructions that can be managed independently by a scheduler
  • Has its own registers. eg Program Counter, Stack Pointer.
  • Can be suspended

Process

  • Instance of a computer program that’s being executed
  • A process can have one or more threads
  • Most programs are single threaded

Parallel Computing

  • Run programs currently on one or more CPUs
  • Multi-threading (shared-memory)
  • Multi-processing (independent-memory): Like paralell universe: a complete fork of the original process.

Multi-threading

Critical Section When multiple threads are accessing a shared resource. Solution: using a lock to make sure the second thread runs only after the first thread is finished.

Communications

Multi-threading 

- Shared variables (efficient)
- Semaphore
- Mutex
- Lock

Multi-processing: Larger cost

- Shared Memory (efficient)
- Pipe `cat a.txt | grep hello`
- Socket 
- RPC (Remote Process Call) (example: HTTP request)
    - RMI
    - HTTP / Rest

Why Multi-threading

  • More Responsive
    • UI
    • Web Servers

  • Speeding Up (Multi-core CPUs)

    • Multithreaded Algorithms
    • Paralleling Computing

  • Responsiveness

    • Avoid blocking the main thread
    • Run “heavy” job in the background
      • CPU bound
      • I/O bound

Example

  • Compute number of primes less than 1000
    • One processor, test all numbers from 1 to 1000
    • Two processors:
      • CPU 1: test 1 - 500
      • CPU 2: test 501 - 1000
      • Combine the result
    • P processors:
      • CPU 1: test 1 - 1000 / P
      • …
    • Divide and Conquer -> Map Reduce
    • Speed up: ~P