가상 메모리

가상 메모리(Virtual Memory)는 메모리 관리 기법의 하나로, 메모리를 추상화하여 사용자에게 무한한 크기의 메모리가 존재하는 것처럼 느끼게 만드는 것이다.

프로그램의 일부분이 메모리에 올라오도록 함으로써 보다 많은 개수의 프로세스를 메모리에 수용함과 동시에 아무리 큰 프로그램이라도 실행할 수 있게 해준다.

도메인 네임만 기억하고 있으면 DNS가 이 주소를 IP 주소로 알아서 변환해주는 것처럼, 메모리관리장치(MMU)가 가상 메모리 주소를 실제 메모리 주소로 매핑해주기 때문에 우리는 실제 주소를 의식할 필요없이 프로그램을 구축할 수 있다.


장점

  • 프로그램의 전체가 메모리에 올라가지 않아도 실행 가능하다.
  • 프로그램 입장에서는 물리적 메모리의 제약을 고려할 필요가 없다.
  • 동시에 여러 프로그램을 실행하는 것이 가능하다. → 동일한 응답 시간 동안 cpu의 이용률과 처리율 상승


가상 메모리 기법은 프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 요구 페이징 방식과 요구 세그먼테이션 방식으로 나뉜다. 대부분 요구 페이징 기법이 사용되므로 이 글에서는 요구 페이징에 대해서만 설명하려고 한다.



요구 페이징

요구 페이징(Demand Paging)이란, 프로세스를 구성하는 모든 페이지를 메모리에 한번에 올리는 것이 아닌, 지금 당장 사용할 페이지만 올리는 기법이다.


장점

  • 메모리 사용량 감소
    당장 실행에 필요한 페이지만을 메모리에 올리기 때문에 메모리 사용량이 감소한다.

  • 입출력 오버헤드 감소
    프로세스 전체를 메모리에 올리지 않아도 되니 입출력 오버헤드가 줄어든다.

  • 더 많은 프로세스 수용

  • 물리적 메모리의 용량 제약 X



유효-무효 비트

가상 메모리 기법에서는 프로세스의 일부 페이지만이 메모리에 올라와있기 때문에 프로세스의 어떤 페이지가 메모리에 올라와있고, 어떤 페이지가 스왑 영역에 남아 있는지에 대한 정보가 필요하다. 이를 나타내기 위한 것이 유효-무효 비트(valid-invalid bit)이며 이 정보 역시 페이지 테이블에 저장된다.

초기에 모든 페이지의 유효-무효 비트는 무효로 설정된다. 그 후 메모리에 올라가게되면(Swap in) 유효 비트로 변환되고, 다시 스왑 영역으로 내려오게 되면(Swap out) 무효 비트로 변환된다. 만약 cpu가 참조하려는 페이지가 메모리에 올라와있지 않다면 페이지 부재(page fault)가 발생하게 된다.



페이지 부재 처리

cpu가 참조하려는 페이지가 메모리에 없다면 어떻게 해야할까?
아래의 수도 코드로 알아보자.

if(페이지 부재) {
  if(빈 프레임 in 메모리) {
    디스크 스왑 영역 -> 메모리로 페이지 읽어옴(Swap in)
  }
  else {
    페이지 교체
  }
}

위에서 본 것처럼 cpu가 참조하려는 페이지가 메모리에 없는데 빈 프레임이 존재한다면 그냥 스왑 영역에서 페이지를 불러와 빈자리에 넣으면 된다.

하지만 메모리가 꽉 차있다면?
빈 공간이 생겨야 새로운 페이지가 들어갈 수 있기 때문에 메모리에 존재하는 페이지 중 하나를 스왑 영역으로 쫓아내야 한다.(Swap out) 이것을 페이지 교체라고 한다.



페이지 교체

페이지 교체를 할 때는 어떤 프레임에 있는 페이지를 쫓아낼 것인지 결정해야 한다. 이것을 페이지 교체 알고리즘이라고 한다.

