[운영체제] 교착상태

교착상태

• 한 프로그램에 공유자원은 여러개이다. 이에 따라 임계구역도 여러곳에 존재한다. 이런 경우 자원의 소유와 대기에 있어 물고 물리는 관계가 되면서 프로그램의 수행이 정지할 수 있다. 이를 '데드락' 혹은 '교착상태'라고 한다.
• 교착상태는 즉, 서로에게 필요한 자원을 서로 요구하는 경우이다.
• 각 프로그램이 지켜야할 프로토콜을 설정하여 해결할 수 있다. 예를 들면 반대쪽의 프로그램이 실행중임을 확인하면 한쪽편의 프로그램은 대기하고 있는 것이다. 그러나 이 역시 반대쪽에서 계속해서 프로그램이 등장하면 한쪽편은 기아상태가 발생할 수 있다. (이는 에이징 등의 기법으로 해결한다.)

교착상태의 예 : 세마포어

// T0 
P(A);
P(B);
V(A);

// T1
P(B);
P(A);
V(B);

• 세마포어에서 각 T0, T1 쓰레드가 P(A), P(B) 까지 수행하면 T0, T1 모두 대기상태에서 빠져나오지 못하는 '교착상태'에 빠진다.
• P 오퍼레이션을 통해 Wait를 호출하며 각각 A와 B자원을 점유한다. 그런데 이를 릴리즈해주는 V 오퍼레이션이 아래쪽에 있기 때문에 T0, T1 모두 무한정 대기상태에 빠진다.

교착상태의 특징

• 교착 상태가 발생하는 필요충분 조건, 4가지 조건이 동시에 만족 될 때 발생한다.
• 상호배제(Mutual Exclusion) : 할당 후 반환까지 한 프로세스를 사용하는 자원이어야 한다. 만약 다른 프로세스에 의해 자원이 요청되면 해당 프로세스는 자원 방출까지 대기해야 한다.
• 점유대기(Hold-and-wait) : 각 프로세스가 적어도 하나의 자원을 보유하여 다른 프로세스로부터 점유된 해당 자원을 얻기 위해 대기해야 한다.
• 비선점(No preemption) : 점유된 자원은 강제로 방출될 수 없고, 점유한 프로세스가 작업을 종료한 후에야 해당 프로세스에 의해서만 자발적으로 방출될 수 있다.
• 환형대기(Circular wait) : 대기 프로세스들은 서로가 환형의 꼬리를 물며 서로의 자원을 기다린다.

시스템 모델

• 현실적으로 교착상태의 특징을 안다고 해도, 이를 코드를 보고 쉽게 파악하기란 어려운 일이다.
• 따라서 시스템의 현재 상태를 정확히 모델링 할 수 있어야하는데, 이를 '시스템 모델'이라고 한다.
• 먼저 자원을 종류에 따라 R1, R2, ... 와 같이 구분한다. 종류의 예로는 프린트와 같은 물리적인 형태도 있고, 세마포어같은 논리적 형태를 띄기도 한다. 각 종류 Ri에는 r1, r2, ... 으로 각 개체들이 존재한다.
• 그리고 자원을 사용하는 규칙을 설정한다. 특정 자원을 사용하려면 반드시 요청,사용,해제의 단계를 거쳐야 한다. 요청의 개수는 자원의 총 개수를 넘지 못한다. 요청과 해제는 시스템 호출로 제공된다. 파일의 경우 open, close / 뮤텍스는 lock, unlcok / 세마포어는 wait, signal이 이에 해당한다. 운영체제는 이러한 시스템 호출을 처리하면서 시스템 테이블에 지원 할당 상황을 기록해 이를 관리하는 역할을 한다.

자원 할당 그래프

• 지원할당 상황을 테이블로 나타는 것보단 그래프로 나타내는 것이 분석에 있어서는 효과적이다.
• 정점과 에지로 이루어진다.
• 먼저 정점은 프로세스의 집합과 자원의 집합으로 분할한다.
• 프로세스의 집합은 P = {P1, P2, ..., Pn} 으로 원으로 표현한다.
• 자원의 집합은 R = {R1, R2, ..., Rm} 으로 네모로 표현한다.
• 에지는 방향성이 있는 유향에지(directed edge) 이다.
• 프로세스에서 자원으로 보내는 것을 '요청 에지'라고 하고, 자원에서 프로세스로 보내는 것을 '할당 에지'라고 한다.
• 자원 유형은 그 안에 하나 이상의 인스턴스를 가질 수 있다. 해당 인스턴스들은 자원을 의미하는 네모 속에 검은 점 혹은 작은 네모로 표현된다.따라서 할당에지는 반드시 이러한 점으로 출발해야 한다.
• 요청 에지는 사용할 인스턴스가 정해진 것은 아니므로, 사각형 바깥부분 까지만 가리킨다.
• 프로세스가 특정 자원에 대해 '요청'하면, 요청을 의미한 선이 자원 할당 그래프에 그려진다. 요청이 만족될 수 있다면 이는 즉시 할당 에지로 바꾸어 그려지고, 사용을 마치면 해당 에지까지 삭제된다.
• 자세한 그림의 예시 참고
• https://stormcoding.tistory.com/entry/%EC%9E%90%EC%9B%90-%ED%95%A0%EB%8B%B9-%EA%B7%B8%EB%9E%98%ED%94%84resource-allocation-graph
• 해당 그래프에서 사이클이 없다면 교착상태는 발생하지 않는다.
• 사이클이 있고, 각 자원의 유형마다 하나씩의 인스턴스만 보유하고 있다면 교착상태의 필요충분조건이 된다. 각 자원의 유형마다 여러개의 인스턴스가 존재한다면 교착 상태의 필요조건이 발생한다.