5장 교착 상태 교착상태의 원리를 이해한다. 교착상태의 해결을 위한 예방, 회피, 탐지 그리고 회복에 대하여 알아본다.

Presentation on theme: "5장 교착 상태 교착상태의 원리를 이해한다. 교착상태의 해결을 위한 예방, 회피, 탐지 그리고 회복에 대하여 알아본다."— Presentation transcript:

1 5장 교착 상태 교착상태의 원리를 이해한다. 교착상태의 해결을 위한 예방, 회피, 탐지 그리고 회복에 대하여 알아본다.
기아상태 해결을 위한 식사하는 철학 자 문제를 이해한다. 한빛미디어(주)

2 교착 상태 교착상태의 정의 다중프로그래밍 시스템에서 결코 일어나지 않을 사건을 기다리고 있는 프로세스 ⇒ 교착상태(deadlock) 빠짐 시스템 측면에서 자원의 요구가 서로 뒤엉킨 상태 두 개 이상의 작업이 중지, 각각 사용할 수 있는 자원을 기다리는 경우  임의의 프로세스 집합에서 그 집합 내의 각각의 프로세스가 그 집합 내의 다른 프로세스 에 의해서만 발생될 사건(event)을 서로 기다리고 있는 상태 [예] 일부 차량 후진 4대의 차량 중 1대를 제거 - 외부의 간섭 필요 초기의 일괄처리 시스템에서는 자주 발생되지 않음 [그림5-1] 교착상태의 예인 교통 교착상태

3 교착 상태 교착상태의 정의 - 계속 [예제 1] 프로세스 P : 카드 판독기 점유 → 프린터 요청
    프로세스 Q : 프린터 점유  → 카드 판독기 요청 교착상태는 제한된 자원의 이용율을 높이고 시스템의 효율성을 증가시키기 위하여 사용되는 병행 처리기술과 자원 공유에서 발생하는 부작용 [그림5-2] 교착상태 표현 예 [예제 2] 테이프 구동기가 3대 일 때 프로세스 P  : 테이프 구동기 점유                           프로세스 Q  : 테이프 구동기 점유  또 다른 테이프 구동기 요청 프로세스 R  : 테이프 구동기 점유

4 교착 상태 교착상태의 정의 - 계속 - 정상적인 작동에서 프로세스의 자원 이용 순서( 요청→사용 →해제) 1) 요청
    요청 거절 : 프로세스가 요구한 자원을 다른 프로세스가 사용 중 일 때   이 프로세스는 그 자원을 할당 받을 때까지 기다림. 2) 사용     프로세스는 자원 작동 가능함.     [예] 자원이 프린터라면 프로세스는 프린터를 통해 출력 3) 해제   요구에 의해 할당 받았던 프로세스는 사용이 끝난 후 되돌려 줌. - 자원의 요청, 사용, 해제는 시스템 호출에 의해서 이루어짐 [예] 파일이나 입출력 장치를 읽거나 쓰는 것 등 ▶ 운영체제의 역활 - 프로세스가 자원 요청 – 할당 받을 수 있도록 확인과 이러한 사실 기록함. - 다른 프로세스가 사용하고 있는 자원 요청 시 그 자원을 기다리는 프로세스 큐에 입력 함.  ▶ 교착상태 - 두 개 이상의 작업이 보류(hold) 상태에 놓여  중요한 자원을 이용하기 위해 기다릴 때 일어 나는 전반적인 자원 요청의 분규 작업들이 필요로 하는 자원들을 다른 작업들이 점유해서 이용할 수 없을 때  발생

5 교착 상태 교착상태 발생 1) 파일을 요청할 때의 교착상태
- 파일, 프린터, 테이프 드라이브와 같은 비공유(비선점) 자원들이 다른 작업들에 의해 사용 중인 비공유(비선점) 자원들을 요구하는 작업들에게 할당될 때 발생 - 디스크나 데이터베이스와 같은 공유 가능한 자원에서도 발생 함. 1) 파일을 요청할 때의 교착상태 - 작업들이 실행되는 동안 파일을 요청하고 점유가 인정되면  교착상태 발생  파일 1과 파일 2를 요구한 프로그램들은 이 상태가 계속되는 한 중지 상태  [해결] - 두 개의 프로그램 중  하나가 실행 취소 - 강제적으로 제거 [그림5-3] 파일 요청할 때의 교착상태

6 교착 상태 교착상태 발생 - 계속 2) 전용장치를 할당할 때의 교착상태
▶ 전용장치들을 그룹으로 사용하면 시스템에서 교착상태가 발생할 수 있음. - 두 사용자(P1, P2)가 두 대의  테이프 드라이브를 사용하여 복사하는 경우 다음과 같은 할당요구 순서가 이루어진다고 가정   ① P1은 테이프 드라이브 1을 요청해서 그것을 얻음(할당)   ② P2는 테이프 드라이브 2를 요청해서 그것을 얻음(할당)   ③ P1은 테이프 드라이브 2를 요청하지만 허용되지 않음   ④ P2는 테이프 드라이브 1을 요청하지만 허용되지 않음  - 작업은 상대방에게 각각 다른 작업이 끝나거나 자원을 반환하기를 기다리고 있기 때문에 더 이상 진행 할 수 없음(교착상태 발생)

7 교착 상태 교착상태 발생 - 계속 3) 다중주변장치 할당할 때의 교착상태
  - 여러 프로세스들이 전용주변 장치들을 요청해서 사용하고 있고, 다른 프로세스들도 마찬가지로 행동할 때 발생한다. [예] 3개의 프로그램(P1, P2, P3)과 3개의 전용장치(테이프 드라이브, 프린터, 플로터)를 사용하는 경우 발생 다음의 순서로 장비 요구  교착상태    ① P1은 테이프 드라이브를 요청해서 얻음    ② P2는 프린터를 요청해서 얻음    ③ P3은 플로터를 요청해서 얻음    ④ P1은 프린터를 요청하지만 허용되지 않음    ⑤ P2는 플로터를 요청하지만 허용되지 않음    ⑥ P3은 테이프 드라이브를 요청하지만 허용 안됨 - 작업이 각각 다른 작업으로 점유된 자원을 기다리고 있기 때문에 더 이상 진행할 수 없음 [그림 5-4] 3개의 장치 할당요구에 의한 교착상태

