인프런 커뮤니티 질문&답변
작성한 질문수
5-J강의 질문
작성
·
396
답변 1
2
안녕하세요 love님 ㅎㅎ
그니까 가장 먼 미래에 참조되는 게 page swap optimal 알고리즘인데
왜 그게 최적알고리즘이냐
이런 질문이시죠? ㅎㅎ
자 그러면 왜 가장 먼미래에 참조되는 스왑 알고리즘이 최적 알고리즘인지 증명해보겠습니다.
사실 "가장 먼 미래에 참조되는 page swap optimal algorithm)은 LFD 알고리즘이라고도 합니다.
Longest Forward Distance의 약자 LFD죠.
LFD가 최적임을 증명하기 위해 LFD와 다른 KKG 알고리즘를 만들어 비교 해보겠습니다.
(Kundol King God의 약자입니다. 임의의 다른 알고리즘을 의미합니다.)
KKG란 다음과 같습니다.
요청 1,2, …, i를 LFD를 사용하여 처리
i + 1부터는 LFD와 다르게 처리합니다.
유한한 페이지요청 배열 A(길이 = n)가 존재한다고 가정할 때 두가지 경우가 있습니다.
ex1) 요청 i + 1이 페이지 폴트가 일어나지 않을 때
LFD와 KKG 둘다 스왑이 일어나지 않습니다.
ex2) 요청 i + 1이 페이지 폴트가 일어날 때
LFD와 KKG 모두 스왑을 하는데 "서로 다른 페이지"를 스왑합니다.
예를 들어 LFD는 페이지 p를 제거하고 KKG는 페이지 p'를 제거하고 필요한 페이지를 가져옵니다.
이제 두가지 경우가 생깁니다.
1) KKG는 요청 j - 1까지 p를 메모리에 유지합니다. 이후 2번스왑이 일어납니다. p를 제거, p'를 제거...
2) KKG는 요청 j - 1까지 p'를 메모리에 유지합니다. 이후 1번 스왑이 일어납니다. p'를 제거..
얼핏보면 LFD나 KKG나 동일해보이는데요.
자 여기서
KKG는 p'를 제거한 이후에 바로 p'가 나타난다면, 무조건 2번 스왑이 일어나게 됩니다. KKG에 p'가 없는 것은 "자명"하니까요.
하지만 LFD는 p를 제거한 이후 바로 p'를 나타났을 때 p가 있을 확률과 p'가 있을 확률 모두 존재하게 됩니다. 따라서 LFD가 KKG보다 더 나은 알고리즘이라고 할 수 있습니다.
즉, LFD는 최적의 페이지 교체 알고리즘이라할 수 있습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.