어떻게 교착상태를 판별하는가
교착 상태 회복- 교착상태 탐지 알고리즘
은행가 알고리즘의 safety 알고리즘과 비슷합니다.
뭐가 다를까요?
은행가 알고리즘은 claim만 가지고 판별합니다.
이건 진짜 할당해봐서 프로세스를 끝내는 것을 결정합니다.
자세히 분석해봅시다.
왜 Allocation이 0이면 True로 바꾸고 아니면 False로 볼 까요?
할당을 안 하고 있는 애들은 이미 자원이 필요하지 않습니다.
3번은 끝낼 수 있기 때문에 끝냈다고 치면 됩니다.
끝낼 수 있는 프로세스를 찾지 못하면 2번 루프를 끝냅니다.
이 알고리즘의 시간 복잡도는 몇일까요?
O(n^2m)입니다.
i라는 프로세스를 찾아내기 위해서 n개의 프로세스를 조사해야 합니다.
1개의 프로세스를 조사할 때 자원의 수(m)를 조사합니다.
이 과정을 n번 다시 합니다.
만약 이 예제에 대해 알고리즘을 적용하면 Finish는 다 어떻게 되어있을까요?
P0를 끝낼 수 있으니
Finish는 T, F, F, F, F가 되겠지요
그리고 work가 010이 돼서 다른 프로세스를 끝내지 못합니다.
그렇게 되면 4번으로 가고 deadlock에 걸립니다.
탐지 알고리즘을 얼마나 자주 호출해야 하는가?
교착 상태 회복 방법 2가지
자원 선점 - 자원을 뺏는 것
뺏긴 것은 하던 일을 못 맞췄으니 기다리빈다.
프로세스 강제 종료 processprocess abortion
모두 제거하는 방법이랑 하나씩 제어하는 방법이 있습니다.
교착상태가 일어난 프로세스 하나씩 제거하는 것은 부담이 큽니다.
그래서 한꺼번에 종료합니다.
희생자 - 누구를 먼저 죽일지
- 프로세스 우선순위 - 우선순위가 낮은걸 종료
- 프로세스가 수행된 시간과 앞으로 수행할 시간 - 수행할 시간이 작은걸 종료
- 프로세스가 사용한 자원 수와 유형, (선점과 복원 restore이 쉬운지) - 앞으로 사용할게 많이 남은 것 종료
- 프로세스가 앞으로 필요한 자원 수 - 자원수가 적은 것을 종료
- 함께 종료해야 하는 프로세스 수 - 함께 종료해야 하는 것이 적은 것을 종료
- 대화식/일괄식 - 일괄식을 먼저 종료
4번입니다.
자원 선점 resource preemption
우리가 관심을 가져야 할 것은 뺏거나 죽이거나 하면 누군가는 계속 죽임을 당합니다. 그것을 "기아상태"라고 합니다.
해결하려면 내가 얼마나 희생자가 되었는가를 저장하는 방법이 있습니다.
프로세스의 동시성, 교착 상태, 기아를 설명하는 예시
쌍으로 포크를 써야 합니다.
포크는 공유자원입니다.
포크의 수가 5개이니2명입니다.
포크를 세마포 코드로 만들기
계속 실행되고 있습니다.
내가 왼쪽 포크를 집는다. => wait(fork [i])
내가 오른쪽 포크를 집는다. => wait(fork [i+1] % 5)
공유자원 모두 사용합니다!
signal로 포크를 놓는 것입니다.
만약 프로세스가 일제히 왼쪽 포크를 집는다면?
이런 상태가 되면 한 명도 식사를 하지 못합니다.
즉, 교착상태가 발생합니다.
교착상태의 4조건
- 상호 배제
포크는 2 사람이 집을 수 없습니다.
- 점유와 대기
한 사람이 포크를 잡았을 때 다른 사람이 포크를 가지려고 대기하고 있습니다.
- 비선점
한 사람이 포크를 잡으면 다른 사람은 잡을 수 없습니다.
- 순환 대기
사람 모두 다 오른쪽 사람이 포크를 놓기를 기다리고 있습니다.
이 상황에서 다음번에 적어줘야 할 것은 reqeust입니다.
request와 need는 다릅니다.
need는 가짜로 (프로세스가 시작할 때 최대 필요량 설정하는 것)
request는 진짜로
reqeust를 그리려면
실선 화살표로 상황을 마무리 지어야 합니다.
교착 상태 예방법
4가지 필요조건 중 1가지라도 정책을 통해 "제거"하는 것입니다.
정책 예시)
우선순위가 높은 프로세스가 포크를 먼저 가진다.
순환 대기를 없애버리는 예시도 있습니다.
4번 프로세스는 0번 포크 요청하고 4번 포크를 요청합니다.
짝수는 왼쪽 먼저 집고 오른쪽 집을 수 있습니다.
시작 거부를 하는 예시입니다.
클레임이 많아지면 할당을 거부하듯이
철학자 4명만 테이블에 앉게 하는 것입니다.
"코드 설명"
세마포에 들어있는 정수 변수는 사용 가능한 자원 수입니다.
포크는 5개 자리는 4개 있습니다.
자리만큼 wait 하고
왼쪽 포크 집고 오른쪽 포크 집고 fork만큼 wait 합니다.
그러면 끝낼 수 있습니다.
그러면 계속 못 먹는 사람이 생깁니다.
교착상태의 해결 방법
- 예방 - 필요조건 중 하나만 제거
- 회피 - 프로세스 시작 거부, 자원 할당 거부
- 회복 - 프로세스 강제 종료, 자원 선점(뺏는 것)
스케줄링의 개념
스케줄링이라는 뜻은 cpu스케줄링, 메모리 스케줄링, 네트워크 링크 스케줄링 모두 다 맞는 말입니다.
보통은 cpu 스케줄링을 의미합니다.
사용자가 만든 프로세스와 커널이 만든 프로세스 모두 다 관리하는 것입니다.
스케줄링의 목적
스케줄링의 기준 요소
버스트란?
프로세스가 실행하는 것을 봅시다.
입출력 버스트
프로세스가 read from file을 하면 cpu를 사용하지 않고 대기하는 순간이 존재합니다.
이 때는 프로세스가 "대기상태"로 변합니다.
프로세서 버스트
프로세스가 load, add, read 같은 것을 할 때 "실행상태 <-> 준비상태"로 변합니다.
스케줄링 기준이 "cpu 버스트"입니다.
cpu 버스트 시간 분포
cpu를 유용하게 나눠 쓸 수 있게 됩니다.
'Computer Science > OS' 카테고리의 다른 글
| SJF, FIFO, 라운드로빈(RR), 다단계 큐(MQL), 다단계 피드백 큐(MLFQ), 응답비율(HRN) (0) | 2021.11.29 |
|---|---|
| 스케쥴링 큐, 장기,단기,중기 스케줄링/ 선입선처리, 최소작업, 우선순위 스케줄링 (0) | 2021.11.23 |
| 은행가 알고리즘 코드, 시간복잡도, 회복 알고리즘 (0) | 2021.11.16 |
| 교착상태 회피 - 은행가 알고리즘 자세히 (0) | 2021.11.15 |
| 교착상태 회피하는법 (0) | 2021.11.09 |