8 교착 상태 교착상태 발생 - 계속 4) 스풀링 시스템에서의 교착상태
▶ 디스크에 할당된 스풀 공간에 이미 다른 작업에 의해 모두 차버린 경우 교착상태 발생 ▶ 스풀링 시스템의 교착상태 발생률을 줄이는 방법 - 예상 필요량보다 많은 공간을 스풀링 처리부(input spooler)에 배당 함.  비용 과다하게 들어감. [해결] - 스풀링 파일의 일정 포화 임계치(saturation threah-old) 설정 [예] 약 75% 정도에 이르면 새로운 작업을 읽어 들이지 못하도록 억제하는 방법으로 예방

9 교착 상태 교착상태 발생 - 계속 5) 디스크 공유할 때의 교착상태
-  디스크는 공유 자원으로 드라이브 사용에 대한 제어가 없다면 즉, 경쟁하는 프로세스들이 서로 충돌하는 명령을 내보내면  교착상태 발생 [예] P1 : read record at 20(실린더 20의 내용을 읽어라) 명령 ⇒ 디스크 헤드는 실린더 20으로 이동, P1은 중지(다음 입출력 요구) P2 : 제어권을 넘겨받아 실린더 310에 위치한 레코드에 기록 명령 할 경우 ⇒ 잠겨있지 않으면 디스크 헤드는 다시 실린더 310으로 이동 - P2는 중지 P1 : 다시 입출력 채널은 P1으로 이동, 실린더 20의 레코드 내용을 읽으라고 명령을 다시 전송 결론: 디스크 헤드가 실린더 20과 300 사이 이동 하지만 원하는 서비스를 완료할 수 없음 실린더 310 실린더 20 P1 P2 입출력 채널 디스크 제어기 디스크 헤더 이동 경로

10 교착 상태 교착상태 발생 - 계속 6) 네트워크에서의 교착상태
6)  네트워크에서의 교착상태 - 네트워크가 붐비거나 또는 입출력(I/O) 버퍼 공간을 대부분 차지하는 네트워크 시스템은 메시지 흐름을 제어하는 프로토콜이 없으면 -교착상태 발생 ※ 화살표는 메시지 흐름 - 노드 N6, N7에서 시작하여 목적지가 N2인 메시지는 N2의 출력 큐에 임시 저장 - N3, N4에서 시작하여 N1이 목적지인 메시지도 N2의 출력 큐에 임시 저장, 이때 트래픽 증가함에 따라 각 출력 큐의 크기도 증가함. - N1의 버퍼 공간이 부족, 메시지 저장할 수 없게 되면 N1은 N2로부터 메시지 수신 못하고 N2는 N1이나 다른 노드로 부터 메시지를 수신할 수 없게 됨. - N1과 N2 사이의 통신 선로 – 교착상태 - N1은 N6과 N7로부터 메시지를 전송 받을 수 있으나 N2로 전송이 불가능 -교착상태 교착상태 발생 [그림 5-6] 네트워크에서의 교착상태

11 교착 상태 교착상태의 특징 - 교착상태는 아래의 4가지 조건이 동시에 발생할 때 일어난다. 상호배제
- 적어도 하나 이상의 자원 비공유 되어야 함 한 번에 한 프로세스만이 그 자원 사용해야 함. 점유와 대기 - 적어도 하나의 자원 보유하고 현재 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 함. 비선점 - 자원은 선점될 수 없음 - 자원을 강제로 빼앗을 수 없고 그 자원을 점유하고 있는 프로세스가 끝나야 그 자원이 해제됨. 순환 대기 - 대기 프로세스의 집합 {P0, P1, …, Pn}이 있을 때, P0는 P1이 보유하고 있는 자원을, P1 은 P2보유하고 있는 자원을, P2는 P3가 보유하고 있는 자원을, …Pn-1은 Pn이 보유하 고 있는 자원을, Pn은 P0가 보유하고 있는 자원을 각각 얻기 위해 기다리는 경우

12 교착 상태 교착상태의 특징 ◈ 교착상태 발생 : 4가지 조건이 모두 만족
◈ 교착상태  발생 : 4가지 조건이 모두 만족 - 3개의 조건은 교착상태 발생에 필요한 조건이지만 충분 조건은 아님. [그림5-7] 순환 대기 ◈ 순환 대기 조건 - 처음 3개의 조건으로부터 발생할 가능성이 있고 순환 대기 조건은 점유와 대기 조건을 포함하므로 위 네 조건이 모두 독립적인 것은 아님

13 교착 상태 교착상태의 특징(징검다리 예) 강을 건너는 사람 - 프로세스, 징검다리의 돌 – 자원
두 사람이 동시에 출발하여 강 중간에서 만났을 때 -교착상태 돌을 딛는 것은 자원 할당, 발을 떼는 것은 자원해제 – 동시에 같은 돌을 디디려 한다면 교착상태 - 상호 배제 성립 : 한 번에 돌 하나에는 한 사람만 디딜수 있으므로 - 점유와 대기조건 성립 : 각 사람은 돌 하나를 딛고 다음 돌을 요구 - 비선점조건 성립 : 그 사람이 딛고 있는 돌을 강제로 제거할 수 없으므로 - 순환 대기조건 성립 : 동쪽에서 오는 사람은 서쪽에서 오는 사람을 기다리고, 서쪽에서 오는 사람도 동쪽에서 오는 사람을 기다림 → 누구도 나아갈 수 없고 서로 상대방이 딛고 있는 돌에서 발을 떼기를 기다림

14 교착 상태 교착상태의 특징 [해결방법] - 둘 중 한 사람이 되돌아 간다(복귀)
[해결방법] - 둘 중 한 사람이 되돌아 간다(복귀)    강을 건너기 전에 상대편 강가를 확인하고 출발   강의 한쪽 편에 우선권을 부여

15 교착 상태 자원 할당 그래프 –교착상태 : 시스템 자원 할당 그래프라고 하는 방향 그래프로 정확하게 기술할 수 있음
G(그래프) =(V, E)로 구성 정점 집합(V) - 프로세스 집합: P = {P1, P2, ... Pn} - 자원들로 구성된 간선 집합(E) : R = {R1, R2, ... Rn} 집합 E의 각 원소는 (Pi,rj)또는 (rj,Pi)와 같은 순서쌍으로 나타내며 Pj = 프로세스, rj = 자원 표시 프로세스 Pi로부터 자원 형태 Rj로의 연결선 : Pi→Rj로 표현 - 프로세스 Pi가 자원 형태 Rj를 요청 -이 자원을 기다리고 있는 상태 자원 형태 Rj로부터 프로세스 Pi로의 연결선 : Rj→Pi로 표현 - 자원 형태 Rj가 프로세스Pi에 할당된 것을 의미 Pi→Rj는 ‘요청 연결선’, Rj→Pi는 ‘할당 연결선‘

