상호 배제와 동기화

woga·2020년 11월 17일

운영체제

목록 보기

4/10

상호 배제 (Mutual Exclusion) 이란?

동시 프로그래밍(여러 개의 계산들을 병행 처리)에서 공유 불가능한 자원(동시에 접근해서는 안되는 공유 자원)의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역(Critical section)으로 불리는 코드 영역에 의해 구현된다.

임계 구역이란? 둘 이상의 스레드가 동시에 접근해서는 공유 자원을 접근하는 코드 일부.

공유 불가능한 자원 Ex) 비트 단위의 깃발, 계수기, 큐 등.
문제는 스레드가 언제라도 정지되거나 시작될 수 있다.

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

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

상호 배제의 조건

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

방법들

소프트웨어로 해결 : 데커 알고리즘, 크누스 알고리즘, 램포트의 베이커리 알고리즘, 핸슨 알고리즘, 다익스트라 알고리즘

소프트웨어가 제공(프로그래밍 언어와 운영체제 수준에서) : 세마포어 모니터

동기화

세마포어

신호기, 깃발을 의미하며 각 프로세스에 제어 신호를 전달하여 순서대로 작업하도록 하는 기법.
세마포어의 값에 따라 운영체제는 프로세스가 즉시 자원을 사용할 지, 자원이 다른 프로세스에 의해 사용 중인걸 알게 될 경우엔 일정 시간을 기다려야 한다.

차단을 원하는 영역에 대해 세마포어를 생성하여 세마포어 값으로 임계 영역에 접근 할 수 있는지 검사한다.

세마포어는 동시에 리소스에 접근할 수 있는 '허용 가능한 Counter의 갯수'라고 Counter라고 보면된다. Counter 개수만큼 공유자원에 접근할 수 있다. 이 세마포어 개수에 따라 1개면 이진 세마포어, 2개 이상의 경우면 카운팅 세마포어 라고 불린다.

세마포어는 한 번에 한 프로세스만 접근하여 작업을 수행하는 부분을 잠그거나(lock), 다시 잠금을 해제하는 기능을 제공하는 정수형 변수(sem)이다. 이 정수형 변수는 함수를 통하여 값을 변경한다.

잠금 함수 : P (try)

잠금 해제 함수 : V (increment)

sem < 0 : 프로세스가 처리부분을 처리하고 있다는 뜻이므로 대기

세마포어의 약점

P함수와 V함수의 동작은 -> 독립적 -> 잘못 사용하면 문제 발생!

P - 임계 구역 - P : 현재 프로세스가 임계 구역에서 빠져나갈 수 없게 된다. 또한 다른 프로세들은 임계 구역에 들어갈 수 없으므로 교착 상태 발생

V - 임계 구역 - P : 2개 이상의 프로세스가 동시에 임계 구역에 들어갈 수 있으므로 상호 배제를 보장할 수 없다.

뮤텍스

공유된 자원의 데이터를 여러 쓰레드가 접근하는 것을 막고, 오직 하나의 쓰레드만 접근 가능하도록 하는 변수이다.

0 또는 1의 값을 가지는 이진 세마포어와 유사하다. 임계 구역을 가진 스레드들의 실행 시간을 서로 겹치지 않게 단독으로 실행하게 하는 기법.

프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 사용한다.
뮤텍스 객체를 두 스레드가 동시에 사용할 수 없다.

세마포어 vs 뮤텍스

세마포어: 열쇠의 개수
뮤텍스: 열쇠

가장 큰 차이점은 동기화 대상의 개수이다.

세마포어는 동기화 대상이 여러개 일 때, 뮤텍스는 동기화 대상이 오직 하나 일 때 사용된다.
세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 책임을 진다.
뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 뮤텍스를 해제할 수 있다. 하지만, 세마포어는 소유하지 않고 있는 스레드가 세마포어를 해제할 수 있다.
세마포어는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재한다. 하지만 뮤텍스는 프로세스 범위를 가지고 프로그램이 종료될 때 자동으로 지워진다.

모니터

어떤 공유 데이터에 대해 모니터를 지정해놓으면, 프로세스는 그 데이터에 접근하기 위해 모니터에 들어가야만 한다. 즉, 모니터 내부에 들어간 프로세스에게만 공유 데이터를 접근할 수 있는 기능을 제공하는 것이다. 또한, 프로세스가 모니터에 들어가고자 할 때, 다른 프로세스가 모니터 내부에 있다면 입장 큐에서 기다려야 한다.

모니터 구성?
필요한 공유자원을 프로세스에게 할당하는 데 필요한 데이터와 데이터를 처리하는 프로시저로 구성.

모니터는 정보를 은폐하는 방식으로 사용하는데 다른 외부 프로시저가 접근하지 못하도록 한다. 모니터에는 한 번에 하나의 프로시저만 접근하여 사용 가능하다(wait와 signal 사용)

공유 변수들은 모니터 속에서 선언되며 이 변수들은 모니터 속의 producer 들에서만 사용될 수 있다.
이 모니터의 프로시저들을 실행할 때 크리티컬 섹션의 조건들을 만족한다. 즉, 한 프로세스가 특정 모니터의 프로시저를 실행 중이면 다른 프로세스들은 이 모니터의 포로시저들을 실행하지 못하고 대기 상태에 있게 된다.