[OS] Semaphore(세마포어) & Mutex(뮤텍스, Mutulal Exclusion)

2024.01.10 - [Computer Science/Operation System] - [OS] IPC(Inter Process Comunication) - 프로세스간 통신

[OS] IPC(Inter Process Comunication) - 프로세스간 통신

IPC 포스팅에 이어서 Semaphore, Mutex 관련해서 공부를 해보았다. IPC를 처음 공부할때 유형 중에 Semaphore가 있은지 몰랐고 아예 Semaphore와 Mutex는 관계가 없는 내용인줄 알았지만 그렇지 않았다. IPC와 같이 포스팅을 하려고했지만 생각보다 양도 많았기 때문에 정확히 이론을 찾아보고 이해하는게 맞을거 같아서 다시 진행한다.

# Deadlock(데드락)

일단 Semaphore와 Mutex를 이해하기전에 운영체제에서 발생하는 Deadlock에 대해서 선행으로 알고 있어야한다.

그렇다면 Deadlock은 어떤것일까?

※  Deadlock 운영체제 혹은 소프트웨어의 잘못된 자원 관리로 인하여 두개 이상의 Process 또는 Thread가 영원히 대기하는 상황 쉽게 설명하자면, A사람이 B사람을 기다리고 B사람이 A사람을 기다리고 있는 것이다. 영원히 서로를 기다리고 있다. 이를 교착상태라고 부른다.

 

Deadlock은 4가지 기준으로 정의하며 명제로 따지자면 4가지 모두를 만족하는 경우를 Deadlock이라고 부를 수 있다. 이중 하나도 부합하지 않다면 Deadlock이 아니다.

1. Mutual exclusion (상호배제) ➡️ Deadlock을 알아야 Mutex에 대해서 쉽게 이해할 수있다.
   • "한번에 하나씩" 이라는 생각으로 접근하면 이해하기 쉽다.
   • 자원 자체를 동시에 쓸수 없으며 한번에 하나의 프로세스만이 해당 자원을 사용
   • 교착상태의 원인중 하나인 이유는 공유자원을 사용하더라도 Process들은 독점적인 사용을 원하며, 독점적인 사용을 하는 중에는 다른 Process들이 본인도 독점적인 사용을 위해서 기다려야하기 때문➡️ Deadlock
   • Mutex를 만족한다는 것은 위의 규칙이 잘 지켜지는 것을 의미함
   • ex) 식당에 키가 있는 한개의 화장실이라고 생각하면 더 쉽게 이해가 가능한데, 화장실에서 한명 나오기 전까지 화장실을 사용하지 못하고 뒤에서 기다려야한다는 것이다. 
2. Hold and Wait (점유 상태 대기)
   • 자원 하나를 붙잡은 상태에서 또 다른 자원을 기다리는 것
   • 2개 이상의 자원을 동시에 사용해야하는데 이 자원을 순차적으로 받는 경우 발생
   • 점유 상태 대기가 발생하지 않으면 프로세스가 다른 자원을 갖고 있지 않기 때문에 순환성대기가 발생 불가
   • 여러 자원이 필요하면 atomically하게 주거나 자원을 할당받으면 다른 자원을 반납하는 형식으로 Deadlock을 해결
3. No Preemition(선점 불가) ➡️ CPU 스케듈링의 선점형
   • 다른 Process의 자원을 뺏어올 수 없는 경우
4. Circular wait(순환성 대기)
   • 대기가 꼬리의 꼬리를 무는 사이클이 되는 상황  ex) 식사하는 철학자 문제
   • Deadlock을 해결하기 위해선 대칭성을 깨뜨리는 방법으로 열린 그래프로 만듬

사실 이번껀 말로 어떻게 쉽게 풀어서 이해하느냐에 따란 차이인데 사실 내가 이해한 방법이 맞는건가 싶다.
(위에는 내가 틀릴수도 있으니 보시는 분들에게 양해부탁드리며 틀린 내용은 댓글로 잡아주시면 감사하겠다.)

 

Deadlock을 해결하는 방법은 저 4가지 조건중에 하나만이라도 부합하지 않게 하면 된다는 것이다.

