교착상태 방지방법과 상호배제의 기법

소개글

교착상태 방지방법과 상호배제의 기법에 대한 보고서 자료입니다.

목차

1. 임계구역에서 프로세스간에 상호배제가 필요한 이유와 이 상호배제를 구현하는 기법들에 관해 기술
(1)상호배제가 필요한 이유
(2) 상호배제를 구현하는 기법
1) 2개 프로세스의 상호배제
2) N개 프로세스의 상호배제
3) 세마포어(semaphore)를 이용한 상호배제의 구현
4) 모니터(monitor)

2. 교착상태가 실생활에서 일어나는 예를 기술하고 컴퓨터시스템 내부에서 일어나는 교착상태를 방지하기 위한 조건들에 관해 기술
(1) 교착상태의 예방(deadlock avoidance)
(2) 교착상태의 회피(deadlock avoidance)
(3) 교착상태탐지(deadlock detection)

본문내용

않으면 최대 요구량을 초과하기 때문에 오류(요구량 > 필요량 → error)
(가) Requesti ≤ Available라면 (가)으로 가고 그렇지 않으면 자원이 부족하기 때문 에 대기(요구량 > 잔여량 → 대기)
(가) 시스템은 상태를 다음과 같이 수행하여 요구된 자원들을 프로세스에게 할당되도 록 한다
Available(잔여량) = Available(잔여량) - Requesti(요구량)
Allocationi(할당량) = Allocationi(할당량) + Requesti(요구량)
Needi(필요량) = Needi(필요량) - Requesti(요구량)
2) 안전 알고리즘
<안전 알고리즘>
(가) Work, Finish를 각각 길이가 m, n인 벡터라고 하면, Work = Available로 Finish[i] = false, i = 1, 2, 3, ..... , n으로 초기화 한다. Work에는 남아 있는 자원 수인
Available의 임시변수이다.
(가) 다음과 같이 되는 i 값을 찾는다.
a) Finish[i] = false
b) Needi ≤ Work
이런 i 값이 존재하면 (가)으로 없으면 (가)로 간다.
(가) 자원을 할당한 후 해제한다.
Work = Work + Allocationi
Finish[i] = true
(가)단계로 간다.
(가) 만약 모든 i에 대하여 Finish[i] = true면 시스템은 안전 상태
(3) 교착상태탐지(deadlock detection)
만일 시스템이 교착상태가 발생하지 않도록 하는 프로토콜을 사용하지 않는다면, 이미 발생한 교착상태를 탐지하고 회복하는 방법이 있어야 할 것입니다. 시스템의 상태를 검사하는 프로그램은 주기적으로 교착상태를 찾는데 이용됩니다.
1) 자원 유형마다 여러 개의 자원이 있는 경우
- 자료구조 정의
① Available : 각 자원의 형태별로 사용가능한 자원의 수를 표시하는 길이
가 m인 벡터
② Allocation : 현재 각 프로세스에 할당된 자원의 수를 정의한 n×m 행렬
③ Request : 각 프로세스의 현재 요구를 표시하는 n×m 행렬
④ Request[i,j] = k라면 프로세스 Pi는 자원형태 Rj의 자원을 k개 더 요구
<발견 알고리즘>
(가) Work, Finish를 각각 길이가 m, n인 벡터라고 하면, Work = Available로 초기화 한다. i = 1, 2, 3, ..... , n일 때 만약 Allocation ≠ 0이면 Finish[i] = false 이고, 그렇지 않으면 Finish[i] = true로 초기화한다.
(가) 다음과 같이 되는 인덱스 i 값을 찾는다.
a) Finish[i] = false
b) Requesti ≤ Work
이런 i 값이 존재하면 (가)으로 없으면 (가)로 간다.
(가) Work = Work + Allocationi
Finish[i] = true
(가)단계로 간다.
(가) Finish[i] = false면 1 ≤ i ≤ n인 범위에서 시스템은 교착상태
2) 자원 유형마다 하나의 자원이 있는 경우 교착 상태 발견
- 대기 그래프 사용 : 자원할당 그래프에서 자원형태 노드들을 삭제하고 적절
히 연결선들을 제거하여 사용
- 대기 그래프가 사이클을 포함하는 경우 교착 상태 존재
(4) 교착상태복구(deadlock recovery)
만일 교착상태가 탐지되면 시스템은 이로부터 회복해야 합니다. 교착상태로부터 회복하기위한 두가지 방법이 있습니다. 하나는 환형 대기를 없애기 위하여 하나 또는 둘이상의 프로세스를 중지시키는 방법입니다. 또 하나는 교착상태의 프로세스로부터 자원을 선점하는 것입니다. 여기서, 교착상태의 탐지나 회복 방법에는 정보유지를 위해 탐지 알고리즘을 수행하는 비용뿐 아니라, 교착상태로부터의 회복에 의한 손실 등을 포함한 오버헤드가 발생한다는 점에 주의해야만 합니다.
1) 프로세스 중지
① 교착상태 프로세스를 모두 중지하는 방법
: 교착상태 사이클 제거시 효과적, 비용이 많이 든다
② 교착상태 사이클이 제거될 때까지 한 프로세스씩 중지 : 오버헤드가 걸림
③ 한 프로세스씩 중지를 위한 희생자 선택의 원칙
- 우선순위 - 수행된 시간과 종료 시간 - 사용한 자원의 유형과 수
- 종료를 위해 필요한 자원의 수 - 복귀하는데 포함된 프로세스의 수
- 대화식인지 일괄 처리식인지의 여부
2) 자원 선점
- 교착상태의 프로세스로부터 자원을 선점하여 다른 프로세스에게 제공
- 자원 선점시 고려해야할 문제 : 희생자 선정문제, 복귀문제, 기아상태 문제

키워드

운영체제,   상호배제,   임계구역,   교착상태,   OS