16 교착 상태 자원 할당 그래프 - 계속 Pi Pi 자원 할당 그래프에 사이클 존재 - 원형 안의 프로세스와 자원이 교착상태
자원 형태 Rj : 사각형안에 그려진 작은 원(검은 색 점) : 각 집합체내의 동일한 자원의 개수 할당 연결선 : 사각형안 하나의 점 지시  Pi Rj    P1, P2가 교착상태를 나타냄 요청 연결선 : 사각형 Rj만을 가리킴 Pi Rj  - 프로세스 Pi가 자원 형태 Rj의 한 자원을 요청하면 ‘요청 연결선’은 자원 할당 그래프 안에 삽입 - 요청 만족  요청 연결선은 즉시 할당 연결선으로 변환 - 프로세스가 나중에 자원을 해제하면, ‘할당 연결선’은 삭제

17 교착 상태 자원 할당 그래프-계속 - 집합 P, R, E : P = {P1, P2, P3}
   R = {R1, R2, R3, R4}    E = {P1→R1, P2→R3, R1→P2, R2→P2 ,R2→1P, R3→P3} - 자원의 사례     자원 형태 R1이 1개     자원 형태 R2가 2개     자원 형태 R3이 1개     자원 형태 R4이 3개 할당 요청 [그림 5-11] 자원할당 그래프  - 프로세스 상태 ▪ 프로세스 P1는 자원 R2의 한 개를 점유하고 , 자원 R1을 기다린다. ▪ 프로세스 P2는 R1과 R2를 각각 한 개씩 점유하고, 자원 R3을 기다린다. ▪ 프로세스 P3는 자원 R3를 점유하고 있다.

18 교착 상태 자원 할당 그래프-계속 P1→R1→P2→R3→P3→R2→P1 P2→R3→P3→R2→P2
그래프 주기가 없다면 교착상태가 발생되지 않으며 그래프에 주기 존재 - 교착상태가 발생 - 각 자원형태가 하나의 자원만을 가지면 주기는 교착상태 암시 주기가 각각 하나씩만 있는 자원의 집합에만 연관 - 교착상태 발생 주기에 포함된 각 프로세스는 교착상태 - 그래프의 주기는 교착상태의 필요 충분조건 여러 개의 자원들이 주기가 있다고 교착상태의 발생을 의미하지 않음 그래프에 있는 주기 : 교착상태 발생의 필요조건, 충분 조건은 아님 프로세스 P3이 자원 형태 R2의 자원을 요청 가정 - 사용 가능한 자원이 없기 때문에, 요청 연결선 P3→R2를 그래프에 추가 - 두 개의 주기가 시스템에 존재 P1→R1→P2→R3→P3→R2→P1 P2→R3→P3→R2→P2 프로세스 P1,P2, 그리고 P3은 교착상태이다 [그림5-12]교착상태의 그래프

19 교착 상태 자원 할당 그래프-계속 P1→R1→P3→R2→P1
프로세스 P2는 프로세스 P3이 점유하고 있는 자원 R3을 기다리고 프로세스 P3은 자원 R2를 얻기 위하여 프로세스 P1이나 프로세스 P2가 자원 R2의 해제하기를 기다림 P2는 역시 자원 R3을 보유하고 있는 P3이 해제하기를 기다림 P1→R1→P3→R2→P1 좌측 그래프 : 교착상태 없음 프로세스 p4가 자원 R2를 해제할 수 있기 때문 이 자원이 P3에 할당되면, 주기가 없어짐   자원 할당 그래프에 주기가 없다면 시스템은 교착상태가 아님 주기가 있다면 : 교착상태일 수도, 아닐 수 도 있음 [그림5-13]사이클이 있으나 교착상태가 아닌 그래프

20 교착상태 처리 전략 02 교착상태 예방 1) 상호 배제 - 상호 배제 조건은 자원의 비공유 전제
▶ 교착상태 방지- 4가지 조건에서 하나는 발생하지 않도록 ▶ Havender(1968) - 상호배제를 제외한 3가지 근본적인 방법 제안 각 프로세스는 한 번에 자기가 필요한 모든 자원을 요구해야 하며 만족되지 않으면 작업의 진행을 할 수 없다. 만일 어떤 자원을 갖고 있는 프로세스가 더 이상 요구가 허용되지 않으면 원래 점유한 자원을 반납하고 필요할 때 다시 그 자원이나 다른 자원을 요구해야 함. 모든  프로세스에 각 자원 유형별로 할당 순서를 부여한 후 순서에 따라 자원을 요구할 수 있도록 함 1) 상호 배제   - 상호 배제 조건은 자원의 비공유 전제 [예] 프린터 : 공유될 수 없으며 교착상태로 될 수 없음 읽기 전용 파일 : 공유 자원(동시 접근 허용), 대기할 필요 없음 - 상호 배제 조건 거부  교착상태 예방불가능 - 근본적으로 공유 불가능 - 쓰기에서는 배타적인 접근만이 허용, 만약 하나 이상의 프로세스가 쓰기 권한을 가지면 이 경우 교착상태가 발생

21 교착상태 처리 전략 02 교착상태 예방 - 계속 2) 점유와 대기 조건의 방지
▶ 점유와 대기 조건이 시스템에서 발생하지 않으려면(방지) - 작업 수행 전에 프로세스는 필요로 하는 모든 자원을 요청하여 획득 함. - 즉, 필요 자원 한꺼번에 요구, 허용될 때 까지 프로세스 보류  방지(최대자원 할당이라 함.) ▶ 자원 요청 방법 ① 하나의 프로세스를 위한 자원을 요청하는 시스템 호출 - 다른 시스템 호출에 앞서 미리 실행하여야 한다. ② 다른 방법 - 프로세스가 자원을 갖고 있지 않을 때만 자원 요청을 허용해야 한다. ③ 모든 프로세스는 자원들을 요청, 사용 가능하나 프로세스가 자원을 더 요청하려면, 자신에게 할당된 모든 자원들을 먼저 해제해야 한다. [예] 카드 판독기에서 디스크 파일로 자료를 복사하고, 정렬한 다음에 프린터에 결과를 인쇄하고 테이프 드라이브에 복사하는 프로세스 일 경우 프로세스가 시작될 때 모든 자원들을 요청해야 한다면, 프로세스는 먼저 카드 판독기, 디스크 파일, 프린터, 테이프 드라이브 요청해야 한다. 테이프 드라이브가 마지막 단계에서 필요하더라도, 프로세스는 전체 실행 시간 동안 프린터를 점유하게 되는 결과를 가져온다.

