[병렬프로그래밍] Mutual Exclusion

Mutual Exclusion - algorithm for critical section
공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘

Concurrent Programming 이 어려운 이유 : unpredictable 예측할 수 없다

#include <iostream>
#include <thread>
 
int a;
 
void foo()
{
    for (int i = 0; i < 100000; i++) {
    	a++;
    }
}
 
int main()
{
    a = 0;
    std::thread thread1(foo);
    std::thread thread2(foo);
    thread1.join();
    thread2.join();
    std::cout << a << '\n';
    // a is predictable??
    return 0;
}

Time : 시간의 흐름
Event : 즉시 실행됨, 하나의 쓰레드에서 동시에 실행되지 않음.
Thread : Thread Events들의 순차적 모음

Threads = State Machine
Events = transitions
Thread A, B 는 Interleaving하게 실행
 ㄴ Interleaving - 여러 프로세스들이 번갈아 가며 실행

Interval : A의 이벤트 사이의 시간 An = (an, an+1)
A0 -> B0 : A0가 B0의 시작지점보다 먼저 끝남 (happens before)

Lock (mutual exclusion)
Precedence order 가 필요한 구간에서 Lock을 사용

 ㄴ Precedence order - 순서를 정할 수 있어야함 (겹치지 않음)

Deadlock-Free
하나의 쓰레드가 lock을 잡고 있지 못한다면, 다른 쓰레드가 lock을 잡고있다가 unlock을 할 것이다
some processes will make progresses, but others might be stuck(starving)

Starvation-Free
접근하는 모든 쓰레드가 lock을 잡는다.
every process trying to get into critical section, will eventually do so

Peterson's Algorithm - flag, victim
Filter Algorithm - using level
Bakery - using label