Skip to content

Latest commit

 

History

History
468 lines (356 loc) · 32.2 KB

2. 메모리.md

File metadata and controls

468 lines (356 loc) · 32.2 KB
Raw

메모리

목차

개요

운영체제에서 중요한 메모리에 대해 다룬 문서입니다. 메모리 계층 구조를 이해하고 메모리를 관리하는 기법에 대해 알아보겠습니다.

핵심 용어

  • 캐시: 데이터를 미리 복사해 놓는 임시 저장소
  • 가상 메모리: 메모리 관리 기법의 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 기법
  • TLB(Translation Lookaside Buffer): 메모리와 CPU 사이에 있는 주소 변환을 위한 캐시로, CPU가 페이지 테이블까지 가지 않도록 해 속도를 향상시키는 캐시 계층
  • 스와핑: 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고, 실행할 프로세스를 메모리에 적재하는 메모리 관리 기법
  • 페이지 폴트: CPU가 프로그램을 실행하면서 필요한 페이지가 물리적 메모리에 없는 상황
  • 스레싱: CPU 작업 시간보다 메모리와 스왑 영역 간 페이지 교체에 시간을 많이 소비하는 것

메모리(Memory)

  • 의미: 전자회로에서 데이터나 상태, 명령어 등을 기록하는 장치. 현재 실행되는 프로그램의 명령어와 데이터를 저장한다.
  • 메모리의 종류
    • RAM(Random Access Memory): 임시 데이터 저장 공간으로서, 컴퓨터가 실행 중인 프로그램 및 작업에 필요한 데이터를 저장
      • 메모리라는 용어는 보통 RAM을 지칭
    • ROM(Read Only Memory): 읽기 전용 메모리로서, 주로 컴퓨터나 기타 디지털 장치에 필요한 고정된 데이터나 프로그램을 저장

메모리 계층

메모리 계층은 레지스터, 캐시, 주기억장치, 보조기억장치로 구성되어있다.

image
  • 레지스터: CPU 안에 있는 작은 메모리(휘발성)
  • 캐시(L1, L2, L3): 대용량의 메인 메모리 접근을 빠르게 하기 위해 CPU 칩 내부나 바로 옆에 탑재하여 데이터나 값을 미리 복사해 놓는 임시 저장소(휘발성)
  • 주기억장치(RAM): 컴퓨터에서 수치·명령·자료 등을 기억하는 컴퓨터 하드웨어 장치(휘발성)
  • 보조 기억 장치(HDD, SDD): 주기억장치의 기억 용량을 보조하거나 데이터를 영구 저장하기 위한 기억 장치(비휘발성)

메모리 계층 구조의 특징

  • CPU와 가까운 저장 장치는 빠르고, 멀리 있는 저장 장치는 느리다.
  • 속도가 빠른 저장 장치는 저장 용량이 작고, 가격이 비싸며 사용 빈도가 높다.
  • 속도가 느린 저장 장치는 저장 용량이 크고, 가격이 저렴하며 사용 빈도가 더 낮다. → ‘CPU에 얼마나 가까운가’를 기준으로 계층적으로 나타낼 수 있다.

메모리 계층 구조의 필요성

  1. 참조의 지역성(Locality of reference)
    • 기억 장치 내의 정보를 균일하게 접근(Access)하는 것이 아닌 어느 한 순간에 특정 부분을 집중적으로 참조하는 특성이다.
    • 큰 용량의 메모리를 사용해도 그 안의 모든 데이터에 고르게 접근하지 않는다.
    • 자주 쓰이는 데이터는 전체 데이터 양에 비해 작은 양이므로 자주 쓰이는 데이터를 저장하는 저장소는 그 아래 계층의 저장소보다 작아도 된다. (캐시<메모리<하드디스크)
  2. 경제성
    • 값이 비싼 장치는 꼭 필요한 만큼의 크기만 사용한다.
    • 값이 싼 장치는 넉넉하게 사용한다.
  3. 디코딩 속도
    • 큰 메모리 용량을 사용할 경우, *디코딩하는 데 더 많은 시간이 소요된다.
      • CPU가 빠르게 데이터에 접근하기 위해서는 데이터를 저장하는 메모리의 용량이 작아야 한다.

*디코딩(Decoding): 부호화된 정보를 부호화되기 전으로 되돌리는 처리(복호화)

