(6) 가상 메모리 (요구 페이징/ 페이지 교체 알고리즘)

TL;DR

• 가상 메모리란? 물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술
• 요구 페이징이란? 프로세스가 필요로 하는 데이터를 프로세스가 요청할 때 메모리에 적재하는 방법
• 페이지 폴트란? 프로세스가 요구한 페이지가 현재 메모리에 없는 상황
• 페이지 폴트 알고리즘이란? 페이지 폴트(Page Fault)가 발생할 시 어떤 프레임을 선택하여 교체할지 결정하는 방법

 

 

 

가상 메모리

물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술이다.

 

🔺 가상 메모리의 필요성

프로세스가 실행되는 코드 전체를 물리 메모리에 존재시킨다면, 메모리 용량보다 큰 프로그램은 실행될 수 없다. 또한 여러 프로그램이 동시에 메모리에 올라갈 경우, 용량 문제나 성능 이슈가 발생한다. 하지만 실제로는 코드의 일부분에서만 시간을 사용하고 특정 순간에는 항상 작은 양의 주소 공간을 사용한다.

가상 메모리는 이러한 물리적 메모리의 한계를 극복하기 위해 나온 기술이다. 프로세스를 실행할 때 실행에 필요한 일부만 메모리에 로드하고 나머지는 디스크에 두는 것이다. 하드디스크에 존재하지만, 메모리 관리자가 관리하는 영역을 스왑 영역이라고 한다. 즉, 가상 메모리의 크기는 물리 메모리의 크기와 스왑 영역을 합한 크기이다.

 

🔺 가상 메모리 시스템이 하는 일

프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터에 접근할 때 물리 주소로 바꿔주는 개념이다.

• virtual address (가상 주소) : 프로세스가 참조하는 주소.
• physical address (물리 주소) : 실제 메모리 주소
• MMU(Memory Management Unit) : CPU 코드 실행 시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소값으로 변환해주는 하드웨어 장치. 이러한 과정을 동적 주소 변환(Dynamic Address Translation, DAT)라고 한다.

 

✅ 요구페이징(Demand Paging)

• 프로세스가 필요로 하는 데이터를 프로세스가 요청할 때 메모리에 적재하는 방법이다.
• 메모리가 꽉 차면 관리하기 어려우므로 가급적 적은 양의 프로세스만 유지한다.
  -> 메모리를 효율적으로 관리
• 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행한다.
  -> 응답 속도 향상

 

✅ 페이지 교체 알고리즘

• 페이지 폴트(Page Fault)가 발생할 시 어떤 프레임을 선택하여 교체할지 결정하는 방법이다.
• 요구페이징에서 언급한대로 프로그램을 실행할 때 , 모든 프로세스가 메모리에 올라오는 것이 아니다. 프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재(page fault)가 발생한다. 페이지 부재 발생 시 원하는 페이지를 보조저장장치에서 가지고 온다. 하지만, 만약 물리 메모리가 모두 사용중이라면, 페이지 교체가 이루어진다.
• 메모리에서 앞으로 사용할 가능성이 적은 페이지를 교체 대상 페이지로 선정해야 페이지 부재를 줄이고 시스템의 성능을 향상시킬 수 있다.

 

🔺 페이지 교체 알고리즘의 성능 평가 기준

같은 메모리 접근 패턴을 사용하는 두 알고리즘을 실행하여 페이지 부재 횟수를 세어 볼 수도 있고, 평균 대기 시간을 측정할 수도 있고, 전체 작업에 걸리는 시간을 비교할 수도있다. 기본적으로는 페이지 부재 발생 비율을 줄이는 것을 목표로 한다.

 

🔺 페이지 교체 알고리즘 종류

1) 최적 페이지 교체 알고리즘(Optimal page replacement algorithm)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 미래의 접근 패턴을 보고 대상 페이지를 결정하는 알고리즘이다.
• 주로 비교 연구 목적을 위해 사용한다. 
• 장점 : 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.
• 단점 : 구현이 어렵다. 미래의 접근 패턴을 안다는 것이 실제로는 불가능하기 때문이다.

 

2) FIFO(First In First Out) 페이지 교체 알고리즘

• 시간상 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 교체하는 것이다.
• 장점 : 가장 간단한 알고리즘으로 구현하기 쉽다. (큐로 구현)
• 단점 : 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다.

• 특징 : 페이지 부재율이 높을 경우, 페이지 프레임을 늘리면 직관적으로 생각할 때 페이지 부재율이 감소할 것으로 예상된다. 그러나 오히려 페이지 부재율이 증가하는 이상현상을 Belady가 발견했는데, 이를 Belady의 이상현상이라고 한다.

 

3) LRU(Least Recentle Used) 페이지 교체 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 선택하는 것

✔️ 페이지 접근 시간에 기반한 구현

• 페이지에 접근한 시간을 기록하여 구현한다.
• 일반적으로 FIFO 알고리즘 보다 우수하고 최적 페이지 알고리즘 보다 성능이 떨어진다.
• 숫자를 표시하기 위해추가 공간을 사용해야 한다.

 

✔️ 참조 비트 시프트 방식 구현

• 참조 페이지에 일정 크기의 참조 비트를 만들어 사용
• 각 페이지에 일정한 크기의 참조 비트를 만든다. 초깃값은 0이고 접근할 때마다 1로 바뀐다. 그리고 주기적으로 오른쪽으로 shift한다.

 

4) LFU(Least Frequently Used) 페이지 교체 알고리즘

• 참조 횟수가 가장 적은 페이지를 교체하는 방법
• 활발하게 사용되는 페이지가 참조 횟수가 많을 것이라는 가정에 기반하여 만들어진 알고리즘
• 최적 페이지 교체를 제대로 근사하지 못한다.
• 페이지 접근 횟수를 표시해야 하기 때문에 추가 공간이 필요

 

5) NUR(Not Used Recently) 페이지 교체 알고리즘

• 최근에 미사용된 페이지를 교체하는 알고리즘이다.  = LRU 알고리즘을 근사하는 알고리즘
• LRU, LFU 페이지 교체 알고리즘과 성능은 유사하면서 불필요한 메모리 낭비를 해결한 알고리즘
• 알고리즘에서 접근 시간이나 접근 빈도를 정확한 값으로 저장하는 것은 공간만 많이 차지할 뿐 큰 의미가 없다. 따라서 이러한 경향을 반영하여 적은 오버헤드로 적절한 성능을 보장하는 알고리즘이다.
• 페이지마다 참조 비트와 변경 비트를 가진다.

 

6) 2차 기회 페이지 교체 알고리즘

• FIFO 페이지 교체 알고리즘을 보완한 것이다.
• 마찬가지고 큐를 사용
• 차이점은 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 마치 새로 적재된 것과 같은 순서를 적용한다는 것 (기회를 한번 더 줌)

 

7) 시계 알고리즘(clock algorithm)

• FIFO 페이지 교체 알고리즘을 보완한 것이다.
• 2차 기회 페이지 교체 알고리즘과의 차이점은 원형큐를 사용한다.
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용한다. 이 포인터가 큐의 맨 바닥으로 내려가면 다음 번에는 다시 큐를 가리킨다.
• 참조 비트가 하나씩 추가된다. 참조 비트의 초깃값은 0이다. 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경된다.