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

이재혁님의 프로필 이미지
이재혁

작성한 질문수

CS 지식의 정석 | 디자인패턴 네트워크 운영체제 데이터베이스 자료구조

페이지교체 알고리즘#1. 오프라인알고리즘(LFD) ★★★

LFD 예시 부분에서 질문

작성

·

159

0

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

 

안녕하세요 큰돌님, 주어진 예시에서 궁금한 점이 생겨서 질문 남깁니다.
오프라인 알고리즘에서 페이지 최대가 3개이고,
0,1,2,3,4,2 순으로 들어올 때
1. 0,1,2 -> 3,1,2
2. 3,1,2 -> 4,1,2
이렇게 교체하면 스와핑은 단 2번만 일어나서 이게 최대의 경우 아닌가요 ?
어째서 가장 먼 미래에 참조되는 페이지와 교체해야 하는지 잘 모르겠습니다.

답변 1

0

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 재혁님 ㅎㅎ

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

 

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

 

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

 

오프라인알고리즘

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

 

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

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

단계별 설명

  1. 초기 요청: 1, 2, 3

    • 처음 세 페이지는 비어 있는 프레임에 하나씩 적재되며, 각각 페이지 폴트가 발생합니다.

    • 현재 메모리: 1, 2, 3

  2. 다음 요청: 4

    • 현재 메모리에 있는 페이지는 1, 2, 3입니다. 각 페이지의 다음 참조는 다음과 같습니다:

      • 1은 5번째 요청에서 다시 사용됩니다.

      • 2는 6번째 요청에서 다시 사용됩니다.

      • 3은 10번째 요청에서 다시 사용됩니다.

    • 3번 페이지는 가장 늦게 사용되므로 교체하기에 최적의 선택입니다.

    • 교체: 3을 4로 교체

    • 현재 메모리: 1, 2, 4

  3. 다음 요청: 1

    • 1페이지는 이미 메모리에 있습니다.

    • 현재 메모리: 1, 2, 4

  4. 다음 요청: 2

    • 2페이지 역시 이미 메모리에 있습니다.

    • 현재 메모리: 1, 2, 4

  5. 다음 요청: 5

    • 현재 메모리에 있는 페이지의 다음 참조는 다음과 같습니다:

      • 1은 8번째 요청에서 다시 사용됩니다.

      • 2는 9번째 요청에서 다시 사용됩니다.

      • 4는 다시 사용되지 않습니다.

    • 4페이지는 다시 사용되지 않으므로 교체하기에 최적의 선택입니다.

    • 교체: 4를 5로 교체

    • 현재 메모리: 1, 2, 5

  6. 다음 요청: 1, 2, 3

    • 1페이지와 2페이지는 이미 메모리에 있으며 해당 요청에 따라 접근됩니다.

    • 3페이지 요청 시 (1, 2, 5 중 아무거나 바꿀 수 있음.) 

    • 교체: 5를 3으로 교체

    • 현재 메모리: 1, 2, 3

 

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

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

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

 

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

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

 

감사합니다.

강사 큰돌 올림.

이재혁님의 프로필 이미지
이재혁

작성한 질문수

질문하기