WHY
면접 질문 5에서 경쟁 조건, 임계 구역, 임계 구역을 보호하기 위한 조건 3가지를 살펴보았다.
그중에서 가장 중요한 조건은 "상호 배제"로 임계 구역을 보호하기 위한 조건이었음을 알 수 있었다.
이번 질문에서는 상호배제를 위한 기법 3가지 뮤텍스, 세마포어, 모니터를 알고 있는지 물어보는 것이다.
세 가지 모두 동기화를 목적으로 한다는 공통점이 있으나 자원을 다루는 관점이 다르다.
각각의 특징들의 핵심을 잘 정리해서 답변하면 깔끔한 답변을 하도록 하자!
뮤텍스(Mutex) : "MUT"ual "EX"clusion [Object]. lock을 활용.
임계 영역(자원)에 하나의 작업 스레드만 허용하는 것이다.
이를 조율하기 위해서 임계 영역에 들어갈 수 있는 작업 스레드는 "lock"을 소유해야 해!라는 조건을 적용한다.
자원을 원하는 작업 스레드는 지속적으로 lock을 요구한다.
자원을 소유하고 있는 작업 스레드는 lock을 쥐고 있으며 작업이 끝난 이후에 lock을 풀어낸다.
해당 자원을 쥐고 있는 스레드만이 lock을 반환할 수 있어서 "비선점"방식이 된다.
임계구역을 위한 lock 변수는 전역 변수로 관리된다.
[ TIP : Java의 경우 모든 객체가 lock 속성을 지니며 JVM만이 관리할 수 있다고 한다 ]
mutex의 특징은 lock을 소유했냐 유무로 임계 영역을 허용한다는 것이다.
그렇기에 임계영역을 원하는 다른 작업 스레드들은 임계 영역이 누군가에 의해서 사용되는 경우
끊임없이 lock이 열려있는지 체크해야 한다. 이를 busy watiting 방식이라고 한다.
spin lock이라고도 부르며 멀티 스레딩 환경에서 프로세스를 깨우는 방식(sleep, wake-up) 시그널을 통해 진행되는
문맥교환을 거치지 않기 때문에 임계 영역을 짧게 사용해야 하는 경우 효율성 측면에서 좋을 수 있다고 한다.
[ 반대로 단일 코어 단일 스레드 환경에서는 상당히 치명적이다. ]
뮤텍스 구현 알고리즘으로는 데커, 피터슨 알고리즘이 존재한다.
세마포어(Semaphore) : 카운팅 변수로 접근 가능한 공유자원을 표기. [ 시그널 기법 사용 ]
공유 자원이 1개 이상인 경우 상호 배제 원리를 보장하는 접근 제어 알고리즘으로
컴퓨터 공학 역사상 많은 공로를 세운 다익스트라의 알고리즘이다.
임계 영역(공유자원)에 들어가는 스레드가 복수개가 가능하다. 세마포어의 경우 동기화 대상이 여러 개일 경우에 사용하며
기찻길의 표식으로 사용하는 깃발(Semaphore)에 메타포한 알고리즘.
당시에는 신호등 대신 깃발수가 한정된 기찻길을 관리했다고 한다. [ 색깔로 신호를 처리 ]
세마포어의 경우 공유 자원에 1개 이상의 스레드가 접근할 수 있으며 "접근 스레드의 수"에 한계를 두는 방식이다.
그림에서 보듯 여러 스레드가 공유자원에 접근이 가능하다.
그만큼 공유자원의 수가 뒷받침되어야 한다.
공유자원을 사용하고 있는 스레드의 수를 공유자원의 수에서 빼서 남아 있는 공유자원의 수를 표기한다.
다음의 3가지 함수가 필수적으로 사용된다.
초기화 함수 : 전역 변수를 지정된 값으로 초기화한다. [ 사용가능한 자원의 수를 명시하는 것]
P() [ Proberen이라는 네덜라는어로 "시도"를 의미한다. 자원이 있는 경우 자원의 수를 감소시키고 사용 ]
- 자원의 점유를 시도하는 것으로 자원의 수가 0 이상인 경우 해당 자원의 값을 1 감소시킨다.
0보다 아래인 경우 사용 가능한 자원이 없다는 것으로 block()로 대기한다.
[ 컴퓨터 공학도는 0부터 수를 카운팅 하는 거 알죠? ]
[ wait() 시그널로도 부른다 ]
V() : [ Verhogen이라는 네덜란드 어로 "증가"를 의미한다. 공유 자원을 사용하고 해당 자원의 수를 증가시키는 것이다.]
잠금 해제와 동기화를 같이 수행한다. 임계 영역의 사용이 끝났기에 자원의 수를 증가시켜주고
wake_up() 시그널을 보내서 block() 프로세스 들 중 하나를 깨운다.
[ signal()로도 부른다. ]
잠금 해제를 기다리는 프로세스(block())들은 "큐"에 저장되어 있다가
wake_up() 시그널을 받으면 큐에서 선택되어 임계 구역으로 들어가게 된다.
문제는 P() -> 임계구역 작업 -> V() 처리가 원활하지 않을 수 있다는 것이다. [ 인터럽트는 언제 터질지 모른다 ]
[ 오로지 하나의 프로세스만 전역 변숫값을 변경해야 하는데 이것을 보장하지 못하는 것이다.
이론상으로는 하나의 프로세스만 전역 변수값을 변경해야 한다. 현실적으로는 어렵다. ]
이러한 문제점 속에서 세마포어는 "상호 배제"와 "한정 대기 조건"을 완전하게 보장하지 못한다.
{ P() -> 임계 구역 처리 -> V() } 이 원자적으로 수행(수행되거나 수행되지 않거나) 되어야 하는데
수행 도중에 인터럽트로 꼬이게 되면 경쟁 상태에 들어가게 돼버리는 것이다.
세마포어에는 한계점이 존재하는 것이다!
이를 위해서 모니터(monitor) 기법을 고안해서 "원자적"으로 실행되도록 보장하는 하드웨어 기법을 고안한다.
이쯤에서 살펴보는 뮤텍스와 세마포어의 차이점 [중요!]
https://stackoverflow.com/questions/34519/what-is-a-semaphore/40238#40238
What is a semaphore?
A semaphore is a programming concept that is frequently used to solve multi-threading problems. My question to the community: What is a semaphore and how do you use it?
stackoverflow.com
뮤텍스는 공유 자원을 보호하기 위해서 사용된다. [ 시그널 기법에 사용 X ]
세마포어의 경우는 복수의 공유 자원을 사용함에 있어서 시그널로 처리할 때 사용한다. [ 보호와는 거리가 멀다 ]
임계 영역에 대한 간섭(소유권)의 관점.
세마포어는 자원의 허용 상태를 나타내는 변수를 사용할 뿐 "소유" 개념이 없다. [ 일종의 스위치 ]
뮤 텍스의 경우 자원을 점유한 프로세스에 대한 소유권(lock)을 쥐고 반환하는 개념이어서 다른 스레드가 간섭할 수 없다.
임계영역에 대한 관점
뮤텍스의 경우는 동기화 대상이 오로지 하나의 자원일 경우에만 사용한다.
해당 자원에 대한 lock을 소유하고 반환하는 방식으로
여러 프로세스의 스레드로 하여금 한 하나의 영역에 하나의 스레드만 허용하는 것을 보장한다.
세마포어의 경우 1개 이상의 공유 자원에 대한 접근을 허용하며 wait(), signal()을 사용해서 자원의 수를 변경한다.
개념적 크기의 관점
세마포어의 경우 counting 변수를 0으로 설정하면 뮤텍스처럼 사용하게 된다. [ 공유자원이 1개 ]
뮤텍스를 바이너리 세마포어라고 부른다.
2개 이상의 스레드가 접근 가능하면 카운팅 세마포어라고 한다.
공유자원의 관점의 수로 보면 세마포어는 뮤텍스를 포함한다.
공유 자원 대기의 관점
세마포어는 P(), V() 함수를 통해서 자원의 수를 수정하며, 대기(block)하거나 wake() 시그널을 보내서 처리한다.
반면 뮤텍스의 경우 다른 프로세들은 lock을 계속 확인하면서 반환되었는지 확인한다.
요약하자면
뮤텍스
- lock 객체 소유와 반환.
- 시그널 메커니즘 사용 X
- 해당 자원에 단일 스레드만 접근 허용
세마포어
- 시그널 메커니즘으로 사용 가능한 자원의 수를 변경.
- 소유의 개념 X
- 해당 자원이 2개 이상인 경우 멀티 프로세스에서 접근 가능.
모니터(Monitor) [ 고수준 동기화 알고리즘 : 프레임워크나 라이브러리 차원에서 제공 ]
세마포어는 잘못 사용할 경우 임계 구역을 보호하지 못하는 문제점이 존재한다.
[ + 사용자가 직접 singal, wait 함수를 구현해야 하기에 난이도가 높다. 사용자에 따라 실수 가능성도 존재 ]
프로세스로 하여금 세마포어의 시그널 메커니즘을 자동으로 처리하는 것 + 편리하게 뮤텍스 개념을 사용할수 있도록
프로그래밍 언어, 혹은 프레임워크 차원에서 제공하는 "모니터" 기법을 사용하는 것이다.
[ Java의 경우 synchronized 키워드, C#의 경우 lock 키워드가 모니터 기능을 제공한다. ]
모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스(프로시저)만을 제공한다.
모니터는 공유 자원을 캡슐화(정보 은닉)하고 해당 공유 자원을 사용할 수 있는 프로시저만 제공한다.
프로시저 호출에 대해서 동기화하여 안전하게 공유 자원을 사용할 수 있도록 돕는다.
공유 자원에 접근하고자 하는 프로세스는 모니터에 "작업"을 요청하면 된다.
모니터는 작업을 큐에 저장하고 순서대로 처리하면서 결과만 프로세스에 알려준다.
한 번에 하나의 프로시저만 접근하여 사용 가능하며 wait(), signal() 함수를 사용한다.
마무리
이번 내용은 정리하기 까다로웠다. 뮤텍스와 세마포어는 워낙 유명한 주제이며 큰 부분에서 차이점이 존재하기에
깔끔하게 정리된 자료들을 인터넷과 책을 통해 접할 수 있었다.
모니터의 경우 그렇지 않았다. 모니터 기법의 경우 고수준 프로그래밍 언어 차원에서 제공하다 보니 특정 프로그래밍
언어를 기반으로 설명하는 글이 많았다. 해당 내용들은 깊게 들어가면 들어갈수록 상당히 많은 정보를 구할 수 있다.
[ 뮤텍스 알고리즘, 세마포어 세부 알고리즘, 모니터 알고리즘 등등... ]
이번 정리의 경우 "임계 영역"을 보호하기 위해 상호 배제를 위한 기법 3가지의 핵심 내용만을 살펴보았다. [ 나의 기준... ]
세마포어와 뮤텍스를 중점으로 정리해보았고
모니터는 핵심만 살펴보았다.
다음으로는 "교착 상태"의 개념과 조건에 대해서 살펴보고자 한다. [ OS의 핵심 질문 중 하나이다. ]
이후에는 OS가 관리하는 메모리에 대한 기법들을 살펴보도록 한다.
빨리 OS와 네트워크를 정리하고 싶다. [1월의 목표!! ]
잘못된 내용이 있을 경우 빠르게 피드백하도록 하겠습니다.
참고자료
책
- 쉽게 배우는 운영체제
블로그 & 기술
- 자바(Java)의 뮤텍스, 세마포어, 모니터 : link
- 진양님의 글 [ 세마포어에 대한 용어와 정리 ] : link
- 이대현 님의 블로그 : link [ 화장실에 대한 메타포가 깔끔하다 ]
'면접질문[CS] > 알고리즘 & OS' 카테고리의 다른 글
| 동기 비동기 블로킹과 논블로킹 2x2 매트릭스 [ 운영체제(OS) 면접질문8 ] (0) | 2022.01.06 |
|---|---|
| 교착상태란 무엇인가. [ 운영체제(OS) 면접질문 7] (0) | 2022.01.04 |
| 동기화, 경쟁 조건(Race Condition), 임계 구역(Critical Section) [ 운영체제(OS) 면접질문 5] (0) | 2021.12.23 |
| CPU 스케줄링 알고리즘 [ 운영체제(OS) 면접 질문 4] (0) | 2021.12.22 |
| CPU 스케줄링 & 선점형, 비선점형 스케줄링 [ 운영체제(OS) 면접 질문 3] (0) | 2021.12.21 |