22 교착상태 처리 전략 02 교착상태 예방 - 계속   [예] 프로세스가 카드 판독기와 디스크 파일만 처음에 요청하게 허용하는 경우 카드 판독기에서 디스크로 복사한 다음 카드 판독기와 디스크 파일을 해제한 후 프로세스는 다시 디스크 파일과 프린터 요청 한다. 그리고 디스크 파일에서 프린터로 복사한 후 두 자원 해제하고 디스크 파일과 테이프 드라이브 요청한다. 그리고 디스크 파일에서  테이프 드라이브로 복사한 후 두 자원 해제하고 프로세스를 종료한다. [단점] ▶ 자원의 효율성이 낮음 많은 자원들이 사용되지 않으면서 오랫동안 할당되어 있다 즉, 자료가 디스크에 그대로 남아 있다고 확신할 수 있으면 카드 판독기와 디스크를 해제하고 디스크와 프린터 요구할 수 있다. 그러나 확신할 수 없으면 모든 자원 요구해야 한다. ▶ 기아 상태의 발생 가능   - 자주 쓰이는 여러 개의 자원을 필요로 하는 프로세스에 필요로 하는 자원 중 적어도 하나가 다른 프로세스에 할당되어 있는 동안 기다려야 하는 경우 발생

23 교착상태 처리 전략 02 교착상태 예방 - 계속 3) 비선점 조건의 방지
 ▶ 여러 방법으로 비선점 조건을 방지할 수 있는데 전제는 할당된 자원에 대한 선점권이 없어야 한다. - 예를 들어 하나의 프로세스가 어떤 자원을 갖고 있고, 또 다른 자원을 요구하는데 그 자원이 그 프로세스에 즉시 할당 될 수 없다면 프로세스가 기다려야 한다면 프로세스는 현재 자원을 모두 되돌려 주어야 한다. 그러면 이들 자원은 해제된다. - 선점된 자원들은 프로세스가 대기하고 있는 자원들의 리스트에 추가된다 프로세스는 자신이 요청한 새로운 자원과 해제한 과거의 자원들을 다시 확보해야 다시 시작할 수 있다. ▶ 하나의 프로세스가 어떤 자원 요청하면 : 사용 가능 검사를 함 - 사용 가능하면  할당하고 아니면 또 다른 자원을 요청하여 대기하고 있는 프로세스가 그 자원을 점유하고 있는지를 검사 한다 만약 그렇다면 대기하는 프로세스로부터 원하는 자원들을 선점하여 이들을 요청 프로세스에게 할당한다. - 요청 자원 사용 불가이고 다른 프로세스에 점유 되어 있다면 - 프로세스는 대기 - 프로세스 대기 동안 자원의 일부는 다른 프로세스가 요청하는 경우 선점될 수 있음

24 교착상태 처리 전략 02 교착상태 예방 - 계속 4) 순환 대기 조건의 방지 함수 F 정의
▶ 다른 방법으로 두 프로세스는 동일한 우선순위를 가지고 있지 않아야 하는 방법이 있다.   - 이 방법은 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후에 다시 복원하기 쉬운 자원에 이용된다. - 그러나 프린터, 카드판독기, 테이프 구동기와 같은 자원에는 - 적용되지 않음 4) 순환 대기 조건의 방지 ▶ 모든 자원의 종류에 일련의 순서를 부여하여 각 프로세스는 순서가 증가하는 순으로(오름차순) 만 자원을 요청할 수 있는 계층적인 요구 기법으로 순환 대기의 가능성을 제거하여 교착상태를 예방할 수 있다. - 예상 순서와 다른 자원 요구하는 작업들은 실재로 자원을 사용하기 휠씬 전부터 오랫동안 자원을 보유하고 있어야 하므로 상당한 낭비 초래한다. ▶ 자원 집합 R = {R1, R2 ,... Rm}을 자원 형태의 집합이라 가정함 각 자원 형태에 고유 숫자 부여 - 두 자원 비교(순서 확인) - 1대1함수 F: R → N로 정의(N은 자연수의 집합) [예] R의 집합 : 테이프 드라이브, 디스크 드라이브, 프린터 포함  F(tape drive) = 1,  F(disk drive) = 5,  F(printer) = 12 함수 F 정의

25 교착상태 처리 전략 02 교착상태 예방 - 계속 프로세스 : 오름차순으로만 자원 요청 F(Rj) > F(Ri) : 자원 Rj 요청 동일한 자원이 여러 개 필요 - 하나의 요청만 가능 [예] 동시에 테이프 드라이브와 프린터 사용 프로세스  테이프 드라이브를 먼저 요청하고 다음에 프린터 요청   [해결] Rj의 자원 요청할 때마다 F(Ri)≥ F(Rj)가 되도록  Rj의 자원 해제  순환 대기 조건 방지 순환 대기의 프로세스 집합: {P0, P1, ..., Pn} Pi는 프로세스 Pi+1이 점유하고 있는 자원 Ri를 대기 Pn은 P0가 점유하고 있는 자원 Rn을 대기 Pi+1은 자원 Ri+1을 요청하는 동안 자원 Ri를 점유하므로 모든 i에 대하여 F(Ri) < F(Ri+1)이 성립 해야 함  F(R0) < F(R1) < < (Rn) < F(R0) : 성립 의미 F(R0) < F(R0) : 불가능  순환 대기가 없음

