08/27 CS공부 - OS(데드락, 뮤텍스, 세마포어)

1. 데드락(DeadLock, 교착상태)

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 못하는 상태 -> 무한히 다음 자원을 기다리게 되는 상태
한정된 자원을 여러곳에서 사용하려고 할 때 발생한다.

출처: https://github.com/gyoogle/tech-interview-for-developer

발생조건

데드락의 발생 조건에는 4가지가 있으며 4가지 조건을 모두 성립해야 데드락이 발생한다. 하나라도 성립하지 않으면 해결이 가능하다.

1. 상호 배제(Mutual exclusion): 자원은 한번에 한 프로세스만 사용할 수 있음
2. 점유대기(Hold and wait): 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야함
3. 비선점(No preemption): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
4. 순환대기(Circular wait): 프로세스의 집합에서 순환형태로 자원을 대기하고 있어야함

처리방법

1. 예방(prevention): 교착상태 발생 조건 중 하나를 제거하면서 해결 - 자원낭비가 매우 심함

• 상호배제 부정: 여러 프로세스가 공유자원 사용
• 점유대기 부정: 프로세스 실행 전 모든 자원을 할당
• 비선점 부정: 자원 점유중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납
• 순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구

2. 회피(avoidance): 교착상태 발생 시 피해나가는 방법

은행원 알고리즘
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하여 교착상태를 회피
안정상태면 할당, 아니면 자원해지까지 대기

자원 할당 그래프 알고리즘
자원과 프로세스에 대해 요청간선과 할당 간선을 적용하여 교착상태를 회피하는 알고리즘
프로세스가 자원을 요구 시 요청간선을 할당간선으로 변경했을 시 사이클이 생성되는지 확인한다.
단, 사이클이 생성된다 하여 무조건 교착상태인 것은 아니다.
 - 자원에 하나의 인스턴스만 존재 시 교착상태로 판단
 - 자원에 여러 인스턴스가 존재할 시 교착상태 가능성으로 판단
사이클을 생성하지 않으면 자원을 할당

3. 교착상태를 탐지하고 회복: 교착상태가 되도록 허용한 다음 회복시키는 방법

1. 탐지(Detection): 자원 할당 그래프를 통해 교착상태를 탐지함 - 자원 요청 시 탐지 알고리즘을 실행시켜 그에대한 오버 헤드 발생
2. 회복(Recovery): 교착상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시켜 회복시키는 방법
   프로세스 종료방법
   - 교착상태의 프로세스를 모두 중지
   - 교착상태가 제거될 때까지 하나씩 프로세스 중지
   자원 선점방법
   - 교착상태의 프로세스가 점유하고있는 자원을 선점해 다른 프로세스에게 할당(해당 프로세스는 일시정지)
   - 우선순위가 낮은 프로세스나 수행횟수 적은 프로세스 위주로 프로세스 자원 선점

2. 뮤텍스(Mutex) & 세마포어(Semaphore)

뮤텍스와 세마포어 모두 멀티스레드 환경에서 동기화 문제를 해결하기 위해 사용되는 주요 동기화 기법이다

세마포어

세마포어는 카운터를 기반한 동기화 기법으로 여러 스레드가 제한된 수의 자원에 접근할 수 있도록 제어한다.

세마포어는 지정된 카운터 값을 유지하며 이 값이 0보다 클 때 스레드가 자원에 접근할 수 있다.

세마포어 P, V 연산

P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

뮤텍스

뮤텍스는 스레드들이 공유자원에 동시에 접근하는 것을 막기 위해 사용된다. 따라서 한 번에 오직 하나의 스레드만이 공유자원에 접근할 수 있도록 보장한다.

Lock을 통해 제어되며 Locked, Unlocked 상태를 통해 접근이 가능한지를 판단한다. Locked 상태라면 스레드는 공유자원에 접근하기 위해 대기해야한다. 두 상태 뿐이므로 이진세마포어라고도 한다.

뮤텍스는 자원을 획득한 스레드가 소유하며 해당 스레드만이 뮤텍스를 Unlock할 수 있다.

뮤텍스 알고리즘

1. 데커 알고리즘

flag와 turn 변수를 통해 임계구역에 들어갈 프로세스/스레드를 결정한다.
flag는 누가 임계구역에 진입할 지 나타내는 변수이며 turn은 누가 임계구역에 들어갈 차례일지를 나타낸다.

2. 피터슨 알고리즘

데커와 유사하지만 상대방 프로세스/스레드에게 진입기회를 양보한다.

3. 베이커리 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘으로 가장 작은 값의 번호표를 가지고 있는 프로세스가 진입한다.