세마포어(Semaphore)란? 뮤텍스(Mutex)란? 교착 상태(deadlock)란?

안드로이드 개발을 하면서 동시성 프로그래밍을 한다면 코루틴을 주로 사용하기 때문에 제목의 2가지 개념은 직접 사용할 일이 없지만, 알아둬서 나쁜 개발 지식은 없다고 생각하기 때문에 포스팅한다.

먼저 뮤텍스와 세마포어 모두 코틀린에서 제공하는, 또는 코틀린만이 제공하는 특별한 개념은 아니다. 2가지는 동시성 프로그래밍 시 사용할 수 있는 동기화 기법들이라는 걸 짚어두고 간다.

 

먼저 세마포어부터 알아본다. 위키백과에서 설명하는 세마포어는 아래와 같다.

 

https://ko.wikipedia.org/wiki/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4

세마포어 - 위키백과, 우리 모두의 백과사전

세마포어는 에츠허르 데이크스트라가 고안한, 2개의 원자적 함수로 조작되는 정수 변수로서 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 쓰인다. 이는 철학자들의 만찬 문제의 고전적 해법이지만 모든 교착 상태를 해결하지는 못한다

 

https://en.wikipedia.org/wiki/Semaphore_(programming) 

Semaphore (programming) - Wikipedia

컴퓨터 과학에서 세마포어는 다중 쓰레드가 공통 리소스에 대한 접근을 제어하고 멀티태스킹 OS와 같은 동시 시스템에서 중요한 섹션 문제를 방지하는 데 사용되는 변수 또는 추상 데이터 타입이다. 세마포어는 동기화 프리미티브(synchronization primitive)의 한 유형이다...(중략)...실제 시스템에서 쓰이는 세마포어를 생각하는 유용한 방법은 사용 가능한 특정 리소스의 단위 수에 대한 레코드로, 해당 레코드를 안전하게 조정(즉, 경합 상태를 피하기 위해)하는 작업과 결합하는 것이다. 획득하거나 자유로워지고 필요한 경우 자원 단위가 사용 가능해질 때까지 기다린다. 세마포어는 deadlock을 방지하는 데 유용한 도구다. 그러나 이걸 쓴다고 해서 프로그램이 이러한 문제로부터 자유롭다는 보장은 없다. 임의의 자원 수를 허용하는 세마포어를 카운팅 세마포어라고 하며 값 0과 1(또는 잠금 / 잠금 해제, 사용 불가능 / 사용 가능)으로 제한되는 세마포어는 바이너리 세마포어라고 하며 잠금을 구현하는 데 사용된다. 세마포어 개념은 네덜란드 컴퓨터 과학자 에츠허르 데이크스트라가 1962년 또는 1963년에 데이크스트라와 그의 팀이 Electrologica X8용 OS를 개발할 때 발명했다. 이 시스템은 다중 프로그래밍 시스템으로 알려지게 되었다
도서관에 한 번에 1명의 학생이 사용할 수 있는 10개의 학습실이 있다고 가정한다. 학습실을 사용하려는 학생은 데스크에 방을 요청해야 한다. 빈 방이 없으면 학생들은 누군가 방을 내줄 때까지 책상에서 기다린다. 학생이 방 사용을 마치면 책상으로 돌아가서 한 방이 비어 있음을 표시해야 한다. 가장 간단한 구현에서 데스크의 직원은 사용 가능한 방의 개수만 알고 있으며 모든 학생이 등록한 동안 실제로 방을 사용하고 완료되면 반납하는 경우에만 올바르게 알고 있다. 학생이 방을 요청하면 직원은 이 숫자(사용 가능한 방의 개수일 것)를 줄인다. 방을 비우면 이 숫자를 늘린다. 방은 원하는 기간만큼 쓸 수 있으므로 미리 예약할 수 없다. 이 시나리오에서 데스크 카운터 홀더는 카운팅 세마포어를 나타낸다. 이 시나리오에서 세마포어의 초기값은 모든 방이 비어있는 10이다. 학생이 방을 요청하면 접근 권한이 부여되고 세마포어의 값이 9로 바뀐다. 다음 학생들이 오면 8, 7로 계속 떨어진다. 누군가 방을 요청하고 세마포어의 현재 값이 0이면 방이 비워질 때까지(카운터가 0에서 증가할 때까지) 기다려야 한다. 방 중 하나가 해제됐지만 대기 중인 학생이 여럿일 경우, 방을 차지할 사람을 선택할 때 FIFO 또는 무작위 선택 등의 방법을 쓸 수 있다. 물론 학생은 실제로 방을 나간 후에 점원에게 방을 비운다고 알려야 한다
리소스 풀에 대한 접근을 제어할 때 쓰이는 경우, 세마포어는 사용 가능한 리소스 수만 추적한다. 어떤 리소스가 사용 가능한지 추적하지 않는다. 특정 무료 리소스를 선택하려면 다른 매커니즘(더 많은 세마포어 포함)이 필요할 수 있다. 이 패러다임은 세마포어 카운트가 다양한 작업에 대한 유용한 트리거 역할을 할 수 있기 때문에 특히 강력하다...(중략)...프로토콜의 성공을 위해선 앱이 프로토콜을 올바르게 따라야 한다. 단일 프로세스가 오작동하는 경우에도 공정성과 안정성이 손상될 수 있다...(중략)

 