캐시(Cache)

  • 의미: 데이터를 미리 복사해 놓는 임시 저장소이며, 빠른 장치와 느린 장치에서 속도 차이에 따른 병목 현상을 줄이기 위한 메모리
  • 캐시의 효용: 캐시는 데이터를 접근하는 시간이 오래 걸리는 경우를 해결하고, 무언가를 다시 계산하는 시간을 절약해준다.
  • 예시1: 메모리와 CPU 사이의 속도 차이가 너무 크기 때문에 그 중간에 레지스터 계층을 둬서 속도 차이를 해결한다. → 이러한 레지스터 계층을 캐시 계층이라 할 수 있다.
  • 예시2: 캐시 메모리와 보조기억장치 사이에 있는 주기억장치를 보조기억장치의 캐싱 계층이라 할 수 있다.

캐싱 계층: 속도 차이를 해결하기 위해 계층과 계층 사이에 있는 계층

참조 지역성의 원리(Locality of Reference)

캐시를 직접 설정하는 경우, CPU가 메모리에 접근할 때의 주된 경향을 바탕으로 만들어진 원리를 따른다.

  • 시간 지역성(Temporal Locality)
    • CPU가 최근에 접근했던 메모리 공간에 다시 접근하려는 특성
  • 공간 지역성(Spatial Locality)
    • CPU가 접근한 메모리 공간 근처를 접근하려는 특성

캐시히트와 캐시미스

  • 캐시히트: CPU가 캐시에서 원하는 데이터를 찾은 것
    • 해당 데이터를 제어장치를 거쳐 가져오게 된다.
    • 위치도 가깝고 CPU 내부 버스를 기반으로 작동하기에 속도가 빠르다.
  • 캐시미스: CPU가 캐시에서 원하는 데이터를 찾지 못해 주 메모리로 가서 데이터를 찾아오는 것
    • 해당 데이터를 메모리에서 가져오게 된다.
    • 시스템 버스를 기반으로 작동하기에 속도가 느리다.
  • 캐시 적중률: 캐시 히트 횟수 / (캐시 히트 횟수 + 캐시 미스 횟수)
image

캐시매핑

  • 의미: 캐시가 히트되기 위해 메모리와 캐시를 매핑하는 방법이다.
  • 종류
    • 직접 매핑(Direct Mapping)
      • 메모리 주소와 캐시의 순서를 일치시키는 것이다.
      • 구현이 비교적 간단하지만 충돌이 잦고 캐시 적중률이 낮다.
    • 연관 매핑(Associative Mapping)
      • 메모리 주소와 캐시의 순서를 일치시키지 않는 것이다.
      • 관련 있는 캐시와 메모리를 매핑한다.
      • 충돌이 적고 적중률이 높지만 탐색 속도가 느리다.
    • 직접 연관 매핑(Set Associative Mapping)
      • 직접 매핑과 연관 매핑을 합쳐 놓은 방식 (두 방식의 장점을 모두 취하는 형태)
      • 순서는 일치시키지만 집합을 둬서 저장하며 블록화되어 있기 때문에 검색이 보다 효율적이다.

추가로 웹 브라우저에서 캐시는 어떤 역할을 하는지 살펴보자.

