동기화 문제를 해결하기 위해 상호배제를 달성하는 기법들이 스핀락, 세마포어, 뮤텍스이다.
스핀락(Spinlock)
- 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프를 돌면서 재시도하는 방식으로 구현된 락을 가리킨다.
- 권한을 획득하기 전까지는 CPU는 무의미한 코드를 수행하는 busy waiting 상태로 대기하고 있다가 접근 권한을 얻는다면 내부 코드를 수행하고 종료 후 권한을 해제한다.
- 스핀락은 상태가 오직 획득(Lock) / 해제(Unlock)만 존재하기에 한 번에 하나의 컴포넌트만 접근이 가능하며, 획득과 해제의 주체는 동일해야 한다.
- 운영체제의 스케줄링 지원을 받지 않기 때문에, 해당 스레드에 대한 문맥 교환(context switch)이 일어나지 않는다.
- 짧은 시간 안에 진입할 수 있는 경우 문맥 교환 비용이 들지 않으므로 효율을 높일 수 있지만 그 반대의 경우에는 다른 스레드에 cpu를 양보하지 않기 때문에 오히려 cpu 효율을 떨어뜨리게 된다.
- 스핀 락은 문맥 교환이 일어나지 않기 때문에 멀티 프로세서 시스템에서만 사용할 수 있다.
//스핀락 예시
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}세마포어(Semaphore)
- 세마포어는 음수가 아닌 정수 값을 가지고 스레드 간에 공유되는 변수다. 이 변수는 임계 구역 문제를 해결하고 동기화를 구현하는 데 사용된다.
- 세마포어는 signaling 메커니즘으로 락을 걸지 않은 스레드도 signal을 사용해 락을 해제할 수 있다.
- 세마포어는 자원의 개수를 의미하기도 한다. 자원의 개수에 따라 두 가지 유형이 있다.
- 이진 세마포어 (Binary semaphore)
0또는 1 값만 가질 수 있는 세마포어다.
임계 구역 문제를 해결하는데 사용하며 자원이 하나이기 때문에 뮤텍스로도 사용할 수 있다.- 개수 세마포어 (Counting semaphore)
도메인이 0이상인 임의의 정수값인 세마포어다.
여러개의 자원을 가질 수 있으며 제한된 자원을 가지고 액세스 작업을 할때 사용한다.
- 세마포어 연산
- wait(S) 연산 : 자원을 획득하는 연산
- signal(S) 연산 : 자원을 해제하는 연산
- 세마포어는 시스템에서 사용할 수 있는 리소스의 수로 초기화되며, wait() 함수를 호출하여 세마포어가 0보다 클 때마다 프로세스는 세마포어를 감소시키고 임계 구역에 들어갈 수 있게 된다.
세마포어가 0에 도달하면 다른 프로세스가 리소스를 해제하고 signal() 함수 호출로 세마포어를 증가시킬 때까지 프로세스가 차단된다.
세마포어(Semaphore) 구현방식
- busy-waiting 방식
자원이 없다면 while 루프 돌면서 기다리는 방식이다. (스핀락과 동일)
while 루프를 돌며 대기하기 때문에 busy-waiting이 발생한다.
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}- block-wakeup 방식
자원이 없다면 blocked 상태에서 기다리는 방법이다.
자원이 생기면 wakeup으로 block 상태인 프로세스를 깨우는 작업을 한다.
typedef struct
{
int value; /* semaphore */
struct process *list; /* process wait queue */
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0 ) { // 자원이 없다면 프로세스를 큐에 넣고 block
add this process to S->list;
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { // 자원이 0이하라면 block중인 프로세스가 있다는 의미
remove a process P from S->list; // 대기하고 있는 프로세스를 가져온다.
wakeup(P); // 가져온 프로세스를 깨운다.
}
}뮤텍스(Mutex)
- Mutex는 Mutual Exclusion의 약자로서 상호 배제라고도 한다.
- 뮤텍스는 상태가 오직 획득(Lock) / 해제(Unlock)만 존재한다는 점은 스핀락과 동일하다. 하지만 스핀락이 임계영역이 언락되어 권한을 획득하기까지 Busy Waiting 상태를 유지한다면, 뮤텍스는 Sleep 상태로 들어갔다 Wakeup 되면 다시 권한 획득을 시도한다.
- 뮤텍스는 Locking 메커니즘으로 락을 걸은 스레드만이 임계 영역을 나갈 때 락을 해제할 수 있다.
- 시스템 전반의 성능에 영향을 주고 싶지 않고 길게 처리해야하는 작업인 경우에 주로 사용된다. 주로 스레드 작업에서 많이 사용된다.
- 뮤텍스는 wait와 signal이라는 원자적 연산을 사용한다.
do { wait (mutex); // Critical section signal (mutex); // Remainder section } while (TRUE);
🙇 참고 사이트 🙇
https://yoongrammer.tistory.com/63 https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore-%EB%AE%A4%ED%85%8D%EC%8A%A4Mutex-%EC%8A%A4%ED%95%80%EB%9D%BDSpin-lock
