[OS] 임계영역 문제 / 뮤텍스(Mutex), 세마포어(Semaphore), 스핀락(Spin lock), 교착상태(Dead lock)
Critical Section Problem(임계 영역 문제)
동일한 자원을 동시에 접근하는 작업이 실행되는 코드영역을 사용할 수 있도록 하는 프로토콜 설계
상호 배제 (Mutual Exclusion)
진행 (Progress)
한정된 대기 (Bounded Waiting)
Lock
+) 스핀락 : 세마포 초기버전
Mutex와 Lock의 차이점
임계 영역의 락이 풀릴 때 까지 기다려야 한다는 점은 같지만,
Lock은 접근 프로세스가 무한 루프를 돌면서 cpu자원을 사용한다.
반면 Mutex는 컨텍스트 스위칭을 실행한다. 따라서 다른 작업을 동시에 진행 할 수 있다.
세마포어
ㄴ 카운팅 세마포 :
가용한 개수를 가진 자원에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수로 초기화 된다. 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가 한다.
ㄴ 이진 세마포 (MUTEX):
뮤텍스라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0과 1사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.
+) 모니터 (Monitor)
단점,
Busy Waiting(바쁜 대기)
스핀락에서, Critical Section에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU시간을 낭비했었다. 일반적인 Semaphore에서 Critical Section 에 진입을 시도했지만, 실패한 프로세스에 대해 Block 시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용하여 시간낭비 문제를 해결한다.
Deadlock(교착상태)
세마포가 Ready queue를 가지고있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리는상태. Critical Section에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되어야만 빠져나올 수 있는 상황을 지칭한다.
교착상태의 조건
- 상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구
- 점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다
- 비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때 까지 그 자원을 뺏을 수 없다
- 순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고있다.
ㄴ교착상태의 예방 (자원 사용의 효율성이 떨어지고, 비용이 많이 듬.)
- 두개 이상의 공유가능한 자원을 사용하지 못하게 한다 (상호배제 조건의 제거)
- 한 프로세스에 수행되기 전에 모든 자원을 할당시키고, 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법 (점유와 대기 조건의 제거) -> 기아 상태, 무한 대기 문제점 발생
- 비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다. (비선점 조건의 제거)
- 자원 유형에 따라 순서를 매긴다. (환형 대기 조건의 제거)
ㄴ교착상태의 회피
- Circular wait 가 발생하지 않도록 자원할당 상태를 검사한다.
- 회피 알고리즘
- 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
- 은행원 알고리즘 (Banker's algorithm)