[운영체제] Virtual Memory

Virutal Memory Intuition

• 가상 메모리: 사용하지 않는 페이지는 디스크에두고, 필요할 때만 메모리에 적재하여 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 만드는 메모리 관리 비법

→ 가상 메모리를 이용한다면 모든 페이지가 RAM에 없어도 프로세스 실행이 가능하다.

 

필요조건:

- OS는 각 페이지가 메모리에 있는지, 디스크에 있는지 알아야한다.

- 어떤 페이지를 메모리에 둘지, 디스크로 내릴지 교체 정책이 필요하다 (ex: LRU, FIFO)

 

가상 주소 공간의 각 페이지는 3가지 상태 중 하나이다:

- Physical main memory : 작고 빠르지만 비싸다.

- Disk: 크고 싸지만 느리다.

- 없음: 에러

 

• PTE: 페이지 테이블을 구성하고 있는 각각의 행들

- present = 1 : 메모리에 있다.

- present = 0 : 디스크에 있다.

- page fault: 필요한 페이지가 메모리에 없을 때 발생. OS가 디스크에서 해당 페이지를 가져와 메모리에 적재.

 

위 사진을 통해 Page Fault가 일어나는 과정을 살펴보자.

[흐름 정리]
1. VPN 0x8에 접근하고자 한다.
2. 이때 Page Table의 Present bit가 0이다. 따라서 Page Fault가 발생한다.

 

 

[흐름 정리]
3. OS가 디스크에서 해당 페이지를 읽어와, 물리 메모리의 빈 프레임(ex: 16)에 저장한다.
4. Page Table을 갱신해줌으로써 다음 접근부터 정상적으로 메모리에서 읽을 수 있게 되었다.

---

Virtual Memory Mechanisms

페이지 테이블, 페이지 테이블 엔트리, TLB 등등 .. 어떻게 동작하는 지 헷갈릴 수 있기 때문에(= 내 상태🫠) 이를 한번 정리하고 넘어가보자.

다음은 가상 메모리의 동작 메커니즘이다.

 

• 우선, 하드웨어 또는 OS가 TLB를 검사한다. (TLB는 페이지 테이블의 캐시 메모리로 사용된다.)
  • TLB 히트: 해당 페이지는 물리 메모리에 존재
  • TLB 미스: 페이지 테이블 확인해야 함
    • → PTE에서 present = 1 이면 메모리에 있음
    • → PTE에서 present = 0 이면 Page Fault 발생 (OS로 trap 발생)
      • 1. 메모리에서 교체할 victim page를 선택한다. 수정된 페이지면 디스크에 다시 기록한다 (dirty bit 확인)
      • 2. 디스크에서 필요한 페이지를 읽어 메모리에 적재한다.
      • 페이지 테이블을 갱신한다. (present = 1)
      • 프로세스 실행을 재개한다.
      • 이때, 스케줄러는 Page Fault가 발생했을 때 Diks I/O가 발생한 것이기 때문에 해당 프로세스를 block 해야 한다.

 

Page Fault는 어떤 명령어 실행 도중에 발생할 수 있기 때문에 하드웨어의 지원이 필요하다.

→ CPU 파이프라인을 멈추고, Fault 발생 전 명령어들은 완료시키고, 그 이후 명령어는 다시 시작할 수 있게 지원해야 한다.

 

따라서 우리의 목표는 Page Fault를 최소화하는 것이다!

(디스크의 접근은 매우 느리기 때문에 Page Fault는 시스템 성능 저하의 주요 원인이다ㅜㅜ)

 

OS가 내려야 하는 두 가지 결정이 있다.

- Page selection: 언제 디스크에 있는 페이지를 메모리로 가져올 것인가?

- Page Replacement: 어떤 페이지를 디스크에서 쫓아낼 것인가?

---

Page Selection

✅질문: 언제 디스크에 있는 페이지를 메모리로 가져올 것인가?

• Demand Paging: 요청이 생기면 필요할때마다 올린다.
  • 프로세스 첫 시작 시 메모리에 아무 페이지도 없다. 따라서 초반에는 모든 페이지마다 Page Fault가 발생하여 실행 속도가 느리다.
• Prepaging : 레퍼런스를 요청하기 전에 OS가 예측해서 미리 올린다.
  • 장점) 연속된 페이지를 올릴 수 있다면 demand보다 퍼포먼스가 좋아진다. 왜냐하면 디스크는 연속된 것을 올리면 빠르게 읽기가 가능하기 때문이다.
  • 단점) 예측 실패하면 페널티가 어마하다. 그 시간이 보장되지 않는다.
• Hints: 프로그램이 OS에게 직접 힌트를 준다.

---

Page Replacement

✅질문: 어떤 페이지를 디스크에서 쫓아낼 것인가?

• OPT: 앞으로 가장 오래 쓰이지 않을 페이지를 교체한다.
  • 단점) 미래를 알아야 하기 때문에 실제 구현이 불가능하다.
• FIFO: 메모리에 가장 오래 있던 페이지를 교체한다.
  • 장점) 만들기가 쉬우며, 모든 페이지가 평등하게 대우 받는다.
  • 단점) 계속해서 읽어야 되는 페이지들을 쉽게 빼버릴 수 있다.
• LRU: 가장 오랫동안 사용되지 않은 페이지를 교체한다.
• LFU: 가장 덜 참조했던 페이지를 교체한다.

⇒ code는 여러 번 불렸을 텐데 이런 code를 빼버리는 걸 LRU, LFU가 막을 수 있다.

⇒ 어느정도 로컬리티를 반영하지만 만들기가 어렵다.

---

Clock Algorithm

아직 알아보지 못한, 클럭 알고리즘에 대해서도 알아보자.

 

Clock Algorithm은 LRU를 단순화한 페이지 교체 기법이다.

각 페이지 프레임에는 use bit(or reference bit)가 있다.

• use bit = 0 이면 페이지를 교체한다.
• use bit = 1이면 bit를 0으로 바꾸고 hand를 전진시킨다.

그림을 통해 알아보면, 현재 hand 포인터가 0번을 가리키고 있다.

근데 use bit가 1이므로 0으로 갱신하고 다음 페이지로 이동한다.

1번 페이지도 똑같이 use bit가 1이므로 0으로 갱신하고 다음 페이지로 이동한다.

마지막으로 2번 페이지에서는 use bit가 0이므로 가장 최근에 쓰이지 않은 것으로 간주되어 페이지를 교체해 준다.