페이지 교체

[Tokwasp]

1. 페이지 교체란 무엇인지 설명해주세요.
2. 요구 페이징이란 무엇이고, 요구 페이징에서 Page Fault가 발생했을 때, 처리되는 Page 교체 순서에 대해 설명해주세요.
3. 페이지 교체 알고리즘의 종류와 각각의 특징에 대해 설명해주세요.
   • 페이지 교체 알고리즘
     • LRU 알고리즘은 어떤 특성을 이용한 알고리즘이라고 할 수 있을까요?
     • LRU 알고리즘을 구현한다면, 어떻게 구현할 수 있을까요?
     • LRU 알고리즘의 단점을 설명해 주세요. 이를 해결할 수 있는 대안에 대해서도 설명해 주세요.
4. Swapping이란?
   • Swapping 시 발생할 수 있는 문제점?
   • 외부 단편화를 해소할 수 있는 방법 두 가지 제시

[Tokwasp]

❓ 페이지 교체란 무엇인지 설명해주세요.

🌱 [ 페이지 교체 ] :

할당된 물리 메모리가 가득찬 상태에서 새로운 페이지를 올리기 위해 특정 페이지를 메모리에서 내보내는 작업

❓ 요구 페이징이란 무엇이고, 요구 페이징에서 Page Fault가 발생했을 때, 처리되는 Page 교체 순서에 대해 설명해주세요.

🌱 [ 요구 페이징 ] :

프로세스의 모든 데이터를 메모리에 올리지 않고 필요한 부분만 메모리에 적재 하는 방법 ( 비연속적 할당 )

[ 처리 과정 ] :

1. 프로세스 실행중 PMT 테이블을 확인 하여 존재 비트가 0 -> 메모리 적재 되지 않은 상태 ( 페이지 폴트 )
2. 프로세스에 할당된 물리 메모리가 가득 차서 메모리에서 페이지를 내려야 하는 경우 ( 페이지 교체 )
3. 페이지 교체 알고리즘에 따라 페이지를 교체 한다.

❓ 페이지 교체 알고리즘의 종류와 각각의 특징에 대해 설명해주세요 / LRU 알고리즘

🌱 [ Min 알고리즘 ( OPT ) ] :

• 앞으로 가장 오랫동안 참조 되지 않을 페이지 교체
• 미래를 알아야 하므로 실현 불가능한 방법 이지만, 교체 기법의 성능 평가 도구로 사용 된다.

🌱 [ FIFO 알고리즘 ] :

• 들어온 순서를 기록하여 가장 먼저 들어온 페이지 순서 대로 교체 하는 알고리즘
• 지역성과 연관이 없으므로 페이지 폴트 수가 증가 하는 경우가 있습니다.

🌱 [ LRU ( Least Recently Used ) 알고리즘 ] :

• 가장 오랫동안 참조 되지 않은 페이지를 교체 하는 알고리즘
• 참조한 시간을 기록 해야 해서 부하가 있지만, 시간 지역성에 기반을 둬서 효율이 Min 알고리즘에 근접함
• 연결 리스트를 통해 참조 될때 마다 맨앞으로 이동, 제거 할때 리스트의 마지막 제거
• 시간 정렬의 필요성이 있기 때문에 오히려 Clock 알고리즘이 나을수 있다.

🌱 [ LFU ( Least Frequently Used ) 알고리즘 ] :

• 가장 참조 빈도가 낮은 페이지를 교체 하는 알고리즘
• 최근 적재된 참조될 가능성이 높은 페이지가 교체될 가능성이 있다.

🌱 [ NUR ( Not Used Recently ) 알고리즘 ] :

• Bit Vector를 활용한 LRU 보다 적은 부하로 비슷한 성능을 내는 알고리즘
• Bit Vector는 PMT 테이블에 있다.

🌱 [ Clock 알고리즘 ] :

• Bit Vector중 참조 비트만을 활용 하고, Pointer( 시계 ) 를 돌리면서 교체 Page 결정
• 먼저 적재된 Page가 교체될 가능성이 높아 FIFO와 유사
  

❓ Swapping이란?

🌱 [ Swapping ] :

• 프로세스를 메모리에서 디스크로 이동시키거나 디스크에서 다시 메모리로 가져오는 기법

[ Swapping 시 발생할 수 있는 문제점 ] :

• 외부 단편화 발생 하여 메모리 내에 단편화가 발생 할 수 있다.
• 프로세스를 디스크에서 메모리로 옮길때 디스크 I/O가 발생하여 성능 저하가 생길 수 있다.
• 스와핑 후 다시 실행 하면 디스크에서 메모리로 불러오는 시간이 필요 하여 응답시간이 증가 할수 있다.