Synchronization

김세영·2021년 6월 11일

프로세스 또는 스레드의 실행을 제어하는 과정을 Synchronization(동기화)라 한다.

Race Condition

같은 데이터를 여러 개의 스레드가 병렬적으로 접근할 때,
특정 시점에 대해 프로그램 실행마다 다른 값이 적용되는 것을
Race Condition이라 한다.

이 때 같은 데이터를 접근하는 부분을 Critical Section이라 한다.
Critical Section을 잘못 처리해주면 Race Condition이 발생하는데,

이 Race Condition을 해결하는 것을 Synchronization(동기화)라 한다.

Synchronization Basic

Critical Section은 접근할 때 Entry Section,
사용하고 빠져나올 때 Exit Section을 지나야 한다.

Entry Section은 Critical Section을 사용할 수 있도록
허락을 기다리는 부분이고,
Exit Section은 Critical Section을 모두 사용했다고
알리는 역할이다.

Race Condition Problem

동기화를 완벽하게 처리하기 위해선 다음 3가지 조건을 만족해야 한다.

1. Mutual Exclusion (상호 배제)
한 스레드가 임계 영역에서 작업하고 있을 때, 다른 스레드가 Entry Section을 지나 임계 영역에서 작업을 할 수 없다.

2. Progress
Entry Section에서 대기하고 있는 스레드가,
임계 영역을 사용하고 있던 스레드가 작업을 끝내서
Exit Section을 지나는 즉시 임계 영역으로 들어가야 한다.

3. Bounded-Waiting
한 스레드가 무한루프 등으로 계속 Entry Section - Exit Section을 반복할 때, 다른 스레드가 이의 영향을 받지 않고 공평하게 임계 영역에 접근할 수 있어야 한다.

Lock

동기화를 할 수 있는 가장 기본적이고 완벽한 방법
Mutex를 사용하여 동기화를 제어한다.

한 스레드가 aquired lock을 지나 lock을 걸면,
해당 임계 영역은 locked state가 된다.

어떠한 스레드도 임계 영역에 접근하고 있지 않을 때,
해당 임계 영역은 unlocked state라고 한다.

여러 스레드가 동일한 aquired lock에 접근하면, 우선적으로 접근한 스레드를
queue에 저장하여 우선 접근한 스레드를 먼저 임계 영역에 접근하도록 해 준다.

Semaphore

세마포어는 counter이라는 변수가 존재한다.

wait() 함수는 counter을 1 감소시키는데,
그 전에 counter값이 0일 때 프로세스를 대기시킨다.

signal() 함수는 counter을 1 증가시킨다.

Binary-Semaphore

counter값이 초기에 1로 설정된 세마포어이다.

Mutex, Lock과 동작이 동일하다.

Busy-Waiting

lock 동작 시 while로 프로세스를 대기시키면,
할당받은 Time Slice를 의미없이 소비하게 된다.

Sleep (Block)

위를 방지하기 위해 해당 스레드를 아예 잠재워 버린다.
이 때 해당 스레드를 waiting queue에 넣고,
나중에 signal()이 호출될 때 큐의 스레드를 하나씩 빼서,
wakeup()시키게 된다.