https://www.baeldung.com/cs/semaphore

세마포어는 여러 프로세스 간에 공유되는 정수 변수다. 세마포어를 쓰는 주요 목적은 동시 환경에서 공통 리소스에 대한 프로세스 동기화 및 접근 제어다. 세마포어의 초기값은 당면한 문제에 따라 다르다. 일반적으로 사용 가능한 리소스 수를 초기값으로 쓴다...(중략)...세마포어에는 분할할 수 없는 2가지 (원자적) 작업인 wait, signal이 있다. 이런 작업은 경우에 따라 P와 V, 또는 일부 컨텍스트에서 down과 up이라고도 한다. wait 함수는 0보다 크면 감소한다(할당 가능한 리소스가 있음). 이미 0이면(할당 가능한 리소스 없음) 호출 프로세스는 휴면 상태가 된다

signal 함수는 리소스를 기다리는 다른 프로세스가 없으면 S를 증가시키는 연산을 수행한다. 그렇지 않으면 값을 증가하는 대신 대기 중인 프로세스가 OS 스케줄러에 의해 깨어나도록 선택된다. 결과적으로 해당 프로세스가 리소스를 제어한다

세마포어는 2가지 타입이 있다
- 바이너리 세마포어
- 카운팅 세마포어

바이너리 세마포어는 0 또는 1의 두 가지 정수값만 가질 수 있다. 구현이 더 간단하고 상호 배제를 제공한다. 크리티컬 섹션 문제를 해결하기 위해 바이너리 세마포어를 쓸 수 있다. 누군가는 바이너리 세마포어를 뮤텍스와 혼동할 수 있다. 서로 바꿔서 쓸 수 있다는 일반적인 오해가 있다. 그러나 실제로 세마포어는 신호(signaling) 메커니즘인 반면 뮤텍스는 잠금(locking) 메커니즘이다. 따라서 바이너리 세마포어가 뮤텍스가 아님을 알아야 한다
카운팅 세마포어는 무제한 도메인(unrestricted domain)에 걸쳐 범위를 지정할 수 있는 정수값이다. 리소스 할당 같은 동기화 문제를 해결하는 데 사용할 수 있다...(중략)

 

https://www.geeksforgeeks.org/semaphores-in-process-synchronization/

Semaphores in Process Synchronization - GeeksforGeeks

세마포어는 컴퓨터 시스템에서 여러 프로세스의 활동을 조정하는 데 사용되는 동기화 메커니즘이다. 상호 배제를 시행하고 경합 상태를 피하며 프로세스 간 동기화 구현에 사용된다. 세마포어는 대기(P)와 신호(V)의 2가지 작업을 제공한다. 대기 연산은 세마포어의 값을 감소시키고 신호 연산은 증가시킨다. 세마포어의 값이 0이면 대기 작업을 수행하는 모든 프로세스는 다른 프로세스가 신호 작업을 수행할 때까지 차단된다. 세마포어는 한 번에 하나의 프로세스에서만 실행돼야 하는 코드 영역인 크리티컬 섹션을 구현하는 데 사용된다. 프로세스는 세마포어를 써서 공유 메모리 또는 I/O 장치 같은 공유 리소스에 대한 접근을 조정할 수 있다...(중략)

 

