07 교착상태

1. 교착상태 문제 제기

1.2 식사하는 철학자 문제

문제점

• 5명의 철학자가 원탁에서 식사, 식사 시간은 서로 다를 수 있음
• 자리마다 스파게티 그릇이 하나 있고 5개의 포크가 그릇 사이에 있음
• 철학자는 다른 철학자와 대화할 수 없음
• 식사를 위해서 양 옆의 포크를 함께 들어야 함
• 왼쪽 포크를 먼저 든 다음 오른쪽 포크를 드는 순서이며 포크가 사용중이면 대기해야함, 왼쪽 포크를 옆 철학자가 사용하고 있다면 오른쪽 포크도 잡을 수 없음

철학자가 식사하는 모든 경우

철학자들의 교착상태 원인 - 환형 요청/대기

모든 철학자가 왼쪽포크를 가진 상태에서 오른쪽 철학자가 가진 포크를 요청하여 대기가 환형 고리를 형성함 환형 고리를 해체할 수 없으 교착상태에 빠짐

철학자들의 교착상태 해결 - 환형 요청/대기가 생기지 않게 규칙 변경

5명중 4명은 원래대로 하고 나머지 철학자만 오른쪽 포크를 먼저 잡은 뒤 왼쪽 포크를 잡도록 규칙 변경 철학자가 대기는 해도 언젠가 식사를 할 수 있게되어 교착상태에 빠지지 않음

1.3 식사하는 철학자와 컴퓨터 시스템

• 철학자 - 프로세스
• 포크 - 자원
• 스파게티 - 프로세스가 처리할 작업

2. 교착상태

2.1 교착상태 정의

자원을 소유한 스레드들 사이에서 각 스레드는 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상

전형적인 멀티스레드 교착상태 사례

두 스레드가 임계구역에 진입하기 위해 2개의 락 LockA와 LockB가 모두 필요할 때, 각 스레드가 락을 하나씩 소유한 상태에서 상대 스레드가 소유한 락을 요청하는 경우

• 단일 cpu든 다중 cpu든 가리지 않고 발생
• 락이나 자원에 대한 멀티스레드 경쟁이 있는 한 발생 가능
• 커널코드내에서는 거의 발생하지 않음(교착상태 고려해서 작성), 사용자 응용프로그램 내에서 주로 발생

2.2 컴퓨터 시스템에 잠재된 교착상태 유발 요인

자원 - 자원은 교착상태의 발생지이다

교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌에서 발생함

• 소프트웨어/데이터 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일락 등
• 하드웨어 자원 - 프린터, 메모리, 프로세서 등

자원과 스레드 - 한 스레드가 동시에 여러 개의 자원을 필요로 하는 경우가 있다

스레드가 실행되는 동안 한 개의 자원만 필요한 경우 교착상태가 발생하지 않음

자원과 운영체제 - 운영체제는 한 번에 하나씩 자원을 할당한다

스레드가 자원을 필요로 할 때 운영체제로부터 할당받음 여러개의 자원이 필요하더라도 한 번에 한 개씩 할당받는 과정을 거침 필요한 자원을 한번에 모두 할당받는다면 교착상태가 발생하지 않을 수도 있음

자원 비선점 - 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못한다

운영체제는 스레드가 할당받은 자원을 강제로 빼앗지 못함

2.3 교착상태 모델링

자원 할당 그래프

자원할당그래프(RAG)를 이용하여 교착상태를 표현하고 교착상태 예방, 회피, 감지 등이 운용됨

• 꼭짓점 - 스레드는 원, 자원은 사각형
• 간선 - 할당 간선(자원→스레드, 스레드가 자원을 소유하고 있음 표현), 요청 간선(스레드→자원, 스레드가 자원을 기다리고 있음 표현)

자원할당 그래프를 통해 표현되는 정보

• 컴퓨터 시스템에 실행중인 전체 스레드와 자원
• 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
• 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
• 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

교착상태가 발생한 자원 할당 그래프 모양

교착상태 발생 - 환형고리가 나타남 자원 할당 그래프를 통해 교착상태를 발견하거나 교착상태에 빠진 스레드들과 자원을 알아낼 수 있음

? linux 운영체제는 자원 할당 그래프를 구성하여 교착상태 발생 감지 기능을 지니고 잇는가?

2.4 교착상태에 빠진 응용프로그램 사례

3. 교착상태 해결

3.1 코프만 조건

교착상태를 유발할 수 있는 4가지 필요충분조건

• 상호배재(Mutual Exclusion) - 자원을 한 번에 한 스레드에게만 할당
• 점유 대기(Hold&Wait) - 스레드가 자원을 소유하면서 다른 자원대기
• 비선점(No Preemption) - 스레드에게 할당된 자원을 강제로 빼앗지 못함
• 환형 대기(Circular Wait) - 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

4가지 조건 중 한가지라도 성립되지 않으면 교착상태에 빠지지 않음

3.2 교착상태 해결 방법

교착상태 예방(prevention)

4가지 조건 중 하나 이상의 조건이 아예 성립되지 못하도록 시스템을 설계하고 구성하여 교착상태가 발생할 여지가 없도록 예방하는 것

교착상태 회피(avoidance)

