📌 가상 메모리

✔ 가상 메모리 개발 배경

실행되는 코드의 전부를 물리 메모리에 존재시켜야 했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다. 또한, 여러 프로그램을 동시에 메모리에 올리기에는 용량의 한계와, 페이지 교체등의 성능 이슈가 발생하게 된다. 또한, 가끔만 사용되는 코드가 차지하는 메모리들을 확인할 수 있다는 점에서, 불필요하게 전체의 프로그램이 메모리에 올라와 있어야 하는게 아니라는 것을 알 수 있다.

프로그램의 일부분만 메모리에 올릴 수 있다면...
물리 메모리 크기에 제약받지 않게 된다.
더 많은 프로그램을 동시에 실행할 수 있게 된다. 이에 따라 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

✔ 가상 메모리가 하는 일

가상 메모리는 실제의 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것으로 정리할 수 있다. 이로써 작은 메모리를 가지고도 얼마든지 큰 가상 주소 공간을 프로그래머에게 제공할 수 있다.

가상 메모리의 기본 아이디어는 프로세스는 가상 주소를 사용하고, 데이터를 사용(읽고/쓰기) 할 때 물리 주소로 변환해주면 된다는 것이다.

즉, 가상 메모리 시스템을 사용하기 위해서는 가상 주소(virtual address)와 물리 주소(physical address)가 필요하다.

• virtual address(가상 주소): 프로세스가 참조하는 주소
• physical address(물리 주소): 실제 메모리 주소

가상 주소 공간
한 프로세스가 메모리에 저장되는 논리적인 모습을 가상메모리에 구현한 공간이다. 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 물리 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있다.
예를 들어, 한 프로그램이 실행되며 논리 메모리로 100KB 가 요구되었다고 하자. 하지만 실행까지에 필요한 메모리 공간(Heap영역, Stack 영역, 코드, 데이터)의 합이 40KB 라면, 실제 물리 메모리에는 40KB 만 올라가 있고, 나머지 60KB 만큼은 필요시에 물리메모리에 요구한다고 이해할 수 있겠다.

그리고 특정 가상 주소가 어느 물리 소에 매핑되어있는지 알 수 있어야 한다. 이 때 필요한 것이 MMU이다.

• MMU(Memory Management Unit): CPU에 코드 실행시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소 값으로 변환해주는 하드웨어 장치
  즉, CPU는 가상 메모리를 다루고, 가상 메모리의 가상 주소에 접근시 MMU하드웨어를 통해 물리 주소로 변환되어 물리 메모리에 접근한다.
  

📌 페이징 시스템(paging system)

가상 메모리 시스템을 구현하는 다양한 방법 중 가장 많이 쓰이는 방법이 페이징 시스템이다.

• paging: 크기가 동일한 page로 가상 주소 공간과 이에 매핑되는 물리 주소 공간을 관리하는 것이다.
• page(page frame): 고정된 동일한 크기의 block
• paging table: 프로세스의 PCB에 Page Table 구조체를 가리키는 주소가 있는데 ,이 Page Table에는 물리 메모리에 있는 page frame 번호와 해당 페이지의 첫 물리 주소 정보를 매핑한 표이이다.
  예를 들어, 리눅스에서는 4KB로 paging을 하고, Page Table에 해당 정보를 기록/사용한다.

• p: 가상 메모리의 page 번호
• d: p안에서 참조하는 위치 (페이지 내부 주소; 변위; offset)

paging system에서 해당 프로세스에서 특정 가상 주소를 가지고 어떤 데이터에 접근하고자 하면,

→ page table에 해당 가상 주소와 그 page 번호(p)가 있는지 확인한다.

→ page 번호가 있으면 이와 매핑된 첫 물리 주소(p')를 알아낸다

→ 그러면 페이지 처음부터 얼마 떨어진 위치인지를 알려주는 변위(d)를 더하면

→ p' + d 가 실제 물리 주소가 된다.

✔ 종류

1) 다중 단계 페이징 시스템

