Critical Section

정의\
Critical Section은 (임계구역 또는 공유변수 영역) 병렬프로그래밍에서 둘 이상의 스레드 (멀티스레드)가 동시에 접근해서는 안되는 공유 자원(파일, 입출력, 공유 데이터 등) 을 접근하는 명령문 또는 코드의 일부 영역을 말합니다.

Race condition의 정의\
두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.

이런 Race condition은 3가지 문제를 직면한다.
1. Mutual exclusion
2. DeadLock
3. Starvation

Mutual exclusion

정의\
특정 프로세스가 공유 자원을 사용 중일 때 다른 프로세스가 이 자원에 접근하지 못하도록 막는 것을 의미한다. 그러니까, 공유를 하면 안되는 자원(Resource)의 동시 사용을 피하는 방법 중 하나이다.

Dekker Algorithm

while(1) {
    flag[i] = true;     // 프로세스 i가 임계영역 진입을 시도한다.
    while(flag[j]) {    // 프로세스 j가 현재 임계영역에 있는지 확인한다.
        if(turn == j) {     // 프로세스 j가 임계영역을 사용 중이라면
            flag[i] = false;    // 프로세스 i의 진입을 취소하고,  
            while (turn == j);  // turn이 j에서 바뀔 때 까지 기다린다...
            flag[i] = true;     // 임계영역에서 j가 나오면 재진입을 시도한다.
        }
    }
    /* critical section */
    turn = j;           // 임계영역의 사용이 끝나면, turn을 넘긴다
    flag[i] = false;    // 진입 flag값을 false로 바꾸어 임계영역 사용 완료를 알린다.
    ...
}

Flag와 Turn 이라는 변수로 임계영역에 들어갈 프로세스를 결정하는 알고리즘으로 turn을 통해 내 차례 라면 들어 가는 알고리즘이다.

장담점

• 구현이 편하고 기아상태나 교착상태가 없다.
• busy wait은 높은 CPU 사용량을 가질 수 있다.

Peterson Algorithm

while(1){
    flag[i] = true; // 프로세스 i가 임계영역 진입시도
    turn = j; // 다른 프로세스에 진입기회를 양보
    while(flag[j] && turn == j);
    /* critical section */
    ...
    flag[i] = false; //임계영역 사용완료
    ...
}

Dekker와 비슷하지만 먼저 다른 프로세스를 확인 하고 기다린다는 점에서 조금 다르다.

장단점

• 구현하기 편하고 2개의 쓰레드의 시스템에서 사용하기 용이합니다.
• 기아상태에 빠질 수 있습니다.
• busy wait은 높은 CPU 사용량을 가질 수 있다.

Bakery Algorithm

while(1){
    choosing[i] = true;
    number[i] = max(number[0] ... number[n-1]) + 1
    choosing[i] = false;
    for(int j = 0; j <= n-1; j++) {
        while(choosing[j]);
        while(number[j] != 0 &&((number[j],j)<(number[i],[i])));
    }
    /* critical section */
    ... 
    number[i] = 0;
    ...
}

위 두 알고리즘과 다르게 여러개의 프로세스나 쓰레드의 대한 처리가 가능하다.
가장 작은수의 번호표를 가지고 있는 프로세스가 임계영역에 진입한다.

장단점

• 2개이상의 쓰레드에서 사용하기 좋습니다.
• 교착, 기아상태가 없습니다.
• 공유 데이터 구조가 필요하며 이는 메모리 및 성능 측면에서 비용이 많이 들 수 있습니다.

Semaphore

정의\
신호기, 깃발을 의미하며 각 프로세스에 제어 신호를 전달하여 순서대로 작업하도록 하는 기법.\
세마포어의 값에 따라 운영체제는 프로세스가 즉시 자원을 사용할 지, 자원이 다른 프로세스에 의해 사용 중인걸 알게 될 경우엔 일정 시간을 기다려야 한다.

• 공유자원의 상태를 나타낼 수 있는 카운터로 생각할 때,
  • 사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성한다.
  • 운영체제 또는 커널의 한 지정된 저장장치 내의 값
  • 일반적으로 비교적 긴 시간을 확보하는 리소스에 대한 이용
  • 유닉스 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 또는 동기화하는 기술
• 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근할 수 있다.
• 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있다.
• 자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용한다.
• 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기해야 한다.
• 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 대기하도록 해야 한다.
• 마포어는 이진수를 사용하거나 추가적인 값을 가질 수 있다.

...
P(s);
/* critical section */
V(s);
...

P(Semaphores){
    while(S==0);
    s = s - 1;
}

V(Semaphores){
    s = s + 1;
}

명심\
P - Critical section - P : 교착 상태 발생\
V - Critical section - P : mutex exclusion을 보장할 수 없다.

Mutex

mutex는 semaphore와 비슷하다.
여러 쓰레드가 접근하는 것을 막고 오직 하나의 쓰레만 접근하게 하는데, 0 or 1의 값을 가지는 이진 세마포어랑 유사하게 동작한다.

Mutex vs Semaphore

가장 큰 차이점은 동기화 대상의 개수이다.

• 세마포어는 동기화 대상이 여러개 일 때, 뮤텍스는 동기화 대상이 오직 하나 일 때 사용된다.
• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
• 세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 책임을 진다.
• 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 뮤텍스를 해제할 수 있다. 하지만, 세마포어는 소유하지 않고 있는 스레드가 세마포어를 해제할 수 있다.
• 세마포어는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재한다. 하지만 뮤텍스는 프로세스 범위를 가지고 프로그램이 종료될 때 자동으로 지워진다.

Monitor

어떤 공유 데이터에 대해 모니터를 지정해놓으면, 프로세스는 그 데이터에 접근하기 위해 모니터에 들어가야만 한다. 즉, 모니터 내부에 들어간 프로세스에게만 공유 데이터를 접근할 수 있는 기능을 제공하는 것이다. 또한, 프로세스가 모니터에 들어가고자 할 때, 다른 프로세스가 모니터 내부에 있다면 입장 큐에서 기다려야 한다

배타동기큐

배타동기의 queue는 하나의 스레드만 공유자원에 접근할 수 있게 하는 작용을 하는 공간이다. 특정 스레드가 공유자원을 사용하는 함수를 사용하고 있으면 다른 스레드는 접근을 할 수 없고 대기해야 한다.

조건동기큐

조건 동기의 queue는 진입 스레드가 블록되면서 새 스레드가 진입가능하게 하는 공간이다. 새 스레드는 조건동기로 블록된 스레드를 깨울 수 있다. 깨워진 쓰레드는 현재 쓰레드가 나가면 재진입할 수 있다.

Semaphore vs Monitor

• 세마포어는 동기화 함수의 제약 조건을 고려해야하는 반면, 모니터는 프로시져를 호출하여 간단히 해결할 수 있다.

Starvation

정의\
프로세스가 CPU자원의 할당을 무한히 대기하는 것을 말한다. 특히 기아상태는 CPU 스케줄링과 밀접한 관련이 있다.

해결책

• 프로세스 우선 순위를 수시로 변경해서 각 프로세스가 높은 우선 순위를 가질 기회를 준다.
• 오래 기다린 프로세스의 우선 순위를 높여준다. (aging 기법)
• 우선 순위가 아닌 요청 순서대로 처리하는 FIFO 기반 요청 큐를 사용한다.