상호 배제 / 동기화 (Mutex, Semaphore, Monitor)

동기화(synchronization)를 위한 상호 배제(Mutual Exclusion)

 앞서 얘기했듯 공유자원에 대해 다수의 프로세스 혹은 스레드가 접근할 때 경쟁조건이 발생하여 의도하지 않은 동작이 발생할 수 있다. 따라서 프로세스나 스레드를 동기화 해야한다. 이때, 동기화란 공유자원에 동시에 접근하지 못하도록 접근 순서를 제어하는 방법을 의미한다.

프로세스/스레드 간 동기화는 일반적으로 상호배제를 통해 구현할 수 있다.

 

상호배제(Mutual Exclusion)란?

 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계구역으로 불리는 코드 영역에 의해 구현된다.

 하나의 프로세스가 순차적으로 파일을 읽는 작업을 하는 도중에 다른 프로세스가 파일의 내용을 변경해 버리면 읽어오는 값이 예상과 다를 수 있기에 이러한 상황을 제어하는 동기화 작업이 필요한 것이다.

 

 즉, A(프로세스)가 화장실 열쇠를 가지고 화장실(공유 자원)에 걸린 잠금(임계영역)을 풀고 이용 중이라면, 화장실을 이용하려던 B(프로세스)는 화장실 열쇠가 반납될 때까지 잠금을 풀지도 못한다. B는 대기하다 추후에 A가 화장실 열쇠를 반환하면 그제서야 잠금을 풀고 자원을 이용할 수 있게 된다.

상호배제의 조건

1. 두 프로세스는 동시에 공유자원에 진입할 수 없다.
2. 프로세스의 속도나 프로세서 수에 영향을 받지 않는다.
3. 공유자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
4. 프로세스가 공유자원을 사용하려고 너무 오래 기다려서는 안된다.

상호배제 여러가지 방법

상호 배제를 시키는 기본적인 방법은 Lock이다. 특정 프로세스/스레드가 공유자원에 접근 중일때는 다른 프로세스/스레드가 접근하지 못하도록 Lock을 걸어 해결한다.

 

1. 소프트웨어를 이용한 해결

• Dekker's 알고리즘 : 
• Peterson's 알고리즘 : 

※단점 : 속도가 느리고, 구현이 복잡하며, Busy waiting이 일어날 수 있는 가능성이 높음, 또한 Interrupt로 인해 Premumtiation될 확률이 높음

 

2. 하드웨어를 이용한 해결

• TestAndSet(TAS) : 

※단점 : 3개 이상의 프로세스/스레드가 하나의 공유자원을 사용하는 경우, Busy waiting이 일어날 수 있는 가능성이 높음.

 

3. OS를 이용한 해결

• Spinlock
• Mutex
• Semaphore
• Monitor

Spinlock

- 하나의 프로세스가 Lock을 소유하고 있다면, 그 Lock이 반환될 때까지 계속 확인하며 기다리는 기법

  임계영역에 진입이 불가능할때 Context Switching을 하지 않고 잠시 Loop를 돌면서 재시도를 하는 것을 말한다.

- Lock을 얻을 수 없다면 계속해서 Lock을 확인하며 얻을 때까지 기다린다. (Busy Waiting)

- 임계영역이 오랜 시간동안 Unlock되지 않으면 그동안 계속 CPU를 점유하고 있어 오버헤드가 존재한다.

- 상태가 Lock/Unlock만 존재하기에 한 번에 하나의 컴포넌트만 접근이 가능하며, Lock과 Unlock의 주체는 동일해야 한다.

- Context Switch가 일어나지 않기 때문에 멀피 프로세서 시스템에서만 사용 가능하다.

 

Mutex

- Mutual Exclusion의 약자로서 상호배제라고도 한다. 

- 상태가 Lock과 Unlock만 존재한다는 점은 Spinlock과 동일하지만, Spinlock이 권한을 획득하기까지 Busy Waiting상태를 유지하는 것에 비해 Mutex는 Sleep상태로 들어갔다 Wakeup되면 다시 권한 획득을 시도한다.