디스크와의 입출력 부담을 최소화해야 하기 때문에 교체 알고리즘의 목표는 페이지의 부재 빈도를 낮추는 것이다. 따라서 앞으로 참조될 가능성이 가장 적은 페이지를 내쫓아야 한다.



페이지 교체 알고리즘

1️⃣ 최적 페이지 교체(Optimal Page Replacement)

페이지 교체에서의 최적 페이지란 현시점에서 앞으로 가장 오랫동안 참조되지 않을 페이지를 말한다. 즉, 가장 쓸데없을 것 같은 페이지를 제거하는 것이다.

이 방법은 페이지 부재를 최소로 해주지만, 프로세스들이 앞으로 어떤 페이지들을 참조할지 미리 예측하는 것이 거의 불가능하기 때문에 현실에서는 사용할 수 없다. 그래서 온라인에서 사용할 수 없다 하여 오프라인 알고리즘으로 불리기도 한다.

하지만 다른 알고리즘과의 성능 비교 기준이 되기 때문에 이 기법을 알아둬야 한다. 만약 어떤 알고리즘을 설게 했는데 그 성능이 최적 페이지 교체 기법과 유사하다면 더 이상 새로운 알고리즘을 설계할 필요가 없어지는 것!


최적 페이지 교체 기법의 다른 명칭

  • 빌레디의 최적 알고리즘(Belady’s optimal algorithm)
  • 오프라인 알고리즘(Offline algorithm)
  • OPT(Optimal Page Replacement)
  • MIN


2️⃣ FIFO(First In First Out)

FIFO 알고리즘은 적재된 지 가장 오래된(가장 먼저 올라온) 페이지를 내쫓는 기법이다. 큐 자료구조를 사용하면 각 페이지의 적재 순서를 쉽게 구현할 수 있다.


장점

  • 제거 대상을 바로 알 수 있다.(맨 앞)


단점

  • 높은 페이지 부재율
    페이지의 향후 참조 가능성을 고려하지 않고 무조건 맨 앞의 페이지를 제거하기 때문에 페이지 부재율을 높일 수 있다.

  • Belady의 모순
    페이지 부재율을 낮추기 위해 더 많은 메모리 공간을 사용하더라도 부재율이 낮아지는 것이 아니라 오히려 증가하게 된다. 발견자의 이름을 따서 Belady의 모순이라는 이름이 붙었다.


3️⃣ LRU 알고리즘(Least Recently Used)

LRU은 참조된 지 가장 오래된 페이지를 교체하는 것이다. 마지막 참조 시점이 가장 오래된 페이지가 향후 재사용될 가능성이 낮다고 판단하는 것이다.


4️⃣ LFU 알고리즘(Least Frequently Used)

LFU는 참조 횟수가 가장 적은 페이지를 교체하는 기법이다. 만약 최소 참조 횟수를 가진 페이지가 두 개 이상이라면 그중 더 오래전에 참조된 페이지(LRU)를 제거하는 것이 효율적이다.


5️⃣ 클럭 알고리즘(Clock algorithm)

클럭 알고리즘은 오랫동안 참조되지 않은 페이지를 제거하는 기법이다. LRU와 비슷하지만, 클럭 알고리즘으로 선택된 페이지가 항상 가장 오래전에 참조된 페이지를 보장하지 않는다는 점에서 둘은 차이가 있다.

포인터가 모든 프레임을 순환하며 각 프레임마다 설정된 참조 비트를 체크한다. 참조 비트가 1이면 최근에 참조되었다는 뜻이고, 0이면 참조되지 않았다는 뜻이다.

이렇게 돌면서 참조 비트가 1이면 0으로 바꾼 후 지나가고, 0이면 교체한다. 포인터가 이동하는 모습이 시곗바늘을 닮았다고 해서 클럭 알고리즘이라고 불린다.


클럭 알고리즘의 다른 명칭

  • NUR(Not Used Recently)
  • NRU(Not Recently Used)
  • Second-chance


장점

  • 빠르고 효율적

단점

  • 항상 가장 오래전에 참조된 페이지를 제거한다는 보장이 없다.



References