[OS] 세마포어와 뮤텍스 📌

🖐 개념 정리

 

공유 자원

• 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다
• 이는 공동으로 이용되는 자원이기 때문에 누가 언제 데이터를 쓰거나 읽느냐에 따라 결과가 달라질 수 있다

 

 

경쟁 조건 (race condition)

• 2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황
• 여러 프로세스/스레드가 동시에 같은 데이터를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
• 즉, 두 개 이상의 프로세스가 하나의 자원을 두고 서로 이용하려고 경쟁하는 상황이다

 

 

동기화 (synchronization)

• 여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것

 

 

임계 구역 (Critical Section)

• 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
• 멀티 프로세스나 멀티 스레드 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역이다
• 이는 공유 자원의 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역이기 떄문에 여러 프로세스가 동시에 접근하는 경우 잘못된 결과를 만들 수 있다
• 즉, 공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 집입해서 실행이 가능한 영역이다

💡 프로그래밍 시, 성능 향상을 위해서 임계 영역을 최소화하는 설계를 해야 한다!

 

---

🚨 교착 상태

• 서로 공유 자원을 놓아줄 생각 없이, 자원 요청만 무한정 대기하고 있는 상태
• 이는 임계 영역에서 발생할 수 있는 문제이다

 

교착 상태 발생 조건

• 교착 상태가 발생하려면 아래의 4가지 조건을 모두 만족해야만 한다
  1. 상호 배제
  2. 점유 대기
  3. 비선점
  4. 순환 대기
• 이 중에서 상호 배제 조건을 해결하기 위해 등장한 방법이 뮤텍스(Mutex)와 세마포어(Semaphore)이다

 

 

상호 배제 (Mutal Exclusion)

• 임계 구역을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며, 다른 프로세스가 현재 사용 중인 임계 구역에 대해 접근하려고 할 때 이를 금지하는 행위

 

---

🔒 뮤텍스 (Mutex)

• Mutual + Exclusion => Mutex
• 한 쓰레드 또는 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호 배제 기법
• 스레드들 간에서 공유가 배제되는 객체이다
• 여러 스레드를 실행하는 환경에서 자원에 대한 접근에 제한을 강제하기 위한 동기화 매커니즘이다
• Lock을 사용하여 임계 구역을 보호하고 경쟁 조건(race condition)을 예방한다
• 뮤텍스의 알고리즘으로는 *데커(Dekker) 알고리즘, 피터슨(Perterson) 알고리즘, 제과점(Bakery) 알고리즘 등이 있다

 

 

뮤텍스 작동 방식

mutex = 1;

void lock () {
    while (mutex == 1) {
    	  // 다른 프로세스/스레드가 lcok을 잡고있는 상태이므로 mutex값이 0이 될 때까지 대기
    }
    // mutex값이 0인 경우 즉, 아무도 lock을 잡고 있지 않으므로 임계 구역 진입 가능 상태
    // mutex값을 1로 바꾼다(lock을 잡음)
    mutex = 1;
}

void unlock() {
    // 임계 구역에서 나온 프로세스는 다른 프로세스가 접근할 수 있도록 락을 해제한다.
    mutex = 0;
}

1) lock

• 현재 임계 구역에 들어갈 수 있는 권한을 얻는다
• 만약 다른 프로세스/스레드가 lock을 잡고 있다면 lock을 놓아줄 때까지 대기한다

 

2) unlock

• 임계 구역을 모두 수행한 후 호출한다
• unlock을 호출하면 lock을 기다리던 다른 프로세스/스레드 들이 lock을 잡을 수 있다

 

 

뮤텍스의 실행 순서

1. Boolean 타입의 Lock 변수를 사용하여 자원에 대한 접근을 제한한다
2. 임계 영역의 자원에 접근하면 해당 스레드는 Lock을 걸고, 이 때 다른 스레드가 공유 자원에 접근하면 Blocking한 후 해당 스레드를 대기 큐로 보낸다
3. 공유 자원 사용을 마친 스레드는 Lock을 해제한다. 이 때 Lock 해제는 Lock을 건 스레드만 가능하다

 

 

 

스핀락 (SpinLock)

• 뮤텍스와 유사한 방법
• 이는 뮤텍스와 달리 대기 큐를 갖지 않으며, busy-waiting한다
• Mutex-nonblocking 모델이라고 볼 수 있다

💡 바쁜 대기 (busy-waiting)
- 상태 변화를 살펴보기 위해 반복문을 무한 실행하며 기다리는 것
- 이는 자원 낭비가 심하기 때문에 비효율적이다

 

 

스핀락을 사용하는 경우

• 스핀락은 busy-waiting 때문에 좋아보이지 않지만, 오히려 뮤텍스보다 좋은 상황이 있다
• 바로 멀티 환경이다
  • 코어가 하나인 경우에는 공회전을 계속 하느라 자원 낭비가 심하다
  • 그러나 CPU 코어가 여러 개인 경우, 빈 코어에서 기다리다가 Lock이 풀리면 바로 진입할 수 있기 때문이다
