2022. 11. 16. 11:33ㆍcs 상식/운영체제
데드락이란?
교착상태 :여러 프로세스가 서로 다른 프로세스의
작업이 끝나기를 기다리다가 아무도 작업을 진행하지
못하는 상황을 교착상태라고 한다.
ex) 퇴근길 (꼬리물기를 해서 도로가 마비 되었을 경우
앞에서 길을 터줘야 하는 데 이러지도 저러지도 못하는 상황이다
이럴때는 누군가가 길을 터줘야 한다,)
=이게 발생하는 이유는 공유자원입니다.
퇴근 예시에서 공유자원은"도로"이다 공유 되는 도로를 서로 차지하려다가
교착상태가 발생하게 된다.
ex)유명한 예시 / 식사하는 철학자
1.원형으로 된 탁자에 맛있는 음식이 있고 의자가세개가 있다
2.각자 앉아서 먹으려고 하는데포크는 3개이다.
3.음식을 먹으려면 2개씩 포크가 필요하다
4.한 철학자가 음식을 먹는 동안 다른 철학자가 기다린다.
=이렇게 되면 문제가 없지만 , 문제가 발생한다
그러나
우연히 철학자 세명이 동시에 포크를 쥐었다
아무도 양보하지 않으면 다 식사를 못하게 된다.
교착상태의 필요조건
:필요조건 4가지 있는데 하나라도 충족되지 않으면 교착 상태는 발생하지 않는다 .
1.상호 배제:어떤 한 프로세스가 리소스를 점유했다면 그 리소스는 다른 프로세스에게 공유가 되면안된다.
ex) 포크 /먼저 포크를 집었다면 그 포크는 다른사람이 사용할수 없는 리소스이다.
2.비선점이다, 프로세스 a가 리소스를 점유하고 있는데 프로세스b가 리소스를 빼앗을수 없어야 한다.
ex)철학자 a가 들고 있는 포크를 철학자 b가 뺏을수 없다.
3. 점유와 대기 이다.
어떤 프로세스가 리소스 a를 가지고 있는 상태에서 리소스 b를 원해야 한다,
ex)식사하는 철학자에서 오른쪽 포크를 가지고 왼쪽 포크를 기다리는 상태이다.
4.원형대기이다.
점유와대기를 하는 프로세스의 관계가 원형을 이루고 있다는 것이다.
ex)서로가 서로의 포크를 원하는 상황이 원형을 이룬다.
=이 필요조건에서 하나라도 충족되지 않는다면 교착상태는 발생하지 않는다.
운영체제를 연구하는 사람들은 교착상태 예방하려 했으나 되지 않아
교착상태에 빠졌을때 해결하는 방법으로 연구하게 되었다 .
교착 상태 해결 방법
교착상태 회피 :
프로세스들에게 자원을 할당할때 어느정도자원을
할당해야 교착상태가 발생하는지 확인해서 교착 상태가 발생하지
않게 자원을 할당을 한다.
교착상태 회피는 전체자원의수와 할당된 자원의 수를 기준으로
안정상태와 불안정상태로 나뉜다.
=운영체제는 최대한 안정 상태를 유지하기 위해 자원을 할당한다,
불안정 상태에있더라도 교착상태에 무조건 빠지는것이 아니라 확률이 높아지는 것이다.
ex)은행원 알고리즘
대출을 해주는 상식적인 알고리즘이다
은행은 돈이 1000만원이 있다
1.사업가 a는 500만원을 빌렸다.
2.사업가 b는 400만원을 빌렸다.
3.그럼 은행에는 100만원이 남았다
4.시간이 지나서 사업가 a에게 돈을 갚으라고 하는데
지금은 갚지 못하고 200만원을 더 빌려주면 그걸로
돈을 더 벌어서 갚아드린다고 한다.
5.은행은 지금 100만원 밖에 없기에 사업가b에게 돈을 갚으라고
하는데 b도 갚을수 없고 200만원을 더 벌어서 갚는다고 말한다.
결과: 은행은 누구에게도 돈을 빌려주지도 못하고 받지도 못하는 교착상태에 빠진다,
이런상황을 피하기 위해 은행의 여윳돈과 사업가들에게 빌려준 돈을 보고
대출가능한 상황인지 보고 빌려주는 데 이것을 은행원 알고리즘이라고 한다.
ex)운영체제에서 은행원 알고리즘 구현하는 방법
시스템 총 자원:
운영체제는 프로세스들에게 자원을 할당하기 전에
자기가 가지고있는 전체 자원의 수를 알고 있어야 한다 그것을 시스템 총 자원이라고 부른다.
총자원 : 20 개
결과: 현재 안정상태인 운영체제는 사용가능 자원2개가 있고 이 자원들을
가지고 프로세스들의 요청이 예상되는 자원을 제공 할수 있따,
p1이 4개를 요청하면 사용가능 한 자원이 2개이기에 p2에 요청을
받는다 전부 거기에 할당하면 p2는 작업을 마치고 6개를 반납하면
p3와 p1이 요청한 것을 전부 할당 할수 있다.
결과: 불안정 상태있더라도 모든 프로세스가 최대자원을 요청하지 않느다면
교착상태에 빠지지 않지만 최대한 빠지지 않게 유지하는게 중요하다
은행원 알고리즘은 비용이 비싸고 비효율적이라 , 교착상태의 발생은 허용하지만
이를 해결하는 방식을 찾는다.
운영체제를 연구하는 사람들은 어떻게 교착상태를 검출할까??
:2가지 방식으로 검출 할수 있다는 것을 알게되었따.
1. 가벼운 교착 상태 검출이라고 부른다
타이머를 이용하는 방식 프로세스가 일정시간동안 작업을 진행하지 않는다면
교착상태가 발생했다고 가정하고 그것을 해결한다.
해결 방법
: 일정시점마다 체크 포인트를 만들어작업을 저장하고 타임아웃으로 교착상태가 발생했다면
마지막으로 저장했던 체크 포인트로 롤백하는 것이다.
10초전 상태로 다시 시작해!
ex) 게임의 이전 버전이나 서버를 롤백 했다 라는 거와 동일한 메커니즘이다.
2. 무거운 교착 상태 검출
"자원할당 그래프"를 이용하는데 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지
지켜보고 교착상태가 발생했다면 해결한다.
그러면 그래프를 이용해서 어떻게교착상태가 발생했는지 알수가있는가?
프로세스들은 각자자원을 차지 하고 있고 분홍색화살표로 다른 자원을 요청하고 잇다
순환구조가 생기지 않기에 교착상태가 없는 그래프이고
왼쪽은 순환구조가 생기기에 교착상태가 생기는 그래프이다 ,
교착상태를 일으킨 프로세스를 강제 종료하고 다시 실행 시킬때 체크 포인터로 롤백을 시킨다
이방식은 운영체제가 지속적으로 자원 할당그래프를 유지하고 검사해야 하기 에
오버해드가 발생한다 하지만 가벼운 교착상태검출에서 발생할수있는 억울하게 종료 되는 프로세스는 발생하지 않는다.