26 교착상태 처리 전략 02 교착상태 예방 - 계속 F : 자원들의 정상적인 이용 순서에 따라 정의
[예] 테이프 드라이브가 프린터보다 먼저 필요  F(테이프 드라이브) < F(프린터) 정의 계층적 요구 - 순환대기 조건 가능성 제거, 교착상태의 예방 - 자원이 가진 번호 순서로 요구(부담) : 자원 요구순서 예측 - 번호 부여 : 자원을 사용하는 순서 반영 운영체제의 중요한 목적 사용자가 이용하기 편리한 작업 환경 조성 하드웨어나 소프트웨어의 제약(작업 환경 영향 받지 않고) 응용 프로그램 개발 Havender의 순서 배정법 장점 : 순환 대기의 가능성 제거 단점 - 사용자가 손쉽고 편리하게 응용 프로그램 작성 :지장 줄 수 있음 - 순환 대기의 예방 : 프로세스의 속도 감소, 자원에 대한 접근 거부  비효율적

27 교착상태 처리 전략 02 교착상태의 회피 교착상태 예방 교착상태의 발생 조건 - 하나라도 성립되지 않도록 자원 요구 제한
- 상호배제, 점유와 대기, 비선점의 조건 억제  간접적 순환 대기의 조건 방지(직접적 예방 결과) [결과] 장치의 효율성을 낮추고 시스템 처리량 감소 교착상태 회피 교착상태의 예방에서 보다 덜 엄격한 조건 요구 - 자원 효율적 이용 목적 교착상태의 발생 가능성 모두 제거는 아님 교착상태 발생 가능성 인정(세 가지 필요조건 허용) - 피해 가는 것 예방보다 회피가 더 병행성 허용 회피 방법 프로세스의 시작 거부(교착상태가 발생할 수 있다면) [예] 현재 프로세스의 최대 요구량 + 새로운 프로세스의 최대 요구량 : 만족  새로운 프로세스 수행(프로세스들이 최대 요구량 필요 : 최악 경우) 자원 할당의 거부 (자원을 할당시 교착상태가 발생하면 ) 프로세스가 자원 요청 - 이 자원을 할당  교착상태가 발생(자원 할당 않음) 일반적으로 은행가 알고리즘이라 한다.

28 교착상태 처리 전략 02 교착상태의 회피 교착상태 회피 방법 - 자원 요구(추가적 정보 필요)
[예] 테이프 드라이브(1), 프린터(1) 가진 시스템 P : 두 자원 해제하기 전에 먼저 테이프 드라이브 요청  프린터 요청 Q : 프린터 요청  테이프 드라이브 요청한다고 가정 프로세스마다 요청과 해제(정확한 순서 파악)  각 요청마다 프로세스 대기 여부 결정할 수 있음 ▶ 각 프로세스 미래의 요구와 해제 정보 알고 있어야(사용 가능, 할당 자원 등)  요구 수용, 대기여부 결정 가장 단순하고 유용한 형태 - 프로세스가 필요한 자원(최대치)의 숫자 선언 요청 자원(최대 값 정보) 파악  교착상태로 되지 않을 알고리즘 작성할 수 있음 교착상태 회피 알고리즘 - 시스템이 순환-대기 조건이 발생 되지 않도록 자원 할당 상태 검사 자원 할당 상태 - 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의하여 정의된다. ‘안정’(safe) 상태 : 프로세스에 자원 할당(최대치까지), 교착상태 방지할 수 있는 것.

29 교착상태 처리 전략 02 교착상태의 회피 - 계속 시스템에 안정한 순서 존재 - 시스템 안정
시스템에 안정한 순서 존재 - 시스템 안정 <P1, P2, ...., Pn> : ‘안정 순서’ 의미 모든 Pi에 대하여 - Pi 요청 자원들이 현재 사용 가능한 자원들과 j>i 인 경우에 모든 Pj가 점유하고 자원들로 충족될 수 있는 경우 Pi가  필요 자원들을 사용할 수 없다면 Pi는 모든 Pj가 끝날 때까지 기다림  Pi 는 필요 자원 확보하여 지정된 작업 끝내고 자원 반납 Pi가 종료  Pi+1은 필요한 자원 확보, 계속 처리 진행 순서 존재 ≠ 시스템 상태 ‘불안정(unsafe)’ 안정 상태 현재 모든 사용자에게 그들 모두의 작업이 일정 기간 내에 끝나도록 해 줄 수 있으면 현재 시스템의 상태는 “안정” 아니면 현재 시스템의 상태가 “불안정”

30 교착상태 처리 전략 02 교착상태의 회피-계속 안정 상태 : 교착상태 아님
교착 상태 : 불안정 상태 모든 불안정 상태 ≠ 교착상태인 것은 아님 불안정 상태 - 교착상태가 되기 쉬움 상태 안정 - 불안정 상태와 교착상태 회피할 수 있음 불안정 상태에서 운영 체제는 프로세스가 교착상태가 일어나는 방향으로 자원을 요구하는 것을 방지할 수 없음 [그림 5-14] 안정, 불안정의 상태와 교착상태 공간

31 교착상태 처리 전략 02 안정과 불안정 시스템 [예] 자기 테이프 장치(12), 프로세스(P0, P1, P2)를 가진 시스템
안정 상태 P0 : 10개의 테이프 장치 요구, P1: 4 개, P2: 9 개 요구 t0  P0 : 5개의 장치 점유, P1: 2 개 점유, P2: 2 개 점유 사용 가능 테이프 장치 : 3 개 상태1<t0 > t0 : 시스템 안정 상태 <P1, P0, P2>순서 : 안정 조건 만족 P1 : 2개의 장치 할당, 실행한 후 반납  5개의 장치 보유 P0 : 나머지 5개의 장치 할당, 실행한 후 반납(이때 10개의 테이프 장치) P2 : 필요한 장치 할당, 실행 후 반납       

32 교착상태 처리 전략 02 안정과 불안정 시스템 불안정 상태 상태2<t0 >
나머지 1 대의 테이프 장치를 어느 프로세스에게 할당하여도  만족 못함        P0 : 남아있는 장치 할당  다른 프로세스들이 장치 반납하기 전 까지 요구하지 않으면 교착상태는 피하게 됨 불안정 상태 : 교착상태 가능성 의미, 반드시 교착상태 발생 의미는 아님

