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에
추가하는 등의 작업을 할 때 발생하는 오버헤드를 말한다.
예시
pthread_mutex_lock()을 이용해서 Busy wait을 할 수 있는데 이는 특수한 하드웨어적 지원이 있어야 가능하다.
mutex는 기본적으로 아래와 같이 구현되어 있는데
typedef struct pthread_mutex {
int lock; // 0: unlocked, 1: locked
pthread_t owner; // 현재 뮤텍스를 소유한 스레드 ID
// ... 기타 필드들
} pthread_mutex_t;mutex의 원자성은 하드웨어 레벨의 특수 명령어를 통해 구현 된다.
- Mutex의 원자성을 보장하기 위한 특수한 명령어 : Test-and-Set
lock xchg [mutex], eax ; 원자적 교환 수행test and set을 cpp로 구현하면 다음과 같다.
bool test_and_set(bool* target) {
bool old_value = *target; // 현재 값 읽기
*target = true; // 새 값 쓰기
return old_value; // 이전 값 반환
}메모리의 값을 읽고 새로운 값을 쓰는 것을 하드웨어 단위에서 원자적으로 연산할 수 있게 해준다.
락이 걸려있는 상태인지 확인하고 락을 거는 동작까지를 원자적으로 실행하며, 락을 해제하는 동작은 다른 메서드를 통해서 실행해야 한다. 아래 코드에서 old_value가 False 였다면 test_and_set == 0 조건이 참이 되어서 현재 thread를 mutex owner로 설정하면서 원자적으로 락을 설정한다.
if (atomic_test_and_set(&mutex->lock) == 0) {
mutex->owner = pthread_self();
return 0;
}- Mutex의 원자성을 보장하기 위한 특수한 명령어 : Compare-and-Swap (CAS)
lock cmpxchg [mutex], ebxCas는 Tas보다 유연한 연산으로 현재 값을 예상 값과 비교한 후 일치할 경우에만 새로운 값으로 업데이트 한다.
Cas의 동작을 cpp로 구현하면 다음과 같다.
bool compare_and_swap(int* target, int expected, int new_value) {
if (*target == expected) {
*target = new_value;
return true; // 성공
}
return false; // 실패
}그래서 Tas를 사용할 때는 무조건 1로 설정하고 이전 값을 반환했다면 Cas는 현재 값이 expected(0)일 때만 new_value(1)로 설정하고 성공 여부를 반환할 수 있다.
Tas 대신 Cas를 사용하는데는 Lock free 또한 관련이 있는데,
첫 째로, 부분적 실패를 허용 가능하다는 점과 둘 째로 선택적 업데이트가 가능하다는 점등을 통해서 Lock free를 구현할 때 Tas 대신 Cas가 더 유연하게 동작할 수 있다.
부분적 실패 허용과 선택적 업데이트
- 부분적 실패 허용
// 예: 큐에서 데이터 읽기
Node* dequeue(Queue* queue) {
while (true) {
Node* head = queue->head;
if (head == NULL) return NULL; // 큐가 비었음
// head가 여전히 우리가 본 값과 같다면 다음 노드로 이동
if (atomic_compare_exchange_strong(&queue->head,
&head,
head->next)) {
return head;
}
// 실패하면 다시 시도 (다른 스레드가 이미 dequeue 했음)
}
}- 선택적 업데이트
// 예: 캐시 값 업데이트
void update_if_greater(AtomicMax* max, int new_value) {
int old_value;
do {
old_value = max->value;
if (new_value <= old_value) {
return; // 새 값이 더 작으면 업데이트하지 않음
}
} while (!atomic_compare_exchange_strong(&max->value,
&old_value,
new_value));
}- pthread_mutext_lock() 함수의 구현
wait wake up 방식이라고 해서 아예 spin lock이 없는건 아니라, cpu를 점유하고 있는 시간동안에 계속 루프를 돌면서 확인하는게 아닌 아주 짧은 시간동안 spin을 돌면서 확인하고 syscall을 통해 커널의 wait queue에 들어가게 된다. 이 때, wait queue에 들어가면 context switching 되지 않고 cpu 자원을 사용하지 않는다.
int pthread_mutex_lock(pthread_mutex_t *mutex) {
while (1) {
// 1. 먼저 빠른 경로 시도 (TAS 사용)
if (atomic_test_and_set(&mutex->lock) == 0) {
mutex->owner = pthread_self();
return 0;
}
// 2. 획득 실패시 시스템 콜을 통한 대기
if (should_spin()) {
// 짧은 시간 동안 스핀
for (int i = 0; i < SPIN_COUNT; i++) {
if (mutex->lock == 0) {
continue; // 다시 TAS 시도
}
cpu_relax(); // 프로세서별 최적화된 대기
}
}
// 3. 스핀 실패시 커널 모드로 전환
syscall(SYS_futex, &mutex->lock, FUTEX_WAIT, 1, NULL);
}
}락을 점유하고 있던 스레드가 unlock을 하면 커널이 futex를 통해 대기하고 있는 스레드를 깨워준다. 그러면 위 코드에서 짧은 spin lock을 실행하고 또 하나의 thread가 lock을 획득하게 되고 다른 스레드는 잠드는 방식으로 계속 동작하게 된다.
전체코드
#include <pthread.h>
typedef struct {
int value; // 세마포어 값
pthread_mutex_t mutex; // 상호 배제를 위한 뮤텍스
pthread_cond_t cond; // 조건 변수
int waiting_threads; // 대기 중인 스레드 수
} semaphore_t;
// 세마포어 초기화
void sem_init(semaphore_t *sem, int initial_value) {
sem->value = initial_value;
sem->waiting_threads = 0;
pthread_mutex_init(&sem->mutex, NULL);
pthread_cond_init(&sem->cond, NULL);
}
// 세마포어 획득 (P 연산)
void sem_wait(semaphore_t *sem) {
pthread_mutex_lock(&sem->mutex);
// 세마포어 값이 0이면 블록
while (sem->value <= 0) {
sem->waiting_threads++;
pthread_cond_wait(&sem->cond, &sem->mutex);
sem->waiting_threads--;
}
sem->value--; // 자원 사용
pthread_mutex_unlock(&sem->mutex);
}
// 세마포어 해제 (V 연산)
void sem_post(semaphore_t *sem) {
pthread_mutex_lock(&sem->mutex);
sem->value++; // 자원 반환
// 대기 중인 스레드가 있으면 하나를 깨움
if (sem->waiting_threads > 0) {
pthread_cond_signal(&sem->cond);
}
pthread_mutex_unlock(&sem->mutex);
}
// 세마포어 제거
void sem_destroy(semaphore_t *sem) {
pthread_mutex_destroy(&sem->mutex);
pthread_cond_destroy(&sem->cond);
}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).