[운영체제 공부] 상호배제

상호배제 (Mutual exclusion)는 공유 불가능한 자원의 동시 사용을 막기 위한 알고리즘이다.

상호배제는 다음 네 가지 조건을 만족해야한다.

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

임계 영역(Critical Section)

임계 영역의 예

공유 데이터에 여러 프로세스가 동시에 접근하면 시간 차이로 예상치 못한 결과를 만들 수 있기 때문에 임계 영역에는 반드시 한 번에 하나의 프로세스만 진입할 수 있어야 한다.

 

선행 그래프를 이용한 상호 배제

 

뮤텍스(mutual exclusion)

가장 흔하고 쉬운 예제로, 화장실과 열쇠에 비유할 수 있다.

화장실 한 칸과 열쇠 하나가 존재한다.

화장실 한 칸에는 한 사람밖에 들어가지 못하고, 그 화장실을 사용하려면 열쇠를 가지고 들어가야 한다.

그렇다면 다른 사람이 화장실을 사용하려면 앞서 화장실에 들어간 사람이 열쇠를 들고 나올 때 까지 기다려야 한다.

여기서 화장실 = 임계영역, 열쇠 = 소유권한으로 이해할 수 있다.

 

세마포어(semaphore)

접근 가능한 스레드 or 프로세스의 수를 나타내는 카운터를 사용한다.

뮤텍스에 반해 세마포어는 화장실이 여러 칸이고, 화장실 입구에 사용 가능한 칸의 개수를 나타내는 카운터가 있다고 생각하면 된다.

화장실이 세 칸이고, 카운터가 3 일때, 세 사람이 들어가면 카운터는 3이 감소해 0이 된다.
이 때 화장실에 들어가려는 사람이 있다면 카운터가 1 이상으로 증가할 때까지 기다려야한다.