33 교착상태 처리 전략 02 안정과 불안정 시스템 자원을 할당한 다음에도 시스템이 항상 안정 상태에 있을 때만 할당 허용
안정 상태에서 불안정 상태로 변환 안정 상태(상태1)에서 P2 가 장치를 1개 더 요구 (허용)  불안정 상태 상태3<t0 > P1 : 나머지 2개의 장치 할당, 실행한 후 장치 반환 - 4개의 장치 여분 P0 : 5개의 장치 할당, 최대로 10개 필요  5개 더 요청(할당 불가)  P0 대기 P2 : 추가로 6개의 장치 요청  대기  교착상태 P2: 장치 요청 허용 잘못  다른 프로세스들이 처리 종료, 자원 반납할 때까지 : P2 대기( 교착상태 회피) 교착상태 회피 알고리즘  자원을 할당한 다음에도 시스템이 항상 안정 상태에 있을 때만 할당 허용

34 교착상태 처리 전략 02 은행가 알고리즘 식 : Need[i, j] = Max[i, j] - Allocation[i, j]
교착상태 회피 - Dijkstra 의 은행가(Banker)알고리즘 - 프로세스 : 자원 할당, 요청하는 자원 종류(최대 수) 정보 필요 자료 구조 유지 - 자원 할당 시스템의 상태 - n : 프로세스 수 , m : 자원 형태의 수 - Available ; 사용 가능한 자원의 수(길이가 m인 벡터) Available[j] = k  자원형태 Rj 자원 k개 사용 가능 - Max ; 프로세스의 최대 자원의 요구를 표시하는 nⅹ m 행렬  Max[i, j] = k  Pi는 자원 형태가 Rj 인 자원을 최대 k개까지 요구 Allocation ; 프로세스에 할당되어 있는 자원 수 정의하는 n ⅹm  행렬    Allocation[i, j] = k  Pi 는 자원 형태가 Rj 인 자원을 최대 k개 할당 받음   - Need ; 프로세스의 남아 있는 자원의 수요를 표시하는 n ⅹ m행렬       Need[i, j] = k  Pi 는 자신의 작업 종료 위하여 자원 Rj 를 k개 더 요구 식 : Need[i, j] =  Max[i, j] - Allocation[i, j] Allocationi : Pi 에 할당된 자원 규정 Needi : Pi 가 자신의 태스크 종료에 필요한 추가 자원 규정

35 교착상태 처리 전략 02 은행가 알고리즘 - 계속 Allocationi := Allocationi + Requesti
Requesti 를 프로세스 Pi 를 위한 요청 벡터 Requesti[j] = k  Pi 는 Rj 자원을 k개 요구, Pi 가 자원을 요청하면 - 1단계 : Requesti ≤ Needi (남아있는 자원의 요구 수)  2단계로 아니면, 프로세스가 최대 요구치를  초과하기 때문에 오류 상태 - 2단계 : Requesti ≤ Available(사용가능 자원의 수)  3단계로 아니면 자원이 부족하기 때문에  Pi 는 대기 - 3단계 : 시스템은 상태를 수정하여 요청된 자원들을 Pi 에게 할당 Available := Available - Requesti ; Allocationi := Allocationi + Requesti Needi := Needi - Requesti  ⇒ 결과 자원 할당 상태가 안정 - 처리가 이루어지고 Pi 는 자원 할당 받음 상태가 불안정 - Pi 는 Requesti 를 기다리며 이전의 자원 할당 상태로 복원.

36 교착상태 처리 전략 02 은행가 알고리즘 - 계속 안전 알고리즘 - 시스템의 안정(불안정) 상태 발견 알고리즘
안전 알고리즘 - 시스템의 안정(불안정) 상태 발견 알고리즘 1단계 : Work(작업)와 Finish(종료)를 각각 길이가 m과 n인 벡터 Work := Available , Finish[i] := false,  i=1,2,…,n이 되도록 초기화 Available=사용 가능한 자원 수 2단계 : 다음과 같이 되는 i 값을 찾음          Finish[i] = false          Needi ≤ work   이러한 i값이 없으면 4단계로 3단계 : work := work + Allocationi          Finish[i] := true   2단계로 4단계 : 모든 i에 대하여 Finish[i] = true이면 시스템은 안정 상태

