운영체제

교착상태(Deadlock)와 기아상태(Starvation)

교착상태

각 방향에서 오던 차들이 도로가 좁아져서 오도가도 못하는 상황을 교착상태라고 보자. 여기서 교착 상태를 어떻게 해결 할 수 있을까?

➡️ 한 대의 차량이 후진하면 해결 가능(선점 리소스 및 롤백)

교착 상태 발생시 여러대의 차량을 후진시켜야 할 수도 있음

기아 발생 가능성 있음(한쪽 방향이 우선권을 가져서 계속 차가들어오면 반대편 차는 계속 지나가지 못해)

P0											P1
Wait(S);							Wait(Q);
Wait(Q);							Wait(S);
.												.
.												.
.												.
Signal(S);						Signal(Q);
Signal(Q);						Signal(S);

• P0이 Wait(S)를 실행, P1이 Wait(Q)를 실행한다고 가정
• P0이 Wait(Q)를 실행할때, P0는 P1이 Signal(Q)를 실행할 때 까지 기다려야함
• P1이 Wait(S)를 실행할때, P1는 P0가 Signal(S)를 실행할 때 까지 기다려야함
• 이들 시그널 연산들은 실행될 수 없기 때문에 P0과 P1은 교착상태가 됨

한 시스템에 다음 네가지 조건 동시 성립 시 교착상태가 발생할 수 있음

다음 네가지중 하나만 성립하지 않아도 교착상태가 발생하지 않아(✂️ 모양이 해당 조건을 끊을 수 있는 방법)

🔹상호배제(Mutual exclusion)

• 두 프로세스는 동시에 같은 자원에 접근할 수 없음.
• 다른 프로세스가 그 자원을 요청하면 요청 프로세스는 자원이 해제될 때까지 대기한 뒤 사용 가능

✂️공유 가능한 리소스 설정(ex 읽기 전용 파일)

🔹점유하며 대기(Hold-and-wait)

• 프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야함

✂️프로세스가 작업을 수행하기 전에 필요한 자원을 모두 요청하고 획득해야함(최대 자원 할당)

-> 단점 : 리소스 활용도 낮음/기아 발생 가능성

🔹비선점(No preemption)

• 자원들을 선점할 수 없어야 함
• 자원이 강제적으로 해제될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후에만 해제됨

✂️이미 할당된 자원에 선점권이 없어야 함(중간에 다른 자원이 낄 수 있게 해)

-> 단점 : 기존 사용중이던 프로세스가 작업 내용을 잃을 수 있음

🔹순환 대기(Circular wait)

• 자원들이 cyclic하게 점유한 자원들을 대기해야함

✂️리소스에 고유한 번호를 할당. 번호 순서대로 리소스를 요청하도록 함

-> 단점 : 작업에 필요한 자원은 오래 전부터 할당 받고 있어야 하므로 자원 낭비 가능성

교착상태 회피 - 은행가 알고리즘(bankers algorithm)

• 상태를 안전상태(safe state)/불안전상태(unsafe state)로 분류

• 안전상태를 유지할 수 있는 요청만을 수락, 불안전상태의 경우 추후 만족하는 상태로 바뀔때까지 계속 거절

  • 현재점유량(Allocation) : 현재 프로세스 별 할당 자원의 수

  • 최대요구자원(Max) : 프로세스 별 최대 자원의 요구

  • 현재여유자원(Available) : 사용 가능한 자원의 수

  • 필요량(Need) : 프로세스 별 남아있는 자원의 수

    ​ Neex[i][j]=Max[i][j]-Allocation[i][j]

---

https://bit.ly/3FVdhDa
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.