웹 브라우저의 캐시

  • 의미: 사용자의 커스텀 정보나 인증 모듈 관련 사항을 웹 브라우저에 저장하고, 추후 서버에 요청할 때 자신을 나타내는 아이덴티티나 중복 요청 방지에 쓰인다.

    *HTTP는 비연결성, 무상태성의 특징을 가지고 있기 때문에 클라이언트가 서버에 데이터를 요청하고 응답을 받게 되면 연결이 끊기며 다음 요청 시 서버는 클라이언트를 식별하지 못한다.

  • 쿠키

    • 의미: 브라우저에 저장되는 key와 value로 이루어진 작은 크기의 데이터 조각
    • 역할
      • stateless한 HTTP 프로토콜에서 브라우저의 상태 정보 기억할 수 있게 한다.
      • 브라우저는 쿠키를 저장해 놓았다가, 동일한 서버에 재요청 시 저장된 쿠키 함께 전송한다.
      • 쿠키는 주로 두 요청이 동일한 브라우저에 들어왔는지 아닌지 판단할 때 주로 사용된다.
    • 특징
      • 만료기한이 있는 키-값 저장소이다.
      • same site 옵션을 strict로 설정하지 않았을 경우, 다른 도메인에서 요청했을 때 자동 전송된다(🔗참고자료)
      • 4KB까지 데이터 저장이 가능하다.
      • 쿠키를 설정할 때는 document, cookie로 쿠키를 볼 수 없게 httponly 옵션을 거는 것이 중요하다.
      • 클라이언트 또는 서버에서 만료기한 등을 정할 수 있는데, 보통 서버에서 만료기한 정한다.
    • 목적
      • 세션 관리: 서버에 저장해야 할 로그인, 장바구니, 게임 스코어, 접속 시간 등의 개인 정보 관리
      • 개인화: 각 사용자에게 적절한 페이지 표현 (다크모드/라이트모드 등 선호하는 설정)
      • 트래킹: 사용자의 행동과 패턴을 분석하고 기록하는 용도

  • 로컬 스토리지

    • 만료기한이 없는 키-값 저장소
    • 웹 브라우저를 닫아도 유지된다.
    • 클라이언트에서만 수정 가능하다.
    • 5~10MB까지 저장 가능하다.

  • 세션 스토리지

    • 만료기한이 없는 키-값 저장소
    • 탭 단위로 세션 스토리지를 생성한다.
    • 탭을 닫을 때 해당 데이터가 삭제된다.
    • 5~10MB까지 저장 가능하다.

표로 보는 차이점

쿠키 로컬 스토리지 세션 스토리지
용량 4KB 데스크탑: 5M ~ 10MB
모바일: 2.5MB		 데스크탑: 5M ~ 10MB
모바일: 2.5MB
브라우저 HTML4+5 HTML5 HTML5
엑세스 가능 모든 창 모든 창 같은 탭
만료 수동 설정 영구적 탭 닫기
접근 클라이언트+서버 클라이언트 클라이언트
요청과 함께 전송됨 O X X

데이터베이스의 캐싱 계층

데이터베이스 시스템을 구축할 때도 메인 데이터베이스 위에 레디스(Redis) 데이터베이스 계층을 캐싱 계층으로 두어 성능 향상을 유도하기도 한다.
*함께 읽어보면 좋은 자료: https://toss.tech/article/cache-traffic-tip

메모리 관리

가상 메모리(Virtual Memory)

  • 의미: 메모리 관리 기법의 하나로 컴퓨터가 실제로 이용 가능한 메모리 자원을 추상화하여 이를 사용하는 사용자들에게 매우 큰 메모리로 보이게 만드는 것
image

가상 메모리의 등장 배경

  • 큰 용량의 프로그램 실행하기 위함
    • 기존에는 프로세스를 실행하기 위해 실행 코드 전체를 메모리에 로드해야 했고, 메모리 용량보다 더 큰 프로그램은 실행할 수 없었다.
  • 동시에 프로그램 실행하기 위함
    • 또한 멀티 프로세스로 프로그램을 실행시킨다고 가정했을 때 동시에 실행할 수 있는 프로세스 개수의 제한이 컸다.
      더 많은 프로세스를 동시에 실행하려면 더 큰 메모리 용량이 필요한데, 이는 비용적인 한계가 있다.
  • 메모리를 효율적으로 사용하기 위함
    • 프로세스의 실행 코드는 자주 사용되지 않는 방어 코드나 관리 코드가 많아 실제로는 코드의 일부에서만 대부분의 시간을 사용하고 특정 순간에 더 작은 양의 주소 공간을 사용하기 때문에 이러한 방식은 매우 비효율적이었다.

→ 가상 메모리는 이러한 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이다.

주소 바인딩

  • 의미: 논리 주소와 물리 주소를 매핑해주는 작업(= 물리 주소를 결정하는 것)
  • 가상 주소 (Logical address)
    • 가상적으로 주어진 주소로, 프로세스마다 독립적으로 가지는 주소 공간이다.
    • 각 프로세스마다 0번지부터 시작한다.
    • CPU는 가상 주소를 바라본다.
  • 물리 주소 (Physical address)
    • 메모리에 실제 올라가는 위치
    • 베이스 레지스터에 논리 주소를 더한 값이다.

