[운영체제] 페이지 교체 알고리즘

운영체제에서 페이지 교체 알고리즘은 가상 메모리 관리에 사용되는 중요한 개념이다.

가상 메모리는 물리적은 실제메모르(RAM)보다 큰 프로세스의 주소 공간을 지원하기 위해 사용한다

페이지 교체 알고리즘은 실제 메모리가 부족할 때 어떤 페이지를 디스크로 스왑하고 새로운 페이지를 로그할지 결정하는 방법을 정의한다.

메모리가 가득 차면, 추가로 페이지를 가져오기 위해서 안쓰는 페이지를 Out하고, 해당 공간에 현재 필요한 페이지를 in 시켜야 한다.

여기서 어떤 페이지를 out시켜야할 지 정해야 하는데 기왕이면 수정이 되지 않는 페이지를 선택하는것이 좋다.

out 되는 페이지를 victim page라고 부른다
기왕이면 수정이 되지 않는 페이지를 선택하는 것이 좋다.

페이지 교체 알고리즘 종류

1. FIFO(First-In, First-Out): 가장 간단한 알고리즘으로 가장 먼저 들어온 페이지를 먼저 교체하는 방식이다.

2. LRU(Least Recently Used): 최근에 사용되지 않은 페이지 중에서 가장 오래 전에 사용된 페이지를 교체하는 방식(과거 기반)

3. LFU(Least Frequently Used) : 사용 빈도가 가장 적은 페이지를 교체하는 방식.

4. Optimal: 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내보냄 (미래 예측)

주소 사용되는 기법

주로 LRU가 많이 사용되는 방법이다 이유는 LRU가 상대적으로 간단하면서 성능이 좋다
하지만 실제 시스템에서는 여러 요소(시스템 특성, 메모리 크기 등)을 고려하여 페이지 교체 알고리즘을 선택해야한다.

LFUDA: LRU의 장점과 LFU의 장점을 결합한 알고리즘

교체 방식

1. Global 교체: 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식

2. Local 교체: 메모리 상의 자기 프로세스 페이지에만 교체하는 방식

메모리 매핑 테이블

가상 메모리 시스템에서 메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리한다.