1. Prevention(예방): Deadlock을 아예 방지하는 것
   • 상호 배제 조건 제거(임계영역제거 ➡️제거는 안되고 줄여야함)
   • 점유 대기 조건 제거
   • 비선점 조건 제거
   • 순환대기 조건 제거
2. Avoidance(회피): Deadlock 발생 가능성을 확인하고 회피
   • 은행원 알고리즘 : Safe Sequence를 통해 자원을 나눠주게 된다. ➡️ 자원이 노는 일이 발생
   • Wait-Die : Timestamp를 기준으로 더 적은 쪽에 요청 ➡️ Startvation 발생 가능성이 있다.
   • Wound-Wait : Timestamp를 기준으로 더 큰 쪽에 요청 ➡️ Startvation 발생 가능성이 있다.
3. Detection(탐지)
   • Deadlock을 탐지
4. Recovery(복구)
   • Process 종료
   • 자원 회수

무한 반복의 교착 상태

이렇게 Deadlock, 교착상태와 Mutex에 대해서 알아보았다. Semaphore를 알아 보기전 알야한다. 그러면 다시 본론으로 돌아와서 Semaphore 부터 이야기를 해보자

# Semaphore(세마포어)

Semaphore, 세마포어의 사전적 의미 부터 알아보자. "수기 신호, 수기 신호로 알린다" 라는 의미를 갖고 있다. 처음에는 이 용어를 철도에서 썼다고 한다. 여러대의 기차가 하나의 철로를 공용하여 쓸 때, 오직 하나만 지나갈 수 있도록 하기 위해 양쪽 끝 선에서 flag를 표시하여 사고가 안나게 하였던 장치이다. OS에서는 프로세스 & 스레드 - 기차, 공유 자원 - 철도 라고 생각할수 있겠다. 

 

이제용어를 설명했으니 쉽게 이해할 수 있을거 같다. Semaphore, 즉 flag는 공유 자원에 Process와 Thread가 접근할때 제한되게 접근하는 표식이다.

 

 

Semaphore는 위에 설명한 Mutex에 기반한다. Mutex를 다시 설명하면 "하나당 하나씩"이다 라는 상호배제의 원리를 갖고 있다. 우리는 이를 원자적(atomic) 연산이라고 부른다. 근데 어이가 없게도 Mutex에 기반한 Semaphore가 Deadlock을 해결하기 위한 방법이라니.... Mutex는 교착상태의 4개중 하나인데 동작원리를 보게된다면 이해가 간다.

 

Semaphore와 Mutex의 동작차이를 보면 쉽게 이해 할 수있다. 또한 Semaphore라는 이름을 왜 Semaphore(깃발로 알림)으로 명명했는지도....!!

 

 

Mutext에 대한 설명은 위에서 간략하게 설명을 진행했지만 Mutext는 임계영역(Critical Section)이라는 것을 설정되어있으며 이는 Process나 Thread가 동시에 접근해서는 안되는 영역이다. 그래서 이를 방지하기 위해 lock/unlock의 을 사용하게 되는데 lock은 임계 구역에 들어갈 권한을 얻는 것이고 unlock은 임계 구역을 다 사용했다는 것을 알리는 것이다. 그렇다면 용어상 문맥에도 lock과 unlock을 할려면 key가 있어야하지 않을까? Mutex는 lock/unlock 매커니즘으로 동작을 하게된다.

Semaphore도 위에서 말한 Mutex를 늘린것 이지만 lock/unlock 연산 기반이 아닌 counting기반으로 동작을 하게 된다. 똑같이 임계영역을 공유한다. 연산 방식은 아래와 같다.

• Wait연산: 자원을 사용하면 숫자를 빼는 연산
• Signal연산: 자원 사용후 반납하면서 숫자를 더하는 연산 

결국은 Process와 Thread를 공통으로 관리하는 Count변수를 두고 Mutex를 달성하게 된다. 공유자원에 최대 자원으로 사용자가 접근할 수 있도록하고 세마포어의 값을 확인하고 변경할 수 있게된다. Mutex에서도 잠깐 업급했지만 Semaphore는 화장실이 많은 식당이라고 생각하며 key로 관리되는 것이 아닌 count라는 화장실 사용내역 전광판으로 구현되어있다. 그래서 semaphore count가 0이면 임계 영역에서 자원을 활용하고 있다는 것이다. 즉, 화장실 풀방이라는 얘기.

 

 

