인프런 워밍업 클럽 - CS Day 8
Algorithm하노이의 탑하향식 계산 방식의 좋은 예시→ 재귀함수의 좋은 예시제약 조건한 번에 하나의 원반을 움직일 수 있다.가장 위에 있는 원반만 옮길 수 있다.아래에 작은 원반이 올 수 없다.OS교착상태여러 프로세스가 서로 다른 프로세스의 작업이 끝나길 기다리다가 아무 작업도 수행되지 않는 상태발생 원인상호 배제 : 공유 자원은 한 번에 하나의 프로세스만 사용할 수 있다.비선점 : 다른 프로세스가 사용 중인 자원을 강제로 빼앗을 수 없다.점유와 대기 : 프로세스가 이미 자원을 보유한 상태에서 다른 자원을 요청하며 대기한다.원형 대기 : 점유와 대기를 하는 프로세스들의 관계가 원형이다.하나라도 충족하지 않으면 교착상태가 발생하지 않는다.→ 교착 상태를 예방하는 것을 구현하기는 매우 어려워서 교착 상태를 해결하는 방향으로 발전됐다.해결방법교착상태 회피프로세스들에게 자원을 할당할 대 어느 정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정 상태로 나뉜다.OS는 안정상태를 유지하려 한다.안전 상태: 모든 프로세스가 요구한 최대 자원을 할당받아 실행을 완료할 수 있는 상태불안정상태에 있더라도 무조건 교착상태에 들어가는 것이 아니라 교착상태에 빠질 확률이 높아지는 것이다.은행원 알고리즘작동 원리프로세스가 자원을 요청할 때, 그 요청이 시스템을 안전 상태로 유지할 수 있는지 확인한다.안전 상태를 유지할 수 있는 요청만 수락하고, 불안정한 상태를 초래할 수 있는 요청은 거절한다.주요 개념최대 요구량(Max Need): 프로세스가 실행을 완료하기 위해 필요한 최대 자원 양할당량(Allocation): 현재 프로세스에 할당된 자원 양필요량(Need): 최대 요구량에서 현재 할당량을 뺀 값가용량(= 시스템 총 자원, Available): 시스템에서 현재 사용 가능한 자원 양단점비용이 비싸고 비효율적이다.교착상태 검출가벼운 교착 상태 검출타이머를 이용하는 방식프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다.교착상태 해결 방법일정 시점마다 체크포인트를 만들어 작업을 저장하고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백한다.무거운 교착 상태 검출자원 할당 그래프를 이용하는 방식OS가 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다.But. 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스가 발생하지 않는다.OS에서 프로세스가 어떤 작업을 사용하는지 지켜보고 교착상태가 발생했다면 해결한다.
