Algorithm

하노이의 탑

• 하향식 계산 방식의 좋은 예시
  → 재귀함수의 좋은 예시

제약 조건

• 한 번에 하나의 원반을 움직일 수 있다.

• 가장 위에 있는 원반만 옮길 수 있다.

• 아래에 작은 원반이 올 수 없다.

OS

교착상태

• 여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태

발생 원인

• 상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.

• 비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.

• 점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.

• 원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.

• 하나라도 충족하지 않으면 교착상태가 발생하지 않는다.
  → 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.

해결방법

교착상태 회피

• 프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.

• 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.

• OS는 안정상태를 유지하려 한다.

  • 안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태

• 불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.

은행원 알고리즘

작동 원리

• 프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.

• 안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.

주요 개념

• 최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양

• 할당량(Allocation): 현재 프로세스에 할당된 자원 양

• 필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값

• 가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양

단점

• 비용이 비싸고 비효율적이다.

교착상태 검출

가벼운 교착 상태 검출

• 타이머를 이용하는 방식

• 프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.

교착상태 해결 방법

• 일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.

무거운 교착 상태 검출

• 자원 할당 그래프를 이용하는 방식

  • OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.
    But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.

• OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.