인프런 워밍업 클럽2 cs <day8>

2024-10-11T05:54:55.664Z

예진안

운영체제

데드락 = 교착상태

프로세스들 중 작업이 끝나기를 기다리다가 아무것도 못하는
프로세스가 이렇지도 저러지도 못하는 상황 => 공유자원이 원인
식사하는 철학자
- 식탁에 세 명의 철학자가 있고 세 개의 포크가 존재한다.
- 밥을 먹을 땐 두 개의 포크를 사용해서 먹어야된다.
- 포크 = 공유자원 , 철학자 = 프로세스
- 교착상태 => 철학자 두 명이상이 밥을 같이 먹게 될 때 포크가 부족한 상황
교착상태의 필요조건
- 상호배제 : 프로세스가 리소스를 점유했을 때 점유한 리소스가 다른 프로세스와 같이 사용될 때
- 비선점 : 프로세스a가 작업 중인데 프로세스 b가 와서 강제로 선점
- 점유과 대기 : 프로세스가 리소스를 하나 점유하고 있고 또다른 리소스를 원하고(대기하고) 있는 상태
- 원형대기 : 점유와 대기 형태가 원을 만들어 무한히 대기 중인 모습

데드락 해결

교착상태를 회피 : 교착상태가 일어날 정도로 프로세스에게 자원을 많이 할당해주지 않는다.
- 안정상태 ------------- 불안정상태
  
  --교착상태에 빠질확률 🔼--->
은행원 알고리즘
- 은행이 돈을 빌려줄 때 사업자의 자금상태를 확인하고(안정상태)
- 여러 사업자에게 돈을 빌려주고 다른 사업자가 돈을 갚았을 때 그 돈으로 다른 사람에게 돈을 빌려주는 방식
- 은행이 교착상태일 때
  - 가진 돈은 100이지만 50, 50씩 빌려주었고 A는 20을 더 빌려주면 50까지 갚겠노라 한다
  
  그래서 B에게 가서 50을 갚으라고 하고 그돈으로 A에게 돈을 빌려주려 했지만 갚지 못했다.
  -> 은행은 가진돈이 없다. 교착상태
- 은행의 안정상태 : 기업가들이 여윳돈과 대출을 했을 때 빌릴 수 있는 능력이 있는지 확인한다.

https://www.inflearn.com/users/17036/@%EA%B0%90%EC%9E%90 감자님 강의 중

위에 상태 중
p1이 자원을 4만큼 요구한다. -> 사용가능한 자원은 2이므로 거절된다.
p2에서는 자원을 2만큼 요구한다 -> 자원을 할당 시켜주고 4+2해서 6을 돌려받아
>>> 프로세스 p1과 p2의 나머지 자원을 할당시켜준다.
불안정상태: 사용가능한 자원은 1개지만 프로세스들이 요구하고자 하는 자원이 훨씬 많을 경우
교착상태를 예방하기엔 어렵고 교착상태가 일어났을 때의 해결방법이 뭐가 있을까
- 교착상태를 구분하기 -> 가벼운 교착상태 무거운 교착상태
- 가벼운 교착 상태 : 프로세스가 일정시간 안에 작업을 진행하지 않음 -> 교착상태로 간주
  
  해결 : 일정 시점마다 체크포인트에 저장을 하도록 하고 이전 체크포인트로 롤백하여 복구
- 무거운 교착 상태 : 자원할당 그래프 이용
  
  자원할당 그래프가 아래와 같이 순환구조 -> 교착상태
  
  해결 : 교착상태가 일어난 프로세스 P2를 강제 종료시켜서 원형대기를 풀어버린다.
  다시 실행 시킬 때 체크포인트로 롤백시킨다.
이렇게 자원할당 그래프를 유지하고 검사 => 오버헤드
가벼운 교첵상태에 비해 문제의 프로세스만 강제종료하면 되기때문에 효율적일지도?

알고리즘

재귀 -하노이탑

이게 왜 재귀문과 연관이 있나...
하향식 방식 계산을 한다. 원반 3을 움직이기 위해서는 원반1,2 전처리를 해야하게 때문

function ha(count, from, to,temp){

      if(count==0) return ; //기저함수
      ha(count-1,from,temp,to);
      console.log(`원반 ${count}를 ${from} 에서 ${to}로 이동`);
      ha(count-1, temp,to,from);
}
ha(3,"A","B","C");

//원반갯수count,원반들이 처음에 꽃혀있는 기둥 from,
  //원반들이 최종적으로 꽂힐 기둥to,
  // 원반들이 이동을 위해 일시적으로 사용할 기둥temp
  //원반3이 기둥c로 이동하기위해서는 (하위문제) 원반 1,2,가 기둥 B로 위치해야함

알고리즘 · 자료구조 알고리즘 운영체제 인프런워밍업클럽2기

답변 0