4GB의 프로세스를 모두 페이지로 나눈다면 이 중 당장 사용되지 않는 데이터까지 페이지로 만들어질 것이고 이러면 너무 많은 페이지로 나눠질 것이다. 이렇게 하지 말고 페이징 정보를 단계를 나누어 생성하면 필요없는 페이지는 생성하지 않고 공간 절약이 가능해진다.

2) 페이징 시스템과 공유 메모리

어떤 경우에는 프로세스간 동일한 물리 주소를 가리키게 하여 공간 절약과 메모리 할당 시간을 절약 할 수도 있다.

✔ MMU와 TLB

MMU는 CPU에 코드 실행시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소 값으로 변환해주는 하드웨어 장치이다. 그러면 매번 MMU가 물리 주소를 확인하기 위해 아래 그림과 같이 메모리를 갔다와야하는데 이 과정을 좀 더 효율적으로 할 순 없을까?

이 때 사용되는 것이 TLB이다.

1) TLB

TLB(Translation Lookingside Buffer): 최근 물리 주소로 변환된 가상 주소 정보를 저장하여 페이지 정보를 캐쉬할 수 있는 하드웨어

📌 Demand Paging(요구 페이징)

위와 같은 paging system을 사용하면 프로세스에서 나눠진 page를 언제 물리 메모리에 올려놓을지에 대한 정책이 필요하다. 선행 페이징으로 하면 그냥 프로세슬를 실행하자마다 page먼저 다 올려두는 것인데 이것 보다 실제로 필요할 때 page를 메모리에 올리는 것이 좋을 것이다. 이게 demand paging이다.

• Demand Paging: 프로세스의 모든 데이터를 메모리로 적재하지 않고, 실행 중 필요한 시점에서만 메모리로 적재함
  이 때 valid/Invalid bit가 사용된다.

• Invalid: 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우 (valid는 반대)
  처음에는 모든 page가 invalid로 초기화되고, 사용되면 valid로 되는데, address translation시에 invalid bit이라면 page fault가 발생한다.

• page fault: 어떤 페이지가 물리 메모리에 없을 때 발생하는 인터럽트로, page fault가 발생하면 운영체제가 해당 페이지를 물리 메모리에 올려준다.

여기까지의 과정을 앞선 MMU와 TLB에 더해서 도표로 보면, 이러한 과정으로 진행된다.

📌 페이지 교체 정책(Page replacement policy)

✔ FIFO 페이지 교체

• 가장 간단한 페이지 교체 알고리즘으로 FIFO(first-in first-out)의 흐름을 가진다. 즉, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다는 것이다.

• 장점 : 이해하기도 쉽고, 프로그램하기도 쉽다.

• 단점
  - 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다(초기 변수 등)
  - 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
  - Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재한다.
  

✔ 최적 페이지 교체(Optimal Page Replacement)

• Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘보다 낮은 페이지 부재율을 보이며 Belady의 모순이 발생하지 않는다. 이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 주로 비교 연구 목적을 위해 사용한다.

• 장점
  - 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.

• 단점
  - 구현의 어려움이 있다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문이다.
  - LRU 페이지 교체(LRU Page Replacement)

✔ LRU: Least-Recently-Used

• 최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.

• 특징
  - 대체적으로 FIFO 알고리즘보다 우수하고, OPT알고리즘보다는 그렇지 못한 모습을 보인다.
  

✔ LFU 페이지 교체(LFU Page Replacement)

• LFU: Least Frequently Used

• 참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다.

• 특징
  - 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다
  - 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

✔ MFU 페이지 교체(MFU Page Replacement)

• MFU: Most Frequently Used

• 참조 회수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

• 특징
  최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

🧩 Reference

• https://libertegrace.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC%EC%9D%98-%EC%9D%B4%ED%95%B4