세마포어에 대해 정리하면 아래와 같다.

 

• 세마포어는 바이너리 세마포어, 카운팅 세마포어의 2가지가 존재한다
• 세마포어는 신호 메커니즘이고, 뮤텍스는 잠금 메커니즘이다
• 바이너리 세마포어는 0 또는 1만 가질 수 있는 세마포어다. 카운팅 세마포어에 비해 구현이 더 간단하고 상호 배제를 제공한다
• 카운팅 세마포어는 공유 리소스에 대한 동시 접근을 제한할 때 사용된다. 세마포어의 값이 제한되지 않은 도메인(=양의 정수값)에 걸쳐 범위를 갖기 때문에 1부터 수천, 수백만에 이르는 범위를 가질 수 있다. 카운팅 세마포어의 값이 1이면 상호 배제가 되어 한 번에 1개의 작업만 수행할 수 있고, 10이면 최대 10개의 작업을 동시에 수행할 수 있다

 

이 때 잠금(lock)이라는 말이 자주 나오는데, 잠금에 대한 내용은 아래와 같다.

 

https://ko.wikipedia.org/wiki/%EB%9D%BD_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99) 

락 (컴퓨터 과학) - 위키백과, 우리 모두의 백과사전

컴퓨터 과학에서 lock 또는 mutex(상호 배제)는 여러 쓰레드를 실행하는 환경에서 자원에 대한 접근에 제한을 강제하기 위한 동기화 매커니즘이다. 잠금이라고도 한다. lock은 상호 배제 동시성 제어 정책을 강제하기 위해 사용된다. 일반적으로 락은 일치 데이터에 접근하기 전에 락을 획득함으로써 각 쓰레드가 협업하는 advisory lock이다. 또 일부 시스템들은 잠금된 자원에 대한 비인가 접근을 시도하면 예외를 강제하는 mandatory lock을 구현한다. 가장 단순한 락의 유형은 바이너리 세마포어다. 잠금된 데이터로의 배타적 접근을 제공한다...(중략)

 

https://en.wikipedia.org/wiki/Lock_(computer_science) 

Lock (computer science) - Wikipedia

잠금 또는 뮤텍스(상호 배제에서)는 실행 쓰레드가 많을 때 리소스에 대한 접근을 제한하는 메커니즘이다. 잠금은 상호 배제 동시성 제어 정책을 사용하도록 설계됐으며...(중략)...일반적으로 잠금은 각 쓰레드가 해당 데이터에 접근하기 전에 잠금을 획득해서 협력하는 권고 잠금이다. 잠긴 리소스에 대한 무단 접근을 시도하면 접근을 시도하는 엔터티에서 예외가 발생한다. 가장 간단한 유형의 잠금은 바이너리 세마포어다. 잠긴 데이터에 대한 독점 접근을 제공한다...(중략)...잠금에 대한 3가지 개념을 이해해야 한다

- lock overhead : 잠금에 할당된 메모리 공간, 잠금을 초기화하고 파괴하는 CPU 시간, 잠금을 획득하거나 해제하는 시간 같이 잠금을 쓰기 위한 추가 리소스. 프로그램이 사용하는 잠금이 많을수록 사용과 관련된 오버헤드가 커진다
- lock contention : 이것은 한 프로세스나 쓰레드가 다른 프로세스나 쓰레드가 가진 잠금을 얻으려고 시도할 때마다 발생한다. 사용 가능한 잠금이 세분화될수록 하나의 프로세스 / 쓰레드가 다른 프로세스 / 쓰레드가 가진 잠금을 요청할 가능성이 줄어든다
- deadlock : 둘 이상의 태스크 각각이 다른 태스크가 갖고 있는 잠금을 기다리는 상황이다. 어떤 조치를 취하지 않는 한 두 작업은 영원히 대기할 것이다

