📗 관련 포스팅
📌 배경 지식
컴퓨터는 한 번에 한 개의 프로세스만 실행이 가능하다.
📌 문제 상황
프로세스 A,B가 존재, 각 프로세스가 회사 계좌에서 돈을 입금/출금하려고 한다.
다음과 같은 그림으로 표현할 수 있을 것이다.
앞서 본 배경지식에서 컴퓨터는 한 번에 하나의 프로세스만 실행할 수 있다고 했다.
다음과 같은 상황에서 계좌 잔액을 불러와 연산(입금) 후 이를 다시 저장해야 한다.
그런데, 저장하기 전에 Process A의 실행이 끝나버렸다. 이 때 Process B가 실행이 된다면 어떻게 될까?
Process B는 저장까지 제대로 실행이 되었다라 가정한다면, 계좌 잔액은 90,000원일 것이다.
이 상황에서 Process B의 실행이 끝난 뒤, 다시 Process A가 실행되게 된다.
Process A가 실행되고 나면 계좌잔액은 110,000원이 된다.
우리의 시선으로 보았을 때는 입금 10,000원 / 출금 10,000원이 되었다면 잔액은 100,000원이 되어야 한다.
그러나 컴퓨터의 입장에서는 앞서 본 컴퓨터는 한 번의 한 프로세스만 실행한다는 특징때문에 다음과 같은 동기화가 되지 않음으로 일어나는 문제가 발생하게 된다.
그렇다면, 여기서 동기화란 무엇인가를 추측할 수 있다.
동기화는 한 프로세스가 해야할 작업이 완전히 끝날 때까지 다른 작업이 실행되지 않도록 하여 결과가 제대로 반영되도록 한다.
위의 사항을 통해 동기화에 사용되는 용어를 몇 개 더 알아보자.
📌 용어
1. Producer-Consumer Problem 생산자-소비자 문제
위에서 본 것과 같이 데이터를 생성해 저장하는 Process A와 데이터를 소비해 저장하는 Process B가 존재할 때 발생하는 문제이다.
용어에 집착하지 말고, 동시에 여러 프로세스(혹은 쓰레드)가 하나의 공유 변수(잔액)에 접근할 때 문제가 발생한다는 것을 알면 된다.2. Race-Condition 경쟁 상태
Producer-Consumer 문제와 비슷한 개념이다. 동시에 여러 프로세스가 하나의 자원을 두고 경쟁하는 상태를 말한다. 위와 같은 상황에서 3가지 문제점 상호 배제(Mutual Exclusion), 교착 상태(Deadlock), 기아(Starvation)이 발생하게 된다. 해당 문제점에 대해선 아래에서 자세히 다룬다.3. Critical Section 임계 영역
위의 상황에서 계좌 잔액이 한 프로세스에 의해 업데이트가 되기 전에 해당 공유 변수(잔액)에 접근하여 문제가 발생하였다.
이와 같이 동시에 여러 프로세스가 접근하면 문제가 되는 영역을 '임계 영역'이라고 한다.
동기화
위에서 발생하는 문제를 막기 위한 방법.
한 프로세스만 임계영역의 코드를 실행할 수 있도록 하여 공유 변수는 하나의 프로세스만 접근 가능하도록 한다.
이는 간단하게 임계 영역에 접근하기 전 lock을 걸어 나만 들어갈 수 있도록 하고, 임계 영역에서 나온 뒤 lock을 풀면 된다는 것을 떠올릴 수 있다.
참고로, 내가 lock을 걸 때 이미 다른 프로세스가 lock을 걸고있으면 나는 대기한다고 생각하면 된다.
동기화에는 여러 방법이 있는데 우선 임계영역 문제 해결법에 요구사항에 대해 알아보자.
📌 임계영역 문제 해결법 요구사항
1. 상호배제 Mutual Exclusion
두 프로세스가 동시에 임계영역에 접근하지 못하도록 한다.2. 진행 Progress
임계영역 내 코드를 실행 중인 프로세스가 없는 경우, 임계 영역에 접근하려는 프로세스가 존재하면 바로 접근 가능해야 한다.
❗ 만약, 한 프로세스가lock을 걸어 임계영역을 실행한 뒤,lock을 반납을 안 했다면?
다른 프로세스는 계속해서 다른 프로세스가lock을 건 줄 알고 실행하지 않을 것이다.3. 유한대기 Bouded Waiting
process A가lock을 걸고 있으면 process B는 임계영역에 접근하지 못하고 기다린다.
만약 A가 해당 공유변수에 접근을 요청하여 A가 자원을 사용 중인 상황에서, B도 요청을 했다고 하자. 이 때, A가 계속해서 요청을 보내면 B는 무한히 대기하게 되는데 이러한 상황을 막아야한다.
따라서, 위의 3가지 요구사항을 동기화 방법들이 만족하는 지 확인하면 된다.
아래에서 몇 가지 방법을 알아보자.
예시 1
다음 코드는 쉽게 말하면 나의 turn이 아니면 while문 반복을 통해 프로세스가 실행하는 동안 대기하는 것이다.
초기에 turn=i라 하고, 코드를 그림으로 나타내보면 다음과 같다
초기에 turn=i이므로 process i는 반복문을 실행하지 않고 임계영역에 접근한다.
임계영역의 접근이 끝난 후 turn=j로 바꾼다.
turn=j이니 process j는 반복문을 실행하지 않고 임계영역에 접근한다.
이 상태에서 process j의 실행이 끝나고 process i가 실행이 되었다고 해보자.
현재 turn=j이니 process j가 여전히 임계 영역 내부의 코드를 실행 중이었다는 상황이다.
따라서, process i는 반복문의 조건에 부합하며 실행 시간동안 내용이 없는 while문을 돌며 대기하게 되는 것이다.
다음 코드에서 turn 변수에 따라 한 프로세스만 임계 영역에 접근하니 상호 배제 Mutual Exclusion는 잘 되는 것 같다.
그러나 진행 Prgress에서 문제가 발생한다.
만약, process j가 임계 영역에 접근하지 않는다고 해보자.
맨 처음봤던 예제를 예로 들자면 process j는 출금이 아니라 계좌 주인을 확인하는 작업을 하려고 한다고 해보자.
계좌 주인은 변하는 값이 아니라 임계 영역이 아니다.
그러나, process j가 실행될 때 process i가 임계영역 내부에 있어 turn != j이면 임계영역에 접근하지 않음에도 불구하고 해당 프로세스는 while 반복문에 걸려 대기하게 되는 문제가 발생할 것이다.
예시 2
다음 코드는 쉽게 말하면 다른 프로세스가 "나 임계영역에 들어갈꺼야"라는 의사표현(flag)을 했으면 나는 대기한다는 코드다.
그림으로 나타내면 다음과 같다.
초기에는 flag[]의 모든 값이 false로 저장되어 있다.
process i가 실행되게 되면
flag[j] == false 이므로 "내가 쓸거야!"라는 의사표현을 하고(flag[i] = true) 임계 영역에 들어가게 된다.
process i가 임계 영역 실행 중에 process j로 넘어갔다고 가정해보자.
그러면 다음과 같은 상황일 것이다. process j가 실행되면 flag[i] == true이므로 while 반복문을 통해 무의미한 반복문을 반복해 대기하게 된다.
그러나, 다음 코드에도 문제가 있다.
바로 프로세스 실행 맨 처음에 상대가 쓰고 싶은지 확인한다는 것이다.
따라서, 만약 Process i와 Process j가 거의 동시에 실행이 된다고 가정해보자.
그러면 초기 flag[i] == false, flag[j] == false 이므로 두 프로세스가 모두 임계 영역에 접근하게 되어 상호 배제 Mutual Exclusion을 만족시키지 못하게 된다.
그러면 flag 설정을 가장 먼저하면 되지 않을까?
예시 3
그러면 위와 같은 코드에서 문제점은 뭘까?
오히려, 맨 처음 둘다 "내가 쓸거야"라는 의사표현을 하게 됨으로써 두 프로세스 모두 임계영역에 진입하지 못하게 될 수 있다.
따라서, 이 방법또한 진행 progress 에서 문제가 발생하게 된다.
위와 같은 방법들에서 문제가 발생하게 된다.
이를 해결하기 위해 SW/HW적 해결 방법이 다수 나오게 된다.
SW적 해결 방법
1. 패터슨 해결법 Paterson's Solution
2. 데커 해결법 Dekker's Solution
3. 세마포어 Semaphore
HW적 해결 방법
1. TestAndSet Instruction
2. Swap Instruction