• 즉, Context Switching 시간을 아낄 수 있다
• 따라서 스핀락은 멀티 코어 환경이나 임계 영역 처리 시간이 context switching 시간보다 짧은 경우에 사용된다

 

 

 

📢 세마포어 (Semaphore)

• Signaling mechanism
• 현재 공유자원에 접근할 수 있는 쓰레드, 프로세스의 수를 나타내는 값을 두어 상호 배제를 달성하는 기법
• 멀티프로그래밍 환경에서 다수의 프로세스나 스레드의 여러 개의 공유 자원에 대한 접근을 제한하기 위해 사용되는 동기화 기법이다
• 세마포어는 변수를 통해 접근 가능한 스레드를 제한한다
• 뮤텍스는 1개의 스레드만 자원을 사용할 수 있었으나, 세마포어는 변수의 수만큼 공유 자원에 접근할 수 있다
• 세마포어에서 잠금이 해제되길 기다리는 프로세스는 세마포어 큐에 저장되어 있다가, 신호를 받으면 큐에서 나와 임계 구역에 진입한다
• 즉, busy-wating을 하는 프로세스가 없다!
• 그러나 세마포어는 잘못 사용하는 경우 임계 구역이 보호받지 못한다
  • 프로세스가 세마포어를 사용하지 않고 바로 임계 구역에 들어간 경우
  •  P()를 두 번 사용하여 wake_up 신호(임계 구역 진입 가능 신호)가 발생하지 ㅇ낳은 경우
  • P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우
• 그러므로 P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고, 완전히 실행되게 해야 한다

 

 

세마포어 작동 방식

procedure P(S)  
    S := S-1  --> s값 감소
    while S>0 do wait  --> S 값이 0보다 작으면 기다려야 함(wait)
end P

// --- 임계 구역 ---

procedure V(S)
    S := S+1   --> S값 증가
end V

1) P (wait)

• 임계 구역 들어가기 전에 수행한다
• 세마포어 값을 감소시킨다
• 세마포어 값이 0보다 작으면 기다린다 -> wait
• 세마포어 값이 0보다 크거나 같으면 리턴한다 -> 프로세스가 임계 구역에 진입 가능

 

2) V (signal)

• 임계 구역에서 나올 때 수행한다
• 세마포어 값을 증가시킨다
• 대기 중인 프로세스를 깨운다

 

 

세마포어의 실행 순서

1. 임계 구역에 진입하기 전에 스위치를 사용 중 (P())으로 변경하고, 임계 구역에 들어간다
2. 이후 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다
3. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계 구역을 사용하라는 동기화 신호(V())를 보낸다

💡 임계 구역이 잠겼는지 직접 점검하거나 바쁜 대기, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다!

 

 

 

💻 이진 세마포어 (Binary Semaphore)

• 자원의 범위가 0과 1로만 나타나기 때문에 뮤텍스와 유사하다
• 그러나 뮤텍스는 Lock을 가진 자만 Lock을 해결할 수 있는 반면, 세마포어는 wait과 signal을 날리는 존재가 다를 수 있다
• 즉, 세마포어에서는 Lock을 걸지 않은 스레드도 signal을 보내 Lock을 해제할 수 있다!

 

 

 

📌 Mutex vs Semaphore

• 세마포어는 세마포어의 변수 개수만큼의 프로세스/스레드가 공유 자원에 접근할 수있다
  • 세마포어는 세마포어 변수 값만큼의 공유자원이 존재하고, 각 공유자원 당 하나의 스레드가 접근이 가능하다
  • 즉, 한 번에 세마포어 변수 개수만큼 각 공유자원에 스레드가 접근이 가능하다
• 반면, 뮤텍스는 오직 1개의 프로세스 또는 스레드만 공유자원에 접근할 수 있다
  
  • 뮤텍스는 공유 자원이 1개이다
• 세마포어는 현재 수행 중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있다
• 반면, 뮤텍스는 Lock을 획득한 프로세스가 반드시 그 Lock을 해제해야 한다

 

 

 

 

🎯 정리

• 뮤텍스와 세마포어 모두 완벽한 기법은 아니기 때문에 데이터 무결성을 보장할 수 없으며, 모든 교착 상태를 해결하지는 못한다
• 그러나 상호배제를 위한 기본적인 문법으로, 여기에 좀 더 복잡한 매커니즘을 적용해 개선된 성능을 가질 수 있도록 하는 것이 중요하다!

 

 

---

참고)

https://www.youtube.com/watch?v=oazGbhBCOfU 

https://zangzangs.tistory.com/128

[OS] 뮤텍스(Mutex) vs 세마포어(Semaphore)

https://github.com/twoosky/TIL/blob/main/CS/OS/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4%2C%20%EB%AE%A4%ED%85%8D%EC%8A%A4.md

GitHub - twoosky/TIL: 기초 탄탄이가 되어보자

https://unequaled-peach-7e5.notion.site/2aaab9f2f5ca462294182258d3d3b3ab

세마포어와 뮤텍스

https://heeonii.tistory.com/14

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

 

*뮤텍스 알고리즘 참고

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

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