잠금의 중요한 속성은 세분성이다. 세분성은 잠금이 보호하는 데이터량의 척도다. 일반적으로 거친 세분성(각각 큰 데이터 세그먼트를 보호하는 적은 수의 잠금)을 선택하면 단일 프로세스가 보호된 데이터에 접근할 때 잠금 오버헤드가 줄어들지만 여러 프로세스가 동시 실행될 때 성능이 저하된다. 잠금 경합(lock contention)이 증가했기 때문이다. 잠금이 거칠수록 잠금이 관련 없는 프로세스의 진행을 중지할 가능성이 높아진다. 반대로 미세한 세분성(각각 상당히 적은 양의 데이터를 보호하는 많은 수의 잠금)을 사용하면 잠금 자체의 오버헤드가 증가하지만 잠금 경합은 줄어든다...(중략)

 

https://www.techopedia.com/definition/1841/lock

Lock

잠금은 컴퓨팅 환경 안에서 특정 리소스에 대한 무제한 접근을 방지하기 위해 제한을 걸어서 서로 다른 처리 쓰레드를 동기화할 때 사용하는 메커니즘이다. 동시 통제 정책을 써서 접근을 정리하는 방식이다. 즉 쓰레드가 쿼리하는 데이터에 대한 접근 권한이 부여되기 전에 잠금을 획득하기 위해 다른 쓰레드와 협력해 작동한다.

 

https://web.mit.edu/6.005/www/fa15/classes/23-locks/

Reading 23: Locks and Synchronization

잠금은 하나의 동기화 테크닉이다. 한 번에 최대 하나의 쓰레드만 소유할 수 있게 하는 추상화다. 잠금을 유지하는 것은 한 쓰레드가 다른 쓰레드에게 "이걸 바꾸고 있으니 지금 만지지 마" 라고 말하는 방법이다. 잠금에는 2가지 작업이 있다

- acquire : 쓰레드가 잠금의 소유권을 가질 수 있게 한다. 쓰레드가 다른 쓰레드가 현재 갖고 있는 잠금을 획득하려고 하면 다른 쓰레드가 잠금을 해제할 때까지 차단된다. 이 시점에서 잠금을 획득하려는 다른 쓰레드와 경쟁하게 된다. 최대 하나의 쓰레드가 한 번에 잠금을 가질 수 있다
- release : 잠금 소유권을 포기하고 다른 쓰레드가 소유권을 가질 수 있게 한다

공유 메모리 동시성의 첫 번째 예시는 현금 인출기가 있는 은행이다. 해당 예제의 다이어그램이 밑에 있다

은행에는 여러 현금 인출기가 있고 모두 메모리에서 같은 계정 객체를 읽고 쓸 수 있다. 계정 잔액에 대한 동시 읽기, 쓰기 간의 조정이 없으면 잘못된 것이다

잠금으로 이 문제를 해결하기 위해 각 은행 계좌를 보호하는 잠금을 추가할 수 있다. 이제 현금 인출기는 계정 잔액에 접근하거나 업데이트하기 전에 먼저 해당 계정에 대한 잠금을 획득해야 한다. 위 다이어그램에서 A, B는 모두 account 1에 접근하려고 한다. B가 먼저 잠금을 얻었다고 가정한다. 그 다음 A는 B가 완료하고 잠금을 해제할 때까지 기다려야 한다. 이렇게 하면 A, B가 동기화되지만 다른 현금 인출기 C는 다른 계정에서 독립적으로 실행될 수 있다. 해당 계정이 다른 잠금으로 보호되기 때문이다

 

잠금에 대해 정리하면 아래와 같다.

 

• 잠금은 동시성 제어를 위한 동기화 메커니즘이다. 이걸 쓰면 여러 쓰레드가 공유 리소스에 접근을 시도할 때 한 번에 1개의 쓰레드만 공유 리소스에 접근하게 할 수 있다
• 세마포어는 잠금 개념을 확장해서 동시 수행 가능한 작업의 최대 개수를 지정할 수 있다
• 잠금은 acquire(쓰레드가 공유 리소스에 접근하기 위해 접근 권한 요청), release(쓰레드가 공유 리소스를 사용한 후 잠금을 해제) 2가지 작업이 있다

 

