동기화 문제와 세마포어

동기화 문제 (Synchronization problem)

동기화 문제란 공유 데이터를 여러 프로세스나 스레드가 동시에 접근하여 연산하려 할 때 연산이 원자적으로 수행되지 않아 발생하는 문제입니다. 아래 예시를 통해 어떤 문제가 생기는 지 알아보겠습니다.

(동기화란 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것)

 

위에 공유 자원 X 에 접근하는 두 스레드 A, B 가 있습니다.

A 는 X 값을 하나 올리는 연산을 하고, B 는 X 를 하나 내리는 연산을 합니다. 

 

실제 CPU 에서는 x= x + 1 연산이 한번에 이루어 지는 것이 아닌 다음과 같이 수행됩니다.

1. x를 레지스터에 로드한다

2. 레지스터에 데이터를 하나 올린다.

3. 다시 레지스터 값을 x에 저장한다.

 

스레드 A 가 1번 까지 연산을  수행하고 인터럽트가 걸려 스레드 B가 실행된다면? 

스레드 B는 자신의 연산을 잘 마무리하고 X 를 1로 만들고 다시 스레드 A에게 CPU 할당이 넘어와 다음 연산부터 실행할 것입니다.

이때 스레드 A의 레지스터에는 이전의 x값이 로드되어 있어 해당 연산을 끝내면 X 를 3으로 만들 것입니다.

그럼 스레드 B에서는 X 에 1을 기대하고 있지만 실제 데이터는 3이 저장되는 데이터 불일치 문제가 일어 날 수 있습니다.

 

해당 연산이 원자성이 보장되어 있지 않기 때문에 발생하는 문제입니다.

 

x=x+1 과 같은 공유 데이터에 접근하는 코드를 Critical Section 이라고 합니다.

그리고 위와 같이 여러 프로세스나 스레드가 같은 공유 자원에 접근하려는 상황을 Race Condition이라고 합니다.

 

동기화 문제 해결하기 위한 충분 조건

1. Mutual Exclusion (상호배제)
   • 한 프로세스가 critical section 부분을 수행중이라면 다른 모든 프로세스들은 critical section 을 수행하지 못하는 것을 말합니다.
2. Progress (진행)
   • 어떠한 프로세스도 critical section에 있지 않고 critical section에 들어가고자 하는 프로세스가 있다면 해당 프로세스는 critical section에 들어갈 수 있도록 해주는 것을 말합니다.
3. Bounded Waiting (한정대기)
   • 한 프로세스가 critical section에 들어가고자 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 진입하는 횟수에 제한이 있는 것을 말합니다. (Starvation을 막기 위함)

 

동기화 문제를  해결하기 위한 주요 알고리즘

알고리즘 1

do{
  while(turn != 0);
  critical section 수행
  trun = 1;
  남은 부분 수행 
}while(1);

 

해당 알고리즘은 내 턴일 경우에만 critical section을 수행 합니다.

내 턴이 아닐 경우는 계속 의미없는 while 문을 돌며 critical section을 수행하지 않다가 내 턴이 됐을 때 critical section을 수행합니다.

• 항상 다른 프로세스가 턴을 내 턴으로 바꿔줘야 내가 들어갈 수 있다.
• 즉 항상 한번씩 돌아가면서 critical section에 들어갈 수 있다.
• 나는 들어가고 싶지만 다른 프로세스는 critical section에 들어갈 필요가 없어서 턴 값을 변경해주지 않는다면 critical section에 들어갈 수 없다.
• mutual exclusion 만족 , progress 불만족

 

알고리즘 2

do{
  flag[i] = true;
  while(flag[j]);
  critical section 수행
  flag[i] = false;
  남은 코드 수행
}while(1)

 

해당 알고리즘은 자신이 critical section에 들어가고 싶다는 의사표현을 합니다. (flag를 통해서)

만약에 다른 프로세스들도 해당 의사표현을 한다면 기다리고 아니라면 critical section 에 들어가 수행하면 됩니다. 

• 실제 critical section에 들어간 프로세스가 없는데도 서로 의사표현만 하며 눈치를 보는 상황이 발생합니다.
• mutual exclusion은 만족하지만 역시 progress 는 불만족 합니다.

Perterson의 알고리즘

do{
  flag[i] = true;
  trun = j;
  while(flag[i] && turn == j);
  critical section 수행
  flag[i] = false;
}while(1)

 

해당 알고리즘은 자신이 critical section에 들어가고 싶다는 의사표현을 하고 실제 내 턴이 됐을 경우에 critical section을 수행하는 알고리즘 입니다.

• 이 알고리즘은 mutual exclusion, progress, bounded waiting 을 모두 만족합니다.
• 하지만 크리티컬 섹션에 들어가지 못하는 프로세스가 계속 CPU와 메모리를 쓰면서 기다리기 때문에 자원을 낭비하는 문제가 있습니다.
• 이 문제를 Busy waiting 또는 Spin lock 이라고 합니다.

 

하드웨어적인 지원 

크리티컬 섹션에 들어가기 전에 락이 걸렸는 지 확인하고 락이 안 걸렸다면 락을 걸고 크리티컬 섹션에 들어가 작업을 처리후 끝나면 락을 풀어주는 방식을 사용한다.

do{
  while(Test_and_set(lock);
  critical section 수행
  lock = false;
  남은 코드 수행
}while(1)

 

test_and_set(lock) 함수는 공유되는 lock을 그대로 반환하고 반환하기 전에 lock의 값은 무조건 true로 변경해주는 함수입니다.

즉 락이 false 라면 false 를 그대로 반환하여 while() 문을 빠져 나오고 critical section을 수행한다. 이때 lock은 true로 바뀌어 다른 프로세스들이 접근하지 못 합니다.

 

test_and_set() 은 CPU에서 지원하는 atomic 명령어로 실행 중간에 간섭받거나 중된되지 않습니다.

 

 

Semarphore (세마포어)

세마포어란 앞의 방식을 추상화 시킨 자료형을 말합니다.

세마포어는 자원의 개수를 나타내는 변수와 자원을 할당하는 함수, 자원을 반납하는 함수로 구성되어 있습니다.

크리티컬 섹션에 접근하지 전에는 자원을 할당하는 함수 (P(s)) 를 통해 자원을 할당 받고 (자원이 없다면 기다리거나, block 된다)

크리티컬 섹션의 작업이 끝난다면 자원을 반납합니다. (V(s))

 

Busy-waiting구현 방식

자원이 없다면 자원이 생길때까지 기다리는 방식입니다. 

자원이 없어도 CPU 가 while 문을 돌리면서 자원을 낭비하기 때문에 비효율적입니다.

 

Block / Wakeup 구현 방식

세마포어 자료형에 process wait queue를 추가하여 자원을 할당받지 못한 프로세스는 wait 시키고 나중에 자원이 생겼을 때 wakeup 시키는 방식입니다.

 

* 일반적으로는 Block / Wakeup 방식이 효율이 좋지만 크리티컬 섹션의 길이가 짧다면 오히려 Busy-waiting 방식이 좋을 수 있다.

context switching 비용이 더 클수도 있다.