주소 바인딩 종류
각 프로그램이 가지고 있던 논리적 주소가 물리적 주소로 언제 결정되는가에 따라 세 가지 형태로 나뉜다.

  • 컴파일 타임 바인딩
    • 컴파일 시점에 물리 주소가 결정되는 것 (물리 주소가 컴파일 시 알려짐)
    • 시작 위치 변경 시 재컴파일
    • 컴파일러는 절대 코드를 생성 컴퓨터 안에서 프로그램이 하나만 실행되는 환경에서 쓰였음
  • 로드 타임 바인딩
    • 프로그램 실행이 시작되고 메모리에 올라갈 때 물리 주소가 결정되는 것 (컴파일 타임에는 논리 주소만 결정된 상태)
    • 로더가 메모리 주소를 부여하고 프로그램이 종료될 때까지 물리 주소 고정됨
    • 비어있는 위치를 실행시에 어느 위치든 올라갈 수 있음
  • 런 타임 바인딩(실행 시간 바인딩)
    • 프로그램이 실행된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
    • CPU가 주소를 참조(요청)할 때마다 바인딩을 점검함
    • 주소변환용 하드웨어 지원이 필요함 → MMU
      → 가상 메모리는 런 타임 바인딩을 사용하고, 이는 주소 변환용 하드웨어 장치인 MMU의 지원을 필요로 한다.

MMU (Memory Management Unit)

  • 의미: 가상 주소를 물리 주소로 매핑해주는 하드웨어 장치
  • 배경: 가상 메모리는 런 타임 바인딩을 사용해야 하기 때문에 주소변환용 하드웨어인 MMU가 필요하다.
    • 논리 주소로 실제 메모리에 접근하기 위해 빠른 주소 변환이 필요한데, 이를 MMU가 도와준다.
  • 역할: 논리 주소와 베이스 레지스터 값을 더하여 논리 주소를 물리 주소로 변환한다.
image
  • 베이스 레지스터
    • 물리 주소의 시작점(최솟값)을 저장한다.
  • 한계 레지스터
    • 논리 주소의 최댓값을 저장한다.
    • 한계 레지스터의 값보다 큰 주소를 참조할 수 없게하여 프로그램 영역을 침벌할 수 있는 명령어의 실행을 막는다(메모리 보호).
    • 베이스 레지스터 값 ≤ 프로그램의 물리 주소 범위 ≤ 베이스 레지스터 + 한계 레지스터 값
image

페이지 테이블

  • 의미: 페이징 기법에서 사용되는 자료구조로서, 프로세스의 페이지 정보를 저장하고 있는 테이블이다.

    • 하나의 프로세스는 하나의 페이지 테이블을 가진다.

  • 역할: 물리 주소에 프로세스가 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치되도록 한다.

    • 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표 역할을 한다.

  • 페이지 테이블에 담기는 정보

    • 색인 : 페이지 번호.
    • 내용 : 해당 페이지에 할당된 물리 메모리(프레임)의 시작 주소. 이 시작 주소와 페이지 주소를 결합하여 물리 메모리 주소를 알 수 있다.

  • 페이지 테이블 엔트리(Page Table Entry, 줄여서 PTE): 페이지 테이블의 레코드 (기억 장치)

    • 페이지 기본주소(Page base address)
    • 플래그 비트
      • 접근 비트(Accessed bit) : 페이지에 대한 접근이 있었는지를 나타낸다.
      • 변경 비트(Dirty bit) : 페이지 내용의 변경이 있었는지를 나타낸다.
      • 존재 비트(Present bit) : 현재 페이지에 할당된 프레임이 있는지를 나타낸다.
      • 읽기/쓰기 비트(Read/Write bit) : 읽기/쓰기에 대한 권한을 표시한다.

TLB

TLB의 등장 배경: CPU는 페이지 테이블을 참조하기 위해 1회를, 이후 페이지를 참조하기 위해 1회를, 총 2회 메모리에 접근하게 된다. 이로 인해 메모리 접근 시간이 늘어난다는 문제점이 있다.

image
  • 의미: 메모리와 CPU 사이에 있는 테이블의 캐시 메모리
  • 페이지 테이블의 일부를 가져와 저장한다.
  • 페이지 테이블에 있는 리스트를 보관하며 CPU가 페이지 테이블까지 가지 않도록 해 속도를 향상시킨다. → 불필요한 메모리 접근을 줄일 수 있다.

페이지: 가상 메모리를 사용하는 최소 크기 단위

프레임: 실제 메모리를 사용하는 최소 크기 단위

스와핑(Swapping)