이제 뮤텍스에 대해 알아본다. 뮤텍스는 잠금과는 다른 개념이지만, 잠금은 뮤텍스를 포함하는 더 일반적인 동시성 제어 메커니즘이다. 그래서 영문 위키백과에 뮤텍스를 검색하면 잠금(Lock) 문서로 이동하고 한글 위키백과는 아예 잠금과 뮤텍스를 같은 문서에 작성해놨다. 그래서 뮤텍스 mutual exclusion(상호 배제) 문서에서 넘어온다고 써 있으므로 상호 배제에 대해 알아본다.

 

https://en.wikipedia.org/wiki/Mutual_exclusion

Mutual exclusion - Wikipedia

상호 배제는 경합 상태를 방지할 목적으로 만들어진 동시성 제어의 속성이다. 동시 실행 쓰레드가 이미 해당 임계 영역에 접근하고 있는 동안 하나의 실행 쓰레드가 임계 영역에 절대 들어가지 않는 것이 요구사항이며, 이는 실행 쓰레드가 공유 리소스 또는 공유 메모리에 접근하는 시간 간격을 나타낸다. 공유 리소스는 둘 이상의 동시 쓰레드가 수정하려고 시도하는 데이터 객체다. 두 개의 동시 읽기 작업은 허용되지만 두 개의 동시 쓰기 작업 또는 하나의 읽기 and 하나의 쓰기는 데이터 불일치로 이어지기 때문에 허용되지 않는다. 상호 배제 알고리즘은 프로세스가 이미 데이터 객체(임계 영역)에 쓰기 작업을 수행 중인 경우, 첫 번째 프로세스가 데이터 객체(임계 영역)에 대한 쓰기를 완료할 때까지 다른 프로세스 / 쓰레드가 같은 객체에 접근 / 수정할 수 없게 한다. 상호 배제의 요구사항은 에츠허르 데이크스트라가 1965년 그의 논문 "Solution of a problem in concurrent programming control"에서 처음 식별하고 해결했으며...(중략)...상호 배제란 용어는 메모리 주소가 하나 이상의 다른 쓰레드에 의해 조작되거나 읽히는 동안 한 쓰레드에 의해 메모리 주소를 동시에 쓰는 것과 관련해 사용된다
상호 배제가 다루는 문제는 리소스 공유의 문제다. 각 프로세스가 작업을 수행하는 동안 해당 리소스를 제어해야 할 때 소프트웨어 시스템이 공유 리소스에 대한 여러 프로세스의 접근을 어떻게 제어할 수 있는가? 이에 대한 상호 배제 솔루션은 프로세스가 임계 영역이라는 특정 코드 세그먼트에 있는 동안에만 공유 리소스를 사용할 수 있게 하낟. 리소스가 사용되는 프로그램 부분의 각 상호 실행을 제어해서 공유 리소스에 대한 접근을 제어한다...(중략)

 

https://www.techopedia.com/definition/25629/mutual-exclusion-mutex

Mutual Exclusion

상호 배제는 공유 리소스에 대한 동시 접근을 방지하는 프로그램 객체다. 이 개념은 프로세스 또는 쓰레드가 공유 리소스에 접근하는 코드 조각인 크리티컬 섹션을 사용한 동시 프로그래밍에 사용된다. 한 번에 하나의 쓰레드만 뮤텍스를 소유하므로 프로그램이 시작될 때 고유한 이름을 가진 뮤텍스가 생성된다. 쓰레드가 리소스를 갖고 있을 때 리소스에 대한 동시 접근을 방지하기 위해 다른 쓰레드의 뮤텍스를 잠가야 한다. 리소스를 해제하면 쓰레드가 뮤텍스를 잠금 해제한다

 

상호 배제에 대해선 다른 곳에서도 비슷하게 말하기 때문에 정리하면 아래와 같다.

 

• 상호 배제는 동시성 프로그래밍에서 여러 프로세스 / 쓰레드가 공유 리소스에 동시 접근하는 걸 막기 위한 개념이다
• 상호 배제를 통해 한 번에 1개의 쓰레드만 공유 리소스를 사용하거나 임계 영역(critical section)에 들어갈 수 있다
• 상호 배제를 활용하면 공유 리소스를 동시에 수정하거나 읽어서 발생할 수 있는 동시성 문제를 방지할 수 있다

 

