multi-threading (not done)

Concurrency 是语义，并发
parallel 是concurrency 的一种实现方法,  并行

Process  VS   Thread:
1.  Process can have multiple threads.
2.  Process has their own memory. but threads share memory space in the same process. shared heap, static/global variable, don't share call stack/register state/program counter
3.  Process must communicate with each other using interprocess communication, threads can communicate with each other directly because threads can see each others' memory spaces.
4. threads are easy to create but process required duplicates of its parent process.

Concurrency:
multi threads and multi processes running at the same time, utilizing CPU efficiently, especially in multi core environment.

Synchronization:
two or more conflict operations in different threads try to operate the share data,  race condition should not appear.

Race Condition:
race condition appears when two or more threads try to access the share data at the same time, the result of the share data depending on the thread scheduling algorithm.
The reason why the race condition happens is that the one statement you make in the code, is transferred into several instructions, it's not the smallest unbreakable unit the CPU can execute. which  is not atomic.

Critical Section:
a piece of code that access and modified the shared state.

Mutual Exclusive (lock):
at any time, only one thread can access and modify the shared state of the critical section.

semaphore:
when the number of resource the lock try to protect is more than one, we need a semaphore to coordinate the operation.

Atomic action:
is one that effectively happens all at once. An atomic action cannot stop in the middle: it either happens completely, or it doesn't happen at all. No side effects of an atomic action are visible until the action is complete.

DeadLock:  two or more threads waiting each other to releasing lock, but no one does.
eg: thread1: lock1(), lock2(), do something.... unlock2(), unlock1();
      thread2: lock2(), lock1(), do something.... unlock1(), unlock2();
why?
thread1 get lock1(), thread2 get lock2(), then thread1 tries to get lock2(), but lock2 is hold by thread2,        thread1 needs to wait for thread2 to unlock2(), but thread2 has to get lock1 first, thus, these two threads are waiting each other to release locks but no one does, this is called deadlock.

conditions:
1. concurrency condition
2. circular waiting
3. hold and wait
4. no preemption

how to solve deadlock:
set the preemption of locks.

thread 和 process 怎么用stack 和 heap实现的？

CPU switch/Content Switch:

when one thread has to give up its quota, the CPU will switch to other thread, this is called content switch.

multiprocess: 不直接通信
multithread: share memory space, thread can see the content of other thread, 直接通信

multithread 需要考虑 concurrency,

1.  一些thread的基本概念
2.   在算法上的改进，要有并行改进程序，怎么从算法上化分程序，
怎么分任务？？？？

eg: DFS:  M*N  怎么并行化？


每一个task 是一个thread， thread也是有资源限制的，
相互独立，相互没有影响的task，划分的粗粒度和细粒度:  ad & disavd
怎么去判断独立任务： task parallelism && data parallelism (eg: 根据任务划分，每个人坐不一样的事，各自做各自的事情；根据数据划分： 每个人做一样的事情但是针对不同的数据)，

data race ?
1. more than one thread access the same memory //heap
2. at least one write operation
3. at least two of those operations are concurrent

mutual exclusion, critical section, and locks