37 교착상태 처리 전략 02 은행가 알고리즘-계속 5개의 프로세스(P0 ∼ P4; 자원 형태 A, B, C; A(10), B (5), C (7) =>총 22개 할당된 자원 수 최대 자원 요구 수 남아 있는 자원의 요구 수 사용 가능 자원 수 =8개 15개(725) 안전 상태 →< P1,P3,P4, P2, P0 >순서는 안정 조건에 해당 Available 자원은 (3,3,2), P0 프로세스에 배당할 수 없음 (7,4,3) ≤ (3,3,2) : 거짓   P1프로세스에 배당 가능 Needi ≤ Available 조건 판단  (1,2,2) ≤ (3,3,2) : 참 P1 프로세스 실행한 후 배당된 자원을 해제하면 Available 자원은 (5,3,2). P3 요구는 (0,1,1) 이므로 배당 가능 :  P4, P2, P0 의 안정 조건은 만족

38 교착상태 처리 전략 02 은행가 알고리즘-계속 P1 은 A의 자원 1 개와 C의 자원 2 개를 더 요청하여 Request1 = (1, 0, 2) 가정 요청  허용 여부 결정 : Request ≤ Available 여부 확인 (1, 0, 2) ≤ (3, 3, 2) ⇒ 참 여부 검사 요청이 충족되어 다음 상태에 도달 가정   할당된 자원 수 남아 있는 자원의 요구 수 사용 가능 자원 수 200→ 안전 상태 -< P1,P3,P4, P0 , P2 > ⇒ P1 요청 허락 P4 가 (3, 3, 0)을 요청하면 자원 부족 – 허용 불가 P0 가 (0, 2, 0)을 요청하면 자원이 충분하더라도 결과로 얻어지는 상태가 불안전하기 때문에 허용 불가

39 교착상태 처리 전략 02 은행가 알고리즘-계속 은행원 알고리즘의 약점 할당할 수 있는 자원의 일정량 요구
 ⇒ 자원 - 유지보수가 필요 고장이나 예방보수 때문에 일정하게 남아 있는      자원의 수를 파악하기는 매우 어려움 사용자의 수가 일정해야   ⇒  다중 프로그래밍 시스템에서는 사용자의 수가 항상 변화함 교착상태 회피 알고리즘을 실행 시킴으로써 시스템의 오버헤드 증가 어떤 프로세스도 자원을 보유한 상태로 끝낼 수 없음 시스템에서는 이보다 더 강력한 보장 필요 사용자가 미리 그들의 최대 필요량을 알려 주도록 요구  ⇒  자원 할당 방법이 동적으로 변화함으로 - 사용자의 최대 필요량 파악 어려움 ⇒  최근 시스템 : 편리한 인터페이스 제공,  ⇒ 사용자 - 필요로 하는 자원이 무엇인지 몰라도 되게 하는 방법이 보편화되고 있다.

40 교착상태 탐지 03 교착상태 예방이나 교착상태 방지 알고리즘 사용하지 않는다면 교착상태가 발생 교착상태를 방지 하려면 다음과 같은 알고리즘을 지원해야 함.  ① 교착상태 발생 파악 : 시스템의 상태를 검사하는 알고리즘  ② 교착상태로부터 회복하는 알고리즘  [문제점] - 교착상태 탐지 알고리즘 수행 시기 결정의 어려움 - 교착상태 탐지 알고리즘을 자주 실행 : 시스템의 성능 감소 - 교착상태 프로세스 빨리 발견하여 자원의 유휴상태 방지하는 이점도 있지만 자주 실행하지 않으면 반대의 상황이 발생됨.  탐지와 회복 기법의 유의할 점 - 필요한 정보 유지하고, 탐지 알고리즘을 실행시키는 비용뿐만 아니라, 교착상태로부터 회복하는데 필요한 부담 요구 된다.       

41 교착상태 탐지 03 탐지 알고리즘 쇼사니(Shoshani)와 포크만(Coffman;1970)에 의해 제기
- 은행가 알고리즘에서 사용한 것과 비슷한 여러 가지 자료 구조들을 사용함. - Available : 사용 가능한 자원의 수를 표시하는 길이가 m인 벡터 - Allocation : 프로세스에 현재 할당된 자원의 수를 표시하는 nⅹm 행렬 - Request : 프로세스의 현재 요청을 표시하는 nⅹm 행렬 - Request[i,j] = k, pi 는 자원 형태 Rj 의 자원을 k개 더 요청 행렬 Allocation과 Request에 있는 행들을 벡터로 취급  Allocationi(할당된 자원 i) 와 Requesti(요청된 자원 j) 로 표기

42 교착상태 탐지 03 탐지 알고리즘 – 남아 있는 프로세스들에 대한 모든 가능한 할당 순서를 찾는다.
1단계 : Work와 Finish를 각각 길이가 m과 n인 벡터 Work := Available(사용 가능한 자원 수)로 초기화 한다 ( i=1,2,…,n) 일 때 Allocationi ≠ 0 ⇒ Finish[i] := false,  아니면 Finish[i] := true 2단계 : 다음과 같이 되는 색인 i 값을 찾음          Finish[i] = false         Requesti ≤ work   이러한 i 값이 없으면 4단계로 3단계 : work := work + Allocationi          Finish[i] := true   2단계로 4단계 : Finish[i] = false ⇒ 1≤ i ≤ n 범위에서 시스템은 교착상태 Finish[i] = false ⇒ pi 는 교착상태 2단계 Requesti(요구한 자원 수) ≤ work(사용 가능한 자원 수) 인 것을 확인하자마자 3단계에서 pi 의 자원을 변환하는 이유는 Requesti ≤ work 이기 때문에 pi 가 교착상태 아님을 확인 pi 자신의 태스크 종료 위하여 더 이상의 자원을 요청하지 않을 것이라고 가정, 아니면 교착상태가 후에 발생할 수도 있다.

43 교착상태 탐지 03 탐지 알고리즘 - 계속 5개의 프로세스(P0 ∼ P4); 자원 형태 A, B, C; A(7), B (2), C (6) 000 교착상태 아님 -< P0, P2,P3, P1 P4 >순서 모든 i에 대하여 Finish[i] = true P2 : C의 자원을 1 개 더 요청, Request 행렬 수정⇒ 교착상태 p0 가 점유하고 있는 자원을 요청하더라도, 가용한 자원의 수는 다른 프로세스들의 요청을 충족시킬 수 있는 정도로 충분하지 못함 <P1, P2, P3, P4 >로 구성된 교착상태 존재

44 교착상태 탐지 03 탐지 알고리즘 사용 횟수 탐지 알고리즘을 호출하는 문제
⇒  교착상태의 발생 빈도수와  교착상태가 발생하였을 때 영향을 받는 프로세스의 수에 따라 결정 교착상태 자주 발생하면 - 탐지 알고리즘도 자주 호출 교착상태로 된 프로세스들에 할당된 자원들은 교착상태가 해결될 때까지 쉬게 되고, 교착상태의 포함된 프로세스들의 수는 점점 늘어남 어떤 프로세스라도 즉시 허용할 수 없는 요청하면 – 교착상태 모든 요청 때마다 교착상태 탐지 알고리즘 호출하면 : 연산 시간 부담 이 크고, 경제적인 방법은 호출 빈도를 줄이는 것이다. [예] - 한 시간마다 또는 CPU 이용율이 40%로 저하될 때마다 호출 함.       

45 교착상태로부터의 회복 04 1) 프로세스 중지 교착상태의 회복 방법
① 오퍼레이터가 수동으로 처리 교착상태가 발생한 것을 ⇒ 오퍼레이터에게 통지 ② 시스템이 자동적으로 교착상태로부터 회복 교착상태 해결 방법 - 순환 대기를 탈피하기 위하여 단순하게 한 개 이상의 프로세스를 중지시키는 것과 교착상태의 프로세스들로부터 자원을 선점하는 것. 1) 프로세스 중지 프로세스를 중지하여 - 교착상태를 탈피한다. ① 교착상태 프로세스들을 모두 중지    확실하게 교착상태의 순환 해결 할 수 있음 - 비용이 많이 든다. - 프로세스들이 오랫동안 연산했을 가능성이 있으며, 이들 부분 결과들을 폐기하여야 하며, 후에 다시 재 연산해야 함 ② 교착상태가 해결될 때까지 한 프로세스씩 중지 프로세스가 중지될 때마다 교착상태 탐지 알고리즘 호출하여 프로세스들이 아직도 ⇒ 교착상태에 있는지 확인 함 - 부담이 상당히 큼       

