Race Condition
두 개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이뤄졌는지에 따라 그 실행 결과가 달라지는 상황
import threading
# 공유 변수
count = 0
def increment_count():
global count
# count 값을 1 증가시키는 함수
for i in range(1000000):
count += 1
# 2개의 스레드 생성 및 실행
thread1 = threading.Thread(target=increment_count)
thread2 = threading.Thread(target=increment_count)
thread1.start()
thread2.start()
# 스레드 종료 대기
thread1.join()
thread2.join()
# 최종 count 값 출력
print(count)다음 코드의 실행결과는 2,000,000이 되길 기대하지만 count가 race condition 문제로 인해서 매번 달라진다는 것을 알 수 있다.
대표적으로 레이스 컨디션이 발생할 수 있는 사례
커널 영역에서 fork()를 통해서 프로세스를 새로 발급 받을 때 pid가 곂칠 수 있다는 문제점이 있다.
임계영역 (Critical Section)
코드의 구성을 다음과 같이 나눌 수 있다.
- Entry Secition : 코드가 시작하는 영역
- Critcal Section : 공유 데이터를 다루는 영역
- Ramainder Section : 코드의 나머지 부분
임계영역 문제 해결을 위해 필요조건
Critical Section에서 발생할 수 있는 문제를 해소하기 위해선 다음과 같은 조건들이 충족되어야 한다.
상호배제 (Mutual Exclustion)
임계 구역에는 하나의 프로세스만 존재해야 한다. 만약 어떤 프로세스가 임계 구역을 실행하고 있다면 다른 어떤 프로세스도 그 임계 구역에 진입할 수 없다.
진행 (Progress)
임계 구역을 실행하고 있는 프로세스가 없고 진입하고자 하는 프로세스가 두 개 이상일 때, 이들의 진입 순서는 이들에 의해서만 결정되야 한다. 또한 선택하는 절차를 무기한 연기할 수 없다.
한정된 대기 (Bounded waiting)
모든 프로세스는 임계 구역에 들어가기 위해 기회를 가질 수 있어야 한다. 👉 기아 현상 방지
소프트웨어적 해결방안
첫 번째 해결방안
Mutual Exclusion을 만족하지만 하나의 프로세스가 Critical Section을 다 사용하고 나와야지만 상대 턴으로 넘어갈 수 있게 된다. 이로 인해서 Progress 문제가 발생할 수 있다고 할 수 있다. 만약에 Process 0이 한 번만 들어가고 싶고 Process 1은 여러번 들어가고 싶은 상태라면 Process 0가 종료되었을 때 Process 1도 턴이 돌아오지 않는 경우가 발생할 수 있다.
Process 0 수행 후 턴 Process 1로 변경 후 종료 👉 Process 1 수행 후 턴 Process 0으로 두고 종료 👉 Process 0은 이미 종료되어서 더 이상 수행 안되므로 Process 1이 Critical Section을 사용하기 위해서 무한정 대기
두번째 해결방안
void main() {
do {
flag[i] = true;
while(flag[j]); // 상대 프로세스가 실행중이면 대기
/* critical section */
flag[i] = false;
/* remainder section */
} while(1);
}해당 알고리즘은 Synchronization 문제를 극복하기 위한 코드지만 이 자체가 Synchronization 문제가 있을 수 있다. 왜냐면 flag[i] = true를 동시에 실행하게 되버린다면 두 프로세스가 다 true를 들고 있는 상황에서 두 프로세스 모두 Critical Section에 들어가지 못하고 대기하는 상태가 되어버릴 수 있기 때문이다.
즉, Bounded waiting 문제가 발생할 수 있다는 것이다.
Peterson’s Algorithm
“상대방이 깃발을 들고 있으면서 상대방 차례이다.”를 동시에 만족하는 경우에만 Critical Section에 진입하지 못하는 알고리즘(while문 부분은 while문을 충족할 경우 ciritical secion으로 진입하라는 뜻이 아니라 while문을 충족할 경우 무한정 대기하라는 뜻)이다.
이 알고리즘은 Busy Waiting이 발생할 수 있다.
Busy Waiting이란 프로세스가 Critical Section에 진입하기 위해 무한정 대기하는 상황을 말한다.
만약에 Block/Wakeup 방식을 사용하면 특정 프로세스가 공유 자원을 다 썻을 때 다른 프로세스를 깨워줌으로써 공유 자원에 접근이 불가능한 시간에는 프로세스가 CPU를 점유하지 못하도록 한다.
하드웨어적 해결방안
Test and Set
Atomic하다는 것은 하나의 Instructions으로 처리를 한다는 뜻이다. 즉, Lock을 거는 Instruction Set을 읽고 쓰고를 분리해서 하는 것이 아니라 읽고 쓰는 과정을 하나로 합쳐서 Lock을 걸 수 있도록 하는 것을 말한다.
Test_and_Set(lock)을 하면 만약에 lock이 걸려있지 않으면 0일테고 0을 1로 변환 후 Critical Section으로 진입하고 이렇게 Lock이 걸린 상태에서 다른 프로세스가 들어오게되면 Test_and_Set(lock)을 했을 때 1을 return 함으로써 lock이 풀릴 때까지 Critical Section에 진입하지 않고 대기하는 것이다.
Semahpores
세마포어는 일종의 추상 자료형으로 세마포어 값을 획득하기 위해서 P연산과 V연산을 할 수 있는데 P 연산과 V 연산은 atomic 하다.
만약에 세마포어를 활용해서 Critical Section 문제를 해결하고 싶다면 세마포어를 1로 초기화하고 P연산을 통해서 세마포어를 획득하고 Critical Section을 실행한 후에 V연산을 통해서 세마포어를 반환하는 방식으로 사용할 수 있다.
👆 세마포어를 활용한 Critical Section 문제 해결방법
위와 같은 방식을 사용하더라도 Peterson’s Solution처럼 Spin Lock이 걸려서 Busy Waiting이 발생할 수 있다.
Block / Wakeup Implementation
Busy Waiting과 같은 문제를 해결하기 위해서 Block / Wakeup을 사용할 수 있다.
IO Queue와 같이 Block Queue를 만들어서 Block Queue에 들어가는 프로세스는 Critical Section에 진입하지 못하고 대기하게 되고 Critical Section을 빠져나온 프로세스는 Wakeup을 통해서 Block Queue에 있는 프로세스를 깨워서 Critical Section에 진입할 수 있도록 하는 방식이다.
Block / Wakeup 방식의 P연산과 V 연산
- P연산 : 자원의 여분이 없다면 Block Queue에 들어가고 자원의 여분이 있다면 자원을 하나 줄이고 Critical Section에 진입한다.
S.value--;
if(S.value < 0) {
// Block Queue 리스트에 현재 프로세스를 추가
add this process to S.list;
block(); // Block 됨
}- V연산 : 자원을 반납하고 끝나는게 아니라 혹시 잠들어 있는 프로세스가 있다면 깨워서 Critical Section에 진입할 수 있도록 해줘야 한다.
S.value++;
if (S.value <= 0) {
// P 프로세스를 Block Queue에서 삭제
remove a process P from S.list;
wakeup(P); // P 프로세스를 깨움
}Busy-wait vs Block/Wakeup
✔️ Critical Section의 길이가 긴 경우 Block/Wakeup 방식이 효율적이다.
✔️ Critical Section의 길이가 매우 짧은 경우 Block/Wakeup 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있다.
✔️ 일반적으로는 Blcok/Wakeup 방식이 Busy-wait 방식보다 효율적이다.
Block/Wakeup 오버헤드란?
Block/Wakeup 방식을 사용하기 위해서 프로세스 상태를 변경하고 Block Queue에 추가하는 등의 작업을 할 때 발생하는 오버헤드를 말한다.
Semaphores의 한계
Deadlock
Process 1이 S라는 세마포어를 Process 2가 Q라는 세마포어를 차지하고 서로 다른 세마포어를 기다리면서 무한히 대기하는 상황을 말한다.
Starvation
특정 프로세스들만 계속해서 세마포어를 획득하고 다른 프로세스가 사용하지 못하도록 하는 상황을 말한다.
ETC
세마포어를 카운팅 하는 방법과 Boolean 값을 사용하는 방식에 따라서 Counting Semahpores와 Binary Semaphores로 나눌 수 있다.
- Counting Semaphores : 세마포어를 0과 1이 아닌 정수값을 가지며 0 이하이면 자원이 없는 것이니 대기하고 0 이상이면 자원이 있는 것이니 사용하도록 하는 방식
- Binary Semaphores : 세마포어를 0과 1로만 가지며 0이면 자원이 없는 것이니 대기하고 1이면 자원이 있는 것이니 사용하도록 하는 방식
Bounded Buffer Problem
버퍼의 크기가 유한한 환경에서 생산자와 소비자가 동시에 버퍼에 접근할 때 발생하는 문제를 말한다.
문제가 발생하는 경우
- 생산자 둘이 동시에 버퍼에 접근해서 버퍼에 데이터를 넣으려고 하는 경우
- 소비자 둘이 동시에 한 데이터를 소비하려고 하는 경우
- 공유 데이터가 가득 차서 생산자가 데이터를 넣을 수 없는 경우
- 소비자가 데이터를 소비해서 버퍼가 빌 때까지 기다려야 한다.
- 공유 데이터가 비어서 소비자가 데이터를 소비할 수 없는 경우
- 생산자가 데이터를 넣을 때까지 기다려야 한다.
생산자/소비자 동작
생산자
- Empty 버퍼가 있나요? (없으면 기다림)
- 공유데이터에 lock을 건다.
- Emtpy Buffer에 데이터 입력 및 Buffer를 조작한다.
- lock을 해제한다.
- Full Buffer 하나 증가한다.
do {
produce an item in X
P(empty); // 락 확인
P(mutex);
add X to buffer;
V(mutex);
V(full);
} while (1);소비자
- full 버퍼가 있나요? (없으면 기다림)
- 공유데이터에 lock을 건다.
- Full Buffer에 데이터 소비 및 Buffer를 조작한다.
- lock을 해제한다.
- Empty Buffer 하나 증가한다.
do {
P(full);
P(mutex); // 락 확인
remove an item from buffer to Y;
V(mutex);
V(empty);
consume the item in Y;
} while (1);Reader Writer Problem
한 process가 DB에 write 중 일 때 다른 process가 접근하면 안된다.
read는 동시에 여럿이 해도 된다.
solution
P(db);
writing DB is performed
V(db);👉 starvation 발생 가능
P(mutex);
readcount++;
// 리드 카운트가 1이면 db에 락을 건다.
// 1이 아니면 이미 누가 lock을 걸었기 때문에 db를 읽기만 하면 된다.
if (readcount == 1) P(db) {
P(db);
}
V(mutex);
reading DB is performed
P(mutex);
readcount--;
// 리드 카운트가 0이면 db에 락을 해제한다.
if(readcount == 0) V(db);
V(mutex);식사하는 철학자 문제
위 그림에서 철학자 4와 철학자 2가 식사를 하게 된다면 철학자 1과 철학자 3은 Starvation이 발생하게 된다.
위 그림에서는 각각의 철학자가 동시에 왼쪽 젓가락을 들었다면 Deadlock이 발생하게 된다. 모든 철학자가 오른쪽 젓가락을 집을 수 없기 때문이다.
해결방안
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
- 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락부터 집도록 한다.
Semaphores Solution
do {
pickup(i);
eat();
putdonw(i);
} while (1);void putdonw(int i) {
P(mutex);
state[i] = THINKING;
test((i + 4) % 5);
test((i + 1) % 5);
V(mutex);
}void pickup(int i) {
P(mutex);
state[i] = HUNGRY;
test(i);
V(mutex);
P(s[i]);
}void test(int i) {
if (state[(i + 4) % 5] != EATING && state[i] == HUNGRY && state[(i + 1) % 5] != EATING)
{
state[i] = EATING;
V(s[i]);
}
}Monitor
기본 뮤텍스 락과 세마포어의 문제
- 뮤텍스의 락 혹은 세마포어를 사용할 때 타이밍 오류가 발생할 수 있다.
- wait()과 signal() 연산의 순서가 뒤바뀌는 경우
- wait : 쉽게 말해 락을 거는(count를 감소시키는) 작업
- signal : 쉽게 락을 푸는(count를 증가시키는) 작업
- Critical Section이 끝나고 signal()대신 wait()이 호출되는 경우
- wait()과 signal() 연산의 순서가 뒤바뀌는 경우
프로그래밍 언어 차원에서 동시접근과 관련된 문제를 monitor가 자동으로 해결해줌으로써 프로그래머의 부담을 줄여주는 방법이다. 내부에 있는 프로시저를 활용해서만 공유 데이터에 접근이 가능하도록 구현된 것이다.
- 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능
- 프로그래머가 직접 lock을 걸거나 해제할 필요가 없음
- 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable을 제공
- ex : Java의 synchronized 키워드
Reference
https://yamyam-spaghetti.tistory.com/50##:~:text=공유되는 자원%2C 즉 동시,이 지난 후 종료된다 (opens in a new tab).