운영체제가 자원 할당 시 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당하는 방법 자원을 할당할 때마다 교착상태 가능성을 검사하므로 시스템 성능을 많이 저하시킴

교착상태 감지 및 복구(detection and recovery)

운영체제가 교착상태를 감지하는 별도의 프로그램을 구동시켜 교착상태를 발견하면 해체하는 방법 감지 작업이 주기적으로 실행되어야 하므로 시스템에 많은 부담

교착상태 무시(ignore and reboot)

교착상태가 발생하도록 내버려두는 방법 교착상태는 웬만하면 발생하지 않음 + 이상을 느끼면 의심가는 스레드를 종료나 부팅시켜 그 때 대책을 세움 unix, linux, windows 등 대부분의 범용 운영체제에서 사용중 → 예방, 회피, 감지/복구 방법은 시간과 공간이 많이 필요해 컴퓨터 시스템 성능을 낮춤 교착상태 무시 알고리즘 : ostrich 알고리즘(타조 알고리즘)

3.3 교착상태 예방

1. 상호배제 → 상호배재 없애기

2개 이상의 스레드가 동시에 자원을 사용할 수 있도록 허용하여 자원 독점을 막음 → 근본적으로 불가능

2. 점유 대기 → 기다리지 않게

스레드가 필요한 자원을 처음부터 모두 가지게 함

1. 운영체제가 스레드 실행 전 스레드가 필요한 자원을 모두 알고 실행과 함께 모든 자원을 할당, 모든 자원이 준비될 때까지 스레드 실행 자체를 대기
2. 스레드가 자원을 소유한 상태에서 새로운 자원이 필요하게 되면 현재 할당받은 자원을 모두 반환하고 다시 요청

3. 비선점 → 자원 선점 허용

높은 순위의 스레드가 자원을 요청하면 운영체제가 자원을 가진 낮은 순위의 스레드에게서 강제로 자원을 빼앗음 자원을 반환한 스레드가 다시 사용하게 될 때 이전 상태로 되돌아 갈 수 있도록 상태관리 필요

4. 환형 대기 → 환형대기 제거

모든 자원에 번호를 매기고 스레드에게 반드시 번호순으로 자원을 할당받게 하는 방법

3.4 교착상태 회피

교착상태 회피 : 자원할당 알고리즘을 이용하여 교착상태를 방지하는 방법 자원할당 알고리즘 : 자원 할당을 요청받았을 때 앞으로 환형 대기가 발생하지 않는다는 확신이 서는 경우에만 자원을 할당함으로써 교착상태의 발생을 피함 → 환형 대기가 발생할 것인지 판단하는 작업 실행

banker’s 알고리즘(은행원 알고리즘)

시스템을 안전한 상태와 불안전한 상태로 나누고 자원을 할당했을 때 안전한 상태로 갈 때만 자원 할당

(판단 기준 : 각 스레드가 필요로 하는 자원 개수, 현재 실행중인 각 스레드가 할당받은 자원 개수, 시스템 내 할당 가능한 자원의 개수)

스레드가 실행 전 필요한 전체 자원의 수를 운영체제에 알려야 함 → 개수를 아는건 사실상 불가능 실행중인 스레드의 개수도 동적으로 변함

3.5 교착상태 감지 및 복구

교착상태 감지 프로그램을 상시적으로 실행시켜 교착상태를 감지하고 해제하는 방법 교착상태 감지 : 자원 할당 그래프에 환형 대기 모양을 가지는 부분이 있는 지 판단

교착상태 해제 방법

자원 강제 선점(preemption)

교착상태에 빠진 스레드 중 하나를 선택하고 이 스레드가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 다른 스레드에게 할당하는 방법

롤백(rollback)

교착상태가 발생할 것으로 예측되는 스레드들에 대해 상태를 주기적으로 저장해두었다가 교착상태 발생 시 최근에 저장해둔 상태로 복구시켜 돌아가게 하는 것 롤백 이후에는 스케줄링 등의 요인에 의해 자원 할당 순서가 다르게 되어 교착상태가 발생하지 않게 됨 주기적으로 저장하기 위해 시스템 시간과 공간을 소모하여 성능을 떨어뜨림

스레드 강제 종료(kill process) — 이게 결국 타조알고리즘 ??

교착상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법 간단하고 효과적이지만 어떤 스레드를 희생시킬 지 결정하는게 문제

교착상태 감지 후 복구 → 상시적으로 프로그램이 실행되면서 자원 할당 그래프를 분석해 시스템에 부담

? 교착상태와 기아 상태 차이점

3.6 교착상태 무시 : 타조(ostrich) 알고리즘

교착 상태가 발생할 가능성히 극히 적으면 굳이 교착상태를 피하기 위해 많은 비용을 사용할 필요가 없음

타조 알고리즘

교착상태에 대해 아무 대책 없이 컴퓨터 시스템을 가동시키고 교착상태가 발생하면 시스템을 재시작하거나 특정 스레드를 강제 종료하는 방법

데이터 손실이 발생할 수 있지만 비용면에서 나은 방법 실시간 시스템에서는 부적절

출처 - https://www.booksr.co.kr/product/%EB%AA%85%ED%92%88-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C%EC%88%98%EC%A0%95%ED%8C%90/