- 교착상태 문제 제기
- 교착상태
- 교착상태 해결
교착상태 문제 제기
무한 대기와 교착상태
교착상태 : 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기
식사하는 철학자 문제
1965년 Edsger Dijkstra에 의해 처음으로 문제화
병렬처리(concurrent programming)에서의 동기화 이슈와 해결방법을 설명하고자 낸 학생 시험 문제(네델란드의 Eindhoven University of Technology)
5명의 철학자가 원탁에서 식사. 식사 시간은 서로 다를 수 있음
• 자리마다 스파게티 1개와 양 옆에 포크 있음
• 각 철학자는 옆의 철학자에게 말할 수 없음
• 식사를 하기 위해서는 양 옆의 포크가 동시에 들려 있어야 함
• 왼쪽 포크를 먼저 들고, 다음 오른쪽 포크를 드는 순서
• 포크가 사용 중이면 대기
식사하는 데 어떠 문제가 있을까?
문제가 발생하는 경우
: 모두 거의 동시에 왼쪽 포크를 든 후 오른쪽 포크를 들려고 하였을 대 모두 상대가 가진 포크를 기다리면서 먹을 수 없는 교착상태 발생
해결
: 원형 상태로 요청이 생기지 않도록 함.
: 5명 중 마지막 사람을 제외한 4명은 왼쪽의 포크를 잡고 오른쪽 포크를 잡는 순서로 진행, 마지막 사람(5-th)은 오른쪽 포크를 잡고 왼쪽 포크를 잡음
-
원인 - 환형 요청/대기(circular wait/request)
: 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리
: 환형 고리는 스스로 인식이나 해체 불가 -
해결 - ‘환형 대기’가 생기지 않도록
: 마지막 철학자(5번)만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙 수정
식사하는 철학자와 컴퓨터 시스템
철학자 : 프로세스
포크 : 자원
스파게티 : 프로세스가 처리할 작업
교착상태
자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가
소유한 자원을 요청하여 무한정 대기하고 있는 현상
발생 위치
- 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생; 정교하지 못한 코딩에서 비롯됨
- 커널 내에서도 발생하지만 매우 정교하게 작성되어 거의 발생하지 않음
- 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없는 실상
-> 교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면, 시스템 재시작(Restart), 혹은 의심스러운 몇몇 프로그램 종료
전형적인 발생 상황
- 2개의 스레드가 각각 락 소유
- 상대가 가진 락 요청하고 기다릴 때
- 락과 자원에 대한 경쟁이 있는 한 언제든 발생 가능
잠재적 요인
-
자원
- 교착상태의 발생지
-> 교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
컴퓨터 시스템에는 많은 자원 존재 - 소프트웨어 자원 – 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일 락
- 하드웨어 자원 – 프린터, 메모리, 프로세서 등
- 교착상태의 발생지
-
자원과 스레드
- 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인
- DB나 file 처리 프로그램에서, 여러 file 이나 record에 동시에 락을 걸기도 함
-
자원과 운영체제
- 한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인
-> 만일 스레드가 필요한 자원을 한 번에 모두 요청하도록 한다면? 교착상태가 발생하지 않게 할 수 있다.
- 한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인
-
자원 비선점(non-preemption)
- 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺐지 못하는 정책이 요인
-> 운영체제는 스레드가 가진 자원을 강제로 뺏지 못함
-> 만일 강제로 빼앗을 수 있다면? 교착상태가 발생하지 않게 할 수 있다.
- 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺐지 못하는 정책이 요인
교착상태 모델링
자원 할당 그래프(Resource Allocation Graph, RAG)
자원에 대한 시스템의 상태를 나타내는 방향성 그래프
- 컴퓨터 시스템에 실행 중인 전체 스레드와 자원의 개수
- 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
- 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
- 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수
교착상태 해결
코프만 조건
교착상태가 발생하는 4가지 필요충분 조건
다음 4가지 상황이 허용되는 시스템은 언제든 교착상태 발생 가
능
-
상호 배제(Mutual Exclusion)
: 각 자원은 한 번에 하나의 스레드에게만 할당
: 자원이 한 스레드에게 할당되면 다른 스레드에게는 할당될 수 없음 -
소유하면서 대기(Hold & Wait)
: 스레드가 한 자원을 소유(lock)하면서 다른 자원을 기다리기 -
강제 자원 반환 불가(No Preemption)
: 스레드에게 할당된 자원을 강제로 빼앗지 못함 -
환형 대기(Circular Wait)
: 한 그룹의 스레드들에 대해, 각 스레드는 다른 스레드가 요청하는 자원을 소유하는 원형 고리 형성
4가지 조건 중 한 가지라도 성립되지 않으면, 교착상태 발생않음
교착상태 해결 방법
-
교착상태 예방(prevention)
: 발생 여지를 차단
: 조건 중 하나라도 성립되지 못하도록 구성 -
교착상태 회피(avoidance)
: 데드락 생기지 않게 회피
: 자원 할당 시마다 미래의 교착 상태 가능성을 검사하여 교착 상태가 발생하지 않을 것이라고 확신하는 경우에만 자원 할당 -
교착상태 감지 및 복구(detection and recovery)
: 교착상태를 감지하는 프로그램 구동, 발견 후 교착상태 해제 -
교착상태 무시
: 아무런 대비책 없음, 교착상태는 없다고 단정
: 사용자가 이상을 느끼면 재실행할 것이라고 믿는 방법
: 리눅스, 윈도우 등 현재 대부분의 운영체제에서 사용하는 가장 일반적인 방법
교착상태 예방
-
상호 배제(Mutual Exclusion) 조건 -> 상호 배제 없애기
: 동시에 2개 이상의 스레드가 자원을 활용할 수 있도록 함
: 컴퓨터 시스템에서 근본적으로 적용 불가능한 방법(동시에 프린팅?) -
소유하면서 대기(Hold & Wait) 조건 -> 기다리지 않게
: 방법 1) 운영체제는 스레드 실행 전 필요한 모든 자원을 파악하고 실행시 한 번에 할당
: 방법 2) 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한꺼번에 요청하여 할당
: 방법1과 방법2 모두 가능하지 않거나 매우 비효율적인 방법 -
강제 자원 반환 불가(No Pre-emption) 조건 -> 선점 허용
: 자원을 강제로 반환하게 된 스레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태를 관리할 필요
: 간단치 않고 오버헤드 매우 큼 -
환형 대기(Circular Wait) 조건 -> 환형 대기 제거
: 모든 자원에게 번호를 매기고, 번호순으로 자원을 할당 받게 함
교착상태 회피
자원 할당 시, 미래에 환형 대기가 발생할 것으로 판단되면 자원 할당 하지 않는 정책
banker’s 알고리즘으로 해결
교착상태 감지 및 복구
교착상태를 감지하는 프로그램을 통해, 형성된 교착상태를 푼다
백그라운드에서 교착상태를 감지하는 프로그램 늘 실행
-
자원 강제 선점(preemption)
: 교착상태에 빠진 스레드 중 하나의 자원을 강제로 빼앗아 다른 스레드에
게 할당 -
롤백(rollback)
: 운영체제는 주기적으로 교착상태가 발생할 것으로 예측되는 스레드의 상
태를 저장하여 두고 교착상태가 발생하면 마지막으로 저장된 상태로 돌
아가도록 하고, 다시 시작하면서 자원을 다르게 할당 -
스레드 강제 종료(kill process)
: 교착상태에 빠진 스레드 중 하나 강제 종료
: 가장 간단하면서도 효과적인 방법 -
시간과 메모리 공간(rollback의 경우)에 대한 부담이 크기 때문에 잘
사용하지 않음
교착상태 무시: 타조(ostrich) 알고리즘
타조 알고리즘
-
Put your head in the sand 접근법
: 타조가 머리를 모래 속에 박고 자신이 보이지 않는 체하는 것 =>현실도피?
: 교착상태는 발생하지 않을 거야 하고 아무 대책을 취하는 않는 접근법 -
Unix와 윈도우 등 현재 거의 모든 운영체제에서 사용
: 의심 가는 스레드를 종료시키거나 시스템 재시작(reboot)
: 거의 발생하지 않거나 아주 드물게 발생하는 것에 비해 교착상태 해결에는 상대적으로 비용이 많이 들기 때문
