[260213금] 페이지 교체 알고리즘에 대해서 설명해 주세요.

가상 메모리 관리 기법(Virtual Memory Management) 

- 프로그램 일부만을 메모리에 적재하여 실제 사용 가능한 물리 메모리 양보다 큰 프로세스를 실행할 수 있도록 하는 기법

- 다양한 관리 기법 중 하나가 페이징

 

페이징(Paging)

- 메모리의 물리 주소 공간을 프레임 단위로 나눈 이후, 프로세스의 논리 주소 공간을 페이지로 나누어 프레임에 할당하는 방식

- 요구 페이징 : 프로세스를 메모리에 적재할 때, 실제로 필요한 때만 페이지를 메모리에 적재하는 것

- 요구 페이징을 사용하는 운영 체제에서 새로운 페이지를 할당하려고 하는데, 공간이 부족한 경우 메모리에 존재하는 다른 페이지와 신규 페이지를 교체해야 한다. 이때 교체 대상을 결정하는 방법을 페이지 교체 알고리즘이라고 한다. 

- 페이징을 통해 외부 단편화를 해결할 수 있음.(그러나 내부 단편화가 발생함)

 

페이지 교체 알고리즘

1. FIFO :적재된 페이지 순서대로 교체하는 알고리즘

2. OPT : 앞으로 가장 나중에 사용될 페이지를 교체, 사용자 패턴을 파악하기 어렵기에 이론적 알고리즘으로 분류 

3. LRU : 가장 오래 사용되지 않은 페이지를 교체

4. LFU : 가장 적게 사용된 페이지를 교체 

5. NUR : 최근에 사용된 적 없는 페이지를 교체

 

✨ 외부 단편화 (External Fragmentation)

메모리 상의 전체 빈 공간은 충분한데, 정작 필요한 크기의 연속된 공간이 없어서 프로세스를 올리지 못하는 현상입니다.

원인 : 프로세스들이 메모리에 들어오고 나가기를 반복하다 보면, 사이사이에 애매한 크기의 빈 공간들이 생기기 때문

 

✨내부 단편화 (Internal Fragmentation)

프로세스에게 필요한 크기보다 더 큰 메모리 조각을 할당해줘서, 그 조각 안에서 메모리가 낭비되는 현상입니다.

원인 : 페이징(Paging) 기법처럼 메모리를 일정한 크기(프레임)로 딱딱 나누어 관리할 때 발생. 프로세스 마지막 조각의 크기가 프레임 크기보다 작을 때 그 남는 공간이 내부 단편화가 됩니다.