🔍 Background
앞서 프로세스가 커뮤니케이션하는 방법에는 shared memory를 이용하는 방법과 message passing을 이용하는 방법이 있다고 하였다.
여기에는 다음과 같은 문제가 발생한다. (절대 귀찮아서 이러는거 아니다)
Synchronization problem
counter의 초기 값은 5이고, producer가 counter 값을 1 증가시킨 후, consumer가 counter 값을 1 감소시켰다면, counter 값은 5이어야 하지만, 실행되는 순서에 따라 아래와 같은 경우가 발생할 수 있다.
counter의 값이 4 또는 6이 될 수 있는 것과 같이 Queue에서 counter의 값이 정확하지 않다면, 버그로 이어질 수 있다.
Process synchronization
- Race condition
- 여러 프로세스가 동일한 데이터에 동시에 액세스하고 조작하는 상황에서 발생한다.
- 프로그램 1개를 실행시켰을 때는 문제가 발생하지 않지만, 여러 개의 스레드를 실행시켰을 때 버그가 발생한다.- 똑같은 코드라도 실행 순서에 따라 결과값이 달라질 수 있다.
- Synchronization: 일정한 시간에 공유 메모리에 오직 하나의 프로세스만 엑세스 가능하도록 한다.
✔️ The Critical-Section Problem
Critical-Section Problem
- Critical section: shared memeory를 읽거나 쓸 때 race condition이 발생할 수 있는 파트를 의미한다.
- Remainder section: 다른 프로세스와는 무관하게 실행되는 코드 섹션
- Entry section: critical section에 접근할 수 있는 권한을 요청하는 코드 섹션 (피팅룸에 들어가기 전에 허락을 구하는 것과 같은 원리다. 피팅룸에 들어간 후에는 다음 사람이 못 들어오게 문을 잠궈야 한다.)
- Exit section: critical section을 떠난다고 알려주는 코드 섹션 (옷을 다 갈아입었으면 == 코드 실행을 마쳤으면, 문을 열어서 다른 사람이 이용할 수 있도록 해야한다.)
각 프로세스는 critical section을 가지고 있는데, 한 프로세스가 자신의 critical section에서 수행되고 있는 동안 다른 프로세스가 critical section에 들어갈 수 없다는 것이다.
한 번에 한 프로세스만 공유 메모리에 접근하도록 한다.
일반적으로 프로세스는 다음과 같은 section으로 나뉜다.
Requirements of Critical-section problem
- mutual exclusion (상호 배제): 특정한 프로세스가 critical section에서 실행되는 동안, 다른 프로세스가 critical section에 접근할 수 없다. 즉, 어떤 프로세스가 임계 영역을 실행할 때, 다른 프로세스는 코드 실행을 하지 못하도록 처리해야 한다.
- progress (진행) : critical section에서 실행되고 있는 프로세스가 없다면, 다른 프로세스가 접근할 수 있도록 한다.
- bounded waiting (한정 대기) : critical section 진입 횟수에 한계를 두어 동일한 프로세스가 계속 독점하여 사용할 수 없도록 한다.
💡 Peterson's solution
위에서 설명한 ciritical section problem의 solution으로는 여러 가지가 있는데, 그 중 피터슨 알고리즘(Peterson's solution)에 대해 알아보자!
피터슨 알고리즘은 turn과 flag라는 변수로 critical section에 들어갈 프로세스/스레드를 결정하는 방법이다.
먼저 P0, P1이라는 2개의 프로세스가 존재한다고 가정한다. (Pi, Pj로 두어도 무방하다.)
int turn, boolean flag[2]라는 2개의 변수를 사용할 것이다. turn 변수는 어떤 프로세스/스레드가 critical section에 들어갈 차례인지 나타내는 변수이고, flag변수는 공유 자원을 쓰고 싶다라는 것을 표현하기 위한 변수이다.
✅ Erroneous Algorithm 1
먼저, turn변수 하나만 사용하여 알고리즘을 구현하였을 때의 모습이다. turn이 0일때 P0, turn이 1일 때 P1이 critical section에 진입할 수 있도록 하였다. 하지만, 위의 알고리즘 같은 경우turn변수를 사용하여 mutual exclusion을 보장하지만, progress는 보장하지 못한다.
그 경우는 다음과 같다.
P1이 critical section을 빠져나오면, turn을 0으로 바꾼다.
이때P1이 remainder section에 계속 머물러 있다고 해보자.
P0은 turn = 0이 되었으므로, ciritical section에 진입하여 코드를 실행한 후, turn을 1로 바꾸고 remainder section을 실행한다.
그 후P0은 다시 loop를 돌아while(turn != 0)조건을 만나게 되는데, 직전에 turn을 1로 만들어 두었고, P1은 여전히 remainder section에 있어 turn이 0으로 전환되지 않았다.
따라서 P0은 critical seciton에 들어가지 못하고,while(turn != 0);을 계속해서 실행시켜야 하는 경우가 발생하게 된다.
✅ Erroneous Algorithm 2
두번째로 flag변수 만을 사용하여 알고리즘을 구현한 경우이다. 이 알고리즘은 다음과 같이 실행된다. 먼저 loop에 진입하면서 flag를 true로 설정하여 critical section에 들어가겠다고 알린다.
while(flag[j]);를 통해, 상대 프로세스의 flag가 true값을 가지는지 확인하고, true일 경우 대기한다. 상대 프로세스의 flag가 false가 되었을 때, critical section에 진입하게 된다.
critical section을 실행하고 나오면, 자신의 flag를 false로 만들어 critical section에 들어갈 생각이 없음을 표시한다.
이 경우 또한 mutual exclusion을 보장하지만, progress는 보장하지 못한다.
두 개의 프로세스가 동시에 실행 된다면, 두 프로세스의 flag가 모두 true가 되어 제대로 동작하지 않게 되어 progress를 보장하지 못한다.
✅ Peterson's solution
위의 2가지 알고리즘의 에러를 막기 위해, turn과 flag변수를 함께 사용한 피터슨 알고리즘은 다음과 같다.
프로세스 P0과 P1이 있다. 먼저 P0는 flag를 true로, turn은 1로 설정한다. while(flag[1] && turn == 1);을 보면, flag[1] = true이고, turn == 1이면 기다려야 함을 알 수 있다. 이는 P1의 flag가 true라면, P1이 먼저 실행되도록 대기하겠다는 것을 의미한다. P1의 flag가 false라면, P0이 critical section을 실행하게 된다.
이 알고리즘이 앞에서 말했던 3가지 조건에 부합하는지 살펴보자.
❗️mutual exclusion: P0과 P1이 동시에 임계 영역에 들어간다는 것은 flag[0] = flag[1] = true라는 것인데, turn은 0또는 1의 값을 가질 수밖에 없으므로 둘이 동시에 임계 영역에 진입하지 못한다. 따라서 mutual exclusion을 보장한다.
❗️progress & bounded wating:
Pj가 임계 영역에 들어갈 준비가 되지 않았을 경우, flag[j] == false이다 ➡️ Pi가 임계 영역에 들어갈 수 있다.
Pj가 while문에서 기다리고 있을 때, turn은 i이거나 j이다. 만약 turn이 i이면, Pi가 임계영역에 들어갈 수 있으며, turn이 j이면 Pj가 임계 영역에 들어가게 된다.
Pj가 임계 영역을 종료하면, Pj는 flag[j]를 false로 설정하고, pj가 turn을 i로 전환하기 때문에 Pi가 임계 영역에 들어갈 수 있게 된다.
❗️Therefore, Pi will enter critical section (Progress) and waits at most one process (Bounded waiting).
❓ 피또문...
피터슨 알고리즘이 3가지 조건을 만족시켰음에도 불구하고 또 문제가 발생한다..
- 현대 컴퓨터 아키텍쳐에서는 보장된 작동을 하지 않을 수 있다.
시스템 성능을 향상시키기 위해 프로세서 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업의 순서를 바꿀 수 있다.
공유 데이터가 있는 멀티 스레드 응용 프로그램의 경우, 명령 순서를 변경하면 일관성이 없거나 예기치 않은 결과가 발생할 수 있다.
위의 예시를 보면 알겠다시피, cpu가 2개의 스레드가 서로 dependency가 없다고 판단하여 순서를 바꿔 실행되게 하면, 예기치 못한 상황이 발생하여 버그로 이어진다~!
그래서 다음 포스팅에서 다른 동기화 방법들을 정리해볼 것이다!
