콘텐츠로 건너뛰기
Home » Blog » 메모리 계층과 페이지 교체 알고리즘

메모리 계층과 페이지 교체 알고리즘

  • os

메모리 계층

  • 레지스터, 캐시, 주기억장치, 보조기억장치로 구성되어 있다.
  • 레지스터 : CPU 내의 작은 메모리, 휘발성, 속도 가장 빠름, 기억 용량이 가장 적음
  • 캐시 : CPU 내의 L1, L2 캐시를 지칭한다. 휘발성, 속도 빠름, 기억 용량이 적음
  • 주기억장치 : RAM을 가리킨다. 휘발성, 속도 보통, 기억 용량 보통
  • 보조기억장치 : HDD, SDD를 일컬으며 비휘발성, 속도 낮음, 기억용량이 큼

계층이 존재하는 이유

  • 더 빠른 접근과 처리속도 증가
    • 특정 데이터에 많이 접근하게 되는데 좀 더 작은 캐시 메모리에 해당 데이터가 있다면 더 빠르게 해당 데이터에 접근이 가능해진다.
  • 비용 효율적 사용
    • 캐시 메모리는 비싸고 램 등 아래로 갈수록 비용은 더 저렴하다.
    • 계층이 있고 캐싱 때문에 비용을 좀 더 효율적으로 쓸 수 있다.
  • 자원의 효율적 사용
    • 메모리 계층 구조는 자주 접근하는 데이터는 빠른 메모리에, 덜 접근하는 데이터는 느린 메모리에 저장하여 자원을 효율적으로 사용할 수 있다.
    • 이를 통해 거의 접근하지 않은 데이터에 비싸고 빠른 메모리를 사용하지 않게 되어 자원을 낭비하지 않게 된다.

가상 메모리

  • virtual memory
  • OS에서 사용되는 메모리 관리 기법의 하나
  • 컴퓨터가 실제로 이용가능한 메모리 자원(실제 주소, physical address)을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 것
  • 참고
    • 가상주소 : MMU와 페이지 테이블에 의해 실제 주소로 변환된다.
    • 페이지 : 가상 메모리를 사용하는 최소 크기 단위
    • 프레임 : 실제 디스크나 메모리를 사용하는 최소 크기 단위 (페이지와 구분!!)

페이지 테이블

  • 가상 메모리는 가상 주소와 실제 주소가 매핑되어있는 페이지 테이블로 관리되며 이 때 속도 향상을 위해 캐싱계층인 TLB를 쓴다.
  • 가상 주소에서 바로 페이지 테이블을 가는게 아니라 TLB에서 있는지를 확인하고 만약 없다면 페이지 테이블로 가서 실제 주소를 가져온다.

페이지 폴트

  • 앞서 설명한 것처럼 가상메모리는 작은 메모리를 매우 큰 메모리로 보이게끔 하는 것
  • 참조하려는 메모리 영역이 실제에는 없을 수도 있다.
  • 즉, 가상메모리에는 존재하지만 실제 메모리인 RAM에는 현재 없는 데이터나 코드에 접근할 경우가 있으며 이 때 페이지 폴트가 발생한다.
  • 이 때 메모리의 당장 사용하지 않는 영역을 하드디스크로 옮기고 하드디스크의 일부분을 “마치 메모리처럼” 불러와 쓰는 것을 스와핑이라고한다. 

페이지 폴트 과정

  1. 어떤 명령어가 유효한 가상주소에 접근했으나 해당 페이지가 만약 없다면 트랩이 발생되어 운영체제에 알리게 된다.
  2. 운영체제는 실제 디스크로부터 사용하지 않은 프레임을 찾는다.
  3. 해당 프레임을 실제 메모리에 가져와서 페이지 교체 알고리즘을 기반으로 특정 페이지와 교체한다. (이 때 스와핑이 발생)
  4. 페이지 테이블을 갱신시킨 후 해당 명령어를 다시 시작한다.

스레싱

  • Thrashing : 페이지 폴트가 증가하여 CPU 이용율이 급격하게 떨어지는 현상
  • 메모리의 페이지 폴트율이 높은 것을 의미한다.
  • 메모리에 너무 많은 프로세스가 동시에 올라가게 되면 스와핑이 많이 일어나서 발생한다.
  • 페이지 폴트가 일어나면 CPU 이용률은 낮아진다.
  • CPU 이용률이 낮아지면 운영체제는 CPU의 가용성을 높이기 위해 더 많은 프로세스를 메모리에 올리게 된다.
  • 이러한 악순환이 반복되어 스레싱이 발생하게 된다.
  • 하드웨어적 해결법
    • 메모리 증가
    • HDD 대신 SSD 사용
  • 운영체제적 해결법
    • 작업세트
      • working set
      • 프로세스의 과거 사용이력을 기반으로 많이 사용하는 페이지 집합을 만들어 한꺼번에 미리 메모리에 로드하는 것
    • PFF
      • page fault frequency
      • 페이지 폴트 빈도를 조절하는 방법
      • 상한선과 하한선을 만들고 상한선에 도달한다면 프레임을 늘리고 하한선에 도달한다면 프레임을 줄이는 방법

가상 메모리의 필요성

  • 주기억장치의 효율적 관리(스와핑)
    • 하드디스크를 주기억장치에 대한 캐시로 설정하여, 당장 사용하는 영역만 유지
    • 쓰지 않는 데이터는 하드디스크로 옮김
    • 필요할 때에만 램에 데이터를 불러와 올리고 다시 사용하지 않으면 하드디스크로 내림으로써 램을 효과적으로 관리
  • 메모리 관리의 단순화
    • 각 프로세스마다 가상메모리의 통일된 주소 공간을 배정할 수 있으므로 메모리 관리가 단순해진다.
  • 메모리 용량 및 안정성 보장
    • 한정된 공간의 램이 아닌 거의 무한한 가상메모리 공간을 배정함으로써 프로세스들끼리 메모리 침범이 일어날 여지를 크게 줄이게 된다.

페이지 교체 알고리즘

  • 스와핑이 일어날 때 페이지 교체 알고리즘에 의해 페이지가 교체되게 된다.

LFD (오프라인 알고리즘)

  • 가장 좋은 알고리즘이라고 일컫는 알고리즘 (스와핑이 가장 적게 일어남)
  • 이는 가장 먼 미래에 참조되는 페이지와 현재 페이지를 바꾸는 알고리즘(LFD, Longest Forward Distance)이다.
  • ex) 0, 1, 2, 3, 4, 2 이렇게 들어온다고 가정하면 가장 미래에 참조되는 2와 스와핑하는 것을 말한다.
  • 그러나 미래에 사용되는 프로세스를 알지 못하기 때문에 사용할 수 없는 알고리즘이다.
    • 다른 알고리즘과의 성능비교에 대한 상한선을 제공한다.

FIFO

  • First In First Out
  • 가장 먼저 온 페이지부터 교체하는 방법

LRU

  • Least Recently Used
  • 최근에 사용되지 않은 페이지를 바꾸는 방법
  • 참조가 오래된 페이지를 바꾼다.
  • 이를 위해 각 페이지마다 최근 사용한 횟수를 나타내는 자료구조를 따로 만들어야 할 수 도 있다.

NRU

  • Not Recently Used (NUR 이라고도 한다)
  • LRU에서 발전한 알고리즘
  • 일명 clock 알고리즘이라고도 한다.

LFU

  • Least Frequenly Used
  • 가장 참조 횟수가 적은 페이지를 교체하는 알고리즘