LFD 예시 부분에서 질문

안녕하세요 재혁님 ㅎㅎ

이렇게 교체하면 스와핑은 단 2번만 일어나서 이게 최대의 경우 아닌가요 ?
>> 네 재혁님 경우의 수가 최대는 아니구... 최소의 경우의 수이며 그렇게 하는게 맞습니다.

제 예제 같은 경우 가장 먼 미래에 참조되는 페이지와 교체한다는 부분만을 보여주려고 하다 보니 이런 실수가 나온 것 같습니다. 혼란을 드려 죄송하다는 말씀을 드립니다.

수정된 설명은 다음과 같습니다.

오프라인알고리즘은 가장 좋은 알고리즘이라고 일컫는 알고리즘이며 이는 1. 더 이상 참조되지 않거나 2. 가장 늦게 다시 참조되는 페이지와 지금 요청된 페이지를 바꾸는 알고리즘(LFD, Longest Forward Distance)입니다.

페이지 참조 순서: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3

메모리 최대 페이지수 : 3개

단계별 설명

초기 요청: 1, 2, 3
- 처음 세 페이지는 비어 있는 프레임에 하나씩 적재되며, 각각 페이지 폴트가 발생합니다.
- 현재 메모리: 1, 2, 3
다음 요청: 4
- 현재 메모리에 있는 페이지는 1, 2, 3입니다. 각 페이지의 다음 참조는 다음과 같습니다:
  - 1은 5번째 요청에서 다시 사용됩니다.
  - 2는 6번째 요청에서 다시 사용됩니다.
  - 3은 10번째 요청에서 다시 사용됩니다.
- 3번 페이지는 가장 늦게 사용되므로 교체하기에 최적의 선택입니다.
- 교체: 3을 4로 교체
- 현재 메모리: 1, 2, 4
다음 요청: 1
- 1페이지는 이미 메모리에 있습니다.
- 현재 메모리: 1, 2, 4
다음 요청: 2
- 2페이지 역시 이미 메모리에 있습니다.
- 현재 메모리: 1, 2, 4
다음 요청: 5
- 현재 메모리에 있는 페이지의 다음 참조는 다음과 같습니다:
  - 1은 8번째 요청에서 다시 사용됩니다.
  - 2는 9번째 요청에서 다시 사용됩니다.
  - 4는 다시 사용되지 않습니다.
- 4페이지는 다시 사용되지 않으므로 교체하기에 최적의 선택입니다.
- 교체: 4를 5로 교체
- 현재 메모리: 1, 2, 5
다음 요청: 1, 2, 3
- 1페이지와 2페이지는 이미 메모리에 있으며 해당 요청에 따라 접근됩니다.
- 3페이지 요청 시 (1, 2, 5 중 아무거나 바꿀 수 있음.)
- 교체: 5를 3으로 교체
- 현재 메모리: 1, 2, 3

이 알고리즘은 향후 요청을 모두 알고 있다는 가정하에 가장 효율적인 교체를 합니다. 이론적으로는 최적이지만 실제 시스템에서는 미래의 요청을 알 수 없기 때문에 이 알고리즘을 직접 구현하는 것은 불가능합니다.

대신, LRU(Least Recently Used)나 LFU(Least Frequently Used) 같은 실현 가능한 대체 알고리즘이 사용됩니다.

즉, 사용할 수 없는 알고리즘이지만 다른 알고리즘과의 성능비교에 대한 상한선을 제공합니다.

해당 설명에 대한 교안수정 및 강의 재촬영, 편집 업로드는 빠르게 오늘내로 수정될 예정입니다.

제 틀린 부분을 알려주셔서 감사하다는 말씀을 드립니다.

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변