46 교착상태로부터의 회복 04 프로세스 중지 - 계속 ③ 종료할 프로세스 선택 프로세스 중지 어려움
- 프로세스가 파일 갱신 중간에 중지 - 파일은 부정확한 상태가 된다. - 프로세스가 자료를 프린터에 출력 때 중지 - 프린터의 상태를 정상 상태로 환원 부분 종료 방식 사용 교착상태를 벗어나려면 어느 프로세스를 중지시켜야 하는지를 결정 ⇒ 프로세서 스케줄링과 유사한 정책 결정의 문제 - 경제적인 문제 : 최소 비용으로 중지시키는 방법 모색 - 최소비용은 정확한 수치가 아니므로 이러한 원칙으로 프로세스를 선정하는데 다음과 같은 많은 요인이 있다. 프로세스 선정 요인 - 프로세스들의 우선 순위 - 지금까지 프로세스가 수행된 시간과 앞으로 종료하는데 필요한 시간 - 프로세스가 사용한 자원 형태와 수(예; 자원들을 선점할 수 있는 지 여부) - 프로세스 종료를 위하여 더 필요한 자원의 수 - 종료하는데 필요한 프로세스들의 수 - 프로세스가 대화식인지 일괄식인지 여부       

47 교착상태로부터의 회복 04 2) 자원 선점 자원 선점 이용 하여 교착상태를 해결하려면 프로세스들로부터 자원 선점하여 교착상태가 해결될 때까지 다른 프로세스들에게 주어야 함. 교착상태를 처리하기 위하여 선점권 이용하려면 다음의 3가지 사항을 해결 해야 함. 희생자의 선택      비용 최소화 : 선점의 순서 결정 - 비용 요인 : 프로세스가 점유하고 있는 지원의 수, 실행 소요 시간 복귀 - 자원 상실로 정상 실행 불가 - 안전 상태로 복귀시키고 재 시작 해야 함 - 가장 간단한 방법은 완전히 복귀시키고(프로세스를 중지) 재 시작 이 방식은 시스템이 실행하는 모든 프로세스들의 상태에 대한 정보를 유지해야 하는 부담이 있다. 기아    - 자원들이 동일한 프로세스로부터 항상 선점되지 않도록  보장? 비용에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택되기 쉽다. - 프로세스가 단지 작은 시간 동안만 희생자로 지정됨을 확실하게 보장해야 한다. 해결 방법 : 비용 요소에 복귀의 횟수를 포함시키는 것이다.       

48 교착상태로부터의 회복 04 3)교착상태 해결을 위한 복합 방식
교착상태를 처리하는 기본적인 방식들(방지, 회피, 탐지)만으로 운영체제에서 발생되는 전체 자원 할당 문제를 취급하는 자원 할당 문제 취급은 적절하지 않음. 한 가지 가능성 - 세 가지 기본적인 방식들을 결합 시스템의 자원 종류마다 최적의 접근 방식을 채택 하는 것       

49 기아상태 05 식사하는 철학자 문제 ⇒ Dijkstra에 의해 제안
기아상태 - 사용할 수 없는 자원을 계속해서 기다리게 되는 결과를 예방하기 위해서 자원을 할당하게 될 때 발생되는 결과 5명의 철학자 : 5개의 의자로 둘러싸인 공통의 원형 테이블 공유 - 테이블 : 5개의 포크 지역 풍습 : 2개의 포크를 사용하여 식사 동시 식사(포크 10 개 필요), 2명만이 동시에 식사 가능 - 철학자는 두 개의 포크(그와 그의 왼쪽과 오른쪽 이웃과의 사이에 있는 포크)를 사용 - 철학자는 한 번에 한 개의 젓가락만을 들 수 있으며 - 왼쪽 포크를 먼저 집고 나서 오른쪽 포크를 잡음 - 그 이웃의 손에 이미 들려져 있는 포크는 들 수 없고 - 철학자가 두 개의 포크를 갖게 되면 식사함 - 식사를 마쳤을 때는 2개의 포크를 내려놓고서 생각        교착상태 - 동시에 배가 고프면(5명) 모두 자신의 왼쪽 포크를 잡고 오른쪽 포크를 잡으려 한다면 모든 철학자들은 굶게 됨 해결 : 포크 5개 더 구입, 1개의 포크 사용 식사, 최대 4명으로 제한

50 기아상태 05 식사하는 철학자 문제 var chopstick : array [0..4] of semaphore (:=1);
해결책 - 각 포크를 세마포어로 표시 철학자 : 세마포어(포크)에 대한 P조작을 수행하고 나서 포크를 잡음 포크는 그 세마포어에 대한 V조작을 수행함으로써 내려놓아짐 [공유 자료] 철학자 i의 구조 var chopstick : array [0..4] of semaphore (:=1); Chopstick : 1로 초기화 repeat    P(chopstick[i]);    P(chopstick[i+1 mod 5] ;            식사한다    V(chopstick[i]);    V(chopstick[i+1 mod 5]);      . . .      생각한다. until false; 교착상태의 발생 가능성 때문에 배제 다섯 철학자가 동시에 왼쪽 젓가락을 들었다고 가정하면 chopstick = 0 철학자가 오른쪽 젓가락을 들려고 할 때 기다리게 되어 교착 상태 발생       

51 기아상태 05 식사하는 철학자 문제 var chopstick : array [0..4] of semaphore (:=1) ;
[해결] 동시에 4명의 철학자만이 테이블에 앉도록 함 양쪽 젓가락 모두를 사용 가능할 때 만듬(임계 영역 내에서 이루어져야 함) 비대칭 해결법 사용 - 홀수 번째 철학자 : 그의 왼쪽 젓가락을 든 후에 오른쪽 젓가락을 들고 - 짝수 번째 철학자 : 오른쪽 젓가락 다음에 왼쪽 젓가락을 들게 함     var   chopstick : array [0..4] of semaphore (:=1) ;           room : semaphore (:=4)   repeat       P(room);       P(chopstick[i]);       P(chopstick[i+1 mod 5] ;                  식사한다            V(room);     V(chopstick[i]);     V(chopstick[i+1 mod 5]);         . . .       생각한다. until false; 기아상태 해결 - 기다리는 작업 발견, 기다린 시간 조사 추적 기아상태 발견 - 새로운 작업의 시작 보류 빈번한 시스템의 보류 - 처리량 감소, 신중한 접근 필요