image
  • 의미: 페이지 폴트가 발생했을 때 현재 사용되지 않는 프로세스들을 보조기억장치의 스왑 영역으로 내보내고, 그렇게 해서 생긴 빈 공간에 새 프로세스를 적재하는 것
  • Swap In: 스왑 영역에서 메모리로 이동하는 것
  • Swap Out: 메모리에서 스왑 영역을 이동하는 것
  • 스왑 영역: RAM의 용량이 가득 차게 될 경우 사용되는 여유 공간. 디스크에 존재하지만 파일 시스템과는 별도로 존재한다(RAM의 확장 개념)
    • 스왑 영역은 외부 저장장치에 존재하기 때문에 스와핑이 발생하면 OS에 의해 IO작업이 일어난다.
    • 공간효율성보다는 시간효율성을 고려한 저장이 일어나서 일반적으로 파일시스템에 접근하는 것보다 빠르다.

페이지 폴트(Page Fault)

  • 의미: 프로세스의 주소 공간에는 존재하지만 실제 메모리인 RAM에는 없는 데이터나 코드에 접근했을 때 발생하는 현상
  • 페이지 폴트와 그로 인한 스와핑 과정
    1. 어떤 명령어가 유효한 가상 주소에 접근했으나 해당 페이지가 메모리상에 없다면 트랩이 발생되어 운영체제에 알린다.
    2. 운영체제는 실제 디스크로부터 사용하지 않은 프레임을 찾는다.
    3. 해당 프레임을 실제 메모리에 가져와서 페이지 교체 알고리즘을 기반으로 특정 페이지와 교체한다. → 이때 스와핑이 일어남.
    4. 페이지 테이블을 갱신시킨 후 해당 명령어를 다시 시작한다.
image

→ 페이지 폴트가 자주 발생하면 처리 시간이 늘어나 컴퓨터 성능을 저하시킨다.

페이지 폴트가 자주 발생하는 이유는?

  • 부적절한 페이지 교체 알고리즘을 사용해서 → 페이지 폴트가 적게 발생하도록 설계된 페이지 교체 알고리즘을 사용해야 한다.
  • 프로세스가 사용할 수 있는 프레임 자체가 적어서 → 그렇기 때문에 메모리가 작은 컴퓨터에 비해 메모리가 큰 컴퓨터가 성능이 좋다.

스레싱(Thrashing)

image
  • 의미: 스레싱은 메모리의 페이지 폴트율이 높아 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 컴퓨터 성능이 저하되는 문제
  • 해결 방법
    • 메모리 늘리기 (하드웨어)
    • HDD를 SSD로 바꾸기 (하드웨어)
    • 작업 세트(Working Set)
      • 프로세스의 과거 사용 이력인 지역성(locality)을 통해 결정된 페이지 집합을 만들어서 미리 메모리에 로드하는 것
      • 탐색 비용 및 스와핑을 줄일 수 있다.
    • PFF(Page Fault Frequency)
      • 페이지 폴트 빈도를 조절하는 방법.
      • 상한선과 하한선을 만들어서 페이지 폴트 빈도가 상한선에 도달하면 프레임을 늘리고, 하한선에 도달하면 프레인을 줄인다.

메모리 할당 방식의 분류

메모리에 프로그램을 할당할 때는 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당하는데, 연속 할당과 불연속 할당으로 나뉜다.

image

메모리 할당 - 연속 할당

  • 의미: 메모리에 연속적으로 공간을 할당하는 것
  • 고정 분할 방식(Fixed partition allocation)
    • 의미: 물리적 메모리를 미리 나누어 관리하는 방식
    • 동시에 메모리에 올릴 수 있는 프로그램의 수가 고정되어 있으며 수행 가능한 프로그램의 최대 크기 또한 제한된다는 점에서 가변분할 방식에 비해 융통성이 떨어진다.
    • 내부 단편화 발생
  • 가변 분할 방식(Variable partition allocation)
    • 의미: 매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용하는 방식
    • 메모리에 적재되는 프로그램의 크기에 따라 분할의 크기, 개수가 동적으로 변한다.
    • 내부 단편화는 발생하지 않지만 외부 단편화 발생할 수 있다.
    • 가변 분할 방식 종류
      • 최초적합(firtst-fit): 운영체제가 홀을 검색하다 발견하면 바로 할당(검색 최소화, 빠른 할당)
      • 최적적합(best-fit): 운영체제가 홀을 모두 검색해본 뒤, 프로세스의 크기 이상인 홀 중 가장 작은 홀에 할당
      • 최악적합(worst-fit): 운영체제가 홀을 모두 검색해본 뒤, 프로세스의 크기 이상인 홀 중 가장 큰 홀에 할당

