Syncrhonization
Computer Science - OS
synchronization(동기화): 프로세스(쓰레드)들이 프로그래머가 의도한 순서대로 실행되도록 제어함
Producer-Consumer model
- producer - buffer에 data를 저장하는 프로세스(쓰레드)
- consumer - buffer의 data를 사용하는(꺼내는) 프로세스(쓰레드)
// Producer thread
while (true)
{
/* Produce an item and put in nextProduced */
while (counter == BUFFER_SIZE)
; // Do nothing if buffer is full.
buffer[in] = nextProduced; // Data inserted
in = (int + 1) % BUFFER_SIZE; // circular buffer
counter++;
}
// Consumer thread
while (true)
{
while (counter == 0)
; // Do nothing if buffer is empty.
nextConsumed = buffer[out]; // Data fetched
out = (out + 1) % BUFFER_SIZE;
counter--;
/* Consumed the item in nextConsumed */
}
Race condition
한 개 이상의 쓰레드가 하나의 공유된 data에 동시에(concurrently) 접근할 때 그 접근 순서에 따라 실행 결과가 달라지는 상황. 프로그램이 의도한대로 실행되지 않을 수 있다.
Synchronization(동기화)은 race conditino을 해결하는 mechanism(protocol)이다.
Synchronization
동기화의 기본 형태
// Entry section: 공유 자원 접근에 대한 허가를 요청하는 코드
/* Critical section
* 공유 자원에 접근하는 코드
**/
// Exit section: 공유 자원 사용을 끝냈음을 알린다.
동기화의 조건
다음 세 가지 조건을 만족해야 race condition을 해결하는 완벽한 매커니즘이다.
- Mutual Exclusion: Critical section에는 한 번에 하나의 thread만 접근 가능하다.
- Progress: 현재 Critical section에 접근중인 쓰레드가 없다면 다음으로 접근할 쓰레드를 바로 선택할 수 있어야 한다.
- Bound Waiting: 한 번에 Critical section에 접근할 수 있는 시간은 제한되어야 한다.
공유자원은 화장실에, 쓰레드는 사람에 비유할 수 있다.
Mutex
Synchronization을 구현한 것이다.
- Locking: Caller는 critical section에 접근하기 위한 lock을 획득(acquire)한다.
- Unlocking: Caller는 획득했던 lock을 반환(release)한다.
- Locked state: 어떤 쓰레드가 mutex를 hold/own하고 있는 상태. Critical Section에 접근할 수 없다.
- Unlocked state: 공유 자원에 접근중인 쓰레드가 없다.
2개 이상의 쓰레드들이 mutex를 획득하기 위해 경쟁할 때, loser(mutex 획득에 실패한 쓰레드)들은 lock을 요청하는 함수가 호출된 시점에 block된다. 순차적으로 lock을 획득하게 된다.(Waiting Queue에 삽입된다.)
Waiting Queue에 삽입된 쓰레드(Wait status)들은 스케쥴링 대상이 아니기 때문에 while loop를 사용한 busy-wait 방식보다 효율적으로 CPU를 사용할 수 있다.
POSIX Mutex-related functions
POSIX
UNIX OS 사이의 호환성을 위해 만든 OS의 표준 인터페이스. 응용 프로그램을 개발할때 사용된다.
int pthread_mutex_init(pthread_mutex_t* restrict mutex);
int pthread_mutex_destroy(pthread_mutex_t* mutex);
int pthread_mutex_lock(pthread_mutex_t* mutex); // Acquire lock
int pthread_mutex_trylock(pthread_mutex_t* mutex);
int pthread_mutex_unlock(pthread_mutex_t* mutex); // Release lock
trylock- lock 획득에 실패하더라도 쓰레드가 block되지 않고 계속 진행된다. Lock 획득에 실패했을 때의 실행 흐름을 제어할 때 사용한다.lock- lock 획득에 실패하면 즉시 쓰레드는 block된다.
Semaphore
Synchronization을 구현한 것이다. Semaphore token 또는 semaphore counter라는 integer value를 사용한다. token의 값이 0이 되면 더 이상 critical section에 접근할 수 없다.
wait(...)- semaphore_token 1 감소 (mutex의 acquire lock과 유사)signal(...)- semaphore_token 1 증가 (mutex의 release lock과 유사)
wait와 signal 함수는 atomic operation이다. 실행 중간에 context switching이 일어나지 않는 것이 보장된다.
Deadlock
모든 쓰레드들이 lock을 획득하기 위해 block된 상태.
Reference
- 3-1 운영체제
Comments