가상메모리와 페이지 교체 알고리즘

가상 메모리(Virtual Memory) 개념

물리 메모리의 한계(크기 등)을 극복하기 위해 사용한다. 핵심은 프로세스 or 프로그램 전체를 메모리에 올리는 것이 아니라, 필요한 부분만 메모리에 적재하는 것이다. 적재 여부는 페이지 테이블에 표시된다. 실행될 가능성이 낮은 코드, 행렬 리스트와 같이 필요한 크기 이상으로 선언된 변수 등은 굳이 적재시키지 않는다. 메모리가 꽉 차면 무슨 기준으로 페이지를 쫓아내야 하는가 => 참조 지역성

---

참조 지역성(Locality of reference)

동일한 값 또는 해당 값에 관계된 스토리지 위치가 자주 액세스 되는 특성을 말한다. 가상 메모리 방식이 효과적임을 뒷받침하는 원리이다. 시간, 공간, 순차 지역성이 있다. 

1. 공간 지역성: 특정 클러스터의 기억 장소들에 대해 참조가 집중적으로 이루어지는 것. 참조된 메모리 근처의 메모리를 참조.ex. 배열 순회, 순차적 코드 실행, 관련 변수 선언, 데이터베이스 파티션

2. 시간 지역성: 최근 사용되었던 장소들이 집중적으로 사용되는 것. 참조했던 메모리를 빠른 시간 안에 다시 참조. ex. 순환, 서브루틴, 스택, 계산에 사용되는 변수, LRU

3. 순차 지역성: 데이터가 순차적으로 액세스되는 것. 별도의 유형으로 구분하지 않고 공간 지역성에 포함시키기도 한다. ex. 배열 데이터

---

가상 메모리는 시스템 라이브러리가 여러 프로세스끼리 공유될 수 있도록 지원한다. 각 프로세스는 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가 있는 물리 메모리 페이지들은 모든 프로세스에 공유된다. 프로세스들은 이를 통해 메모리를 공유하고, 메모리를 통해 통신할 수 있다. 

 

요구 페이징 기법

가상 메모리 기법은 프로세스의 주소 공간을 적재하는 단위에 따라 요구 페이징 기법과 요구 세그멘테이션 기법으로 나뉜다.

요구 페이징 기법은 필요한 페이지가 생기면 그때 페이지를 메모리로 이동시키는 것이다. 예측 페이징 기법과 달리 실제 필요한 페이지 만을 적재하기 때문에 페이지 결정에 대한 오버헤드가 최소화된다. (↔ 예측 페이징 기법은 현재 요구되지는 않지만 곧 사용될 것으로 예측되는 페이지를 미리 옮겨놓는 것이다.)

 

페이지 부재 및 교체

페이지 부재는 필요한 페이지가 메모리에 없어 유효-무효 비트가 무효로 설정되어 있는 것을 뜻한다. 페이지 부재가 발생하면 디스크로부터 페이지를 읽어와야 하는데 해당 과정에서 막대한 오버헤드가 발생한다. 따라서 필요한 페이지를 그때그때 적재시키는 요구 페이징 기법에서 페이지 부재 발생률은 성능에 있어서 큰 비중을 차지한다. -> page fault 발생 비율을 줄이는 것을 목표

만약 필요한 페이지를 적재해야 하는데 메모리가 충분하지 않다면, 메모리에 있는 페이지 중 가장 쓸모없어 보이는 것을 골라 스왑 영역으로 내보내는 페이지 교체가 일어난다. 교체할 페이지를 선정할 때는 대상이 될 프레임의 범위에 따라 전역 교체와 지역 교체로 나눌 수 있다. 전역 교체는 모든 페이지 프레임이 교체 대상이 되는 것이고, 지역 교체는 현재 수행중인 프로세스에 할당된 프레임 내에서만 페이지 교환을 수행하는 방식이다.

 

페이지 교체 알고리즘

OPT(Optimal) / 최적 알고리즘

각 페이지의 호출 순서를 미리 알고있다는 가정 하에 돌아가는 알고리즘이다. 가장 나중에 호출될 페이지를 내보내는 방식이다. 실제로 구현하기 힘들다.

FIFO(First In First Out)

가장 먼저 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.

LRU(Least Recently Used)

가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다. 

LFU(Least Frequently Used)

참조 횟수가 가장 적은 페이지를 교체하는 알고리즘이다.

NUR(Not Used Recently)

LRU와 비슷한 알고리즘이다. 오랫동안 참조하지 않은 페이지 중 하나를 선택하지만 가장 오래된 페이지라는 보장은 없다.

MFU(Most Frequently User)

LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

 

스레싱 - 페이지 교체 알고리즘의 문제

메모리가 꽉 찬 후에는 기존 프로그램을 스왑 영역으로 옮겨야 한다. 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱이라고 한다.

스레싱은 메모리 크기가 일정할 경우 멀티 프로그램의 수와 관련이 있다. 동시에 실행하는 프로그램의 수를 멀티 프로그래밍 정도라고 하는데, 이것이 과도하게 높아지면 스레싱이 발생한다. 프로그램의 수가 적을 때는 CPU 사용률이 계속 증가하다가 메모리가 꽉 차면 CPU가 일하는 시간보다 페이지를 내보내고 가져오는 작업이 빈번해진다. 결국 CPU가 작업할 수 없는 상태가 되는데, 이를 스레싱 발생 지점이라고 한다.

이를 해결하기 위해서는 1. 다중 프로그래밍 정도를 적정 수준으로 유지, 2. 페이지 부재 빈도를 조절, 3. working set(지역성을 기반으로 가장 많이 쓰이는 페이지 집합)을 유지, 4. 일부 프로세스를 중단 하는 등의 방법이 있다.

 

참고

http://blog.skby.net/%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-virtual-memory/

https://velog.io/@adam2/OS%EA%B8%B0%EC%B4%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EA%B4%80%EB%A6%AC%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%8E%98%EC%9D%B4%EC%A7%80-%EB%B6%80%EC%9E%AC-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B1%84-%EC%8A%A4%EB%A0%88%EC%8B%B1