마지막으로 위에서 말한 잠금의 3가지 개념 중 deadlock에 대해 확인한다.

 

https://en.wikipedia.org/wiki/Deadlock

Deadlock - Wikipedia

교착 상태(deadlock)는 자신을 포함한 다른 구성원이 메시지를 보내거나 일반적으로 잠금 해제 같은 조치를 취하기를 기다리기 때문에 일부 엔터티 그룹의 구성원이 진행할 수 없는 상황이다. 교착 상태는 멀티프로세싱 시스템, 병렬 컴퓨팅, 분산 시스템에서 공통적인 문제다. 이런 컨텍스트에서 시스템은 종종 공유 리소스를 조정하고 프로세스 동기화를 구현하기 위해 소프트웨어 또는 하드웨어 잠금을 사용하기 때문이다. OS에서 교착 상태는 프로세스나 쓰레드가 대기 상태에 들어갈 때 발생한다. 요청한 시스템 자원이 다른 대기 프로세스에 의해 보유되고 있고, 대기 중인 다른 프로세스가 보유하고 있는 다른 자원을 기다리고 있기 때문이다. 프로세스가 요청한 자원이 대기 중인 다른 프로세스에 의해 쓰이고 있기 때문에 프로세스가 무기한 상태를 변경할 수 없는 경우, 시스템이 교착 상태에 있다고 한다
리소스의 교착 상태는 시스템에서 아래 조건이 모두 동시에 발생할 때에만 발생할 수 있다

- 상호 배제 : 최소 하나의 리소스가 비공유 모드로 유지되어야 한다. 즉 한 번에 하나의 프로세스만 리소스를 사용할 수 있다. 그렇지 않으면 필요할 때 프로세스가 리소스를 사용하는 걸 막을 수 없다. 주어진 시간에 하나의 프로세스만 리소스를 사용할 수 있다
- 보유 및 대기(Hold and wait) or 자원 보유 : 프로세스가 현재 최소한 하나의 자원을 갖고 있으며 다른 프로세스가 갖고 있는 추가 자원을 요청하고 있다
- 비선점 : 리소스를 보유하고 있는 프로세스에 의해서만 자발적으로 리소스를 해제할 수 있다
- 순환 대기 : 각 프로세스는 다른 프로세스가 갖고 있는 리소스를 기다리고 있어야 하며 차례로 첫 번째 프로세스가 리소스를 해제하길 기다린다

이 4가지 조건은 Edward G. Coffman의 1971년 기사에서 처음 설명된 Coffman 조건으로 알려져 있다. 이런 조건은 단일 인스턴스 리소스 시스템에서 교착 상태를 생성하기 충분하지만 여러 인스턴스의 리소스가 있는 시스템에서 교착 상태가 발생할 가능성만 나타낸다

 

https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

Introduction of Deadlock in Operating System - GeeksforGeeks

교착 상태는 각 프로세스가 리소스를 갖고 있는 상태에서 다른 프로세스가 가진 다른 리소스를 기다리고 있기 때문에 일련의 프로세스가 차단되는 상황이다. 두 열차가 같은 선로에서 서로를 향해 다가오고 있고 선로가 하나뿐일 때 서로 앞에 있으면 열차가 움직일 수 없는 경우를 예로 든다. 일부 리소스를 갖고 있고 다른 프로세스가 가진 리소스를 기다리는 둘 이상의 프로세스가 있을 때 OS에서 유사한 상황이 발생한다...(중략)

 

교착 상태(deadlock)에 대해 정리하면 아래와 같다.

 

• 교착 상태는 둘 이상의 프로세스 / 쓰레드가 각각 리소스를 가진 상태에서 다른 프로세스 / 쓰레드가 갖고 있는 리소스를 요청해서 발생하는 상황이다
• 교착 상태가 발생하면 각 프로세스 / 쓰레드는 다른 프로세스 / 쓰레드가 리소스를 해제할 때까지 계속 기다리게 되고, 이로 인해 전체 시스템이 차단되어 성능 저하 또는 프로그램 정지 같은 문제가 발생할 수 있다
• 교착 상태는 상호 배제, 보유 및 대기, 비선점, 순환 대기의 4가지 조건이 동시에 만족될 때 발생한다