Critical Section / 데드락 / 세마포어 / 뮤텍스

요약

Critical Section(임계구역)

임계구역 조건

1. 상호배제,상호배타(Mutual exclusion)
• 오류가 발생하지 않도록, 오직 한 스레드만이 진입 가능한 것입니다.
• 한 스레드(프로세스)가 임계구역에서 실행 중이라면 다른 스레드(프로세스)는 이 구역을 접근할 수 없습니다.

2. 진행(Progress)
• 임계구역에 프로세스가 존재하지 않는 경우, 다른 프로세스가 접근할 수 있도록 만들어줘야 합니다.
• 임계구역에 들어간 프로세스가 없는 상태에서 들어가려는 프로세스가 여러 개 있다면 어떤 프로세스가 들어갈지를 결정하는 것으로, 이것은 유한 시간 이내에 이루어져야 합니다.

3. 유한 대기(Bounded waiting)
• 다른 프로세스의 *기아를 방지하기 위해, 한 번 임계 구역에 들어간 프로세스는 그 다음에 임계 구역에 들어갈 때 제한을 두어야 합니다.
• 임계구역으로 진입하기 위해서 대기하는 모든 스레드는 유한 시간이내에 해당 임계구역으로 진입할 수 있어야 합니다.
• 진행과 다른 점
• 진행은 말 그래도 임계구역 해결을 위해 코드 실행이 멈추지 않는 것을 의미
• 유한대기는 임계구역 코드 실행에 들어간 프로세스 외 나머지 프로세스들이 기아 현상이 나타나지 않도록 하기 위해 이미 임계구역을 실행한 프로세스를 제한하는 것

임계구역 보호 방법

• 공유 자원에 대한 접근을 제한하는 기법

• 공유 자원에 접근할 수 있는 프로세스/쓰레드 수를 나타내는 값( = 자원의 개수)을 두어 상호배제를 달성한다.

• wait과 singal을 활용한 기법
• wait이 먼저 호출되어 임계영역에 들어갈 수 있는지와 먼저 실행되어야 하는 프로세스가 실행되는지 확인한다.
• 조건에 만족하면 wait을 빠져나와 임계영역으로 들어간다.
• 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알린다.

• 공유 불가능한 자원의 동시 사용을 피하는 기법

• 임계 구역을 가진 쓰레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되도록 하는 기술
• 임계 구역에 하나의 스레드만 접근 가능
• 상태가 0, 1로 이진 세마포어라고 부르기도 함

• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 사용
• 한 스레드가 임계영역에 들어가기 위해서 lock을 하고, 나올 땐 unlock을 한다.

• 한 프로세스내에 있는 하나의 스레드만 자원에 접근이 가능하다( 하나의 프로세스 안에 다른 스레드간 동기화를 할 때 사용한다 )

• 모니터는 프레임워크나 라이브러리 그 자체에서 제공된다.

• 일련의 동기화 작업들이 캡슐화되어 있어서 synchronized, wait(), notify()등의 키워드를 통해 편하게 동기화 할 수 있다.

• 즉, 세마포어와 달리 wait, signal 설정 없이 함수 앞에 synchronized를 붙여주기만 하면 상호배제하여 함수의 작업을 수행한다.

세마포어 vs 뮤텍스

1. 가장 큰 차이점은 동기화 대상의 갯수이다.
• Mutex는 동기화 대상이 only 1개일 때 사용
• Semaphore는 동기화 대상이 1개 이상일 때 사용

2. 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
• Mutex는 0, 1로 이루어진 이진 상태를 가지므로 Binary Semaphore!

3. Mutex는 자원 소유 가능 + 책임을 가지는 반면, Semaphore는 자원 소유 불가
• 뮤텍스는 상태 0, 1 뿐이므로 Lock 가질 수 있음

4. Mutex는 소유하고 있는 스레드만이 이 Mutex를 해제할 수 있다.
• 반면, Semaphore는 Semaphore를 소유하지 않는 스레드가 Semaphore를 해제할 수 있다.

5. Semaphore는 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재한다.
• 반면, Mutex는 프로세스의 범위를 가지며 프로세스 종료될 때 자동으로 Clean up 된다.

교착상태(DeadLock)

교착상태 발동 조건

1. 상호 배제(Mutual exclusion)
• 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있음

2. 점유 및 대기(Hold and wait)
• 프로세스가 공유 자원을 점유한 상태에서 다른 자원을 얻기 위해 대기하고 있는 상태여야 함

3. 비선점(No preemption)
• 프로세스가 한 자원을 점유하고 있으면 다른 프로세스가 강제로 빼앗을 수 없음

4. 순환대기(Circular wait)
• 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

교착 상태 해결 방법

1. 교착 상태 예방
• 교착상태 발생 조건 중 하나라도 발생하지 않게 하여 예방하는 방법
• 상호 배제 방지 : 읽기 전용 공유 자원을 사용하기, 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.
• 점유 및 대기 방지 : 프로세스가 실행되기 전 필요한 모든 자원을 할당(자원 낭비 발생)하거나 자원을 점유하고 있지 않을 때만 다른 자원을 요청할 수 있도록 한다
• 비선점 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 합니다
• 순환 대기 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.
• 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있습니다.

2. 교착 상태 회피
• 교착 상태가 발생하기 전에 안전한 상태에서만 자원 요청을 허용하는 방법.
• 안전 상태 (Safe state): 교착상태를 발생시키지 않고 자원을 할당하는 순서 (safe sequence)가 존재해서 모든 프로세스가 정상적으로 종료할 수 있는 상태
• • 불안전 상태 (Unsafe state): 교착상태가 발생할 수 있는 상태
• 교착 상태 회피에 필요한 가정
• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

3. 교착 상태 탐지 및 회복
• 탐지 알고리즘을 사용하여 교차상태를 탐지하고, 회복시키는 방법
• Allocation, Request, Available, 자원 할당 그래프 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다.
• 데드락을 탐지 기법을 통해 발견했다면, 순환대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용합니다.
• 교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제시켜서 복구
• 교착상태를 유발한 프로세스를 강제 종료
• 교착상태를 일으킨 모든 프로세스를 모두 종료
• 교착상태를 일으킨 프로세스 중 하나를 골려 순서대로 종료
• 우선 순위 낮은 프로세스 먼저 종료
• 우선 순위가 같은 경우 작업 시간이 짧은 프로세스 먼저 종료
• 자원을 많이 사용하는 프로세스를 먼저 종료
• 자원 선점
• 교착상태에 있는 프로세스의 자원을 다른 프로세스에게 선점 할당해서 해당 프로세스를 정지시키는 방법

4. 교착 상태 무시
대부분 교착 상태는 드물게 발생하고 예방,회피,탐지 및 복구는 비용이 많이 들기때문에 그냥 무시하는 방식

기아

• 프로세스가 임계 영역에 들어가기 위해 무한정으로 기다리는 현상

• 기다리는 결과를 예방하기 위해 자원할당할 때 발생하는 결과

• 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 발생

• 해결 방안
• 프로세스 우선순위 수시 변경을 통해 각 프로세스 높은 우선순위 가지도록 기회 부여
• 오래 기다린 프로세스의 우선순위 높이기
• 우선순위가 아닌 요청 순서대로 처리하는 요청큐 사용

참고 사이트