홀(hole): 할당할 수 있는 비어 있는 메모리 공간


내부 단편화, 외부 단편화란?

  • 내부 단편화 (Internal Fragmentation) 필요한 양보다 더 큰 메모리가 할당되어 할당 된 메모리 내부에 사용하지 않는 메모리 공간이 발생하는 현상을 말한다.

    image

  • 외부 단편화 (External Fragmentation) 프로세스들이 실행되고 종료되길 반복하며 메모리 중간중간 빈 공간이 발생하는데, 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 외부 단편화라고 한다.

    image

메모리 할당 - 불연속 할당

  • 의미: 메모리를 연속적으로 할당하지 않는 것
  • 현대 운영체제에서는 메모리를 연속적으로 할당하지 않는 불연속 할당 방식을 사용하며, 이는 연속 할당에서 발생하는 내부 단편화, 외부 단편화 문제를 해결하고 가상 메모리 기법을 가능하게 해준다.
  • 불연속 할당 기법
    • 페이징(paging)
      • 의미: 프로세스의 논리 주소 공간을 가상 메모리를 사용하는 최소 크기 단위인 페이지라는 일정 단위로 자르고 메모리의 물리 주소 공간을 페이지와 동일한 일정 단위인 프레임으로 자른 뒤, 페이지를 프레임에 할당하는 가상 메모리 관리 기법
      • 프로세스를 실행하는 데 해당 프로세스를 이루고 있는 모든 페이지가 반드시 필요한 것은 아니기 때문에 스와핑을 통해 메모리를 효율적으로 사용한다. (물리 메모리보다 큰 프로세스를 실행할 수 있음)
      • 홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해진다.
      • 외부 단편화 문제를 해결할 수 있다.
    • 세그멘테이션(segmentation)
      • 의미: 페이지 단위가 아닌 의미 단위인 세그먼트로 나누는 방식
      • 공유와 보안 측면에서 장점을 가지지만, 홀 크기가 균일하지 않다.
    • 페이지드 세그멘테이션(paged segmentation)
      • 의미: 프로그램을 의미 단위인 세그먼트로 나누고, 임의의 길이가 아닌 동일한 크기의 페이지 단위로 나누는 방식
      • 공유와 보안 측면에서 장점을 가진다.

페이지 교체 알고리즘

페이지를 적재하다 보면 메모리가 가득 차게 되고, 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 한다. 이때, 어떤 페이지를 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다.

→ 페이지 폴트가 가장 적게 일어나도록(스와핑이 적게 일어나도록) 설계되어야 한다.

  • 오프라인 알고리즘
    • 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 교체하는 알고리즘이며, 가장 좋은 방법이다.
    • 한계: 미래에 사용되는 프로세스를 예측할 수 없다.
    • 역할: 사용할 수 없는 알고리즘이지만, 가장 이상적인 알고리즘이기에 다른 알고리즘과의 성능 비교에 대한 상한 기준(upper_bound)을 제공한다.

  • FIFO(First in First out)
    • 메모리에 가장 먼저 올라온 페이지를 교체한다. (가장 단순한 방식)
image

→ 프로그램 실행 내내 사용될 페이지는 먼저 적재되었다고 해서 내보내면 안되기 때문에 성능 측면에서 좋은 방식은 아니다.

  • LRU(Least Recently Used)
    • 가장 오랫동안 사용되지 않은 페이지를 교체한다.
    • 가장 오래된 페이지라는 것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 한다는 문제점이 있다.
image

  • NUR(Not Used Recently)

    • 최근에 사용하지 않은 페이지를 교체한다.
    • 참조 비트를 사용하여 교체 대상 페이지를 찾는다.
      1. 프레임 내 페이지가 참조되면 1로 자동 세팅된다.
      2. 페이지 요청이 들어오면 프레임을 시계 방향으로 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
      3. 참조 비트가 0인 페이지를 만나면 해당 페이지 교체한다.
    image

**LRU에서 파생된 알고리즘으로, clock 알고리즘이라고도 한다.

  • LFU(Least Frequently Used)
    • 과거 참조 횟수가 가장 적은 페이지를 교체한다.
    • Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
    • Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식
image

참고 자료