프로세스 동기화 (Synchronization)

동기화 vs 비동기화

1. 동기화(Synchronous) 

• 동시에 일어나서, 결과가 그 자리에서 주어짐
• 설계가 매우 간단하고 직관적
• 결과가 주어질 때까지 아무것도 못하고 대기해야 함

2. 비동기화(Asynchronous)

• 동시에 일어나지 않아서, 결과가 그자리에서 주어지지 않음
• 동기화보다 복잡함
• 결과가 주어지는데 시간이 걸리지만, 그 동안 다른 작업을 할 수 있어서 자원을 효율적으로 사용할 수 있음

 

Race Condition

: 여러 프로세스들이 동시에 데이터에 접근할 때 어떤 순서로 접근하느냐에 따라 결과 값이 달라질 수 있는 상황
 

• 공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있음
• Race condition을 막고, 일관성을 유지하기 위해 협력 프로세스 간의 실행 순서를 정해주는 동기화가 필요

 

Race Condition이 발생하는 경우

1. 커널 작업을 수행하는 중에 인터럽트가 발생하는 경우
   : 사용자 프로세스는 해당 프로세스에 할당받은 메모리에만 존재할 수 있지만,
     커널은 서로 다른 프로세스가 공유하기 때문에 발생

• 의도 : count++과 count--가 모두 반영되어 count가 초기값을 유지하는 것
• 결과 : 인터럽트 시점에 따라, count++ 혹은 count-- 만 또는 둘다 반영될 수 있음
• 해결 방안 : 커널 모드의 수행이 끝나기 전에는 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 함

 

2. 프로세스가 시스템 콜을 호출해 커널 모드 수행 중 context switching이 발생하는 경우

• 시스템 콜을 수행하는 동안에는 두 프로세스 모두 커널 주소 공간의 데이터를 접근
• 커널 주소 공간에서 작업을 수행하는 도중에 CPU를 빼앗으면 race condition이 발생
• 커널모드 수행 중에는 시간이 초과되어도 CPU 제어권을 다른 프로세스에게 넘어가지 않도록 해서 해결

 

3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근하는 경우

• 멀티프로세서의 경우 인터럽트 제어로는 해결 불가능
• 한 번에 한 CPU만 커널에 들어갈 수 있도록 하는 것은 비효율적
• 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대해서만 lock/unlock 하는 방식으로 해결

 

* 유저모드: 사용자가 접근할 수 있는 영역에 제한을 두어 프로그램의 자원에 함부로 침범하지 못함
* 커널모드: 모든 자원(드라이버, 메모리, CPU 등)에 접근, 명령을 할 수 있음

 

Critical Section (임계 구역)

: 병렬컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원을 접근하는 코드의 일부
 

Critical Section으로 인해 발생하는 문제를 해결하기 위한 조건

1. Mutual Exclusion (상호 배제)
: 이미 한 프로세스가 Critical Section에서 작업 중이면 다른 모든 프로세스는 Critical Section에 진입해서는 안됨
 
2. Progress (진행)
: Critical Section에서 작업 중인 프로세스가 없다면, 진입하고자 하는 프로세스가 존재하는 경우 진입할 수 있어야 함
 
3. Bounded Waiting (한정 대기) 
: Critical Section에 들어가기 위한 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 함 = Critical Section에 진입하려는 프로세스가 무한정 기다리면 안됨
 

Mutex Lock

• Critical Section Problem을 해결하기 위한 소프트웨어 도구 중 가장 단순한 방법
• Critical Section에 진입할 때 프로세스는 Lock을 걸고, 빠져나올 때 Lock을 해제하여 동시 접근을 막음
• Busy Waiting 문제 존재

* Busy Waiting 문제
: Critical Section에 프로세스가 존재하는데 다른 프로세스들이 계속해서 진입하려고 시도하기 때문에 CPU 낭비

 

Semaphores

• S(사용 가능한 자원 수)에 따라 여러 프로세스나 스레드가 Critical Section에 진입할 수 있음
• Critical Section 진입에 실패한 프로세스는 Block된 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식 사용
• Signaling 매커니즘, Busy Waiting이 필요 없는 동기화 도구
  • block : S <= 0 인 경우, waiting queue로 !
  • wakeup : waiting queue -> ready queue

 

semaphore 구조체 예시

 

Semaphore Implementation with no Busy waiting (single-core)

 

multi-core의 경우, single-core보다 contention이 적어, spinlock 유용

* 단일 CPU에서는 interrupt disable을 통해 wait()와 signal()의 원자성을 구현할 수 있다.
   그러나 다중 코어시스템에서 모든 코어의 interrupt를 막는 것은 손해가 많다.
   따라서 spinlock을 사용하여 다른 코어와 공유하는 세마포 데이터의 상호배타를 보장한다!
 

Semaphores 종류

1. Counting semaphores

• 가용한 개수를 가진 자원 에 대한 접근 제어용으로 사용 (가용한 자원의 개수 로 초기화)
• 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가

2. Binary semaphores

• MUTEX 라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어짐
• 0 과 1 의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용

 

Mutex lock과 Binary Semaphores의 차이 

• mutex lock의 경우, lock을 건 프로세스(,스레드)만 Critical Section을 나갈 때 락을 해제할 수 있음
• Semaphores의 경우, lock을 걸지 않은 프로세스(,스레드)도 signal을 사용해 lock을 해제할 수 있음

= Semaphores는 mutex가 될 수 있지만, mutex는 Semaphores가 될 수 없다!

 

Monitor

• 동시 수행 중인 프로세스 사이에서 추상 데이터의 안전한 공유를 보장하기 위한 High-level 동기화 구조
• 모니터의 내부 Procedure를 통해서만 공유 데이터에 접근할 수 있음
• 하나의 프로세스만 모니터 내부 함수 사용 (active), 나머지는 대기!
• 실행 중인 프로세스가 더 이상 진행이 불가능한 경우, condition variable(queue) 을 사용하여 스스로 suspend
• 직접 wait(), siganl() 할 필요 없이, synchronized를 붙이면 자동으로 구현 해줌 (세마포와의 차이점)
• mutex는 프로세스 간 동기화에, monitor는 스레드 간의 동기화에 사용 (mutex와의 차이점)
• (객체 개념과 유사)

 
Q. 프로세스 P가 x.signal()을 호출하고 프로세스 Q가 x.wait()으로 일시 중단되면 어떻게 될까?
monitor에서는 동시에 2개의 프로세스가 병렬로 진행될 수 없다. 따라서 Q가 깨어났을 때 총 2가지 방안이 있다.
 
1. Signal and Wait
: P는 Q가 다 마치거나 스스로 suspended 될 때까지 기다린다. (깨운 것이 기다리는 방식)
 
2. Signal and Continue 
: Q는 P가 다 마치거나 스스로 suspended 될 때까지 기다린다. (깨어난 것이 기다리는 방식)