참고자료 : https://wansook0316.github.io/cs/os/2020/04/06/운영체제-정리-16-가상메모리.html

• 사용하는 부분만 메모리에 올리고, 나머지는 디스크에 보관

• 가상 메모리 논리 메모리는 물리 메모리보다 큰 공간을 가지고 있습니다. 논리 메모리는 프로세스별로 할당되는 메모리, 물리 메모리는 실제 저장이이루어지는 공간을 말합니다. 어떻게 논리 메모리는 물리 메모리보다 큰 공간을 가지게 되는 것일까요?그것은 운영체제의 가상메모리 기법에 의해 가능합니다.가상 메모리 기법은 논리 메모리와 물리 메모리를 분리하기 위한 기술이며, 이를 이용하여 논리 메모리가 물리 메모리 공간보다 커지는 것을가능하게 해주게 됩니다.그러한 가상 메모리 기술에 대해 알아보도록 하겠습니다.

• Demand Paging
  • 실제로 필요한 페이지만 메모리에 올리는 것을 말합니다. 논리 메모리의 페이지를 모두 물리 메모리에 한번에 올린다면, 실제로 아직 사용되지 않는 페이지까지 모조리 올려버리는 것이기 때문에,메모리 낭비가 발생할 것입니다.더불어 메모리 낭비는 많은 프로그램을 물리 메모리에 올리지 못하는 것을 초래할 것입니다.Demand paging 기법은 페이지 테이블에 추가 엔트리를 부여하여 구현이 되게 됩니다.사용되는 주소 영역이며 물리적 메모리에 존재한다는 의미의 Valid bit,사용되지 않고, 물리적 메모리에 존재하지 않는다는 Invalid bit 입니다.처음에는 모든 페이지 엔트리가 invalid로 초기화 되어 있고, 주소 변환 수행시에 invalid bit로 설정이 되어 있는 상황을"Page fault" 라고 합니다.
• Page fault
  • 물리 메모리에 해당 페이지가 존재하지 않는 상황에서invalid page를 접근하게 되면 MMU 라는 장치가 trap을 발생시키게 되는데요이것을 page fault trap이라고 합니다.
• Page fault의 처리과정
  • 처리과정은 다음과 같은 일련의 과정을 통해 진행됩니다.
  • 사용자 프로그램이 invalid page를 접근하면 MMU에 의해 page fault trap 발생운영체제에게 CPU 넘어오고 page fault 처리 코드 실행해당 페이지가 접근할 수 있는 페이지인지 검증 (주소 사용가능 여부, 권한 등)정상적인 요청에 대해서는 페이지를 디스크로부터 올림만약 메모리가 부족하다면 페이지 하나를 backing store로 쫓아냄I/O 요청일 경우 해당 프로세스를 blocked 상태로 만들고 ready 상태의 프로세스에게 CPU 넘겨줌I/O가 끝나면 운영체제가 페이지 테이블 엔트리를 valid로 기록추후 CPU를 잡은 프로세스가 이후의 인스트럭션 실행
• Page fault 오버헤드
  • page falut는 위에서 보시다시피 오버헤드가 매우 큰 작업입니다.page fault가 시도때도 없이 발생한다면 demand paging은 사용하지 않는게 나을 수도 있을 것입니다.따라서 page fault를 최소화하는 것은 굉장히 중요한 과제입니다.실제로 현대 운영체제에서 대부분의 경우에는 page fault가 잘 나지 않는다고 합니다.
• 메모리 교체 알고리즘
  • 그렇다면 page fault를 최소화하기 위한 물리 메모리 교체 알고리즘에 대해 알아보도록 하겠습니다.Optimal Algorithm해당 알고리즘은 우선 가장 이상적인 알고리즘입니다.즉 page fault가 가장 적게 발생하는 알고리즘입니다.미래의 페이지 참조에 따라 가장 먼 미래에 참조되는 page를 교체하는 것으로 작동됩니다.미래를 알고 있으니 가장 최선의 선택을 할 수 있습니다.그렇다면 미래의 참조는 어떻게 알 수 있을까요그것은 알 수 없습니다. 즉 해당 알고리즘은 실제로 적용할 수는 없는 알고리즘입니다.해당 알고리즘은 타 알고리즘의 성능 평가에 있어서 기준점으로 활용할 수 있습니다
• FIFO
  • 여기서부터는 실제로 사용되는 알고리즘입니다.FIFO 알고리즘은 선입선출 알고리즘으로 가장 먼저 들어온 페이지를 가장 먼저 내쫓는 알고리즘입니다.FIFO 알고리즘은 특이하게도 메모리 크기를 올려주면 오히려 성능이 낮아진다는 기이한 일이 발생하는데요,이것을 FIFO Anomaly라고 말합니다.
• LRU
  • 가장 오래 전에 참조된 페이지를 지우는 알고리즘입니다.
• LFU
  • 참조 횟수가 가장 적은 페이지를 지우는 알고리즘입니다.성능향상을 위해서 만약 최저 참조 횟수가 동일한 페이지가 복수로 존재할 경우,가장 오래 전에 참조된 페이지를 지우도록 구현할 수도 있습니다.LRU와 비교해서는 장기적인 시간 규모를 본다는 점이지만, 참조 시점의 최근성을 반영하지는 못합니다.
• Clock Algorithm
  • 앞서 소개를 드렸는데 아이러니하게도 LRU와 LFU는 실제로 페이지 교체 알고리즘으로 활용할 수 없다고 합니다.왜냐하면 페이징 시스템에서는 메모리에 이미 존재하는 내용에 대해 운영체제는 알수가 없기 때문입니다. 즉 page fault가 발생할 때에만알 수 있기 때문에 LRU, LFU는 가상 메모리 관리 시스템에서는 사용할 수 없고 버퍼 캐싱이나, 웹 캐싱에서 활용된다고 합니다.따라서 실제로 가상 메모리 관리 시스템에서는 Clock 알고리즘을 사용합니다.LRU의 근사한 알고리즘으로 reference bit를 사용해서 교체 대상 페이지를 선정합니다.이후 포인터를 이동하는 도중 reference but 1 -> 0으로 교체하고,reference bit가 0인 것을 찾으면 해당 페이지를 교체하게 됩니다.