- Mutex의 경우 Locking 메커니즘으로 Lock을 걸은 프로세스/스레드만이 임계영역을 나갈 때 Lock을 해제할 수 있다.

- 시스템 전반의 성능에 영향을 주고 싶지 않고 길게 처리해야하는 작업인 경우에 주로 사용된다.

Semaphore

- 정수값으로 표현하는데, 이는 공유자원에 접근할 수 있는 프로세스/스레트의 최대 허용치이다.

- Spinlock과 목적은 동일하지만, Ready queue라는 공간에서 기다리면서 공유자원을 할당받는 방식이다.

- Semaphore의 종류

1. 바이너리 Semaphore : 임의의 변수가 0과 1 두 종류의 값만 갖는 경우, 상호배제, 동기화 목적으로 사용
2. 카운팅 Semaphore : 임의의 변수가 0이상의 정수값을 가질 수 있는 경우, 생산자, 소비자 문제를 해결

※ 생상자-소비자 문제 : 생산자가 생산하는 속도와 소비자가 소비하는 속도의 차이가 존재하는데, 일반적으로 생산되는 속도가 소비되는 속도보다 빠른 경우가 많아서 생산된 데이터를 바로 소비하지 못하게 된다. 이런 상황에서 발생되는 문제

Monitor

- 임계구역에 명시적으로 구현되었던 상호배제 로직을 추상화하고, 공유자원 접근에 대한 인터페이스만을 제공한다.

- 공유자원을 외부로부터 캡슐화하여 숨길 수 있다.

- 공유자원에 접근하고자 하는 프로세스/스레드는 모니터 안으로 들어가야 한다.

- Monitor는 Monitor queue에 작업을 순차적으로 쌓아두고, 한번에 한 프로세스/스레드만 임계영역에 접근할 수 있도록 한다. 즉, 한번에 하나의 프로세스만 모니터에서 활동할 수 있도록 보장한다. 

- Semaphore에 비해 고수준이며, 비교적 상호배제를 구현하기 쉽다.

Semaphore와 Mutex의 차이

- Semaphore는 Mutex가 될 수 있지만, Mutex는 Semaphore가 될 수 없다.

- Semaphore는 소유할 수 없으며, Mutex는 소유할 수 있고 소유주가 그에 대한 책임을 진다.

- Mutex의 경우 Mutex 를 소유하고있는 스레드가 이 Mutex를 해제할 수 있다. 하지만, Semaphore는 소유하지 않고 있는 스레드가 Semaphore를 해제할 수 있다.

- Semaphore는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재한다. 하지만, Mutex는 프로세스 범위를 가지고 프로그램이 종료될 때 자동으로 지워진다.

- Semaphore는 동기화 대상이 여러 개일 때, Mutex는 동기화 대상이 오로지 하나일 때 사용된다.

 

 

 

처음에 한번 보고는 비슷한 것들끼리 왜 모여서 이러고 있나 복잡해서 이해하기가 어려웠다. 하지만 임계구역과 경쟁상태부터 탄탄히 하고 오니까 이해가 쉬워졌다. 글로 이해가 어렵다면 밑에 영상부터 보고오자. 깔끔하게 잘 설명해주신다.https://www.youtube.com/watch?v=gTkvX2Awj6g

 

 

출처

https://velog.io/@woga1999/%EC%83%81%ED%98%B8-%EB%B0%B0%EC%A0%9C%EC%99%80-%EB%8F%99%EA%B8%B0%ED%99%94

상호 배제와 동기화

https://hudi.blog/race-condition-critical-section-mutual-exclusion/

경쟁상태, 임계영역의 개념과 동기화를 위한 여러 상호배제 기법 (mutex, semaphore, monitor)

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

[CS 기초 - 운영체제] 세마포어(Semaphore), 뮤텍스(Mutex), 스핀락(Spin lock)

https://sangcho.tistory.com/entry/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EB%8F%99%EA%B8%B0%ED%99%94%EB%B0%8F%EC%83%81%ED%98%B8%EB%B0%B0%EC%A0%9C#%EB%8F%99%EA%B8%B0%ED%99%94-1

프로세스 동기화 및 상호배제