# Semaphore, Mutex 그래서 뭐가 다른데?

후... 일단 Semaphore와 Mutex를 어느 수준으로 이해하기는 했다. 각각의 연산 방식에 대해서 살펴보았고, 어떤 차이인지도 알아보았다. 근데 찾아보면서 의문점이 들었다. 그래서, Semaphore는 그냥 Mutex늘린거 아닌가?

 

사실 이렇게 이야기하는것도 틀린 말은 아니다. Samaphore는 count가 최대 1이라면 Mutex가 될수 있다. 하지만, Mutex는 Semaphore가 될 수 없다. Mutex는 동기화 대상이 하나일때 사용되기 때문이다.

 

또한 깊게 들어가면 Semaphore에는 priority inversion이 있기 때문에 사실상 다른 개념이긴 하다. 좋은 예시를 찾았는데 '나'라는 공유 자원으로 유튜브를 보고 있었지만, 전화가 울릴때에는 나는 전화를 먼저 받는다.

이렇듯 전화를 받는게 유튜브를 보는 것보다 먼저 우선순위가 있다는 것이다. 이는 priority inversion이 있는 Semaphore에서 그렇게 동작을 하게되고 Mutex는 key를 쥐고 꼼짝도 하지 않을 것이다. 

 

 

일단, 나조차도 작성하면서 헷갈린다. Mutex라는 말은 "상호배제"라는 뜻에서 Binary Semaphore는 Mutex가 될 수 있지만 Mutex자체의 구현으로 본다면 Binary Semaphore는 태생부터 달라서 똑같지 않다는건가.......

 

여러글에서는 같지 않은 이유를 설명한거 같다. 매커니즘 자체가 달라서 Semaphore랑 Mutex가 다르다는 이유는 뭐 매커니즘 자체가 달라서 라는 말도 있다. 해석을 어떻게 하냐에 따라 다른거 같다.
(lock/unlock 매커니즘 사용하는걸 뮤텍스 말고 다른말로 지어주시는게...)

아무튼 두가지 모두 임계영역(Critical Section)에서 다루어진다. 그 이유는 Race Condition을 발생을 방지하기 위함이다. 이는 임계영역에 동시에 적븝이 되서 값이 오염되거나 동일한 데이터의 일관성이 깨지는 현상을 의미한다.

 

#결론....?

이번 세마포어와 뮤텍스관련해서 래퍼런스를 찾아보는 작업은 생각보다 힘들었다. 꼬리에 꼬리를 무는 질문을 나에게 던졌더니 결과가 너무 다양했고 뭔가 명제?를 잘해야 이야기를 할 수있었다. Deadlock은 OS 자체에서 아주 큰 문제 이다. 하지만 Race Condition 조차 그렇다. Mutex를 하면 racecondition을 방지할 수 있지만, Deadlock의 4가지 조건중에 하나이다.

이것말고도 OS는 여러가지 연결고리가 많다. IPC에도 세마포어가 포함되어있다. 최근이며 실용주의적 학문이라 그런지 뭔가 공부하다보면 정리되있지 않거나 번역이 잘못된 부분을 종종 찾곤한다. 그래서 최대한 영어로 작성하려고한다. 용어가 전달해주는 의미 자체가 다르니깐

 

아래에는 레퍼런스를 첨부한다. 내가 틀렸을수도 있으니...!!

 

#레퍼런스

https://blog.naver.com/luexr/223174354766

뮤텍스(Mutex)와 세마포어(Semaphore) 이해

 

https://incheol-jung.gitbook.io/docs/q-and-a/computer-science/undefined-1

뮤텍스와 세마포어 - Incheol's TECH BLOG

 

https://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html

세마포어(Semaphore) & 뮤텍스(Mutex) | 👨🏻‍💻 Tech Interview

https://stackoverflow.com/questions/42720131/multiple-locks-with-mutex-and-the-possibility-of-a-deadlock

Multiple locks with mutex and the possibility of a deadlock

https://libertegrace.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Semaphore%EC%99%80-deadlock-starvation

[운영체제] Semaphore와 deadlock, starvation

https://heeonii.tistory.com/14

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

https://www.geeksforgeeks.org/mutex-vs-semaphore/

Mutex vs Semaphore - GeeksforGeeks